Best move statistics

[matthewlai]

I took 100000 random positions from the CCRL PGN dump, did a fast search on each of them, and randomly selected an internal node from each search (more or less). This gives me a collection of positions uniformly drawn from the searches, where the search had to order moves.

Then I did another fast search using each internal node as root, to find the best move from the internal node.

The goal is to compute some statistics and see if there's any insight that can be used in move ordering and (even more importantly for me) prior probability estimation.

I created a bunch of filters, and kept statistics about moves that match each filter. For each of the filter below, "best" is the number of times a move matching the filter is the best move, "legal" is the number of times a move matching the filter is legal, and "scaled" is how frequent a move matching the filter turns out to be the best, scaled to uniform probability.

For example, scaled = 1 means a move matching the filter would have 1/30 the probability of being best, if there are 30 legal moves.

Some results:

1. captures and non-captures with positive, 0, and negative SEE -

Code: Select all

+SEE captures: 
best: 38573	legal: 78130	scaled: 7.96696
=SEE captures: 
best: 7132	legal: 25675	scaled: 8.39814
=SEE non-captures: 
best: 51063	legal: 1857763	scaled: 0.770027
-SEE captures: 
best: 1079	legal: 113573	scaled: 0.31697
-SEE non-captures: 
best: 2153	legal: 769055	scaled: 0.0873344

Here we see that +SEE captures are obviously very likely to be good, but surprisingly, neutral captures are even more likely to be good. We also see that -SEE captures have higher probability than -SEE non-captures (throwing away pieces). The probability for losing captures is actually surprisingly high (almost 1/2 the probability for neutral non-captures).

2. Broken down by piece type:

Code: Select all

iece Types (+SEE):
K:
best: 3342	legal: 5823	scaled: 2.44043
Q:
best: 6819	legal: 14534	scaled: 9.4128
R:
best: 8469	legal: 15945	scaled: 9.71956
N:
best: 5181	legal: 12108	scaled: 9.64009
B:
best: 5641	legal: 12055	scaled: 9.92174
P:
best: 9121	legal: 17665	scaled: 11.8489

Piece Types (=SEE):
K:
best: 7664	legal: 266165	scaled: 0.490375
Q:
best: 8991	legal: 307500	scaled: 0.995242
R:
best: 11726	legal: 456309	scaled: 0.791842
N:
best: 9318	legal: 216618	scaled: 1.3492
B:
best: 8547	legal: 268396	scaled: 0.976824
P:
best: 11949	legal: 368450	scaled: 0.996478

Piece Types (-SEE):
K:
no match
Q:
best: 217	legal: 245682	scaled: 0.0301311
R:
best: 539	legal: 201789	scaled: 0.0789882
N:
best: 619	legal: 135626	scaled: 0.146236
B:
best: 446	legal: 178976	scaled: 0.0802111
P:
best: 1411	legal: 120555	scaled: 0.331534

Here we see that +SEE captures are very good for all pieces except the king. Since the king cannot be captured, these are essentially the king capturing undefended pieces.

When we go to =SEE, everything is pretty close to 1, except for kings, which is at 0.5.

For -SEE, it's basically never a good idea to sacrifice a queen, rook, or bishop. Knight sacrifices are slightly better. Pawn sacrifices are surprisingly high at 0.33, which is about 1/3 the probability of normal pawn moves.

3. Promotions:

Code: Select all

Queen promotions:
best: 502	legal: 1318	scaled: 8.36711

Under-promotions:
best: 30	legal: 3954	scaled: 0.166675

Queen promotions are about as good as +SEE captures. Under-promotions are pretty low.

------------------------------------------------------------------------------------
I'll be generating more statistics. In particular, I want to see how game phase changes things.

I now have a system that's very easy to write filters for, and do and/or/xor with the filters. Any suggestions? What would you like to see?

[kbhearn]

might be interesting to have the number of how many positions had at least one move of the category. are those 78130 legal SEE capture moves spread over 70k positions? 50k positions? Would give an idea how often a +SEE capture isn't best just because there was a better +SEE capture in that particular position.

Also interesting might be some sort of 'size of error' measurement for the failed moves.

[brtzsnr]

Similarly I was looking at which moves cause most fail-highs. The table below has the following columns:
hit ratio (hit / miss), attacker, victim, mvvlva score (specific to my engine, lower means searched later).

