Hash move ordering vs. Hash cuts: savings in number of nodes visited

[mvanthoor]

Hi,

It seems my transposition table works perfectly fine, but the numbers on saved number of nodes is different than what I expected. I'd like to know if there's an answer to this, or that it depends on the engine. I have implemented a transposition table, and also sort on the hash move. These are the results in the KiwiPete position:

Hash table in use, but with both hash move ordering and hash cuts disabled (the table always returns "nothing found" for this test).

Code: Select all

info score cp 25 depth 1 seldepth 16 time 0 nodes 4271 nps 0 pv e2a6 b4c3 b2c3 e6d5
info score cp 25 depth 2 seldepth 16 time 0 nodes 8576 nps 0 pv e2a6 b4c3 b2c3 e6d5
info score cp 20 depth 3 seldepth 20 time 2 nodes 23332 nps 11666000 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 20 depth 4 seldepth 20 time 7 nodes 62976 nps 8996571 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 5 depth 5 seldepth 22 time 28 nodes 257843 nps 9208679 hashfull 1 pv e2a6 b4c3 d2c3 e6d5 e4d5 f6d5
info score cp 15 depth 6 seldepth 22 time 140 nodes 1116882 nps 7977729 hashfull 16 pv e2a6 e6d5 c3d5 b6d5 a6b7 a8d8 b7d5 f6d5
info score cp 5 depth 7 seldepth 24 time 679 nodes 5635001 nps 8298971 hashfull 62 pv e2a6 e6d5 c3d5 f6d5 e5c4 f7f5 c4b6 a7b6
info score cp -15 depth 8 seldepth 26 time 4006 nodes 28315376 nps 7068242 hashfull 371 pv e2a6 e6d5 c3d5 f6d5 e5d3 f7f5 g2h3 f5e4
info score cp -40 depth 9 seldepth 27 time 23292 nodes 167732837 nps 7201307 hashfull 923 pv d5e6 e7e6 e2a6 e6e5 g2h3 b4c3 d2c3 e5e6 c3f6 g7f6

Only hash move sorting:

Code: Select all

info score cp 25 depth 1 seldepth 16 time 0 nodes 4271 nps 0 pv e2a6 b4c3 b2c3 e6d5
info score cp 25 depth 2 seldepth 16 time 1 nodes 8576 nps 8576000 pv e2a6 b4c3 b2c3 e6d5
info score cp 20 depth 3 seldepth 20 time 2 nodes 23332 nps 11666000 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 20 depth 4 seldepth 20 time 6 nodes 60738 nps 10123000 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 5 depth 5 seldepth 20 time 28 nodes 255524 nps 9125857 hashfull 1 pv e2a6 b4c3 d2c3 e6d5 e4d5 f6d5
info score cp 15 depth 6 seldepth 22 time 138 nodes 1090083 nps 7899152 hashfull 16 pv e2a6 e6d5 c3d5 b6d5 a6b7 a8d8 b7d5 f6d5
info score cp 5 depth 7 seldepth 24 time 643 nodes 5377310 nps 8362846 hashfull 59 pv e2a6 e6d5 c3d5 f6d5 e5c4 f7f5 c4b6 a7b6
info score cp -15 depth 8 seldepth 26 time 3854 nodes 27042610 nps 7016764 hashfull 359 pv e2a6 e6d5 c3d5 f6d5 e5d3 f7f5 g2h3 f5e4
info score cp -40 depth 9 seldepth 27 time 22048 nodes 158657343 nps 7195997 hashfull 909 pv d5e6 e7e6 e2a6 e6e5 g2h3 b4c3 d2c3 e5e6 c3f6 g7f6

Hash move sorting AND hash cuts:

Code: Select all

info score cp 25 depth 1 seldepth 16 time 0 nodes 4271 nps 0 pv e2a6 b4c3 b2c3 e6d5
info score cp 25 depth 2 seldepth 16 time 1 nodes 8576 nps 8576000 pv e2a6 b4c3 b2c3 e6d5
info score cp 20 depth 3 seldepth 20 time 2 nodes 23332 nps 11666000 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 20 depth 4 seldepth 20 time 6 nodes 60618 nps 10103000 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2
info score cp 5 depth 5 seldepth 20 time 26 nodes 231149 nps 8890346 hashfull 1 pv e2a6 b4c3 d2c3 e6d5 e4d5 f6d5
info score cp 15 depth 6 seldepth 22 time 108 nodes 849402 nps 7864833 hashfull 12 pv e2a6 e6d5 c3d5 b6d5 a6b7 a8d8 b7d5 f6d5
info score cp 5 depth 7 seldepth 24 time 425 nodes 3347752 nps 7877064 hashfull 40 pv e2a6 e6d5 c3d5 f6d5 e5c4 f7f5 c4b6 a7b6
info score cp -15 depth 8 seldepth 26 time 1923 nodes 13492089 nps 7016167 hashfull 248 pv e2a6 e6d5 c3d5 f6d5 e5d3 f7f5 g2h3 f5e4
info score cp -40 depth 9 seldepth 27 time 9306 nodes 64753214 nps 6958222 hashfull 817 pv d5e6 e7e6 e2a6 e6e5 g2h3 b4c3 d2c3 e5e6 c3f6 g7f6

Note the fact that the savings on counted nodes when using the hash value to cut the search are massive, while the savings on using the best move from the hash table for sorting are marginal; certainly there, but not shocking. On several sites I've read that "hash move sorting is much more important than the cuts provided by the hash table", and that "Best move from the previous iteration first is more important than hash cuts."

In my situation, the hash cuts seem to provide a much bigger saving than the hash move ordering.

Going by the descriptions on some of the websites, I was expecting world-shattering savings on the hash move sorting, and marginal savings on the hash cuts, but it seems to be the other way around. Do you have any thoughts about why this could be?

[mar]

well, TT cutoff saves you the effort of searching a whole subtree, so it should help a lot.
let's not forget all nodes, where no move is able to beat alpha (no hashmove most likely).
I'm lying here a bit because I don't overwrite the hashmove when storing to TT IF no bestmove is found.

I did a simple test recently:

Code: Select all

ttCuts: 836334 betaCuts: 5291715 failLows: 1651950

where betacuts = beta cutoffs (cut nodes) and "failLows" is all nodes

this is a depth 20 search from startpos.

you could also try internal iterative deepening in the cases where you don't have a hashmove (yet), by doing a reduced search

edit: I get this with aspiration windows disabled (in fact I used a 15k cp windows as I have no way of truly disabling aspiration):

Code: Select all

ttCuts: 670693 betaCuts: 4096405 failLows: 1322901

[lithander]

So hash move sorting doesn't provide much benefit at all for you? Do you have any other move ordering in place when hash move sorting is disabled? Or is it then playing just the sequence in which the moves where generated?

I can tell you that for me two types of move ordering provide massive reduction in nodes visited:
1) search the move from the PV table at the same depth first
2) play captures first and play those in MVV-LVA order

I would have thought TranspositionTables to provide at least that if not more.

(If you give me the FEN of your position I can give you my numbers)
Edit: This position? r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w - - 0 1

[mar]

removing hash move ordering increases total node count (d20 startpos) by a factor of 4+ in my case, certainly not what I'd call marginal...

EDIT: removing all advanced search features I only get aboud 20% increase in total node count by not ordering hashmove first, however, so that's probably what you see as well

[mvanthoor]

removing hash move ordering increases total node count (d20 startpos) by a factor of 4+ in my case, certainly not what I'd call marginal...

EDIT: removing all advanced search features I only get aboud 20% increase in total node count by not ordering hashmove first, however, so that's probably what you see as well

So if you have lots of move ordering already, hash move ordering provides lots of benefit...
And if you don't have lots of move ordering, hash move ordering doesn't provide a lot of benefit.

So it seems that hash move ordering removes a certain X numbers of moves, where X doesn't vary much if you have a lot, or a little move ordering. If you already cut a lot of moves because other move orderings being in place, then X's impact is obviously bigger.

However, in my example, number of nodes counted without hash move ordering is only 5% larger than number of nodes counted with hash move ordering; but I still do have MVV-LVA in place. I'll try and remove that and see what the difference is.

edit:

Well... when disabling MVV_LVA, which at this time is my only other move ordering, the hash move ordering benefit at depth 3 is actually massive. The number of searched nodes drops from 117 million down to 29 million. That is the 4x improvement you also reported.

No move ordering at all:

Code: Select all

info score cp 25 depth 1 seldepth 30 time 839 nodes 8057866 nps 9604131 pv e2a6 b4c3 b2c3 e6d5
info score cp 25 depth 2 seldepth 32 time 6216 nodes 61725608 nps 9930117 pv e2a6 b4c3 b2c3 e6d5
info score cp 20 depth 3 seldepth 33 time 118902 nodes 1170114231 nps 9840997 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2

Hash move ordering only: (4x less nodes at depth 3)

Code: Select all

info score cp 25 depth 1 seldepth 30 time 847 nodes 8057866 nps 9513419 pv e2a6 b4c3 b2c3 e6d5
info score cp 25 depth 2 seldepth 32 time 5545 nodes 54948351 nps 9909531 pv e2a6 b4c3 b2c3 e6d5
info score cp 20 depth 3 seldepth 33 time 30347 nodes 298167556 nps 9825273 pv e2a6 e6d5 a6b7 b4c3 b7a8 c3d2

Could it be that hash move ordering has more impact if:
- your moves are not ordered well
- you already search few moves

Even so... the question from the other topic remains: how far do PV Move first and hash move ordering overlap?

[mvanthoor]

So hash move sorting doesn't provide much benefit at all for you? Do you have any other move ordering in place when hash move sorting is disabled? Or is it then playing just the sequence in which the moves where generated?

I can tell you that for me two types of move ordering provide massive reduction in nodes visited:
1) search the move from the PV table at the same depth first
2) play captures first and play those in MVV-LVA order

I would have thought TranspositionTables to provide at least that if not more.

(If you give me the FEN of your position I can give you my numbers)
Edit: This position? r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w - - 0 1

Yes. My test was with the KiwiPete position.

I have MVV-LVA order obviously; without it, the engine basically grinds to a halt.

Your other point is what I was trying to address with the two topics I just made. "Everybody" seems to get huge benefits from playing the PV move first, and most sources are expounding about the "massive" impact of hash move ordering. Because I put all the best moves into the hash table (best moves are by definition PV Moves), and I get the best move from the hash table and sort on it, I was of the opinion that ordering on hash move _includes_ ordering on PV move... but maybe not.

How did you implement ordering on the PV move; by the 'old' way of just saving all the PV's in an array, and then getting the move by all_pvs[ply][ply]? (Or was it all_pvs[ply-1][ply-1]? Don't remember on top of my head.)

The problem with this stuff is that there's lots of incorrect or conflicting information about; some engines don't do PV Move ordering because they have hash move ordering, some engines claim that they DO have PV Move ordering on top of hash move ordering because it provides a benefit, and some claim that it just wastes time because the PV is _always_ in the hash table.

I could obviously stuff the PV moves into the hash table at the end of an iteration (without any socres), so I KNOW they'll be in there in the next iteration, and then see if this provides a benefit.

[lithander]

I think you need to run your tests on many different positions and average the results. On average playing the PV move first is beneficial but on the kiwipete position it isn't.

Usually I run the following test against the positions from the Bratko-Kopec test. The numbers show how the search becomes less effective when I don't search the PV move first. Every number on eval, moves and positions is a ratio compared to the "baseline" run I have recorded. If the ratios are significantly below 1 on average I have made an improvement otherwise not. In this case I made it much worse - as expected.

Code: Select all

PV d6d1 c1d1 d7g4 d1e1 d8d1 = -9999.00, OK!
1 OK! eval 3.591, moves 1.477, positions 6.671 acs 1.353 / 0.368 = 3.677.

PV e4e5 d6d5 f4f5 f8g8 f5f6 g7f6 e5f6 = +50.00, OK!
2 OK! eval 8.831, moves 8.33, positions 4.892 acs 14.729 / 1.376 = 10.704.

PV h7h5 g4h5 g6h5 f3h4 h8h7 g3f5 g7f5 = +31.00, OK!
3 OK! eval 3.806, moves 4.453, positions 2.861 acs 6.554 / 1.741 = 3.764.

