Zobrist Hash

Zobrist Hashing (juga biasa disebut Kunci Zobrist atau Tanda Tangan Zobrist) adalah sebuah konstruksi fungsi hash yang digunakan didalam program komputer seperti permainan abstract board games, mirip catur dan Go, untuk mengimplementasi tabel transposisi, sebuah jenis tabel hash yang terindeks dari posisi board dan digunakan untuk menghindari analisis pada posisi yang sama lebih dari satu. Zobrist hashing diambil nama dari penemunya yaitu Albert Lindsey Zobrist. Hal ini juga sudah diterapkan sebagai metode untuk mengenali konfigurasi alloy dalam simulasi kristalisasi bahan.

Perhitungan nilai hash

Zobrist hashing memulai secara acak untuk menggenerate bitstring untuk setiap kemungkinan elemen pada permainan board, i.e untuk setiap bagian kombinasi dan posisi (dalam permainan catur, dalam 12 bagian x 64 posisi board, atau 14 x 64 jika raja masih berada di benteng dan bidak tertangkap secara terpisah). Sekarang konfigurasi board apapun bisa diretas/pecah menjadi komponen independen/posisi komponen, yang dipetakan ke bitstring secara acak dari hasil sebelumnya. Zobrist Hash yang terakhir dihitung dengan menggabungkan bitstring tersebut menggunakan bit XOR. Contoh psudokode dari permainan catur:

constant indices
       white_pawn:= 1
       white_rook:= 2
       # etc.
       black_king:= 12
   
   function init_zobrist():
       # fill a table of random numbers/bitstrings
       table:= a 2-d array of size 64×12
       for i from 1 to 64:  # loop over the board, represented as a linear array
           for j from 1 to 12:      # loop over the pieces
               table[i][j] = random_bitstring()
   
   function hash(board):
       h:= 0
       for i from 1 to 64:      # loop over the board positions
           if board[i] != empty:
               j:= the piece at board[i], as listed in the constant indices, above
               h:= h XOR table[i][j]
       return h

Penggunaan Nilai Hash

Jika bitstring cukup panjang, perbedaan posisi board akan hampir dipastikan memiliki nilai hash yang berbeda; namun seberapapun panjangnya bitstring akan membutuhkan sumber daya komputer untuk di manipulasi. Panjang bitstring (kunci) yang paling banyak digunakan adalah 64 bits. Banyak mesin game hanya menyimpan nilai hash di tabel transposisi, sebenarnya menghilangkan posisi informasi itu sendiri hanya untuk mengurangi penggunaan memori, dan asumsi bahwa terjadi tabrakan hash tidak akan terjadi, atau tidak akan banyak mempengaruhi hasil tabel jika mereka menggunakannya.

Zobrist hashing adalah contoh hashing tabulasi pertama yang diketahui. Hasilnya adalah 3-wise independent hash familiy. Secara khusus ini sangat kuat.

Sebagai contoh, dalam catur, masing-masing dari 64 kotak dapat setiap saat kosong, atau berisi salah satu dari 6 buah permainan, yang hitam atau putih. Artinya, setiap kuadrat dapat berada dalam salah satu dari 1 + 6 x 2 = 13 keadaan yang memungkinkan setiap saat. Jadi seseorang perlu menghasilkan paling banyak 13 x 64 = 832 bitstring acak. Diberi posisi, orang mendapatkan hash Zobristnya dengan mencari tahu bagian mana yang berada di kotak mana, dan menggabungkan bitstring yang relevan bersama-sama.

Memperbarui Nilai Hash

Daripada menghitung hash untuk seluruh papan setiap kali, seperti pseudocode di atas, nilai hash dari papan dapat diperbarui hanya dengan XORing keluar dari bitstring (s) untuk posisi yang telah berubah, dan XORing dalam bitstring untuk yang baru posisi. Misalnya, jika pion pada papan catur digantikan oleh benteng dari kotak lain, posisi yang dihasilkan akan dihasilkan oleh XORing hash yang ada dengan bitstring untuk:

 'pawn at this square'      (XORing out the pawn at this square)
 'rook at this square'      (XORing in the rook at this square)
 'rook at source square'    (XORing out the rook at the source square)
 'nothing at source square' (XORing in nothing at the source square).

Ini membuat hashing Zobrist sangat efisien untuk melintasi pohon permainan .

Di komputer, teknik ini juga digunakan untuk deteksi superko .

Penggunaan Lebih Luas

Metode yang sama telah digunakan untuk mengenali konfigurasi paduan pengganti selama simulasi Monte Carlo untuk mencegah pemborosan upaya komputasi pada keadaan yang telah dihitung.

Universitas Budi Luhur