Code: Select all

0.024119543 -3  // remaining quiets
0.074027255 Queen Pawn 495                                                                                                         
0.100140676 Bishop Pawn 595                                                                                                        
0.124711886 Knight Pawn 600                                                                                                        
0.14264102 Rook Pawn 572                                                                                                           
0.15881053 Queen Knight 2415                                                                                                       
0.29876742 Rook Knight 2492                                                                                                        
0.33257645 Queen Bishop 2735                                                                                                       
0.37431753 Queen Rook 4207                                                                                                         
0.387258 Bishop Knight 2515                                                                                                        
0.38957718 Rook Bishop 2812                                                                                                        
0.40323406 Pawn Pawn 630                                                                                                           
0.7213379 Knight Knight 2520                                                                                                       
0.8817832 Knight Bishop 2840                                                                                                       
0.97507095 Bishop Bishop 2835                                                                                                      
1.0336807 Pawn Bishop 2870                                                                                                         
1.264169 Pawn Knight 2550                                                                                                          
1.6103945 -2   // killer move                                                                                                                    
1.6257391 King Bishop 2624                                     
1.8360018 Pawn Rook 4342 
1.8785022 Rook Rook 4284                                     
2.0860481 Bishop Rook 4307                                    
2.3786378 Knight Rook 4312                                     
2.9654443 Queen Queen 9135
3.4405515 Rook Queen 9212                                    
3.7926605 Knight Queen 9240                                   
4.2608695 Bishop Queen 9235                                   
4.341822 King Rook 4096  
4.463642 -1  // hash move
5.230321 Pawn Queen 9270            
6.443419 King Pawn 384                                        
14.311106 King Queen 9024                           
20.738932 King Knight 2304                      

Now, it's interesting that king attacking knight / queen / pawn / rook (but not bishop) has a very high chance of fail high. However, changing the move order to search these moves earlier is an Elo regression.

[nionita]

Thanks for sharing this!

It would be interesting to repeat this exactly for a few times (if it is not very time intensive) to see how the spread of those values are, because the 100k positions seem to be very few compared with what an engine sees in a search.

[matthewlai]

Similarly I was looking at which moves cause most fail-highs. The table below has the following columns:
hit ratio (hit / miss), attacker, victim, mvvlva score (specific to my engine, lower means searched later).

Code: Select all

0.024119543 -3  // remaining quiets
0.074027255 Queen Pawn 495                                                                                                         
0.100140676 Bishop Pawn 595                                                                                                        
0.124711886 Knight Pawn 600                                                                                                        
0.14264102 Rook Pawn 572                                                                                                           
0.15881053 Queen Knight 2415                                                                                                       
0.29876742 Rook Knight 2492                                                                                                        
0.33257645 Queen Bishop 2735                                                                                                       
0.37431753 Queen Rook 4207                                                                                                         
0.387258 Bishop Knight 2515                                                                                                        
0.38957718 Rook Bishop 2812                                                                                                        
0.40323406 Pawn Pawn 630                                                                                                           
0.7213379 Knight Knight 2520                                                                                                       
0.8817832 Knight Bishop 2840                                                                                                       
0.97507095 Bishop Bishop 2835                                                                                                      
1.0336807 Pawn Bishop 2870                                                                                                         
1.264169 Pawn Knight 2550                                                                                                          
1.6103945 -2   // killer move                                                                                                                    
1.6257391 King Bishop 2624                                     
1.8360018 Pawn Rook 4342 
1.8785022 Rook Rook 4284                                     
2.0860481 Bishop Rook 4307                                    
2.3786378 Knight Rook 4312                                     
2.9654443 Queen Queen 9135
3.4405515 Rook Queen 9212                                    
3.7926605 Knight Queen 9240                                   
4.2608695 Bishop Queen 9235                                   
4.341822 King Rook 4096  
4.463642 -1  // hash move
5.230321 Pawn Queen 9270            
6.443419 King Pawn 384                                        
14.311106 King Queen 9024                           
20.738932 King Knight 2304                      

Now, it's interesting that king attacking knight / queen / pawn / rook (but not bishop) has a very high chance of fail high. However, changing the move order to search these moves earlier is an Elo regression.

