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 chess and Go, to implement transposition tables, 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

  1. etc.

black_king := 12

function init_zobrist():

  1. 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

Use of the hash value

If the bitstrings are long enough, different board positions will almost certainly hash to different values; however longer bitstrings require proportionally more computer resources to manipulate. The most commonly used bitstring (key) length is 64 bits.

See also

  • Alpha–beta pruning

References