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

Zobrist hashing

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

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

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

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

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

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

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

Например, в шахматы, каждое из 64 квадратов может в любой момент быть пустым или содержать одну из 6 игровых фишек, которые являются черными или белыми. То есть каждый квадрат может находиться в одном из 1 + 6 x 2 = 13 возможных состояний в любое время. Таким образом, необходимо сгенерировать не более 13 x 64 = 832 случайных битовых строки. Для данной позиции можно получить ее хэш Зобриста, выясняя, какие части на каких квадратах, и комбинируя соответствующие битовые строки вместе.

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

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

'пешка на этом квадрате' (XORing из пешка на этом поле) 'ладья на этом поле' (XORing в ладья на этом поле) 'ладья на исходном поле' (XORing из ладья в исходном квадрате) 'ничего в исходном поле' (XORing в ничего на исходной площади).

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

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

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

Тот же метод был использован для распознавания замещающий сплав конфигурации во время Моделирование Монте-Карло чтобы избежать ненужных затрат вычислительных ресурсов на уже вычисленные состояния.[3]

Смотрите также

Рекомендации

  1. ^ Ключи Zobrist: средство для сравнения позиций.
  2. ^ Альберт Линдси Зобрист, Новый метод хеширования с приложением для игры, Тех. Представитель 88, факультет компьютерных наук, Университет Висконсина, Мэдисон, Висконсин, (1969).
  3. ^ а б Mason, D. R .; Hudson, T. S .; Саттон, А. П. (2005). «Быстрое воспроизведение истории состояний в кинетическом моделировании Монте-Карло с использованием ключа Зобриста». Компьютерная физика Коммуникации. 165: 37. Bibcode:2005CoPhC.165 ... 37M. Дои:10.1016 / j.cpc.2004.09.007.