No Transposition table at all (base):
Code: Select all
info score cp 25 depth 1 seldepth 16 time 0 nodes 1598 nps 0 pv e2a6 b4c3 b2c3 e6d5
info score cp 25 depth 2 seldepth 16 time 0 nodes 3196 nps 0 pv e2a6 b4c3 b2c3 e6d5
info score cp 20 depth 3 seldepth 20 time 2 nodes 8556 nps 4278000 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 20 depth 4 seldepth 20 time 6 nodes 21644 nps 3607333 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 5 depth 5 seldepth 22 time 27 nodes 80147 nps 2968407 pv e2a6 b4c3 d2c3 e6d5 e4d5 f6d5
info score cp 15 depth 6 seldepth 22 time 136 nodes 313607 nps 2305934 pv e2a6 e6d5 c3d5 b6d5 a6b7 a8d8 b7d5 f6d5
info score cp 5 depth 7 seldepth 24 time 646 nodes 1415412 nps 2191040 pv e2a6 e6d5 c3d5 f6d5 e5c4 f7f5 c4b6 a7b6
info score cp -15 depth 8 seldepth 26 time 3758 nodes 7683695 nps 2044623 pv e2a6 e6d5 c3d5 f6d5 e5d3 f7f5 g2h3 f5e4
info score cp -40 depth 9 seldepth 27 time 21632 nodes 42283163 nps 1954658 pv d5e6 e7e6 e2a6 e6e5 g2h3 b4c3 d2c3 e5e6 c3f6 g7f6
info score cp -40 depth 10 seldepth 29 time 123303 nodes 242565118 nps 1967228 pv d5e6 e7e6 e2a6 e6e5 g2h3 b4c3 d2c3 e5e6 c3f6 g7f6
Code: Select all
info score cp 25 depth 1 seldepth 16 time 0 nodes 1598 nps 0 pv e2a6 b4c3 b2c3 e6d5
info score cp 25 depth 2 seldepth 16 time 0 nodes 3196 nps 0 pv e2a6 b4c3 b2c3 e6d5
info score cp 20 depth 3 seldepth 20 time 2 nodes 8556 nps 4278000 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 20 depth 4 seldepth 20 time 6 nodes 20598 nps 3433000 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 5 depth 5 seldepth 20 time 28 nodes 77862 nps 2780786 pv e2a6 b4c3 d2c3 e6d5 e4d5 f6d5
info score cp 15 depth 6 seldepth 22 time 141 nodes 302241 nps 2143553 hashfull 4 pv e2a6 e6d5 c3d5 b6d5 a6b7 a8d8 b7d5 f6d5
info score cp 5 depth 7 seldepth 24 time 656 nodes 1317243 nps 2007992 hashfull 15 pv e2a6 e6d5 c3d5 f6d5 e5c4 f7f5 c4b6 a7b6
info score cp -15 depth 8 seldepth 26 time 3956 nodes 7278234 nps 1839796 hashfull 101 pv e2a6 e6d5 c3d5 f6d5 e5d3 f7f5 g2h3 f5e4
info score cp -40 depth 9 seldepth 27 time 22663 nodes 39228707 nps 1730958 hashfull 419 pv d5e6 e7e6 e2a6 e6e5 g2h3 b4c3 d2c3 e5e6 c3f6 g7f6
info score cp -40 depth 10 seldepth 29 time 124545 nodes 222164456 nps 1783809 hashfull 949 pv d5e6 e7e6 e2a6 e6e5 g2h3 b4c3 d2c3 e5e6 c3f6 g7f6
depth 8: 7.68 M nodes => 7.28 M nodes
depth 9: 42.3 M nodes => 39.2 M nodes
depth 10: 242 M nodes => 222 M nodes
Thus the search tree does get smaller when using hash move sorting, but time to depth gets slightly slower... ?
Putting the TT move at the front of the move list does shrink the search tree, but it takes longer to search the remaining leaves. What does this mean? The search move causes the tree to be smaller, but more positions need to be searched to find the best move. Could this be improved with a better evaluation function, where less moves are equally as good?
256 MB Transposition table, TT cuts ONLY
Code: Select all
info score cp 25 depth 1 seldepth 16 time 0 nodes 1598 nps 0 pv e2a6 b4c3 b2c3 e6d5
info score cp 25 depth 2 seldepth 16 time 1 nodes 3196 nps 3196000 pv e2a6 b4c3 b2c3 e6d5
info score cp 20 depth 3 seldepth 20 time 2 nodes 8550 nps 4275000 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 20 depth 4 seldepth 20 time 6 nodes 19865 nps 3310833 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 5 depth 5 seldepth 22 time 25 nodes 72168 nps 2886720 pv e2a6 b4c3 d2c3 e6d5 e4d5 f6d5
info score cp 15 depth 6 seldepth 22 time 101 nodes 220990 nps 2188020 hashfull 2 pv e2a6 e6d5 c3d5 b6d5 a6b7 a8d8 b7d5 f6d5
info score cp 5 depth 7 seldepth 24 time 430 nodes 956490 nps 2224395 hashfull 9 pv e2a6 e6d5 c3d5 f6d5 e5c4 f7f5 c4b6 a7b6
info score cp -15 depth 8 seldepth 26 time 1888 nodes 3631306 nps 1923361 hashfull 54 pv e2a6 e6d5 c3d5 f6d5 e5d3 f7f5 g2h3 f5e4
info score cp -40 depth 9 seldepth 27 time 9551 nodes 17825410 nps 1866340 hashfull 274 pv d5e6 e7e6 e2a6 e6e5 g2h3 b4c3 d2c3 e5e6 c3f6 g7f6
info score cp -40 depth 10 seldepth 29 time 42794 nodes 77616507 nps 1813724 hashfull 883 pv d5e6 e7e6 e2a6 e6e5 g2h3 b4c3 d2c3 e5e6 c3f6 g7f6
depth 8: 7.68 M nodes => 3.63 M nodes, 3.7s => 1.9s
depth 9: 42.3 M nodes => 17.8 M nodes, 27.7s =? 9.6s
depth 10: 242 M nodes => 77m M nodes, 123.3s =? 42.8s
So search cuts by the TT provide a massive improvement, both in time to depth, and in shrinking the search tree.
256 MB Transposition table, TT Move sorting AND TT cuts:
Code: Select all
info score cp 25 depth 1 seldepth 16 time 0 nodes 1598 nps 0 pv e2a6 b4c3 b2c3 e6d5
info score cp 25 depth 2 seldepth 16 time 0 nodes 3196 nps 0 pv e2a6 b4c3 b2c3 e6d5
info score cp 20 depth 3 seldepth 20 time 2 nodes 8550 nps 4275000 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 20 depth 4 seldepth 20 time 6 nodes 18819 nps 3136500 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 5 depth 5 seldepth 20 time 24 nodes 69957 nps 2914875 pv e2a6 b4c3 d2c3 e6d5 e4d5 f6d5
info score cp 15 depth 6 seldepth 22 time 96 nodes 212014 nps 2208479 hashfull 2 pv e2a6 e6d5 c3d5 b6d5 a6b7 a8d8 b7d5 f6d5
info score cp 5 depth 7 seldepth 24 time 401 nodes 891698 nps 2223686 hashfull 8 pv e2a6 e6d5 c3d5 f6d5 e5c4 f7f5 c4b6 a7b6
info score cp -15 depth 8 seldepth 26 time 1753 nodes 3345849 nps 1908642 hashfull 51 pv e2a6 e6d5 c3d5 f6d5 e5d3 f7f5 g2h3 f5e4
info score cp -40 depth 9 seldepth 27 time 8765 nodes 16124441 nps 1839640 hashfull 255 pv d5e6 e7e6 e2a6 e6e5 g2h3 b4c3 d2c3 e5e6 c3f6 g7f6
info score cp -40 depth 10 seldepth 29 time 38004 nodes 68136673 nps 1792882 hashfull 850 pv d5e6 e7e6 e2a6 e6e5 g2h3 b4c3 d2c3 e5e6 c3f6 g7f6
Change compared to base:
depth 8: 7.68 M nodes => 3.35 M nodes, 3.7s => 1.75s
depth 9: 42.3 M nodes => 16.1 M nodes, 27.7s => 8.77s
depth 10: 242 M nodes => 68.1 M nodes, 123.3s => 38.0s
Then, compare TT cuts only, to TT cuts + TT Move sorting:
depth 8: 3.63 M nodes => 3.35 M nodes, 1.9s => 1.75s
depth 9: 17.8 M nodes => 16.1 M nodes, 9.6s => 8.77s
depth 10: 77 M nodes => 68.1 M nodes, 42.8s => 38.0s
In this case, TT Move sorting does provide a noticable, and fairly large benefit. It's not in the realm of what the TT cuts provide, but it's still around 10%.
It seems there are quite a few functions in chess engines that go together very well; in the QSearch thread by Lithander we noticed that PST's gave about 200 Elo gain, QSearch gave about 100 Elo gain, but BOTH TOGEHTER resulted in an (almost) 600 Elo gain. (For engines at the development stage of Rustic and MinimalChess.)
Here, TT Move sorting ONLY just gives a small reduction of the tree size, and is even negative for time to depth, but when you use it in combination with hash cuts, it does pull its weight and provides a noticable 10% speed gain. I assume, when the evaluation function improves (to the point where material and PST values get Texel tuned), Alpha/Beta will become more efficiënt, because less moves are equally good. And if A/B becomes more efficient, move sorting and TT cuts may have a larger impact.
Any thoughts?
PS: I was in doubt if the transposition table was actually working correctly because I'm not seeing 300-500 Elo points of improvement which was suggested by some people. I'm now assuming, seeing the actual results of the TT search against a non-TT search, that the transposition table IS working as it should, and a 300-500 Elo gain is just unrealistic. In self-play, and also against other engiens, I'm seeing a +/- 100 Elo improvement (error bars are +/- 50), while I haven't yet included mate scoring... so the engine is botching some games it should have won. I'll see how it pans out after I fix that.