Чуть правее наклон — упадет, пропадет!
Чуть левее наклон — все равно не спасти!
Но спокойно, ему остается пройти
Всего две четверти пути!

        Владимир Высоцкий "Натянутый канат" 
 
Когда фронт работ выглядит совершенно необозримым, его волей-неволей, приходится делить на мелкие куски. Кусочек, для первой итерации, я выбрал совсем небольшой:


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

Разумеется, речь идёт не о том, чтобы «закодить очередные шашки» (это можно было бы сделать и с меньшими усилиями). Я хочу разработать «метаигровую» систему, позволяющую описывать достаточно сложные логические игры, используя простой DSL и, в идеале, не обладая продвинутыми навыками программирования (то есть, ровно то, что делает Zillions of Games, но в полностью открытом и кроссплатформенном проекте).

Crazy Russian Stack Machine

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

(move
   (check (any nw ne))
   (check is-empty?)
)

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

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

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

(move
   (while true
      (let dir (any nw ne sw se))
      (check dir)
      (check is-enemy?)
      (capture)
      (check dir)
      (check is-empty?)
      (end-move)
   )
)

Пусть вас не смущает «бесконечный» цикл! Он будет прерван любой из check-проверок (вместе с разбором соответствующего варианта хода), при нарушении соответствующих условий. Этот код немного сложнее чем предыдущий, но разобраться в нём вполне реально. Вот что делается (по шагам) в каждой итерации цикла:

1. Мы выбираем одно из четырёх направлений (уже знакомым нам оператором any) и сохраняем его в переменную
2. Двигаемся в выбранном направлении (при условии, что это возможно)
3. На том поле, куда мы переместились, должна находиться вражеская фигура (иначе всё прерываем)!
4. Берём фигуру (сейчас мы не рассматриваем меры по противодействию "Турецкому удару")
5. И продолжаем двигаться в том же направлении (проверяя, что есть куда двигаться)
6. Целевая клетка должна быть пустой!
7. ...

Дальше начинается магия. Форма end-move говорит о том, что в этом месте ход может быть завершён, а (бесконечный) цикл требует двигаться дальше! Фактически, это равносильно выполнению следующего псевдокода, в котором на арену вновь выходит уже знакомый нам any:

(if (any true false)
    (execute post-actions)
    (generate-move)
)

Более того, any настолько универсален, что, с его помощью, можно переписать ещё одного участника спектакля, до сих пор остававшегося в тени. Вот как выглядит псевдокод эквивалентный оператору check:

(if (not <condition>)
    (any)
)

Выбор варианта, без возможности выбора — превосходная метафора для завершения любого перебора. Разумеется, это не означает, что check будет реализован именно таким образом, но мы можем его так реализовать!


В общем, что делать было понятно, но как это сделать? Оператор any (как, впрочем, и многое другое) может быть реализован при помощи продолжений, но в Java нет продолжений! Некоторое время я всерьёз раздумывал о том, чтобы перевести разработку ядра на Scheme (в которой продолжения не только есть, но и на них всё построено). Когда (после продолжительных экспериментов с прикручиванием «продолжений» к синтаксическим деревьям выражений) я уже находился на максимальной глубине отчаянья и вовсю читал "Лисп маленькими кусочками" (спасибо, ilammy), я понял, что есть другой способ.


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

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


Дальше — всё просто. Выполнение цепочки команд — это, по большей части, последовательный проход по ней в AbstractPorocessor. Команды If и Jump обеспечивают возможность ветвлений и циклов. Any — полна магией, но реализация Check довольно тривиальна. CommandFactory обеспечивает удобный интерфейс, для создания команд по имени. Лишь одна вещь способна омрачить настроение. Для реализации откатов к «точкам недетерминизма» необходимо научиться запоминать и восстанавливать состояние всех переменных, изменяемых при выполнении программы. Давайте, займёмся этим!

Не ACID

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

1. Размещение фигур (часть состояния)
2. Значения атрибутов фигур (часть состояния)
3. Значения атрибутов позиции (часть состояния)
4. Позиционные значения (временные)
5. Значения локальных переменных (временные)

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

• Строка
• Целое число
• Булевское значение

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





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

