6/17/2013

Hashing schemes

Eventually, I will have to implement a transposition table for the chess engine. That requires accessing global memory during the search. This, however, should not be a problem if I do not use the transposition table at the leaf nodes or in the queiscence search. Transpositions occur most often at the deepest branches. However, the subtrees are smallest near the leaf nodes. Most benefit comes from nodes that are roots of larger subtrees. And fortunately, testing the transposition entries is always cheaper than move generation which involves global memory writes.

I have been thinking about the best way to implement hashing. Many chess engines use Zobrist keys for hashing. They require serializing the bitboards and using a table of random values for each piece and position. Although simple and effective, I do not like this approach, because it requires lookup tables (about 6 kb), which I have tried to eliminate. I would like to find an alternative hashing scheme. It does not matter if the hashing function is more complicated as far as it does not consume the precious memory.

The good thing about Zobrist keys is that each square and each piece has an equal contribution to the final hash value and positions are spread uniformly in the hash table. I would like to achieve similar results with less random numbers which could be hard coded as constants in the hashing function. I could interleave the hash key calculation with the global memory writes, so I would get the keys for free.

2 comments:

  1. hashing will be useful also for threefold-repetition-detection.

    --
    Srdja

    ReplyDelete
  2. Can you rewrite Stockfish/cutechess-cli to run on CUDA GPU-s? I think that many short games on 1 thread can run nicely on CUDA (for the purpose of testing new patches).

    ReplyDelete