Zobrist Hashing

This post was originally published on my blog.

Zobrist hashing, named for its inventor Albert Zobrist, is a technique to represent game board positions, like from chess or Go, as hash value. It's mainly used with transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same board position more than once.

What it's good for

In game theory there are algorithms like Minimax or AlphaBeta that are used to analyze board positions and find the best possible move in the given situation. This might be applied to games like chess, Go or tic-tac-toe.

These algorithms take a given starting position and simulate the further course of the game with all possible moves for each player. With the help of an evaluation method, that is prescribed by the developer, the algorithm can calculate a score in each game situation. Based on this score the algorithm knows how good or bad a position is or a move that has led to this position. Ideally, the outpout of such an algorithm is the best possible move with it's calculated score.

One problem is that it might take a very long time to calculate the best possible move, especially for games like chess. That's because game like chess has a huge game tree. A game tree is a directed graph whose nodes are positions in a game and whose edges are moves. Algorithms like Minimax builds such a graph and traverse it to find the best possible move.

With the help of transposition tables it's possible to speed up these algorithms. Transposition tables act like a cache that store already analyzed board positions. While building up a game tree you mostly come across the same board position more than once. Without a transposition table you have to re-analyze the board position each time. So once the algorithm evaluated a position it stores the result in the transposition table to avoid this behavior. The next time the algorithm comes across this position it can take the result from the transposition table.

All in all: Transposition tables are used within the algorithms to avoid analyze the same position multiple times.

Mostly, transposition tables are implemented as a HashMap where the key is a board position in string representation. So regarding to a board position it's possible to store some information about it, like the best move.

This is where the Zobrist hash comes up: Zobrist hashing is a way to represent a given board position as an (unique) hash value. This hash is used within the transposition table to map information, like the best move, to the board and make it accessible.

So the following paragraph describes how a Zobrist hash works and how it's calculated. Tic-tac-toe is taken as example game here. At the end of this post you'll find an implementation in Kotlin.

How it works

Zobrist hashing works with a bunch of xor operations of random generated numbers, called keys. We break this down into two parts:

• Generating the keys
• Calculating the hash

Generating the keys

First of all, we have to generate keys according to the following scheme:

For every available board cell and every possible game character in one of these cells, we generate a random number.

This might sound a little bit confusing but it's actually quite easy. Let's have a look at our example, tic-tac-toe:

In a tic-tac-toe board, there are 9 available cells. In each of one of these cells there can be placed 2 different game characters: X or O. So according to above's quote we have to generate 18 (9*2) random numbers.

cell  |   player 1 (X)  |   player 2 (O)
------------------------------------------
0     |      44532      |      72217
1     |      90195      |      10291
2     |      81410      |      65932
3     |      36721      |      91854
...

In practice, most of the time 64 bit numbers, e.g. of data type Long, are used as random numbers. This reduces the risk of collisions while calculating the hashes later on.

Calculating the hash

Now, after the keys were generated it's possible to calculate the Zobrist hash of a given board position:

Take the previously generated random number of each cell where a game character is placed in and combine them per xor operation.

Again, it's easier than it might sound. Let's have an example.

Before we begin with that a quick note: The cells of our tic-tac-toe game are ordered like this: from 0 to 8.

0 1 2 
3 4 5
6 7 8

Okay, now it's time for an example. Have a look at the following board position:

X . O
X . .
. . .

Player 1 (X) in cells: 0, 3
Player 2 (O) in cells: 2

The players played in the following cells:

• Player 1: 0, 3
• Player 2: 2

Finally, we can calculate the Zobrist hash for this position: We take the random numbers / keys for these cells from above and combine them per xor operation. The order of the operations does not matter:

    44532 (cell #0 player 1)
XOR 65932 (cell #2 player 2)
XOR 36721 (cell #3 player 1)
---------
  = 74505 (Zobrist hash)

We successfully calculated the Zobrist hash for the game position: 74505.

Now, this hash can be used to store the board position inside the transposition table. In this case, the calculated hash value is used as key.

Reusing the hash

A huge advantage of this procedure is that it's not necessary to calculate the hash completely new after a move was played: We can take the key of the cell where the new move is played and combine it with the already existing Zobrist hash.

Assuming we have the same position as above:

X . O
X . .
. . .

=> 74505 (Zobrist hash)

Now, player O plays his move in cell #1, even though it's a bad one:

X O O
X . .
. . .

Again we'd like to calculate the Zobrist hash for the newly created board position. We use the old hash 74505 and combine it again per xor operation with the key of the new played cell (#1):

    74505 (old Zobrist hash)
XOR 10291 (cell #1 player 2)
---------
  = 68410 (new Zobrist hash)

Reusing the old hash to calculate a new one after a move was played makes it very efficient for traversing a game tree.

Moreover, it's quite easy do undo a move: we use the newly created Zobrist hash and combine it with key of the cell we'd like to undo. Let's undo player's 2 last move in cell #1 from above.

    68410 (new Zobrist hash)
XOR 10291 (cell #1 player 2)
---------
  = 74505 (Zobrist hash after undo last move)


Resulting position:
X . O
X . .
. . .

The Zobrist hash, 74505, equals the one in the beginning, before the move of player 2 was played.

Last but not least an example implementation in Kotlin for tic-tac-toe:

This post was originally published on Medium.