Better move ordering statistics

[Gian-Carlo Pascutto]

A common method of measuring move ordering performance is to check the ration "fail high on first move / fail high".

Several people have correctly observed that this is in fact a pretty bad way to measure, because there might be many moves that would fail high, and in that case you want the smallest tree.

It seems to me that the only kind of positions where you can really measure this is at PV nodes.

So, the move ordering performance would be: "number of times the first move at a PV node was indeed the best move".

There might be a sensible definition at alpha nodes too; if we have a fail high there, it should be at the first move, and no other move should fail high.

It's funny that the only places where you can measure is where most people don't do it.

Did anyone measure this way? What rates do you get in what positions?

[Steve Maughan]

Yes I've tossed out the fail high first statistics - I'm in the process of implementing a better statistic in Monarch but one that is more difficult to implement. I call it the percentage of waisted nodes. Basically if you make a Beta cutoff after the first move you have "waisted nodes" searching the tree associated with the earlier moves. The lower the percentage of these waisted nodes, the better the move ordering. Also this measure has the advantage that it gives credits to move ordering schemes that differ based on depth i.e. you may wish to spend more time doing fancy move ordering if the remaining depth is large. As I said the implementation is not straightforward since you do not want to double count the waisted nodes in the sub tree (or maybe you can just ignore the double counting problem?).

Any thoughts? Anyone already do this?

Steve

[H.G.Muller]

I think this is a very tricky issue, because it interacts with how you manipulate your window limits (i.e. do you do aspiration searches, or even an MTD(f) search).

If you search another move before the one causing the fail high, this need not be wasted effort: the first search might increase alpha a lot, so that the search on the failing move can be done with a much narrower window, making that subtree much more heavily pruned. In the end this might even save compared to searching the best move first! (But not if you would have guessed the higher alpha even before searching the earlier move, in an aspiration scheme.)

Effects like this might be especially important in programs that do lots of extensions/reductions, making for very uneven tree depth. If the failing move leads to a very deep subtree, great savings would occur if you could narrow the window first by upping alpha through another, non-failing move that only needs a shallow search. But even for a fixed-depth tree, such effects might occur because of the branching factor. A subtree that starts with the exchange of Q+R (e.g. 1. QxR, QxQ; 2. RxQ BxQ) will, after the semi-forced and easily guessed first four moves have a much lower branching than a (slightly better) move that keeps the two Queens and Rooks on the board, and it probably pays off to search it first. I think humans do this too: first consider a quiet and possibly simplifying move to create a reference before you start thinking about the really tricky stuff.

[Steve Maughan]

If you search another move before the one causing the fail high, this need not be wasted effort

I agree that an earlier search can have *some* benefit but I think in *all* cases it would be better to search the move that gives the cutoff first. Effectively you're advocating sub-optimal move ordering.

...the first search might increase alpha a lot, so that the search on the failing move can be done with a much narrower window, making that subtree much more heavily pruned...

