Best move statistics

[brtzsnr]

Same stats for 5000 random positions

Code: Select all

ATT.    VIC.      HITS    MISSES   HITRATIO                                                                                        
King    Queen     921007   95538     0.9060169495693747                                                                            
Bishop  Queen     365576   58208     0.8626470088535669                                                                            
Queen   Queen     1183900  200700    0.8550483894265491                                                                            
Rook    Queen     672870   114148    0.8549613858895222                                                                            
King    Rook      822301   145475    0.8496811245577489                                                                            
Knight  Queen     367948   73033     0.8343851549159714                                                                            
Pawn    Queen     502613   101242    0.8323405453295907                                                                            
Rook    Rook      943630   251719    0.789417985876928                                                                             
King    Bishop    329449   101754    0.7640229775766866                                                                            
Bishop  Rook      407398   156492    0.722477788221107                                                                             
Knight  Rook      310714   129821    0.7053105882619997                                                                            
Bishop  Bishop    363564   152034    0.7051307413915492                                                                            
Knight  Knight    322820   146187    0.6883052918186722                                                                            
King    Knight    324333   155161    0.6764067954969196                                                                            
Pawn    Knight    472964   247346    0.6566117366134026                                                                            
Knight  Bishop    336336   187505    0.6420574181860527                                                                            
Pawn    Bishop    312904   185288    0.6280791341490831                                                                            
Pawn    Rook      329419   198708    0.6237495905340951                                                                            
Queen   Rook      656000   422984    0.6079793583593455                                                                            
King    Pawn      504173   402136    0.5562926110189792                                                                            
Rook    Bishop    483547   441199    0.5228970982302167                                                                            
Queen   Bishop    453546   415046    0.5221623040506935                                                                            
Bishop  Knight    434447   401141    0.519929678262493                                                                             
Pawn    Pawn      1176361  1086611   0.5198301172086972                                                                            
Rook    Knight    366115   386841    0.4862369115858032                                                                            
Queen   Knight    509734   689299    0.4251209099332545                                                                            
Rook    Pawn      1426638  2478331   0.3653391358548557                                                                            
Knight  Pawn      951070   2017155   0.3204170842843787                                                                            
Bishop  Pawn      941146   2136929   0.3057579818555428                                                                            
Queen   Pawn      1578258  3738206   0.2968623506149952                                                                            
King    NoFigure  6315100  17624667  0.26379120565375597                                                                           
Pawn    NoFigure  1789633  11838311  0.1313208360703566                                                                            
Knight  NoFigure  544738   7952203   0.06410989554946891                                                                           
Bishop  NoFigure  564219   9808552   0.05439424045898632                                                                           
Rook    NoFigure  994218   22719152  0.04192647438976409                                                                           
Queen   NoFigure  868406   28597419  0.029471633663744355

[matthewlai]

Same stats for 5000 random positions

Code: Select all

ATT.    VIC.      HITS    MISSES   HITRATIO                                                                                        
King    Queen     921007   95538     0.9060169495693747                                                                            
Bishop  Queen     365576   58208     0.8626470088535669                                                                            
Queen   Queen     1183900  200700    0.8550483894265491                                                                            
Rook    Queen     672870   114148    0.8549613858895222                                                                            
King    Rook      822301   145475    0.8496811245577489                                                                            
Knight  Queen     367948   73033     0.8343851549159714                                                                            
Pawn    Queen     502613   101242    0.8323405453295907                                                                            
Rook    Rook      943630   251719    0.789417985876928                                                                             
King    Bishop    329449   101754    0.7640229775766866                                                                            
Bishop  Rook      407398   156492    0.722477788221107                                                                             
Knight  Rook      310714   129821    0.7053105882619997                                                                            
Bishop  Bishop    363564   152034    0.7051307413915492                                                                            
Knight  Knight    322820   146187    0.6883052918186722                                                                            
King    Knight    324333   155161    0.6764067954969196                                                                            
Pawn    Knight    472964   247346    0.6566117366134026                                                                            
Knight  Bishop    336336   187505    0.6420574181860527                                                                            
Pawn    Bishop    312904   185288    0.6280791341490831                                                                            
Pawn    Rook      329419   198708    0.6237495905340951                                                                            
Queen   Rook      656000   422984    0.6079793583593455                                                                            
King    Pawn      504173   402136    0.5562926110189792                                                                            
Rook    Bishop    483547   441199    0.5228970982302167                                                                            
Queen   Bishop    453546   415046    0.5221623040506935                                                                            
Bishop  Knight    434447   401141    0.519929678262493                                                                             
Pawn    Pawn      1176361  1086611   0.5198301172086972                                                                            
Rook    Knight    366115   386841    0.4862369115858032                                                                            
Queen   Knight    509734   689299    0.4251209099332545                                                                            
Rook    Pawn      1426638  2478331   0.3653391358548557                                                                            
Knight  Pawn      951070   2017155   0.3204170842843787                                                                            
Bishop  Pawn      941146   2136929   0.3057579818555428                                                                            
Queen   Pawn      1578258  3738206   0.2968623506149952                                                                            
King    NoFigure  6315100  17624667  0.26379120565375597                                                                           
Pawn    NoFigure  1789633  11838311  0.1313208360703566                                                                            
Knight  NoFigure  544738   7952203   0.06410989554946891                                                                           
Bishop  NoFigure  564219   9808552   0.05439424045898632                                                                           
Rook    NoFigure  994218   22719152  0.04192647438976409                                                                           
Queen   NoFigure  868406   28597419  0.029471633663744355

