Move Ordering (Again :))

[Richard Allbert]

Hi,

I read an interesting post on the Chess Programming Wiki about move ordering and collecting statistics. There was also a reference to a very old CC post about it, but I can't find it again.

Anyway, I've had a go at collecting some of the information. Ignore the PV column, as there is no PVS implemented.

This was done using AB search with TT cut offs, 20 seconds per position.

Code: Select all

Results: 

Position                                                                               %Qn      %ord     %ttcu      knps
r2qkb1r/pp1n1ppp/2p2n2/3pp2b/4P3/3P1NPP/PPPN1PB1/R1BQ1RK1 b kq e3 0 8                 49,1      88,4      13,5     460,2
r2q1rk1/ppp1bppp/1nn1b3/4p3/1P6/P1NP1NP1/4PPBP/R1BQ1RK1 b - b3 0 10                   48,7      89,2      10,2     474,4
rnbq1rk1/p3ppbp/1p1p1np1/2p5/3P1B2/2P1PN1P/PP2BPP1/RN1QK2R w KQ - 0 8                 48,8      87,4      14,6     449,1
r1b1qrk1/ppp1p1bp/n2p1np1/3P1p2/2P5/2N2NP1/PP2PPBP/1RBQ1RK1 b - - 2 9                 48,4      86,4      12,0     453,6
rnbq1rk1/1p2ppbp/2pp1np1/p7/P2PP3/2N2N1P/1PP1BPP1/R1BQ1RK1 b - - 0 8                  48,9      87,0      13,7     459,4
2kr3r/ppqn1pp1/2pbp2p/7P/3PQ3/5NP1/PPPB1P2/2KR3R w - - 3 16                           47,9      85,6      12,2     506,7
r3kb1r/pp2pppp/1nnqb3/8/3p4/NBP2N2/PP3PPP/R1BQ1RK1 b kq - 4 10                        48,4      88,8      12,8     506,7
r2qk2r/5pbp/p1npb3/3Np2Q/2B1Pp2/N7/PP3PPP/R4RK1 b kq - 1 15                           48,1      87,5      10,6     518,2
r1bqk2r/4bpp1/p2ppn1p/1p6/3BPP2/2N5/PPPQ2PP/2KR1B1R w kq b6 0 12                      48,5      89,4      13,9     495,0
r1b1k2r/1pq3pp/p1nbpn2/3p4/3P4/2NB1N2/PP3PPP/R1BQ1RK1 w kq - 0 13                     48,5      88,8      11,5     496,1
rn1q1rk1/pp3ppp/3b4/3p4/3P2b1/2PB1N2/P4PPP/1RBQ1RK1 b - - 2 12                        48,4      88,0      12,8     510,6
r1b1kb1r/ppp2ppp/2p5/4Pn2/8/2N2N2/PPP2PPP/R1B2RK1 w - - 5 10                          46,3      85,8      11,8     538,2
r2qrbk1/1b1n1p1p/p2p1np1/1p1Pp3/P1p1P3/2P2NNP/1PB2PP1/R1BQR1K1 w - - 0 17             48,7      89,4      15,1     455,1
r2q1rk1/pp1n1ppp/2p1pnb1/8/PbBPP3/2N2N2/1P2QPPP/R1B2RK1 w - - 1 11                    48,6      89,9      14,6     485,4
r1bq1rk1/1p2bppp/p1n1pn2/8/P1BP4/2N2N2/1P2QPPP/R1BR2K1 b - - 2 11                     48,8      89,4      12,3     485,6
r1b2rk1/pp3ppp/2n1pn2/q1bp4/2P2B2/P1N1PN2/1PQ2PPP/2KR1B1R b - - 2 10                  49,1      91,1      11,3     478,0
rnbq1rk1/2pnppbp/p5p1/1p2P3/3P4/1QN2N2/PP3PPP/R1B1KB1R w KQ - 1 10                    48,6      91,5      14,2     488,7
rnb2rk1/ppp1qppp/3p1n2/3Pp3/2P1P3/5NP1/PP1N1PBP/R2Q1RK1 w - - 1 11                    47,9      87,3      12,4     484,4
r2q1rk1/pbpn1pp1/1p2pn1p/3p4/2PP3B/P1Q1PP2/1P4PP/R3KBNR w KQ - 1 11                   48,3      87,1      13,8     494,2
r3qrk1/1ppb1pbn/n2p2pp/p2Pp3/2P1P2B/P1N5/1P1NBPPP/R2Q1RK1 w - - 1 13                  47,7      87,8      11,5     470,7
TotalResult:                                                                          48,4      88,3      12,6     485,5




FHF Cutoff stats:
PV             HASH           PROMQ          CAP            K1             K2             PROMS          HIST           
0              18594          6925           2038114        47             0              0              235            
0              21426          9201           1841984        417            0              0              42             
0              23380          4274           1906098        51             0              0              704            
0              28659          12399          1777996        583            1698           0              4531           
0              23345          9178           1918455        1010           4              0              7294           
0              39838          1352           1789863        28             0              0              7362           
0              42546          8873           1908133        1517           24             0              2797           
0              41256          1088           1818397        1484           897            0              6803           
0              40225          9523           1753535        0              0              0              3329           
0              29115          404            1780258        17             0              0              2756           
0              38426          541            1905870        418            0              0              3451           
0              69939          3231           1478159        4784           11             0              129894         
0              26402          9913           1715999        0              0              0              649            
0              29504          14430          1878440        65             0              0              4302           
0              28245          1644           1812614        0              86             0              561            
0              19306          2991           1724089        0              0              0              893            
0              28090          4248           1831704        16             0              0              1995           
0              35819          11989          1924528        0              5              0              22463          
0              42585          3111           1957238        7              0              0              4683           
0              41732          10067          1625945        3              0              0              37730          

