http://habrahabr.ru/post/242547/

Бежит на юг и кружит на север, кружит, кружит на бегу своем ветер,
И на круги свои возвращается ветер;
Бегут все реки в море, — а море не переполнится,
К месту, куда реки бегут, — Туда они продолжают бежать;

Книга Экклезиаста.

В 1998 году, было разработано совершенно уникальное, для своего времени, приложение, позволяющее свести процесс разработки абстрактной настольной игры (или головоломки) к небольшому текстовому описанию на языке, отдалённо напоминающем Lisp. Этот проект получил название Zillions of Games и произвел настоящий фурор в среде любителей настольных игр. В настоящее время, создано более 2000 приложений, с использованием этой технологии.

Очень быстро выяснилось, что ZoG обладает множеством недостатков. Я уже писал об этом на Хабре и не буду повторяться. Скажу лишь, что разработчики не учли особенностей огромного количества уже существующих игр, а часть важных опций «захардкодили» таким образом, что их изменение стало крайне проблематичным. Грэг Шмидт, в 2007 году, постарался исправить ситуацию, выпустив Axiom Development Kit, но тесная интеграция этого решения с ZoG не позволила решить все проблемы.

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

Моей целью является разработка более универсального и удобного в использовании «движка» для создания абстрактных настольных игр. Уже почти год я изучаю возможности ZoG и Axiom и узнал очень многое об их ограничениях. Я думаю, что смогу решить их проблемы, создав более универсальное и кроссплатформенное решение. О ходе работы над этим проектом я и собираюсь рассказать.

Открытость и модульность

Пожалуй, главным недостатком ZoG является его закрытость. Продукт собран «раз и навсегда» под одну единственную платформу — Windows. Будь исходные коды открытыми, можно было бы попытаться портировать их под Linux, Android, iOS… Другой проблемой является монолитность.

В ZoG имеются зачатки модульности, позволяющие подключать к играм DLL, содержащие кастомные реализации AI. Axiom идёт чуть дальше, позволяя запускать приложения в режиме autoplay, без использования ядра ZoG. Даже несмотря на серьёзное ограничение этого решения (поддерживаются приложения только для двух игроков), этот пример наглядно показывает, насколько модульность была бы полезна! Возможность организовать игру двух ботов (использующих различные настройки AI) и собрать статистику по большому количеству их игр трудно переоценить. Но насколько было бы лучше, если бы продукт был полностью модульным!

• Модуль генерации ходов
• Модуль выполнения хода
• Управляющий модуль
• Модуль AI
• Модуль визуализации

Вся работа с описанием игр должна выполняться модулем генерации ходов. Это «сердце» проекта. Перенос всей не связанной с его задачами функциональности в другие модули позволит сделать его максимально простым. Можно улучшать этот модуль, не оглядываясь на вопросы AI и взаимодействия с пользователем. Можно полностью изменить формат описания игр или добавить поддержку описаний в формате ZoG, Axiom и Ludi. Модульность — основа гибкости решения!

Модуль выполнения хода — это хранитель игрового состояния. Информация о текущем игровом состоянии передаётся всем остальным модулям по требованию. По причинам, о которых я скажу ниже, выполнение хода должно проходить через модуль генерации, задачей которого является формирование команды в терминах модуля выполнения хода. Также, задачей модуля генерации является первичное конфигурирование игрового пространства, на основании описания игры.

Управляющий модуль — это, по сути, само приложение. Он запрашивает у модуля генерации списки возможных ходов и изменяет игровое состояние, передавая выбранный ход в модуль выполнения хода. Управляющий модуль может подключить к игре один или несколько AI ботов. Столько, сколько требуется (и возможно различных)! Тип используемого управляющего модуля определяется решаемыми задачами. Это может быть autoplay для сбора игровой статистики, игровой сервер (он может управлять сразу несколькими хранилищами состояния, ведя большое количество игровых сессий) или индивидуальное приложение для игры в offline.

Возможность подключения различных реализаций AI позволит улучшить качество игры. Понятно, что модули для игры в Шахматы и Го должны использовать различные подходы. Игры с неполной информацией и игры использующие случайные данные также требуют индивидуального подхода. Универсальная реализация AI будет одинаково плохо играть во все игры! Модульное подключение AI позволит сравнивать «силу» используемых алгоритмов, включая их в режиме игры «между собой». Поскольку AI архитектурно отделён от хранилища игрового состояния, одна реализация игрового бота сможет поддерживать неограниченное количество игровых сессий одновременно.

Визуализация игрового процесса также может быть различной. Первое, что приходит в голову — это 2D и 3D реализации. Платформа, для которой разрабатывается приложение, также имеет значение. Менее очевидно, что визуализация может быть важной частью игрового процесса! Так например, в игре Суракарта, взятие фигур будет совершенно неочевидным при отсутствии правильной анимации ходов.


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

Игровое пространство

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


Можно заметить, что помимо собственно игровых настроек, здесь имеются настройки, связанные с визуализацией. Я твёрдо убеждён в том, что этим настройкам здесь не место. Реализаций модуля визуализации может использоваться несколько и настройки им потребуются различные. Более того, игровая симуляция может работать и без модуля визуализации вообще (как autoplay в Axiom). Действительно, поскольку Axiom использует для визуализации ZoG, определение не содержит ничего лишнего:


К сожалению, определения игровых зон оно также не содержит (расположение игровых зон приходится определять в коде вручную). Это не единственное упрощение, на которое идёт Axiom. Определение доски в этом проекте не может содержать более одного grid-а и этот grid должен быть двумерным. Доска, определённая таким образом, представляет собой одномерный массив, но для удобства программиста, определяются синонимы для каждого из полей, по следующей схеме:


По сравнению с более гибкой схемой определения grid-ов в ZoG, эти ограничения довольно неудобны (особенно с учетом того, что навязанная схема именования полей используется и при визуализации). К счастью, имеется возможность определения доски произвольной формы. И Axiom и ZoG предоставляют возможность поэлементного определения каждой позиции доски с возможностью определения связей между произвольными парами позиций. Используя этот подход, можно определить доску любой топологии. Единственный его минус — крайняя многословность и трудоёмкость описания.

Помимо расположения фигур на доске и в резерве, должна иметься возможность хранения атрибутов как для отдельных фигур, так и для полей доски. Хорошим примером необходимости использования атрибутов является правило "рокировки" в Шахматах. Это сложный ход, включающий в себя одновременное перемещение короля и одной из ладей, возможный при условии, что ни одна из этих фигур, до выполнения этого хода, не передвигалась. Атрибут может быть использован для хранения булевского признака того, что фигура перемещалась когда либо. Атрибутам полей можно также найти довольно интересные применения.

Следует отметить, что атрибуты — не просто переменные, а часть игрового состояния. Значение атрибута может быть изменено при выполнении хода (в том числе модулем AI) и должно быть доступно для всех последующих ходов, но не для ходов, выполняемых в другой ветви игры. В настоящее время, ZoG поддерживает хранение булевских атрибутов фигур. Axiom хранение атрибутов не поддерживает, но позволяет добавлять в определение доски описание переменных и массивов. Такие переменные могут быть использованы, например, как счетчики количества съеденных фигур:

{board
	5 18 {grid}
	{variable}	WhitePieces
	{variable}	BlackPieces
board}

Ещё одним ограничением как ZoG, так и Axiom является правило, по которому каждое поле доски может содержать не более одной фигуры. Если какая либо фигура завершает ход на поле, занятом другой фигурой, фигура ранее занимавшая поле, автоматически считается «съеденной». Это правило хорошо сочетается с «шахматным» принципом взятия фигур и позволяет упростить описания использующих его игр, но затрудняет реализацию таких игр как "Столбовые шашки" и "Таврели".


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


Резюмируя, можно сказать, что для своего игрового framework-а, я решил взять всё лучшее, что было придумано в ZoG, Axiom и Ludi и добавить то, чего, по моему мнению, им не хватает.