That is really cool! I wonder if there is an even stronger correlation between hit rate and SEE (vs hit rate and MVV/LVA).

[matthewlai]

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'

Ah I see what you mean now. I wonder about that often, too, but I still don't really know what to do with it.

There's non-linearity, too.

If you are winning by 800 centipawns, losing 100 is not a big deal. If it's an even game, losing 100 is a big deal.

[matthewlai]

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.

It does seem like history counters are basically random noise. I wonder if (back when they helped), they were basically discovering static information that doesn't change between games. In fact, that's what motivated this study - to see if we can get that information in explicit form.

We do already have some very good knowledge - for example, we know that positive and neutral SEE captures are about 8x as likely to be the best move as quiet, non-losing moves, and about the same ratio from quiet non-losing moves to negative SEE moves (except for negative SEE captures, which are better than non-captures).

The problem is there's no good way to use that knowledge.

Right now most engines only use that knowledge indirectly through LMR + move ordering. If you reduce after 3rd move for example, in most positions, you are basically reducing all quiet moves. This makes sense when you have a position with a hash move and maybe 1 or 2 +SEE captures, but doesn't make any sense when all moves are quiet.

It would be more principled to explicitly reduce quiet moves and -SEE moves instead. The only problem is when there are only quiet moves. Then do you reduce them all, or not reduce them? Conversely, if there are multiple +SEE moves, do you search them all to high depth?

There is no clean solution in a depth-based search framework, but can be solved cleanly in a probability-based one, and that's what I am trying to do. I just have to assign each move a score proportional to their probability of being best, and then renormalize so they sum to one. This is a clean, principled, and theoretically sound approach, to achieve more or less what LMR achieves, hopefully more accurately.

Even if we have the knowledge, how would you use them in a depth-based search? Let's say you know there are two classes of moves, A and B, and moves in class A are twice as likely to be best moves than moves in class B, how can you use that knowledge? You can change their depths, but by how much? Let's say you decide to reduce moves in class B by one ply -

If you are doing a depth=3 search and have
ABBB, you can search them to d=3, d=2, d=2, d=2.

Now what if you have AAAB? d=3, d=3, d=3, d=2.

But that doesn't make sense, because the probability of each move in class A being the best is now reduced, just because there are so many moves in class A. Why are we spending more total time in this parent node now, even though there's still just one best move?

LMR is a workaround for this, but it's a pretty crude one. It makes the assumption that the "probability decay" curve in each node to be the same. That is obviously not true. AAAAB and ABBBB should be reduced very differently.

The fact that extending and reducing children affect total time spent in the parent node is a (or even "the") fundamental problem in depth-based search. When we decide a node is worth x amount of time, the distribution of moves below that node shouldn't affect it, since we know there is exactly one best move among them.

I believe the fundamentally correct solution is to stop using depths, and start using probabilities instead. Everything is nice and logical with probabilities. And, as shown by Giraffe, it's perfectly possible to make a chess engine without using depth-based search.

Depth-based search made sense back in the days with no extensions/reductions heuristics, and we had uniform-depth trees. When we start playing with essentially probabilities, probabilistic search is much more natural. We should stop putting more and more patches and hacks into the depth-based framework, and start exploring totally different approaches, even if they may take a while to catch up.

[matthewlai]

Same filters, with 500k positions.

Code: Select all

