Главная » Игры, Теория » Более сложные приемы ZObrist-ключи

0

 

Для написания шахматной программы нужно уметь сравнить две позиции, одинаковы ли они? Такая задача возникает довольно часто, и ее выполнять нужно с максимальной скоростью. Например, при построении хеш-таблицы нужно иметь ключ, однозначно идентифицирующий позицию. При поиске конкретной позиции сначала находится начало подсписка, соответствующе­го данному ключу. Хотя ключ и не совсем точен, поиск значительно сокра­щается.

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

Таким образом, определение ключа позиции является принципиальным моментом при построении хорошей шахматной программы. Какие требова­ния предъявляются к хеш-ключу? Он должен вычисляться максимально бы­стро и как можно точнее характеризовать данную позицию, т. е. должно быть как можно меньше коллизий ключа (хеш-индекса). Хеш-ключ может быть "связан" с позицией, и тогда будет много повторов. Например, если при определении хеш-ключа используется номер клетки доски и величина фигуры в этой клетке, то коллизии неизбежны, и их будет очень много. На­пример, key = NSquare х ValuePiece, где NSquare — номер клетки, valuePiece — фигура в клетке.

Для определения не связанного с позицией ключа используется техника ZObrist-ключей. Суть ее в том, что имеется массив вычисленных заранее чисел, не связанных с данной позицией. Массив может быть трехмерным:

zobrist [pieceType] [colType] [square], Где pieceType — КОД фигуры В данной клетке, colType — цвет фигуры, square — номер клетки. Размеры массива будут, очевидно, 6 * 2 * 64.

Для хранения значений ключей используется тип данных unsigned_int64. Это 64-битовое без знака. Раньше использовался unsigned long (32-битовое без знака), но сейчас в этом нет необходимости. Данное число не отражает позицию на доске однозначно, т. к. для точного отражения нужно 4 х 64 = 256-битовое число. Но, тем не менее, коллизии достаточно редки. Таблица заполняется случайными числами. Для инициализации можно использовать стандартный генератор случайных чисел:

typedef unsigned     int64 U64

U64 rand64(void) {

return rand() Л ((U64)rand() « 15) Л ((U64)rand() « 31) Л ((U64)rand() « 47) Л ((U64)rand() « 59);

}

Используется операция XOR (исключающее ИЛИ), которая в каждом бите возвращает 1, только если биты различны. XOR двух одинаковых чисел вер­нет нули во всех разрядах. Вместо XOR можно использовать обычное сло­жение, но считается, что XOR дает лучшее распределение хеш-индекса. Так ли это? Я использовал XOR.

Теперь, когда у нас есть таблица с вычисленными значениями для всех воз­можных случаев на доске, вычислить хеш-индекс совсем просто. Например, для белого коня на е5

key = zobrist[KNIGHT][WHITE][E5]

Если нужно иметь полный ключ, нужно сканировать всю позицию, и каж­дый раз выполнять XOR с новым значением. Особенностью операции XOR является то, что когда мы делаем два раза XOR с каким-то числом, то полу­чаем исходное число. Это дает возможность нам убрать фигуру из ключа, просто применив к ключу операцию XOR с ней. Если эта фигура была в ключе, значит, мы ее вычли, если не было, то добавили. Это дает нам воз­можность просто по шагам вычислять хеш-ключ.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии