Move ordering statistics

[sandermvdb]

I was wondering how good the move ordering of my engine is. So therefore I have gathered statistics about the bestmove move number; is the bestmove the first move, the second move, etc... ?
These statistics are from the starting position up to ply 12.

My engine has the following move ordering implementation:
1) hashmove
2) winning captures (SEE-score > -50)
3) killer-moves
4) quiet-moves, using the history heuristic
5) losing captures (SEE-score < -50)

The evaluation function does not recognize hanging pieces. These will be found the next ply so this is bad for move ordering.
SEE does not recognize illegal moves (pinned-pieces), again bad for move ordering.

Image:
https://drive.google.com/file/d/0BxPfDW ... 9UWVk/view

The following can be seen in the data:
- the chart of the EXACT moves is not 100% accurate because of the 0 values
- total number of moves LOWER > UPPER > EXACT
- move ordering for LOWER moves > EXACT > UPPER
- the rise of UPPER-moves between move 20 and 45 are caused by the sorting of loosing captures. If I disable this, this peak is not seen, but the total number of nodes is higher (needs tuning?)
- smetimes the bestmove is movenumber 50!

What do you think of these numbers? I am still not 100% familiar with CUT-nodes, ALL-nodes, fail-high fail-low, etc...

Data:

Code: Select all

    EXACT        UPPER          LOWER 
ply    #    %      #      %       #      %
1    182  57,24  83321  43,81  573940  94,7
2     57  17,93  31173  16,39   21999   3,63
3     20   6,29  21524  11,32    4744   0,79
4     11   3,46  13349   7,02    1779   0,3
5     13   4,09   8137   4,28    1026   0,17
6      2   0,63   3590   1,89     667   0,12
7      5   1,58   2139   1,13     383   0,07
8      4   1,26   1380   0,73     242   0,04
9      1   0,32    908   0,48     172   0,03
10     2   0,63    761   0,41     152   0,03
11     0   0       647   0,35      84   0,02
12     4   1,26    599   0,32      90   0,02
13     0   0       482   0,26      84   0,02
14     1   0,32    483   0,26      81   0,02
15     0   0       406   0,22      50   0,01
16     0   0       405   0,22      47   0,01
17     1   0,32    375   0,2       53   0,01
18     0   0       350   0,19      55   0,01
19     1   0,32    331   0,18      42   0,01
20     1   0,32    322   0,17      52   0,01
21     1   0,32    418   0,22      34   0,01
22     0   0       454   0,24      28   0,01
23     0   0       533   0,29      20   0,01
24     2   0,63    625   0,33      26   0,01
25     3   0,95    684   0,36      31   0,01
26     1   0,32    784   0,42      16   0,01
27     0   0       865   0,46      13   0,01
28     2   0,63   1064   0,56      13   0,01
29     2   0,63   1171   0,62      16   0,01
30     1   0,32    998   0,53      18   0,01
31     0   0      1167   0,62      15   0,01
32     0   0      1153   0,61      15   0,01
33     0   0      1013   0,54      18   0,01
34     0   0      1064   0,56      13   0,01
35     1   0,32    970   0,51       9   0,01
36     0   0      1010   0,54       7   0,01
37     0   0       987   0,52       7   0,01
38     0   0       881   0,47       7   0,01
39     0   0       805   0,43       7   0,01
40     0   0       713   0,38       8   0,01
41     0   0       619   0,33      12   0,01
42     0   0       482   0,26       4   0
43     0   0       319   0,17       3   0
44     0   0       288   0,16       3   0
45     0   0       185   0,1        1   0
46     0   0       112   0,06       1   0
47     0   0        62   0,04       1   0
48     0   0        44   0,03       0   0
49     0   0        31   0,02       0   0
50     0   0        18   0,01       0   0
51     0   0         2   0,01       0   0
52     0   0         1   0          0   0
53     0   0         3   0,01       0   0

[sandermvdb]