I would also add that the number of nodes where alpha is increased and there is then a subsequent beta cutoff is tiny (I'm guessing < 0.001%), at least for a PVS search.

Regards,

Steve

[Uri Blass]

A common method of measuring move ordering performance is to check the ration "fail high on first move / fail high".

Several people have correctly observed that this is in fact a pretty bad way to measure, because there might be many moves that would fail high, and in that case you want the smallest tree.

It seems to me that the only kind of positions where you can really measure this is at PV nodes.

So, the move ordering performance would be: "number of times the first move at a PV node was indeed the best move".

There might be a sensible definition at alpha nodes too; if we have a fail high there, it should be at the first move, and no other move should fail high.

It's funny that the only places where you can measure is where most people don't do it.

Did anyone measure this way? What rates do you get in what positions?

I never measured move ordering.

if I do a change in move ordering than testing if the change is good is simply by test suites.

If the result in test suites is better than probably the change is a good change.

Uri

[Steve Maughan]

if I do a change in move ordering than testing if the change is good is simply by test suites.

If the result in test suites is better than probably the change is a good change.

IMO test suites are a poor indicator of move ordering efficiency. If you look at checks early you'll probably do well in test but it may not be good for normal play.

Steve

[Uri Blass]

I do not agree about it.

I do not think that looking at checks earlier will improve results of test suites(espacially if we talk about hard test positions).

Note that I do not talk about easy WAC but about positions when the program need more time to find.

starting from checks may cause the program to search at least one ply less and even if the first move is check it is not going to cause the program to find it faster.

Note that I even did not try searching checks first because it does not seem logical to me and it is only a guess about what is going to happen if I do it.

The program may be faster in easy test positions but I do not talk about them and I do not care much if the program needs 1000 nodes to solve easy positions or 2000 nodes.

Uri

[H.G.Muller]

If you search another move before the one causing the fail high, this need not be wasted effort

I agree that an earlier search can have *some* benefit but I think in *all* cases it would be better to search the move that gives the cutoff first. Effectively you're advocating sub-optimal move ordering.

...the first search might increase alpha a lot, so that the search on the failing move can be done with a much narrower window, making that subtree much more heavily pruned...

I would also add that the number of nodes where alpha is increased and there is then a subsequent beta cutoff is tiny (I'm guessing < 0.001%), at least for a PVS search.

Well, I am advocating that some sub-optimal move orderings are better than others. Your truth that optimal move-ordering is best falls in the same category as "smoke detectors are a waste of money, it is better not to cause fires"... Rock climbers 'waste' a lot of effort hammering in anchors that they don't need to get to the top, to secure their savety lines. In an imperfect world you simply get better over-all performance by investing in precautions.

So in the case that the move ordering on ply 3 is perfect, there is indeed nothing to be gained by upping alpha on an earlier move in ply 1. None of the answers on ply 4 will be good enogh to cause a faiil high, even with the lower value of beta you will have their. Deep cutoffs will never occur if the move ordering is perfect. But in practice your engine suffers a lot if you don't implement them.

So searching a non-best but solid quiet move first on ply 1 should be seen as a precaution/insurance against the possibility that the engine will have trouble identifying the best continuation on ply 3 of what will eventually become the PV, in cases where you can effect the gain that makes this move the best one only by very secure play, while the rest ends in disaster. If insurance is cheep, its usually better to take it...

That it happens in a small fraction of the nodes does not mean anything: it happens on ply 2, where alpha is -inf in ordinary minimax, and any move will up it. Indeed a very small fraction of the nodes is on ply 2, but the whole tree is behind such nodes. In particular the position after the best ply-one move will carry a large part of the tree: if the move ordering is perfect in a tree with homogeneous branching it carries 50% of it! So if you can search that tree more efficiently because of the higher alpha you start with (as an aspiration search would do) the savings are very substantial, even if that were the only node for which this would happen in the whole tree.

In addition, if by choice you decide to sort some quiet solid moves before the suspected but tricky best one in cases where this will reduce the expected tree size, the percentage of course goes up. It is only so low because you biased your engine against this (perhaps biasing it towards larger average tree size) that the percentage of nodes were this happens is so low...

[Steve Maughan]

[snip]
Well, I am advocating that some sub-optimal move orderings are better than others.
[snip]

Hmmmmm, in classical alpha-beta (or PVS) it's never better to search a sub-optimal move first when searching to a fixed depth - that's the whole point of alpha-beta. Maybe you're alluding to Internal Iterative Deepening (IID) where you search the position to a lower depth before doing the full depth search - this is certainly beneficial.

Regards,

Steve

[H.G.Muller]

But never better than what?

Let me give this simple (counter)example to your statement:

Code: Select all

    ----a +1   Minimax
    |---b +1
----A---c +1
|    /--d -1
R---B---e -1
|    \--f -1
|---C---g -3
|   |---h -3
|   ----j -3
----D---k  0


    ----a +1   Alpha-Beta
    |---b +1   with perfect move ordering
----A---c +1
|    /--d -3
R---B-x
|    \x
|---C---g -3
|   |-x
|   --x
----D---k  0


    ----d -3   Alpha-Beta
    |---e -3   with 1 wrong move sorted in front for ply 1
----B---f -3
|    /--a +1
R---A---b +1
|    \--c +1
|---C---g -3
|   |-x
|   --x
----D---k  0


----D---k  0   Alpha-Beta
|   ----d -3   with simple sub-optimal move sorted in front
|   |-x      
----B-x
|    /--a +1
R---A---b +1
|    \--c +1
----C---g -3
    |-x
    --x


A 2-ply search tree sprouts from root position R. From R there is one move that leads to a much simplified position D, from where each side has only very few moves (in this example only one). Many other moves, however, keep the situation complicated, and in these complex positions many moves are possible. (Many = three here, for ease of drawing.)

Without any cutoffs, there are 10 end leaves after 2 ply (a...k). With alpha-beta and perfect move ordering, the best move - leading to position A - is searched first, and all replies (a,b,c) have to be considered to conclude that its score is +1. When moves (to positions) B and C are tried after that, the first reply (d and g, respectively) is enough to refute them compared to the +1 score, and cause a fail high on ply 2. So e,f,h and j are not searched. In the D branch there is nothing to cut off, because it was the last (and only) reply that caused the fail high.

In the third case, the move ordering is imperfect, and B is sorted before A in ply 1. So now B is best at the moment it is searched, and all replies (d,e,f) hae to be searched to conclude that its score is -3. To find that A supersedes B as best move, all its replies (a,b,c) have to be searched on ply 2. So the only fail highs now occur on searching C (h,k).

Now suppose I intentionally sort move D in front, not based on its suspected score, but on the (easily recognized) property that it leads to a sub-tree with small branching. Then the move B, that was erroneously picked as next one to search, will see a fail high in the first considered reply (d), so that 2 branches (e,f) are cut that were not cut in the third case. The tree is 25% smaller!

Conclusion: one more sub-optimal move sorted in front makes the (fixed-depth) tree smaller (by 2 end leaves).

Of course 'many'could have meant 30 in stead of 3, so that 29 leaves were pruned from the tree in stead of 2. And the drawn part of the tree could have been the first two ply of an 8-ply search, so that every end-leave that was cut was in fact a 6-ply subtree with each thousands of end leaves.

I could give you many more examples, also where the move ordering on ply 0 was perfect, where sorting the suboptimal D in front of the otherwise perfectly ordered A,B,C would result in savings on ply 4 (in the subtree starting at a) because of imperfect ordering of the moves on ply 3. But they are a bit difficut to draw, because they need 4 plies...

[Steve Maughan]

It seems that the formatting got messed up - hopefully I've corrected it at the end of my message.

But never better than what?

Sub-optimal move ordering never gives a tree size small than optimal move ordering. Of course some sub-optimal more ordering schemes are better than others - in your case (4) is better than (3). Note that (4) is not better than (2) and is only equal in nodes due to the fact that (D) has only one sub node.

Anyway, enough - if you don't want to use the "Wasted Nodes" statistic all is well and good. You certainly haven't convinced me that there is anything wrong with it as a measure of move ordering fitness.

Regards,

Steve

A 2-ply search tree sprouts from root position R. From R there is one move that leads to a much simplified position D, from where each side has only very few moves (in this example only one). Many other moves, however, keep the situation complicated, and in these complex positions many moves are possible. (Many = three here, for ease of drawing.)

Without any cutoffs, there are 10 end leaves after 2 ply (a...k). With alpha-beta and perfect move ordering the best move, leading to position A, is searched first, and all answers (a,b,c) have to be considered to conclude that its score is +1. When moves (to positions) B and C are tried after that, the first answer (d and g, respectively) is enough to refute them compared to the +1 score, and cause a fail high on ply 2. So e,f,h and j are not searched. In the D branch there is nothing to cut off, because it was the last (and only) reply that caused the fail high.

In the third case, the move ordering is imperfect, and B is sorted beore A in ply 1. So now B is best at the moment it is searched, and all replies (d,e,f) hae to be searched to conclude that its score is -3. To find that A supersedes B as best move, al its replies (a,b,c) have to be searched on ply 2. So the only fail highs now occur on searching C (h,k).

Now suppose I intentionally sort move D in fromt, not based on its suspected value, but on the (easily recognized) property that it leads to a sub-tree with small branching. Then the move B, that was erroneously picked as next to search, will see a fail high in the first considered reply (d), so that 2 branches (e,f) are cut that were not cut in the third case.

Conclusion: one more sub-optima move sorted in front makes the (fixed-depth) tree smaller (by 2 end leaves).

Of course 'many'could have meant 30 in stead of 3, so that 29 leaves were pruned from the tree in stead of 2. And the drawn part of the tree could have been the first two ply of an 8-ply search, so that every end-leave that was cut was in fact a 6-ply subtree with each thousands of end leaves.

I could give you many more examples, also where the move ordering on ply 0 was perfect, where sorting the suboptimal D in front of the otherwise perfectly ordered A,B,C would result in savings on ply 4 (in the subtree starting at a) because of imperfect ordering of the moves on ply 3. But they are a bit difficut to draw, because they need 4 plies...

[Uri Blass]

It seems that the formatting got messed up - hopefully I've corrected it at the end of my message.

But never better than what?

Sub-optimal move ordering never gives a tree size small than optimal move ordering.

This is wrong

Imagine search to depth 3 white to move

Let denote the first move of every player by 0 and the second best move by 1.

you have
eval(000)=1 pawns for white
eval(001)=0 pawns for white
eval(10x)=2 pawns for black for 0<=x<=1)
eval(11)=0(stalemate)

optimal move ordering are means searching
000
001
100
101

non optimal move ordering means searching
000
001
11

to demonstrate it more clearly the minimax tree may be

1.e4 e5 2.Nf3(1 pawn for white)
1.e4 e5 2.Nc3 draw
1.d4 d5 2.c4 (2 pawns for black)
1.d4 d5 2.Nf3(2 pawns for black)
1.d4 Nf6 stalemate

optimal move ordering search

1.e4 e5 2.Nf3
1.e4 e5 2.Nc3
1.d4 d5 2.c4
1.d4 d5 2.Nf3

(1.e4 is better than d4 so not need to search more and 1...e5 is the only legal reply to 1.e4 in the example)

non optimal move ordering replace the last 2 lines by 1.d4 Nf6

1...Nf6 lead to stalemate when 1...d5 gives advantage for black so the program does not search best move first when it searches first 1...Nf6 but 1...Nf6 is enough to prove that 1.d4 is worse relative to 1.e4

Uri

[H.G.Muller]

Of course some sub-optimal more ordering schemes are better than others - in your case (4) is better than (3).

This is exactly what I said: some sub-optimal move orderings are better than others. If you can pick the optimal ove ordering with certainty, there is no reason for this discussion (or for your statistic...). I merely point out that it can be benificial to accept that you will not be able to acheive perfect move ordering, and take measures that limit the damage this can do. The observation that tree 2 is smaller than tree 3 does not help without a reliable way to figure out in advance if you should search B before A (or C or...) or vice versa. It might be much easier to identify how complex a move is than how good it is, (e.g. by passing the size of the sub-tree to the caller) and this information might also be much more stable from one iteration to the next than the move score.

If sorting a quiet but reasonable move in front rather than aggressively going for an expensive suspected best one on the average gives you a smaller tree than your best efforts at optimal sorting would give you, the fact that the optimum would even be better is worth zilch.

That's all I wanted to point out.

[mridul]

A common method of measuring move ordering performance is to check the ration "fail high on first move / fail high".

Several people have correctly observed that this is in fact a pretty bad way to measure, because there might be many moves that would fail high, and in that case you want the smallest tree.

It seems to me that the only kind of positions where you can really measure this is at PV nodes.

So, the move ordering performance would be: "number of times the first move at a PV node was indeed the best move".

There might be a sensible definition at alpha nodes too; if we have a fail high there, it should be at the first move, and no other move should fail high.

It's funny that the only places where you can measure is where most people don't do it.

Did anyone measure this way? What rates do you get in what positions?

Hi GCP,

Even I had already stopped using fh/ffh statistics sometime back itself.
Just to give a number for the test you proposed :

Nolot.epd , search time of approx 30 seconds , 2 processor failsoft search with no singular extensions and check limiting :

fh_h : % of failhigh in first move , b_pv - % stat as defined (see below)
1) fh_f : 87.9421 , b_pv : 56.6946
2) fh_f : 87.9058 , b_pv : 40.1515
3) fh_f : 91.0557 , b_pv : 52.4324
4) fh_f : 87.8090 , b_pv : 60
5) fh_f : 86.8200 , b_pv : 50.4673
6) fh_f : 88.5499 , b_pv : 50.5703
7) fh_f : 88.5479 , b_pv : 50.8333
8) fh_f : 89.3660 , b_pv : 51.8466
9) fh_f : 90.0076 , b_pv : 53.1111
10) fh_f : 92.8886 , b_pv : 46.3654
11) fh_f : 87.6984 , b_pv : 50.5804
12) fh_f : 78.9323 , b_pv : 50.1458

