Transposition table replacement strategies

[zd3nik]

Root move counter idea seems bad. You do iteration N and move A is best. At N+1 A is replaced by B. You REALLY want to overwrite A's entry as you search other moves, just because it was bumped down to the second slot?

I don't see the reasoning behind that. Much more logical is to use an age replacement, so that positions from previous searches (not previous iterations) are replaced first. If that fails, replace shallowest draft.

I think I may have poorly communicated what I'm doing, again. The move counter at root isn't reset with each depth iteration or advance to the next move in the root search, it gets incremented after each move is made in the actual game. So it is in essence the "search number". E.g. The first search of the game will have mcount 1, the second search will have mcount 2, etc. So whatever is stored in the TT for position A for search #1 would be considered older than any search #2 results - and search #2 doesn't occur until a move has been played in the actual game.

I was under the impression that mcount at the root of the search is typically what is used as an age counter. Could you please describe what you mean by "age".

Thanks,
STC

[hgm]

Note, however, that this sort of breaks the engine for interactive analysis, where it is very important that the scores of already deeply analyzed side branches is stillpresent in the TT when you return to the position they branched off, after analyzing another line. When doing such analysis I discovered that it was really essential the engine considers the entire session as a single search, and only starts incrementing the search count when you leave analysis mode.

[bob]

Note, however, that this sort of breaks the engine for interactive analysis, where it is very important that the scores of already deeply analyzed side branches is stillpresent in the TT when you return to the position they branched off, after analyzing another line. When doing such analysis I discovered that it was really essential the engine considers the entire session as a single search, and only starts incrementing the search count when you leave analysis mode.

What about the effect of the search getting slower and slower as you analyze more? At least the always replace will zap the shallowest draft, but still???

[bob]

Root move counter idea seems bad. You do iteration N and move A is best. At N+1 A is replaced by B. You REALLY want to overwrite A's entry as you search other moves, just because it was bumped down to the second slot?

I don't see the reasoning behind that. Much more logical is to use an age replacement, so that positions from previous searches (not previous iterations) are replaced first. If that fails, replace shallowest draft.

I think I may have poorly communicated what I'm doing, again. The move counter at root isn't reset with each depth iteration or advance to the next move in the root search, it gets incremented after each move is made in the actual game. So it is in essence the "search number". E.g. The first search of the game will have mcount 1, the second search will have mcount 2, etc. So whatever is stored in the TT for position A for search #1 would be considered older than any search #2 results - and search #2 doesn't occur until a move has been played in the actual game.

I was under the impression that mcount at the root of the search is typically what is used as an age counter. Could you please describe what you mean by "age".

Thanks,
STC

Most increment age at the beginning of a NEW search, not a new iteration. Store this in the table. If you need to replace, replace the entry that doesn't match the current age (it is from an old search).

[hgm]

What about the effect of the search getting slower and slower as you analyze more? At least the always replace will zap the shallowest draft, but still???

If it starts to be unbearable, you can always clear the table. Or, less drastically, leave analysis mode and re-enter it. To minimize the damage you could do that in the 'root' of your own analysis excursions, so that the deepest parts of all your previous analysis will be quickly reconfirmed as belonging in the new search as well.

Perhaps the usual 'shallowest-of-4' replacement is not ideal in this case, as it will eventually throw you back on just 25% of the table. An alternative could be to never overwrite the deepest draft of a bucket in analysis mode, even if it is aged, but apply normal aging to other entries. That can never poison more than 25% of the table with stale entries, and still leaves some depth-preferred capability in the remaining 75%. The question is how to eventually get rid of this 25% when you want to start another analysis. You really should have two search identifiers, one the usual search number, one the analysis number, which only increments when you enter analyze mode. The deepest entry of a bucket would use the analyzis number to judge aging, other entries the search number.

Most increment age at the beginning of a NEW search, not a new iteration. Store this in the table. If you need to replace, replace the entry that doesn't match the current age (it is from an old search).

That is a bit risky, because you could be replacing an entry that would have been needed in the current search, but just was not visited yet. So I usually protect entries from the previous search as well:

if((unsigned int) searchNumber - hash->age > 1) Replace();

[bob]

What about the effect of the search getting slower and slower as you analyze more? At least the always replace will zap the shallowest draft, but still???

If it starts to be unbearable, you can always clear the table. Or, less drastically, leave analysis mode and re-enter it. To minimize the damage you could do that in the 'root' of your own analysis excursions, so that the deepest parts of all your previous analysis will be quickly reconfirmed as belonging in the new search as well.