Ходогенерация

Генерация хода сродни недетерминированному программированию. Задача генератора ходов — предоставление, по требованию, списка всех возможных ходов, из текущей позиции. Какой именно ход, из этого списка, будет выбран игроком или AI — не его дело. Рассмотрим, как именно выполняется генерация ходов в ZoG. В качестве примера, возьмём макрос генерации хода дальнобойной фигурой (ферзём или слоном). Вот как он используется в определении фигуры:

(piece
      (name Bishop)
      (image White "images\Chess\SHaag\wbishop.bmp" "images\Chess\wbishop.bmp"
             Black "images\Chess\SHaag\bbishop.bmp" "images\Chess\bbishop.bmp")
      (moves
         (slide ne)
         (slide nw)
         (slide se)
         (slide sw)
      )
)

В качестве параметра, в макрос передаётся направление перемещения по доске. Если не рассматривать возможность установки новых фигур на доску, генерация хода выглядит просто. Для каждой из фигур на доске, выполняется перебор всех определённых правилами ходов. Дальше начинается магия…

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

(define slide (
    $1 
    (while empty? 
        add 
        $1
    ) 
    (verify not-friend?) 
    add
))

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

Очень просто! Выполнив, командой verify, проверку того, что поле не занято дружественной фигурой, мы формируем ещё одну команду add, завершая ход. Если на этой клетке размещалась вражеская фигура, она будет взята автоматически (поскольку на одном поле доски, единовременно, не может размещаться более одной фигуры). Если фигура была дружественная, расчёт хода прервётся командой verify (нарушение условия, указанного в этой команде, немедленно прерывает расчёт текущего хода).

И в ZoG и в Axiom ходить можно только своими фигурами (вернее ходить фигурами противника можно, но только в том случае, если это указано в режиме расчёта хода). Я нахожу это ограничение крайне неудобным, поскольку имеется множество игр, в которых ходить фигурами противника можно (в "Ставропольских шашках", например). Более последовательным было бы выполнять расчёт хода для всех фигур, независимо от их принадлежности. В макрос, определяющий ход, понадобилось бы добавить всего одну проверку, для того, чтобы ходить можно было только своими фигурами:

(define slide (
    (verify friend?) 
    $1 
    (while empty? 
        add 
        $1
    ) 
    (verify not-friend?) 
    add
))

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

(define checker-jump
    ($1 (verify enemy?)
        capture
        $1
        (verify empty?)
        (if (not-in-zone? promotion-zone)
            (add-partial jumptype)
         else
            (add-partial King jumptype)
        )
    )
)

Частичный ход формируется командой add-partial (для неё, как и для команды add, существует вариант хода, с «превращением» фигуры). Такой ход всегда является частью большего, «составного» хода. Как правило, для последующих ходов, устанавливается «режим», в котором должно осуществляться продолжение. Так в шашках, взятие можно продолжить лишь последующими взятиями, но не «тихим» ходом.


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

(verify (not-position-flag? my-flag))
(set-position-flag my-flag true)

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

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

1. Инициализация переменных и проверка предусловий составного хода
2. Инициализация переменных и проверка предусловий частичного хода
3. Генерация частичного хода
4. Проверка постусловий частичного хода
5. Генерация завершения и проверка постусловий составного хода
6. Проверка выполнения условий завершения игры

Группа шагов со второго по четвёртый, при выполнении составного хода, может повторяться многократно. Идею пред- и постусловий, называемых мной инвариантами, я взял из проекта Ludi. Впрочем, об использовании инвариантов я подробнее расскажу в дальнейшем.

О важности нотации

Генерация всех возможных из позиции ходов — это только половина дела. Для управления игровым состоянием, требуется компактная форма представления сгенерированных ходов. В ZoG, для этой цели, используется ZSG-нотация. Вот как выглядит запись возможного начала шахматной партии в этой форме:

