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