Transposition table is a lookup table which is used to cache negamax search results when searching for best move in a chess engine. In the previous post we looked at transposition tables and their use in a negamax search in the context of a chess engine. Transposition tables fine when used in a linear negamax search but what about parallelised negamax search? Anyone who has done basic multithreaded programming will be able to see potential problems with using a shared transposition table in a parallelised negamax search. The solution lies in the lockless transposition table.
This post discusses such a lockless transposition table. It is based upon this article by Robert Hyatt, author of the famous Crafty chess engine. The article describes lockless transposition tables in more detail and reading it will. However, if you’ve been following this series of posts or if you want to get a different explanation of lockless transposition tables it would make sense to continue reading this post.
A word about Zobrist hashing
In order to understand the implementation of a lockless transposition table, we need to have a basic understanding of what is called Zobrist hashing. Zobrist hash is a 64-bit hash which represents a chess board position. The lockless hash table will use Zorist hash values as its keys.
Like any other hash, Zobrist hash has following two properties:
– there is a low probability that any two board positions will have the same hash, and
– it is very hard or impossible to derive a board position from a given hash value
It has one more property which makes it so useful for chess engines. Zobrist hashes of two similar chess positions will be very different. Since the positions that you can move to from the current board position will be similar, their hashes will be very different. Why exctly this property helps will be clear towards the end of this post, once we have covered transposition table implementation.
Zobrist hashes are also lightweight and fast to generate. They are used with a particular board representation called bitboard. Many endgame table-bases, which are databases of solved end games use zobrist hashing as well.
Idea behind Lockless Transposition Table
The lockless transposition table we are talking about is a hash table where the key and value are 64-bit word each. In C it will be unsigned long long. It is different in other languages. Now on a 64-bit maching reading or writing a 64-bit word is atomic operation. Therefore when you read a 64-bit key or value from the hash table, it will either be the existing item or a new one. But it won’t be a partially written item. That is the basic idea behind the lockless transposition table. There are two problems with this approach which we will address in the rest of the post.
1. Since reading the key and value are two separate operations, how do we ensure that the value is correct one, i.e. the one corresponding to the key that we read? Afterall, the value might have been overwritten after we read the key but before we read value.
2. How do we store details about board position, like score, depth searched etc, in a 64-bit word?
Ensuring that key and value correspond
First we will present the solution to this problem and then see why it works.
When storing the hash and its corresponding value we will alter the key as follows:
key = hash ^ value
So we will XOR the hash with value and use the result as key. Value will be the same as it was. When we come to retrieve the key-value pair, we will first XOR the value with key and then compare the result with the hash that we were searching for. If the two match then it means the value corresponds to the hash key we were looking for. If they don’t match then the key-value pair was corrupt and we ignore the entry.
So let’s see why this works. XOR is a reversible operation. XORing twice with the same value will give us the original value, i.e.
x ^ y ^ y = x.
What we are doing is XORing the hash with the value once to get our key. Then we XOR that key again with the value. If the value is the same that we originally XORed the hash with, we will get the correct hash, if not, then we will get some other result.
Storing details in 64-bits
What you want to store in the 64-bit value word will depend upon where you want to use the transposition table. Here we will present a simple way of storing values relevant to chess search. Remember that this is a very basic composition of the value word. In a real chess engine you’ll use different composition.
In our discussion, three things have stood out to be the most relevant:
1. Score associated with that position
2. Depth searched which resulted in the score
3. Best move in that position
The score can be packed into 32 bits, giving us 32-bit signed integer. Depth will take five bits more to give us maximum searchable depth of 32 levels which is more than enough for most engines. Best move can be represented by eight bits giving us 256 possible moves for any given position. Maximum number of legal moves in a chess position have been found to be 218 (see http://chessprogramming.wikispaces.com/Encoding+Moves#MoveIndex). So a byte should be enough.
When using a transposition table like the one described here, we are constrained by size in memory. That means that we will have to replace older entries by newer ones which is not necessarily a bad thing. However, one may want to consider a replacement strategy to improve the chances of a hit in the transposition table. A simple way to store entries is to modulo the key with the maximum number of entries (i.e. capacity) that the transposition table can hold. This happens to be a common way to store entries in transposition tables. Here we can also see why the fact that Zobrist hashes for two similar positions are very different is helpful. When we generate positions from a given position, they tend to be similar to the one we currently have. So when we store the generated positions in our hash table, they will more likely end up in indexes farther apart from each other, decreasing the chances of overwriting each other. Thus the newer more similar positions are more likely to stay cached in the table. This isa good thing because more recent positions that repeat themselves more frequently.