Zobrist-Hashing

Zobrist-Hashing weist den Merkmalen, aus denen eine Stellung bestehen kann, pseudozufällige Zahlen zu. Gewöhnlich gibt es eine Zahl für jede Kombination aus Figurentyp, Farbe und Feld sowie Zahlen für die Seite am Zug, die Rochaderechte, welche festhalten, ob König und Turm den besonderen Zug noch ausführen dürfen, und den relevanten en-passant-Zustand für den besonderen Bauernschlag. Pseudozufällig bedeutet, dass die Werte zufällig erscheinen, aber reproduzierbar erzeugt werden.

Der Stellungsschlüssel entsteht, indem die aktiven Werte mittels XOR verknüpft werden, kurz für exclusive OR, einer binären Operation, die wie ein Umschalter wirkt. Wird derselbe Wert zweimal angewendet, hebt sich seine Wirkung auf. Wenn eine Figur zieht, kann das Programm ihren Wert für das alte Feld aus dem Schlüssel entfernen und ihren Wert für das neue Feld hinzufügen, ohne den Schlüssel vollständig neu aufzubauen. Schlagzüge, Umwandlungen und Seitenwechsel lassen sich auf dieselbe Weise aktualisieren.

Dieser Fingerabdruck lässt eine Schachengine, also ein Programm zur Stellungsanalyse, schnell erkennen, dass eine Stellung bereits vorgekommen ist. Sie kann gespeicherte Analysen wiederverwenden, wenn verschiedene Zugfolgen denselben Zustand erreichen, Wiederholungen erkennen und Caches organisieren, also schnelle Speicher früherer Ergebnisse. Für einen korrekten Vergleich reicht die Figurenaufstellung nicht aus, weil Zugrecht und Sonderrechte die legalen Möglichkeiten verändern können.

Ein Zobrist-Schlüssel ist nicht garantiert eindeutig. Zwei verschiedene Stellungen können dieselbe Zahl erzeugen, was als Kollision bezeichnet wird. Große Schlüssel machen dies unwahrscheinlich, doch Speicherung und Überprüfung müssen die Möglichkeit weiterhin berücksichtigen. Bei Tests wie Perft kann ein inkrementeller Schlüssel außerdem Aktualisierungsfehler aufdecken, wenn er nach Ausführung und Rücknahme eines Zuges nicht zu seinem ursprünglichen Wert zurückkehrt.