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

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

Очень простые шашки
(board
   (name chess-board-10x10)
   (dim "a-j")
   (dim "10-1")
   (dir (name nw) -1 -1)
   (dir (name ne)  1 -1)
   (dir (name se)  1  1)
   (dir (name sw) -1  1)
)

(piece
   (name Man)
   (pre
      (check is-friend?)
      (take)
      (log position)
      (let captured 0)
   )
   (post
      (check (<= max-captured captured))
      (set! max-captured captured)
      (log " - " position)
      (drop)
   )
   (move
      (check (any nw ne))
      (check is-empty?)
   )
   (move
      (while true
         (let dir (any nw ne sw se))
         (check dir)
         (check is-enemy?)
         (capture)
         (inc! captured)
         (check dir)
         (check is-empty?)
         (end-move)
      )
   )
)

(game
   (name "Simple Checkers")
   (board chess-board-10x10)
   (players 
      (White (Man a1 c1 e1 g1 i1 b2 d2 f2 h2 j2 a3 c3 e3 g3 i3)) 
      (Black (Man b8 d8 f8 h8 j8 a7 c7 e7 g7 i7 b6 d6 f6 h6 j6))
   )
)


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

Разумеется, речь идёт не о том, чтобы «закодить очередные шашки» (это можно было бы сделать и с меньшими усилиями). Я хочу разработать «метаигровую» систему, позволяющую описывать достаточно сложные логические игры, используя простой 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 будет реализован именно таким образом, но мы можем его так реализовать!

Out of scope
У оператора any есть и другие полезные возможности применения, которые мы не будем рассматривать на текущем этапе разработки проекта. Вот как, например, будет выглядеть условие завершения игры в шахматах:

(game 
   (name chess-game)
   (loss 
      (exists?
         (any King)
         (if is-friend?
             (check is-attacked?)
         )
         (check no-moves?)
      )
   )
)

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

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

Немного о дварфийском хлебе
Не знаю, кому как, а мне Scheme очень сильно напоминает «дварфийский хлеб», неоднократно упоминаемый в произведениях Терри Пратчетта. Вот как его описывает автор:
Дварфийский хлеб можно использовать для купли-продажи, для проведения церемоний – зачастую дварфы скрепляют заключаемые сделки, «переламыванием хлеба» и некоторые железные молоты, с помощью которых его переламывали, являются ценными произведениями искусства. И, конечно же, хлеб применяют в качестве оружия, что является его основным предназначением. Плоская круглая буханка дварфийского хлеба с песочной корочкой, запущенная на манер метательного диска, запросто обезглавит противника и более того, если правильно ее бросить, вернется к своему владельцу. Менее распространенные длинные батоны, называемые багетами, традиционно применяются в рукопашном бою. Уронительные лепешки первоначально применялись в защитных целях, например, при обороне крепостных стен. Дварфийский хлеб может быть съеден, по крайней мере, дварфами.


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

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

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

Ещё одна прекрасная возможность
Использование команд стековой машины открывает ещё одну интересную возможность. Я уже писал о том, что мне хотелось бы обеспечить совместимость с описаниями игр в форматах ZRF (Zillions of Games) и GDL (Ludi Project). Оба эти языка лиспоподобны и я планирую использовать XSLT для преобразования описаний на них в свой формат «на лету». Это сложно, но вполне возможно.

Увы, для Axiom этот способ не подходит. ForthScript-машину вряд ли удастся «засунуть» в XSLT-скрипт. Но, коль скоро я использую стековую машину, что мешает мне продублировать (хорошо документированную) систему команд Axiom, чтобы загружать описания непосредственно во внутреннее представление, минуя DSL? Думаю, автор не будет против (впрочем, я у него спрошу).

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

Не ACID


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

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

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

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

На самом деле, есть ещё и ссылки
(while true
   (let dir (any ...))
   (check dir)
   ...
)

Здесь any возвращает строку, впоследствии используемую для выполнения команды навигации (о том, как выполняется навигация, я расскажу ниже). Если значение, сохранённое в dir, не будет помечено как ссылка, check интерпретирует его как булевское (это будет 'истина', поскольку строка не пуста и не равна «0»), не пытаясь выполнить какие либо побочные действия, связанные с позиционированием.

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

Что означают пометки в скобках?
Важно понимать, что под «состоянием» я понимаю информацию, необходимую для точного восстановления соответствующей позиции на доске. Например, размещение фигур на доске, безусловно, является частью состояния. Более сложный пример — атрибуты фигур. Одно из условий выполнения рокировки — неподвижность задействованных в ней фигур в течение всех предыдущих ходов. Подобный признак удобно хранить в атрибуте фигуры, содержащем булевское значение. При выполнении любого хода фигурой, мы изменяем это значение, делая невозможной последующую рокировку. Поскольку эта информация передаётся между различными позициями, она является частью состояния. Аналогичным образом могут определяться атрибуты, связанные со всей позицией, а не с какой либо конкретной фигурой. Я не буду использовать атрибуты в текущей итерации, но поскольку это очень важный элемент архитектуры — реализую их.

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

