Функция Connect Four Hash: сопоставить элементы закрытия с ключами закрытия хэша

Question

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

Можно ли создать хеш-функцию, которая отображает положения закрытой доски для закрытия хеш-ключей?

Позиция доски для одного игрока представлена ​​битбордом следующей структуры:

.  .  .  .  .  .  .  TOP
5 12 19 26 33 40 47
4 11 18 25 32 39 46
3 10 17 24 31 38 45
2  9 16 23 30 37 44
1  8 15 22 29 36 43
0  7 14 21 28 35 42

Я не знаю, возможно ли это вообще. Спасибо за вашу помощь!

Answer 1

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

Пусть hash (gamestate) будет вашей существующей функцией. Мы создадим newhash (gamestate), который использует хэш для случайного поведения, но имеет достаточно высокую вероятность создания хэшей, которые находятся рядом друг с другом для тесно связанных состояний игры.

Пусть «цвет» состояния доски будет следующим игроком, который двинется. Если вы хотите найти ключ хеша для белого игрока, используйте newhash (board) = hash (board). Если вы хотите найти хеш для черной позиции, найдите черный фрагмент с максимальным числом в соответствии с вашим порядком, скажем, в позиции i. Удалите часть i из игрового состояния и вызовите измененное состояние probableparent. Затем используйте newhash (board) = hash (probableparent) + i. Если вы упорядочиваете позиции в соответствии с вероятным порядком размещения (более высокие позиции появляются позже в качестве критерия первого порядка, может быть, средние позиции появляются раньше в качестве второго критерия? Я не знаю хорошей стратегии для connect4), тогда вполне вероятно, что на белый ход до черного хода был вероятным родителем, и, следовательно, в вашем кэше, и, следовательно, я рядом. Кроме того, 8 возможных ходов черных, скорее всего, будут иметь одинаковое состояние prev_board и, следовательно, будут располагаться рядом с хеш-позициями.

Вы можете расширить эту идею для отката более чем одного слоя за раз. Скажем, если текущий ход% 3 == 2, удаляя максимум два хода в позициях доски i и j, а затем используйте newhash (board) = hash (board-two-removeals-ago) + i * 48 + j.

Answer 2

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

Примите во внимание следующее: даже если вы сопоставите позиции доски один на один с таблицей с (2 ^ 7-1) ^ 7 позициями, вы не сможете отобразить «близкие» позиции доски для закрытия областей памяти: если кусочек с низким индексом изменяется, позиции будут ближе, но чем выше индекс фигуры, тем больше различие в позициях удваивается, а у старших будет много терабайт друг от друга; -)

Как автор шахматного движка я знаю эту проблему. AFAIK никто еще не решил эту проблему, и все используют хеширование zobrist, возможно, с некоторыми незначительными изменениями.

В любом случае, удачи в решении Connect-4 ... Я знаю, что это было сделано раньше, но более удовлетворительно это сделать самостоятельно; -)