Singular Extensions (SE),
are domain-independent extensions introduced in 1988 by Thomas Anantharaman, Murray Campbell, and Feng-hsiung Hsu[1], as implemented in ChipTest[2] and Deep Thought. The idea is to extend the search at expected PV- and 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 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. 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[3][4]. A somehow "reversed" idea compared to SE is Björnsson'sMulti-Cut[5] , to prune if in a reduced search multiple moves may fail high.
At ACM 1986, in the 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 was dead, replaced by the new idea of selective extensions. According to Hsu, that was how the idea of Singular Extensions began [7].
In his Ph.D. thesis, Schrüfer proves[9]that singularity is related to pathology in game trees: intuitively, if there are too many singular moves in a game tree, brute-forceminimax search becomes pathological, beyond a certain depth deep searches are worse than shallow searches. More specifically for brute-force minimax search, where the 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 PV-nodes whose value is dependent on a single successor (singular) must be less than 1/B, where B is the branching factor (36 for typical middle games). This result can be extended to the case when more than one value is assigned to 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.
Restricted SE
A somehow relaxed version of SE was implemented in Stockfish 1.6 in 2009, restricted to moves found in the TT with a lower bound flag set. According to Larry Kaufman the idea may have its origin from Rybka 3 via the disputed open source program Ippolit or its successors [10] :
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.
^Feng-hsiung Hsu (2002). Behind Deep Blue: Building the Computer that Defeated the World Chess Champion, Princeton University Press, ISBN 0-691-09065-3, pp. 54-55
are domain-independent extensions introduced in 1988 by Thomas Anantharaman, Murray Campbell, and Feng-hsiung Hsu [1], as implemented in ChipTest [2] and Deep Thought. The idea is to extend the search at expected PV- and 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 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. 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 [3] [4]. A somehow "reversed" idea compared to SE is Björnsson's Multi-Cut [5] , to prune if in a reduced search multiple moves may fail high.
Table of Contents
An Idea was born
At ACM 1986, in the 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 was dead, replaced by the new idea of selective extensions. According to Hsu, that was how the idea of Singular Extensions began [7].Singularity and Pathology
Thomas Anantharaman in Extension Heuristics [8] :Restricted SE
A somehow relaxed version of SE was implemented in Stockfish 1.6 in 2009, restricted to moves found in the TT with a lower bound flag set. According to Larry Kaufman the idea may have its origin from Rybka 3 via the disputed open source program Ippolit or its successors [10] :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
Publications
[11]Forum Posts
1990 ...
1995 ...
2000 ...
2005 ...
2010 ...
2015 ...
External Links
Travis Reuter, Jeremy Viner, Bobby Avey, Chris Tordini, Jason Nazary
References
What links here?
Up one Level