(seq
   (let <переменная> <выражение>)
   ...
   <область действия переменной>
   ...
)

Это очень важный момент, поскольку, при расчёте хода в фразе move, должна иметься возможность использования переменных, объявленных в одной из фраз предварительных действий (фраза pre). Также, объявленные переменные должны оставаться доступными и при выполнении завершающих действий (фраза post). Переменные могут перекрываться, повторными объявлениями let. Кроме того, значение локальной переменной может быть изменено, при помощи команды set!. Возможность удаления переменной (закрытия её области действия), реализована на уровне команд стековой машины (для определения «гигиенических» переменных), но, пока не поддерживается на уровне DSL.

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




На этой схеме изображены все типы хранилищ, используемых при расчёте хода. Здесь не рассматриваются данные о загруженной игре (такие как, топология доски). Они могут быть довольно сложными, но с точки зрения генератора ходов, они постоянны. Вся информация о размещении фигур, а также все ранее перечисленные значения, кроме локальных переменных, хранятся в 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 — тип фигуры, расположенной на текущей позиции

Формы - обычные и специальные
Из того, что я говорил выше, уже можно было заметить, что существует некий «концептуальный» разрыв между описываемым мной DSL и цепочками команд стековой машины. Это вотчина классов statements. Задача каждого из этих классов — преобразование последовательности лексем, составляющих известную ему форму, в правильную цепочку команд стековой машины (то есть кодогенерация). Например, ExpressionStatement обрабатывает все «обычные» формы (то есть формы, не являющиеся специальными). Так работают все арифметические выражения (кстати, поскольку арность определена скобками, такие функции как сложение и умножения не ограничены лишь двумя операндами, а минус вполне может быть унарным).

Специальные формы реализуют особый порядок обработки операндов. Типичными их представителями являются IfStatement (фраза else поддерживается) и WhileStatement. Формы OrStatement и AndStatement также являются специальными, поскольку реализуют «сокращённое вычисление» логических выражений. Это важно, поскольку в выражениях могут использоваться псевдопеременные, обращение к которым связано с побочными эффектами.

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

(check
   (and (is-empty? n nw)
        (is-empty? n ne)
        (is-empty? e ne)
        (is-empty? e se)
        (is-empty? s se)
        (is-empty? s sw)
        (is-empty? w sw)
        (is-empty? w nw)
   )
)

В этом коде, is-empty? уже не псевдопеременная, а форма. Конечно, такие обёртки можно было бы определять при помощи макросов (возможность переопределять формы, при помощи макросов, тоже будет), но почему бы не предоставить удобную альтернативу, тем более, что её реализация почти ничего мне не стоит?

Если 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.

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

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

В Dagaz всё будет по другому! Во первых, я не считаю необходимым отражать в нотации хода все изменения состояния. Расширениям незачем заниматься парсингом, поскольку, вместе с записью хода, им будет передаваться IState, через который будет доступна вся информация о состоянии после выполнения хода. От нотации требуется лишь уникальность. Фактически, это просто имя хода из текущей позиции. Содержимое этой записи будет полностью определяться кодом DSL. Команда log формирует запись выполняемого хода (а в тех случаях, когда она не будет использована, можно генерировать имя хода автоматически). Кстати MoveLogger это ещё один класс, реализующий интерфейс ITransactional.

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

Разумеется, будет изменена семантика перемещения фигур. В ZoG, на всём протяжении расчёта хода, доступно лишь состояние на момент начала хода. Фигура, которую мы перемещаем, как бы остаётся на начальной позиции, пока ход не завершён. Звучит логично, но, на практике, портит невероятное количество крови и нервов. В Dagaz фигура будет явно сниматься с доски командой take, проноситься над доской «в руке» и возвращаться на доску, при помощи команды drop. После этого, без всяких дурацких cascade, from и to, можно будет взять и перенести другую фигуру, если этого требуют правила выполнения хода (например, при выполнении рокировки). Также (не в этой итерации), можно будет переносить несколько фигур одновременно «по одной траектории» (это требуется в таких играх как Ордо, Столбовые шашки, Таврели и пр.).

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

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

О unit-тестах


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

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

