Зобристское хеширование

Хеширование Зобриста (также называемое ключами Зобриста или подписями Зобриста) . ^[1]) — конструкция хэш-функции, используемая в компьютерных программах , играющих в абстрактные настольные игры , такие как шахматы и го , для реализации таблиц транспозиции — особого вида хеш-таблицы , которая индексируется по положению на доске и используется, чтобы избежать анализа одной и той же позиции более чем один раз. Зобристское хеширование названо в честь его изобретателя Альберта Линдси Зобриста . ^[2] Он также применялся как метод распознавания конфигураций сплавов замещения при моделировании кристаллических материалов. ^[3] Зобристское хеширование — это первый известный пример общеполезного базового метода, называемого табуляционным хешированием .

Расчет хэш-значения

Хеширование Зобриста начинается со случайной генерации битовых строк для каждого возможного элемента настольной игры, то есть для каждой комбинации фигуры и позиции (в игре в шахматы это 12 фигур × 64 позиции на доске или 18 × 64, если короли и ладьи может еще замок, ^{[ сомнительно – обсудить ]} и пешки, которые могут взять на проходе , рассматриваются отдельно для обоих цветов). Теперь любую конфигурацию доски можно разбить на независимые компоненты фигур/позиций, которые отображаются в сгенерированные ранее случайные строки битов. Окончательный хеш Zobrist вычисляется путем объединения этих битовых строк с помощью побитового XOR . Пример псевдокода для игры в шахматы: ^{[ нужна ссылка ]}

постоянные индексы    белая_пешка := 1    белая_ладья := 2    # и т. д.    черный_король := 12 функция  init_zobrist():    # заполняем таблицу случайных чисел/битовых строк    таблица:= двумерный массив размером 64×12     для  i от 1 до 64: # цикл по доске, представленной в виде линейного массива         для  j от 1 до 12: # цикл по фрагментам            таблица[i][j] := случайная_битовая строка()    table.black_to_move = случайная_битовая строка() хеш функции  (доска):    ч := 0    если is_black_turn(доска):        h := h XOR table.black_to_move     for  i от 1 до 64: # цикл по позициям доски         если  доска[i] ≠ пуста:            j := фигура на доске[i], как указано в индексах констант выше.            h := h Таблица XOR[i][j]     вернуть  ч

Использование хеш-значения

Если битовые строки достаточно длинные, разные позиции на плате почти наверняка будут хэшироваться с разными значениями; однако для манипулирования более длинными битовыми строками требуется пропорционально больше компьютерных ресурсов. Наиболее часто используемая длина битовой строки (ключа) составляет 64 бита. ^[1] Многие игровые движки хранят в таблице транспонирования только хеш-значения, полностью опуская саму информацию о позиции, чтобы уменьшить использование памяти, и предполагая, что хеш-коллизии не произойдут или не окажут сильного влияния на результаты таблицы, если они произойдут.

Зобристское хеширование является первым известным примером табулированного хеширования . В результате получается трехкратное независимое семейство хэшей . В частности, он сильно универсален .

Например, в шахматах в любой момент каждая из 64 клеток может быть пустой или содержать одну из 6 игровых фигур, черных или белых. Кроме того, это может быть как очередь черных, так и очередь белых. Таким образом, необходимо сгенерировать 6 x 2 x 64 + 1 = 769 случайных битовых строк. Учитывая позицию, можно получить хэш Зобриста, выяснив, какие фигуры находятся на каких клетках, и объединив соответствующие строки битов вместе.Если позиция является черной для перемещения, битовая строка «черная для перемещения» также включается в хеш Zobrist. ^[1]

Обновление хэш-значения

Вместо того, чтобы каждый раз вычислять хэш для всей платы, как это происходит в приведенном выше псевдокоде, значение хеш-функции платы можно постепенно обновлять, просто выполняя XOR из битовой строки(й) для позиций, которые изменились, и XOR в битовых строках для новые должности. ^[1] Например, если пешка на шахматной доске заменяется ладьей из другого поля, результирующая позиция будет получена путем XOR существующего хэша с битовыми строками для:

'пешка на этом поле' (исключающее ИЛИ  пешки  на этом поле)'ладья на этом поле' (исключающее ИЛИ  для  ладьи на этом поле)'ладья на исходном поле' (исключающее  ИЛИ  ладью на исходном поле)

Это делает хеширование Zobrist очень эффективным для обхода дерева игры .

В компьютерном Go этот метод также используется для суперко обнаружения .

Более широкое использование

В более общем смысле хеширование Зобриста можно применять к конечным наборам элементов (в примере с шахматами эти элементы $(piece,position)$ кортежи ), при условии, что каждому возможному элементу может быть назначена случайная битовая строка. Это можно сделать либо с помощью генератора случайных чисел для меньших пространств элементов, либо с помощью хэш-функции для больших. Этот метод использовался для распознавания сплавов замещения конфигураций во время моделирования Монте-Карло , чтобы предотвратить трату вычислительных усилий на уже рассчитанные состояния. ^[3]

См. также

Альфа-бета-обрезка

Ссылки

^ Jump up to: Перейти обратно: ^а ^б ^с ^д Брюс Морленд. Ключи Зобриста: средство сравнения позиций.
^ Альберт Линдси Зобрист, Новый метод хеширования с применением для игр , Tech. Представитель 88, факультет компьютерных наук, Университет Висконсина, Мэдисон, Висконсин (1969).
^ Jump up to: Перейти обратно: ^а ^б Мейсон, доктор медицинских наук; Хадсон, Т.С.; Саттон, AP (2005). «Быстрый вызов истории состояний в кинетическом моделировании Монте-Карло с использованием ключа Зобриста». Компьютерная физика. Коммуникации . 165 (1): 37–48. Бибкод : 2005CoPhC.165...37M . дои : 10.1016/j.cpc.2004.09.007 .

[moreland-1] Jump up to: Перейти обратно: ^а ^б ^с ^д Брюс Морленд. Ключи Зобриста: средство сравнения позиций.

[2] Альберт Линдси Зобрист, Новый метод хеширования с применением для игр , Tech. Представитель 88, факультет компьютерных наук, Университет Висконсина, Мэдисон, Висконсин (1969).

[MonteCarlo-3] Jump up to: Перейти обратно: ^а ^б Мейсон, доктор медицинских наук; Хадсон, Т.С.; Саттон, AP (2005). «Быстрый вызов истории состояний в кинетическом моделировании Монте-Карло с использованием ключа Зобриста». Компьютерная физика. Коммуникации . 165 (1): 37–48. Бибкод : 2005CoPhC.165...37M . дои : 10.1016/j.cpc.2004.09.007 .

[1]

[2]

[3]