Zobrist hashing
Zobrist hashing
- Zobrist hashing (also referred to as Zobrist keys or Zobrist signatures** ) is a hash function construction used in computer programs that play abstract board games, such as [[computer-chess|chess]] and [[computer-go|Go]], to implement [[transposition-table]]s, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same position more than once. Zobrist hashing is named for its inventor, Albert Lindsey Zobrist. It has also been applied as a method for recognizing substitutional alloy configurations in simulations of crystalline materials. Now any board configuration can be broken up into independent piece/position components, which are mapped to the random bitstrings generated earlier. The final Zobrist hash is computed by combining those bitstrings using bitwise XOR. Example pseudocode for the game of chess:
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