Fail-highs and fail-lows

[metax]

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?

[hgm]

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.

[Gerd Isenberg]

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?

You should use < alpha, == alpha is not a fail low.

[metax]

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?

[Sven]

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 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.

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

[metax]

You should use < alpha, == alpha is not a fail low.

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.
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'...

[Sven]

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?

You should use < alpha, == alpha is not a fail low.

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

[metax]

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

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]

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.

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.

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

[Gerd Isenberg]

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?