zd3nik wrote:hgm wrote: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.