Хранение игрока в Zobrist hash

Question

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

Answer 1

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

Answer 2

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

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

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