Solving a fail low situation at the root

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 24529
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Solving a fail low situation at the root

Post by hgm » Mon Nov 03, 2014 8:45 pm

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
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Solving a fail low situation at the root

Post by xmas79 » Mon Nov 03, 2014 8:54 pm

bob wrote:
xmas79 wrote:
hgm wrote: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
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Solving a fail low situation at the root

Post by xmas79 » Mon Nov 03, 2014 8:56 pm

hgm wrote: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.

User avatar
asanjuan
Posts: 211
Joined: Thu Sep 01, 2011 3:38 pm
Location: Seville, Spain

Re: Solving a fail low situation at the root

Post by asanjuan » Mon Nov 03, 2014 9:05 pm

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.

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Solving a fail low situation at the root

Post by Evert » Tue Nov 04, 2014 9:03 am

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
Posts: 397
Joined: Sun Oct 29, 2006 3:38 am
Location: Schenectady, NY
Contact:

Re: Solving a fail low situation at the root

Post by Ron Murawski » Wed Nov 05, 2014 4:48 pm

xmas79 wrote: 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
Posts: 397
Joined: Sun Oct 29, 2006 3:38 am
Location: Schenectady, NY
Contact:

Re: Solving a fail low situation at the root

Post by Ron Murawski » Wed Nov 12, 2014 5:37 pm

Ron Murawski wrote:
xmas79 wrote: 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
Posts: 743
Joined: Fri Mar 10, 2006 3:29 pm
Location: Germany

Re: Solving a fail low situation at the root

Post by Joerg Oster » Wed Nov 12, 2014 6:20 pm

Ron Murawski wrote:
Ron Murawski wrote:
xmas79 wrote: 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. :)
Jörg Oster

Ron Murawski
Posts: 397
Joined: Sun Oct 29, 2006 3:38 am
Location: Schenectady, NY
Contact:

Re: Solving a fail low situation at the root

Post by Ron Murawski » Wed Nov 12, 2014 7:03 pm

Joerg Oster wrote:
Ron Murawski wrote:
Ron Murawski wrote:
xmas79 wrote: 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
Posts: 743
Joined: Fri Mar 10, 2006 3:29 pm
Location: Germany

Re: Solving a fail low situation at the root

Post by Joerg Oster » Thu Nov 13, 2014 10:34 am

Ron Murawski wrote:
Joerg Oster wrote:
Ron Murawski wrote:
Ron Murawski wrote:
xmas79 wrote: 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. :D
Correct me if I'm wrong.
Jörg Oster

Post Reply