Zobrist Incremental Board Hashing

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.

The board is initialized with a predetermined feature key for every possible piece at every possible location. When a piece is placed or removed, we XOR the hash with the key of the outgoing piece (which "cancels" it out) and then XOR with the key of the incoming piece.

Worked Example

Let's examine how a board update works. Consider a cross-shaped board. We want to update cell 4 (the center) by replacing its current piece with a new piece B.

1. Base hash of Cross board = 72 2. The outgoing piece at cell 4 is A, with feature key = 68 3. The incoming piece is B, with feature key = 37 4. XOR Delta = 68 ^ 37 = 97 5. Incremental hash = 72 ^ 97 = 41 6. If we independently recompute the full board with B at cell 4, we also get 41.

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.

Limitations

This module uses simplified 8-bit feature keys to demonstrate the concept. Because 8-bit space is very small (only 256 possible values), hash collisions are highly likely. A collision occurs when two different board states produce the exact same hash (like "A corner" and "B center"). In real applications, wider random keys (like 64-bit integers) are used. While this drastically reduces collisions, it does not completely eliminate them. Thus, a Zobrist hash is not a secure cryptographic digest or an absolutely perfect equality test, and collision resolution is still necessary when storing boards in transposition tables.

References

The original technique for game trees was introduced by Albert Zobrist, detailing how XORing random constants produces uniform incremental hash updates. Below are the primary resources for further exploration of this module and technique:

Zobrist, A. L. (1970). A new hashing method with application for game playing. Technical Report 88, Computer Sciences Department, University of Wisconsin, Madison.

Zobrist Incremental Board Hashing