# Fonction de hachage de Zobrist

Le hachage Zobrist (également appelé clés Zobrist ou signatures Zobrist ) est une fonction de hachage utilisée dans les programmes informatiques qui jouent à des jeux de société abstraits, tels que les échecs et le go, via des tables de transposition, un type spécial de table de hachage qui est indexé par une position sur le plateau et utilisé pour éviter d’analyser la même position plus d’une fois. Le hachage Zobrist doit son nom à son inventeur, Albert Lindsey Zobrist. Cette fonction a également été appliquée comme méthode de reconnaissance des configurations d'alliages de substitution dans les simulations de matériaux cristallins.

## Calcul de la valeur de hachage

Le hachage Zobrist commence par générer aléatoirement des chaînes de bits pour chaque élément possible d'un jeu de société, c'est-à-dire pour chaque combinaison d'une pièce et d'une position (dans le jeu d'échecs, cela fait 12 pièces × 64 positions sur le plateau, ou 18 × 64 si les rois et les tours peuvent encore roquer, et les pions qui peuvent capturer en passant sont traités séparément pour les deux couleurs). Ainsi, toutes les configurations de plateaux peuvent être divisées en composantes pièce/position indépendantes, qui sont chacune mappées avec chaînes de bits aléatoires générées précédemment. Le hachage Zobrist final est calculé en combinant ces chaînes de bits à l'aide d'opérations binaires XOR. Exemple de pseudo-code pour le jeu d'échecs :

## Utilisation de la valeur de hachage

Si les chaînes de bits sont suffisamment longues, des positions différentes sur le plateau donneront presque certainement des valeurs de hachage différentes ; néanmoins, les chaînes de bits plus longues nécessitent proportionnellement plus de ressources informatiques pour être manipulées. La longueur de chaîne de bits (clé) la plus couramment utilisée est de 64 bits. De nombreux moteurs de jeu stockent uniquement les valeurs de hachage dans la table de transposition, en omettant entièrement les informations de position elles-mêmes pour réduire l'utilisation de la mémoire et en supposant que les collisions de hachage ne se produiront pas ou n'influenceront pas grandement les résultats de la table si elles se produisaient.
Le hachage Zobrist est le premier exemple connu de hachage de tabulation . Le résultat est une famille de hachage indépendante à 3 niveaux . En particulier, il est fortement universel.
A titre d'exemple, aux échecs, à un instant donné chacune des 64 cases de l'échiquier peut être vide ou contenir l'une des 6 pièces du jeu, qui sont soit noires, soit blanches (12 au total). De plus, le trait peut soit être aux noirs (aux noirs de jouer) ou aux blancs. Il faut donc générer 6 x 2 x 64 + 1 = 769 chaînes de bits aléatoires. Étant donnée une position, on obtient son hachage Zobrist en déterminant quelles pièces se trouvent sur quelles cases et en combinant les chaînes de bits pertinentes ensemble. Si le trait est aux noirs, lorsque la position est analysée, la chaîne de bits "table.noirs_vont_jouer" est également incluse dans le calcul du hachage.

## Mise à jour de la valeur de hachage

Plutôt que de calculer le hachage du plateau en entier à chaque fois, comme le fait le pseudo-code ci-dessus, la valeur de hachage du plateau peut être mise à jour de manière incrémentale en effectuant simplement une opération XOR sur les chaînes de bits correspondant aux positions des pièces capturées d'une part, et des mouvements des pièces du joueur qui a le trait d'autre part. On calcule initialement la valeur de hachage pour la première position du jeu, puis, incrémentalement, on effectue un XOR pour chaque pièce capturée et pour chaque mouvement de pièces.
L'intérêt de l'utilisation de l'opération XOR est que si c := a XOR b alors c XOR a donne b et c XOR b donne a.
Par exemple, si un pion sur une case de l'échiquier est remplacé par une tour d'une autre case, la position résultante serait produite en effectuant un XOR sur la valeur de hachage courante avec les chaînes de bits :
Cela rend cette méthode de hachage très efficace pour identifier des positions identiques lorsque l'on parcourt l'arbre de jeu et permet d'éviter de recalculer plusieurs fois la même position.
Dans l'ordinateur Go, cette technique est également utilisée pour la détection de superko.

## Utilisation plus large

De manière plus générique, le hachage Zobrist peut être appliqué sur des ensembles finis d'éléments (dans l'exemple des échecs, ces éléments sont les tuples $(piece,position)$, à condition que l'on puisse attribuer une chaîne de bits aléatoire à chacun des éléments possibles. Cela peut être fait soit avec un générateur de nombres aléatoires pour les espaces d'éléments plus petits, soit avec une fonction de hachage pour les plus grands. Cette méthode a été utilisée pour reconnaître les configurations d'alliages de substitution lors des simulations de Monte Carlo afin d'éviter de recalculer les états déjà calculés.

## Voir également

* Élagage alpha-bêta
* Méthode de Monte-Carlo
* Algorithme minimax