PV e5e6 f7e6 d4e6 c8e6 e2e6 d8d7 e6e5 = +53.00, OK!
4 OK! eval 3.547, moves 4.446, positions 1.929 acs 8.265 / 1.769 = 4.672.

PV a2a4 b5a4 c3a4 f6g4 f1f8 e7f8 a4b6 = +72.00, OK!
5 OK! eval 5.967, moves 3.24, positions 2.418 acs 102.631 / 15.828 = 6.484.

PV g3g4 g7g6 b3b4 b7b5 g4f3 g8g7 f3e4 = +43.00, OK!
6 OK! eval 3.612, moves 3.997, positions 2.73 acs 1.45 / 0.385 = 3.767.

PV h5f6 g7f6 e5f6 g8g6 f6e7 b8c6 f3h3 = +82.00, OK!
7 OK! eval 7.566, moves 6.28, positions 4.424 acs 31.593 / 4.003 = 7.892.

PV e2c3 e7e6 a2a4 a7a5 h2h4 e8c6 c3b5 = -43.00, OK!
8 OK! eval 2.4, moves 2.433, positions 2.504 acs 0.23 / 0.098 = 2.347.

PV f1d3 f8h6 h4g3 g8e7 h1e1 e7f5 c3b5 = +178.00, OK!
9 OK! eval 4.147, moves 2.96, positions 2.515 acs 41.627 / 9.853 = 4.225.

PV c6e5 d3d1 d4d3 f2b6 a7b6 c2d3 e5d3 = -117.00, OK!
10 OK! eval 2.103, moves 2.029, positions 1.805 acs 12.063 / 5.887 = 2.049.

PV g3f5 c8d8 e3g5 f7f6 g5e3 a5b3 a1d1 = +119.00, OK!
11 OK! eval 5.368, moves 5.728, positions 3.942 acs 30.851 / 5.878 = 5.249.

PV d7f5 a1d1 h7h6 g5e4 f5g6 h5g4 a8c8 = -9.00, OK!
12 OK! eval 4.367, moves 4.048, positions 2.471 acs 19.843 / 4.382 = 4.528.

PV a2a4 a6a5 d3g3 a8b8 a1b1 e7f6 d2f4 = +40.00, OK!
13 OK! eval 1.301, moves 1.367, positions 1.078 acs 7.097 / 5.618 = 1.263.

PV d1d2 a5d5 b2c3 e7e5 d2h6 d5f7 a1d1 = +376.00, OK!
14 OK! eval 1.163, moves 1.184, positions 0.996 acs 1.552 / 1.357 = 1.144.

PV g4g7 e7g7 f1f6 c8e8 g1f2 a5a4 g3g7 = +64.00, OK!
15 OK! eval 0.785, moves 0.904, positions 0.634 acs 1.05 / 1.243 = 0.845.

PV d2e4 h6g5 e4d6 e8d7 d6f7 d8c7 f7h8 = +99.00, OK!
16 OK! eval 4.173, moves 3.534, positions 2.762 acs 7.613 / 1.704 = 4.468.

PV c7c6 c1e3 c6d5 c4d5 a8c8 g4g5 c8c3 = +22.00, OK!
17 OK! eval 6.408, moves 4.365, positions 3.715 acs 27.981 / 4.275 = 6.545.

PV d6d5 e4d5 d8d5 e1e2 c8e6 a3b5 a8d8 = -51.00, OK!
18 OK! eval 1.364, moves 1.7, positions 1.389 acs 12.486 / 9.727 = 1.284.

PV e8e4 e1e4 d6d5 c4a6 d5e4 d4c5 d7g4 = -33.00, OK!
19 OK! eval 1.272, moves 1.375, positions 1.061 acs 3.7 / 2.973 = 1.244.

PV c3b5 d6d8 e2h5 a7a6 b5c3 f8g8 c1b1 = +71.00, OK!
20 OK! eval 7.964, moves 6.284, positions 4.015 acs 67.866 / 8.261 = 8.215.

PV f5h6 e6h3 h6f7 h8g8 g2h3 g8f7 b2d4 = +228.00, OK!
21 OK! eval 17.765, moves 10.315, positions 4.368 acs 90.376 / 3.893 = 23.215.

