Due to the complexity of this topic I have divided this post into two entries. This article will discuss the Transposition Table and Zobrist Hashing techniques with no code samples. The second part in the series will discuss the code used in my chess engine.
An Alpha Beta search will often have to consider the same position several times. This occurs due to the fact that in chess there are many ways to reach the same piece arrangement. For this reason most chess engines implement a Transposition Table that stores previously searched positions and evaluations.
The problems
The first problem is that although same chess positions do often re-occur during an alpha beta search, we can only count on having this happen somewhere between 15%-20%. We can’t know which positions these will be ahead of time so for every 100 entries we save in our Transposition Table we might only use 20 entries. Hence whatever Transposition Table scheme we choose, it has to be very efficient because we will be storing and searching more useless entries than useful ones.
In a perfect world we would have the ability to simply save every single node we search in our Transposition Table. Unfortunately this is simply not practical. The memory requirements for this scheme would be higher than most computers can accommodate. Furthermore the time wasted on searching such a large table would outweigh any time saving benefits. So we have to accept that our Transposition Table is limited in size will not store all the nodes we search.
Implementation
First we need to figure out how uniquely identify each position we come across. This has to be extremely efficient since we will have to do this for every node in our search. Simply converting the chess board to a string of values like FEN is far too slow.
Zobrist Hashing
Fortunately for us a process for indexing game positions called Zobrist Hashing has already been invented by professor at the University of Wisconsin by the name of Albert Zobrist.
The Zobrist Hash uniquely representing our chess board will be a 64 bit variable. In C# we can implement this as an unsigned long (ulong). We calculate a chess boards Zobrist Hash using the following steps
1. Generate an array of 12 * 64 Pseudo Random numbers representing each chess piece type on each of the 64 positions on a chess board. You only do this once at when your chess engine initiates. This will give you a single hash value for every single chess piece for every single position on the board. You will have to elect which portions of the array represent which chess piece. Let’s say you choose to have the first 64 entries in your array represent the white pawn. So the 9th value in your array will be White Pawns A2 square etc.
2. For each chess piece on the chess board XOR its positions random number against the current Zobrist hash value. So a white pawn on B2 might be the 10th value in the array.
This is easy enough, however we don’t necessary want to calculate the Zobrist hash from scratch each time we make a move. That would be very slow and would make the whole exercise futile. For this reason each time a move is made on our chess board, whether during game play or alpha beta search we simply update the Zobrist Hash by:
1. XOR the chess pieces previous positions random number against the current Zobrist hash value, this erases the chess piece from our hash.
2. XOR the chess pieces new positions random number against the current Zobrist hash value adding the chess piece back to its new position.
A bit about the XOR operator:
If you don’t understand what I mean by XOR in the above paragraphs you may want to read this:
XOR or Exclusive Or is one of the standard bit operators available to you in most programming languages. By bit operator I mean it allows you to manipulate the individual bits in a value. If you are not sure what that means, you might need to Google this first. The one nice side effect of the XOR operator is that if you XOR a value 2 times by the same value it will return to its original value.
For example
1110 XOR 1001 = 0111
0111 XOR 1001 = 1110
In order to add and remove chess pieces from our hash we will be using the XOR operator to add the chess piece to a position and then use the XOR again to erase it once it moves. For example if we XOR the Zobrist Hash representing our chess board against the 64 bit number representing a white pawn on A2 it would be like adding the pawn to the chess board on A2. If we do it again we remove or erase the pawn from A2. We can than XOR the hash against the 64 bit value representing a white pawn on A3. The last 2 operations would essentially move the white pawn from A2 to A3.
Collisions
Right about now you might have noticed that a 64bit value is not large enough to represent every single possible chess position. So using the above scheme it is possible to have 2 different chess positions evaluate to the same 64 bit hash value. This is called a collision and no matter how you implement this, you will always have a small chance of a collision. The key here is to minimise the chance of a collision down to a small enough value so that the speed gain you get from having a transposition table (and perhaps constantly deeper search) outweighs the negative effect of the possibility of a collision. In most chess circles a 64 bit value is considered to be large enough to make collisions not a practical problem.
Transposition Table Contents
So what goes in a transposition table entry? Here are the items included in my Transposition Table:
Hash: This is a Zobrist Hash representing the chess position
Depth: The depth remaining in the alpha beta search. So depth 5 would mean the score is recorded for a 5 ply search. This can also be referred to as the Depth of the Search Tree.
Score: The evaluation score for the position.
Ancient: Boolean flag, if false the node will not be replaced with a newer entry.
Node Type: There are 3 node types, Exact, Alpha and Beta. Exact means this is an exact score for the tree. However in the events that an alpha beta cut-off occurs we can’t use the score as an exact score. An Alpha Node Type means the value of the node was at most equal to Score. The Beta Node Type means the value is at leastequal to score.
Replacement Schemes
Since your Transposition Table can’t hold all the moves searched in a game you will have to start replacing your entries fairly soon. In the same time you don’t simply want to replace all entries regardless of their usefulness. For this reason in the event that I find an entry that is useful (was used in a lookup), I set a Boolean flag Ancient to false, meaning doesn’t replace. This way you always replace entries that are unused and keep the ones that were historically useful. To prevent your table from filling up with Ancient nodes from 10 turns ago, the Ancient flag gets set to true for every entry after every search.
Table Lookup
The last problem we have to find is how to we quickly search a Zobrist Table. We can’t just do a for loop. This would be slow. The trick is actually in how we store the entries in the first place. Rather than simply adding an entry in the order we received them we calculate the entry index as follows:
Table Entry Index = Hash mod TableSize
This way when we search the table to see if a certain Hash exists we know there is only one place it could be stored Table[Hash mod TableSize]
That’s it for this article on the Transposition Table. Stay tuned for the next article that will discuss C# implementation.
Want to skip to the end, download the full chess engine source code on GitHub