Зобристово хеширање

Зобристово хеширање (такође познато као Зобристови кључеви или Зобристови потписи^[1]) је хеш функција која се користи у компјутерским програмима који играју апстрактне игре на табли, као што су Шах и „Go“, за имплементацију табеле транспозиције, специјалну врсту хеш табеле која се индексира према позицијама на табли и користи се да би се избегло анализирање исте позиције више од једном. Зобристово хеширање је добило име по свом проналазачу, Алберт Линдзи Зобрист.^[2] Такође се примењује као метод за препознавање одређених заменских легура у процесу симулације кристализације материјала.^[3]

Рачунање хеш вредности

Зобристово хеширање почиње генерисањем псеудослучајних низова битова за сваки могући елемент игре, односно за сваку комбинацију фигуре и позиције (у шаху, то је 12 фигура × 64 позиције, или 14 ако се краљ који се може затворити и пешак који може да ухвати претицање третирају одвојено). Свака конфигурација табле може бити раздвојене у независне фигура/позиција компоненте, које се мапирају по случајним низовима битова генерисаним раније. Коначно Зобристово хеширање се рачуна комбиновањем ових низова битова коришћењем ексклузивне битске дисјункције XOR. Пример псеудокода за игру шаха:

   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

Коришћење хеш вредности

Ако су низови битова довољно дуги, различите позиције на табли ће скоро сигурно имати различите вредности; ипак, дужи низови захтевају пропорционално више ресурса за рад. Многи програми чувају само хеш вредности у табели транспозиције, избегавајући саму информацију о позицији у потпуности ради смањивања меморијске захтевности, и претпостављајући да се судари хеша неће појавити, или да неће много утицати на резултат на табли ако се појаве.

Зобристово хеширање је прва позната имплементација табличног хеширања. Ово је резултат троструких независних хеш фамилија. Посебно, то је универзално хеширање.

На пример, у шаху, сваки од 64 квадрата може бити празан у било ком тренутку, или да садржи једну од 6 фигура, које су беле или црне. Односно, сваки квадрат може бити у једном од 1 + 6 x 2 = 13 могућих стања у било ком тренутку. Тако да за сваки квадрат мора бити генерисано 13 x 64 = 832 насумичних низова битова. Када му је дата позиција, квадрат добија хеш вредност откривањем која је фигура на ком квадрату, и комбиновањем битних низова битова.

Освежавање хеш вредности

Уместо да рачуна хеш вредности за целу таблу сваки пут, као што наведени псеудокод изнад ради, хеш вредност табле може бити освежена применом екслузивне битске дисјункције за оне вредности хеша које су се промениле и низове битова нових позиција. На пример, ако је пешак на неком пољу замењен топом са другог поља, резултујућа позиција се добија применом ХОR постојећих хеш вредности за:

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

Ово чини Зобристово хеширање веома ефикасним за разапињање стабла игре.

У игри Go, овај метод се такође користи за проналажење суперко елемента.

Шира примена

Исти метод се користи за препознавање заменских легура у процесу кристализације елемената за спречавање узалудног утрошка труда на стања која су већ обрађена.^[3]

Види још

Алфа-бета претрага

Референце

^ Zobrist keys: a means of enabling position comparison.
^ Albert Lindsey Zobrist, A New Hashing Method with Application for Game Playing, Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).
^ ^а ^б Mason, D.R.; Hudson, T.S.; Sutton, A.P. (2005). „Fast recall of state-history in kinetic Monte Carlo simulations utilizing the Zobrist key”. Computer Physics Communications. 165 (1): 37—48. Bibcode:2005CoPhC.165...37M. doi:10.1016/j.cpc.2004.09.007.

[1] Zobrist keys: a means of enabling position comparison.

[2] Albert Lindsey Zobrist, A New Hashing Method with Application for Game Playing, Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).

[MonteCarlo-3] а ^б Mason, D.R.; Hudson, T.S.; Sutton, A.P. (2005). „Fast recall of state-history in kinetic Monte Carlo simulations utilizing the Zobrist key”. Computer Physics Communications. 165 (1): 37—48. Bibcode:2005CoPhC.165...37M. doi:10.1016/j.cpc.2004.09.007.

[1]

[2]

[3]