On transposition tables

This page collects some suggestions for engine developers for dealing with transposition tables.

Initialization

For many chess engines, transposition table hash initialization is by far the most expensive operation in engine startup. This is especially true with big hash sizes.

Deferred initialization

The first problem with some engines, including Stockfish at the time of writing, is that they initialize the hash table multiple times on start-up. Let's take a look what SF does here: (commit 353e20674b2019094059caaa3567e9a44abe9cd1)

% ./stockfish
Resize 16 MB     <-- default hash at initialization
Clear 1 threads
Clear 1 threads
uci
...
setoption name Hash value 32768
Resize 32768 MB  <-- resize and clear with 1 thread
Clear 1 threads
setoption name Threads value 12
Resize 32768 MB  <-- resize and clear with 12 threads
Clear 12 threads
isready          <-- this is a no-op, other than printing out readyok
readyok
ucinewgame
Clear 12 threads
isready          <-- this is a no-op, other than printing out readyok
readyok
go depth 1
info depth 1 seldepth 1 multipv 1 score cp 110 nodes 251 nps 83666 tbhits 0 time 3 pv e2e3
bestmove e2e3 ponder b7b6

To avoid redundant resizes and clears, the obvious solution here would be to defer initialization until isready is sent. However, isready may be sometimes omitted, and it wouldn't be good if the search is started before initialization. So, initialization should also be triggered by any command that could potentially start a search.

The other issue is that there are often multiple UCI commands triggering a hash clear in the engine launch sequence. To avoid this, state tracking is needed for the hash table.

Ideally:

% ./stockfish    <-- default hash is 16 MB, but we don't initialize yet
uci
...
setoption name Hash value 32768
setoption name Threads value 12
isready          <-- this needs to trigger the initialization
Resize 32768 MB  <-- allocate the memory
Clear 12 threads <-- clear with 12 threads; hash state is clean
readyok
ucinewgame       <-- clear request on clean hash is redundant, so no need to actually clear
isready          <-- nothing to do here
readyok
go depth 1       <-- mark the hash state dirty here
info depth 1 seldepth 1 multipv 1 score cp 110 nodes 251 nps 83666 tbhits 0 time 3 pv e2e3
bestmove e2e3 ponder b7b6
ucinewgame       <-- clear request on dirty hash is triggers actual clear, mark the hash to be cleared
isready
Clear 12 threads <-- clear with 12 threads; hash state is clean again
readyok

Optimizing the initialization sequence

There is a somewhat notable difference on when