PV d7e5 f3e5 d6e5 a1c1 c8d8 a4c3 d8d4 = -4.00, OK!
22 OK! eval 2.905, moves 2.795, positions 2.267 acs 18.483 / 6.938 = 2.664.

PV c8f5 a4a5 e8g8 a5a6 a8b8 f1f2 b7b6 = -6.00, OK!
23 OK! eval 9.957, moves 6.618, positions 5.893 acs 80.166 / 8.44 = 9.498.

PV f2f4 f5e4 d3e4 g8e7 b3b1 c5b4 a3b4 = +99.00, OK!
24 OK! eval 0.772, moves 1.631, positions 1.111 acs 4.973 / 7.874 = 0.632.

Test finished with 0 wrong results! Time: 5.016, Eval: 4.631, Moves generated: 3.812, Moves played: 2.852, Performance: 1251kN/sec
A total of 17507075 moves were generated. 3424816 were played. 19%
  Operation took 596.0447s

Your chosen position does not reflect that average behavior at all.

With PV moves:

Code: Select all

info depth 1 score cp 33 nodes 3666 nps 146640 time 25 pv e2a6
info depth 2 score cp 33 nodes 6860 nps 99420 time 69 pv e2a6 b4c3
info depth 3 score cp 13 nodes 25449 nps 257060 time 99 pv d5e6 e7e6 e2a6
info depth 4 score cp 13 nodes 89112 nps 497832 time 179 pv d5e6 e7e6 e2a6 e6e5
info depth 5 score cp -29 nodes 494459 nps 890917 time 555 pv e2a6 b4c3 d2c3 e6d5 e4d5
info depth 6 score cp -29 nodes 1668008 nps 1147975 time 1453 pv e2a6 b4c3 d2c3 e6d5 e4d5 h3g2
info depth 7 score cp -30 nodes 7921677 nps 1234290 time 6418 pv e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2
info depth 8 score cp -42 nodes 37785091 nps 1276437 time 29602 pv e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2 b6c4

Without PV moves first.

Code: Select all

info depth 1 score cp 33 nodes 3666 nps 152750 time 24 pv e2a6
info depth 2 score cp 33 nodes 7457 nps 201540 time 37 pv e2a6 b4c3
info depth 3 score cp 13 nodes 25903 nps 275563 time 94 pv d5e6 e7e6 e2a6
info depth 4 score cp 13 nodes 70189 nps 487423 time 144 pv d5e6 e7e6 e2a6 e6e5
info depth 5 score cp -29 nodes 423086 nps 823124 time 514 pv e2a6 b4c3 d2c3 e6d5 e4d5
info depth 6 score cp -29 nodes 1401169 nps 1104152 time 1269 pv e2a6 b4c3 d2c3 e6d5 e4d5 h3g2
info depth 7 score cp -30 nodes 8940401 nps 1164721 time 7676 pv e2a6 b4c3 d2c3 h3g2 f3g2 e6d5 e5g4
info depth 8 score cp -42 nodes 30402270 nps 1220827 time 24903 pv e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2 b6c4

So, the PV move first doesn't improve search on this position. Removing the feature I expected the search to take 5x longer (according to average results on other positions at the same depth) but is actually faster. Note how test 24 and 15 in the bratko kopek test also didn't benefit from PV moves first. So kiwipete is one of the outliers. If the PV move would be always best we didn't have to search any further!

Not even bratko-kopek is enough: I have found "improvements" that worked for the bratko-kopek set with ratios around 0.8 on average but when finally run against a set of 900 positions from my ultimate test the improvement turned out uneffective.

[mvanthoor]

I think you need to run your tests on many different positions and average the results. On average playing the PV move first is beneficial but on the kiwipete position it isn't.

So, the PV move first doesn't improve search on this position.

Sigh. Why does it have to be me? (Just let's credit that to Abba, while we're at it.)

It's the same at work sometimes. Someone shows me some almost perfect piece of code, and I unfailingly manage to get the team aggravated by running the ONE edge case against it that everybody forgot about. And it doesn't take me any effort to do it.

So just leave it to ME, to find the ONE, SINGLE position in the history of ever to point out that some feature "doesn't work" or "gets less results than expected." Sigh.

