— Знаешь свой главный грех?
— Какого черта? я обожаю все семь…
   но сейчас… я готов дать волю гневу!
 
        Малькольм Рейнольдс "Миссия Серенити" 


По мере того, как мой личный "рейтинг неприятностей" стремительно движется к завершению, становится всё сложнее добиваться от Zillions of Games требуемого поведения. Некоторые правила очень легко сформулировать, но они способны попортить разработчику немало крови. «Правило гнева» — одно из них.

4. За фук!

Возможность снятия с доски фигур (своих или противника) бывает очень полезна. За примерами далеко ходить не надо. Я уже писал об игре "Фокус", описанной Мартином Гарднером в его "Математических досугах". Играть в неё не просто, но удовольствие от игры может несколько омрачить факт наличия очень простой беспроигрышной стратегии для второго игрока. Повторяя каждый ход противника симметрично относительно центра доски, он может затянуть игру до бесконечности:



Каждым своим ходом, второй игрок восстанавливает центральную симметрию, нарушенную предыдущим ходом. Поскольку фигуры не могут перемещаться по диагоналям, первый игрок не может нарушить симметрию невосстановимым (за один ход) образом, следовательно — его противник не может проиграть, в точности повторяя все ходы. Очевидно, что справиться с этим недостатком можно лишь нарушив первоначальную симметричную расстановку фигур.

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


Здесь sym — направление, попарно связывающее поля доски, расположенные симметрично. Фактически мы не удаляем, а помещаем на доску некую вспомогательную фигуру. Фигура, размещавшаяся ранее на целевом поле, удаляется автоматически, а саму добавленную фигуру мы удаляем командой capture, перед завершением хода командой add. В ZSG-нотации такой ход выглядит следующим образом:

1. White t e6 x e6

Ещё проще выполнить «переключение» фигуры, изменив цвет противника на свой (достаточно закомментировать команду capture в приведённом выше фрагменте кода), но уже здесь нас подстерегает первая засада. Можно поместить свою фигуру поверх фигуры противника, но не наоборот! ZoG разрешает играть лишь своими фигурами. К счастью, в данном случае, это не очень значимое ограничение. Добровольное удаление с доски своих фигур (а тем более замена их фигурами противника) — не самая удачная мысль. Поскольку нам вряд ли удастся убедить противника поступить столь же благородно, дело закончится гигантским дисбалансом в самом начале игры.


Разумеется, «Фокус» — не единственная игра, в которой ходы, выполняющие удаление произвольных фигур оказываются востребованными. В 30-е годы прошлого века, в СССР активно пропагандировалась игра "Шахбой", в которой фигуры на игровом поле символизировали силы пехоты, авиации и артиллерии. Артиллерия, в этой игре, представляла собой грозную силу, поскольку могла уничтожать фигуры противника, буквально «не сходя с места». Это могло полностью разрушить игровой баланс, но проблема была решена весьма оригинальным образом.

Самая слабая фигура «пехотинца», в этой игре, доходя до противоположного края доски, не превращалась в какую либо другую фигуру. В самом деле, игра выглядела бы очень странно, если бы пехотинец, дойдя до лагеря противника, превращался в танк или самолёт (не говоря уже о «штабе»). Пройдя через всё поле боя, «пехотинец» убирался с доски, но имел право «выполнить диверсию» — убрать с доски любую фигуру противника на выбор (кроме «штаба», конечно). Другое правило позволяло «пехотинцу» перепрыгивать через чёрные поля доски (не занятые другими фигурами), что позволяло эффективно «просачиваться» сквозь артиллеристские заслоны.



В различных вариантах "Мельницы", являющихся переходной формой между "Крестиками-ноликами" и играми семейства шашек, удаление произвольных фигур противника выполняется при выстраивании в ряд трёх своих фишек. В начале игры, фишки, принадлежащие игрокам, поочерёдно выкладываются на пустую доску, после чего их разрешается двигать по линиям доски. В существующих ZoG-реализациях, удаление фигуры противника совмещено с ходом, выстраивающим «мельницу» (линию из 3 фишек в ряд).


Здесь стоит обратить внимание на использование флага writeit. Формирование «тихого» хода (командой add) в макросе перемещения фишки (shift) происходит лишь в том случае, если не найдено ни одного варианта удаления вражеской фишки. В свою очередь, каждая команда add, выполняемая после взятия (capture) в макросе take-piece приводит к формированию независимого варианта хода (одновременно запрещая формирование «тихого» хода).

Это весьма интересная реализация алгоритма взятия «Мельницы», не покрывающая, к сожалению, всех возможных ситуаций этой игры. По некоторым вариантам правил, одновременное выстраивание нескольких рядов фишек должно обеспечивать возможность снятия соответствующего количества фишек противника. Попытка решения этой задачи представленным выше алгоритмом приводит к «комбинаторному взрыву». В своей реализации похожей африканской игры "Болотуду" я решил применить другой подход:


В этой игре, выстраивание ряда из трёх фигур, также как и в «Мельнице», даёт возможность боя фигуры противника, но не любой, а лишь «примыкающей к тройке сбоку». Для того, чтобы понять, что под этим имеется в виду, пришлось воспроизвести партию этой игры по следующей записи. Сразу скажу, что качество этой нотации ужасно. Скан с какой-то неизвестной мне книги не потрудились вычистить от ошибок распознавания. Впрочем, имея перед глазами доску, ход партии восстановить удалось (некоторые ходы игроков не показались мне особо умными).

Фрагмент кода, приведённый выше, основан на анализе этой партии. Макросы check-side и check-middle не только проверяют формирование троек, но и помечают поля, находящиеся «под боем» позиционным флагом is-marked?. Поскольку все флаги (включая позиционные) автоматически очищаются в начале каждого хода, не требуется выполнять какую либо «чистку мусора», по завершении расчёта хода. По той же причине, полученную информацию о возможном бое фигур приходится передавать в следующий ход, установкой атрибута is-capturing?. Следующим ходом, разрешается удалить любую фигуру, у которой установлен этот атрибут. Такой подход представляется мне более гибким, кроме того, удаление фигуры, выполненное отдельным ходом, более наглядно, чем выбор из длинного списка возможных ходов, формируемых «Мельницей».



Графические ресурсы я взял из реализации другой африканской игры. Ситуация была совершенно анекдотична. Когда я уже практически полностью реализовал игровой алгоритм, ZoG преподнесла сюрприз:

(loss-condition (White Black) (pieces-remaining 2))

Партия в «Болотуду» начинается с установки фигур парами на пустую доску. Указанная выше строка завершала игру в момент добавления второй фигуры любым из игроков. Потребовалось реализовать одноразовый «резерв» для того, чтобы фигуры учитывались ZoG уже на этапе добавления фигур на доску. Поскольку рисовать и настраивать доску с «резервом» сил уже не было, я взял подходящее определение доски из «Йотай».

Кстати, «Йотай» тоже подходит под тему сегодняшнего разговора. Эта игра ещё более похожа на шашки. Взятия в ней осуществляются привычным нам «перепрыгиванием» через фигуру противника. Как и в шашках, допускается несколько взятий «по цепочке» за ход. Отличие в том, что на каждую взятую фигуру, игрок имеет права взять ещё одну (любую) фигуру противника. Такая «положительная обратная связь» приводит к тому, что любой полученный перевес быстро приводит к победе (ничьи в этой игре бывают редко), а сам характер игры весьма подходит для темпераментных жителей африканского континента.

Но не следует думать, что подобные правила встречаются лишь в экзотических играх. Многие из тех, кто играл в шашки в детстве, наверняка помнят правило, по которому фигура, «прозевавшая» возможность боя, могла быть удалена с доски «за фук». Это правило ни в коем случае не изобретение «Русских шашек»! Точно также «профукать» (huffing) фигуру можно и в английских Checkers. Многие исследователи сходятся к тому, что подобное «правило гнева» существовало уже в прародителе всех шашечных игр — Алькуэрке.



В отношении самого «правила гнева» история вынесла практически однозначный приговор. Применение этого правила в шашках делает практически невозможной хоть сколь-нибудь сложную комбинационную игру. Действительно, в большинстве случаев, игроку гораздо выгоднее отдать «за фук» одну фигуру чем позволить заманить себя в ловушку, в результате которой он может потерять гораздо больше! Не удивительно, что в большинстве современных вариантов шашек «правило гнева» было упразднено.

В настоящее время, оно применяется лишь в некоторых африканских вариантах, таких как Damii, в которую играют на территории республики Гана. Как и многие другие африканские игры, этот вариант шашек играется «на скорость» и «зевки» в нём — важный элемент тактики. В остальном, правила Damii аналогичны "Международным шашкам".

В качестве своего рода «интеллектуальной гимнастики», я решил реализовать шашки «с зевками» на ZRF. Первый шаг был очевиден — поскольку для игрока требовалось обеспечить максимальную свободу выбора, я отключил приоритеты взятий, правило большинства и разрешил прерывание цепочки взятий. В этой игре, игрок не обязан «есть» фигуры противника, но если его шашки что-то «недоели», противник имеет право удалить любую из них с доски. Фигуры, подпадающие под действие «правила гнева» я решил помечать атрибутами. Немедленно сформировался следующий нехитрый алгоритм:

1. По завершении своего хода, для всех фигур противника, выполнять проверку возможности боя своих фигур (фигуры, способные выполнить бой, помечать атрибутом)
2. При выполнении противником взятия, очищать атрибуты на всех его фигурах (при выполнении тихого хода — атрибуты не трогать)
3. Если какая либо из фигур противника помечена атрибутом, взять её (очистив атрибуты на всех остальных фигурах)
4. Выполнить очередной свой ход

На бумаге всё было гладко. Разумеется, ZoG немедленно принялась вносить свои коррективы. Первое с чем приходится сталкиваться при реализации чего-то более менее сложного в ZRF — не очень внятная модель перемещения фигур. Вплоть до завершения хода, фигура в ZoG остаётся «как бы» на своей начальной позиции и, в большинстве случаев, это дьявольски неудобно. Приходится «помнить» о том, что стартовое поле «на самом деле» пустое, а конечное — заполнено перемещаемой фигурой. В результате получаются следующие макросы:


Разумеется, позиционные флаги from? и to? требуется ещё и правильно заполнить, да и сами макросы пришли к своему конечному варианту не сразу. Следующей стала проблема удаления помеченных фигур. Взяв фигуру «за фук» игрок должен выполнить ещё один ход, без передачи хода противнику. Мне не хотелось изменять порядок ходов в turn-order (на то были причины) и я решил блокировать возможность последующего хода, размещением на поле специальной невидимой фигуры (удаляемой по завершении обычного хода). Для того, чтобы игрок мог пропустить ход, пришлось активировать соответствующую опцию:

(option "pass turn" forced)

Далее, одно потянуло за собой другое. Опция "pass turn" управляет возможностью пропуска хода игроком (то есть добавляет к списку сгенерированных ходов пустой ход — pass). При установке значения "forced", её действие ещё хитрее — пас возможен лишь при отсутствии любых других возможных ходов (и пропуск хода, в этом случае, выполняется автоматически). К сожалению, по самой своей сути, эта опция совершенно несовместима со следующим условием завершения игры:

(loss-condition (First Second) stalemated)

И это очень плохо, поскольку завершение игры поражением игрока, при отсутствии возможности хода, едва ли не главное из того, что есть в шашках. Где-то в другом, более идеальном мире, хотелось бы, чтобы работала следующая конструкция (но это пустые мечты):

(loss-condition (First Second) (and stalemated (total-piece-count 0 Lock) ) )

Пропуск хода пришлось делать «вручную». На самом деле, это не так страшно как звучит. Требуется всего лишь реализовать «кнопку», на которую будет нажимать игрок, выполняя «пропуск хода». Поле a8 (на 64-клеточной доске) — подходящее место для её размещения (поскольку нормальные фигуры на него не заходят). Есть правда один минус — в отличии от честного "pass turn forced", эта кнопка сама «нажиматься» не будет. С другой стороны, в код обработки этого хода, можно поместить любую дополнительную логику, например очистку атрибутов (в текущей реализации это не понадобилось, но так везёт не всегда). В конечном итоге, с "Английскими шашками" всё получилось, но дальнобойные дамки — дело другое:


Этот вариант даже работал, пока дело не доходило до дамок. Дамки вели себя загадочно:



Загадка разрешилась просто. Дальнобойная дамка может остановиться на любом поле, по пути следования, следовательно для каждого из них должна быть проведена проверка возможности боя вражескими фигурами. Флаг, для дамки на h8, устанавливался при прохождении чёрной дамкой поля b2, но уже не сбрасывался в начале следующей итерации цикла. Подобным играм со значениями атрибутов не место в цикле генерации хода. Старый добрый «копипаст» в очередной раз пришёл на помощь:


Может показаться, что на этом мои мытарства закончились и я получил корректную работающую реализацию «Русских шашек с зевками», но всё не так просто. Во первых, включение опции "maximal captures" возвращало к жизни баг, описанный мной в одной из предыдущих статей. В какой-то момент игры, под управлением AI, программа переставала видеть возможность взятия своими фигурами (а поскольку код, выполняющий проверку за противника такую возможность видел, он брал шашки «за фук» буквально на ровном месте).

Я уже научился бороться с подобным багом в «Checkers Collection» и даже выложил соответствующее исправление, но в варианте «с зевками» этот метод почему-то не сработал.



Но и это лишь часть проблемы. На иллюстрации выше, белая дамка должна взять фигуры на d6 и f6, попав под бой h8. Конечно, она может «зевнуть», выполнив тихий ход или оставшись на месте, но в этом случае, её можно будет взять «за фук». Сложность заключается в том, что никакими техническими средствами я не могу «заставить» белую дамку продолжить бой. Она может уйти на f4 или g3 и пометка «зевка» всё равно будет снята. Некоторые вещи реализовать на ZRF корректно попросту невозможно.