Hashing Zobrist

Hashingul Zobrist atribuie numere pseudoaleatorii caracteristicilor care pot forma o poziție. Există de obicei câte un număr pentru fiecare combinație de tip de piesă, culoare și câmp, plus numere pentru partea aflată la mutare, drepturile de Rocadă, care indică dacă regele și turnul mai pot efectua acea mutare specială, și starea en passant relevantă pentru captura specială de pion. Pseudoaleatoriu înseamnă că valorile par aleatorii, dar sunt generate reproductibil.

Cheia poziției se formează prin combinarea valorilor active cu XOR, abreviere pentru OR exclusiv, o operație binară care funcționează ca un comutator: aplicarea aceleiași valori de două ori îi anulează efectul. Când o piesă se mută, programul poate elimina din cheie valoarea câmpului vechi și o poate adăuga pe cea a câmpului nou, fără să reconstruiască cheia de la zero. Capturile, promovările și schimbarea părții aflate la mutare pot fi actualizate în același mod.

Această amprentă îi permite unui motor de șah, adică unui program care analizează poziții, să recunoască rapid că o poziție a mai apărut. El poate reutiliza analiza stocată când secvențe diferite de mutări ajung la aceeași stare, poate detecta repetările și poate organiza cache-uri, adică spații rapide de stocare a rezultatelor anterioare. Comparația corectă necesită mai mult decât amplasarea pieselor, deoarece partea aflată la mutare și drepturile speciale pot schimba posibilitățile legale.

Nu există garanția că o cheie Zobrist este unică. Două poziții diferite pot produce același număr, fenomen numit coliziune. Cheile mari fac acest lucru improbabil, dar stocarea și verificarea trebuie totuși să țină cont de posibilitate. În teste precum perft, o cheie incrementală poate dezvălui și erori de actualizare atunci când nu revine la valoarea inițială după efectuarea și anularea unei mutări.