Хеширование Zobrist (также называемое ключами Zobrist или подписями Zobrist [1] ) - это конструкция хеш-функции, используемая в компьютерных программах, которые играют в абстрактные настольные игры , такие как шахматы и го , для реализации таблиц транспонирования , особого вида хеш-таблицы, которая является индексируется позицией доски и используется, чтобы не анализировать одну и ту же позицию более одного раза. Хеширование Zobrist названо в честь его изобретателя, Альберта Линдси Зобриста . [2] Он также применялся как метод распознавания конфигураций сплавов замещения при моделировании кристаллических материалов. [3]
Расчет хеш-значения [ править ]
Хеширование Zobrist начинается со случайной генерации цепочек битов для каждого возможного элемента настольной игры, то есть для каждой комбинации фигуры и позиции (в шахматной игре это 12 фигур на 64 позиции на доске или 16 x 64, если король может Тем не менее, замок и пешка, которая может взять на проходе , рассматриваются отдельно для обоих цветов). Теперь любая конфигурация платы может быть разбита на независимые части / компоненты позиции, которые отображаются на случайные последовательности битов, сгенерированные ранее. Окончательный хэш Zobrist вычисляется путем объединения этих битовых строк с помощью побитового XOR . Пример псевдокода для игры в шахматы: [ ссылка ]
постоянные показатели white_pawn: = 1 white_rook: = 2 # так далее. black_king: = 12функция init_zobrist (): # заполняем таблицу случайных чисел / битовых строк table: = 2-мерный массив размером 64 × 12 for i от 1 до 64: # цикл по доске, представленный как линейный массив для j от 1 до 12: # цикл по кусочкам таблица [i] [j]: = random_bitstring ()функция хеш (доска): ч: = 0 for i от 1 до 64: # перебрать позиции доски, если доска [i] ≠ пуста: j: = фигура на доске [i], как указано в индексах констант выше h: = h Таблица XOR [i] [j] вернуться ч
Использование хеш-значения [ править ]
Если строки битов достаточно длинные, разные позиции на плате почти наверняка будут иметь разные значения; однако более длинные битовые строки требуют для манипулирования пропорционально больше компьютерных ресурсов. Наиболее часто используемая длина строки (ключа) составляет 64 бита. Многие игровые движки хранят только хеш-значения в таблице транспонирования, полностью опуская информацию о положении, чтобы уменьшить использование памяти, и предполагая, что хеш-коллизии не произойдут или не сильно повлияют на результаты таблицы, если они будут.
Хеширование Zobrist - это первый известный пример хеширования табуляции . В результате получается трехуровневая независимая семья хешей . В частности, он сильно универсален .
Например, в шахматах каждое из 64 квадратов может в любой момент быть пустым или содержать одну из 6 игровых фигур, которые являются черными или белыми. То есть каждый квадрат может находиться в одном из 1 + 6 x 2 = 13 возможных состояний в любое время. Таким образом, необходимо сгенерировать не более 13 x 64 = 832 случайных битовых строки. Для данной позиции можно получить ее хэш Зобриста, выясняя, какие части на каких квадратах, и комбинируя соответствующие битовые строки вместе.
Обновление хеш-значения [ править ]
Вместо того, чтобы вычислять хэш для всей платы каждый раз, как это делает приведенный выше псевдокод, значение хеш-функции платы можно обновить просто путем XOR для строки (ов) битов для позиций, которые изменились, и XORing в цепочках битов для новых позиции. Например, если пешка на поле шахматной доски заменяется ладьей из другого поля, результирующая позиция будет получена путем XOR-операции существующего хэша со строками битов для:
'пешка на этом поле ' (исключающая пешку на этом поле)«ладья на этой площади» (XORing в ладье на этой площади)'ладья в исходном поле ' (исключающее или исключающее ладью в исходном поле)«ничего в источнике квадрата» (XORing в ничто в исходном квадрате).
Это делает хеширование Zobrist очень эффективным для обхода дерева игры .
В компьютерном Go этот метод также используется для обнаружения суперко .
Более широкое использование [ править ]
Тот же метод использовался для распознавания конфигураций сплавов замещения во время моделирования методом Монте-Карло , чтобы избежать ненужных затрат вычислительных усилий на состояния, которые уже были рассчитаны. [3]
См. Также [ править ]
Ссылки [ править ]
- ^ Ключи Zobrist: средство включения сравнения позиций.
- ^ Альберт Линдси Зобрист, Новый метод хеширования с приложением для игры , Tech. Представитель 88, факультет компьютерных наук, Университет Висконсина, Мэдисон, Висконсин, (1969).
- ^ a b Мейсон, доктор философии; Хадсон, ТС; Саттон, AP (2005). «Быстрое воспроизведение истории состояний в кинетическом моделировании Монте-Карло с использованием ключа Зобриста». Компьютерная физика . 165 : 37. Bibcode : 2005CoPhC.165 ... 37M . DOI : 10.1016 / j.cpc.2004.09.007 .