1. Pawn e2 - e4
1. Pawn e7 - e5
2. Knight g1 - f3
2. Knight b8 - c6
3. Bishop f1 - c4
3. Knight g8 - f6
4. King e1 - g1 Rook h1 - f1 @ f1 0 0 @ g1 0 0
4. Pawn d7 - d5
5. Pawn e4 x d5
5. Knight f6 x d5

Такая запись близка к привычной шахматной нотации и, в целом, понятна пользователю. Некоторое недоумение может вызвать лишь четвёртый ход белых. Так в ZSG выглядит рокировка. Часть описания хода до символа '@' вполне понятна — это одновременное перемещение ладьи и короля, но что следует далее? Таким образом, в ZSG, выглядит сброс атрибутов фигур, выполнение которого необходимо для того чтобы не дать возможность выполнить рокировку повторно.


Запись хода в ZSG-нотации должна содержать полную информацию, достаточную для корректного изменения игрового состояния. Если бы информация об изменении атрибутов не сохранялась, партия, по такой записи, могла бы быть воспроизведена некорректно (например, у игрока имелась бы возможность повторного выполнения рокировки). К сожалению, в DLL-расширения (такие как Axiom), расширенная информация может не передаваться.

Работая с DLL-расширениями, ZoG вынуждена производить довольно хитрую манипуляцию при выполнении позиционирования на выбранный ход (например, при откате хода). Из предыдущей позиции, генерируются все возможные ходы, после чего, в списке, выполняется поиск выбранного хода по его ZSG-представлению. Сгенерированный ход применяется к игровому состоянию, возможно выполняя побочные действия, не отражённые в его ZSG-представлении.

Ситуация усугубляется ещё и тем, что единственным способом получения игрового состояния, на момент какого-то хода в прошлом, является последовательное применение всех ходов, с начала партии, к начальному состоянию доски. В действительно сложных случаях, подобная навигация происходит не быстро. Другой недостаток ZSG-нотации может проиллюстрировать запись следующего хода из партии Го:

1. White Stone G19 x A19 x B19 x C19 x D19 x E19 x F19

Здесь, в позицию G19, устанавливается белый камень, что приводит к снятию группы чёрных камней. Поскольку все фигуры, задействованные при выполнении хода, должны быть упомянуты в ZSG-представлении, запись хода может оказаться очень длинной (в Го, одним ходом может быть снято до 360 камней). К чему это может привести, я уже писал ранее. Размера буфера, выделяемого ZoG под запись хода, может и не хватить. Кроме того, если по каким-то причинам порядок снятия камней изменится (в процессе разработки игры такое бывает), попытка применения хода, со старым порядком взятий, закончится ошибкой.

К счастью, имеется простой способ борьбы со всеми этими проблемами. Посмотрим на то, как определяются ходы фигур в ZRF:

(piece
     (name Pawn)
     (image White "images\Chess\SHaag\wpawn.bmp" "images\Chess\wpawn.bmp"
            Black "images\Chess\SHaag\bpawn.bmp" "images\Chess\bpawn.bmp")
     (moves
        (Pawn-capture nw)
        (Pawn-capture ne)
        (Pawn-move)
        (En-Passant e)
        (En-Passant w)
     )
)

Имена ходов, определяемых в ZoG макросами, генератору ходов недоступны. Но что нам мешает отказаться от макросов и сделать описания ходов именованными? Вот как будет выглядеть запись шахматной партии:

1. e2 - e4 Pawn-move
1. e7 - e5 Pawn-move
2. g1 - f3 leap2 n nw
2. b8 - c6 leap2 n ne
3. f1 - c4 slide nw
3. g8 - f6 leap2 n nw
4. e1 - g1 O-O
4. d7 - d5 Pawn-move
5. e4 x d5 Pawn-capture nw
5. f6 x d5 leap2 w nw

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

1. G19 drop-to-empty White Stone

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


Ещё одной возможностью, которую следует поддерживать, является функциональность «частичных» ходов. Вот пример из "Русских шашек":

1. Checker g3 - f4
1. Checker f6 - g5
2. Checker e3 - d4
2. partial 2 Checker g5 - e3 = XChecker on f4
2. Checker e3 - c5 = XChecker on d4 x d4 x f4