The way I interpreted your statistics definition was :

Code: Select all

if value > best
  if alpha != beta - 1
    if first move , first_move_count ++;
    else if this_node_not_failed_best_condition
            num_pvnode_count ++;
            first_move_count --;
            this_node_not_failed_best_condition =1

and final stat :
(first_move_count * 100) / (num_pvnode_count + first_move_count)


Stupid code snippet above but that was the general idea for getting the stat output (was I wrong in interpreting it ?).


As you can see , my numbers are sub-optimal - I just finished my search a few days back and have started with fixing and modifying my eval , qsearch and move ordering.
Hopefully this will improve as things proceed !
Also, not sure what the impact will be with singular extension completed ...

Would be great if you post your numbers

Regards,
Mridul[/code]

[Gian-Carlo Pascutto]

I would write it like this:

Code: Select all

if value > best
  if alpha != beta - 1
    num_pvnode_count++;
    if first move , first_move_count ++;
    else if this_node_not_failed_best_condition
            this_node_not_failed_best_condition =1

and final stat :
(first_move_count * 100) / (num_pvnode_count + 1)


[mridul]

I would write it like this:

Code: Select all

if value > best
  if alpha != beta - 1
    num_pvnode_count++;
    if first move , first_move_count ++;
    else if this_node_not_failed_best_condition
            this_node_not_failed_best_condition =1

