… И повторится все, как встарь:
Ночь, ледяная рябь канала,
Аптека, улица, фонарь. 

                 Александр Блок 
 

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

При игре человека с компьютером, это не проблема (понятно кто устанет первым), но что делать если играют два бота? Для сравнения «силы» различных вариантов AI, например, требуется провести в автоматическом режиме большое количество игр. Корректная обработка «ничьих», в такой ситуации, жизненно необходима. И крайне желательно, чтобы она выполнялась в точном соответствии с правилами игры.

2. Повторение пройденного

Наиболее прямолинейный подход, используется в играх семейства «Шашек». Партия прерывается, если ни одному из игроков не удаётся выиграть в течение заданного количества ходов. Так, в хорошо нам знакомых "Русских шашках", партия считается сыгранной вничью, если не удаётся выиграть за 30 ходов. Более сложные правила, связанные со спецификой «тихоходных дамок», используются в "Английских шашках". Если у каждого из противников остаётся по одной дамке, разрешается делать не более 20 ходов, до признания ничьей. Если у одного противника три дамки, а у другого две, последний имеет право требовать, чтобы игра была сыграна не более чем за 40 ходов. Правила "Международных шашек" ещё более подробно описывают все возможные ситуации:

• Если игроки в течение 25 ходов делали ходы только дамками, не передвигая простых шашек и не производя взятия, объявляется ничья.
• Если у игрока в окончании партии остались 3 дамки, 3 дамки и 1 простая, 1 дамка и 2 простые, 3 простые шашки, 2 дамки, 1 дамка и 1 простая против одинокой дамки или 1 дамка против одинокой дамки или одинокой простой, игрок обязан 5-м ходом выиграть, иначе объявляется ничья.
• Если на доске остаются 5 дамок (или 4 дамки и 1 простая шашка) против 2 дамок, сильнейшая сторона обязана победить в 50 ходов, иначе объявляется ничья.
• Если три (или более) раза повторяется одна и та же позиция (т.е. одно и то же расположение шашек), причём, очередь хода каждый раз за одной и той же стороной – также объявляется ничья.

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



Если бы повторение позиции было разрешено, игроки могли бы продолжать эту последовательность ходов до бесконечности (забирая у противника всё новые и новые камни). С этим можно бороться, запретив белым играть С17, после хода чёрных на D17, но повторение позиции может быть и более сложным. В игре возможны ситуации «тройного Ко» и даже ещё более сложные позиции «Вечной жизни»:



Правила Инга пытаются регламентировать этот вопрос, но результат сложно считать удовлетворительным. Для того, чтобы отличить «боевое» Ко от «беспокоящего» требуется высокая квалификация. Начинающий игрок вряд ли справится с этим. В упрощённом варианте правил, позицию просто запрещено повторять. Этот подход называется "суперко" и может определять повторение позиции двумя различными способами:

• Позиционное суперко — безусловный запрет на повторение позиции, без учета очерёдности хода
• Ситуационное суперко — запрет повторения позиции, при условии очереди хода того-же игрока

В общем, понятно, что умение сравнивать различные позиции может оказаться полезным, при реализации некоторых настольных игр (и жизненно необходимым для AI), но, с учётом того, что сравнивать придётся очень много, простое поэлементное сравнение позиций может оказаться слишком накладным. Чтобы решить эту проблему, известный разработчик компьютерных игр Albert Lindsey Zobrist разработал простой и элегантный метод, названный в его честь.

Zobrist hashing применим для большинства настольных игр и суть его проста. Первым делом, составляется таблица случайных чисел (чем случайнее — тем лучше), для каждой возможной позиции каждой фигуры. В случае Шахмат, для каждого из 64 полей доски потребуется 12 случайных значений (по одному на каждый тип фигур, с учётом цвета). Далее, составляется хэш, путём "сложения по модулю 2" чисел, взятых из таблицы, для соответствующего расположения фигур на доске. Разумеется, если хэш-значения для двух позиций совпадут, это ещё не означает, что позиции одинаковы. Вероятность коллизий остаётся всегда, но использование этого метода позволяет минимизировать количество поэлементных сравнений позиций.

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

Разумеется, в ZoG она используется тоже (в Axiom-то уж точно), но лишь для внутренних нужд. Условие останова игры при троекратном повторении позиции «прибито гвоздями» в exe-нике! Axiom позволяет переопределить поведение (завершить игру поражением вместо ничьей) или детектировать первое повторение позиции вместо третьего, но работая в качестве engine для ZoG, отменить эту проверку вовсе он тоже не может. Лично мне, такое неизменяемое «поведение по умолчанию» попортило немало нервов.


Отсутствие какой либо возможности настройки проверки повторения позиции в ZoG я считаю одной из наиболее серьёзных ошибок дизайна этой программы. Наряду с «checkmated» и «maximal captures», эта опция достойна того, чтобы в честь неё отлили памятник из бронзы, на тему «как никогда не надо делать». При помощи ZRF можно лишь переопределить поведение, при обнаружении троекратного повторения позиции, но не более того. По умолчанию, действует следующее определение:

(draw-condition (White Black) repetition)

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

(not-situation-repeated? 1 1)

Это знакомое нам Ко. Первый аргумент определяет, какое по счёту повторение позиции необходимо детектировать, а второй — глубину поиска. И это должно быть универсальное выражение, которое можно использовать не только в условии завершения игры (как в ZRF), но и в любом инварианте, используемом генератором ходов (поскольку в Го повторение позиции должно запрещать ход, а не прерывать игру). Разумеется, также должна иметься возможность использования предиката *-position-repeated?, для определения позиционного Ко, наряду с ситуационным.

Возможно, ради всего сказанного выше, не стоило бы затевать эту статью, но у Zobrist hashing нашлось ещё одно неожиданное применение. Есть одна, поистине легендарная, игра, которая связывает собой "Шашки" и "Крестики-нолики". Также как в африканской "Bolotoudou", в ней требуется строить линии «3 в ряд» из своих камней, чтобы снимать камни противника, но, в отличии от последней, для этой игры существуют варианты, запрещающие выполнять взятие построением одного и того же ряда два раза подряд.



Легко заметить, что в реализации на видео, такая проверка не выполняется и это не случайно! Мне трудно придумать требование, реализовать которое на ZRF было бы сложнее. Эта проверка должна контролировать повторение позиции, но не всей, а лишь её части. Если три камня составили линию («мельницу»), повторное их расположение на тех же местах, через один ход, должно быть либо запрещено, либо не должно приводить к взятию. Но ведь и хэш можно строить лишь частичный!


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


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


Как можно видеть, древние разработчики настольных игр хорошо потрудились над тем, чтобы мы не заскучали над их реализацией. Вот пожалуй и всё, что я хотел рассказать о применении Zobrist hashing в проекте «Dagaz». Надеюсь, что мой рассказ был вам интересен.