Difference between revisions of "Fail-High"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Search * Alpha-Beta * Fail-High''' There are two related semantics, if talking of a '''Fail-High''' - inside the search tree o...") |
GerdIsenberg (talk | contribs) |
||
(5 intermediate revisions by the same user not shown) | |||
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|[[: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]]. | ||
Line 43: | Line 45: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=30333 Return eval or upper bound?] by [[John Merlino]], [[CCC]], October 26, 2009 | * [http://www.talkchess.com/forum/viewtopic.php?t=30333 Return eval or upper bound?] by [[John Merlino]], [[CCC]], October 26, 2009 | ||
==2010 ...== | ==2010 ...== | ||
+ | * [http://www.open-chess.org/viewtopic.php?f=5&t=2220 Fail High nodes] by [[Christian Daley|CDaley11]], [[Computer Chess Forums|OpenChess Forum]], January 14, 2013 | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=48274 First post (and FailHigh question!)] by [[Natale Galioto]], [[CCC]], June 14, 2013 » [[Fail-Hard]], [[Fail-Soft]] | * [http://www.talkchess.com/forum/viewtopic.php?t=48274 First post (and FailHigh question!)] by [[Natale Galioto]], [[CCC]], June 14, 2013 » [[Fail-Hard]], [[Fail-Soft]] | ||
* [http://www.open-chess.org/viewtopic.php?f=5&t=2726 Why lower bound in fail-high?] by grandsmaster, [[Computer Chess Forums|OpenChess Forum]], September 20, 2014 | * [http://www.open-chess.org/viewtopic.php?f=5&t=2726 Why lower bound in fail-high?] by grandsmaster, [[Computer Chess Forums|OpenChess Forum]], September 20, 2014 | ||
Line 48: | Line 51: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=55889 Fail low after fail high] by [[J. Wesley Cleveland]], [[CCC]], April 04, 2015 » [[Fail-Low]], [[Search Instability]] | * [http://www.talkchess.com/forum/viewtopic.php?t=55889 Fail low after fail high] by [[J. Wesley Cleveland]], [[CCC]], April 04, 2015 » [[Fail-Low]], [[Search Instability]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=65477 cut nodes] by [[Folkert van Heusden]], [[CCC]], October 18, 2017 » [[Node Types#CUT|Cut-Nodes]] | * [http://www.talkchess.com/forum/viewtopic.php?t=65477 cut nodes] by [[Folkert van Heusden]], [[CCC]], October 18, 2017 » [[Node Types#CUT|Cut-Nodes]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69927 On failing high and finding mates] by [[Vincent Tang]], [[CCC]], February 16, 2019 | ||
+ | ==2020 ...== | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73250 Searching fail highs shallower..] by [[Tom King]], [[CCC]], March 02, 2020 | ||
=External Links= | =External Links= | ||
Line 54: | Line 60: | ||
=References= | =References= | ||
<references /> | <references /> | ||
− | |||
'''[[Alpha-Beta|Up one Level]]''' | '''[[Alpha-Beta|Up one Level]]''' | ||
+ | [[Category:Paul Klee]] |
Latest revision as of 10:22, 11 April 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 ...
- Fail High nodes by CDaley11, OpenChess Forum, January 14, 2013
- 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