Difference between revisions of "Fail-Soft"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
| (11 intermediate revisions by the same user not shown) | |||
| Line 27: | Line 27: | ||
=Forum Posts= | =Forum Posts= | ||
==1995 ...== | ==1995 ...== | ||
| + | * [https://groups.google.com/d/msg/rec.games.chess.computer/xkepvuKHYUc/vI9AK1G2KkwJ bounds in alpha-beta] by [[Walter Ravenek]], [[Computer Chess Forums|rgcc]], June 05, 1996 » [[Arthur]], [[Crafty]] | ||
* [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 | * [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=45482 Fail-soft with PVS?] by [[Will Singleton]], [[CCC]], March 09, 1999 » [[Principal Variation Search]] | ||
| Line 37: | Line 38: | ||
* [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=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=316955 Is this a correct fail-soft?] by [[Mikael Bäckman]], [[CCC]], September 21, 2003 | ||
| + | * [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=45430 fail soft question?] by [[Daniel Shawul]], [[Computer Chess Forums|Winboard Forum]], December 03, 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=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 | * [https://www.stmintz.com/ccc/index.php?id=363710 Fail-hard, fail-soft question] by [[Dan Honeycutt]], [[CCC]], May 06, 2004 | ||
| Line 42: | Line 44: | ||
* [https://www.stmintz.com/ccc/index.php?id=487414 Fail Soft question] by [[David B. Weller]], [[CCC]], February 17, 2006 | * [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.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/forum3/viewtopic.php?f=7&t=21627 Returning score] by [[Fermin Serrano]], [[CCC]], June 05, 2008 | ||
* [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=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=24954 fail soft vs fail hard] by [[Matthew Lai|cyberfish]], [[CCC]], November 19, 2008 | ||
| Line 49: | Line 52: | ||
* [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=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]] | * [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]] | ||
| − | |||
* [http://www.talkchess.com/forum/viewtopic.php?t=60650 Multi-cut and fail-soft] by [[Matthew R. Brades]], [[CCC]], June 30, 2016 » [[Multi-Cut]] | * [http://www.talkchess.com/forum/viewtopic.php?t=60650 Multi-cut and fail-soft] by [[Matthew R. Brades]], [[CCC]], June 30, 2016 » [[Multi-Cut]] | ||
| + | * [http://www.open-chess.org/viewtopic.php?f=5&t=3180 Fail Soft best practices] by kickstone, [[Computer Chess Forums|OpenChess Forum]], July 30, 2018 | ||
| + | ==2020 ...== | ||
| + | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79223 Fail hard/soft] by Philippe Chevalier, [[CCC]], January 28, 2022 | ||
=External Links= | =External Links= | ||
| + | * [https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning#Pseudocode Alpha–beta pruning from Wikipedia] | ||
| + | * [https://www.ics.uci.edu/~eppstein/180a/990202b.html Lecture notes for February 2, 1999 Variants of Alpha-Beta Search] by [[David Eppstein]] | ||
* [https://en.wiktionary.org/wiki/fail-soft fail-soft - Wiktionary] | * [https://en.wiktionary.org/wiki/fail-soft fail-soft - Wiktionary] | ||
* [https://en.wikipedia.org/wiki/Fail_soft Fail soft from Wikipedia] | * [https://en.wikipedia.org/wiki/Fail_soft Fail soft from Wikipedia] | ||
| − | * [[:Category:Soft Machine|Soft Machine]] - [https://en.wikipedia.org/wiki/Bundles_ | + | * [[:Category:Soft Machine|Soft Machine]] - [https://en.wikipedia.org/wiki/Bundles_(album) Hazard Profile], 1975, [https://en.wikipedia.org/wiki/YouTube YouTube] Video |
| − | : Lineup: [https://en.wikipedia.org/wiki/Mike_Ratledge Mike Ratledge], [[:Category:John Marshall|John Marshall]], [[:Category:Karl Jenkins|Karl Jenkins]], [ | + | : Lineup: [https://en.wikipedia.org/wiki/Mike_Ratledge Mike Ratledge], [[:Category:John Marshall|John Marshall]], [[:Category:Karl Jenkins|Karl Jenkins]], [[:Category:Roy Babbington|Roy Babbington]], [[:Category:Allan Holdsworth|Allan Holdsworth]] |
| − | : {{#evu:https://www.youtube.com/watch?v= | + | : {{#evu:https://www.youtube.com/watch?v=6zSZBAcQ-5M|alignment=left|valignment=top}} |
| − | * [[:Category:Ian Carr|Ian Carr's]] [ | + | * [[:Category:Ian Carr|Ian Carr's]] [[:Category:Nucleus|Nucleus]] - Song For The Bearded Lady (1970), [https://en.wikipedia.org/wiki/YouTube YouTube] Video |
| − | : Lineup: | + | : Lineup: [[:Category:Ian Carr|Ian Carr]], [https://en.wikipedia.org/wiki/Brian_Smith_%28musician%29 Brian Smith], [[:Category:Karl Jenkins|Karl Jenkins]], [[:Category:John Marshall|John Marshall]], [https://en.wikipedia.org/wiki/Chris_Spedding Chris Spedding], [[:Category:Jeff Clyne|Jeff Clyne]] |
| − | : {{#evu:https://www.youtube.com/watch?v= | + | : {{#evu:https://www.youtube.com/watch?v=lBK1s77r0Ao|alignment=left|valignment=top}} |
=References= | =References= | ||
<references /> | <references /> | ||
| − | |||
'''[[Alpha-Beta|Up one Level]]''' | '''[[Alpha-Beta|Up one Level]]''' | ||
[[Category:Soft Machine]] | [[Category:Soft Machine]] | ||
| + | [[Category:Nucleus]] | ||
| + | [[Category:Roy Babbington]] | ||
[[Category:Ian Carr]] | [[Category:Ian Carr]] | ||
| + | [[Category:Jeff Clyne]] | ||
[[Category:Allan Holdsworth]] | [[Category:Allan Holdsworth]] | ||
[[Category:Karl Jenkins]] | [[Category:Karl Jenkins]] | ||
[[Category:John Marshall]] | [[Category:John Marshall]] | ||
Latest revision as of 20:49, 12 March 2022
Home * Search * Alpha-Beta * Fail-Soft
Window of Perception [1]
Fail-Soft is a term related to an Alpha-Beta like search. Returned scores might be outside the bounds:
- an upper bound less than alpha at All-Nodes
- a lower bound greater than beta at Cut-Nodes
Contents
History
In his 1983 paper Another optimization of alpha-beta search [2], John Philip Fishburn introduced Fail-Soft Alpha-Beta as an improvement of Fail-Hard without any extra work [3]. Fail-Soft has the reputation for searching less nodes than Fail-Hard, but might also require some care regarding to search instability issues in conjunction with transposition tables and various pruning-, reduction- and extension techniques.
Mate Scores
In Chrilly Donninger's initial null move pruning implementation there was a deep search extension [4], if the null move was refuted by a mate attack, thus relying on Fail-Soft of a null window search, where many "random" moves may refute the null-move with or without score in the mate range.
See also
Publications
- John Philip Fishburn (1983). Another optimization of alpha-beta search. SIGART Bulletin, Issue 84, pdf
Forum Posts
1995 ...
- bounds in alpha-beta by Walter Ravenek, rgcc, June 05, 1996 » Arthur, Crafty
- New improvement to alpha/beta + TT? by Heiner Marxen, rgcc, January 13, 1997
- Fail-soft with PVS? by Will Singleton, CCC, March 09, 1999 » Principal Variation Search
- What is the advantage of fail-soft? by Bas Hamstra, CCC, August 25, 1999
2000 ...
- Fail-soft or Fail-hard ? by Teerapong Tovirat, CCC, November 04, 2000 » Fail-Hard
- Alpha beta fail soft, pruning & hash bounds? by Steve Maughan, CCC, December 14, 2000 » Pruning, Bound
- Fail Soft Alpha Beta & Transpositions by Orhan Öztürk, rgcc, September 3, 2003
- (Fail soft) alpha beta by Delphi, rgcc, September 4, 2003
- Fail soft alpha-beta by Russell Reagan, CCC, September 08, 2003
- Is this a correct fail-soft? by Mikael Bäckman, CCC, September 21, 2003
- fail soft question? by Daniel Shawul, Winboard Forum, December 03, 2003
- My fail soft reduces quality of collected PV. Help needed by Volker Böhm, CCC, April 20, 2004
- Fail-hard, fail-soft question by Dan Honeycutt, CCC, May 06, 2004
2005 ...
- Fail Soft question by David B. Weller, CCC, February 17, 2006
- Search questions by Sven Schüle, Winboard Forum, July 17, 2007 » Mate Distance Pruning, Principal Variation Search
- Returning score by Fermin Serrano, CCC, June 05, 2008
- mate detetion issue by Mike Adams, CCC, October 24, 2008 » Checkmate, Connect Four
- fail soft vs fail hard by cyberfish, CCC, November 19, 2008
- 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-High, Fail-Hard
- Fail soft vs fail hard by Sergei S. Markoff, CCC, February 15, 2014 » Fail-Hard, Fail-Low, Internal Iterative Deepening
- Implications of Lazy eval on Don Beal effect in Fail Soft by Henk van den Belt, CCC, November 19, 2014 » Lazy Evaluation
- Multi-cut and fail-soft by Matthew R. Brades, CCC, June 30, 2016 » Multi-Cut
- Fail Soft best practices by kickstone, OpenChess Forum, July 30, 2018
2020 ...
- Fail hard/soft by Philippe Chevalier, CCC, January 28, 2022
External Links
- Alpha–beta pruning from Wikipedia
- Lecture notes for February 2, 1999 Variants of Alpha-Beta Search by David Eppstein
- fail-soft - Wiktionary
- Fail soft from Wikipedia
- Soft Machine - Hazard Profile, 1975, YouTube Video
- Ian Carr's Nucleus - Song For The Bearded Lady (1970), YouTube Video
- Lineup: Ian Carr, Brian Smith, Karl Jenkins, John Marshall, Chris Spedding, Jeff Clyne
References
- ↑ Window of Perception (Jump Start Century 21 and move on) by Dominic01, May 19, 2013, Wikimedia Commons
- ↑ John Philip Fishburn (1983). Another optimization of alpha-beta search. SIGART Bulletin, Issue 84, pdf
- ↑ Jean-Christophe Weill (1991). Experiments With the NegaC* Search - An Alternative for Othello Endgame Search. Heuristic Programming in AI 2
- ↑ Chrilly Donninger (1993). Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs. ICCA Journal, Vol. 16, No. 3
