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

Question

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

В настоящее время я реализую таблицу транспозиции в минимаксном алгоритме китайских шашек. В китайских шашках фигуры не захватываются, и доска функционально занимает 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

algorithm c++game-ai hash hash-function

Решение

Другие решения

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

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

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

0

Источник

Accepted Answer

Вы можете использовать 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].

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

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

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

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

for (unsigned x(0); x < 81; ++x)
if (board[x])
myHash ^= randoms[x][board[x]];

1