Знание — сила.
Фрэнсис Бэкон.
… во многой мудрости много печали;
и кто умножает познания, умножает скорбь.
Книга Экклезиаста.
Игры живут своей жизнью. Они возникают из ниоткуда, развиваются, порождают новые игры, забываются всеми и, порой, вновь возвращаются из забвения. В истории немало примеров игр, потерпевших поражение в этом процессе естественного отбора. Таковы разнообразные варианты Сёги, дошедшие до наших дней лишь благодаря трепетному отношению жителей Японии к своему культурному наследию. Партия в игру, подобную Taikyoku shogi, могла затянуться на месяцы (если не на годы). Но эти шахматные динозавры эпохи Хэйан не являются самыми яркими представителями «ископаемого» мира настольных игр.
Я хочу рассказать о поистине удивительной игре. Угрозы в ней не очевидны, а цели не тривиальны. Победить можно множеством способов, но играть совсем не легко. Её нельзя отнести ни к семейству Шашек ни к шахматному семейству. Происхождение её туманно. Для среднестатистического обывателя, эта игра примерно столь же увлекательна, сколь и составление магических квадратов. Она полностью оправдывает одно из своих названий — играть в неё могут только философы.
Впервые, Rithmomachia, также известная как «Битва чисел» или «Игра философов» была описана, приблизительно, в 1030 году монахом по имени Asilo. Авторство, по всей видимости безосновательно, приписывается Платону, а правила игры основаны на арифметической теории Боэция. Впоследствии, правила игры были незначительно изменены другим монахом, по имени Hermannus Contractus, добавившим примечания, посвященные теории музыки. Продолжительное время Ритмомахия использовалась в качестве учебного пособия, при обучении студентов математике. Интеллектуалы того времени играли в Ритмомахию для удовольствия (одно время она была даже более популярна чем Шахматы), Роберт Бёртон упоминал её в "Анатомии меланхолии", а Томас Мор считал эту игру хорошим досугом для обитателей своей "Утопии". Затем, внезапно, всё кончилось. Интересы математики и Ритмомахии разошлись и игра была забыта. Разумеется, это не означает, что мы не можем её вспомнить.
В Ритмомахию играют два игрока на прямоугольной доске 8x16 клеток. Ходы совершаются поочерёдно. За каждый ход перемещается одна фигура. В результате хода, может быть взята (снята с доски) одна или более фигур противника. Определены следующие типы фигур:
Не обращая внимания на числовые пометки на фигурах (о них я скажу ниже), можно заметить, что допускается два типа ходов. В первом случае, фигура движется по прямой и может быть остановлена любой другой фигурой (своей или противника), находящейся на пути. Таким образом перемещается Круг (на одну клетку по диагонали), а также Треугольник (строго две клетки по ортогонали) и Квадрат (строго три клетки по ортогонали). Другой возможностью является «прыжок» фигуры на целевую клетку, наподобие хода Коня в Шахматах. Так может ходить Треугольник или Квадрат. Любой ход должен выполняться только на пустую клетку.
Уникальной фигурой является Пирамида. Собственно это не фигура, а набор фигур. Каждая фигура в наборе (Круг, Треугольник или Квадрат) даёт возможность Пирамиде выполнять соответствующий тип хода. На рисунке выше, показаны возможные ходы Пирамиды в «максимальной комплектации». Как легко догадаться, к концу игры, «комплектность» может быть сильно нарушена (к слову сказать, Пирамида из Ритмомахии — это единственная известная мне фигура, которую можно «убивать по частям»).
Остановлюсь подробнее на способах «убийства». В Ритмомахии их четыре:
Наиболее радикальным является взятие фигуры «в осаду». Фигура будет снята, если после очередного хода она окажется блокирована по всем диагональным или ортогональным направлениям. Если фигура расположилась у края доски или в углу — блокировать придётся меньшее количество направлений. Это простейший (но не единственный) способ взять Пирамиду всю сразу — целиком. Взятие «в осаду» — единственный способ, не использующий числовые значения фигур.
Другим способом является взятие фигуры с совпадающим числовым значением. Если, после выполнения хода, на поле, куда следующим своим ходом могла бы переместиться фигура (если бы это поле было пустым, разумеется) расположена фигура противника, с тем же числовым значением, она будет взята. Следует отметить, что этот способ боя может быть несимметричным. Так (на рисунке выше), после хода белых, Круг, с числовым значением 16, может взять чёрный Треугольник с тем же значением, но Треугольник, на своём ходу, этого сделать не может, поскольку ходит на другие клетки. В то же время, белый и чёрный треугольники с числовыми значениями 25 бьют друг друга симметрично (то какая фигура будет снята — определяется очередностью хода).
Усовершенствованным вариантом предыдущего является следующий способ. В этот раз, «из засады», нападают две фигуры. Если сумма, разность, произведение или частное их числовых значений совпадёт с числовым значением на фигуре противника — фигура снимается. Это наиболее часто используемая возможность боя фигур в игре, но увидеть все такие угрозы, в более менее сложной позиции, может быть совсем не просто.
Последний способ позволяет бить фигуры на дальнем расстоянии. Если результат произведения или частного числового значения фигуры и расстояния до фигуры противника (по ортогонали) совпадает с числовым значением фигуры противника — фигура снимается. Другие фигуры, расположенные по направлению боя, не препятствуют угрозе. При расчёте расстояния, учитываются начальная и конечная позиции. Это симметричный способ боя (поскольку он не зависит от правил перемещения фигур). Очередность хода определяет, какая из фигур будет снята.
Осталось рассказать о том, как эти правила распространяются на Пирамиды. С этим всё просто — в любых подсчётах на взятие фигур, Пирамида может выступать либо как самостоятельная фигура (её числовое значение совпадает с суммой числовых значений всех её компонентов), либо как любая из её частей. Аналогично этому, Пирамида может быть взята как целиком (по её суммарному значению), так и по частям (уязвим каждый из её компонентов в отдельности). С учетом правил перемещения Пирамиды, о которых я говорил выше, это делает Пирамиду самой сильной (и самой уязвимой) фигурой.
Начальная расстановка фигур связана с еще одной важной особенностью игры. Хотя набор фигур одинаков, числовые значения различаются. Также, различна «комплектация» пирамид (показана сбоку от доски, для каждого из игроков). Это делает игру ассиметричной. Тактические приемы и стратегии, для чёрного игрока не годятся для белых (и наоборот). Это делает игру более интересной.
Описанных выше правил достаточно, чтобы начать играть в Ритмомахию, но если бы целью игры было простое взятие всех фигур противника, игра не была бы столь интересной. Да, победить можно и таким образом, но это не единственный (и не лучший) способ одержать победу! Мне очень нравятся игры, целью которых не является прямолинейное «убийство» фигур противника. Так в Шахматах, для победы, совсем не обязательно «есть» все фигуры, достаточно поставить мат Королю! В некоторых вариантах Hasami Shogi, цель игры еще более неожиданная (для победы необходимо построить линию из 5 своих фишек «в ряд»). Ритмомахия не разочаровывает и в этом отношении. Вот список способов одержать победу в этой игре (в порядке возрастания их «славности»):
Здесь можно различить два принципиально различных вида целей игры. Common Victories связаны с захватом фигур противника (с возможным ограничением количества захватываемых фигур, с целью защиты от агрессивной игры). Proper Victories считаются более достойным завершением и связаны с воссозданием некой «гармонии» на территории противника (что не исключает возможности боя фигур противника).
Примеры выше иллюстрируют, что в «гармонию» могут (и должны) вовлекаться фигуры противника. В первом случае, построена арифметическая прогрессия (16, 36, 56). Второй пример сочетает геометрическую (4, 12, 36) и гармоническую (4, 6, 12) прогрессии. В третьем случае, присутствуют все три вида прогрессии (вы сами можете найти их). На случай, если имеются сложности с устным счётом, построены таблицы всех возможных в Ритмомахии решений (впрочем, людей, имеющих проблемы с устным счётом, Ритмомахия вряд ли заинтересует).
В период своего расцвета, Ритмомахия уже претерпела немало изменений. Последующие реконструкции не улучшили ситуацию. Имеется множество разночтений в описаниях правил этой игры. Некоторые источники дают альтернативные варианты первоначальной расстановки фигур (мне попадался даже вариант, описывающий игру на доске 8 x 14):
Имеются варианты с упрощенными правилами перемещения фигур. По этим правилам, фигуры движутся по прямой (ортогоналям и диагоналям) на заданное число клеток. Любая фигура, на пути движения, останавливает перемещение. Прыжки, наподобие хода Коня в Шахматах, отсутствуют. Пирамида, как обычно, сочетает ходы присутствующих в её наборе фигур.
Помимо этого, имеется вариант с обычными правилами движения фигур, в котором добавляется специальный ход Пирамиды на 3 клетки по диагонали. Такой ход возможен при условии, что не взята ни одна из фигур, первоначально входящих в состав Пирамиды. С сохранностью первоначального набора фигур Пирамиды связан и другой вариант. В нём разрешается использовать суммарное значение Пирамиды, только при условии, что ни одна из её фигур ещё не была «съедена». Есть и более простые варианты, в которых Пирамида убирается полностью, если атакован любой из её компонентов.
Часть вариантов связана с изменениями правил взятия фигур. Так, в одном из вариантов, для взятия фигуры "by Siege" (осада), необходимо блокировать все направления её «естественного» перемещения. При этом, не обязательно располагать свои фигуры вплотную к блокируемой (примеры ниже иллюстрируют концепцию). Это довольно интересное правило.
Есть вариант, в котором взятие "by Ambush" (засада) осуществляется подобно играм «зажимного» типа (при этом, правила перемещения фигур игнорируются):
Имеется большое количество расхождений в определениях "Glorious Victories". Часто, в условия таких побед, включается предварительное уничтожение Пирамиды противника. Также, существует условие завершения игры, ограничивающееся взятием Пирамиды. Вариантов этой игры много. Ознакомление с нюансами правил, перед началом игры, в любом случае, будет совсем не лишним.
Реализация игры естественным образом разделилась на несколько этапов. Проще всего было реализовать перемещение фигур. С этого я и начал. Вот как выглядит перемещение Квадратов:
Некоторая сложность возникла с Пирамидами, поскольку их набор ходов определяется тем, какие фигуры входят в них, в настоящий момент. Пришлось описывать для них все возможные ходы, а при выполнении хода, проверять наличие в наборе соответствующей фигуры:
Реализация боя фигур обернулась настоящей «гонкой на выживание». Требовалось реализовать четыре совершенно различных (и весьма нетривиальных) способа взятия. При этом, хотелось ограничить количество просмотров полей, чтобы минимизировать накладные расходы на вычисления (ход и так рассчитывается безобразно долго). В результате, я остановился на идее предварительного заполнения нескольких массивов, с выполнением последующих проверок условий боя фигур:
Взятие фигур в Пирамиде, как и перемещение, пришлось обрабатывать особым образом:
Уже в процессе отладки, я понял, что все проверки выполняются на момент до выполнения хода. Пришлось написать небольшую функцию, имитирующую перемещение фигуры (это не совсем полноценный перерасчёт позиции на доске, но мне удалось обойтись малой кровью):
На фоне всех этих ужасов, проверка условий завершения игры показалась тривиальной задачей. Не обошлось без небольшого количества магии Axiom, но здесь нет ничего такого, что я боялся бы показать родителям:
Начиная с этого момента, программа уже могла играть (правда делала это довольно пассивно). Дело в том, что, в отсутствии оценочной функции (и кастомной реализации AI), Axiom пытается выполнять полный перебор, до терминальной позиции. Понятно, что завершение партии находится далеко за горизонтом возможной глубины перебора, в результате чего, найденные ходы не отличаются особой осмысленностью. В общем, осталось добавить AI зубы:
Здесь использована очень удобная функция material-balance (предоставляемая Axiom), использующая весовые значения заданные фигурам (эти же значения использованы для реализаций правил Ритмомахии):
Этой реализации многого не хватает (например проверки завершения игры по Glorious Victories). Я постараюсь добавить недостающий функционал в будущем. Актуальную версию исходников всегда можно посмотреть здесь.
Ритмомахия заинтересовала меня, в первую очередь, своей сложностью. Разумеется, и мыслей не было реализовать её на ZRF. Мне пришлось освоить Axiom, для этого! В настоящий момент, имеется упрощенная реализация, не поддерживающая Glorious Victories. Также, нет твердой уверенности в том, что я нашёл все ошибки в коде (1000 строк на ForthScript — это серьёзно). Это бета-версия, но, в целом, она работает:
Можно заметить, что игра заканчивается очень быстро. Это действительно так. В случае, если оба игрока играют агрессивно, по условиям Common Victories (и без ограничения на количество взятых фигур), средняя продолжительность партии составляет ~10 ходов. При этом, первый игрок имеет серьёзное преимущество:
Забавно, что если агрессивен лишь один из игроков, партия затягивается до более чем 300 ходов (агрессивный игрок практически всегда выигрывает).
Человеку с компьютером играть сложно. Даже с подсветкой фигур, находящихся под боем, бывает непросто сообразить, какой именно фигурой следует сделать ход, чтобы выполнить взятие (при этом, желательно еще и не подставить свои фигуры). В наше время, эта игра вряд ли будет популярна, но одного у неё не отнять. Она здорово развивает навык устного счёта.
Фрэнсис Бэкон.
… во многой мудрости много печали;
и кто умножает познания, умножает скорбь.
Книга Экклезиаста.
Игры живут своей жизнью. Они возникают из ниоткуда, развиваются, порождают новые игры, забываются всеми и, порой, вновь возвращаются из забвения. В истории немало примеров игр, потерпевших поражение в этом процессе естественного отбора. Таковы разнообразные варианты Сёги, дошедшие до наших дней лишь благодаря трепетному отношению жителей Японии к своему культурному наследию. Партия в игру, подобную Taikyoku shogi, могла затянуться на месяцы (если не на годы). Но эти шахматные динозавры эпохи Хэйан не являются самыми яркими представителями «ископаемого» мира настольных игр.
Я хочу рассказать о поистине удивительной игре. Угрозы в ней не очевидны, а цели не тривиальны. Победить можно множеством способов, но играть совсем не легко. Её нельзя отнести ни к семейству Шашек ни к шахматному семейству. Происхождение её туманно. Для среднестатистического обывателя, эта игра примерно столь же увлекательна, сколь и составление магических квадратов. Она полностью оправдывает одно из своих названий — играть в неё могут только философы.
Впервые, Rithmomachia, также известная как «Битва чисел» или «Игра философов» была описана, приблизительно, в 1030 году монахом по имени Asilo. Авторство, по всей видимости безосновательно, приписывается Платону, а правила игры основаны на арифметической теории Боэция. Впоследствии, правила игры были незначительно изменены другим монахом, по имени Hermannus Contractus, добавившим примечания, посвященные теории музыки. Продолжительное время Ритмомахия использовалась в качестве учебного пособия, при обучении студентов математике. Интеллектуалы того времени играли в Ритмомахию для удовольствия (одно время она была даже более популярна чем Шахматы), Роберт Бёртон упоминал её в "Анатомии меланхолии", а Томас Мор считал эту игру хорошим досугом для обитателей своей "Утопии". Затем, внезапно, всё кончилось. Интересы математики и Ритмомахии разошлись и игра была забыта. Разумеется, это не означает, что мы не можем её вспомнить.
Правила игры
В Ритмомахию играют два игрока на прямоугольной доске 8x16 клеток. Ходы совершаются поочерёдно. За каждый ход перемещается одна фигура. В результате хода, может быть взята (снята с доски) одна или более фигур противника. Определены следующие типы фигур:
- Круг
- Треугольник
- Квадрат
- Пирамида
Не обращая внимания на числовые пометки на фигурах (о них я скажу ниже), можно заметить, что допускается два типа ходов. В первом случае, фигура движется по прямой и может быть остановлена любой другой фигурой (своей или противника), находящейся на пути. Таким образом перемещается Круг (на одну клетку по диагонали), а также Треугольник (строго две клетки по ортогонали) и Квадрат (строго три клетки по ортогонали). Другой возможностью является «прыжок» фигуры на целевую клетку, наподобие хода Коня в Шахматах. Так может ходить Треугольник или Квадрат. Любой ход должен выполняться только на пустую клетку.
Уникальной фигурой является Пирамида. Собственно это не фигура, а набор фигур. Каждая фигура в наборе (Круг, Треугольник или Квадрат) даёт возможность Пирамиде выполнять соответствующий тип хода. На рисунке выше, показаны возможные ходы Пирамиды в «максимальной комплектации». Как легко догадаться, к концу игры, «комплектность» может быть сильно нарушена (к слову сказать, Пирамида из Ритмомахии — это единственная известная мне фигура, которую можно «убивать по частям»).
Остановлюсь подробнее на способах «убийства». В Ритмомахии их четыре:
- Capture by Siege
- Capture by Equality
- Capture by Ambush
- Capture by Eruption
Наиболее радикальным является взятие фигуры «в осаду». Фигура будет снята, если после очередного хода она окажется блокирована по всем диагональным или ортогональным направлениям. Если фигура расположилась у края доски или в углу — блокировать придётся меньшее количество направлений. Это простейший (но не единственный) способ взять Пирамиду всю сразу — целиком. Взятие «в осаду» — единственный способ, не использующий числовые значения фигур.
Другим способом является взятие фигуры с совпадающим числовым значением. Если, после выполнения хода, на поле, куда следующим своим ходом могла бы переместиться фигура (если бы это поле было пустым, разумеется) расположена фигура противника, с тем же числовым значением, она будет взята. Следует отметить, что этот способ боя может быть несимметричным. Так (на рисунке выше), после хода белых, Круг, с числовым значением 16, может взять чёрный Треугольник с тем же значением, но Треугольник, на своём ходу, этого сделать не может, поскольку ходит на другие клетки. В то же время, белый и чёрный треугольники с числовыми значениями 25 бьют друг друга симметрично (то какая фигура будет снята — определяется очередностью хода).
Усовершенствованным вариантом предыдущего является следующий способ. В этот раз, «из засады», нападают две фигуры. Если сумма, разность, произведение или частное их числовых значений совпадёт с числовым значением на фигуре противника — фигура снимается. Это наиболее часто используемая возможность боя фигур в игре, но увидеть все такие угрозы, в более менее сложной позиции, может быть совсем не просто.
Последний способ позволяет бить фигуры на дальнем расстоянии. Если результат произведения или частного числового значения фигуры и расстояния до фигуры противника (по ортогонали) совпадает с числовым значением фигуры противника — фигура снимается. Другие фигуры, расположенные по направлению боя, не препятствуют угрозе. При расчёте расстояния, учитываются начальная и конечная позиции. Это симметричный способ боя (поскольку он не зависит от правил перемещения фигур). Очередность хода определяет, какая из фигур будет снята.
Осталось рассказать о том, как эти правила распространяются на Пирамиды. С этим всё просто — в любых подсчётах на взятие фигур, Пирамида может выступать либо как самостоятельная фигура (её числовое значение совпадает с суммой числовых значений всех её компонентов), либо как любая из её частей. Аналогично этому, Пирамида может быть взята как целиком (по её суммарному значению), так и по частям (уязвим каждый из её компонентов в отдельности). С учетом правил перемещения Пирамиды, о которых я говорил выше, это делает Пирамиду самой сильной (и самой уязвимой) фигурой.
Начальная расстановка фигур связана с еще одной важной особенностью игры. Хотя набор фигур одинаков, числовые значения различаются. Также, различна «комплектация» пирамид (показана сбоку от доски, для каждого из игроков). Это делает игру ассиметричной. Тактические приемы и стратегии, для чёрного игрока не годятся для белых (и наоборот). Это делает игру более интересной.
Славные победы
Описанных выше правил достаточно, чтобы начать играть в Ритмомахию, но если бы целью игры было простое взятие всех фигур противника, игра не была бы столь интересной. Да, победить можно и таким образом, но это не единственный (и не лучший) способ одержать победу! Мне очень нравятся игры, целью которых не является прямолинейное «убийство» фигур противника. Так в Шахматах, для победы, совсем не обязательно «есть» все фигуры, достаточно поставить мат Королю! В некоторых вариантах Hasami Shogi, цель игры еще более неожиданная (для победы необходимо построить линию из 5 своих фишек «в ряд»). Ритмомахия не разочаровывает и в этом отношении. Вот список способов одержать победу в этой игре (в порядке возрастания их «славности»):
- De Corpore («by body»): Взять заданное (или большее) количество фигур противника (обычно 15)
- De Bonis («by goods»): Взять фигуры противника с заданным (или большим) суммарным значением (обычно 1315 для белых и 984 для чёрных)
- De Lite («by lawsuit»): Взять фигуры противника с заданным (или большим) суммарным значением, при условии, что количество цифр, на захваченных фигурах, не превышает заданного
- De Honore («by honour»): Взять фигуры противника с заданным (или большим) суммарным значением, при условии, что количество захваченных фигур не превышает заданного
- De Honore Liteque («by honour and lawsuit»): Взять фигуры противника с заданным (или большим) суммарным значением, при условии, что количество захваченных фигур не превышает заданного и количество цифр, на захваченных фигурах, не превышает заданного
- Victoria Magna («great victory»): Расположить три фигуры (на территории противника) в арифметической прогрессии
- Victoria Major («greater victory»): Расположить четыре фигуры (на территории противника) так, чтобы в них имелись две (но не более) групп из трёх фигур, размещенных в различных видах прогрессии (арифметической, геометрической или гармонической)
- Victoria Excellentissima («most excellent victory»): Расположить (на территории противника) четыре фигуры так, чтобы имелось все три вида прогрессии
Здесь можно различить два принципиально различных вида целей игры. Common Victories связаны с захватом фигур противника (с возможным ограничением количества захватываемых фигур, с целью защиты от агрессивной игры). Proper Victories считаются более достойным завершением и связаны с воссозданием некой «гармонии» на территории противника (что не исключает возможности боя фигур противника).
Примеры выше иллюстрируют, что в «гармонию» могут (и должны) вовлекаться фигуры противника. В первом случае, построена арифметическая прогрессия (16, 36, 56). Второй пример сочетает геометрическую (4, 12, 36) и гармоническую (4, 6, 12) прогрессии. В третьем случае, присутствуют все три вида прогрессии (вы сами можете найти их). На случай, если имеются сложности с устным счётом, построены таблицы всех возможных в Ритмомахии решений (впрочем, людей, имеющих проблемы с устным счётом, Ритмомахия вряд ли заинтересует).
Возможны варианты
В период своего расцвета, Ритмомахия уже претерпела немало изменений. Последующие реконструкции не улучшили ситуацию. Имеется множество разночтений в описаниях правил этой игры. Некоторые источники дают альтернативные варианты первоначальной расстановки фигур (мне попадался даже вариант, описывающий игру на доске 8 x 14):
Имеются варианты с упрощенными правилами перемещения фигур. По этим правилам, фигуры движутся по прямой (ортогоналям и диагоналям) на заданное число клеток. Любая фигура, на пути движения, останавливает перемещение. Прыжки, наподобие хода Коня в Шахматах, отсутствуют. Пирамида, как обычно, сочетает ходы присутствующих в её наборе фигур.
Помимо этого, имеется вариант с обычными правилами движения фигур, в котором добавляется специальный ход Пирамиды на 3 клетки по диагонали. Такой ход возможен при условии, что не взята ни одна из фигур, первоначально входящих в состав Пирамиды. С сохранностью первоначального набора фигур Пирамиды связан и другой вариант. В нём разрешается использовать суммарное значение Пирамиды, только при условии, что ни одна из её фигур ещё не была «съедена». Есть и более простые варианты, в которых Пирамида убирается полностью, если атакован любой из её компонентов.
Часть вариантов связана с изменениями правил взятия фигур. Так, в одном из вариантов, для взятия фигуры "by Siege" (осада), необходимо блокировать все направления её «естественного» перемещения. При этом, не обязательно располагать свои фигуры вплотную к блокируемой (примеры ниже иллюстрируют концепцию). Это довольно интересное правило.
Есть вариант, в котором взятие "by Ambush" (засада) осуществляется подобно играм «зажимного» типа (при этом, правила перемещения фигур игнорируются):
Имеется большое количество расхождений в определениях "Glorious Victories". Часто, в условия таких побед, включается предварительное уничтожение Пирамиды противника. Также, существует условие завершения игры, ограничивающееся взятием Пирамиды. Вариантов этой игры много. Ознакомление с нюансами правил, перед началом игры, в любом случае, будет совсем не лишним.
Подробности для любознательных
Реализация игры естественным образом разделилась на несколько этапов. Проще всего было реализовать перемещение фигур. С этого я и начал. Вот как выглядит перемещение Квадратов:
Перемещение Квадратов
: leap-n ( 'leap-dir 'shift-dir count ? -- )
IF
BEGIN
OVER EXECUTE IF
on-board? IF
1- DUP 0> IF
FALSE
ELSE
2DROP TRUE TRUE
ENDIF
ELSE
2DROP FALSE TRUE
ENDIF
ELSE
2DROP FALSE TRUE
ENDIF
UNTIL
IF
EXECUTE IF
on-board? empty? AND IF
from
here DUP last-position !
move
capture-all
add-move
ENDIF
ENDIF
ELSE
DROP
ENDIF
ELSE
2DROP DROP
ENDIF
;
: shift-n ( 'shift-dir count ? -- )
IF
BEGIN
OVER EXECUTE IF
on-board? empty? AND IF
1- DUP 0> IF
FALSE
ELSE
2DROP TRUE TRUE
ENDIF
ELSE
2DROP FALSE TRUE
ENDIF
ELSE
2DROP FALSE TRUE
ENDIF
UNTIL
IF
from
here DUP last-position !
move
capture-all
add-move
ENDIF
ELSE
2DROP
ENDIF
;
: s-move-n ( -- ) ['] North 3 TRUE shift-n ;
: s-move-s ( -- ) ['] South 3 TRUE shift-n ;
: s-move-w ( -- ) ['] West 3 TRUE shift-n ;
: s-move-e ( -- ) ['] East 3 TRUE shift-n ;
: s-move-nw ( -- ) ['] Northwest ['] North 2 TRUE leap-n ;
: s-move-ne ( -- ) ['] Northeast ['] North 2 TRUE leap-n ;
: s-move-sw ( -- ) ['] Southwest ['] South 2 TRUE leap-n ;
: s-move-se ( -- ) ['] Southeast ['] South 2 TRUE leap-n ;
: s-move-wn ( -- ) ['] Northwest ['] West 2 TRUE leap-n ;
: s-move-ws ( -- ) ['] Southwest ['] West 2 TRUE leap-n ;
: s-move-en ( -- ) ['] Northeast ['] East 2 TRUE leap-n ;
: s-move-es ( -- ) ['] Southeast ['] East 2 TRUE leap-n ;
{moves s-moves
{move} s-move-n
{move} s-move-s
{move} s-move-w
{move} s-move-e
{move} s-move-nw
{move} s-move-ne
{move} s-move-sw
{move} s-move-se
{move} s-move-wn
{move} s-move-ws
{move} s-move-en
{move} s-move-es
moves}
Некоторая сложность возникла с Пирамидами, поскольку их набор ходов определяется тем, какие фигуры входят в них, в настоящий момент. Пришлось описывать для них все возможные ходы, а при выполнении хода, проверять наличие в наборе соответствующей фигуры:
Перемещение Пирамид
: is-correct-type? ( piece-type -- ? )
not-empty? IF
piece-type PYRAMID > IF
here SWAP a1 to
BEGIN
friend-p IF
DUP is-piece-type? IF
DROP TRUE TRUE
ELSE
FALSE
ENDIF
ELSE
DROP FALSE TRUE
ENDIF
UNTIL
SWAP to
ELSE
DROP FALSE
ENDIF
ELSE
DROP FALSE
ENDIF
;
: pr-move-ne ( -- ) ['] Northeast ROUND is-correct-type? leap-0 ;
: pr-move-se ( -- ) ['] Southeast ROUND is-correct-type? leap-0 ;
: pr-move-nw ( -- ) ['] Northwest ROUND is-correct-type? leap-0 ;
: pr-move-sw ( -- ) ['] Southwest ROUND is-correct-type? leap-0 ;
{moves p-moves
{move} pr-move-ne
{move} pr-move-se
{move} pr-move-nw
{move} pr-move-sw
...
moves}
Реализация боя фигур обернулась настоящей «гонкой на выживание». Требовалось реализовать четыре совершенно различных (и весьма нетривиальных) способа взятия. При этом, хотелось ограничить количество просмотров полей, чтобы минимизировать накладные расходы на вычисления (ход и так рассчитывается безобразно долго). В результате, я остановился на идее предварительного заполнения нескольких массивов, с выполнением последующих проверок условий боя фигур:
Способы боя
MAXV [] attacking-values[]
MAXS [] current-positions[]
MAXS [] current-values[]
MAXS [] eruption-values[]
: fill-current ( pos -- )
1 current-count !
DUP 0 current-positions[] !
DUP piece-type-at PYRAMID > IF
a1 to 0
BEGIN
enemy-p IF
not-empty? IF
piece piece-value
current-count @ MAXS < IF
here current-count @ current-positions[] !
DUP current-count @ current-values[] !
current-count ++
ENDIF
+
ENDIF
FALSE
ELSE
TRUE
ENDIF
UNTIL
ELSE
DUP piece-at piece-value
ENDIF
0 current-values[] !
to
;
: get-eruption-values ( n -- )
0 sum-value !
PYRAMID is-piece-type? IF
here a1 to
BEGIN
friend-p IF
not-empty? eruption-count @ MAXE < AND IF
OVER piece piece-value
DUP sum-value @ + sum-value !
*
eruption-count @ eruption-values[] !
eruption-count ++
ENDIF
FALSE
ELSE
TRUE
ENDIF
UNTIL
to
sum-value @
ELSE
piece piece-value
ENDIF
eruption-count @ MAXE < IF
*
eruption-count @ eruption-values[] !
eruption-count ++
ELSE
2DROP
ENDIF
;
: get-attacking-values ( piece-type -- )
0 sum-value !
FALSE sum-flag !
PYRAMID is-piece-type? IF
here a1 to
BEGIN
friend-p IF
not-empty? attacking-count @ MAXV < AND IF
piece piece-value
sum-value @ + sum-value !
OVER is-piece-type? IF
TRUE sum-flag !
piece piece-value
attacking-count @ attacking-values[] !
attacking-count ++
ELSE
ENDIF
ENDIF
FALSE
ELSE
TRUE
ENDIF
UNTIL
to DROP
sum-flag @ attacking-count @ MAXV < AND IF
sum-value @
attacking-count @ attacking-values[] !
attacking-count ++
ENDIF
ELSE
is-piece-type? attacking-count @ MAXV < AND IF
piece piece-value
attacking-count @ attacking-values[] !
attacking-count ++
ENDIF
ENDIF
;
: check-siege-od ( 'dir -- )
EXECUTE IF
predict-move
on-board? NOT friend? OR IF
siege-counter --
ENDIF
on-board? friend? AND IF
2 get-eruption-values
ENDIF
to
ELSE
siege-counter --
ENDIF
;
: check-siege-dd ( 'dir -- )
EXECUTE IF
predict-move
on-board? NOT friend? OR IF
siege-counter --
ENDIF
on-board? friend? AND IF
ROUND get-attacking-values
ROUND check-equality-piece
ENDIF
to
ELSE
siege-counter --
ENDIF
;
: check-siege ( pos -- )
4 siege-counter !
DUP to ['] North check-siege-od
DUP to ['] South check-siege-od
DUP to ['] West check-siege-od
DUP to ['] East check-siege-od
siege-counter @ 0= IF
TRUE is-captured? !
ENDIF
4 siege-counter !
DUP to ['] Northeast check-siege-dd
DUP to ['] Southeast check-siege-dd
DUP to ['] Northwest check-siege-dd
DUP to ['] Southwest check-siege-dd
siege-counter @ 0= IF
TRUE is-captured? !
ENDIF
to
;
: check-equality-dd ( 'second-dir count 'first-dir -- )
EXECUTE on-board? AND IF
BEGIN
1- DUP 0< IF
TRUE
ELSE
OVER EXECUTE on-board? AND IF
predict-move
friend? IF
OVER count-to-piece-type
DUP get-attacking-values
check-equality-piece
ENDIF
to
FALSE
ELSE
TRUE
ENDIF
ENDIF
UNTIL
2DROP
ELSE
2DROP
ENDIF
;
: check-equality-od ( 'second-dir count 'first-dir -- )
EXECUTE on-board? AND empty? AND IF
BEGIN
1- DUP 0< IF
TRUE
ELSE
OVER EXECUTE on-board? AND IF
predict-move
friend? IF
OVER count-to-factor get-eruption-values
OVER count-to-piece-type
DUP get-attacking-values
check-equality-piece
TRUE
ELSE
not-empty?
ENDIF
SWAP to
ELSE
TRUE
ENDIF
ENDIF
UNTIL
2DROP
ELSE
2DROP
ENDIF
;
: check-equality ( pos -- )
DUP to ['] North 2 ['] North check-equality-od
DUP to ['] North 2 ['] Northwest check-equality-dd
DUP to ['] North 2 ['] Northeast check-equality-dd
DUP to ['] South 2 ['] South check-equality-od
DUP to ['] South 2 ['] Southwest check-equality-dd
DUP to ['] South 2 ['] Southeast check-equality-dd
DUP to ['] West 2 ['] West check-equality-od
DUP to ['] West 2 ['] Northwest check-equality-dd
DUP to ['] West 2 ['] Southwest check-equality-dd
DUP to ['] East 2 ['] East check-equality-od
DUP to ['] East 2 ['] Northeast check-equality-dd
DUP to ['] East 2 ['] Southeast check-equality-dd
to
;
: check-ambush-prod ( value -- ? )
value-1 @ value-2 @ * OVER = IF
DROP TRUE
ELSE
DUP value-1 @ * value-2 @ = IF
DROP TRUE
ELSE
value-2 @ * value-1 @ = IF
TRUE
ELSE
FALSE
ENDIF
ENDIF
ENDIF
;
: check-ambush-cond ( value -- ? )
value-1 @ value-2 @ + OVER = IF
DROP TRUE
ELSE
DUP value-1 @ + value-2 @ = IF
DROP TRUE
ELSE
DUP value-2 @ + value-1 @ = IF
DROP TRUE
ELSE
check-ambush-prod
ENDIF
ENDIF
ENDIF
;
: check-ambush-pair ( -- )
current-count @
BEGIN
1-
DUP current-positions[] @ 0< NOT IF
DUP current-values[] @ check-ambush-cond IF
DUP 0> IF
DUP current-positions[] @
DUP enemy-at? IF
DUP ChangePieces
capture-at
ELSE
DROP
ENDIF
-1 OVER current-positions[] !
ELSE
TRUE is-captured? !
ENDIF
ENDIF
ENDIF
DUP 0> NOT
UNTIL
DROP
;
: check-ambush ( -- )
attacking-count @
BEGIN
1-
attacking-count @
BEGIN
1-
2DUP < IF
2DUP
attacking-values[] @ value-1 !
attacking-values[] @ value-2 !
check-ambush-pair
ENDIF
DUP 0> NOT
UNTIL
DROP
DUP 0> NOT
UNTIL
DROP
;
: fill-eruption-values ( 'dir pos n -- )
value-1 ! to 1
BEGIN
1+ OVER EXECUTE IF
predict-move
OVER value-1 @ > on-board? friend? AND AND IF
OVER get-eruption-values
ENDIF
to
FALSE
ELSE
TRUE
ENDIF
UNTIL
2DROP
;
: check-eruption-pair ( -- )
current-count @
BEGIN
1-
DUP current-positions[] @ 0< NOT IF
DUP current-values[] @ value-1 @ = IF
DUP 0> IF
DUP current-positions[] @
DUP enemy-at? IF
DUP ChangePieces
capture-at
ELSE
DROP
ENDIF
-1 OVER current-positions[] !
ELSE
TRUE is-captured? !
ENDIF
ENDIF
ENDIF
DUP 0> NOT
UNTIL
DROP
;
: check-eruption-values ( -- )
eruption-count @
BEGIN
1-
DUP eruption-values[] @ value-1 !
check-eruption-pair
DUP 0> NOT
UNTIL
DROP
;
: check-eruption ( pos -- )
['] North OVER 4 fill-eruption-values
['] South OVER 4 fill-eruption-values
['] West OVER 4 fill-eruption-values
['] East OVER 4 fill-eruption-values
to
check-eruption-values
;
: capture-all ( -- )
here ROWS COLS *
BEGIN
1-
DUP on-board-at? OVER enemy-at? AND IF
0 attacking-count !
0 eruption-count !
FALSE is-captured? !
DUP fill-current
DUP check-siege
is-captured? @ NOT IF
DUP check-equality
ENDIF
is-captured? @ NOT IF
check-ambush
ENDIF
is-captured? @ NOT IF
DUP check-eruption
ENDIF
is-captured? @ IF
capture-piece
ENDIF
ENDIF
DUP 0> NOT
UNTIL
DROP to
;
Взятие фигур в Пирамиде, как и перемещение, пришлось обрабатывать особым образом:
Взятие фигур
: capture-piece ( -- )
current-count @
BEGIN
1- DUP 0> IF
DUP current-positions[] @
DUP 0< NOT IF
DUP enemy-at? IF
DUP ChangePieces
capture-at
ELSE
DROP
ENDIF
ELSE
DROP
ENDIF
FALSE
ELSE
DUP current-positions[] @
DUP enemy-at? IF
DUP ChangePieces
capture-at
ELSE
DROP
ENDIF
TRUE
ENDIF
UNTIL
DROP
;
Уже в процессе отладки, я понял, что все проверки выполняются на момент до выполнения хода. Пришлось написать небольшую функцию, имитирующую перемещение фигуры (это не совсем полноценный перерасчёт позиции на доске, но мне удалось обойтись малой кровью):
Изменение позиции
: predict-move ( -- pos )
here
DUP from = IF
last-position @ to
ELSE
DUP last-position @ = IF
from to
ENDIF
ENDIF
;
На фоне всех этих ужасов, проверка условий завершения игры показалась тривиальной задачей. Не обошлось без небольшого количества магии Axiom, но здесь нет ничего такого, что я боялся бы показать родителям:
Проверка завершения
15 CONSTANT WINC
1315 CONSTANT WINW
984 CONSTANT WINB
: WhitePieces++ ( -- ) WhitePieces ++ ;
: BlackPieces++ ( -- ) BlackPieces ++ ;
: WhiteValues++ ( -- ) WhiteValues ++ ;
: BlackValues++ ( -- ) BlackValues ++ ;
: ChangePieces ( pos -- )
DUP piece-at piece-value SWAP
player-at White = IF
COMPILE WhitePieces++
BEGIN
1-
COMPILE WhiteValues++
DUP 0> NOT
UNTIL
DROP
ELSE
COMPILE BlackPieces++
BEGIN
1-
COMPILE BlackValues++
DUP 0> NOT
UNTIL
DROP
ENDIF
;
: OnIsGameOver ( -- gameResult )
#UnknownScore
current-player White = IF
WhitePieces @ WINC >= IF
DROP
#LossScore
ENDIF
WhiteValues @ WINW >= IF
DROP
#LossScore
ENDIF
ENDIF
current-player Black = IF
BlackPieces @ WINC >= IF
DROP
#LossScore
ENDIF
BlackValues @ WINB >= IF
DROP
#LossScore
ENDIF
ENDIF
;
Начиная с этого момента, программа уже могла играть (правда делала это довольно пассивно). Дело в том, что, в отсутствии оценочной функции (и кастомной реализации AI), Axiom пытается выполнять полный перебор, до терминальной позиции. Понятно, что завершение партии находится далеко за горизонтом возможной глубины перебора, в результате чего, найденные ходы не отличаются особой осмысленностью. В общем, осталось добавить AI зубы:
Оценочная функция
: OnEvaluate ( -- score )
current-player material-balance
;
Здесь использована очень удобная функция material-balance (предоставляемая Axiom), использующая весовые значения заданные фигурам (эти же значения использованы для реализаций правил Ритмомахии):
Описание фигур
{pieces
{piece} R0 {moves} r-moves 0 {value}
{piece} R1 {moves} r-moves 1 {value}
{piece} R2 {moves} r-moves 2 {value}
{piece} R3 {moves} r-moves 3 {value}
{piece} R4 {moves} r-moves 4 {value}
{piece} R5 {moves} r-moves 5 {value}
{piece} R6 {moves} r-moves 6 {value}
{piece} R7 {moves} r-moves 7 {value}
{piece} R8 {moves} r-moves 8 {value}
{piece} R9 {moves} r-moves 9 {value}
{piece} R16 {moves} r-moves 16 {value}
{piece} R25 {moves} r-moves 25 {value}
{piece} R36 {moves} r-moves 36 {value}
{piece} R49 {moves} r-moves 49 {value}
{piece} R64 {moves} r-moves 64 {value}
{piece} R81 {moves} r-moves 81 {value}
{piece} T0 {moves} t-moves 0 {value}
{piece} T6 {moves} t-moves 6 {value}
{piece} T9 {moves} t-moves 9 {value}
{piece} T12 {moves} t-moves 12 {value}
{piece} T16 {moves} t-moves 16 {value}
{piece} T20 {moves} t-moves 20 {value}
{piece} T25 {moves} t-moves 25 {value}
{piece} T30 {moves} t-moves 30 {value}
{piece} T36 {moves} t-moves 36 {value}
{piece} T42 {moves} t-moves 42 {value}
{piece} T49 {moves} t-moves 49 {value}
{piece} T56 {moves} t-moves 56 {value}
{piece} T64 {moves} t-moves 64 {value}
{piece} T72 {moves} t-moves 72 {value}
{piece} T81 {moves} t-moves 81 {value}
{piece} T90 {moves} t-moves 90 {value}
{piece} T100 {moves} t-moves 100 {value}
{piece} S0 {moves} s-moves 0 {value}
{piece} S15 {moves} s-moves 15 {value}
{piece} S25 {moves} s-moves 25 {value}
{piece} S28 {moves} s-moves 28 {value}
{piece} S36 {moves} s-moves 36 {value}
{piece} S45 {moves} s-moves 45 {value}
{piece} S49 {moves} s-moves 49 {value}
{piece} S64 {moves} s-moves 64 {value}
{piece} S66 {moves} s-moves 66 {value}
{piece} S81 {moves} s-moves 81 {value}
{piece} S120 {moves} s-moves 120 {value}
{piece} S121 {moves} s-moves 121 {value}
{piece} S153 {moves} s-moves 153 {value}
{piece} S169 {moves} s-moves 169 {value}
{piece} S225 {moves} s-moves 225 {value}
{piece} S289 {moves} s-moves 289 {value}
{piece} S361 {moves} s-moves 361 {value}
{piece} P0 {moves} p-moves 0 {value}
{piece} P91 {moves} p-moves 91 {value}
{piece} P190 {moves} p-moves 190 {value}
pieces}
Этой реализации многого не хватает (например проверки завершения игры по Glorious Victories). Я постараюсь добавить недостающий функционал в будущем. Актуальную версию исходников всегда можно посмотреть здесь.
Что в итоге?
Ритмомахия заинтересовала меня, в первую очередь, своей сложностью. Разумеется, и мыслей не было реализовать её на ZRF. Мне пришлось освоить Axiom, для этого! В настоящий момент, имеется упрощенная реализация, не поддерживающая Glorious Victories. Также, нет твердой уверенности в том, что я нашёл все ошибки в коде (1000 строк на ForthScript — это серьёзно). Это бета-версия, но, в целом, она работает:
Можно заметить, что игра заканчивается очень быстро. Это действительно так. В случае, если оба игрока играют агрессивно, по условиям Common Victories (и без ограничения на количество взятых фигур), средняя продолжительность партии составляет ~10 ходов. При этом, первый игрок имеет серьёзное преимущество:
Cumulative results following game 13 of 100:
Player 1 "Eval", wins = 13.
Player 2 "Eval", wins = 0.
Draws = 0
Забавно, что если агрессивен лишь один из игроков, партия затягивается до более чем 300 ходов (агрессивный игрок практически всегда выигрывает).
Cumulative results following game 22 of 100:
Player 1 "Rithmomachy", wins = 1.
Player 2 "Eval", wins = 21.
Draws = 0
Человеку с компьютером играть сложно. Даже с подсветкой фигур, находящихся под боем, бывает непросто сообразить, какой именно фигурой следует сделать ход, чтобы выполнить взятие (при этом, желательно еще и не подставить свои фигуры). В наше время, эта игра вряд ли будет популярна, но одного у неё не отнять. Она здорово развивает навык устного счёта.