Опубликовано также в моей колонке на Информационном Буме под названием «Вздумалось козлику».

 Впервые эту игру я увидел в старинном (за 1962 год, кажется) журнале «Техника – молодежи» будучи учеником девятого класса. Естественно, последовал игровой бум, играли на всех уроках и переменах в школе, во дворе и дома, вовлекая всех в это чудо.

С тех пор прошло более трети века, играл в институте на лекциях, на отдыхе, наблюдая периодические всплески интереса к игре. На рабочем столе под стеклом лежало поле для игры, созданное на Лиспе в Автокаде. Называется игра «Козлик и волки». О ней писал журнал «Наука и жизнь» лет назад. Но во всех публикациях просто приводились правила игры, не вдаваясь в самые настоящие чудеса, заложенные в ней. Правила простейшие: на поле из шестиугольников (рис1) двигаются (ходят по очереди) пять волков и один козлик. Волки могут двигаться только вперед, а козлик в любом из шести направлений на соседнюю ячейку. Начальная позиция и варианты допустимых ходов показаны на рис. 2.  Задача волков – зажать козлика, чтобы ему некуда было ходить (и, наверное, съесть…), а задача козлика – прорваться через цепь волков.

Теперь, покончив со вступлением, перейдем к справедливому вопросу читателя: «В чем же, как теперь говорят, фишка?» Ведь ясно, что у волков преимущество – двигай их потихоньку на свободные ячейки, и постепенно «припрешь» козлика. И, действительно, первое время волки побеждают. Но, только первое время! Постепенно выясняется, что козлик силен, и выиграть его почти невозможно. В позиции на рисунке 3 при ходе волков они проигрывают, так как их цепь разрывается. В позиции на рисунке 4 (так называемый «ковшик») то же самое – если сейчас ход волков, то они проиграли. При игре волки должны избегать таких позиция, а козлик, естественно, стремиться к ним, создавать их. И, все-таки, волки побеждают, но, при сильной игре козлика они должны выбирать единственные правильные ходы, что не очень то просто.

Друзья, оторвитесь на часик от мышки и монитора (давно ли вы играли не с компьютером?), разлинуйте поле, причем не обязательно вырисовывать шестиугольники, можно от руки нарисовать касающиеся кружочки. Идеальными волками могут служить канцелярские кнопки (с соблюдением техники безопасности) а козликом – монетка. Найдите напарника (жертву) из сотрудников, сокурсников, сокамерников (не обязательно на «с», можно внуков – кому кто подвернется) и поиграйте.

После получения некоторого опыта вам понятней будут следующие рассуждения. Кто первый ходит? Вообще-то волки. Но так как при идеальной игре волки побеждают, то право первого хода можно отдать козлику, это увеличит его шанс на победу. Если волки у вас все равно часто побеждают, сдвиньте начальную позицию козлика поближе к волкам и он будет непобедим.

В чем сложности волков? В том, что они должны перестраивать свою цепь с четырехъячеечного ряда на пятиячеечный и при этом не разрываться. Им надо стараться, чтобы при расположении в четырехъячеечном ряду пятый волк был бы не сзади ряда, а впереди его. Еще волки должны оставлять «резервный» ход для возможности передачи очереди хода козлику.

Поле может быть не только с пяти и четырехъячеечными рядами, как в нашем примере, но и с шести и пятиячеечными. На таком поле шансы выиграть у козлика уменьшаются, так как волки имеют дополнительную свободу для маневров. Когда ваш класс возрастет, попробуйте поиграть на доске с четырех и трехъячеечными рядами, сила козлика на ней превышает силу волков.

Количество рядов на доске также можно менять, уменьшая или увеличивая, уменьшая или увеличивая соответственно шансы козлика на прорыв цепи волков.

Эта игра известна и на простой шахматной доске (точнее, шашечной, так как ведется только на черных полях), но там она тривиальна, и только переход на шестиугольное поле оживляет ее.

Задание на дом. Подумайте над вопросами.

Можно ли вместо шестиугольников использовать пяти- семи или восьмиугольники?

Если поле замкнуть по горизонтали, как цилиндр, то чьи шансы на победу увеличатся?

Как бы вы раскрасили поле, выделив узловые, на ваш взгляд, поля для волков?

Если волки слишком часто побеждают, то можно разрешить козлику один из двух ходов делать на два поля – уравняет ли это силу игроков?

 

Продолжаем...

Странно, что до сих пор нет этой игры на компьютере, она же просто просится для программирования. (Я и сам пытался, еще на Синклере...) Здесь начинает работать эффект, заключающийся в том, что обдумывание алгоритма рализации игры  приятнее, чем сама игра. Начните, и получите удовольствие даже от предварительных рассуждений.

Самое время вспомнить о Самообучающихся машинах. О самодельной самообучающейся машине рассказал Мартин Гарднер в книге «Математические досуги». Например, для игры в крестики-нолики – предположим, машина ходит первая и все нечетные ходы ее. Машина представляет собой набор спичечных коробков, на которых нарисована позиция в игре и разными цветами показаны возможные ходы. В коробке лежат бусинки, цвета которых соответствуют цветам вариантов ходов. При ходе машины достают случайно выбранную бусинку и ходят в соответствии с ее цветом. Обучение состоит в том, что если машина выигрывает, то в каждый игравший коробок добавляют по бусинке того цвета, который играл в этой партии, а при проигрыше соответствующие бусинки удаляют. Результаты потрясающие – после нескольких сыгранных партий машина становится непобедима.

Этот остроумный метод обучения так и просится для программной реализации, вам не только не придется возиться с коробками, но и не надо будет тратить время на обучение – ведь программа может обучаться играя сама с собой! Опять же это верный шаг в направлении создания Искусственного Интеллекта, ведь этот самый ИИ должен самообучаться. И лучшего объекта для самообучающихся программы, чем Волки и козлик не найти.

Если же вам в принципе неприятны разговоры о самообучении, то можно построить программу, играющую, например, за козлика, на простом переборе всех вариантов, тем более, что количество их вполне обозримо.  Для уменьшения вариантов и увеличения силы козлика можно использовать поле с четырьмя и тремя полями в рядах. Для удобства анализа позиции каждое поле можно назвать буквой английского алфавита. Букв, как известно, 26, полей 25, букву О исключим из-за похожести на нуль.

Теперь начальная позиция волков будет выглядеть как строка символов «WXYZ», а первый ход волков может создать шесть ситуаций: TXYZ, WTYZ, WUYZ, WXUZ, WXVZ и WXYV. На втором ходу первый и последний варианты имеют по шесть продолжений, а остальные всего по три, но это не значит, что второй ход волков создаст 24 разных позиций, так как многие позиции совпадают. Предложенный метод облегчает анализ ситуации, сводящийся к рассмотрению строки из четырех букв. Не надо бояться обилия вариантов, так как в подавляющем большинстве из них волки проигрывают, не пройдя второй линии. Облегчает анализ и то, что первые три-четыре хода козлика с поля F практически не зависят от ходов волков, ну а уж после надо крепко думать.

Заложив в программу все варианты вы убедитесь, что теоретически волки сильнее, но для победы им надо совершать единственные правильные ходы. Тот же, кто не знает их будет недоумевать, что не в силах сладить с осколками кремния и мотком проводов, из которых, собственно, и состоят наши любимцы.

Ну, вот и все. Удачной охоты, как говорят волки.