and final stat :
(first_move_count * 100) / (num_pvnode_count + 1)


The problem with this is that , suppose at a node you have multiple 'best' scores returned - then you will count it multiple times in num_pvnode_count.

Hmm , maybe this also makes sense since we want to reduce that value too ... but right now , I was more interested in first vs rest.

Mridul

[H.G.Muller]

If I want to judge the quality of my move sorting I count the nodes actually visited, and compare that to the size of the minimal tree required to judge that the move found was the best. To obtain the latter I redo the search with the window closed around the value that the earlier search found, and I added code to pass the number of required nodes down to the root: for alpha or PV nodes this is the sum of the corresponding values of all spawned subtrees + 1, for a beta node it counts only the subtree that caused the fail high + 1. This is not perfect, because there is no guarantee that there was no smaller subtree (not yet examined) that would also have caused a fail high. But it should be a good indication.

To be really precise I would have to search all moves in every node, i.e. continue searching after a fail high to look for cheaper fail highs, and for a deep tree this is so expensive that it is usually not feasible. (According to theory this squares the number of nodes in the tree...) So by comparing the numbers I measure how efficiently the program picks the best move first in PV nodes (in alpha nodes sorting has no effect on the tree size), without knowing anything about how clever it is in choosing the cheapest move to cause a fail high from all moeves that do cause it.

