Best practices for transposition tables

[Sven]

I think in middlegame positions the biggest gain you get from a TT is the move ordering improvement. The saving through transpositions is not the most important part there.

I've just re-instated my old transposition table implementation from a year ago, which was written explicitly for perft. It only stores leaf node counts (and zobrist and depth), so I'll have to change the data structures to be able to save the information needed to use the table for playing games, but its a (working) start.

In Jumbo, which is written in C++, I use templates to model the different hash table use cases. There is a base class "HashTable" which has basically one template parameter "E", there are three hash element data structures "TTHashElement", "PerftHashElement", and "PawnHashElement", and finally there are these derived classes:

Code: Select all

class TTHash    : public class HashTable<TTHashElement,    ...> {...}
class PerftHash : public class HashTable<PerftHashElement, ...> {...}
class PawnHash  : public class HashTable<PawnHashElement,  ...> {...}

where ", ...>" is related to the number of slots per bucket which may differ depending on the size of one hash element. Most of the implementation is in the base class "HashTable", only those small pieces of code that need to know the details of a single hash element (i.e. a store() method that takes some parameters depending on the hash element type) are implemented by the derived class. Of course all methods are inlined so that there will be no function call overhead. It works like a charm, is flexible enough for me, and greatly simplifies all parts of the code that use hash tables.

[mvanthoor]

In Jumbo, which is written in C++, I use templates to model the different hash table use cases.

Rust doesn’t have templates or inheritance. It uses generics an traits (interfaces).

I intend to do what you did, but I’ll have to look up how it works in Rust.

[Nomis]

Sure, I never said anything about what would cause the speedup. But not having a TT move means you would have to get it through IDD. That obviously takes some extra time, but not a huge factor, as the pilot search takes only a small fraction of the time needed for the full-depth search.

Regarding that, what is there to gain by adding IID to an engine that has a TT ?
I'd expect the "normal" iterative deepening to fill the TT with best moves for all nodes.
Surely evictions from the TT are not enough to make IID significantly useful ? What am I missing ?

[hgm]

Sometimes on deeper search a move might not turn out as good as it seemed at lower depth. Then the engine might have to look for alternatives in in branches it has never visited before. It wouldn't find anything in the TT for the entire subtree, and would plunge blindly ahead to full depth on many moves that could have easily (i.e. with very shallow search) have been seen to be no good before it finds the best one.

E.g. suppose in the root move A in not the best up to 10 ply, because it is consistently refuted by reply B (which is in the TT). Now at 11 ply B doesn't refute A anymore, but fails low. Perhaps because it runs into some deep tactics, or simply because the PV move in the root dropped a bit in score. So no beta cutoff this time, and you have to search alternatives B', B", ... for B to see whether they can refute A instead. (And if they cannot, then perhaps A now really is the best move in the root.) But B', B" have never been searched yet, because from 1 ply on B has always done the job, and cut them off.

[Nomis]

Oh, I see. Thanks a lot.