Fonction de hachage de Zobrist

Le hachage Zobrist (également appelé clés Zobrist ou signatures Zobrist ^[1] ) 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^[2]. 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^[3].

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article est orphelin. Moins de trois articles lui sont liés (septembre 2023).

Vous pouvez aider en ajoutant des liens vers [[Fonction de hachage de Zobrist]] dans les articles relatifs au sujet.

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 :^{[réf. nécessaire]}

indices constants
  pion_blanc := 1
  tour_blanc := 2
  # etc.
  roi_noir := 12

fonction init_zobrist() :
  # initialisation: remplir une table de nombres/chaînes de bits aléatoires (table de transposition)
  table := un tableau 2D de taille 64×12
  pour i de 1 à 64 :   # boucle qui couvre l'échiquier (représenté sous forme d'un tableau linéaire)
    pour j de 1 à 12 : # boucle sur les pièces du jeu, noires et blanches
      table[i][j] := chaîne_de_bits_aléatoire()
  table.noirs_vont_jouer = chaîne_de_bits_aléatoire()

fonction de hachage (échiquier):
  h := 0
  si trait_aux_noirs(échiquier) :
    h := h XOR table.noirs_vont_jouer
  pour i de 1 à 64 : # boucle qui couvre l'échiquier
    si échiquier[i] ≠ vide :
      j := échiquier[i]        # comme indiqué dans les indices constants ci-dessus
      h := h XOR table[i][j]   # XOR binaire entre la valeur de hachage dans la table de transposition et h
  retourner h

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^[1]. 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^[1].

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^[1]. 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 :

'pion sur cette case' ( XOR le pion capturé sur cette case)
'tour sur cette case' ( XOR la tour qui va désormais occuper cette case)
'tour à la case source' ( XOR cette même tour qui quitte sa case source)

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^[3].

Voir également

Références

↑ ^{a b c et d} Bruce Moreland. Zobrist keys: a means of enabling position comparison.
↑ Albert Lindsey Zobrist, A New Hashing Method with Application for Game Playing, Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).
↑ ^{a et b} Mason, Hudson et Sutton, « Fast recall of state-history in kinetic Monte Carlo simulations utilizing the Zobrist key », Computer Physics Communications, vol. 165, n^o 1,‎ 2005, p. 37–48 (DOI 10.1016/j.cpc.2004.09.007, Bibcode 2005CoPhC.165...37M)

[moreland-1] {a b c et d} Bruce Moreland. Zobrist keys: a means of enabling position comparison.

[2] Albert Lindsey Zobrist, A New Hashing Method with Application for Game Playing, Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).

[MonteCarlo-3] {a et b} Mason, Hudson et Sutton, « Fast recall of state-history in kinetic Monte Carlo simulations utilizing the Zobrist key », Computer Physics Communications, vol. 165, n^o 1,‎ 2005, p. 37–48 (DOI 10.1016/j.cpc.2004.09.007, Bibcode 2005CoPhC.165...37M)

[1]

[2]

[3]