In the data table, ply should be movenumber of course!

[abulmo2]

There is no best move on all nodes, when the score <= alpha, (UPPER), so the quality of move ordering is not important here.
On cut nodes, (when score >= beta) the best move is any move good enough to get a cut off. So a better move ordering in cut nodes is logical as there are several candidates as best moves.
On exact node, there is a single best move, equally strong moves excepted. So the best statistics is got on such nodes.

[pkumar]

There is no best move on all nodes, when the score <= alpha, (UPPER), so the quality of move ordering is not important here.

Is it possible that with fail soft there is a better than average chance of success with the best score move in all nodes? The chances are low anyway - no harm in trying.

[Evert]

There is no best move on all nodes, when the score <= alpha, (UPPER), so the quality of move ordering is not important here.

Is it possible that with fail soft there is a better than average chance of success with the best score move in all nodes? The chances are low anyway - no harm in trying.

Move ordering in an ALL-node is irrelevant. You will always search all of them anyway.
The kicker, of course, is that you don't know that a node is an ALL-node until after you've searched all moves. If your move ordering is good, then "late" moves are unlikely to be good, and the probability of the current node being an ALL-node increases. That's the idea behind late-move reductions.
You may get better bounds from fail soft, but that doesn't seem to make much difference in practice.

[hgm]

Is it possible that with fail soft there is a better than average chance of success with the best score move in all nodes? The chances are low anyway - no harm in trying.

It is a tricky thing. If a previous, lower-depth search has shown that the upper score bound on a move is very much below alpha, trying that move early seems a waste of time. So you might want to postpone its search to after having searched the moves that had upper bounds that wereclose to alpha. Which could also be arbitrarily poor, but at least might have been close, and might only need a small score fluctuation to now fail high.

Problem is that in alpha-beta, even with fail soft, almost all upper bounds are very close to alpha. Alpha-beta search is very lazy, and works just hard eough topush the score marginally below alpha. (Which is why it is so efficient.)

So it is largely a moot point; the best upper bound will only be marginally better than the other upper bounds, and the static ordering probably gives you a more reliable indication of what move might be good than the upper bounds.

One thought I had was this, though: if a hash move fails low, you knowit can only have become hash move by virtue of all moves before it in the static move ordering failing even lower. So does it really make sense to use the standard static ordering which starts with all those previously rejected moves? At least the moves that would normally come after it have not been searched before, because the hash move cut them off at that time. So there could be much better moves amongst those, while we settled for a move that marginally did the job.

[Volker Annuss]

Move ordering in an ALL-node is irrelevant. You will always search all of them anyway.

I read that many times here and I always thought it is true. But now I think it is not. It should be advantageous to keep moves together, that are refuted by the same killer move.

[Evert]

Move ordering in an ALL-node is irrelevant. You will always search all of them anyway.

I read that many times here and I always thought it is true. But now I think it is not.

It is true by definition. An ALL node is a node where you search all moves because none of them cause a cut-off.

[Volker Annuss]

Move ordering in an ALL-node is irrelevant. You will always search all of them anyway.

I read that many times here and I always thought it is true. But now I think it is not.

It is true by definition. An ALL node is a node where you search all moves because none of them cause a cut-off.

It is true by definition, that in an all-node you have to search all moves.

Nevertheless move ordering in an all-node is not irrelevant. Look at this position.
[d]r4r1k/pp3pp1/5n1p/5Q2/8/3B4/PP4PP/R5K1 b - - 0 1[/d]
When this position is an all-node most knight moves are refuted by Qh7#. (Let's ignore Ne5.)

When searching the first knight move, Qh7# becomes a killer move. When you search all other knight moves immediately one after the other, they all are immediately refuted by the killer move Qh7#, which gives a small search tree.

But when you sort the moves in a different order, say Ng8, Rb8, Nh7, Rc8, Nh5, b5 ... the mating move may no longer be the first killer move and the search tree becomes larger.