25,161
edits
Changes
Created page with "'''Home * Search * Selectivity * Extensions * Singular Extensions''' FILE:Uplifting.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Extensions]] * Singular Extensions'''
[[FILE:Uplifting.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d67d58ae5574bf8baa| [[Arts#Bak|Samuel Bak]] - Uplifting <ref>Uplifting, Oil on Canvas, 24 x 36", [http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d67d58ae5574bf8baa Chess in the Art of Samuel Bak], [http://www.chgs.umn.edu/ Center for Holocaust & Genocide Studies], [https://en.wikipedia.org/wiki/University_of_Minnesota University of Minnesota]</ref>]]
'''Singular Extensions''' (SE),<br/>
are domain-independent extensions introduced in 1988 by [[Thomas Anantharaman]], [[Murray Campbell]], and [[Feng-hsiung Hsu]] <ref>[[Thomas Anantharaman]], [[Murray Campbell]], [[Feng-hsiung Hsu]] ('''1988'''). ''Singular extensions: Adding Selectivity to Brute-Force Searching''. AAAI Spring Symposium, Computer Game Playing, pp. 8-13. Also published in [[ICGA Journal#11_4|ICCA Journal, Vol. 11, No. 4]], republished (1990) in [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 43, No. 1, pp. 99-109. ISSN 0004-3702</ref>, as implemented in [[ChipTest]] <ref>[http://groups.google.com/group/rec.games.chess/browse_frm/thread/b3b584ef5a572d79# Feng's (Deep Thought) article in Scientific American (long)] by [[Feng-hsiung Hsu]], [[Computer Chess Forums|rgc]], October 19, 1990</ref> and [[Deep Thought]]. The idea is to extend the search at expected [[Node Types#PV|PV-]] and [[Node Types#CUT|Cut-Nodes]], if one move seems to be a lot better than all of the alternatives. The problem is that one does not know in advance, and therefore has to perform a reduced search with a [[Null Window|null window]] lowered by some significant margin. Only if all alternatives fail below that window, a singular move is detected, and that move is re-searched with an extended [[Depth|depth]]. While it sounds expensive, the initial publication in 1988 reported encouraging results in tactical positions. In 1991, Anantharaman re-considered SE in comparison and interaction with other extensions, and mentioned implementation issues related to the [[Transposition Table|transposition table]] <ref>[[Thomas Anantharaman]] ('''1991'''). ''Confidently Selecting a Search Heuristic.'' [[ICGA Journal#14_1|ICCA Journal, Vol. 14, No. 1]]</ref> <ref>[[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. [[ICGA Journal#14_2|ICCA Journal, Vol. 14, No. 2]]</ref>. A somehow "reversed" idea compared to SE is [[Yngvi Björnsson|Björnsson's]] [[Multi-Cut]] <ref>[[Yngvi Björnsson]], [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search.'' Theoretical Computer Science, Vol. 252, pp. 177-196. [http://www.ru.is/faculty/yngvi/pdf/BjornssonM01a.pdf pdf]</ref> , to prune if in a reduced search multiple moves may [[Fail-High|fail high]].
=An Idea was born=
At [[ACM 1986]], in the [[Bebe#Singular|battle for the second place]], [[Bebe]] was defeated by [[Lachex]]. Both programs went in a sequence of forced moves where both sides had only one single good choice along the way. Neither program had any idea about who would come up ahead in the end, until suddenly after playing along the forced line, both programs realized that Bebe was lost. In a discussion with [[Feng-hsiung Hsu]] and others, [[Tony Scherzer]] made the statement that the old idea of selective [[Pruning|pruning]] was dead, replaced by the new idea of selective [[Extensions|extensions]]. According to Hsu, that was how the idea of Singular Extensions began <ref>[[Feng-hsiung Hsu]] ('''2002'''). ''[http://press.princeton.edu/titles/7342.html Behind Deep Blue]: Building the Computer that Defeated the World Chess Champion'', Princeton University Press, ISBN 0-691-09065-3, pp. 54-55</ref>.
<span id="SingularityAndPathology"></span>
=Singularity and Pathology=
[[Thomas Anantharaman]] in ''Extension Heuristics'' <ref>[[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. [[ICGA Journal#14_2|ICCA Journal, Vol. 14, No. 2]]</ref> :
In his Ph.D. thesis, [[Günther Schrüfer|Schrüfer]] proves <ref>[[Günther Schrüfer]] ('''1988'''). ''Minimax-Suchen : Kosten, Qualität und Algorithmen''. Braunschweig : TU, 1988. (German)</ref> that singularity is related to [[Search Pathology|pathology]] in game trees: intuitively, if there are too many singular moves in a game tree, [[Brute-Force|brute-force]] [[Minimax|minimax search]] becomes pathological, beyond a certain [[Depth|depth]] deep searches are worse than shallow searches. More specifically for brute-force minimax search, where the [[Evaluation|leaf evaluation]] values are just [-1,1] (lose or win), then one necessary condition for the absence of pathology is that the fraction of nodes other than [[Node Types#PV|PV-nodes]] whose value is dependent on a single successor (singular) must be less than 1/B, where B is the [[Branching Factor|branching factor]] (36 for typical middle games). This result can be extended to the case when more than one value is assigned to [[Leaf Node|leaf nodes]], though the resultant statement is more complicated. Intuitively, brute-force minimax search becomes pathological because it devotes too little effort to critical lines. The singular extension heuristic can be seen as a solution to this problem.
<span id="RestrictedSE"></span>
=Restricted SE=
A somehow relaxed version of SE was implemented in [[Stockfish|Stockfish 1.6]] in 2009, restricted to moves found in the [[Transposition Table|TT]] with a [[Lower Bound|lower bound flag]] set. According to [[Larry Kaufman]] the idea may have its origin from [[Rybka|Rybka 3]] via the disputed open source program [[Ippolit]] or its successors <ref>[http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=14574 A question to Larry Kaufman], [[Computer Chess Forums|Rybka Forum]], December 30/31, 2009</ref> :
At least one idea discussed on other forums that was attributed to Rybka 3 via the clone is already implemented in Stockfish 1.6, and was apparently the main reason for its large jump in strength over 1.5. So at least this idea will surely be in all top programs soon. Some developers will study the clone code themselves, while others may only use ideas they read about that came from the clone, but sooner or later other programs will show large gains from this information. At the very least, once an idea is implemented in a legitimate open-source program like Stockfish, it becomes accepted as something every programmer may use.
I don't think this is the place to publicize ideas from Rybka that were supposed to be secret, but the Stockfish 1.6 notes make it obvious that the big change in this version was a new way of doing "singular extension", improved from the way it was done in Deep Thought/Deep Blue.
Clearly the reverse engineering of Rybka is indeed "the highest form of flattery"; as to why the author(s) of the clone don't openly admit it I can't say. But the specific idea I'm talking about here is attributed to the clone (and hence by implication to Rykba) in the forum where it was discussed, so I don't think Stockfish or any other program which uses this idea is denying its origin. Once a good idea becomes common knowledge, regardless of its origin, programmers must use it (if it helps) to remain competitive.
=See also=
* [[Check Extensions]]
* [[One Reply Extensions]]
* [[Recapture Extensions]]
* [[Multi-Cut]]
=Publications=
<ref>[http://ilk.uvt.nl/icga/journal/docs/References.pdf ICGA Reference Database] (pdf)</ref>
* [[Thomas Anantharaman]], [[Murray Campbell]], [[Feng-hsiung Hsu]] ('''1988'''). ''Singular extensions: Adding Selectivity to Brute-Force Searching''. AAAI Spring Symposium, Computer Game Playing, pp. 8-13. Also published in [[ICGA Journal#11_4|ICCA Journal, Vol. 11, No. 4]], republished (1990) in [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 43, No. 1, pp. 99-109. ISSN 0004-3702. <ref>[http://www.talkchess.com/forum/viewtopic.php?t=53713 Paper "Singular Extensions" by Anantharaman, Campbell, and Hsu (1988)] by [[Roland Stuckardt]], [[CCC]], September 15, 2014</ref>
* [[Thomas Anantharaman]], [[Murray Campbell]], [[Feng-hsiung Hsu]] ('''1990'''). ''Singular Extensions: Adding Selectivity to Brute-Force Searching''. Artif. Intell. 43(1): 99-109
* [[Thomas Anantharaman]] ('''1991'''). ''Confidently Selecting a Search Heuristic.'' [[ICGA Journal#14_1|ICCA Journal, Vol. 14, No. 1]]
* [[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. [[ICGA Journal#14_2|ICCA Journal, Vol. 14, No. 2]]
* [[Tony Marsland]], [[Yngvi Björnsson]] ('''2001'''). ''Variable Depth Search.'' [[Advances in Computer Games 9]], pp. 9-24. [http://www.ru.is/faculty/yngvi/pdf/MarslandB01.pdf pdf]
=Forum Posts=
==1990 ...==
* [http://groups.google.com/group/rec.games.chess/browse_frm/thread/b3b584ef5a572d79# Feng's (Deep Thought) article in Scientific American (long)] by [[Feng-hsiung Hsu]], [[Computer Chess Forums|rgc]], October 19, 1990 <ref>[[Feng-hsiung Hsu]], [[Thomas Anantharaman]], [[Murray Campbell]], [[Andreas Nowatzyk]] ('''1990'''). ''A Grandmaster Chess Machine''. [[Scientific American]], Vol. 263, No. 4, pp. 44-50. ISSN 0036-8733. [http://www.disi.unige.it/person/DelzannoG/AI2/hsu.html Online Reprint]</ref>
==1995 ...==
* [http://groups.google.com/group/rec.games.chess/browse_frm/thread/195d7f43cbe85c98# Deep Thought], post 27 by [[Paul Hsieh]], [[Computer Chess Forums|rgc]], April 26, 1995
* [http://groups.google.com/group/rec.games.chess.misc/browse_frm/thread/17daf11c5654b174 Want pseudo code of chess programming algorithm] by Chavalit Likitvivatanavong, [[Computer Chess Forums|rgcc]], April 7, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7043cdb46dd2ef5b# Deep Blue and Bob Hyatt...]by [[Ed Schroder|Ed Schröder]], [[Computer Chess Forums|rgcc]], September 9, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/9356c55de4664308# Singular Extensions...] by [[Ed Schroder|Ed Schröder]], [[Computer Chess Forums|rgcc]], September 11, 1996
* [https://www.stmintz.com/ccc/index.php?id=13783 Singular extensions] by [[Bas Hamstra]], [[CCC]], January 08, 1998
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/e661555d60ae82e6# Singular extensions] by KK, [[Computer Chess Forums|rgcc]], April 12, 1998
* [https://www.stmintz.com/ccc/index.php?id=24282 questions about singular extensions] by [[Uri Blass]], [[CCC]], August 09, 1998
* [https://www.stmintz.com/ccc/index.php?id=33662 DB and Singular Extensions] by [[Jonathan Baxter]], [[CCC]], November 22, 1998
* [https://www.stmintz.com/ccc/index.php?id=41906 Bob's secret SE experiment] by [[Bas Hamstra]], [[CCC]], February 02, 1999
* [https://www.stmintz.com/ccc/index.php?id=43328 Singular Extensions, Nullmove deepsearch] by [[Frank Schneider]], [[CCC]], February 16, 1999 » [[Null Move Pruning]]
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=88189 Checks in qsearch/singular extensions] by [[James Robertson]], [[CCC]], January 12, 2000
* [https://www.stmintz.com/ccc/index.php?id=125295 singular extension] by [[Frank Phillips]], [[CCC]], August 20, 2000
* [https://www.stmintz.com/ccc/index.php?id=130980 singular extensions?] by [[Martin Fierz]], [[CCC]], September 29, 2000
* [https://www.stmintz.com/ccc/index.php?id=170356 Limited singular extensions. Anybody tried?] by [[Miguel A. Ballicora]], [[CCC]], May 18, 2001
* [https://www.stmintz.com/ccc/index.php?id=209565 Re: Nice tactical shot] by [[Steve Timson]], [[CCC]], January 24, 2002
* [https://www.stmintz.com/ccc/index.php?id=340288 Q: Singular extensions] by [[José Carlos Martínez Galán|José Carlos]], [[CCC]], January 05, 2004
* [https://www.stmintz.com/ccc/index.php?id=387763 singular extension] by [[Stuart Cracraft]], [[CCC]], September 15, 2004
* [https://www.stmintz.com/ccc/index.php?id=393739 Which programs have Singular Extensions?] by Joshua Lee, [[CCC]], October 28, 2004
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=407576 New Algorithm for "el cheapo Singular Extensions" :)], [http://www.future-shape.com/steinhage.html Dr. Axel Steinhage], [[CCC]], January 26, 2005
* [https://www.stmintz.com/ccc/index.php?id=428759 Re: Singular extensions and null move] by [[Gian-Carlo Pascutto]], [[CCC]], May 29, 2005 » [[Null Move Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=30211 Singular Extensions revisited] by [[Mark Lefler]], [[CCC]], October 19, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=35302 iid and singular extensions] by [[Daniel Shawul]], [[CCC]], July 05, 2010 » [[Internal Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=35419 Stockfish Singular Extension, does it make sense?] by [[Volker Böhm]], [[CCC]], July 08, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=35603 Singular Extensions] by [[Robert Hyatt]], [[CCC]], July 28, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=35697 Mult-cut, SE and ETC] by Ricardo Gibert, [[CCC]], August 05, 2010 » [[Multi-Cut]], [[Enhanced Transposition Cutoff]]
* [http://www.talkchess.com/forum/viewtopic.php?t=35698 next singular extension test] by [[Robert Hyatt]], [[CCC]], August 05, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=35898 Singular extension tests] by [[Robert Hyatt]], [[CCC]], August 26, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=38104 The "Secret" TT-move Singular Extension] by [[Edward Yu]], [[CCC]], February 17, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=42419 Singular Margin based on depth?] by [[Larry Kaufman]], [[CCC]], February 11, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=53713 Paper "Singular Extensions" by Anantharaman, Campbell, and Hsu (1988)] by [[Roland Stuckardt]], [[CCC]], September 15, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54281 search extensions] by [[Robert Hyatt]], [[CCC]], November 08, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55734 Singular extensions] by [[Shawn Chidester]], [[CCC]], March 21, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57004 Singular extension] by [[Harm Geert Muller]], [[CCC]], July 17, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=60435 Singular extension] by [[Daniel José Queraltó]], [[CCC]], June 11, 2016 » [[Andscacs]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66270 Singular extension improvement idea] by [[Jerry Donald]], [[CCC]], January 08, 2018
=External Links=
* [http://web.archive.org/web/20040420020213/brucemo.com/compchess/programming/extensions.htm#singular Singular extension] from [http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm Programming Topics] by [[Bruce Moreland]]
* [http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-v-advanced-search-r1197 Chess Programming Part V: Advanced Search] from [[François-Dominic Laramée#Chess Programming|Chess Programming]] by [[François-Dominic Laramée]], [http://www.gamedev.net/ gamedev.net]
* [http://travisreuter.com/ Travis Reuter Quintet] - [http://www.allaboutjazz.com/rotational-templates-travis-reuter-new-focus-recordings-review-by-glenn-astarita.php Singular Arrays], [http://www.newfocusrecordings.com/catalogue/travis-reuter-rotational-templates/ Rotational Templates] (2012), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [http://travisreuter.com/ Travis Reuter], [http://jeremyviner.com/ Jeremy Viner], [http://bobbyavey.com/ Bobby Avey], [https://de.wikipedia.org/wiki/Chris_Tordini Chris Tordini], [http://www.discogs.com/artist/1206973-Jason-Nazary Jason Nazary]
: {{#evu:https://www.youtube.com/watch?v=-bJmHBqPvNs|alignment=left|valignment=top}}
=References=
<references />
'''[[Extensions|Up one Level]]'''
[[FILE:Uplifting.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d67d58ae5574bf8baa| [[Arts#Bak|Samuel Bak]] - Uplifting <ref>Uplifting, Oil on Canvas, 24 x 36", [http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d67d58ae5574bf8baa Chess in the Art of Samuel Bak], [http://www.chgs.umn.edu/ Center for Holocaust & Genocide Studies], [https://en.wikipedia.org/wiki/University_of_Minnesota University of Minnesota]</ref>]]
'''Singular Extensions''' (SE),<br/>
are domain-independent extensions introduced in 1988 by [[Thomas Anantharaman]], [[Murray Campbell]], and [[Feng-hsiung Hsu]] <ref>[[Thomas Anantharaman]], [[Murray Campbell]], [[Feng-hsiung Hsu]] ('''1988'''). ''Singular extensions: Adding Selectivity to Brute-Force Searching''. AAAI Spring Symposium, Computer Game Playing, pp. 8-13. Also published in [[ICGA Journal#11_4|ICCA Journal, Vol. 11, No. 4]], republished (1990) in [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 43, No. 1, pp. 99-109. ISSN 0004-3702</ref>, as implemented in [[ChipTest]] <ref>[http://groups.google.com/group/rec.games.chess/browse_frm/thread/b3b584ef5a572d79# Feng's (Deep Thought) article in Scientific American (long)] by [[Feng-hsiung Hsu]], [[Computer Chess Forums|rgc]], October 19, 1990</ref> and [[Deep Thought]]. The idea is to extend the search at expected [[Node Types#PV|PV-]] and [[Node Types#CUT|Cut-Nodes]], if one move seems to be a lot better than all of the alternatives. The problem is that one does not know in advance, and therefore has to perform a reduced search with a [[Null Window|null window]] lowered by some significant margin. Only if all alternatives fail below that window, a singular move is detected, and that move is re-searched with an extended [[Depth|depth]]. While it sounds expensive, the initial publication in 1988 reported encouraging results in tactical positions. In 1991, Anantharaman re-considered SE in comparison and interaction with other extensions, and mentioned implementation issues related to the [[Transposition Table|transposition table]] <ref>[[Thomas Anantharaman]] ('''1991'''). ''Confidently Selecting a Search Heuristic.'' [[ICGA Journal#14_1|ICCA Journal, Vol. 14, No. 1]]</ref> <ref>[[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. [[ICGA Journal#14_2|ICCA Journal, Vol. 14, No. 2]]</ref>. A somehow "reversed" idea compared to SE is [[Yngvi Björnsson|Björnsson's]] [[Multi-Cut]] <ref>[[Yngvi Björnsson]], [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search.'' Theoretical Computer Science, Vol. 252, pp. 177-196. [http://www.ru.is/faculty/yngvi/pdf/BjornssonM01a.pdf pdf]</ref> , to prune if in a reduced search multiple moves may [[Fail-High|fail high]].
=An Idea was born=
At [[ACM 1986]], in the [[Bebe#Singular|battle for the second place]], [[Bebe]] was defeated by [[Lachex]]. Both programs went in a sequence of forced moves where both sides had only one single good choice along the way. Neither program had any idea about who would come up ahead in the end, until suddenly after playing along the forced line, both programs realized that Bebe was lost. In a discussion with [[Feng-hsiung Hsu]] and others, [[Tony Scherzer]] made the statement that the old idea of selective [[Pruning|pruning]] was dead, replaced by the new idea of selective [[Extensions|extensions]]. According to Hsu, that was how the idea of Singular Extensions began <ref>[[Feng-hsiung Hsu]] ('''2002'''). ''[http://press.princeton.edu/titles/7342.html Behind Deep Blue]: Building the Computer that Defeated the World Chess Champion'', Princeton University Press, ISBN 0-691-09065-3, pp. 54-55</ref>.
<span id="SingularityAndPathology"></span>
=Singularity and Pathology=
[[Thomas Anantharaman]] in ''Extension Heuristics'' <ref>[[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. [[ICGA Journal#14_2|ICCA Journal, Vol. 14, No. 2]]</ref> :
In his Ph.D. thesis, [[Günther Schrüfer|Schrüfer]] proves <ref>[[Günther Schrüfer]] ('''1988'''). ''Minimax-Suchen : Kosten, Qualität und Algorithmen''. Braunschweig : TU, 1988. (German)</ref> that singularity is related to [[Search Pathology|pathology]] in game trees: intuitively, if there are too many singular moves in a game tree, [[Brute-Force|brute-force]] [[Minimax|minimax search]] becomes pathological, beyond a certain [[Depth|depth]] deep searches are worse than shallow searches. More specifically for brute-force minimax search, where the [[Evaluation|leaf evaluation]] values are just [-1,1] (lose or win), then one necessary condition for the absence of pathology is that the fraction of nodes other than [[Node Types#PV|PV-nodes]] whose value is dependent on a single successor (singular) must be less than 1/B, where B is the [[Branching Factor|branching factor]] (36 for typical middle games). This result can be extended to the case when more than one value is assigned to [[Leaf Node|leaf nodes]], though the resultant statement is more complicated. Intuitively, brute-force minimax search becomes pathological because it devotes too little effort to critical lines. The singular extension heuristic can be seen as a solution to this problem.
<span id="RestrictedSE"></span>
=Restricted SE=
A somehow relaxed version of SE was implemented in [[Stockfish|Stockfish 1.6]] in 2009, restricted to moves found in the [[Transposition Table|TT]] with a [[Lower Bound|lower bound flag]] set. According to [[Larry Kaufman]] the idea may have its origin from [[Rybka|Rybka 3]] via the disputed open source program [[Ippolit]] or its successors <ref>[http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=14574 A question to Larry Kaufman], [[Computer Chess Forums|Rybka Forum]], December 30/31, 2009</ref> :
At least one idea discussed on other forums that was attributed to Rybka 3 via the clone is already implemented in Stockfish 1.6, and was apparently the main reason for its large jump in strength over 1.5. So at least this idea will surely be in all top programs soon. Some developers will study the clone code themselves, while others may only use ideas they read about that came from the clone, but sooner or later other programs will show large gains from this information. At the very least, once an idea is implemented in a legitimate open-source program like Stockfish, it becomes accepted as something every programmer may use.
I don't think this is the place to publicize ideas from Rybka that were supposed to be secret, but the Stockfish 1.6 notes make it obvious that the big change in this version was a new way of doing "singular extension", improved from the way it was done in Deep Thought/Deep Blue.
Clearly the reverse engineering of Rybka is indeed "the highest form of flattery"; as to why the author(s) of the clone don't openly admit it I can't say. But the specific idea I'm talking about here is attributed to the clone (and hence by implication to Rykba) in the forum where it was discussed, so I don't think Stockfish or any other program which uses this idea is denying its origin. Once a good idea becomes common knowledge, regardless of its origin, programmers must use it (if it helps) to remain competitive.
=See also=
* [[Check Extensions]]
* [[One Reply Extensions]]
* [[Recapture Extensions]]
* [[Multi-Cut]]
=Publications=
<ref>[http://ilk.uvt.nl/icga/journal/docs/References.pdf ICGA Reference Database] (pdf)</ref>
* [[Thomas Anantharaman]], [[Murray Campbell]], [[Feng-hsiung Hsu]] ('''1988'''). ''Singular extensions: Adding Selectivity to Brute-Force Searching''. AAAI Spring Symposium, Computer Game Playing, pp. 8-13. Also published in [[ICGA Journal#11_4|ICCA Journal, Vol. 11, No. 4]], republished (1990) in [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 43, No. 1, pp. 99-109. ISSN 0004-3702. <ref>[http://www.talkchess.com/forum/viewtopic.php?t=53713 Paper "Singular Extensions" by Anantharaman, Campbell, and Hsu (1988)] by [[Roland Stuckardt]], [[CCC]], September 15, 2014</ref>
* [[Thomas Anantharaman]], [[Murray Campbell]], [[Feng-hsiung Hsu]] ('''1990'''). ''Singular Extensions: Adding Selectivity to Brute-Force Searching''. Artif. Intell. 43(1): 99-109
* [[Thomas Anantharaman]] ('''1991'''). ''Confidently Selecting a Search Heuristic.'' [[ICGA Journal#14_1|ICCA Journal, Vol. 14, No. 1]]
* [[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. [[ICGA Journal#14_2|ICCA Journal, Vol. 14, No. 2]]
* [[Tony Marsland]], [[Yngvi Björnsson]] ('''2001'''). ''Variable Depth Search.'' [[Advances in Computer Games 9]], pp. 9-24. [http://www.ru.is/faculty/yngvi/pdf/MarslandB01.pdf pdf]
=Forum Posts=
==1990 ...==
* [http://groups.google.com/group/rec.games.chess/browse_frm/thread/b3b584ef5a572d79# Feng's (Deep Thought) article in Scientific American (long)] by [[Feng-hsiung Hsu]], [[Computer Chess Forums|rgc]], October 19, 1990 <ref>[[Feng-hsiung Hsu]], [[Thomas Anantharaman]], [[Murray Campbell]], [[Andreas Nowatzyk]] ('''1990'''). ''A Grandmaster Chess Machine''. [[Scientific American]], Vol. 263, No. 4, pp. 44-50. ISSN 0036-8733. [http://www.disi.unige.it/person/DelzannoG/AI2/hsu.html Online Reprint]</ref>
==1995 ...==
* [http://groups.google.com/group/rec.games.chess/browse_frm/thread/195d7f43cbe85c98# Deep Thought], post 27 by [[Paul Hsieh]], [[Computer Chess Forums|rgc]], April 26, 1995
* [http://groups.google.com/group/rec.games.chess.misc/browse_frm/thread/17daf11c5654b174 Want pseudo code of chess programming algorithm] by Chavalit Likitvivatanavong, [[Computer Chess Forums|rgcc]], April 7, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7043cdb46dd2ef5b# Deep Blue and Bob Hyatt...]by [[Ed Schroder|Ed Schröder]], [[Computer Chess Forums|rgcc]], September 9, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/9356c55de4664308# Singular Extensions...] by [[Ed Schroder|Ed Schröder]], [[Computer Chess Forums|rgcc]], September 11, 1996
* [https://www.stmintz.com/ccc/index.php?id=13783 Singular extensions] by [[Bas Hamstra]], [[CCC]], January 08, 1998
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/e661555d60ae82e6# Singular extensions] by KK, [[Computer Chess Forums|rgcc]], April 12, 1998
* [https://www.stmintz.com/ccc/index.php?id=24282 questions about singular extensions] by [[Uri Blass]], [[CCC]], August 09, 1998
* [https://www.stmintz.com/ccc/index.php?id=33662 DB and Singular Extensions] by [[Jonathan Baxter]], [[CCC]], November 22, 1998
* [https://www.stmintz.com/ccc/index.php?id=41906 Bob's secret SE experiment] by [[Bas Hamstra]], [[CCC]], February 02, 1999
* [https://www.stmintz.com/ccc/index.php?id=43328 Singular Extensions, Nullmove deepsearch] by [[Frank Schneider]], [[CCC]], February 16, 1999 » [[Null Move Pruning]]
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=88189 Checks in qsearch/singular extensions] by [[James Robertson]], [[CCC]], January 12, 2000
* [https://www.stmintz.com/ccc/index.php?id=125295 singular extension] by [[Frank Phillips]], [[CCC]], August 20, 2000
* [https://www.stmintz.com/ccc/index.php?id=130980 singular extensions?] by [[Martin Fierz]], [[CCC]], September 29, 2000
* [https://www.stmintz.com/ccc/index.php?id=170356 Limited singular extensions. Anybody tried?] by [[Miguel A. Ballicora]], [[CCC]], May 18, 2001
* [https://www.stmintz.com/ccc/index.php?id=209565 Re: Nice tactical shot] by [[Steve Timson]], [[CCC]], January 24, 2002
* [https://www.stmintz.com/ccc/index.php?id=340288 Q: Singular extensions] by [[José Carlos Martínez Galán|José Carlos]], [[CCC]], January 05, 2004
* [https://www.stmintz.com/ccc/index.php?id=387763 singular extension] by [[Stuart Cracraft]], [[CCC]], September 15, 2004
* [https://www.stmintz.com/ccc/index.php?id=393739 Which programs have Singular Extensions?] by Joshua Lee, [[CCC]], October 28, 2004
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=407576 New Algorithm for "el cheapo Singular Extensions" :)], [http://www.future-shape.com/steinhage.html Dr. Axel Steinhage], [[CCC]], January 26, 2005
* [https://www.stmintz.com/ccc/index.php?id=428759 Re: Singular extensions and null move] by [[Gian-Carlo Pascutto]], [[CCC]], May 29, 2005 » [[Null Move Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=30211 Singular Extensions revisited] by [[Mark Lefler]], [[CCC]], October 19, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=35302 iid and singular extensions] by [[Daniel Shawul]], [[CCC]], July 05, 2010 » [[Internal Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=35419 Stockfish Singular Extension, does it make sense?] by [[Volker Böhm]], [[CCC]], July 08, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=35603 Singular Extensions] by [[Robert Hyatt]], [[CCC]], July 28, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=35697 Mult-cut, SE and ETC] by Ricardo Gibert, [[CCC]], August 05, 2010 » [[Multi-Cut]], [[Enhanced Transposition Cutoff]]
* [http://www.talkchess.com/forum/viewtopic.php?t=35698 next singular extension test] by [[Robert Hyatt]], [[CCC]], August 05, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=35898 Singular extension tests] by [[Robert Hyatt]], [[CCC]], August 26, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=38104 The "Secret" TT-move Singular Extension] by [[Edward Yu]], [[CCC]], February 17, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=42419 Singular Margin based on depth?] by [[Larry Kaufman]], [[CCC]], February 11, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=53713 Paper "Singular Extensions" by Anantharaman, Campbell, and Hsu (1988)] by [[Roland Stuckardt]], [[CCC]], September 15, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54281 search extensions] by [[Robert Hyatt]], [[CCC]], November 08, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55734 Singular extensions] by [[Shawn Chidester]], [[CCC]], March 21, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57004 Singular extension] by [[Harm Geert Muller]], [[CCC]], July 17, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=60435 Singular extension] by [[Daniel José Queraltó]], [[CCC]], June 11, 2016 » [[Andscacs]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66270 Singular extension improvement idea] by [[Jerry Donald]], [[CCC]], January 08, 2018
=External Links=
* [http://web.archive.org/web/20040420020213/brucemo.com/compchess/programming/extensions.htm#singular Singular extension] from [http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm Programming Topics] by [[Bruce Moreland]]
* [http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-v-advanced-search-r1197 Chess Programming Part V: Advanced Search] from [[François-Dominic Laramée#Chess Programming|Chess Programming]] by [[François-Dominic Laramée]], [http://www.gamedev.net/ gamedev.net]
* [http://travisreuter.com/ Travis Reuter Quintet] - [http://www.allaboutjazz.com/rotational-templates-travis-reuter-new-focus-recordings-review-by-glenn-astarita.php Singular Arrays], [http://www.newfocusrecordings.com/catalogue/travis-reuter-rotational-templates/ Rotational Templates] (2012), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [http://travisreuter.com/ Travis Reuter], [http://jeremyviner.com/ Jeremy Viner], [http://bobbyavey.com/ Bobby Avey], [https://de.wikipedia.org/wiki/Chris_Tordini Chris Tordini], [http://www.discogs.com/artist/1206973-Jason-Nazary Jason Nazary]
: {{#evu:https://www.youtube.com/watch?v=-bJmHBqPvNs|alignment=left|valignment=top}}
=References=
<references />
'''[[Extensions|Up one Level]]'''
