Drealmer's Tumblr

Zobrist Keys

When writing the AI for a board game, a basic optimization consists of pruning the search space from similar parts which have already been explored. To identify these parts, you have to be able to very quickly compare game configurations.

The problem is that the information that describes a game state (board position) might be too large to allow efficient comparisons, take up too much memory, require a lot of bit wizardry, etc. So a hash might come in handy.

[Zobrist Keys are] 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.

The principle is really simple: assign a random number to each piece for each position, then to hash a game state you just XOR these numbers together. Let me clarify this with a small example, here is the list of random numbers (generated once and for all) for a game played on a 8x8 board with 4 different pieces.

key_size ZKeys[4][8][8] = { ... }

And here is how you would describe a configuration where there is a piece of type 2 in (4,3), a piece of type 1 in (7,4), and a piece of type 3 in (2, 6):

key_size state = ZKeys[2][4][3] ^ ZKeys[1][7][4] ^ZKeys[3][2][6];

The recommended key size for chess is 64 bits, but keep in mind that this is a hash, so you cannot reverse it, and collisions are possible (but unlikely). Also notice that you can toggle a piece on and off a key with another XOR, so moving pieces without recomputing the whole key is fast and convenient.

Zobrist Hashing on Wikipedia: (link)

Zobrist Hashing on Chess Programming Wiki: (link)