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

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

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

 myHash = 0;
 //randoms[81][3] is an array filled completely with pseudorandom values
 for (int x = 0; x < 81; x++) {
      myHash ^= randoms[x][board[x]]; 
      //board[x] is the piece at space x (1=player1 piece, 2=player2 piece, 0=empty)
 }

Что еще более важно, я делаю это постепенно в функции applyMove (и функции undoMove):

applyMove(int to, int from) {

   //Undo the 'from' piece in the hash
   myHash ^= randoms[from][board[from]];
   // Apply the move
   std::swap(board[from], board[to]);
   //Add the 'to' piece to the hash
   myHash ^= randoms[to][board[to]];

   // Update whose turn it is
   swapTurn();
 }

Это работает из-за свойства обратимости функции XOR.

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

По сути, мой вопрос таков: как я могу хранить ход игрока в постепенно генерируемой хэш-функции, сохраняя при этом возможность полностью изменить ее (и желательно недорого)? Предполагая, что ход игрока представляет собой целое число, а не логическое значение, поскольку в игре будет 6 игроков, а не два.

Источник

2 ответа

Решение

Вы можете использовать turns[6] массив, заполненный псевдослучайными значениями:

unsigned n = 6;  // number of players;

myHash ^= turns[active_player];           // 'undo' the old active player
active_player = (active_player + 1) % n;  // new active player's index
myHash ^= turns[active_player];           // 'add' new active player

это похоже на пошаговое обновление позиции куска и работает для n ∈ [2, 6].

Как примечание стороны...

обычно хеширование Зобриста осуществляется путем сканирования местоположения фигур, исключая пустые квадраты. Расположение пустых квадратов явно не хэшируется.

Таким образом, вы можете использовать меньший (более удобный для кэша) массив. Что-то вроде:

std::uint64_t randoms[81][2];  // two players

for (unsigned x(0); x < 81; ++x)
  if (board[x])
    myHash ^= randoms[x][board[x]];
Источник

Для чего бы это ни стоило, вы можете сохранить состояние поворота как немного в начале хэша...

inline bool GetTurn(int hash){
  return (bool)(hash & 1);
}

и у всех хеш-ключей Zobrist в массиве есть 0 для их младшего значащего бита, напр. [[0x2348dec2, 0x93857e34, ....] ...]

Источник
Другие вопросы по тегам