Основная задача LocalEnvironment — управление локальными переменными. Интерфейс IEnvironment предоставляет все необходимые для этого методы. Кроме того, метод get возвращает соответствующее значение, если, вместо имени переменной, в него передаётся константа (число, строка в кавычках, а также литералы true и false). Значения, соответствующие этим строкам, не могут быть изменены командой set! или переопределены при помощи let.

С точки зрения DSL, любое упоминание «голого» имени (строки без кавычек) приводит к выполнению команды get. Последствия выполнения этой команды зависят от того, каким окружением она обрабатывается. Все окружения связаны «по цепочке» и если LocalEnvironment не знает какого-то имени, он обращается к StateEnvironment. Здесь и начинается самое интересное. Этот модуль обеспечивает доступ к «певдопеременным», управляющим навигацией и предоставляющим доступ к информации о размещении фигур на доске.

Вот как это выглядит. Допустим, модель определяет позиции обычной шахматной доски. В этом случае, мы можем использовать имя любой позиции в DSL так, как если бы это было имя переменной. Значение «переменной» (например 'a1') запрашивается в LocalEnvironment, а затем в StateEnvironment. Это окружение связано со State и имеет полную информацию о всех позициях, определяемых моделью. Если запрошенная позиция существует, возвращается значение true, а, в качестве побочного эффекта, в переменной, определяющей текущую позицию в State, сохраняется имя полученной позиции. В противном случае, возвращается false и никакие побочные действия не выполняются. Аналогичным образом обрабатываются имена направлений (с той разницей, что на момент запроса, «текущая позиция» в State должна быть определена). Помимо псевдопеременных навигации, StateEnvironment определяет ещё несколько имён, предоставляющих доступ к исключительно полезной информации:

• position — имя текущей позиции
• is-empty? — истинно если текущая позиция пуста
• not-empty? — ложно если текущая позиция пуста
• is-friend? — истинно если на поле расположена дружественная фигура
• not-friend? — истинно если на поле не расположена дружественная фигура
• is-enemy? — истинно если на поле расположена враждебная фигура
• not-enemy? — истинно если на поле не расположена враждебная фигура
• player — имя игрока, владеющего фигурой, расположенной на текущей позиции
• piece — тип фигуры, расположенной на текущей позиции

Если StateEnvironment не знает какого-то имени, он обращается вниз по цепочке, к PlayersEnvironment. Задача этого окружения — выяснение взаимоотношений игроков. В текущей итерации, всё просто — если запрашиваемое имя игрока не совпадает с именем игрока, выполняющего текущий ход, то он враг. Впоследствии, логика проверок может усложниться (например добавятся коалиции игроков). Принимая имя, определённое в списке игроков, PlayerEnvironment сравнивает его с именем текущего игрока и возвращает false при несовпадении (этим пользуется StateEnvironment, при вычислении is-friend? и is-enemy?). Другие имена обрабатываемые этим окружением:

• current-player — имя игрока, выполняющего текущий ход
• next-player — имя игрока, выполняющего следующий ход
• turn-number — номер 'большого' хода (для рассматриваемой игры — пары полуходов)
• turn-order — номер полухода в рамках 'большого' хода

Если запрошенное имя неизвестно PlayersEnvironment, оно опускается ещё ниже, но о том, зачем нужен GlobalEnvironment и как он работает, я буду рассказывать в следующем разделе (это действительно сложная тема). Теперь главное, причём тут ACID? В общем-то совершенно не причём, но я не смог придумать более подходящего имени для интерфейса ITransactional. Мне даже не нужны транзакции, как таковые. Всё что требуется — уметь определять точки сохранения и выполнять полный откат состояния к ним. Откатывать, таким образом, придётся LocalEnvironment (состояние локальных переменных) и State (состояние доски). StateEnvironment — всего лишь обёртка над State и не владеет какими либо данными, а состояние PlayersEnvironment не изменяется в процессе расчёта хода. Помимо этого, Processor должен уметь откатывать состояние стека данных, но это его внутреннее дело.

За пределами «транзакционности»

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

