25,161
edits
Changes
Created page with "'''Home * Search * Alpha-Beta * Fail-Soft''' '''Fail-Soft''' is a term related to an Alpha-Beta like search. Returned scores might be out..."
'''[[Main Page|Home]] * [[Search]] * [[Alpha-Beta]] * Fail-Soft'''
'''Fail-Soft''' is a term related to an [[Alpha-Beta]] like [[Search|search]]. Returned scores might be outside the [[Bound|bounds]]:
* an [[Upper Bound|upper bound]] less than [[Alpha|alpha]] at [[Node Types#ALL|All-Nodes]]
* a [[Lower Bound|lower bound]] greater than [[Beta|beta]] at [[Node Types#CUT|Cut-Nodes]]
<span id="History"></span>
=History=
In his 1983 paper ''Another optimization of alpha-beta search'' <ref>[[John Philip Fishburn]] ('''1983'''). ''[http://portal.acm.org/citation.cfm?id=1056623.1056628&coll=DL&dl=GUIDE&CFID=26266656&CFTOKEN=86225814 Another optimization of alpha-beta search]''. [[ACM#SIG|SIGART Bulletin]], Issue 84, [https://drive.google.com/file/d/0B2pvWWlf39g-cjJpZkc1cDhfbkk/view pdf]</ref>, [[John Philip Fishburn]] introduced Fail-Soft [[Alpha-Beta]] as an improvement of [[Fail-Hard]] without any extra work <ref>[[Jean-Christophe Weill]] ('''1991'''). ''Experiments With the NegaC* Search - An Alternative for Othello Endgame Search.'' [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]]</ref>. Fail-Soft has the reputation for searching less [[Node|nodes]] than Fail-Hard, but might also require some care regarding to [[Search Instability|search instability]] issues in conjunction with [[Transposition Table|transposition tables]] and various [[Pruning|pruning]]-, [[Reductions|reduction]]- and [[Extensions|extension]] techniques.
=Mate Scores=
In [[Chrilly Donninger|Chrilly Donninger's]] initial [[Null Move Pruning|null move pruning]] implementation there was a [[Null Move Pruning#ThreatDetection|deep search extension]] <ref>[[Chrilly Donninger]] ('''1993'''). ''Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs.'' [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]</ref>, if the null move was refuted by a mate attack, thus relying on Fail-Soft of a [[Null Window|null window]] search, where many "random" moves may refute the null-move with or without [[Score|score]] in the mate range.
=See also=
* [[Fail-Hard]]
* [[Fail-High]]
* [[Fail-Low]]
* [[Principal Variation Search]]
* [[NegaScout]]
* [[NegaC*]]
* [[MTD(f)]]
=Publications=
* [[John Philip Fishburn]] ('''1983'''). ''[http://portal.acm.org/citation.cfm?id=1056623.1056628&coll=DL&dl=GUIDE&CFID=26266656&CFTOKEN=86225814 Another optimization of alpha-beta search]''. [[ACM#SIG|SIGART Bulletin]], Issue 84, [https://drive.google.com/file/d/0B2pvWWlf39g-cjJpZkc1cDhfbkk/view pdf]
=Forum Posts=
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/a895e1a5524f8158 New improvement to alpha/beta + TT?] by [[Heiner Marxen]], [[Computer Chess Forums|rgcc]], January 13, 1997
* [https://www.stmintz.com/ccc/index.php?id=45482 Fail-soft with PVS?] by [[Will Singleton]], [[CCC]], March 09, 1999 » [[Principal Variation Search]]
* [https://www.stmintz.com/ccc/index.php?id=65947 What is the advantage of fail-soft?] by [[Bas Hamstra]], [[CCC]], August 25, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=136488 Fail-soft or Fail-hard ?] by [[Teerapong Tovirat]], [[CCC]], November 04, 2000 » [[Fail-Hard]]
* [https://www.stmintz.com/ccc/index.php?id=144854 Alpha beta fail soft, pruning & hash bounds?] by [[Steve Maughan]], [[CCC]], December 14, 2000 » [[Pruning]], [[Bound]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/287d76556a5a298c Fail Soft Alpha Beta & Transpositions] by Orhan Öztürk, [[Computer Chess Forums|rgcc]], September 3, 2003
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/91dbbc00fc666c86 (Fail soft) alpha beta] by Delphi, [[Computer Chess Forums|rgcc]], September 4, 2003
* [https://www.stmintz.com/ccc/index.php?id=314585 Fail soft alpha-beta] by [[Russell Reagan]], [[CCC]], September 08, 2003
* [https://www.stmintz.com/ccc/index.php?id=316955 Is this a correct fail-soft?] by [[Mikael Bäckman]], [[CCC]], September 21, 2003
* [https://www.stmintz.com/ccc/index.php?id=360837 My fail soft reduces quality of collected PV. Help needed] by [[Volker Böhm]], [[CCC]], April 20, 2004
* [https://www.stmintz.com/ccc/index.php?id=363710 Fail-hard, fail-soft question] by [[Dan Honeycutt]], [[CCC]], May 06, 2004
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=487414 Fail Soft question] by [[David B. Weller]], [[CCC]], February 17, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6665 Search questions] by [[Sven Schüle]], [[Computer Chess Forums|Winboard Forum]], July 17, 2007 » [[Mate Distance Pruning]], [[Principal Variation Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=24560 mate detetion issue] by [[Mike Adams]], [[CCC]], October 24, 2008 » [[Checkmate]], [[Connect Four]]
* [http://www.talkchess.com/forum/viewtopic.php?t=24954 fail soft vs fail hard] by [[Matthew Lai|cyberfish]], [[CCC]], November 19, 2008
* [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-High]], [[Fail-Hard]]
* [http://www.talkchess.com/forum/viewtopic.php?t=51284 Fail soft vs fail hard] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], February 15, 2014 » [[Fail-Hard]], [[Fail-Low]], [[Internal Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54387 Implications of Lazy eval on Don Beal effect in Fail Soft] by [[Henk van den Belt]], [[CCC]], November 19, 2014 » [[Lazy Evaluation]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=60650 Multi-cut and fail-soft] by [[Matthew R. Brades]], [[CCC]], June 30, 2016 » [[Multi-Cut]]
=External Links=
* [https://en.wikipedia.org/wiki/Fail_soft Fail soft from Wikipedia]
* [[Videos#SoftMachine|Soft Machine]] - [https://en.wikipedia.org/wiki/Bundles_%28album%29 Hazard Profile] (1975), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: Lineup: [https://en.wikipedia.org/wiki/Mike_Ratledge Mike Ratledge], [[Videos#JohnMarshall|John Marshall]], [[Videos#KarlJenkins|Karl Jenkins]], [https://en.wikipedia.org/wiki/Roy_Babbington Roy Babbington], [[Videos#AllanHoldsworth|Allan Holdsworth]]
: {{#evu:https://www.youtube.com/watch?v=6zSZBAcQ-5M|alignment=left|valignment=top}}
* [[Videos#IanCarr|Ian Carr's]] [https://en.wikipedia.org/wiki/Nucleus_%28band%29 Nucleus] - Song For The Bearded Lady (1970), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: Lineup: [https://en.wikipedia.org/wiki/Ray_Russell_%28musician%29 Ray Russell], [[Videos#IanCarr|Ian Carr]], [https://en.wikipedia.org/wiki/Brian_Smith_%28musician%29 Brian Smith], [[Videos#KarlJenkins|Karl Jenkins]], [[Videos#JohnMarshall|John Marshall]], [https://en.wikipedia.org/wiki/Roy_Babbington Roy Babbington]
: {{#evu:https://www.youtube.com/watch?v=nnDgalLCFfw|alignment=left|valignment=top}}
=References=
<references />
'''[[Alpha-Beta|Up one Level]]'''
'''Fail-Soft''' is a term related to an [[Alpha-Beta]] like [[Search|search]]. Returned scores might be outside the [[Bound|bounds]]:
* an [[Upper Bound|upper bound]] less than [[Alpha|alpha]] at [[Node Types#ALL|All-Nodes]]
* a [[Lower Bound|lower bound]] greater than [[Beta|beta]] at [[Node Types#CUT|Cut-Nodes]]
<span id="History"></span>
=History=
In his 1983 paper ''Another optimization of alpha-beta search'' <ref>[[John Philip Fishburn]] ('''1983'''). ''[http://portal.acm.org/citation.cfm?id=1056623.1056628&coll=DL&dl=GUIDE&CFID=26266656&CFTOKEN=86225814 Another optimization of alpha-beta search]''. [[ACM#SIG|SIGART Bulletin]], Issue 84, [https://drive.google.com/file/d/0B2pvWWlf39g-cjJpZkc1cDhfbkk/view pdf]</ref>, [[John Philip Fishburn]] introduced Fail-Soft [[Alpha-Beta]] as an improvement of [[Fail-Hard]] without any extra work <ref>[[Jean-Christophe Weill]] ('''1991'''). ''Experiments With the NegaC* Search - An Alternative for Othello Endgame Search.'' [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]]</ref>. Fail-Soft has the reputation for searching less [[Node|nodes]] than Fail-Hard, but might also require some care regarding to [[Search Instability|search instability]] issues in conjunction with [[Transposition Table|transposition tables]] and various [[Pruning|pruning]]-, [[Reductions|reduction]]- and [[Extensions|extension]] techniques.
=Mate Scores=
In [[Chrilly Donninger|Chrilly Donninger's]] initial [[Null Move Pruning|null move pruning]] implementation there was a [[Null Move Pruning#ThreatDetection|deep search extension]] <ref>[[Chrilly Donninger]] ('''1993'''). ''Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs.'' [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]</ref>, if the null move was refuted by a mate attack, thus relying on Fail-Soft of a [[Null Window|null window]] search, where many "random" moves may refute the null-move with or without [[Score|score]] in the mate range.
=See also=
* [[Fail-Hard]]
* [[Fail-High]]
* [[Fail-Low]]
* [[Principal Variation Search]]
* [[NegaScout]]
* [[NegaC*]]
* [[MTD(f)]]
=Publications=
* [[John Philip Fishburn]] ('''1983'''). ''[http://portal.acm.org/citation.cfm?id=1056623.1056628&coll=DL&dl=GUIDE&CFID=26266656&CFTOKEN=86225814 Another optimization of alpha-beta search]''. [[ACM#SIG|SIGART Bulletin]], Issue 84, [https://drive.google.com/file/d/0B2pvWWlf39g-cjJpZkc1cDhfbkk/view pdf]
=Forum Posts=
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/a895e1a5524f8158 New improvement to alpha/beta + TT?] by [[Heiner Marxen]], [[Computer Chess Forums|rgcc]], January 13, 1997
* [https://www.stmintz.com/ccc/index.php?id=45482 Fail-soft with PVS?] by [[Will Singleton]], [[CCC]], March 09, 1999 » [[Principal Variation Search]]
* [https://www.stmintz.com/ccc/index.php?id=65947 What is the advantage of fail-soft?] by [[Bas Hamstra]], [[CCC]], August 25, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=136488 Fail-soft or Fail-hard ?] by [[Teerapong Tovirat]], [[CCC]], November 04, 2000 » [[Fail-Hard]]
* [https://www.stmintz.com/ccc/index.php?id=144854 Alpha beta fail soft, pruning & hash bounds?] by [[Steve Maughan]], [[CCC]], December 14, 2000 » [[Pruning]], [[Bound]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/287d76556a5a298c Fail Soft Alpha Beta & Transpositions] by Orhan Öztürk, [[Computer Chess Forums|rgcc]], September 3, 2003
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/91dbbc00fc666c86 (Fail soft) alpha beta] by Delphi, [[Computer Chess Forums|rgcc]], September 4, 2003
* [https://www.stmintz.com/ccc/index.php?id=314585 Fail soft alpha-beta] by [[Russell Reagan]], [[CCC]], September 08, 2003
* [https://www.stmintz.com/ccc/index.php?id=316955 Is this a correct fail-soft?] by [[Mikael Bäckman]], [[CCC]], September 21, 2003
* [https://www.stmintz.com/ccc/index.php?id=360837 My fail soft reduces quality of collected PV. Help needed] by [[Volker Böhm]], [[CCC]], April 20, 2004
* [https://www.stmintz.com/ccc/index.php?id=363710 Fail-hard, fail-soft question] by [[Dan Honeycutt]], [[CCC]], May 06, 2004
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=487414 Fail Soft question] by [[David B. Weller]], [[CCC]], February 17, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6665 Search questions] by [[Sven Schüle]], [[Computer Chess Forums|Winboard Forum]], July 17, 2007 » [[Mate Distance Pruning]], [[Principal Variation Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=24560 mate detetion issue] by [[Mike Adams]], [[CCC]], October 24, 2008 » [[Checkmate]], [[Connect Four]]
* [http://www.talkchess.com/forum/viewtopic.php?t=24954 fail soft vs fail hard] by [[Matthew Lai|cyberfish]], [[CCC]], November 19, 2008
* [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-High]], [[Fail-Hard]]
* [http://www.talkchess.com/forum/viewtopic.php?t=51284 Fail soft vs fail hard] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], February 15, 2014 » [[Fail-Hard]], [[Fail-Low]], [[Internal Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54387 Implications of Lazy eval on Don Beal effect in Fail Soft] by [[Henk van den Belt]], [[CCC]], November 19, 2014 » [[Lazy Evaluation]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=60650 Multi-cut and fail-soft] by [[Matthew R. Brades]], [[CCC]], June 30, 2016 » [[Multi-Cut]]
=External Links=
* [https://en.wikipedia.org/wiki/Fail_soft Fail soft from Wikipedia]
* [[Videos#SoftMachine|Soft Machine]] - [https://en.wikipedia.org/wiki/Bundles_%28album%29 Hazard Profile] (1975), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: Lineup: [https://en.wikipedia.org/wiki/Mike_Ratledge Mike Ratledge], [[Videos#JohnMarshall|John Marshall]], [[Videos#KarlJenkins|Karl Jenkins]], [https://en.wikipedia.org/wiki/Roy_Babbington Roy Babbington], [[Videos#AllanHoldsworth|Allan Holdsworth]]
: {{#evu:https://www.youtube.com/watch?v=6zSZBAcQ-5M|alignment=left|valignment=top}}
* [[Videos#IanCarr|Ian Carr's]] [https://en.wikipedia.org/wiki/Nucleus_%28band%29 Nucleus] - Song For The Bearded Lady (1970), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: Lineup: [https://en.wikipedia.org/wiki/Ray_Russell_%28musician%29 Ray Russell], [[Videos#IanCarr|Ian Carr]], [https://en.wikipedia.org/wiki/Brian_Smith_%28musician%29 Brian Smith], [[Videos#KarlJenkins|Karl Jenkins]], [[Videos#JohnMarshall|John Marshall]], [https://en.wikipedia.org/wiki/Roy_Babbington Roy Babbington]
: {{#evu:https://www.youtube.com/watch?v=nnDgalLCFfw|alignment=left|valignment=top}}
=References=
<references />
'''[[Alpha-Beta|Up one Level]]'''
