Hashing di Zobrist

L’hashing di Zobrist assegna numeri pseudocasuali agli elementi che possono formare una posizione. Di norma esiste un numero per ogni combinazione di tipo di pezzo, colore e casa, oltre a numeri per la parte al tratto, i diritti di arrocco, che registrano se re e torre possono ancora eseguire quella mossa speciale, e lo stato pertinente dell’en passant per la cattura speciale di pedone. Pseudocasuale significa che i valori sembrano casuali ma vengono generati in modo riproducibile.

La chiave della posizione si forma combinando i valori attivi con XOR, abbreviazione di exclusive OR, un’operazione binaria che funziona come un interruttore: applicare due volte lo stesso valore ne annulla l’effetto. Quando un pezzo muove, il programma può rimuovere dalla chiave il valore della vecchia casa e aggiungere quello della nuova senza ricostruire tutto da zero. Catture, promozioni e cambi di tratto possono essere aggiornati nello stesso modo.

Questa impronta consente a un motore scacchistico, cioè un programma che analizza posizioni, di riconoscere rapidamente che una posizione è già comparsa. Può riutilizzare analisi memorizzate quando sequenze diverse raggiungono lo stesso stato, rilevare ripetizioni e organizzare cache, cioè memorie rapide di risultati precedenti. Un confronto corretto richiede più della disposizione dei pezzi, perché la parte al tratto e i diritti speciali possono modificare le possibilità legali.

Una chiave di Zobrist non è garantita come unica. Due posizioni diverse possono produrre lo stesso numero, evento chiamato collisione. Chiavi grandi rendono il fenomeno improbabile, ma archiviazione e verifica devono comunque tenerne conto. In test come perft, una chiave incrementale può anche rivelare errori di aggiornamento quando non ritorna al valore originale dopo che una mossa è stata eseguita e annullata.