Zobrist Incremental Board Hashing
Cancel and replace piece features to update a board hash incrementally.
Free theory articleCancel and replace piece features to update a board hash incrementally.
Concept & interpretation
Zobrist hashing is a technique used to create a hash of a board position, such as in chess or tic-tac-toe. Instead of hashing the entire board state from scratch every time a move is made, the hash is updated incrementally using bitwise XOR operations. This allows for extremely fast hash updates, which is essential when searching through millions of positions in game trees.
Experiment
Use the interactive module to see incremental hashing in action:
- Change the Board to "A corner" and the New piece to "Empty". Notice how the XOR delta directly cancels out the feature key of the existing piece, leaving an empty hash of 0.
- Try changing the Board to "B center". Notice that its base hash is 37, which is identical to the base hash of "A corner". This is an example of a hash collision caused by using small 8-bit feature keys where some keys intentionally coincide.
- Select the same piece as the one already at the cell. The XOR delta will be 0, and the board will not change.