It's really good that you have hash move and killers as well! I didn't include anything related to search, but that's very useful information.

[matthewlai]

might be interesting to have the number of how many positions had at least one move of the category. are those 78130 legal SEE capture moves spread over 70k positions? 50k positions? Would give an idea how often a +SEE capture isn't best just because there was a better +SEE capture in that particular position.

That is a very good point. It's something I wondered about, too. I'll see if I can do something about that tonight.

Also interesting might be some sort of 'size of error' measurement for the failed moves.

Not sure what you meant by this?

[matthewlai]

Thanks for sharing this!

It would be interesting to repeat this exactly for a few times (if it is not very time intensive) to see how the spread of those values are, because the 100k positions seem to be very few compared with what an engine sees in a search.

It only takes a few minutes. I'll try using more positions tonight.

[brtzsnr]

I realized that the previous numbers were a bit misleading. Hitratio was very much dependent on the previous moves and since King/Pawn was searched last it happened that all threats where already gone.

I redid the stats on ECM to depth 8, this time forcing the (attacker/victim) pair to be the first move (after hash). The order seems to be Queen, Rook, Knight ~= Bishop, Pawns. I need to redo it for a more representative sample.

Code: Select all

ATT.    VIC.      HITS    MISSES   HITRATIO
King    Queen     202530  27222    0.8815157212994882
Queen   Queen     449395  72530    0.8610336734205106
Knight  Queen     180426  30874    0.8538854708944629
Bishop  Queen     180076  30931    0.853412446032596
Rook    Queen     310175  62615    0.8320368035623273
Pawn    Queen     193730  42412    0.8203962022850657
King    Rook      121755  39956    0.7529172412513682
King    Bishop    91730   34637    0.7259015407503542
Pawn    Rook      105853  46658    0.6940679688678194
Knight  Rook      138692  64813    0.6815164246578708
Bishop  Rook      162420  80305    0.669152332887012
Rook    Rook      321478  170999   0.6527776931714577
Knight  Knight    154596  87334    0.6390112842557765
Pawn    Knight    188322  110947   0.6292733293458393
King    Pawn      39308   23690    0.6239563160735262
Bishop  Bishop    155605  94499    0.6221611809487253
King    Knight    57235   35320    0.61838906596078
Pawn    Bishop    133620  88327    0.6020356211167531
Knight  Bishop    164606  114800   0.589128365174692
Queen   Rook      306632  294480   0.5101079332969564
Bishop  Knight    231998  241062   0.49041981989599626
Queen   Bishop    208434  249853   0.4548110681734372
Rook    Bishop    203912  257114   0.4423004342488276
Pawn    Pawn      289850  369029   0.43991385368178376
Rook    Knight    196056  284013   0.4083912937515232
Queen   Knight    240910  421699   0.3635779169917704
Queen   Pawn      768926  1704098  0.3109254095390906
Rook    Pawn      388256  897916   0.30186942337416767
Bishop  Pawn      427715  1094766  0.2809328983415885
Knight  Pawn      367179  968707   0.2748580342933454
King    NoFigure  381806  1957235  0.16323185442238936
Knight  NoFigure  102721  1759826  0.05515082303963336
Pawn    NoFigure  108444  2646546  0.0393627563076454
Bishop  NoFigure  93252   2333081  0.03843330655767366
Queen   NoFigure  148602  4013388  0.03570455479229888
Rook    NoFigure  125211  4108389  0.029575538548752833

[bob]

I took 100000 random positions from the CCRL PGN dump, did a fast search on each of them, and randomly selected an internal node from each search (more or less). This gives me a collection of positions uniformly drawn from the searches, where the search had to order moves.

Then I did another fast search using each internal node as root, to find the best move from the internal node.

The goal is to compute some statistics and see if there's any insight that can be used in move ordering and (even more importantly for me) prior probability estimation.

I created a bunch of filters, and kept statistics about moves that match each filter. For each of the filter below, "best" is the number of times a move matching the filter is the best move, "legal" is the number of times a move matching the filter is legal, and "scaled" is how frequent a move matching the filter turns out to be the best, scaled to uniform probability.

For example, scaled = 1 means a move matching the filter would have 1/30 the probability of being best, if there are 30 legal moves.

Some results:

1. captures and non-captures with positive, 0, and negative SEE -

