Sub-optimal move ordering gives smaller tree

[H.G.Muller]

Usually one assumes that, with alpha-beta pruning, trying the best move first will always produce the smallest tree. That this is not universally true even for fixed-depth trees is shown in the example below:

Code: Select all

Case 1: Full tree (40 leaves)
    ----a=== (+1,+1,+1,+1)   (=== means a bundle of 4 moves to positions a1,a2,a3,a4)
    |---b=== (+1,+1,+1,+1)
    |---c=== (+1,+1,+1,+1)
----A---d--- +1
|---B---e---  0
|    /--f=== (-3,-3,-3,-3)
R---C---g=== (-3,-3,-3,-3)
|    \--h=== (-3,-3,-3,-3)
|     --i---  0
----D---j=== (-3,-3,-3,-3)
    |---k=== (-3,-3,-3,-3)
    |---l=== (-3,-3,-3,-3)
    ----m---  0

Case 2: Alpha-Beta with best move first (16 leaves)
    ----a=== (+1,+1,+1,+1)
    |---b--- +1
    |---c--- +1
----A---d--- +1
|---B---e---  0
|    /--f=== (-3,-3,-3,-3)
R---C-x
|    \x
|     x
----D---j=== (-3,-3,-3,-3)
    |-x
    |-x
    --x

Case 3: Alpha-Beta with simplest move first (10 leaves)
----B---e---  0
|   ----a=== (+1,+1,+1,+1)
|   |---b--- +1
|   |---c--- +1
|---A---d--- +1
|    /--i---  0
R---C-x
|    \x
|     x
----D---m---  0
    |-x
    |-x
    --x


From the root position R there are 4 moves, one (B) that simplifies the situation so that only a low branching factor remains (here: 1), while the other three moves keep the situation complex. As long as the situation is complex there is a high branching factor (here: 4), but there is always one move among those that simplifies the situation (from where-on the branching factor drops to 1 again).

Case 1 sketches the full tree, with evaluation written at the leaves. Move A (i.e. to position A) is the best in ply 1, emerging with a score of +1 from the complex situation. The complex situation can also lead to a score -3, though, if I enter it with the bad moves C or D. The simplifying move B is not the best, it leads to score 0. In reply to C and D the simplifying moves for black on ply 2 (i and m) are also not the best for him, they lead to a score 0 in stead of -3.

Case 2 shows how alpha-beta prunes the tree with optimal move ordering, i.e. A is searched before B on ply 1, and f and j are searched before i and m (respctively) on ply 2. From the 40 end leaves, only 16 remain.

Case 3 shows alpha-beta with 'sub-optimal' move ordering. In stead of searching the best move first, we systematically search the simplifying move first, although this move is worse. Only 10 end leaves remain now. The savings come from the beta nodes in ply 2, where the fail high is effected cheaply by the simple move, which, although it was not the best, still produced a score large enough to cause the fail. Sorting B in front on ply 1 did not hurt, despite the fact that it was now searched with a wider window: the tree was to small for this making a significant difference (here there was in fact no difference at all).

In fact sorting B in front on ply 1 has a very favorable side effect: because searchin B ups alpha, the move after that will be searched with this new alpha rather than with alpha = -inf. If the move searched directly after it is the best one, this does not make any difference (and after that this nw move determines alpha, so any possible effect of searchin B is expired). But if we occasionally making a mistake in judging beforehand in the complex situation what the best move is, we might inadvertantly sort C in front of A. If C was the first, then, its search would be just as expensive as that of the A subtree (no cutoffs). But if C is searched after B, it is just as cheap as when it was searched after A: there is already a reasonable value for alpha, causing the same cutoffs in ply 3. So sorting the simple move in front in a PV node does not cost much, and acts as an insurance to sorting errors for the complex moves.

So in contrast to popular believe, 'sub-optimal' move ordering can in some cases beat 'optimal' move ordering as far as tree size is concerned, even for fixed-depth trees. Sorting by complexity might beat sorting by expected score.

[Uri Blass]

I already gave an example for it earlier and my example is simpler

see my last post in
http://wbforum.volker-pittlik.name/viewtopic.php?t=4156

[Uri Blass]

I can add that I usually tend to extend moves that simplifies the situation so practically searching the best move first is relatively good strategy.

people usually extend checks but of course if a program does not extend checks then it may be better for it to search checks earlier even if they are not the best moves because they may be good enough to refute the opponent move.

Uri

[H.G.Muller]

Sorry, I missed that one entirely, because I was typing a message in the same thread while you were posting it, and did not read back in the thread after pressing the 'submit' key.

I will have a look to your example, because I think this is a pretty interesting effect. It is so much easier to judge statically if a position is complex than it is to judge if a non-quiet position is good. In trees with extensions/reductions I can imagine that the effect can be even bigger.

[L?szl? G?sp]

I find this observation very nice and interesting!
Thank you dear H.,..no...dear G.,...??...no..., dear Mr. H. G. Muller? Or Mrs.?

Best regards,
L?szl?

[H.G.Muller]

Mr., actually...

Since my first name sounds ominous to English speakers, and my second name is unpronouncible for them, I usually go about by the name 'H.G.' when I am abroad.

[L?szl? G?sp]

Since my first name sounds ominous to English speakers, and my second name is unpronouncible for them, I usually go about by the name 'H.G.' when I am abroad.

I see...I also could have had this problem...

Anyway, your idea is great! I already experienced that my engine did an n ply search fast, but after the opponents move it hardly reached the n-2 ply, thus consuming a lot of time and doing nothing ! I wanted to investigate this problem and an explanation can be this.

Regards,
L?szl?

[Gerd Isenberg]

Mr., actually...

Since my first name sounds ominous to English speakers, and my second name is unpronouncible for them, I usually go about by the name 'H.G.' when I am abroad.

I found my first name unpronouncible for dutch

[H.G.Muller]

Well, the problem is related, because my second name is Geert... So you must have a pretty good idea how that is pronounced, by now!

I have thought about adopting the new name Harry to fit my first initial, and as a reference/pun to my usual hair-do, but I probably would not react to it if people called me that...

[H.G.Muller]

But to return to the subject:

The mentioned effect might be (part of) the explanation why null-move pruning is so succesful. In that case the null move is tried before all real moves, despite the fact that you can hardly expect it to be the best. Typically you do this in situations where it is reasonable to hope the null move will cause a fail high (i.e. eval > beta). And although the null move itself does not seem to do much in terms of simplification, at least it does not initiate tactical complications of its own. Furthermore, it can be qualified as a cheap move, because usually one reduces the search depth in its branch by 2 or more plies. So even if the branching ratio is the same, the smaller depth is what you gain.

Situations where a null move would lead to tremendous complications (because you fail to recapture a piece, that as a consequence can get berserk) you usually don't try it, beause the fact that you are behind one recapture pushes eval far below beta.

So null-move pruning perfectly fits the more general algorithm to reduce tree size by move ordering: if there are moves available that have the potential to raise the score above beta (e.g. by capturing material worth at least beta-eval, or attacking such material), don't sort them by expected score, but by expected complexity. E.g. try recaptures before counter threats, try exchanging an attacker before withdrawing the attacked piece before defending it.