Здесь чёрные, на втором ходу, берут две фигуры на d4 и f4. Предварительное «превращение» фигур в XChecker является особенностью реализации и служит для предотвращения возможности повторного взятия «битых» фигур на том же ходу. Фраза "partial 2" описывает начало «составного» хода, состоящего из двух «частичных» ходов. Такая форма описания неудобна, поскольку на момент генерации первого хода, длина последовательности «частичных» ходов может быть неизвестна. Вот как будет выглядеть это описание в новом формате:

1. g3 - f4 checker-shift nw
1. f6 - g5 checker-shift ne
2. e3 - d4 checker-shift nw
2. + g5 - e3 checker-jump nw
2. + e3 - c5 checker-jump sw
2. +

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

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

Жизненный цикл игры

Наряду с информацией о размещении фигур на доске, очередность хода является составной частью состояния, изменяемого в процессе игры. В простейшем (и наиболее распространённом) случае, для хранения этой информации достаточно одного бита, но ZoG предоставляет чуть больше возможностей, для реализации более сложных случаев. Вот как могло бы выглядеть описание последовательности ходов для игры Splut!:

(players South West North East)
(turn-order
    South
    West West
    repeat
    North North North
    East East East
    South South South
    West West West
)

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


Метка repeat обозначает начало циклически повторяющейся последовательности ходов. Если она отсутствует, циклически повторяется всё описание. ZoG позволяет использовать метку repeat не более одного раза. Другой важной возможностью является определение режима хода. Вот как может выглядеть описание последовательности ходов игры, в которой каждый из игроков выполняет по два хода (первый ход — перемещение фигуры, второй — взятие фигуры противника):

(players White Black)
(turn-order
    (White normal-move)
    (White capture-move)
    (Black normal-move)
    (Black capture-move)
)

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

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


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

(players South North)
(turn-order
    (turn-order 
         (South p-i-move)
         (North p-i-move)
    )
    (label phase-ii)
    (turn-order 
         (South p-ii-move)
         (North p-ii-move)
    )
)

Здесь, каждый список turn-order определяет свою повторяющуюся последовательность ходов (различающуюся режимом выполнения хода). Ключевое слово label определяет метку, переход по которой может быть сформирован при генерации очередного хода. Можно заметить, что здесь мы исходим из неявного предположения о том, что такой переход всегда происходит после хода второго игрока (в противном случае будет нарушена последовательность ходов). Как выполнить переход к следующей фазе в произвольный момент времени?

(players South North)
(turn-order
    (turn-order 
         (South p-i-move)
         (North p-i-move)
    )
    (turn-order 
         (labels - phase-ii)
         (South p-ii-move)
         (labels phase-ii -)
         (North p-ii-move)
    )
)

Здесь метки перенесены в тело цикла и содержат по два имени. Имена меток, в списках labels перечисляются в соответствии с порядком перечисления игроков в списке players. Имя, используемое для перехода, определяется в зависимости от того, какой из игроков выполнил ход последним. Если это был North, будет выполнен переход к первой метке, в противном случае — ко второй. Если какое либо из имён в labels не будет использоваться, соответствующую позицию можно заполнить прочерком.


Важным моментом, в управлении чередованием ходов, является возможность выполнения повторного хода. В играх семейства Нард, таких как Ур, например, возможность выполнения повторных ходов является важным элементом игровой тактики. В ZoG можно использовать пропуск хода, для эмуляции этой возможности, но такой подход существенно запутывает описание игры (особенно при участии нескольких игроков). Гораздо логичнее использовать метку для повторения хода:

(players South North)
(turn-order
    (label repeat)
    South
    (label repeat)
    North
)

Выполнив переход к repeat, игрок вернётся к повторению последнего хода (при этом будет действовать метка, ближайшая к текущему положению в списке ходов). Мне нравится подход Perl в части неявных определений. Неявная генерация управляющих структур может существенным образом упростить описание. Поскольку повторные ходы могут быть использованы во многих играх, метки repeat, предваряющие каждый ход, можно формировать неявно:

