Zobrist-hashing

Zobrist-hashing kent pseudowillekeurige getallen toe aan de kenmerken waaruit een stelling kan bestaan. Gewoonlijk is er een getal voor elke combinatie van stuksoort, kleur en veld, plus getallen voor de kant die aan zet is, de rokaderechten, die vastleggen of koning en toren die bijzondere zet nog mogen uitvoeren, en de relevante en-passanttoestand voor de bijzondere pionnenslag. Pseudowillekeurig betekent dat de waarden willekeurig lijken, maar reproduceerbaar worden gegenereerd.

De stellingssleutel wordt gevormd door de actieve waarden te combineren met XOR, een afkorting van exclusive OR, een binaire bewerking die als een schakelaar werkt: dezelfde waarde tweemaal toepassen maakt haar effect ongedaan. Wanneer een stuk beweegt, kan het programma de waarde van het oude veld uit de sleutel verwijderen en die van het nieuwe veld toevoegen zonder de hele sleutel opnieuw op te bouwen. Slagen, promoties en wisselingen van de zetbeurt kunnen op dezelfde manier worden bijgewerkt.

Met deze vingerafdruk kan een schaakengine, een programma dat stellingen analyseert, snel herkennen dat een stelling al eerder is verschenen. Zij kan opgeslagen analyse hergebruiken wanneer verschillende zettenreeksen dezelfde toestand bereiken, herhalingen detecteren en caches organiseren, snelle opslagplaatsen voor eerdere resultaten. Voor een juiste vergelijking is meer nodig dan de plaatsing van de stukken, omdat de zetbeurt en bijzondere rechten de legale mogelijkheden kunnen veranderen.

Een Zobrist-sleutel is niet gegarandeerd uniek. Twee verschillende stellingen kunnen hetzelfde getal opleveren, een verschijnsel dat een botsing heet. Grote sleutels maken dit onwaarschijnlijk, maar opslag en verificatie moeten rekening houden met die mogelijkheid. In tests zoals perft kan een incrementele sleutel ook bijwerkfouten onthullen wanneer hij na het uitvoeren en terugnemen van een zet niet naar zijn oorspronkelijke waarde terugkeert.