Computer Othello, Part 4: Trials and Transposition Tables

By the time I implemented transposition tables for my computer player in Othello, I'd finished most of the components of what's required for a decent Othello computer player. I didn't really need to add a transposition table, but I really wanted to understand and implement all the aspects of a computer player for these sorts of games.

A transposition table is used to help speed-up a depth-first search. It does this by keeping track of game states that it has already searched. Along with the game state, it records the value it found for that state in the evaluation function. (Therefore, a suitable data-type for a transposition table in C# is a Dictionary<gamestate,float>. GameState overrides the GetHashCode method to provide an unique as possible hash of the game state. The float holds the value from the evaluation function.) If the search finds the same game state again (via a different path), it uses the value in the transposition table rather than re-calculating it. This saves time.

Intuitively, I wouldn't have thought Othello would have many ways in which different sequences of plays could result in the same game state. Any reading about computer Othello says otherwise, however. In practice, I managed to wipe a couple seconds off a search by using a transposition table.

When I began writing my transposition table I looked for a good way to hash a game state. I found a description of the Zobrist hash:

One useful method for hashing positions in games like Othello and Chess is Zobrist hashing [12]. A Zobrist hash consists of an XOR sum of several bitstrings. For each square on the board, there is one randomly generated bitstring representing a black piece and another representing a white piece. A position's Zobrist hash is formed by XORing together the appropriate bitstrings. The primary benefit of Zobrist hashing is that it can be incrementally updated very quickly by XORing it with the bitstrings for the pieces that have changed. Zobrist hashes also have the advantage of uniform distribution. (Applications of Arti ficial Intelligence and Machine Learning in Othello)

I implemented a Zobrist Hash for Othello, created a dictionary of type Dictionary<ulong,float>, then wondered why I was getting so many bad results. The problem? When you add a key to a dictionary it'll call GetHashCode on the object to retrieve the hash. What happens when you add a hash as a key to a dictionary? The same thing. I was double hashing! Not only that, I was going from a 64-bit Zobrist hash to a 32-bit .NET hash. I was burning time in creating the hash as well as losing information and most likely increasing the number of collisions between different game states. All pretty ugly stuff. The solution, outlined above, was very simple: ditch the Zobrist hash, override the GameState GetHashCode to have:

        public override int GetHashCode()
        {
            return (PlayerPieces | OpponentPieces).GetHashCode();
        }

and change the dictionary to have GameState as the key. The result isn't as fast as if I had implemented my own type of hashtable with my own hash type, but it was a lot easier to do.

In the end, adding a transposition table to my game was relatively easy to do, though I took a long and unnecessary detour to achieve it.