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

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

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

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

constant indices
    white_pawn := 1
    white_rook := 2
    # etc.
    black_king := 12

function init_zobrist():
    # fill a table of random numbers/bitstrings
    table := a 2-d array of size 64×12
    for i from 1 to 64:  # loop over the board, represented as a linear array
        for j from 1 to 12:      # loop over the pieces
            table[i][j] := random_bitstring()
    table.black_to_move = random_bitstring()

function hash(board):
    h := 0
    if is_black_turn(board):
        h := h XOR table.black_to_move
    for i from 1 to 64:      # loop over the board positions
        if board[i] ≠ empty:
            j := the piece at board[i], as listed in the constant indices, above
            h := h XOR table[i][j]
    return h

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

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

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

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

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

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

'pawn at this square'      (XORing out the pawn at this square)
'rook at this square'      (XORing in the rook at this square)
'rook at source square'    (XORing out the rook at the source square)

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

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

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

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

См. также

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

Ссылки

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

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

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

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

[1]

[2]

[3]