Total
0              668432         125382         36387419       10447          2725           0              242474         


FH Cutoff stats:
PV             HASH           PROMQ          CAP            K1             K2             PROMS          HIST           
0              34689          7336           2268861        11204          283            32             12708          
0              36429          9756           2001686        3713           197            0              48176          
0              38838          4277           2114233        9609           47             0              45412          
0              48595          12544          1939789        1484           18460          0              91318          
0              43651          9226           2138301        1913           478            4              58030          
0              63617          1352           1957579        685            16             0              124369         
0              63757          8973           2108881        3018           473            1              26107          
0              59097          1088           2016053        2455           1024           0              56789          
0              62943          9614           1898552        22             53             1              49661          
0              40477          404            1918636        10179          6              0              70339          
0              58627          565            2118800        2302           170            0              34852          
0              102025         3575           1553115        6160           15             0              300484         
0              43432          10119          1847487        34             0              9              58691          
0              48426          14433          2050190        99             0              0              29076          
0              47784          1649           1931992        7              387            0              79136          
0              33912          3150           1868958        8              2              0              12742          
0              45180          4312           1942648        364            24             0              47914          
0              56261          12570          2065660        0              5              1              149936         
0              66001          3201           2177918        34             132            0              58343          
0              65773          10739          1749005        153            0              1              128822         

Total
0              1059514        128883         39668344       53443          21772          49             1482905    

A couple of (well, more than a couple..) questions come to mind.

The capture cut offs are so high due to QSearch, I assume. Should I not collect this information in the QSearch at all?

What is the best way to go about using this information? The ordering is done using MVV/LVA, with the overall ordering as in the table left to right.

From the general results, the ordering was 88,3%. I remember reading here that it should be at least 90%.

I've defined the ordering as the %of beta cut offs that occur on the first move vs the total beta cut offs.

Are there any other stats I can collect to work on improving to over 90% ?

Apart from SEE()

Thanks

Richard

[hgm]

The capture cut offs are so high due to QSearch, I assume. Should I not collect this information in the QSearch at all?

I have only found it useful when I collect this kind of information per remaining depth. That would map all QS nodes to the d=0 stats bin. I am surprised you don't list null move; it is the largest source of cutoffs.

It could also be useful to collect stats for in-check nodes separately from other nodes. Rather than looking at the stats I found it useful to take samples of the different cases. E.g. you can print out some positions where the cutoff occurred only at the 20th move or later, and look at them to see what kind of positions these typically are, and if you could conceive a heuristic that would have identified the cut move in some way.

[Richard Allbert]

Hi HG,

I forgot to mention - no null move pruning at all here! and no IID.

I'll have a look at what you suggest.

Regards

Richard

[bob]

The capture cut offs are so high due to QSearch, I assume. Should I not collect this information in the QSearch at all?

I have only found it useful when I collect this kind of information per remaining depth. That would map all QS nodes to the d=0 stats bin. I am surprised you don't list null move; it is the largest source of cutoffs.

It could also be useful to collect stats for in-check nodes separately from other nodes. Rather than looking at the stats I found it useful to take samples of the different cases. E.g. you can print out some positions where the cutoff occurred only at the 20th move or later, and look at them to see what kind of positions these typically are, and if you could conceive a heuristic that would have identified the cut move in some way.

I don't think null-move will be the largest source of cutoffs, although it is probably the largest source of tree size reduction. But a null-move search still has a pretty normal tree directly below it that will get traditional cutoffs everywhere...

In check would probably be useful to see if there is a more effective way to order moves there...

[hgm]

Well, for me it was; more than 50% of the cutoffs in the full-width search were caused by null moves. I could only see that by sorting out the stats by depth, of course. If 85% of the nodes are QS, where null move is not even tried, the total fracttion of null-move cutoffs could obviously never be higher than 15%.

This is why heaping all depths together makes these stats so utterly useless. It could in theory be that killer 1 would be responsible for 100% of the cutoffs in full-width search, while captures were never any good there, and with 85% of the nodes QS you would then see that 85% of the cutoffs is caused by a capture, and only 15% by killer 1. So you would think: "hey, these captures do pretty well; let's search them before killer 1". Which in that hypothetical case would be a pure waste of time.

[Don]

Well, for me it was; more than 50% of the cutoffs in the full-width search were caused by null moves. I could only see that by sorting out the stats by depth, of course. If 85% of the nodes are QS, where null move is not even tried, the total fracttion of null-move cutoffs could obviously never be higher than 15%.

This is why heaping all depths together makes these stats so utterly useless. It could in theory be that killer 1 would be responsible for 100% of the cutoffs in full-width search, while captures were never any good there, and with 85% of the nodes QS you would then see that 85% of the cutoffs is caused by a capture, and only 15% by killer 1. So you would think: "hey, these captures do pretty well; let's search them before killer 1". Which in that hypothetical case would be a pure waste of time.

Move ordering is a black art just like most of computer chess! I think there is more than can be done but I'm not sure what!