Currently, my engine only uses a depth-based replacement scheme for the transposition table, which has shown pretty significant speedups.
But I think that a replacement scheme only based on depth is problematic since entries with high depths risk never getting replaced even though they are outdated and irrelevant in the new part of the tree.
Therefore I am trying to create a replacement policy based partly on depth and partly on age since this would allow high-depth entries to be overwritten if they're old enough to not matter anymore. But the problem is that I can't seem to think of any good way of keeping track of an entry's age...
I have thought about just having a field with the time since epoch when it was inserted, but my function for measuring this is quite slow. Another possibility was to save the nodes searched when the entry is created and compare this to the current amount of nodes when deciding wether or not to replace, but this runs in to another problem: The engine is multithreaded, so locking all threads to get their node-count is also slow.
Do you have any suggestions as to how one can go about keeping track of an entry's age?
Any help is much appreciated!
Transposition table replacement scheme
Moderators: hgm, Rebel, chrisw
-
niel5946
- Posts: 174
- Joined: Thu Nov 26, 2020 10:06 am
- Full name: Niels Abildskov
-
hgm
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Transposition table replacement scheme
A common method is to have a search counter that you increment for every new search, and store its value of the current search in the age field of the hash entry whenever you probe or write it. The difference between the counter and the age field then tells you how many searches ago the entry was last referenced, and if that is too long ago, you can assume that it is no longer needed. I normally only keep entries that were referenced in the current or the previous search. That can already be done with a 2-bit counter, and finding two spare bits in the hash entry usually isn't a problem.
If you already want to use this during a single search, you can just increment the counter more frequently. E.g. when thread number 1's node counter is a multiple of 1 million.
To combat the problem of accumulating higher depths within a search I often use an 'undercut' replacement scheme: there I don't only allow a position to go into a depth-preferred slot when it has a depth >= the depth of the current occupant, but also when it has a depth exactly one lower. This is an intermediate between always-replace and depth-preferred, that eventually flushes out everything. But the higher the depth, the longer it will survive (statistically).
If you already want to use this during a single search, you can just increment the counter more frequently. E.g. when thread number 1's node counter is a multiple of 1 million.
To combat the problem of accumulating higher depths within a search I often use an 'undercut' replacement scheme: there I don't only allow a position to go into a depth-preferred slot when it has a depth >= the depth of the current occupant, but also when it has a depth exactly one lower. This is an intermediate between always-replace and depth-preferred, that eventually flushes out everything. But the higher the depth, the longer it will survive (statistically).