Why lower bound in fail-high?

Code, algorithms, languages, construction...
Post Reply
grandsmaster
Posts: 9
Joined: Sun Aug 03, 2014 1:40 pm

Why lower bound in fail-high?

Post by grandsmaster » Sat Sep 20, 2014 1:36 am

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.

User923005
Posts: 616
Joined: Thu May 19, 2011 1:35 am

Re: Why lower bound in fail-high?

Post by User923005 » Sat Sep 20, 2014 3:36 am

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

grandsmaster
Posts: 9
Joined: Sun Aug 03, 2014 1:40 pm

Re: Why lower bound in fail-high?

Post by grandsmaster » Sat Sep 20, 2014 8:27 am

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.

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Why lower bound in fail-high?

Post by hyatt » Tue Sep 23, 2014 3:17 am

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.

syzygy
Posts: 148
Joined: Sun Oct 16, 2011 4:21 pm

Re: Why lower bound in fail-high?

Post by syzygy » Fri Sep 26, 2014 10:00 pm

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

Post Reply