Solving a fail low situation at the root
Moderators: hgm, Rebel, chrisw
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Solving a fail low situation at the root
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.
-
- Posts: 286
- Joined: Mon Jun 03, 2013 7:05 pm
- Location: Italy
Re: Solving a fail low situation at the root
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.bob wrote:A couple of issues:xmas79 wrote: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.hgm wrote:Set alpha = -INFINITY. Then you cannot possibly 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.
(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'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...
-
- Posts: 286
- Joined: Mon Jun 03, 2013 7:05 pm
- Location: Italy
Re: Solving a fail low situation at the root
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.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.
-
- Posts: 214
- Joined: Thu Sep 01, 2011 5:38 pm
- Location: Seville, Spain
Re: Solving a fail low situation at the root
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.
looks like we will face this problem always, as it is due to the horizont effect at the previous iteration.
Still learning how to play chess...
knigths move in "L" shape ¿right?
knigths move in "L" shape ¿right?
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Solving a fail low situation at the root
I currently do this (which is a bit stupid and can certainly be improved):
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).
- 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.
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).
-
- Posts: 397
- Joined: Sun Oct 29, 2006 4:38 am
- Location: Schenectady, NY
Re: Solving a fail low situation at the root
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.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].
-
- Posts: 397
- Joined: Sun Oct 29, 2006 4:38 am
- Location: Schenectady, NY
Re: Solving a fail low situation at the root
A less-aggressive form of this idea has worked for Stockfish:Ron Murawski wrote: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.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].
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
-
- Posts: 937
- Joined: Fri Mar 10, 2006 4:29 pm
- Location: Germany
Re: Solving a fail low situation at the root
Yet the non-failing bound gets narrowed and not widened. Unlike you proposed.Ron Murawski wrote:A less-aggressive form of this idea has worked for Stockfish:Ron Murawski wrote: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.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].
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
Jörg Oster
-
- Posts: 397
- Joined: Sun Oct 29, 2006 4:38 am
- Location: Schenectady, NY
Re: Solving a fail low situation at the root
Hi Joerg,Joerg Oster wrote:Yet the non-failing bound gets narrowed and not widened. Unlike you proposed.Ron Murawski wrote:A less-aggressive form of this idea has worked for Stockfish:Ron Murawski wrote: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.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].
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
There is no inconsistency. Please re-read my original post.
Ron
-
- Posts: 937
- Joined: Fri Mar 10, 2006 4:29 pm
- Location: Germany
Re: Solving a fail low situation at the root
Hi Ron,Ron Murawski wrote:Hi Joerg,Joerg Oster wrote:Yet the non-failing bound gets narrowed and not widened. Unlike you proposed.Ron Murawski wrote:A less-aggressive form of this idea has worked for Stockfish:Ron Murawski wrote: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.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].
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
There is no inconsistency. Please re-read my original post.
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.
Jörg Oster