Fail-High

Home * Search * Alpha-Beta * Fail-High

Paul Klee - Red Balloon, 1922

There are two related semantics, if talking of a Fail-High - inside the search tree or if using aspiration windows at the root.

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 :

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. 

Root with Aspiration

Another meaning of a Fail-High, is associated with Aspiration Windows at the Root, where one needs to re-search with wider windows to get the true score rather than a lower bound.

Quote by Bruce again:

You can also talk about failing high and failing low from the root position, if you use an aspiration window. 

See also

• Fail-Hard
• Fail-High Reductions
• Fail-Low
• Fail-Soft
• Upper Bound
• Lower Bound
• Exact Score
• Move Ordering
• Null Window

Forum Posts

1995 ...

• Question: Fail High then Low at Root by William Bryant, CCC, December 28, 1999 » Fail-Low, Root, Search Instability

2000 ...

• "Percentage of fail-highs" question by Daniel Clausen, CCC, January 03, 2000
• Fail highs..which subsequently fail low by Tom King, CCC, August 27, 2000 » Fail-Low, Search Instability
• Q: Fail High percentage by Peter Fendrich, CCC, December 08, 2000
• What means lazy/plain alpha bounding? by Severi Salminen, CCC, February 06, 2001 » Root
• About False Fail Highs, professionals, and MTD searches by Gian-Carlo Pascutto, CCC, April 12, 2002 » MTD(f)
• what does "fail high" mean? by Scott Farrell, CCC, November 29, 2002
• what does "fail high" mean? In the context of iterative deepening by Scott Farrell, CCC, November 30, 2002 » Iterative Deepening
• Hash and first Fail High by Peter Fendrich, CCC, August 14, 2003
• Search behavior in a case of root fail high/low by Sergei S. Markoff, CCC, March 10, 2004 » Fail-Low, MTD(f)
• Fail-high on first move stat (86%) by Michael Henderson, CCC, July 29, 2004 » Move Ordering

2005 ...

• Return eval or upper bound? by John Merlino, CCC, October 26, 2009

2010 ...

• First post (and FailHigh question!) by Natale Galioto, CCC, June 14, 2013 » Fail-Hard, Fail-Soft
• Why lower bound in fail-high? by grandsmaster, OpenChess Forum, September 20, 2014

2015 ...

• Fail low after fail high by J. Wesley Cleveland, CCC, April 04, 2015 » Fail-Low, Search Instability
• cut nodes by Folkert van Heusden, CCC, October 18, 2017  » Cut-Nodes
• On failing high and finding mates by Vincent Tang, CCC, February 16, 2019

2020 ...

• Searching fail highs shallower.. by Tom King, CCC, March 02, 2020

External Links

• Programming - Glossary - Fail Low, Fail High from Bruce Moreland's Programming Topics Site

References

Up one Level