Why lower bound in fail-high?

Code, algorithms, languages, construction...

Why lower bound in fail-high?

Postby 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.
grandsmaster
 
Posts: 9
Joined: Sun Aug 03, 2014 1:40 pm

Re: Why lower bound in fail-high?

Postby 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."
User923005
 
Posts: 606
Joined: Thu May 19, 2011 1:35 am

Re: Why lower bound in fail-high?

Postby 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.
grandsmaster
 
Posts: 9
Joined: Sun Aug 03, 2014 1:40 pm

Re: Why lower bound in fail-high?

Postby 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.
hyatt
 
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Location: University of Alabama at Birmingham

Re: Why lower bound in fail-high?

Postby 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).
syzygy
 
Posts: 148
Joined: Sun Oct 16, 2011 4:21 pm


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 1 guest

cron