There was another recent thread regarding sorting root moves, but i'll include this in the most recent thread.
I just ran a test of using the number of cutoffs (score >= beta) as the basis of sorting the ROOT moves.
cutoff counts were collected in both the main and qsearch nodes.
the move selection at each iteration is:
1. try the best moves from each previous iteration first...
2. try the move with the "minimal" number of cutoffs (must be > zero, though)
3. use the original static eval value that was calculated before the search started.
compared to my original static move ordering, this technique reduces the nodes searched by about 1% and a speedup of about .5%. the difference is probably because of the extra overhead of counting the cutoffs and the possible loss of new good moves to try because of using the best moves from previous plies (diminishing return).
here is an example from position #3 in the BT2450 suite.
5r1k/p1q2pp1/1pb4p/n3R1NQ/7P/3B1P2/2P3P1/7K w - - 0 1
Tests were run using straight PVS with TT with no NULL or LMR pruning, and a VERY simplistic evaluation function.
Original static sorting (no re-sort)
Code: Select all
1 0:00 50 -0.72 1.Bf5
2 0:00 386 -0.78 1.Nh7 g6
3 0:00 2,587 -0.74 1.c4 f6 2.Rf5
4 0:00 14,470 -0.81 1.f4 Qd6 2.Nh7 g6
5 0:00 87,963 0.33 1.Rf5 Qg3 2.Nxf7+ Kg8 3.c4
6 0:00 182,841 0.28 1.Rf5 Kg8 2.Rxf7 Rxf7 3.Qxf7+ Qxf7
7 0:00 884,991 0.33 1.Rf5 Kg8 2.Nxf7 Qg3 3.Qg4 Qxg4 4.fxg4
8+ 0:01 2,870,253 -0.91 1.f4
8+ 0:01 4,426,434 -0.89 1.Nh7
8+ 0:02 6,454,050 0 1.Re6
8 0:02 6,591,388 0 1.Re6 Kg8 2.Bh7+ Kh8 3.Bd3
9 0:05 14,563,965 1.47 1.Re6 Kg8 2.Rxh6 gxh6 3.Qxh6 f5 4.Ne6 Qg3 5.Nxf8
10 0:10 30,425,844 1.46 1.Re6 Kg8 2.Rxh6 gxh6 3.Qxh6 f5 4.Ne6 Qg3 5.Qxf8+ Kh7
11 0:32 96,494,203 3.56 1.Re6 Kg8 2.Bh7+ Kh8 3.Rxh6 Re8 4.Bg6+ gxh6 5.Qxh6+ Kg8 6.Bxf7+
12 1:15 220,566,525 3.45 1.Re6 f5 2.Bxf5 Kg8 3.Rxc6 Qf4 4.Be6+ Kh8 5.Rc3 b5 6.Nh3 g6
13 4:35 823,264,267 3.57 1.Re6 f5 2.Bxf5 Kg8 3.Rxc6 Qf4 4.Bh7+ Kh8 5.Ne6 Qc1+ 6.Kh2 Nxc6 7.Nxf8
14 11:56 2,110,252,082 3.47 1.Re6 f5 2.Bxf5 Kg8 3.Rxc6 Qf4 4.Be6+ Kh8 5.Rc3 Qg3 6.Nf7+ Kh7 7.Qg4 Qxg4
Counting cutoffs (re-sorting after each iteration)
Code: Select all
1 0:00 46 -0.72 1.Bf5
2 0:00 512 -0.78 1.Nh7 g6
3 0:00 2,773 -0.74 1.g4 f6 2.Rf5
4 0:00 11,271 -0.81 1.f4 Qd6 2.Bf5 Nc4
5 0:00 80,623 0.33 1.Rf5 Qg3 2.Nxf7+ Kg8 3.c4
6 0:00 174,430 0.28 1.Rf5 Kg8 2.Rxf7 Rxf7 3.Qxf7+ Qxf7
7 0:00 849,251 0.33 1.Rf5 Kg8 2.Nxf7 Qg3 3.Qg4 Qxg4 4.fxg4
8+ 0:01 2,825,835 -0.91 1.f4
8+ 0:01 3,984,100 -0.89 1.Nh7
8+ 0:02 5,754,687 0 1.Re6
8 0:02 6,051,643 0 1.Re6 Kg8 2.Bh7+ Kh8 3.Bd3
9 0:04 13,731,838 1.47 1.Re6 Kg8 2.Rxh6 gxh6 3.Qxh6 f5 4.Ne6 Qg3 5.Nxf8
10 0:10 28,980,143 1.46 1.Re6 Kg8 2.Rxh6 gxh6 3.Qxh6 f5 4.Ne6 Qg3 5.Qxf8+ Kh7
11 0:32 95,786,026 3.51 1.Re6 f5 2.Bxf5 Kg8 3.Rxc6 Qf4 4.Be6+ Kh8 5.Rc3 b5 6.Re3
12 1:06 194,059,614 3.45 1.Re6 f5 2.Bxf5 Kg8 3.Rxc6 Qf4 4.Be6+ Kh8 5.Rc3 b5 6.Nh3 g6
13 4:26 794,278,742 3.57 1.Re6 f5 2.Bxf5 Kg8 3.Rxc6 Qf4 4.Bh7+ Kh8 5.Ne6 Qc1+ 6.Kh2 Nxc6 7.Nxf8
14 11:52 2,094,383,787 3.47 1.Re6 f5 2.Bxf5 Kg8 3.Rxc6 Qf4 4.Be6+ Kh8 5.Rc3 Qg3 6.Nf7+ Kh7 7.Qg4 Qxg4
Here is an example of the root stats after ply six, prior to trying ply seven.
Code: Select all
1 g5f7 97 9835
2 e5a5 295 8998
3 h5h6 94 10499
4 h5f7 94 11144
5 c2c3 12 25190
6 g2g3 20 12103
7 f3f4 10,004 5896
8 c2c4 13 22768
9 g2g4 10,003 6690
10 g5h3 19 15084
11 g5e4 17 16463
12 g5e6 16 18423
13 g5h7 10,002 8034
14 d3f1 14 20105
15 d3e2 14 20668
16 d3c4 11 27032
17 d3e4 16 19004
18 d3b5 8 27921
19 d3f5 10,001 8504
20 d3a6 4 28733
21 d3g6 17 16924
22 d3h7 17 17642
23 e5e1 12 26092
24 e5e2 13 23430
25 e5e3 14 21607
26 e5e4 15 19398
27 e5b5 7 28170
28 e5c5 10 27357
29 e5d5 13 23875
30 e5f5 10006 4129
31 e5e6 14 22046
32 e5e7 13 24367
33 e5e8 12 26615
34 h5g4 20 12793
35 h5g6 19 15725
36 h1g1 20 13762
37 h1h2 22 11230
the 3rd column is the original static eval. Scores above 10,000 indicate the move was the PV from the specified ply (score - 10000).
the 4th column is the number of cutoffs for the current ply.
at ply 7, the first move tried would be e5f5 since it was the best move at ply 6, (it was also the best move at ply 5), then f3f4 (10,004), then g2g4 (10,003), etc. after that, the move with the lowest cutoff count is tried, in this case, e5a5. If you notice, the moves that were the best at the previous ply had the lowest number of cutoffs.
The question is, would there be a benefit of applying this technique recursively?
i haven't tried counting nodes yet...