Solving a fail low situation at the root

[hgm]

I am not sure a better branching factor would make it really more predictable. Whatever lower your branching factor, the larger fraction of the search time will be used by the PV move (as it is a search of d-1). And when you overturn the PV, either because the previous one has gone sour, or you find an unexpected better one, it will take again as long. So iterations that change the PV will always take a factor longer than those that don't.

[xmas79]

Set alpha = -INFINITY. Then you cannot possibly fail low.

Setting alpha to -INFINITY at first fail low can produce big penalty, isn't it? My undestanging is that he sets alpha to -INF on second fail low.

The problem I see is that on two fail low alpha will be set to -INF, but beta to +INF as well, and on two fail high beta will be set to +INF and alpha will be set to -INF as well. This will lead to sub-obtimal search, isn't it? I would change only alpha/beta upon fail low/high.

A couple of issues:

(1) you should not play a "bad move" in that the move is random or whatever. You should always have a "best move" from previous iteration.

(2) extending time on a fail low is a good idea. How much is a good question. I allow up to 5x the normal target time. It is generally better to widen the window gradually, but most use a sort of quadratic function or something, such as alpha -= 16, then 32, then 64, then 128, etc... Use any multiple you like.

I currently use 1, so when I must move and have no best move for the current iteration I play the best move of the previous one.

I'm using a fail-soft framework, so I roughly get the idea of how bad the score is, and I can shift instantly the window around the (bad) score. Window is also widened during this shifting, and allowed search time is extended.

As an example, when I search with a window [-15,15] and fail low I can get a score that can be say -80. Then I research with a center of -80 and an aperture of 20, so I search [-100, -60].

I'm also experimenting with asymetric windows, where on a fail low I widen only on the alpha side and on a fail high I widen only on the beta side, but I'm not sure of the implications. In the previous example, that means that on a fail low I will search with a window of [-100, -65].

As another experiment I'm trying to avoid the typical fail high/fail low ping pong can happen with such searches by setting only alpha, so on the previous example again the window becomes [-100, 15]. I found this last idea to be more robust on the beta side, where I widen and raise only beta, and keep alpha at the original value, probably the effect is the one described by HGM some post ago. But I'm still investigating search windows...

[xmas79]

I am not sure a better branching factor would make it really more predictable. Whatever lower your branching factor, the larger fraction of the search time will be used by the PV move (as it is a search of d-1). And when you overturn the PV, either because the previous one has gone sour, or you find an unexpected better one, it will take again as long. So iterations that change the PV will always take a factor longer than those that don't.

This is perfect from a theorical point of view, but I don't see that in my engine. I see unexpected behaviour in random iterations. I'll pay more attention to where the engine spends more time.

[asanjuan]

Yes, the current version returns the move from the previous iteration, but now I know that at some points, that move can be crap.
looks like we will face this problem always, as it is due to the horizont effect at the previous iteration.

[Evert]

I currently do this (which is a bit stupid and can certainly be improved):

• I update my "best move" when the score is in-window, or on fail high (so when score > alpha)
• When the root move fails low, I allocate extra time up to 90% of my remaining time, widen the aspiration window around the returned score (fail-soft) and search again to resolve the fail low.

I also allocate some extra time on a fail-high, but much less. Not sure if that's really necessary (I suspect it probably isn't).

