If I do not have an error in reasoning now, a fail-high occurs when value >= beta at the root, and a fail-low occurs when the value is <= alpha. If I fail-high, I research with the window [value, MATE] at the next ply (I know I can first try value+100 and value+300 before opening the window completely, but to keep it simple let's say MATE). So if the same value is returned by the research, I get a fail-low because the returned value is <= alpha. This occurs at some mate-in-n positions with my engine. To illustrate (the example is invented, but I had cases like this one):
Ply 07 Move 20.00
Ply 08 Move M8++
Ply 09 Move M8--
Ply 09 Move M8
Ply 10 Move M8
...
This looks strange to me. Should the search really fail-low if after a fail-high, the same value is returned by the research?
Fail-highs and fail-lows
Moderators: hgm, Rebel, chrisw
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Fail-highs and fail-lows
This is known as search instability, and can be caused by certain score-dependent prunings (null move, LMR) or hashing. If it happens in a plain alpha-beta search without hashing, you have a bug.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Fail-highs and fail-lows
You should use < alpha, == alpha is not a fail low.metax wrote:If I do not have an error in reasoning now, a fail-high occurs when value >= beta at the root, and a fail-low occurs when the value is <= alpha. If I fail-high, I research with the window [value, MATE] at the next ply (I know I can first try value+100 and value+300 before opening the window completely, but to keep it simple let's say MATE). So if the same value is returned by the research, I get a fail-low because the returned value is <= alpha. This occurs at some mate-in-n positions with my engine. To illustrate (the example is invented, but I had cases like this one):
Ply 07 Move 20.00
Ply 08 Move M8++
Ply 09 Move M8--
Ply 09 Move M8
Ply 10 Move M8
...
This looks strange to me. Should the search really fail-low if after a fail-high, the same value is returned by the research?
-
- Posts: 344
- Joined: Wed Sep 23, 2009 5:56 pm
- Location: Germany
Re: Fail-highs and fail-lows
Is it even instability if the same score is returned after a fail-high. I always thought fail-high means that the score is an inclusive lower bound of the 'real' score, so that if I have a fail-high like +8.75++ the 'real' score could be 8.75 or higher. If I understand you correctly, you say that +8.75++ means the 'real' score is at least +8.76.
So can I avoid these search instability issues without abandoning forward pruning?
So can I avoid these search instability issues without abandoning forward pruning?
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Fail-highs and fail-lows
I have encountered the same question a long time ago already. The solution I prefer is to always perform the research with [value-1 .. INFINITY] for a fail-high, and with [-INFINITY .. value+1] for a fail-low. This looks correct for me even if 'value' is not a mate score, although I think the problem mainly occurs with mate scores.metax wrote:If I do not have an error in reasoning now, a fail-high occurs when value >= beta at the root, and a fail-low occurs when the value is <= alpha. If I fail-high, I research with the window [value, MATE] at the next ply (I know I can first try value+100 and value+300 before opening the window completely, but to keep it simple let's say MATE). So if the same value is returned by the research, I get a fail-low because the returned value is <= alpha. This occurs at some mate-in-n positions with my engine. To illustrate (the example is invented, but I had cases like this one):
Ply 07 Move 20.00
Ply 08 Move M8++
Ply 09 Move M8--
Ply 09 Move M8
Ply 10 Move M8
...
This looks strange to me. Should the search really fail-low if after a fail-high, the same value is returned by the research?
I also don't think this is related to search instability somehow, as stated by HGM in his answer.
I even go one step further, and find out the maximum possible score for the moving side which is usually a mate score directly depending on the number of the current iteration (previous iterations should have found shorter mates already, provided your engine can't miss that due to its massive pruning strategies). If the search fails high but returns that maximum possible score then no research is necessary.
Sven
-
- Posts: 344
- Joined: Wed Sep 23, 2009 5:56 pm
- Location: Germany
Re: Fail-highs and fail-lows
Really? I wonder because as far as I remember, there are real fail-lows in my engine where the score is == alpha, but a research causes a lower score.Gerd Isenberg wrote:You should use < alpha, == alpha is not a fail low.
So should I also use > beta instead of >= beta?
EDIT: This seems illogical to me because in the null-window searches after the first iteration alpha and beta themselves would then be 'inside the window'...
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Fail-highs and fail-lows
This is wrong IMO, <= alpha is correct. It must be symmetrical to the fail-high case obviously since failing low is caused by all our moves being refuted by the opponent with "value >= beta" from his viewpoint.Gerd Isenberg wrote:You should use < alpha, == alpha is not a fail low.metax wrote:If I do not have an error in reasoning now, a fail-high occurs when value >= beta at the root, and a fail-low occurs when the value is <= alpha. If I fail-high, I research with the window [value, MATE] at the next ply (I know I can first try value+100 and value+300 before opening the window completely, but to keep it simple let's say MATE). So if the same value is returned by the research, I get a fail-low because the returned value is <= alpha. This occurs at some mate-in-n positions with my engine. To illustrate (the example is invented, but I had cases like this one):
Ply 07 Move 20.00
Ply 08 Move M8++
Ply 09 Move M8--
Ply 09 Move M8
Ply 10 Move M8
...
This looks strange to me. Should the search really fail-low if after a fail-high, the same value is returned by the research?
Sven
-
- Posts: 344
- Joined: Wed Sep 23, 2009 5:56 pm
- Location: Germany
Re: Fail-highs and fail-lows
Thanks. Set the research alpha to value - 1 in case of a fail-high (and beta to value + 1 in case of a fail-low).Sven Schüle wrote:This is wrong IMO, <= alpha is correct. It must be symmetrical to the fail-high case obviously since failing low is caused by all our moves being refuted by the opponent with "value >= beta" from his viewpoint.
Sven
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Fail-highs and fail-lows
His problem is about exact scores returned by the first search. The old proposal to research with [value .. +INFINITY] does not deal with exact scores. If there is no heavy pruning and maybe also no hashing involved then you still would run into that problem with the lower bound of the new window set to 'value', because the exact score 'value' must remain "inside" the new window bounds. So the new lower bound should always be 'value - 1' to guarantee that.hgm wrote:This is known as search instability, and can be caused by certain score-dependent prunings (null move, LMR) or hashing. If it happens in a plain alpha-beta search without hashing, you have a bug.
However, if search instability is possible then it may still be the better choice to open the new aspiration window completely, i.e. [-INF .. + INF]. But at least the 'exact score' issue seems unrelated to search instability for me.
Sven
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Fail-highs and fail-lows
If you set alpha to [mate in 8] after a fail high, and you find a [mate in 8] again it should not be interpreted as fail low. Or?