25,161
edits
Changes
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..."
'''[[Main Page|Home]] * [[Search]] * [[Alpha-Beta]] * Fail-High'''
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]].
=Inside the Tree=
A '''Fail-High''' is associated with a [[Beta-Cutoff]] in the [[Alpha-Beta|alpha-beta algorithm]], which appears at so called [[Node Types#CUT|Cut-Nodes]], also called Fail-High nodes. The score returned is a [[Lower Bound|lower bound]] on the [[Exact Score|exact score]] of the [[Node|node]].
Quote by [[Bruce Moreland]] <ref>[http://web.archive.org/web/20040512194831/brucemo.com/compchess/programming/glossary.htm#fail-high Programming - Glossary - Fail Low, Fail High] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm Programming Topics Site]</ref>:
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|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 ...==
* [https://www.stmintz.com/ccc/index.php?id=84651 Question: Fail High then Low at Root] by [[William Bryant]], [[CCC]], December 28, 1999 » [[Fail-Low]], [[Root]], [[Search Instability]]
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=85729 "Percentage of fail-highs" question] by [[Daniel Clausen]], [[CCC]], January 03, 2000
* [https://www.stmintz.com/ccc/index.php?id=126878 Fail highs..which subsequently fail low] by [[Tom King]], [[CCC]], August 27, 2000 » [[Fail-Low]], [[Search Instability]]
* [https://www.stmintz.com/ccc/index.php?id=143776 Q: Fail High percentage] by [[Peter Fendrich]], [[CCC]], December 08, 2000
* [https://www.stmintz.com/ccc/index.php?id=153648 What means lazy/plain alpha bounding?] by [[Severi Salminen]], [[CCC]], February 06, 2001 » [[Root]]
* [https://www.stmintz.com/ccc/index.php?id=223036 About False Fail Highs, professionals, and MTD searches] by [[Gian-Carlo Pascutto]], [[CCC]], April 12, 2002 » [[MTD(f)]]
* [https://www.stmintz.com/ccc/index.php?id=268076 what does "fail high" mean?] by [[Scott Farrell]], [[CCC]], November 29, 2002
* [https://www.stmintz.com/ccc/index.php?id=268121 what does "fail high" mean? In the context of iterative deepening] by [[Scott Farrell]], [[CCC]], November 30, 2002 » [[Iterative Deepening]]
* [https://www.stmintz.com/ccc/index.php?id=311272 Hash and first Fail High] by [[Peter Fendrich]], [[CCC]], August 14, 2003
* [https://www.stmintz.com/ccc/index.php?id=353798 Search behavior in a case of root fail high/low] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], March 10, 2004 » [[Fail-Low]], [[MTD(f)]]
* [https://www.stmintz.com/ccc/index.php?id=379624 Fail-high on first move stat (86%)] by Michael Henderson, [[CCC]], July 29, 2004 » [[Move Ordering]]
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=30333 Return eval or upper bound?] by [[John Merlino]], [[CCC]], October 26, 2009
==2010 ...==
* [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
==2015 ...==
* [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]]
=External Links=
* [http://web.archive.org/web/20040512194831/brucemo.com/compchess/programming/glossary.htm#fail-high Programming - Glossary - Fail Low, Fail High] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm Programming Topics Site]
=References=
<references />
'''[[Alpha-Beta|Up one Level]]'''
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]].
=Inside the Tree=
A '''Fail-High''' is associated with a [[Beta-Cutoff]] in the [[Alpha-Beta|alpha-beta algorithm]], which appears at so called [[Node Types#CUT|Cut-Nodes]], also called Fail-High nodes. The score returned is a [[Lower Bound|lower bound]] on the [[Exact Score|exact score]] of the [[Node|node]].
Quote by [[Bruce Moreland]] <ref>[http://web.archive.org/web/20040512194831/brucemo.com/compchess/programming/glossary.htm#fail-high Programming - Glossary - Fail Low, Fail High] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm Programming Topics Site]</ref>:
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|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 ...==
* [https://www.stmintz.com/ccc/index.php?id=84651 Question: Fail High then Low at Root] by [[William Bryant]], [[CCC]], December 28, 1999 » [[Fail-Low]], [[Root]], [[Search Instability]]
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=85729 "Percentage of fail-highs" question] by [[Daniel Clausen]], [[CCC]], January 03, 2000
* [https://www.stmintz.com/ccc/index.php?id=126878 Fail highs..which subsequently fail low] by [[Tom King]], [[CCC]], August 27, 2000 » [[Fail-Low]], [[Search Instability]]
* [https://www.stmintz.com/ccc/index.php?id=143776 Q: Fail High percentage] by [[Peter Fendrich]], [[CCC]], December 08, 2000
* [https://www.stmintz.com/ccc/index.php?id=153648 What means lazy/plain alpha bounding?] by [[Severi Salminen]], [[CCC]], February 06, 2001 » [[Root]]
* [https://www.stmintz.com/ccc/index.php?id=223036 About False Fail Highs, professionals, and MTD searches] by [[Gian-Carlo Pascutto]], [[CCC]], April 12, 2002 » [[MTD(f)]]
* [https://www.stmintz.com/ccc/index.php?id=268076 what does "fail high" mean?] by [[Scott Farrell]], [[CCC]], November 29, 2002
* [https://www.stmintz.com/ccc/index.php?id=268121 what does "fail high" mean? In the context of iterative deepening] by [[Scott Farrell]], [[CCC]], November 30, 2002 » [[Iterative Deepening]]
* [https://www.stmintz.com/ccc/index.php?id=311272 Hash and first Fail High] by [[Peter Fendrich]], [[CCC]], August 14, 2003
* [https://www.stmintz.com/ccc/index.php?id=353798 Search behavior in a case of root fail high/low] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], March 10, 2004 » [[Fail-Low]], [[MTD(f)]]
* [https://www.stmintz.com/ccc/index.php?id=379624 Fail-high on first move stat (86%)] by Michael Henderson, [[CCC]], July 29, 2004 » [[Move Ordering]]
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=30333 Return eval or upper bound?] by [[John Merlino]], [[CCC]], October 26, 2009
==2010 ...==
* [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
==2015 ...==
* [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]]
=External Links=
* [http://web.archive.org/web/20040512194831/brucemo.com/compchess/programming/glossary.htm#fail-high Programming - Glossary - Fail Low, Fail High] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm Programming Topics Site]
=References=
<references />
'''[[Alpha-Beta|Up one Level]]'''
