Root move sorting

[xr_a_y]

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.

[ZirconiumX]

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.

[xr_a_y]

And do some engines have special order treatments for lines with already detected checkmate or checkmated move at root ?

[MOBMAT]

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...

[MOBMAT]

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.