Zobristovo heširanje

Zobristovo heširanje (takođe poznato kao Zobristovi ključevi ili Zobristovi potpisi) je heš funkcija koja se koristi u kompjuterskim 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. 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 razdvojene 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():
       # попуњавање табеле насумичним бројевима/низовима битова
       table := a 2-d niz duzine 64×12
       for i from 1 to 64:  # петља кроз таблу, представљену као линеарни низ
           for j from 1 to 12:      # петља кроз фигуре
               table[i][j] = nasumicni_niz_bitova()
   
   function hash(board):
       h := 0
       for i from 1 to 64:      # петља кроз позиције
           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 transpozicije, izbegavajući samu informaciju o poziciji u potpunosti radi smanjivanja memorijske zahtevnosti, i pretpostavljajući da se sudari heša neć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 eksluzivne 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:

 'пешак на овом пољу'      (XOR напоље пешак са овог поља)
 'топ на овом пољу'      (XOR унутра топ на овом пољу)
 'топ на почетном пољу'    (XOR напоље топ на почетном пољу)
 'ништа на почетном пољу' (XOR унутра ништа на почетном пољу).

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.

Vidi još

• Alfa-beta pretraga