Мы расшатали ваши умственные фильтры, и в результате появился ответ. Метод сработал, он будет действенным всегда. Все, что необходимо сделать — это избавиться от лишнего груза предрассудков…Раймонд Джоунс "Уровень шума"
Dagaz появился не на пустом месте. Я всегда увлекался настольными играми и головоломками, а программированием занимаюсь сколько себя помню, но мысль о некоем «универсальном» движке просто не могла бы прийти мне в голову. К самой этой идее я относился скептически. Пока не увидел Zillions. К сожалению, продукт, на тот момент, уже не развивался, исходный код был недоступен, да и вообще, программа работала только под Windows. Спустя некоторое время, я решил взяться за открытый проект.
Как я уже сказал, никаких исходных кодов у меня не было, но немного "пощупав" Zillions, я уловил его главную идею — максимальное повторное использование прикладного кода, позволяющее использовать одни и те же конструкции в различных, казалось бы совершенно не похожих друг на друга случаях. Всё дело было в правильно подобранных usecase-ах. И я составил план.
Шашки
Это важное, но крайне недооценённое семейство игр заложило первый камень в фундамент проекта. Все «шашечные» игры похожи друг на друга и различаются лишь в деталях. С точки зрения игрового дизайна, все они объединяются тремя главными идеями:
- Шашечным взятием
- Приоритетом взятия
- Составным ходом
Первый пункт особых вопросов не вызывает, но если разработка ориентирована на шахматные игры, может оказаться неожиданностью. Далеко не во всех играх, взятие происходит на том же поле, где фигура завершает движение. С приоритетными ходами всё немного интереснее. В шашках, это правило позволяет строить сложную комбинационную игру, заманивая противника в ловушки, работающие по принципу «отдать меньше — забрать больше».
Разумеется, механизм приоритетных ходов был реализован в Zillions (и перекочевал оттуда в Dagaz). Без него практически все шашечные игры (безусловно входящие в «джентельменский набор» настольных игр обязательных к реализации) просто не могли бы работать правильно. Здесь всё дело в деталях. Посмотрим, как этот механизм был реализован:
В Zillions
(move-priorities jump-type normal-type)
...
(define checker-shift (
$1 (verify empty?) ; Двигаемся вперёд и проверяем что поле пусто
add ; Завершаем ход
))
(define checker-jump (
$1 (verify enemy?) ; Двигаемся вперёд и проверяем что там вражеская фигура
capture ; Берём её (вызов capture необходим - взятие не шахматное)
$1 (verify empty?) ; Двигаемся в том же направлении и проверяем что поле пусто
add ; Завершаем ход
))
...
(piece
(name Man)
(image White "images/stapeldammen/white.bmp"
Red "images/stapeldammen/red.bmp")
(moves
(move-type jump-type)
(checker-jump nw) (checker-jump ne) (checker-jump sw) (checker-jump se)
(move-type normal-type)
(checker-shift nw) (checker-shift ne)
)
)
Это практически полное описание простейшей шашечной игры. В ZRF введено понятие режимов хода (move-type), а конструкция move-priorities позволяет сказать, что при наличии ходов более приоритетных (взятий), менее приоритетные (тихие ходы) рассматриваться не должны. Уровней приоритета может быть определено и больше двух, в этом плане, конструкция достаточно универсальна, но работая над играми в Dagaz, я столкнулся с некоторыми ограничениями этого механизма.
В этой игре, придуманной Соломоном Голомбом, помимо шашек, присутствуют и шахматные фигуры. Сложность заключается в том, что взятие, оставаясь приоритетным для шашечных фигур, не является таковым для фигур шахматных (в противном случае их было бы слишком легко заманить в ловушку и съесть). Наивное определение приоритетов при помощи ключевого слова move-priorities, в этой игре, работать не будет.
В самом деле, если не включать взятия шахматными фигурами в состав приоритетных ходов, при наличии возможности взятия как шашечной фигурой так и шахматной, мы не сможем сходить шахматной фигурой, поскольку шашечное взятие приоритетно. Если же считать шахматные взятия столь же приоритетными, мы будем обязаны брать шахматными фигурами всегда, когда предоставится такая возможность. И то и другое противоречит правилам игры.
В Zillions эта проблема практически не решается. И это было главной причиной, по которой я задумался о введении в Dagaz механизма JavaScript-расширений. Идея, сама по себе, довольно простая: поскольку некоторые игровые механики довольно сложно выразить в ZRF, почему бы не ввести фазу пост-обработки ходов? Модуль расширения, в этом случае, просматривает весь список сгенерированных ходов целиком и может принимать решения об отбраковке тех или иных ходов. Вот как это выглядит для "Шашмат":
Простой и компактный код
var CheckInvariants = Dagaz.Model.CheckInvariants;
Dagaz.Model.CheckInvariants = function(board) {
var design = Dagaz.Model.design;
var types = [];
types.push(design.getPieceType("Bishop"));
types.push(design.getPieceType("Camel"));
var isPriority = false;
_.each(board.moves, function(move) {
if (isCapturing(board, move)) {
if (_.indexOf(types, getType(board, move)) < 0) isPriority = true;
}
});
if (isPriority) {
_.each(board.moves, function(move) {
if (!isCapturing(board, move)) {
move.failed = true;
}
});
}
CheckInvariants(board);
}
В дальнейшем, идея расширений развивалась и цвела пышным цветом. Я получил удобный и мощный механизм для кодирования многих игр, реализация которых на чистом ZRF была бы крайне проблематична, но означает ли это, что определение приоритетов в стиле ZRF устарело? Разумеется нет! Во первых, написать одну строку на ZRF проще чем полсотни на JavaScript, но, что более важно, «жёсткие» приоритеты в стиле ZRF работают таким образом, что низко-приоритетные ходы даже не генерируются! Это важно, с точки зрения производительности. Генерация ходов в Dagaz — очень дорогая операция.
Еще одна игра со сложными приоритетами
Dablot — игра чем-то похожая на "Итальянские шашки", но более древняя. Помимо обычных фигур, в ней есть «принцы» и «короли» и младшие фигуры не имеют права бить старших. Но сложность не в этом. Для королей (а в некоторых разновидностях игры и для принцев тоже) взятие не является обязательным! Здесь возникает та же проблема, что и с Шашматами. Если мы объявим взятия королём приоритетными, то грубо нарушим правила игры, в противном же случае, мы не сможем бить королём при возможности альтернативного боя простой фигурой. Только механизм расширений Dagaz решает эту проблему.
Кстати, с «Итальянскими шашками» всё не так просто. Во многих разновидностях шашек существует правило гласящее, что игрок обязан брать максимальное количество фигур. То есть, не просто не может прервать цепочку взятий, а обязан выбрать тот путь, фигур на котором он возьмёт больше! По причинам, о которых я расскажу ниже, это правило не могло быть реализовано в Zillions в универсальном виде и разработчики были вынуждены его захардкодить. В итальянских шашках «правило большинства» звучит ещё сложнее: «бить нужно максимально возможное количество шашек соперника, а при равных вариантах боя нужно бить максимальное количество дамок».
Dablot — игра чем-то похожая на "Итальянские шашки", но более древняя. Помимо обычных фигур, в ней есть «принцы» и «короли» и младшие фигуры не имеют права бить старших. Но сложность не в этом. Для королей (а в некоторых разновидностях игры и для принцев тоже) взятие не является обязательным! Здесь возникает та же проблема, что и с Шашматами. Если мы объявим взятия королём приоритетными, то грубо нарушим правила игры, в противном же случае, мы не сможем бить королём при возможности альтернативного боя простой фигурой. Только механизм расширений Dagaz решает эту проблему.
Кстати, с «Итальянскими шашками» всё не так просто. Во многих разновидностях шашек существует правило гласящее, что игрок обязан брать максимальное количество фигур. То есть, не просто не может прервать цепочку взятий, а обязан выбрать тот путь, фигур на котором он возьмёт больше! По причинам, о которых я расскажу ниже, это правило не могло быть реализовано в Zillions в универсальном виде и разработчики были вынуждены его захардкодить. В итальянских шашках «правило большинства» звучит ещё сложнее: «бить нужно максимально возможное количество шашек соперника, а при равных вариантах боя нужно бить максимальное количество дамок».
Составные ходы — вторая важная составляющая шашечных игр. Настолько важная, что тест на правильность взятия в "Турецких шашках" я периодически запускаю до сих пор. Пару раз, когда я ломал модель очередными изменениями, это действительно помогало.
Ходы - составные и частичные
Вот так вот всё просто. Команда add-partial говорит, что ход можно продолжить (той же фигурой, это важно) если есть ещё ходы с указанным режимом. Иными словами: «фигура должна продолжать взятие, пока есть такая возможность». Вроде бы, всё замечательно, но есть один нюанс. Zillions рассматривает каждое такое взятие как отдельный «частичный» ход. Посмотрим, к чему это может привести.
В этой игре, количество «шажков», выполняемых фигурой, определяется значком, на котором она стоит. Сейчас ход белых и ходит Damyo (фигура обозначенная красной бусинкой). В Zillions, выполнив два частичных хода, она легко может зайти в левый верхний угол, из которого уже не сможет сделать последний оставшийся ход (назад возвращаться нельзя). Брать фигуру противника на втором частичном ходу также запрещено. В Zillions нет никакой возможности, для того чтобы запретить последовательность ходов, заводящую в тупик.
В Dagaz — всё по другому! Последовательность частичных ходов всегда собирается в полный составной ход. Ход, который не удаётся завершить, попросту не соберётся! Это более ресурсозатратный подход, в результате чего генерация списка ходов в Dagaz — очень дорогая операция. Но и плюсы у него весомые. Например бот получает весь составной ход целиком и не должен просматривать позицию вперёд, выполняя оставшиеся частичные ходы.
Ещё более важно, что такой подход предоставляет возможность рассматривать весь список условно-допустимых ходов, выполняя более сложные проверки и запрещать одни ходы в зависимости от наличия других. Например «правило большинства», о котором я упоминал выше, в Dagaz реализуется совершенно элементарно. Причём, и для «Итальянских шашек» тоже. Разработчики Zillions «решили» известную им проблему для шашечных игр, захардкодив опцию "maximal captures", но существует огромное количество игр с другими сложными проверками, о которых они, на тот момент, не имели ни малейшего представления!
Посмотрим, как в ZRF реализованы составные ходы
(define checker-shift (
$1 (verify empty?)
(if (in-zone? promotion)
(add King)
else
add
)
))
(define checker-jump (
$1 (verify enemy?)
capture
$1 (verify empty?)
(if (in-zone? promotion)
(add King)
else
(add-partial jump-type)
)
))
(define king-shift (
$1 (verify empty?)
add
))
(define king-jump (
$1 (verify enemy?)
capture
$1 (verify empty?)
(add-partial jump-type)
))
Вот так вот всё просто. Команда add-partial говорит, что ход можно продолжить (той же фигурой, это важно) если есть ещё ходы с указанным режимом. Иными словами: «фигура должна продолжать взятие, пока есть такая возможность». Вроде бы, всё замечательно, но есть один нюанс. Zillions рассматривает каждое такое взятие как отдельный «частичный» ход. Посмотрим, к чему это может привести.
В этой игре, количество «шажков», выполняемых фигурой, определяется значком, на котором она стоит. Сейчас ход белых и ходит Damyo (фигура обозначенная красной бусинкой). В Zillions, выполнив два частичных хода, она легко может зайти в левый верхний угол, из которого уже не сможет сделать последний оставшийся ход (назад возвращаться нельзя). Брать фигуру противника на втором частичном ходу также запрещено. В Zillions нет никакой возможности, для того чтобы запретить последовательность ходов, заводящую в тупик.
В Dagaz — всё по другому! Последовательность частичных ходов всегда собирается в полный составной ход. Ход, который не удаётся завершить, попросту не соберётся! Это более ресурсозатратный подход, в результате чего генерация списка ходов в Dagaz — очень дорогая операция. Но и плюсы у него весомые. Например бот получает весь составной ход целиком и не должен просматривать позицию вперёд, выполняя оставшиеся частичные ходы.
Ещё более важно, что такой подход предоставляет возможность рассматривать весь список условно-допустимых ходов, выполняя более сложные проверки и запрещать одни ходы в зависимости от наличия других. Например «правило большинства», о котором я упоминал выше, в Dagaz реализуется совершенно элементарно. Причём, и для «Итальянских шашек» тоже. Разработчики Zillions «решили» известную им проблему для шашечных игр, захардкодив опцию "maximal captures", но существует огромное количество игр с другими сложными проверками, о которых они, на тот момент, не имели ни малейшего представления!
В процессе работы над новыми играми, концепция составного хода также развивалась. Fanorona и Pasang подсказали интересную игровую механику, в рамках которой группа снимаемых с доски фигур должна выбираться игроком, выполняющим ход:
Также, Fanorona — одна из тех редких игр, в которых игрок имеет право прерывать цепочку взятий. Первое взятие в ней обязательно, последующие, в рамках того же хода — на усмотрение игрока. В Dagaz эта опция (pass-partial) реализована ходом фигуры «на месте». Здесь могут быть missclick-и это, по всей видимости, не очень удобно, но с введением в проект session-manager-а, ошибочные ходы стало возможно откатывать.
Дальнейшим развитием темы стали «стреляющие» ходы. Впервые я сделал их в Hanga Roa и Ko Shogi, но, как выяснилось позже, сделал неправильно! Ошибочная реализация не работала под управлением ботов (а поскольку никаких ботов для обеих этих игр у меня нет до сих пор, не удивительно, что я ничего не заметил). Много позже, когда я делал "Амазонок", мне удалось локализовать проблему и исправить её. Своего расцвета эта идея достигла в игре, придуманной одним из наших соотечественников в далёком 1957 году.
Есть ещё одна проблема, связанная с реализацией составных ходов в Dagaz. Дело в том, что список допустимых ходов, из конкретного игрового состояния, формируется сразу — весь целиком. В Zillions, с её частичными ходами, это не очень критично, но в Dagaz, если фигура получит возможность «кружить на месте», фаза генерации хода никогда не будет завершена (очевидно, что исправить эту проблему расширениями невозможно, потому что до них дело просто не доходит). Вот одна из игр, для которых это важно:
Здесь фигуры с доски не убираются и одну и ту же фигуру можно перепрыгивать много раз подряд. Очевидным решением является запрет на посещение одного и того же поля дважды за ход, но мне пришлось основательно влезть в ядро, чтобы реализовать такую проверку. Это немножко напоминало реализацию опции "отложенного взятия", но поскольку "Русские шашки" я делал гораздо раньше, то и проблем с ней было намного меньше.
К сожалению, есть игры, в которых даже такие проверки не спасают
В правилах Stapeldammen (это такая разновидность "Столбовых шашек" явно указывается, что одну и ту же фигуру можно бить по нескольку раз за ход. Фигура, выполняющая ход, возвращается на одни и те же позиции по нескольку раз и продолжает бой, пока во вражеских столбиках есть фигуры. Составные ходы Dagaz не могут справиться с этой проблемой. Логика боя «Столбовых шашек» слишком сложна для ядра, а до расширений дело не дойдёт, поскольку поскольку генерация хода зацикливается. Разумеется, выход есть:
В Dagaz нет частичных ходов, но мы можем их сэмулировать, пропуская очередной ход противником (тот же подход используется в манкалах). И как раз эта логика легко реализуется расширением. Просто запрещаем все ходы, при определённых условиях, а опция pass-turn=forced автоматически генерирует пустой ход. Вот ещё одна игра с подобной эмуляцией.
Искусственное разделение составных ходов на частичные не очень хорошо для AI ботов, но иногда, просто не остаётся другого выхода.
В Dagaz нет частичных ходов, но мы можем их сэмулировать, пропуская очередной ход противником (тот же подход используется в манкалах). И как раз эта логика легко реализуется расширением. Просто запрещаем все ходы, при определённых условиях, а опция pass-turn=forced автоматически генерирует пустой ход. Вот ещё одна игра с подобной эмуляцией.
Искусственное разделение составных ходов на частичные не очень хорошо для AI ботов, но иногда, просто не остаётся другого выхода.
В общем, концепция составных ходов живёт и развивается. Совсем недавно, мне пришлось сделать ещё одну новую опцию (complete-partial) для одной древнеегипетской игры.
Помимо автоматического завершения перемещения фигур по стрелочкам, в ней есть и другие интересные технические решения. Но об этом как-нибудь в другой раз.