Perhaps the usual 'shallowest-of-4' replacement is not ideal in this case, as it will eventually throw you back on just 25% of the table. An alternative could be to never overwrite the deepest draft of a bucket in analysis mode, even if it is aged, but apply normal aging to other entries. That can never poison more than 25% of the table with stale entries, and still leaves some depth-preferred capability in the remaining 75%. The question is how to eventually get rid of this 25% when you want to start another analysis. You really should have two search identifiers, one the usual search number, one the analysis number, which only increments when you enter analyze mode. The deepest entry of a bucket would use the analyzis number to judge aging, other entries the search number.

Most increment age at the beginning of a NEW search, not a new iteration. Store this in the table. If you need to replace, replace the entry that doesn't match the current age (it is from an old search).

That is a bit risky, because you could be replacing an entry that would have been needed in the current search, but just was not visited yet. So I usually protect entries from the previous search as well:

if((unsigned int) searchNumber - hash->age > 1) Replace();

I was doing that until fairly recently, but testing suggested just overwriting anything old worked better, at least for the way I am hashing with 4 entry buckets...

[zd3nik]

Root move counter idea seems bad. You do iteration N and move A is best. At N+1 A is replaced by B. You REALLY want to overwrite A's entry as you search other moves, just because it was bumped down to the second slot?

I don't see the reasoning behind that. Much more logical is to use an age replacement, so that positions from previous searches (not previous iterations) are replaced first. If that fails, replace shallowest draft.

I think I may have poorly communicated what I'm doing, again. The move counter at root isn't reset with each depth iteration or advance to the next move in the root search, it gets incremented after each move is made in the actual game. So it is in essence the "search number". E.g. The first search of the game will have mcount 1, the second search will have mcount 2, etc. So whatever is stored in the TT for position A for search #1 would be considered older than any search #2 results - and search #2 doesn't occur until a move has been played in the actual game.

I was under the impression that mcount at the root of the search is typically what is used as an age counter. Could you please describe what you mean by "age".

Thanks,
STC

Most increment age at the beginning of a NEW search, not a new iteration. Store this in the table. If you need to replace, replace the entry that doesn't match the current age (it is from an old search).

That's what I'm trying to tell you I'm doing. MCount change at root means it's a new search, not a new iteration.

[zd3nik]

To see any effect of replacement strategy, you must work under conditions where a lot of replacement goes on. When there is nothing to replace it does not matter much how you do it. In particular, there isn't much replacement when the search tree is not at least 10x larger than the table. So if you do 1-min games (~1 sec/move) and your engine does 1Mnps, you will only start to see an effect when the hash table has fewer than 100K entries (i.e. < 1.6MB).

Good point.

The testing I have done so far includes playing gauntlets with TT size set to 512MB and time control set to 2 min +1 sec inc or 1 min + 0.5 sec inc. Plus some EPD testing with short time limits.

I will try lowering the TT size and adjusting the time controls in my testing. Perhaps then I will see some difference.

Thanks,
STC

So, this was definitely revealing. And now I'm wondering if it means I have other issues with my transposition table implementation.

Here are EPD test results using the Win At Chess epd and a 50 position epd file with a broad mix of position types (mostly middlegame):

No TT:

Code: Select all

WAC.epd
info string --- Passed    286 passed (95.3333%)
info string --- Time      264121 (880.403 avg)
info string --- Nodes     580112812, 2196.39 KNodes/sec
info string --- Depth     7 min, 12 avg, 100 max
info string --- SelDepth  16 min, 25 avg, 100 max
info string 425082 searches, 1502204 qsearches (77.944%)
info string 832091 late moves, 10985 increase alpha (1.32017%), 10926 confirmed (99.4629%)

50_positions.epd
info string --- Passed    28 passed (56%)
info string --- Time      245029 (4900.58 avg)
info string --- Nodes     492502120, 2009.97 KNodes/sec
info string --- Depth     9 min, 10 avg, 16 max
info string --- SelDepth  20 min, 27 avg, 33 max
info string 1600459 searches, 8056447 qsearches (83.4268%)
info string 3862995 late moves, 61083 increase alpha (1.58123%), 60861 confirmed (99.6366%)

One Megabyte TT (simple replacement strategy):

Code: Select all

WAC.epd
info string --- Passed    289 passed (96.3333%)
info string --- Time      245126 (817.087 avg)
info string --- Nodes     573762174, 2340.68 KNodes/sec
info string --- Depth     7 min, 23 avg, 100 max
info string --- SelDepth  9 min, 35 avg, 100 max
info string 1473023 TT gets, 175835 TT hits (11.937%)
info string 699712 searches, 1206475 qsearches (63.2926%)
info string 987513 late moves, 7563 increase alpha (0.765863%), 7502 confirmed (99.1934%)