Code: Select all

+SEE captures: 
best: 38573	legal: 78130	scaled: 7.96696
=SEE captures: 
best: 7132	legal: 25675	scaled: 8.39814
=SEE non-captures: 
best: 51063	legal: 1857763	scaled: 0.770027
-SEE captures: 
best: 1079	legal: 113573	scaled: 0.31697
-SEE non-captures: 
best: 2153	legal: 769055	scaled: 0.0873344

Here we see that +SEE captures are obviously very likely to be good, but surprisingly, neutral captures are even more likely to be good. We also see that -SEE captures have higher probability than -SEE non-captures (throwing away pieces). The probability for losing captures is actually surprisingly high (almost 1/2 the probability for neutral non-captures).

2. Broken down by piece type:

Code: Select all

iece Types (+SEE):
K:
best: 3342	legal: 5823	scaled: 2.44043
Q:
best: 6819	legal: 14534	scaled: 9.4128
R:
best: 8469	legal: 15945	scaled: 9.71956
N:
best: 5181	legal: 12108	scaled: 9.64009
B:
best: 5641	legal: 12055	scaled: 9.92174
P:
best: 9121	legal: 17665	scaled: 11.8489

Piece Types (=SEE):
K:
best: 7664	legal: 266165	scaled: 0.490375
Q:
best: 8991	legal: 307500	scaled: 0.995242
R:
best: 11726	legal: 456309	scaled: 0.791842
N:
best: 9318	legal: 216618	scaled: 1.3492
B:
best: 8547	legal: 268396	scaled: 0.976824
P:
best: 11949	legal: 368450	scaled: 0.996478

Piece Types (-SEE):
K:
no match
Q:
best: 217	legal: 245682	scaled: 0.0301311
R:
best: 539	legal: 201789	scaled: 0.0789882
N:
best: 619	legal: 135626	scaled: 0.146236
B:
best: 446	legal: 178976	scaled: 0.0802111
P:
best: 1411	legal: 120555	scaled: 0.331534

Here we see that +SEE captures are very good for all pieces except the king. Since the king cannot be captured, these are essentially the king capturing undefended pieces.

When we go to =SEE, everything is pretty close to 1, except for kings, which is at 0.5.

For -SEE, it's basically never a good idea to sacrifice a queen, rook, or bishop. Knight sacrifices are slightly better. Pawn sacrifices are surprisingly high at 0.33, which is about 1/3 the probability of normal pawn moves.

3. Promotions:

Code: Select all

Queen promotions:
best: 502	legal: 1318	scaled: 8.36711

Under-promotions:
best: 30	legal: 3954	scaled: 0.166675

Queen promotions are about as good as +SEE captures. Under-promotions are pretty low.

------------------------------------------------------------------------------------
I'll be generating more statistics. In particular, I want to see how game phase changes things.

I now have a system that's very easy to write filters for, and do and/or/xor with the filters. Any suggestions? What would you like to see?

Personally, I have been studying this issue for a LONG time now. I have specifically been looking at the history counters and how they can be updated, and how reliable they are. Bottom line is "they are almost random noise". IE better moves do often have better history counter values, but the actual value itself doesn't correlate with anything I can find doing statistical analysis. I'd love to be able to find something that will produce numbers that can directly influence reductions and pruning, but I have found no such approach. The idea that several use today came from my testing this stuff when Fruit first came out (so-called history pruning back then). I hit upon the idea of increasing the counter on a fail high, and then later I added the idea of reducing all the counters for moves that failed low before the move that failed high. But it STILL gives lousy values if you just look at the numbers.

Seems to me there SHOULD be a way to get an idea of how good or bad a move is on an absolute scale, but so far - not that I have found.

I continue to look, but I am afraid it is similar to a Sasquatch hunt.. Lots of places to look, but nothing to find.

[kbhearn]

Also interesting might be some sort of 'size of error' measurement for the failed moves.

Not sure what you meant by this?

Given that in most positions you're not actually looking for a best move but rather any cut move, a move that's 0.01 worse than best move is still very likely a successful first try while a move that's say a pawn or more worse than the best is more likely to be the difference between cut and not cut. I'm not sure what measures would be most informative though to represent information on that distribution over many positions, maybe just binning the size of blunder into 'small', 'medium', 'large'