Removing the feature I expected the search to take 5x longer (according to average results on other positions at the same depth) but is actually faster. Note how test 24 and 15 in the bratko kopek test also didn't benefit from PV moves first. So kiwipete is one of the outliers. If the PV move would be always best we didn't have to search any further!

Not even bratko-kopek is enough: I have found "improvements" that worked for the bratko-kopek set with ratios around 0.8 on average but when finally run against a set of 900 positions from my ultimate test the improvement turned out uneffective.

Is that first test you showd the Bratko-Kopek test? I never heard of it.

I'll test hash move ordering on some other, more normal middle game positions. I still suspect that hash move ordering overlaps a great deal with last iteration's best move first, because that move is a PV move, and all of those are in the TT. They shouldn't be overwritten too quickly if the TT has a somewhat decent size. Thus it would be beneficial to do Last Iteration's best move first, when running without a TT. For a minimal engine, that's quite a nice option actually. Do you just pick the best move when in the root and order that, or do you actually follow the entire PV down the tree?

[mvanthoor]

I've just tested on a standard position in the Ruy Lopez:

[d]r1bq1rk1/2p1bppp/p1np1n2/1p2p3/3PP3/1B3N2/PPP2PPP/RNBQR1K1 w - - 0 9

No use of info from the TT:

Code: Select all

info score cp 15 depth 1 seldepth 11 time 0 nodes 237 nps 0 pv c1g5
info score cp 15 depth 2 seldepth 15 time 0 nodes 2877 nps 0 pv d4d5 c6b8
info score cp 20 depth 3 seldepth 15 time 1 nodes 9085 nps 9085000 pv d4d5 c6a5 c1d2 a5b3 a2b3
info score cp 15 depth 4 seldepth 21 time 10 nodes 87162 nps 8716200 pv c1e3 c8g4 d4d5 g4f3 d1f3
info score cp 20 depth 5 seldepth 22 time 38 nodes 350405 nps 9221184 hashfull 3 pv d4d5 c6a5 c1d2 a5b3 a2b3
info score cp 10 depth 6 seldepth 31 time 232 nodes 2084726 nps 8985888 hashfull 19 pv c1e3 c6a5 b3d5 f6d5 e4d5 a5c4
info score cp 15 depth 7 seldepth 31 time 899 nodes 8173079 nps 9091300 hashfull 91 pv b3d5 c8d7 c2c3 a8a7 d4e5 d6e5 c1e3
info score cp 10 depth 8 seldepth 32 time 5626 nodes 49652562 nps 8825553 hashfull 457 pv b3d5 f6d5 e4d5 c6d4 f3d4 e5d4 d1d4 c8f5
info score cp 10 depth 9 seldepth 32 time 33076 nodes 289299373 nps 8746504 hashfull 980 pv b3d5 c8d7 d5c6 d7c6 b1c3 d8d7 d4d5 c6b7 c1d2

Only TT Move ordering:

Code: Select all

info score cp 15 depth 1 seldepth 11 time 0 nodes 237 nps 0 pv c1g5
info score cp 15 depth 2 seldepth 15 time 0 nodes 2643 nps 0 pv d4d5 c6b8
info score cp 20 depth 3 seldepth 15 time 0 nodes 5118 nps 0 pv d4d5 c6a5 c1d2 a5b3 a2b3
info score cp 15 depth 4 seldepth 19 time 5 nodes 44508 nps 8901600 pv d4d5 c6b8 c1d2 c8g4
info score cp 20 depth 5 seldepth 19 time 19 nodes 179875 nps 9467105 hashfull 1 pv d4d5 c6a5 c1d2 a5b3 a2b3
info score cp 10 depth 6 seldepth 31 time 190 nodes 1720204 nps 9053705 hashfull 16 pv c1e3 c6a5 b3d5 f6d5 e4d5 a5c4
info score cp 15 depth 7 seldepth 31 time 863 nodes 7861611 nps 9109630 hashfull 86 pv b3d5 c8d7 c2c3 a8a7 d4e5 d6e5 c1e3
info score cp 10 depth 8 seldepth 33 time 4184 nodes 36469738 nps 8716477 hashfull 392 pv b3d5 f6d5 e4d5 c6d4 f3d4 e5d4 d1d4 c8f5
info score cp 10 depth 9 seldepth 33 time 22333 nodes 198985071 nps 8909912 hashfull 931 pv b3d5 c8d7 c2c3 d8e8 c1d2 d7e6 d5c6 e8c6 d4e5 f6e4

