Singular Extensions
Home * Search * Selectivity * Extensions * Singular Extensions
Singular Extensions (SE),
are domain-independent extensions introduced in 1988 by Thomas Anantharaman, Murray Campbell, and Feng-hsiung Hsu [2], as implemented in ChipTest [3] 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 [4] [5]. A somehow "reversed" idea compared to SE is Björnsson's Multi-Cut [6] , to prune if in a reduced search multiple moves may fail high.
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] :
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-force minimax 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.
See also
Publications
- Thomas Anantharaman, Murray Campbell, Feng-hsiung Hsu (1988). Singular extensions: Adding Selectivity to Brute-Force Searching. AAAI Spring Symposium, Computer Game Playing, also in ICCA Journal, Vol. 11, No. 4, and (1990) in Artificial Intelligence, Vol. 43, No. 1 [12]
- Thomas Anantharaman, Murray Campbell, Feng-hsiung Hsu (1990). Singular Extensions: Adding Selectivity to Brute-Force Searching. Artificial Intelligence, Vol. 43, No. 1
- Thomas Anantharaman (1991). Confidently Selecting a Search Heuristic. ICCA Journal, Vol. 14, No. 1
- Thomas Anantharaman (1991). Extension Heuristics. ICCA Journal, Vol. 14, No. 2
- Tony Marsland, Yngvi Björnsson (2001). Variable Depth Search. Advances in Computer Games 9, pp. 9-24. pdf
Forum Posts
1990 ...
- Feng's (Deep Thought) article in Scientific American (long) by Feng-hsiung Hsu, rgc, October 19, 1990 [13]
1995 ...
- Re: Deep Thought by Paul Hsieh, rgc, April 26, 1995
- Want pseudo code of chess programming algorithm by Chavalit Likitvivatanavong, rgcc, April 7, 1996
- Deep Blue and Bob Hyatt...by Ed Schröder, rgcc, September 9, 1996
- Singular Extensions... by Ed Schröder, rgcc, September 11, 1996
- Singular extensions by Bas Hamstra, CCC, January 08, 1998
- Singular extensions by KK, rgcc, April 12, 1998
- questions about singular extensions by Uri Blass, CCC, August 09, 1998
- DB and Singular Extensions by Jonathan Baxter, CCC, November 22, 1998
- Bob's secret SE experiment by Bas Hamstra, CCC, February 02, 1999
- Singular Extensions, Nullmove deepsearch by Frank Schneider, CCC, February 16, 1999 » Null Move Pruning
2000 ...
- Checks in qsearch/singular extensions by James Robertson, CCC, January 12, 2000
- singular extension by Frank Phillips, CCC, August 20, 2000
- singular extensions? by Martin Fierz, CCC, September 29, 2000
- Limited singular extensions. Anybody tried? by Miguel A. Ballicora, CCC, May 18, 2001
- Re: Nice tactical shot by Steve Timson, CCC, January 24, 2002
- Q: Singular extensions by José Carlos, CCC, January 05, 2004
- singular extension by Stuart Cracraft, CCC, September 15, 2004
- Which programs have Singular Extensions? by Joshua Lee, CCC, October 28, 2004
2005 ...
- New Algorithm for "el cheapo Singular Extensions" :), Dr. Axel Steinhage, CCC, January 26, 2005
- Re: Singular extensions and null move by Gian-Carlo Pascutto, CCC, May 29, 2005 » Null Move Pruning
- Singular Extensions revisited by Mark Lefler, CCC, October 19, 2009
2010 ...
- iid and singular extensions by Daniel Shawul, CCC, July 05, 2010 » Internal Iterative Deepening
- Stockfish Singular Extension, does it make sense? by Volker Böhm, CCC, July 08, 2010
- Singular Extensions by Robert Hyatt, CCC, July 28, 2010
- Mult-cut, SE and ETC by Ricardo Gibert, CCC, August 05, 2010 » Multi-Cut, Enhanced Transposition Cutoff
- next singular extension test by Robert Hyatt, CCC, August 05, 2010
- Singular extension tests by Robert Hyatt, CCC, August 26, 2010
- The "Secret" TT-move Singular Extension by Edward Yu, CCC, February 17, 2011
- Singular Margin based on depth? by Larry Kaufman, CCC, February 11, 2012
- Paper "Singular Extensions" by Anantharaman, Campbell, and Hsu (1988) by Roland Stuckardt, CCC, September 15, 2014
- search extensions by Robert Hyatt, CCC, November 08, 2014
2015 ...
- Singular extensions by Shawn Chidester, CCC, March 21, 2015
- Singular extension by Harm Geert Muller, CCC, July 17, 2015
- Singular extension by Daniel José Queraltó, CCC, June 11, 2016 » Andscacs
- Singular extension improvement idea by Jerry Donald, CCC, January 08, 2018
- singular extension by Vivien Clauzon, CCC, August 24, 2018
- some questions about singular search in Stockfish by Jon Dart, CCC, November 01, 2019 » Stockfish
- ELO value of TTSE? by Tom King, CCC, December 29, 2019
External Links
References
- ↑ Uplifting, Oil on Canvas, 24 x 36", Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
- ↑ Thomas Anantharaman, Murray Campbell, Feng-hsiung Hsu (1988). Singular extensions: Adding Selectivity to Brute-Force Searching. AAAI Spring Symposium, Computer Game Playing, also in ICCA Journal, Vol. 11, No. 4, and (1990) in Artificial Intelligence, Vol. 43, No. 1
- ↑ Feng's (Deep Thought) article in Scientific American (long) by Feng-hsiung Hsu, rgc, October 19, 1990
- ↑ Thomas Anantharaman (1991). Confidently Selecting a Search Heuristic. ICCA Journal, Vol. 14, No. 1
- ↑ Thomas Anantharaman (1991). Extension Heuristics. ICCA Journal, Vol. 14, No. 2
- ↑ Yngvi Björnsson, Tony Marsland (2001). Multi-cut Alpha-Beta Pruning in Game Tree Search. Theoretical Computer Science, Vol. 252, pp. 177-196. pdf
- ↑ 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
- ↑ Thomas Anantharaman (1991). Extension Heuristics. ICCA Journal, Vol. 14, No. 2
- ↑ Günther Schrüfer (1988). Minimax-Suchen : Kosten, Qualität und Algorithmen. Braunschweig : TU, 1988. (German)
- ↑ A question to Larry Kaufman, Rybka Forum, December 30/31, 2009
- ↑ ICGA Reference Database (pdf)
- ↑ Paper "Singular Extensions" by Anantharaman, Campbell, and Hsu (1988) by Roland Stuckardt, CCC, September 15, 2014
- ↑ Feng-hsiung Hsu, Thomas Anantharaman, Murray Campbell, Andreas Nowatzyk (1990). A Grandmaster Chess Machine. Scientific American, Vol. 263, No. 4, Online Reprint