Enregistrer le joueur dans le hash Zobrist

Question

J'implémente actuellement une table de Transposition dans un algorithme de minimax de Checkers chinois. Dans Chinese Checkers, aucune pièce n'est capturée, et le plateau a une taille fonctionnelle de 81 cases. Les joueurs prennent des pièces en mouvement à travers le tableau.

Une partie du processus consiste à créer un hachage pour l'état de la carte. Jusqu'à présent, j'ai une méthode de fonctionnement qui crée un (je l'espère) hachage unique pour chaque état du plateau:

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) 
} 

Plus important encore, je fais progressivement dans la fonction applyMove (et la fonction 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(); 
} 

Cela fonctionne en raison de la propriété de réversibilité de la fonction XOR.

Le problème que j'ai maintenant, c'est que la fonction de hachage ne stocke pas dont le tour est. Autrement dit, vous pourriez avoir deux plateaux de jeu identiques, mais ils renverraient des valeurs différentes dans l'algorithme minimax parce que l'un essayait de maximiser le score, et l'autre essayait de le minimiser. Fondamentalement, ma question est la suivante: Comment puis-je stocker le tour du joueur dans une fonction de hachage par incrément, tout en gardant la possibilité de l'inverser parfaitement (et de préférence à peu de frais)? En supposant que le tour du joueur est un entier plutôt qu'un booléen, puisque le jeu aura finalement 6 joueurs plutôt que deux joueurs.

Answer 1

Vous pouvez utiliser un tableau turns[6] rempli de valeurs pseudo-aléatoires:

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 

ce qui est similaire à la position de mise à jour incrémentale pièce et fonctionne pour n ∈ [2, 6].

---

Comme une note de côté ...

habituellement hash Zobrist se fait en balayant l'emplacement des pièces, hors carrés vides. L'emplacement des carrés vides n'est pas explicitement haché. Par conséquent, vous pouvez utiliser une baie plus petite (plus sensible au cache). Quelque chose comme:

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

Pour ce que ça vaut la peine, vous pouvez stocker l'état de tour comme un peu au début du hachage ...

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

et ont les clés de hachage Zobrist dans le tableau tous avoir 0 pour leur bit le moins significatif, ex. [[0x2348dec2, 0x93857e34, ....] ...]