Могу я в Тафл игратьДевять умений я знаю
Забываю нечасто руны
Ведаю книги и счёт
Умею скользить я на лыжах
Гребу и стреляю неплохо
Из искусств мне ведомы оба…
"Сага об оркнейцах"
История, которую я хочу рассказать, полна загадок, малопонятного кода, бессонных ночей, шума кошачьих шагов...
Это одна из тех историй, в которых процесс гораздо важнее результата. Если вам нужен результат, его можно найти здесь, но если вам интересны подробности, что же… я готов рассказать о своих мытарствах.
Начиналось всё как обычно. Sultan Ratrout, большой любитель настольных игр, нашёл один из моих роликов на YouTube и попросил разработать для него коллекцию наиболее известных игр семейства шашек. Просьба меня удивила. Сказать, что таких программ много — означает лишь несколько преуменьшить. Шашки имеются на любой вкус и для множества различных платформ. В одном только ZoG — более 20 наименований. Дьявол, по обыкновению, оказался скрыт в деталях.
Я уже писал о том, что реализовать шашки полностью корректно и аутентично совсем не просто. Правила превращения шашек в дамки (порой довольно сложные) и «правило большинства» (в его разнообразных трактовках) превращают такую разработку в настоящий тест на внимательность, а сложность реализации правила «турецкого удара», вообще заслуживает отдельного разговора. Увы, при более пристальном рассмотрении, «шашечные» программы для Zillions of Games оказались крайне далеки от идеала.
Первой ласточкой оказался баг, обнаруженный мной в коллекции шашек от Uwe Wiedemann. В его реализации «Русских шашек», шашка, оказавшаяся в зоне превращения в ходе боя, не продолжала ход в случае, если следующую шашку можно было взять только ходом дамки. Я опубликовал исправление и думал было на этом успокоиться, но взглянув на другие варианты, понял, что проще разработать свой набор игр чем исправить все ошибки в существующих реализациях. Даже вариант от самих разработчиков ZoG, поставляемый вместе с программой, работал с чудовищными ошибками!
В результате, я решил создать свою коллекцию шашек. Разумеется, начал я с внимательного анализа существующих реализаций. Из них же взял и графические ресурсы, подправив мелкие огрехи в графическом редакторе (тот же набор ресурсов уже использовался ранее несколькими авторами). Из программного кода я узнал много нового. Например, в «Турецких шашках», дамке, в ходе боя, запрещается изменять направление движения на противоположное. Вот как элегантно это реализуется:
Бой дамкой
(define dama-king-jump (
(while (empty? $1)
$1
)
(verify (enemy? $1))
$1
(verify (empty? $1))
$1
(while empty?
mark
(while empty?
(opposite $1)
)
capture
back
(add-partial continuetype)
$1
)
))
(define dama-king-continue (
(while (empty? $1)
$1
(verify not-last-from?)
)
(verify (enemy? $1))
$1
(verify (empty? $1))
$1
(while empty?
mark
(while empty?
(opposite $1)
)
capture
back
(add-partial continuetype)
$1
)
))
(game
(title "Turkish Dama")
...
(move-priorities jumptype normaltype)
(piece
(name King)
(image First "images/wiedem/CheckerKingWhite.bmp"
Second "images/wiedem/CheckerKingBlack.bmp")
(moves
(move-type jumptype)
(dama-king-jump n)
(dama-king-jump e)
(dama-king-jump w)
(dama-king-jump s)
(move-type continuetype)
(dama-king-continue n)
(dama-king-continue e)
(dama-king-continue w)
(dama-king-continue s)
(move-type normaltype)
(king-shift n)
(king-shift e)
(king-shift w)
(king-shift s)
)
)
)
Предикат last-from? проверяет, является ли текущее поле начальным полем предыдущего (частичного) хода. Если мы пересекаем такое поле — значит направление движения дамки изменилось на противоположное и ход выполнять нельзя. Разумеется, такая проверка не должна выполняться в рамках самого первого частичного хода. Здесь на помощь приходят режимы выполнения хода. Первый ход осуществляется в рамках приоритетного режима jumptype и выполняет переключение в continuetype, в рамках которого должны выполняться все последующие ходы. Выяснилось (я не знал этого раньше), что назначаемый явно continuetype не требуется упоминать в списке приоритетов.
Другой приятной неожиданностью оказался способ расчёта «длинного» хода, при бое дамкой, когда дамка, может останавливаться не только на поле следующем непосредственно за сбитой фигурой (как в "Тайских шашках"), но и на любом следующем за ним свободном поле. Выяснилось, что необязательно писать портянки из «копи-паста»:
Возможное описание боя дамкой
(define king-jump-1 (
(while (empty? $1)
$1
)
$1
(verify enemy?)
capture
$1
(verify empty?)
(add-partial jumptype)
))
(define king-jump-2 (
(while (empty? $1)
$1
)
$1
(verify enemy?)
capture
$1
(verify empty?)
$1
(verify empty?)
(add-partial jumptype)
))
(define king-jump-3 (
(while (empty? $1)
$1
)
$1
(verify enemy?)
capture
$1
(verify empty?)
$1
(verify empty?)
$1
(verify empty?)
(add-partial jumptype)
))
...
Напомню, что проблема заключается в том, что очевидная реализация приводит к ошибке, в процессе генерации хода:
Этот код не работает!
(define king-jump (
(while (empty? $1)
$1
)
$1
(verify enemy?)
capture
$1
(while empty?
(add-partial jumptype)
$1
)
))
Правильная реализация чем-то напоминает алгоритм маляра Шлемиэля. От точки возможного завершения хода (в цикле их генерируется несколько), необходимо вернуться в противоположном направлении и удалить первую встреченную вражескую фигуру. Это смешно, но только такой способ и работает!
Альтернативное решение
(define king-jump (
(while (empty? $1)
$1
)
(verify (enemy? $1))
$1
(verify (empty? $1))
$1
(while empty?
mark
(while empty?
(opposite $1)
)
capture
back
(add-partial continuetype)
$1
)
))
Если вы улыбаетесь, значит мы двигаемся в правильном направлении. Но погодите, мы еще не рассматривали «турецкий удар»! Для того, чтобы не «взять» фигуры противника повторно, их необходимо как-то пометить. Сделать это можно двумя способами. Можно изменить тип фигуры, либо использовать один из её атрибутов (последний способ недоступен в Axiom). По завершении составного хода, можно удалить все ранее помеченные фигуры.
Турецкий удар (использование атрибутов)
(define checker-captured-find
mark
(if (on-board? $1)
$1
(if (and enemy? (empty? $1) (not captured?))
(set-flag more-captures true)
)
)
back
)
(define checker-jump (
$1
(verify enemy?)
(verify (not captured?))
(set-attribute captured? true)
$1
(verify empty?)
(set-flag more-captures false)
(checker-captured-find $1)
(checker-captured-find $2)
(checker-captured-find $3)
(if (not (flag? more-captures))
mark
a0
(while (on-board? next)
next
(if captured? capture)
)
back
)
(if (in-zone? promotion)
(add King)
else
(add-partial jumptype)
)
))
...
(piece
(name Checker)
(image First "images/wiedem/CheckerWhite.bmp"
Second "images/wiedem/CheckerBlack.bmp")
(attribute captured? false)
(moves
(move-type jumptype)
(checker-jump nw sw ne)
(checker-jump sw se nw)
(checker-jump ne se nw)
(checker-jump se ne sw)
(move-type normaltype)
(checker-shift nw)
(checker-shift ne)
)
)
Для простоты, здесь рассматривается английский вариант шашек. Решение с «дальнобойными» дамками выглядит сложнее. Самый не очевидный момент в этом коде — определение момента завершения составного хода. Решение довольно прямолинейно — чтобы определить, имеет ли ход продолжение, просто выполняем поиск фигуры, которую мы можем «съесть» далее, в одном из трёх направлений (поскольку направления, с точки зрения ZoG, никак не взаимосвязаны, все три приходится передавать в макрос). Это должно работать! Но это не работает:
В чём дело? Возможно что-то не так с атрибутами? Попробуем изменять тип фигуры:
Турецкий удар (изменение типа фигур)
(define checker-captured-find
mark
(if (on-board? $1)
$1
(if (and enemy? (empty? $1) (not (piece? XChecker)))
(set-flag more-captures true)
)
)
back
)
(define checker-jump (
$1
(verify enemy?)
(verify (not (piece? XChecker)))
(change-type XChecker)
$1
(verify empty?)
(set-flag more-captures false)
(checker-captured-find $1)
(checker-captured-find $2)
(checker-captured-find $3)
(if (not (flag? more-captures))
mark
a0
(while (on-board? next)
next
(if (piece? XChecker) capture)
)
back
)
(if (in-zone? promotion)
(add King)
else
(add-partial jumptype)
)
))
...
(piece
(name Checker)
(image First "images/wiedem/CheckerWhite.bmp"
Second "images/wiedem/CheckerBlack.bmp")
(moves
(move-type jumptype)
(checker-jump nw sw ne)
(checker-jump sw se nw)
(checker-jump ne se nw)
(checker-jump se ne sw)
(move-type normaltype)
(checker-shift nw)
(checker-shift ne)
)
)
(piece
(name XChecker)
(image First "images/wiedem/CheckerWhite.bmp"
Second "images/wiedem/CheckerBlack.bmp")
)
Уже лучше! По крайней мере, этот зомби не пытается нас съесть! Именно так и выглядит эта ошибка в официальной редакции «Русских шашек» от разработчиков Zillions of Games. Последняя взятая фигура не удаляется с доски. Ходить она конечно не может, но мешает движению других фигур! Для того, чтобы разобраться, в чём тут дело, выгрузим протокол этой «мини-игры» в ZSG-файл:
ZSG-лог
1. partial 2 Checker a5 — c7 = XChecker on b6
1. partial 2 Checker c7 — e5 = XChecker on d6
1. partial 2 Checker e5 — g7 = XChecker on f6 x b6 x d6
1. partial 2 Checker c7 — e5 = XChecker on d6
1. partial 2 Checker e5 — g7 = XChecker on f6 x b6 x d6
Всё дело в последнем ходе. Мы «помечаем» фигуру на поле f6 для удаления, но не удаляем её вместе с другими! Очевидно, что программа просто не может этого сделать. При использовании атрибутов, лог выглядит сложнее, но суть остаётся неизменной. Мы не можем удалить фигуру, с которой что-то делали в рамках того же частичного хода. Меняли ли мы атрибут или тип фигуры — неважно. Немедленное удаление такой фигуры — несовместимо с возможностями ZSG-нотации!
Решение проблемы очевидно, хотя и не делает код более «читабельным». Последнюю фигуру «помечать» не нужно, её надо просто «брать»:
Бой в русских шашках
(define russian-checker-jump (
(verify (not captured?))
$1
(verify enemy?)
(verify (not captured?))
$1
(verify empty?)
(set-flag more-captures false)
(if (in-zone? promotion)
(king-captured-find $1)
(king-captured-find $2)
(king-captured-find $3)
else
(checker-captured-find $1)
(checker-captured-find $2)
(checker-captured-find $3)
)
(if (flag? more-captures)
(opposite $1)
(markit)
$1
)
(if (not (flag? more-captures))
(opposite $1)
(if enemy?
capture
)
$1
(capture-all)
)
(if (in-zone? promotion)
(if (flag? more-captures)
(add-partial King jumptype)
else
(add King)
)
else
(if (flag? more-captures)
(add-partial jumptype)
else
add
)
)
))
Разобравшись со всеми этими проблемами, я быстренько «наштамповал» джентельменский набор игр, включающий в себя обязательные турецкие, армянские, английские и русские шашки. Экзотика была представлена осетинскими и хакасскими шашками, но коллекции всё ещё не хватало «изюминки».
Эту позицию я решил застолбить за "Северными шашками". От привычных нам «Русских шашек» этот вариант отличается всего одним правилом: «съеденная» дамка не убирается с доски, а «понижается в звании» до обычной шашки. Это, казалось бы, небольшое отличие в корне меняет характер игры в эндшпиле. Достаточно сказать, что две дамки довольно легко ловят одну, даже в том случае, если она находится на «большаке» — главной диагонали доски!
Выбор был сделан, осталось воплотить его в жизнь. Первый вариант играл приблизительно так:
Очень брутально, но не совсем так как хотелось. Когда в игре (как в Chu Shogi) есть всего пара фигур, способных «съесть» любую фигуру противника и вернуться на место в течение одного хода, это может быть забавно, но когда таких фигур много и они дальнобойные… геймплей серьёзно страдает. Стало понятно, что надо как-то запрещать возможность повторного «поедания» фигуры в течение одного хода, но как это сделать?
В ZoG выбор невелик. Предикат last-from?, не позволит решить проблему, так как дамка, способна «съесть» фигуру на возвратном движении и не дойдя до стартового поля предыдущего хода. Позиционные флаги, позволяющие привязать булевское значение к произвольному полю, увы, не подошли. Было большое искушение воспользоваться ими, поскольку документация гарантирует их автоматическую очистку в начале каждого хода.
К сожалению, эта очистка происходит в начале каждого частичного хода и, как средство передачи информации между частичными ходами, позиционные флаги совершенно бесполезны! Остались атрибуты. Можно помечать «взятые» фигуры установкой атрибутов, но, в этом случае, мы должны позаботится об их очистке между составными ходами.
С этим и был связан очередной баг (заметить и локализовать его было непросто). Хотя очистка атрибутов и выполнялась при перемещении фигур, атрибут той фигуры, которая выполняла ход, похоже не очищался. Разобраться с этим вновь помог ZSG-лог (в списке ходов, отображаемых программой, информация об изменении значений атрибутов скрывается):
ZSG-лог
1. partial 3 King d8 — a5 = Checker on c7 @ c7 0 1
1. partial 3 King a5 — e1 = Checker on c3 @ c3 0 1
1. Checker c7 — b6 @ c3 0 0 @ c7 0 0
2. partial 3 King e1 — a5 x c3
2. Checker b6 — c5 @ b6 0 0
1. partial 3 King a5 — e1 = Checker on c3 @ c3 0 1
1. Checker c7 — b6 @ c3 0 0 @ c7 0 0
2. partial 3 King e1 — a5 x c3
2. Checker b6 — c5 @ b6 0 0
В третьей строке можно видеть, что очистка атрибутов производится, но атрибут очищается на позиции c7, в то время как фигура уже переместилась с этого поля на b6! После внесения необходимых исправлений, всё стало работать так, как планировалось:
north-shift
(define clear-all
mark
a0
(while (on-board? next)
next
(if (piece? Checker)
(set-attribute captured? false)
)
)
back
)
(define north-shift (
(clear-all)
$1
(verify empty?)
(if (in-zone? promotion)
(add King)
else
+ (set-attribute captured? false)
add
)
))
Оставалась ещё одна проблема. В начале игры, «Северные шашки» ничем не отличались от «русских», а до дамок надо было ещё дожить. Так родился вариант «Северные короли», в котором игра начиналась с дамок! Массовая доступность дальнобойных дамок в самом начале игры, а также их феноменальная живучесть обеспечили игре совершенно уникальный, «взрывной» геймплей. Эту игру я считаю «жемчужиной» своей коллекции:
На этой радостной ноте можно было бы и закончить. В самом деле, коллекция готова, всё работает, в ней есть пара-тройка уникальных игр. Но несколько моментов серьёзно омрачают мою радость. Во первых, эти постоянные «танцы на граблях» делают код таким запутанным, что я не поручусь за то, что в нём совсем не осталось ошибок (и это гложет меня по ночам). Кроме того, часть проблем мне так и не удалось решить.
В «Ossetian Kena» шашки могут перепрыгивать через дружественные фигуры. Хочется иметь возможность перемежать такие ходы с боем вражеских фигур в произвольном порядке, но это не работает! Даже без учёта того, что для таких ходов (даже теоретически) сделать взятие обязательным невозможно, сама попытка «зациклить» ходы таким образом приводит к немедленной ошибке.
Осетинские Кены
(piece
(name Checker)
(image First "images/wiedem/CheckerWhite.bmp"
Second "images/wiedem/CheckerBlack.bmp")
(moves
(move-type jumptype)
(checker-jump n)
(checker-jump e)
(checker-jump w)
(checker-jump s)
(move-type continuetype)
(checker-jump n)
(checker-jump e)
(checker-jump w)
(checker-jump s)
; (ken-jump-variant n)
; (ken-jump-variant e)
; (ken-jump-variant w)
; (ken-jump-variant s)
(move-type normaltype)
(checker-shift n)
(checker-shift e)
(checker-shift w)
(ken-jump-variant n)
(ken-jump-variant e)
(ken-jump-variant w)
(ken-jump-variant s)
)
)
Стоит убрать эти комментарии и всё ломается! Даже если помечать дружественные фигуры, запрещая повторные прыжки через них, это не помогает. Если говорить о «пометках», то большой удачей является то, что ни в одном из вариантов шашек не требуется запрещать повторное прохождение через пустые поля. Это удача, поскольку реализовать такой запрет в ZoG нельзя (во всяком случае простым способом). Позиционные флаги могли бы помочь в этом, но… видимо не в нашей вселенной.
ZoG, в свою очередь, всегда готова подложить новый сюрприз:
Да, да, программа ведёт себя по разному в зависимости от того, выполняется ли она под управлением AI или в ручном режиме! Дальнобойные дамки, правило большинства и турецкий удар — когда все «три всадника» собираются вместе… AI может начать вести себя странно. Причём, даже когда я снимал этот ролик, ошибка проявлялась не детерминированно — иногда бралась одна шашка, иногда две. Я не знаю как с этим бороться. Приходится идти на компромисс с совестью и отключать одну из трёх опций. Например, в «Международных шашках» пришлось отказаться от «правила большинства».
В любой, даже самой большой, бочке мёда всегда найдётся место для маленькой ложечки дёгтя…
Vitter
Да уж, мир не совершенен (Гёдель).
Языки описания также несовершенны.
Гибче язык — проще описание.
GlukKazan Автор
Да, мир не совершенен. Но удивителен.