(players South North)
(turn-order
    South
    North
)

Более того, поскольку последовательность ходов полностью соответствует перечислению игроков в players, автоматически можно формировать всю фразу turn-order:

(players South North)

Чем проще получится описание — тем лучше.

Нарушаемый инвариант

Главное, что мне не нравится в ZoG можно выразить одним словом — checkmated. На первый взгляд, это просто условие (весьма распространённое в играх шахматного семейства), связывающее завершение игры с образованием матовой ситуации. Увы, при более пристальном рассмотрении, простота оказывается обманчивой. Использование этого ключевого слова подразумевает не только выполнение, после каждого хода, проверок завершения игры, но и навязывает игроку определённое «поведение».

И модуль генерации ходов и AI должны учитывать, что после выполнения хода, свой король не должен оказываться под шахом. При этом, недостаточно выполнять проверку только для сходившей фигуры, шах вполне может быть "открытым". Правильно реализовать все необходимые проверки непросто (во всяком случае, в ZoG этого сделать не удалось):

От обычного Сёги эта игра отличается только количеством игроков. К сожалению, этого отличия достаточно, чтобы сделать работу checkmated (и всей связанной с этим словом «магии») некорректной. Правильная проверка нахождения под шахом выполняется лишь по отношению к одному из игроков. В результате, король вполне может оказаться под ударом и быть съеденным! Разумеется это не лучшим образом отражается и на работе AI.

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


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

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


Очевидно, что необходимо отделять логику проверки завершения игры от проверки попадания короля под шах, являющейся, по сути, инвариантом, проверяемым после выполнения каждого хода. Нарушение инварианта делает выполнение хода невозможным (ход изымается из списка доступных ходов). Вот так (упрощенно) может выглядеть проверка попадания короля под шах для «Шахмат Тамерлана»:

(verify
    (or
        (> (count (pieces my? (is-piece? King))) 1)
        (= (count (pieces my? (is-piece? King) is-attacked?)) 0)
    )
)

Важно понимать, что эта проверка должна выполняется только для собственных королей (я использовал предикат my?, поскольку, при поддержке коалиций, атрибут friend? будет удовлетворяться не только для собственных фигур, но и для фигур дружественного игрока). Допустима (и желательна) ситуация, в которой вражеский король попадает под шах, после выполнения хода, но в отношении собственного короля, такая ситуация должна быть невозможной! При условии поддержки проверки подобных инвариантов, проверка завершения игры матом становится тривиальной. Если нет возможных ходов и король находится под шахом — игра проиграна:

(loss-condition
    (and
        (= (count moves) 0)
        (> (count (pieces my? (is-piece? King) is-attacked?)) 0)
    )
)

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


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

(option "maximal captures" true)

Такая настройка подходит для "Международных шашек", но в "Итальянских шашках" правило большинства формулируется иначе. В этом варианте игры, если имеется несколько вариантов с одинаковым количеством взятий, требуется выбрать вариант, в котором берётся больше превращенных шашек (дамок). Разработчики ZoG предусмотрели это, введя следующее значение настройки:

(option "maximal captures" 2)

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

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

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

(verify 
    (>= capturing-count max-capturing-count)
)
(if (> capturing-count max-capturing-count)
    (let max-capturing-count capturing-count)
    (let max-capturing-sum capturing-sum)
    (let max-attacking-value attacking-value)
)
(verify 
    (>= capturing-sum max-capturing-sum)
)
(if (> capturing-sum max-capturing-sum)
    (let max-capturing-sum capturing-sum)
    (let max-attacking-value attacking-value)
)
(verify 
    (>= attacking-value max-attacking-value)
)
(let max-attacking-value attacking-value)

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

• capturing-count — количество взятых фигур
• capturing-sum — суммарное достоинство взятых фигур
• attacking-value — достоинство фигуры, выполняющей ход

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

Заключение

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

Viam supervadet vadens.