Root move sorting
Moderators: hgm, Rebel, chrisw
-
- Posts: 1871
- Joined: Sat Nov 25, 2017 2:28 pm
- Location: France
Root move sorting
At root, it is very easy to store each move score, especially in a fail soft framework, whether from the previous iterative deepening loop or from a small iid. How such a move ordering perform ? The best move will still be first but others may be sorted differently.
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Root move sorting
Fail soft scores are still fairly unreliable in my experience; just because a score can be outside the window doesn't always mean it is.
Hyatt suggested root move ordering by node count, and I think it's worth trying out, but I would have to test.
Printing root move ordering coincidentally helped me find a bug in my TT code.
Hyatt suggested root move ordering by node count, and I think it's worth trying out, but I would have to test.
Printing root move ordering coincidentally helped me find a bug in my TT code.
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 1871
- Joined: Sat Nov 25, 2017 2:28 pm
- Location: France
Re: Root move sorting
And do some engines have special order treatments for lines with already detected checkmate or checkmated move at root ?
-
- Posts: 385
- Joined: Sat Feb 04, 2017 11:57 pm
- Location: USA
Re: Root move sorting
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)
Counting cutoffs (re-sorting after each iteration)
Here is an example of the root stats after ply six, prior to trying ply seven.
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...
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
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
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 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...
i7-6700K @ 4.00Ghz 32Gb, Win 10 Home, EGTBs on PCI SSD
Benchmark: Stockfish15.1 NNUE x64 bmi2 (nps): 1277K
Benchmark: Stockfish15.1 NNUE x64 bmi2 (nps): 1277K
-
- Posts: 385
- Joined: Sat Feb 04, 2017 11:57 pm
- Location: USA
Re: Root move sorting
please don't comment on my previous post.
I found an SPE (stupid programmer error) that tainted the results.
I'll post the corrections once the tests are complete.
I found an SPE (stupid programmer error) that tainted the results.
I'll post the corrections once the tests are complete.
i7-6700K @ 4.00Ghz 32Gb, Win 10 Home, EGTBs on PCI SSD
Benchmark: Stockfish15.1 NNUE x64 bmi2 (nps): 1277K
Benchmark: Stockfish15.1 NNUE x64 bmi2 (nps): 1277K