Zobrist Hashing
Created on 2024-04-22T20:27:45-05:00
A hashing scheme for dealing with game decision trees and boards.
Features like board position, chess piece, and color to move, are given random bit strings.
Relevant features are XORed together to create the new hash.
Because XORing is used you can also remove features by just XORing the feature again. This makes it cheaper to update state.
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() table.black_to_move = random_bitstring() function hash(board): h := 0 if is_black_turn(board): h := h XOR table.black_to_move 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