50_positions.epd
info string --- Passed    37 passed (74%)
info string --- Time      245015 (4900.3 avg)
info string --- Nodes     519385577, 2119.81 KNodes/sec
info string --- Depth     10 min, 12 avg, 26 max
info string --- SelDepth  11 min, 29 avg, 37 max
info string 9271342 TT gets, 1003766 TT hits (10.8265%)
info string 2461353 searches, 7722679 qsearches (75.8313%)
info string 4604742 late moves, 49639 increase alpha (1.078%), 48953 confirmed (98.618%)

One Megabyte TT (4 entries per hash slot, 3 phase replacement strategy):

Code: Select all

WAC.epd
info string --- Passed    290 passed (96.6667%)
info string --- Time      244888 (816.293 avg)
info string --- Nodes     545538142, 2227.7 KNodes/sec
info string --- Depth     8 min, 23 avg, 100 max
info string --- SelDepth  9 min, 35 avg, 100 max
info string 1377868 TT gets, 175313 TT hits (12.7235%)
info string 684990 searches, 1127430 qsearches (62.2058%)
info string 974422 late moves, 6526 increase alpha (0.66973%), 6463 confirmed (99.0346%)

50_positions.epd
info string --- Passed    40 passed (80%)
info string --- Time      245016 (4900.32 avg)
info string --- Nodes     489847050, 1999.24 KNodes/sec
info string --- Depth     10 min, 13 avg, 28 max
info string --- SelDepth  11 min, 28 avg, 43 max
info string 8599818 TT gets, 785635 TT hits (9.13548%)
info string 2308523 searches, 7296322 qsearches (75.965%)
info string 4260050 late moves, 43760 increase alpha (1.02722%), 43519 confirmed (99.4493%)

So the 3-phase replacement strategy shows some small advantage over the simple replacement strategy when TT space is limited.

Now here's the part that makes me really worry that something may be wrong with my TT implementation in general:

512MB TT (4 entries per hash slot, 3 phase replacement strategy):

Code: Select all

WAC.epd
info string --- Passed    290 passed (96.6667%)
info string --- Time      245156 (817.187 avg)
info string --- Nodes     466565741, 1903.14 KNodes/sec
info string --- Depth     7 min, 23 avg, 100 max
info string --- SelDepth  9 min, 35 avg, 100 max
info string 1147217 TT gets, 169928 TT hits (14.8122%)
info string 610348 searches, 939706 qsearches (60.6241%)
info string 872304 late moves, 5382 increase alpha (0.616987%), 5328 confirmed (98.9967%)

50_positions.epd
info string --- Passed    40 passed (80%)
info string --- Time      245012 (4900.24 avg)
info string --- Nodes     430821524, 1758.37 KNodes/sec
info string --- Depth     10 min, 13 avg, 35 max
info string --- SelDepth  12 min, 28 avg, 51 max
info string 7345764 TT gets, 1096999 TT hits (14.9338%)
info string 2357667 searches, 6089815 qsearches (72.0903%)
info string 4121586 late moves, 35468 increase alpha (0.860543%), 35264 confirmed (99.4248%)

Increasing the TT size by a factor 512 yields insignificant differences. Avg depth stays the basically same. % of nodes spent in QSearch only went down a couple percentage points (Qnodes in my engine do gets from the TT, but don't store anything to TT, so they should be able to get some early cutoffs from the TT). And percentage of late moves that are better than the 1st move is hardly effected. One of the 2 primary things a TT is supposed to do is increase the likelyhood of searching the best move first. So if nothing else I would expect a bigger drop in late move alpha increases.

TT hit rate did go up a little, but not as much as I would expect from a x512 increase in TT size.

So I'm wondering if these numbers are way outside the norm. Is 9-14% hit rate normal? (I think someone on this forum once said they get about 27%). Are my late move alpha increase numbers anywhere near the norm? Do ANY of these figures jump out as being off-the-mark?

Sorry for posting such a broad set of questions. But I'm at a loss as to why changing the TT size so dramatically would have so little effect. I'm not even sure where to begin debugging.

[Evert]

If increasing the table-size doesn't make any real difference, the pressure on the table is low. Try reducing the size of the table instead.

A hit-rate of 10-15% doesn't sound very strange to me, although 20% also rings a bell. I suspect that it depends very much on the positions you look at.

[zd3nik]

If increasing the table-size doesn't make any real difference, the pressure on the table is low. Try reducing the size of the table instead.

A hit-rate of 10-15% doesn't sound very strange to me, although 20% also rings a bell. I suspect that it depends very much on the positions you look at.

Go smaller than 1 MB? The tests I posted are with TT sizes of 0MB, 1MB, and 512MB. And there's basically no substantial diff between 1MB and 512MB.

I'm not trying to complain, just wanting to know if the kind of effects (or lack thereof) I'm seeing are common/expected.