Difference between revisions of "Fail-High"
GerdIsenberg (talk | contribs) m |
GerdIsenberg (talk | contribs) |
||
| Line 1: | Line 1: | ||
'''[[Main Page|Home]] * [[Search]] * [[Alpha-Beta]] * Fail-High''' | '''[[Main Page|Home]] * [[Search]] * [[Alpha-Beta]] * Fail-High''' | ||
| − | [[File:Red Balloon.JPG|border|right|thumb|[[ | + | [[File:Red Balloon.JPG|border|right|thumb|[[:Category:Paul Klee|Paul Klee]] - Red Balloon, 1922 <ref>[[:Category:Paul Klee|Paul Klee]] - Red Balloon, 1922, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Solomon_R._Guggenheim_Museum Solomon R. Guggenheim Museum]</ref>]] |
There are two related semantics, if talking of a '''Fail-High''' - inside the [[Search Tree|search tree]] or if using [[Aspiration Windows|aspiration windows]] at the [[Root|root]]. | There are two related semantics, if talking of a '''Fail-High''' - inside the [[Search Tree|search tree]] or if using [[Aspiration Windows|aspiration windows]] at the [[Root|root]]. | ||
Revision as of 00:23, 6 February 2020
Home * Search * Alpha-Beta * Fail-High
There are two related semantics, if talking of a Fail-High - inside the search tree or if using aspiration windows at the root.
Contents
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 [2]:
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