TT Move ordering + TT cuts:

Code: Select all

info score cp 15 depth 1 seldepth 11 time 0 nodes 237 nps 0 pv c1g5
info score cp 15 depth 2 seldepth 15 time 0 nodes 2643 nps 0 pv d4d5 c6b8
info score cp 20 depth 3 seldepth 15 time 0 nodes 5118 nps 0 pv d4d5 c6a5 c1d2 a5b3 a2b3
info score cp 15 depth 4 seldepth 19 time 5 nodes 43212 nps 8642400 pv d4d5 c6b8 c1d2 c8g4
info score cp 20 depth 5 seldepth 19 time 17 nodes 155381 nps 9140059 hashfull 1 pv d4d5 c6a5 c1d2 a5b3 a2b3
info score cp 10 depth 6 seldepth 31 time 150 nodes 1318029 nps 8786860 hashfull 12 pv c1e3 c6a5 b3d5 f6d5 e4d5 a5c4
info score cp 15 depth 7 seldepth 31 time 601 nodes 5348643 nps 8899572 hashfull 60 pv b3d5 c8d7 c2c3 a8a7 d4e5 d6e5 c1e3
info score cp 10 depth 8 seldepth 33 time 2428 nodes 20687053 nps 8520203 hashfull 284 pv b3d5 f6d5 e4d5 c6d4 f3d4 e5d4 d1d4 c8f5
info score cp 10 depth 9 seldepth 33 time 10737 nodes 92619866 nps 8626233 hashfull 858 pv b3d5 c8d7 c2c3 d8e8 c1d2 d7e6 d5c6 e8c6 d4e5 f6e4

As can be seen, in this position, hash move ordering is much more effective. On depth 9, it cuts off about 100 million nodes, dropping the needed time by about 33%. When enabling TT cuts, that time more than halves.

It seems the TT is working perfectly fine; I'm just somewhat underwhelmed. When playing at time controls such as 2m+1s, time for a single move is often only about 2 seconds, or less. In less than 2 seconds, I can reach depth 7 without a TT. When using TT move ordering, I also only can reach depth 7; and even when using TT Move ordering + TT Cuts, I *still* can only reach depth 7 in under 2 seconds; depth 8 still takes more than 2 seconds.

Maybe my expectations of being able to reach 1-2 extra plys in the middle game were just unrealistic. Maybe that will materialize when I implement the additions I have in mind for Alpha 3, which will cut down on number of nodes searched, even without a TT:

- Aspiration window
- Principal vaariation search
- Killer moves
- History Heuristic

This will narrow the tree; maybe the hash table has more impact on that narrower tree (I actually expect that to be the case).

One other thing: I don't cut when in the root. If I do so, I often end up without a PV, and thus, without a best move, which will get the engine killed by the GUI because it will make a move without actually having one, resulting in a1-a1K. I don't know if it's normal to not cut in the root, or if if there is a better way.

[emadsen]

best moves are by definition PV Moves

That's not correct. Hopefully this is just a matter of terminology. But I'll state the idea explicitly just in case it affects your implementation:

In an expected cut node, you want to play a move that immediately causes a beta cutoff. You don't want to waste time searching 20 moves (and the tree underneath those 20 moves) only to find move 21 causes a beta cutoff. The cache (AKA transposition table or hash) can save a lot of work by providing the "best move" here even though it's not in the PV. Remember a beta cutoff at ply n is a fail low at ply n - 1. So underneath all the nodes you expect to fail low at ply n you benefit from "best move" ordering that causes beta cutoffs at ply n + 1, recursively.

In my engine I order "best move" first. I don't order any moves based on the PV. Though mar makes a good point that ordering by PV at the root node is important in MultiPV mode. You want to search the best move first, then second best, third best, etc... from the multiple PVs found the previous iteration / depth. For similar reasons as above. It searches the moves most likely to be among the best (if you do multiple searches) or most likely to be in the alpha / beta window (if you do a single search). Depends how you implement MultiPV.