Singular Extensions

From Chessprogramming wiki
Jump to: navigation, search

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.

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

[11]

Forum Posts

1990 ...

1995 ...

2000 ...

2005 ...

2010 ...

2015 ...

External Links

References

  1. ↑ Uplifting, Oil on Canvas, 24 x 36", Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
  2. ↑ 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
  3. ↑ Feng's (Deep Thought) article in Scientific American (long) by Feng-hsiung Hsu, rgc, October 19, 1990
  4. ↑ Thomas Anantharaman (1991). Confidently Selecting a Search Heuristic. ICCA Journal, Vol. 14, No. 1
  5. ↑ Thomas Anantharaman (1991). Extension Heuristics. ICCA Journal, Vol. 14, No. 2
  6. ↑ Yngvi Björnsson, Tony Marsland (2001). Multi-cut Alpha-Beta Pruning in Game Tree Search. Theoretical Computer Science, Vol. 252, pp. 177-196. pdf
  7. ↑ 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
  8. ↑ Thomas Anantharaman (1991). Extension Heuristics. ICCA Journal, Vol. 14, No. 2
  9. ↑ Günther Schrüfer (1988). Minimax-Suchen : Kosten, Qualität und Algorithmen. Braunschweig : TU, 1988. (German)
  10. ↑ A question to Larry Kaufman, Rybka Forum, December 30/31, 2009
  11. ↑ ICGA Reference Database
  12. ↑ Paper "Singular Extensions" by Anantharaman, Campbell, and Hsu (1988) by Roland Stuckardt, CCC, September 15, 2014
  13. ↑ Feng-hsiung Hsu, Thomas Anantharaman, Murray Campbell, Andreas Nowatzyk (1990). A Grandmaster Chess Machine. Scientific American, Vol. 263, No. 4, Online Reprint

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=Singular_Extensions&oldid=22292"