Комментарии (12)


  1. godlin
    05.11.2015 15:36
    +1

    Что-то мне кажется с декларативностью у Вас не очень получилось…


    1. GlukKazan
      05.11.2015 17:54

      Да, описание ходов, само по себе, довольно императивно, но здесь я отталкивался от существующих аналогов. И в ZoG и в Ludi и в Axiom оно примерно такое же, но только без any и инвариантов. Чего то более декларативного, в этой области, я не видел. Если что-то придумаете или найдёте, сообщите мне. Меня этот вопрос очень интересует.


      1. godlin
        05.11.2015 19:14

        Было бы неплохо, если бы сначала Вы где-нибудь объяснили начальный код («Очень простые шашки»), а то не всё понятно. :)


        1. GlukKazan
          05.11.2015 22:09

          как-то так:

             (pre                                  ; Предварительные действия (для любого из определённых (двух) ходов
                (check is-friend?)                 ; На текущей клетке дружественная фигура?
                (take)                             ; Взять её в руку
                (log position)                     ; Отметить начальную позицию (для нотации хода)
                (let captured 0)                   ;  Определяем переменную - счётчик взятых фигур
             )
             (post                                 ; Завершающие действия для любого из ходов
                (check (<= max-captured captured)) ; Взято фигур не меньше глобального счётчика?
                (set! max-captured captured)       ; Обновить глобальный счётчик
                (log " - " position)               ; Отметить конечную позицию (для нотации хода)
                (drop)                             ; Поместить фигуру на доску
             )
             (move                                 ; Тихий ход
                (check (any nw ne))                ; Двигаемся на северо-запад или северо-восток (если возможно)
                (check is-empty?)                  ; Позиция пуста?
             )
             (move                                 ; Бой фигур
                (while true                        ; Повторять в цикле
                   (let dir (any nw ne sw se))     ; Выбираем одно из 4 направлений
                   (check dir)                     ; Двигаемся в выбранном направлении (если это возможно)
                   (check is-enemy?)               ; Вражеская фигура?
                   (capture)                       ; Берём её (можно ещё и отметить промежуточную позицию командой log)
                   (inc! captured)                 ; Увеличиваем счётчик взятых фигур
                   (check dir)                     ; Продолжаем двигаться в том же направлении (если это возможно)
                   (check is-empty?)               ; Пустая клетка?
                   (end-move)                      ; В этом месте ход может быть завершён
                )
             )
          


      1. godlin
        05.11.2015 19:29

        Чтобы перейти к декларативному стилю, надо, в частности, while, скажем, менять на пару «состояние — действие». Например, я бы попробовал как-то так:

        1. задан список текущих позиций шашек А.

        2. если нет активной шашки, и есть шашки, у которых есть доступные ходы -> выбрать (any) активную шашку (из тех, что с доступными ходами)

        3. если нет активной шашки, и нет шашек, у которых есть доступные ходы -> конец игры

        4. если есть активная шашка и у неё есть варианты ходов-> сделать (any) возможный ход

        5. если есть активная шашка без вариантов хода -> снять с неё метку активности.

        Этот список прогоняется до тех пока не сработает пункт 3.

        Это навскидку :)


        1. GlukKazan
          05.11.2015 22:22

          while здесь не перебирает шашки на доске. Это цикл последовательных шагов в цепочечном взятии. Надеюсь, комментарии выше немного прояснили этот момент. Это моя промашка. Я настолько часто писал ZRF код, что посчитал всё это самоочевидным.


          1. godlin
            06.11.2015 00:59

            Фишка в том, что в при декларативном подходе не должно быть циклов. Должны быть рекурсии.


            1. GlukKazan
              06.11.2015 09:31

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


  1. godlin
    06.11.2015 14:57
    +1

    Вы заметили, что никто не комментирует, кроме меня?
    Возможно, это потому, что сквозь Ваш текст вообще крайне сложно прорваться (во всяком случае, для меня — точно ;))…

    Объясните, пожалуйста, почему в этом фрагменте:

    (game 
       (name chess-game)
       (loss 
          (exists?
             (any King)
             (if is-friend?
                 (check is-attacked?)
             )
             (check no-moves?)
          )
       )
    )
    

    написано:
             (if is-friend?
                 (check is-attacked?)
             )
             (check no-moves?)
    

    а не, скажем:
             (check is-friend?)
             (check is-attacked?)
             (check no-moves?)
    


    1. GlukKazan
      06.11.2015 19:56

      Это очень правильный вопрос. Дело в том, что предикат is-attacked? крайне дорогой в вычислительном отношении. По хорошему, чтобы проверить атакуется ли фигура на поле, необходимо выполнить просмотр ещё на один ход вперёд и найти ходы, атакующие фигуру на поле. Именно фигуру, а не пустое поле, поскольку в таких играх, как Ультима, тип атаки может зависеть от типа атакуемой фигуры (Хамелеон бьёт фигуры их атаками). В общем, хотелось ограничить количество обращений к столь дорогому предикату.

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

      (loss 
         (check no-moves?)
         (check (exists?
            (any King)
            (if is-friend?
                (check is-attacked?)
            )
         ))
      )
      

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

      Что касается сложности текста — ничего не могу поделать. Текст сложен. Тема сложная. Я старался изложить всё как можно проще, но не мне судить, насколько хорошо это удалось.


      1. GlukKazan
        06.11.2015 20:10

        Опять всё напутал. Вот код для Шахмат (надеюсь, теперь правильно).

        (loss 
           (check no-moves?)
           (check (exists?
              (any King)
              (check (and is-friend?
                  (check is-attacked?)
              ))
           ))
        )
        

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


    1. GlukKazan
      06.11.2015 20:01

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