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

1. itd.

crni_kralj := 12

function pocetno_hesiranje():

1. 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.