Zobristovo heširanje

**Zobristovo heširanje** (takođe poznato kao **Zobristovi ključevi** ili **Zobristovi potpisi** ) je heš funkcija koja se koristi u kompijuterskim programima koji igraju apstraktne igre na tabli, kao što su Šah i "Go", za implementaciju tabele transpozicije, specijalnu vrstu heš tabele koja se indeksira prema pozicijama na tabli i koristi se da bi se izbeglo analiziranje iste pozicije više od jednom. Zobristovo heširanje je dobilo ime po svom pronalazaču, Albert Lindzi Zobrist (programer). Takođe se primenjuje kao metod za prepoznavanje određenih zamenskih legura u procesu simulacije kristalizacije materijala.

## Računanje heš vrednosti
Zobristovo heširanje počinje generisanjem pseudoslučajnih nizova bitova za svaki mogući element igre, odnosno za svaku kombinaciju figure i pozicije (u šahu, to je 12 figura × 64 pozicije, ili 14 ako se kralj koji se može zatvoriti i pešak koji može da uhvati *[[preticanje]]* tretiraju odvojeno).Svaka konfiguracija table može biti razdvojenea u nezavisne figura/pozicija komponente, koje se mapiraju po slučajnim nizovima bitova generisanim ranije. Konačno Zobristovo heširanje se računa kombinovanjem ovih nizova bitova korišćenjem ekskluzivne bitske disjunkcije XOR. Primer pseudokoda za igru šaha:

stalni indeksi
beli_pion := 1
beli_top := 2
# itd.
crni_kralj := 12

function pocetno_hesiranje():
# popunjavanje tabele nasumičnim brojevima/nizovima bitova
table := a 2-d niz duzine 64×12
for i from 1 to 64: # petlja kroz tablu, predstavljenu kao linearni niz
for j from 1 to 12: # petlja kroz figure
table[i][j] = nasumicni_niz_bitova()

function hash(board):
h := 0
for i from 1 to 64: # petlja kroz pozicije
if board[i] != empty:
j := figura na tabli[i], kao sto je navedena u tabeli konstantnih indeksa
h := h XOR table[i][j]
return h

## Korišćenje heš vrednosti
Ako su nizovi bitova dovoljno dugi, različite pozicije na tabli će skoro sigurno imati različite vrednosti; ipak, duži nizovi zahtevaju proporcionalno više resursa za rad. Mnogi programi čuvaju samo heš vrednosti u tabeli tanspozicije, izbegavajući samu informaciju o poziciji u potpunosti radi smanjivanja memorijske zahtevnosti, i pretpostavljajući da se sudari kešaneće pojaviti, ili da neće mnogo uticati na rezultat na tabli ako se pojave.

Zobristovo heširanje je prva poznata implementacija tabličnog heširanja. Ovo je rezultat trostrukih nezavisnih heš familija. Posebno, to je univerzalno heširanje.

Na primer , u šahu, svaki od 64 kvadrata može biti prazan u bilo kom trenutku, ili da sadrži jednu od 6 figura, koje su bele ili crne. Odnosno,svaki kvadrat može biti u jednom od 1 + 6 x 2 = 13 mogućih stanja u bilo kom trenutku. Tako da za svaki kvadrat mora biti generisano 13 x 64 = 832 nasumičnih nizova bitova. Kada mu je data pozicija, kvadrat dobija heš vrednost otkrivanjem koja je figura na kom kvadratu, i kombinovanjem bitnih nizova bitova.

## Osvežavanje heš vrednosti
Umesto da računa heš vrednosti za celu tablu svaki put, kao što navedeni pseudokod iznad radi, heš vrednost table može biti osvežena primenom ekssluzivne bitske disjunkcije za one vrednosti heša koje su se promenile i nizove bitova novih pozicija. Na primer, ako je pešak na nekom polju zamenjen topom sa drugog polja, rezultujuća pozicija se dobija primenom HOR postojećih heš vrednosti za:
'pešak na ovom polju' (XOR *napolje* pešak sa ovog polja)
'top na ovom polju' (XOR *unutra* top na ovom polju)
'top na početnom polju' (XOR *napolje* top na početnom polju)
'ništa na početnom polju' (XOR *unutra* ništa na početnom polju).
Ovo čini Zobristovo heširanje veoma efikasnim za razapinjanje stabla igre.

U igri Go, ovaj metod se takođe koristi za pronalaženje superko elementa.

## Šira primena
Isti metod se koristi za prepoznavanje zamenskih legura u procesu kristalizacije elemenata za sprečavanje uzaludnog utroška truda na stanja koja su već obrađena.

## Reference