Singular Extensions
Home * Search * Selectivity * Extensions * Singular Extensions
Samuel Bak - Uplifting [1] 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.
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] :
Modern singular extensions
In recent times we have a more relaxed form of restricted SE, by also allowing singular search on TT entries with an exact score.
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
- Singular extension by Stefan Geschwentner, FishCooking, November 01, 2013 » Stockfish
- Singular extension: exclusion key by Stefan Geschwentner, FishCooking, November 24, 2013
- 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 » TTSE
External Links
- Singular extension from Programming Topics by Bruce Moreland
- Chess Programming Part V: Advanced Search from Chess Programming by François-Dominic Laramée, gamedev.net
- Travis Reuter Quintet - Singular Arrays, Rotational Templates (2012), YouTube Video
Travis Reuter, Jeremy Viner, Bobby Avey, Chris Tordini, Jason Nazary
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
- ↑ 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