+SEE captures: 
best: 194422	legal: 393661	scaled: 8.05807
=SEE captures: 
best: 35468	legal: 129082	scaled: 8.32042
=SEE non-captures: 
best: 254011	legal: 9295146	scaled: 0.753209
-SEE captures: 
best: 5089	legal: 568244	scaled: 0.298848
-SEE non-captures: 
best: 11010	legal: 3856477	scaled: 0.0888461

Piece Types (+SEE):
K:
best: 16556	legal: 28758	scaled: 2.49482
Q:
best: 34086	legal: 73197	scaled: 9.43191
R:
best: 43185	legal: 81085	scaled: 9.83191
N:
best: 26157	legal: 60743	scaled: 9.62502
B:
best: 29011	legal: 61238	scaled: 10.1661
P:
best: 45427	legal: 88640	scaled: 11.5961

Piece Types (=SEE):
K:
best: 37594	legal: 1332817	scaled: 0.48204
Q:
best: 44721	legal: 1532338	scaled: 0.994136
R:
best: 58151	legal: 2281240	scaled: 0.784854
N:
best: 46884	legal: 1089186	scaled: 1.35106
B:
best: 43045	legal: 1348632	scaled: 0.981701
P:
best: 59084	legal: 1840015	scaled: 0.987765

Piece Types (-SEE):
K:
no match
Q:
best: 1027	legal: 1228246	scaled: 0.0285149
R:
best: 2552	legal: 1013905	scaled: 0.0745581
N:
best: 3093	legal: 680944	scaled: 0.145958
B:
best: 2274	legal: 898611	scaled: 0.0814202
P:
best: 7153	legal: 603015	scaled: 0.335464

Queen promotions:
best: 2465	legal: 6642	scaled: 8.26808

Under-promotions:
best: 159	legal: 19926	scaled: 0.17778

Looks like the values are pretty stable.

[kbhearn]

perhaps breaking out the surprising results by other static features of the move may be interesting.

obvious examples that i assumed were just not that common and that's why they're ignored:

- removes a defender of an attacked piece/pawn (or perhaps more complicated a notable square like a knight outpost)
- opens a discovered attack
- recapture would double a pawn (perhaps may require more specificity - king shield pawn or capture happening on half-open file)
- checks before recapture of material either as a desperado to get something for a hanging piece or to remove a piece from being en prise

If you're testing enough of these sorts of categories maybe -SEE moves could be ignored even moreso than they already are through LMR and being booted to the end of the move list. And perhaps in some case good -SEE moves could be tried much earlier than they are now and remove some of the blindness engines have at low depths to long sequences of such moves.

edit: would of course need the 'none of the above' category as well since some moves would fit into multiple categories

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

Here we go:

Code: Select all

Highest SEE captures:
best: 42965	legal: 81338	scaled: 8.60188
Non-highest SEE captures:
best: 937	legal: 11729	scaled: 2.43837

The probability for highest SEE captures are actually not very different from the probability for +SEE captures in general. I guess not many positions actually have multiple +SEE captures (or they have the same SEE).

The prob for non-highest SEE captures is still surprisingly high.

[matthewlai]

Looking only at positions with only one highest SEE capture, the probability increases. So it looks like there are significant number of positions with multiple highest SEE captures (most commonly pawns probably).

Code: Select all

Highest unique SEE captures:
best: 25921	legal: 34674	scaled: 10.2058

[matthewlai]

perhaps breaking out the surprising results by other static features of the move may be interesting.

obvious examples that i assumed were just not that common and that's why they're ignored:

- removes a defender of an attacked piece/pawn (or perhaps more complicated a notable square like a knight outpost)
- opens a discovered attack
- recapture would double a pawn (perhaps may require more specificity - king shield pawn or capture happening on half-open file)
- checks before recapture of material either as a desperado to get something for a hanging piece or to remove a piece from being en prise

If you're testing enough of these sorts of categories maybe -SEE moves could be ignored even moreso than they already are through LMR and being booted to the end of the move list. And perhaps in some case good -SEE moves could be tried much earlier than they are now and remove some of the blindness engines have at low depths to long sequences of such moves.

edit: would of course need the 'none of the above' category as well since some moves would fit into multiple categories

This is becoming complicated very fast . The dimensionality just keeps increasing.

I think I'll focus on one piece type at a time for now. Hopefully that will be more manageable.

[ymatioun]

I have done something similar, but limited to Q search only. Then you only have good or equal captures. I constructed a table indexed by attacker and by victim, and use that for move ordering instead of the usual MVV/LVA. That approach helped, but only slightly.