This way I always have a move to play, assuming that the first iteration completed (which I've had issues with at really short time controls in shogi).

[Ron Murawski]

I'm also experimenting with asymetric windows, where on a fail low I widen only on the alpha side and on a fail high I widen only on the beta side, but I'm not sure of the implications. In the previous example, that means that on a fail low I will search with a window of [-100, -65].

For me asymmetric widening works best. I've found that the other, non-failing bound must be widened too, but only by a small amount compared to the widening of the failed bound.

[Ron Murawski]

I'm also experimenting with asymetric windows, where on a fail low I widen only on the alpha side and on a fail high I widen only on the beta side, but I'm not sure of the implications. In the previous example, that means that on a fail low I will search with a window of [-100, -65].

For me asymmetric widening works best. I've found that the other, non-failing bound must be widened too, but only by a small amount compared to the widening of the failed bound.

A less-aggressive form of this idea has worked for Stockfish:

Code: Select all

Author: lucasart
Date: Sat Nov 8 10:47:56 2014 -0500
Timestamp: 1415461676

Be more optimistic in aspiration window

Be more optimistic wrt search instability, and set the unviolated bound
half window.

STC
LLR: 2.96 (-2.94,2.94) [-1.00,4.00]
Total: 16362 W: 3371 L: 3197 D: 9794

LTC
LLR: 2.94 (-2.94,2.94) [0.00,5.00]
Total: 21666 W: 3780 L: 3569 D: 14317

Bench: 6807896

Resolves #105

[Joerg Oster]

I'm also experimenting with asymetric windows, where on a fail low I widen only on the alpha side and on a fail high I widen only on the beta side, but I'm not sure of the implications. In the previous example, that means that on a fail low I will search with a window of [-100, -65].

For me asymmetric widening works best. I've found that the other, non-failing bound must be widened too, but only by a small amount compared to the widening of the failed bound.

A less-aggressive form of this idea has worked for Stockfish:

Code: Select all

Author: lucasart
Date: Sat Nov 8 10:47:56 2014 -0500
Timestamp: 1415461676

Be more optimistic in aspiration window

Be more optimistic wrt search instability, and set the unviolated bound
half window.

STC
LLR: 2.96 (-2.94,2.94) [-1.00,4.00]
Total: 16362 W: 3371 L: 3197 D: 9794

LTC
LLR: 2.94 (-2.94,2.94) [0.00,5.00]
Total: 21666 W: 3780 L: 3569 D: 14317

Bench: 6807896

Resolves #105

Yet the non-failing bound gets narrowed and not widened. Unlike you proposed.

[Ron Murawski]

I'm also experimenting with asymetric windows, where on a fail low I widen only on the alpha side and on a fail high I widen only on the beta side, but I'm not sure of the implications. In the previous example, that means that on a fail low I will search with a window of [-100, -65].

For me asymmetric widening works best. I've found that the other, non-failing bound must be widened too, but only by a small amount compared to the widening of the failed bound.

A less-aggressive form of this idea has worked for Stockfish:

Code: Select all

Author: lucasart
Date: Sat Nov 8 10:47:56 2014 -0500
Timestamp: 1415461676

Be more optimistic in aspiration window

Be more optimistic wrt search instability, and set the unviolated bound
half window.

STC
LLR: 2.96 (-2.94,2.94) [-1.00,4.00]
Total: 16362 W: 3371 L: 3197 D: 9794

LTC
LLR: 2.94 (-2.94,2.94) [0.00,5.00]
Total: 21666 W: 3780 L: 3569 D: 14317

Bench: 6807896

Resolves #105

Yet the non-failing bound gets narrowed and not widened. Unlike you proposed.

Hi Joerg,

There is no inconsistency. Please re-read my original post.

Ron

[Joerg Oster]

I'm also experimenting with asymetric windows, where on a fail low I widen only on the alpha side and on a fail high I widen only on the beta side, but I'm not sure of the implications. In the previous example, that means that on a fail low I will search with a window of [-100, -65].

For me asymmetric widening works best. I've found that the other, non-failing bound must be widened too, but only by a small amount compared to the widening of the failed bound.

A less-aggressive form of this idea has worked for Stockfish:

Code: Select all

Author: lucasart
Date: Sat Nov 8 10:47:56 2014 -0500
Timestamp: 1415461676

Be more optimistic in aspiration window

Be more optimistic wrt search instability, and set the unviolated bound
half window.

STC
LLR: 2.96 (-2.94,2.94) [-1.00,4.00]
Total: 16362 W: 3371 L: 3197 D: 9794

LTC
LLR: 2.94 (-2.94,2.94) [0.00,5.00]
Total: 21666 W: 3780 L: 3569 D: 14317

Bench: 6807896

Resolves #105

Yet the non-failing bound gets narrowed and not widened. Unlike you proposed.

Hi Joerg,

There is no inconsistency. Please re-read my original post.

Ron

Hi Ron,

I did, several times now. Still I always come to the same conclusion.
Assume beta is the non-failing bound. Narrowing means shift bound towards alpha, and widening means shift the bound towards +infinity. When you write the non-failing bound must be widened as well, I interpreted to do the latter.
Correct me if I'm wrong.