[diepeveen]

Well, I am advocating that some sub-optimal move orderings are better than others. Your truth that optimal move-ordering is best falls in the same category as "smoke detectors are a waste of money, it is better not to cause fires"... Rock climbers 'waste' a lot of effort hammering in anchors that they don't need to get to the top, to secure their savety lines. In an imperfect world you simply get better over-all performance by investing in precautions.

So in the case that the move ordering on ply 3 is perfect, there is indeed nothing to be gained by upping alpha on an earlier move in ply 1. None of the answers on ply 4 will be good enogh to cause a faiil high, even with the lower value of beta you will have their. Deep cutoffs will never occur if the move ordering is perfect. But in practice your engine suffers a lot if you don't implement them.

Actually even in a 3 ply depthleft case a suboptimal move ordering might cutoff sooner.

Nullmove might give a cutoff...

So i order nullmove as the first move usually

Nullmove beats everything!

[diepeveen]

If I want to judge the quality of my move sorting I count the nodes actually visited, and compare that to the size of the minimal tree required to judge that the move found was the best. To obtain the latter I redo the search with the window closed around the value that the earlier search found, and I added code to pass the number of required nodes down to the root: for alpha or PV nodes this is the sum of the corresponding values of all spawned subtrees + 1, for a beta node it counts only the subtree that caused the fail high + 1. This is not perfect, because there is no guarantee that there was no smaller subtree (not yet examined) that would also have caused a fail high. But it should be a good indication.

To be really precise I would have to search all moves in every node, i.e. continue searching after a fail high to look for cheaper fail highs, and for a deep tree this is so expensive that it is usually not feasible. (According to theory this squares the number of nodes in the tree...) So by comparing the numbers I measure how efficiently the program picks the best move first in PV nodes (in alpha nodes sorting has no effect on the tree size), without knowing anything about how clever it is in choosing the cheapest move to cause a fail high from all moeves that do cause it.

Indeed, when i wanted to figure out a year or 10 ago the minimal tree needed when searching with hashtables + nullmove, it soon appeared to be quickly a O ( n ^ 3 ) problem, where n = sum of all legal moves in all positions visited.

We didn't take into account qsearch in that case even, as i assume qsearch to be constant overhead, which in itself is already a bad assumption.

Determining a minimal search tree is a similar problem in dimension to tuning parameters in a neural net, each theta( 1 ) in that case however is a learning curve in itself (which will be what is it, a game or 200?),
so the constant overhead of ANN tuning is eating even more system time thanks to the constant costs of 1 experiment

Best Regards,
Vincent