OpenChess

Why in a fail-high framework, the returned score is a lower bound? I'd expect if score >= beta, and we return score. The score would be an upper bound to the exact score.

From:
https://chessprogramming.wikispaces.com/Fail-High
We have this simple explanation:

"Inside the Tree
A Fail-High is associated with a Beta-Cutoff in the alpha-beta algorithm, which appears at so called Cut-Nodes, also called Fail-High nodes. The score returned is a lower bound on the exact score of the node.

Quote by Bruce Moreland [1]:
A fail-high indicates that the search found something that was "too good". What this means is that the opponent has some way, already found by the search, of avoiding this position, so you have to assume that they'll do this. If they can avoid this position, there is no longer any need to search successors, since this position won't happen."

I posted the question because I also read the page. I'm looking for an understanding why exactly this is a lower bound. Say, if alpha = 1, beta = 5, our evaluation gives 10. We fail high, and return 10. At the end of the search, considering all possibilities, the PV line gives a score of 3. Shouldn't our returned value 10 is the upper bound for the exact score? In this example, the exact score is 3.

Here's the answer:

When you fail high at the root, all you know is that score from the search is >= beta. You do not know how much greater than beta. So that score that is returned is the guaranteed minimum, where the real score could be much higher (say beta = 0.1, but you just found a move that led to a forced mate). 0.1 is the lower bound on the score for this fail-high move, but the actual score can be much higher (here it is actually a mate). And, of course, on occasion, the real score just happens to be equal to beta, but that is rare compared to the cases where the score is greater than beta, simply because there are so many more choices that are > beta, as opposed to just the one choice where score == beta.

Hope that helps.

grandsmaster wrote:Why in a fail-high framework, the returned score is a lower bound? I'd expect if score >= beta, and we return score. The score would be an upper bound to the exact score.

If score is the REAL score, then alpha-beta in case of a fail-high does not return that value, but a value "v" that satisfies v <= score. This is why the condition beta <= v (i.e. a fail-high) allows a cutoff: if beta <= v, it is certain that beta <= v <= score.

So the value returned (v) is a lower bound for the REAL score (score).