Hachage de Zobrist

Le hachage de Zobrist attribue des nombres pseudo-aléatoires aux éléments susceptibles de former une position. Il existe généralement un nombre pour chaque combinaison de type de pièce, de couleur et de case, ainsi que des nombres pour le camp au trait, les droits de roque, qui indiquent si le roi et une tour peuvent encore effectuer ce coup spécial, et l'état pertinent de la prise en passant. Pseudo-aléatoire signifie que les valeurs paraissent aléatoires, mais sont produites de manière reproductible.

La clé de position est obtenue en combinant les valeurs actives avec XOR, abréviation de l'OU exclusif, une opération binaire qui agit comme un interrupteur : appliquer deux fois la même valeur annule son effet. Lorsqu'une pièce se déplace, le programme peut retirer de la clé sa valeur sur l'ancienne case et ajouter sa valeur sur la nouvelle, sans reconstruire la clé depuis zéro. Les captures, promotions et changements de trait s'actualisent de la même manière.

Cette empreinte permet à un moteur d'échecs, un programme qui analyse des positions, de reconnaître rapidement qu'une position s'est déjà présentée. Il peut réutiliser une analyse mémorisée lorsque différentes suites de coups atteignent le même état, détecter les répétitions et organiser des caches, c'est-à-dire des stockages rapides de résultats antérieurs. Une comparaison correcte exige davantage que la seule disposition des pièces, car le trait et les droits spéciaux peuvent modifier les possibilités légales.

Une clé de Zobrist n'est pas garantie unique. Deux positions différentes peuvent produire le même nombre, phénomène appelé collision. Des clés de grande taille rendent ce cas peu probable, mais le stockage et la vérification doivent encore en tenir compte. Dans des tests comme perft, une clé incrémentale peut aussi révéler des erreurs de mise à jour si elle ne revient pas à sa valeur initiale après qu'un coup a été joué puis annulé.