(piece
   (name Man)
   (pre
      ...
      (let captured 0)
   )
   (post
      (check (<= max-captured captured))
      (set! max-captured captured)
      ...
   )
   ...
   (move
      (while true
         (let dir (any nw ne sw se))
         ...
         (check is-enemy?)
         (capture)
         (inc! captured)
         ...
      )
   )
)

Хитрую проверку в post я называю «нарушаемым инвариантом». Как он работает? Допустим, в процессе разбора был сгенерирован ход, берущий одну фигуру. Проверка в post прошла успешно и в переменную max-captured была сохранена единичка. Теперь все ходы, не выполняющие взятий, будут отвергаться, поскольку условие в check будет нарушено. Понятно, что переменная max-captured должна храниться в совершенно особом месте. На неё не должны действовать какие либо откаты состояния и, самое главное, она должна быть доступна всем вариантам рассчитываемых ходов (почти что разным реальностям). GlobalEnvironment — то самое место. Это окружение не умеет создавать локальные переменные по команде let, но создаёт переменные глобальные по любому set! или get-запросу! Если имя переменной не объявлено конструкцией attribute или let, переменная создаётся автоматически, при первом использовании и её значение разделяется между различными вариантами расчёта хода.

Но, сами по себе, глобальные переменные — только часть дела! Обычно, действует совсем другой кейс. Мы находим какой-то ход, берущий одну фигуру, а затем, например продолжая цепочку взятий, берём вторую, третью, четвёртую… Простая проверка здесь не поможет! Мы должны повторять все выполненные ранее проверки, при каждом изменении глобальной переменной max-captured, и отвергать соответствующие им ходы, при обнаружении нарушений. Инвариант для этих ходов выполнялся, на момент их генерации, но был сломан изменением max-captured! Это действительно сложное место и я пока не уверен, что оно работает. Управлять всей этой «магией» должен MoveGenerator.


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

Практически во всех играх семейства шашек (из числа традиционных игр, исключением является лишь "Фанорона"), начав цепочку взятий, игрок обязан пройти её до конца! При этом, например в "Русских шашках", не требуется брать максимальное количество фигур. Это более сложное ограничение чем простое «правило большинства» (во всяком случае, пока я не придумал как его выразить через «нарушаемый инвариант») и для него будет использоваться другой вид отложенной проверки. Предикат no-moves? будет проверять отсутствие у хода возможных продолжений. Если продолжение будет обнаружено, предыдущий (более короткий) вариант хода будет аннулирован. Я не буду заниматься реализацией этого предиката в текущей итерации.

О unit-тестах

Главное, что необходимо знать о unit-тестах, это то, что unit-тесты помогают! Нет, серьёзно, я не являюсь сторонником методики TDD, но полезность самих unit-тестов, именно в этом проекте, сложно переоценить! Здесь (пока) нет БД или каких либо сетевых компонентов (соответственно, не приходится ломать голову над mock-обёртками для них), но зато сам проект довольно сложен. Мысль о том, что его можно просто написать с нуля, запустить целиком и в таком виде отладить — меня пугает. Unit-тесты помогают выполнить эту отладку по частям, начиная с простых вещей, вроде системы команд, поднимаясь все выше, к более сложным концепциям. Этот подход действительно работает! В процессе написания тестов, я уже нашёл и исправил несколько серьёзных ошибок. Аналогичные исправления, на этапе отладки всего проекта, обошлись бы мне гораздо дороже.

При переходе к более высокому слою, unit-тесты дают уверенность (иногда ложную, но тут уж всё от покрытия зависит) в том, что все нижележащие слои работают так, как было задумано. Более того, если в проекте что-то всерьёз меняется (а такое бывает), unit-тесты немедленно сигнализируют о том, что и как развалилось. В каком-то смысле, unit-тесты документируют API проекта (это конечно не отменяет обычную документацию), причем, сосредотачиваясь на наиболее тонких и сложных случаях. В общем, в настоящий момент, я работаю над unit-тестами и намерен продолжать двигаться в этом направлении до тех пор, пока это возможно (вплоть до того момента, пока сама цель первой итерации проекта не станет одним из тестов). Это половина пути и я надеюсь пройти весь путь целиком.