SSS and Dual
Home * Search * SSS* and Dual*
M. C. Escher, Stars, 1948 [1] SSS*,
a best-first state space search developed in 1977 by George C. Stockman for the linguistic analysis of waveforms [2] . In a later paper, Stockman ( 1979) [3] showed how to use this algorithm to determine the minimax value of game trees. SSS* and it counterpart Dual* are non-directional algorithms for searching AND/OR graphs in a best-first manner similar to A*. They expand multiple paths of the search graph and retain global information about the search space, and search fewer nodes than Alpha-Beta in fixed-depth minimax tree search.
The algorithm was examined and improved by various researchers: Igor Roizen and Judea Pearl [4], Toshihide Ibaraki [5] , Tony Marsland et al., Subir Bhattacharya and Amitava Bagchi, Alexander Reinefeld, Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin. In 1988 Burkhard Monien and Oliver Vornberger compared parallel Alpha-Beta with parallel SSS* [6] and in 1990, Hans-Joachim Kraas wrote his Ph.D thesis about how to parallelize SSS* [7] .
However, it turned out the algorithmic overhead was too big to pay off the saved nodes. Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin pointed out, that SSS* can be reformulated as a sequence of alpha-beta null window calls with a Transposition Table.
Pseudo C-Code
In each step, the node with the maximum h-value is removed from OPEN.
Whenever an interior MAX-node gets SOLVED, all direct and indirect descendants must be purged from OPEN
These two steps alone take 90% of the CPU time!
Aske Plaat et al. continue:
Quote by Judea Pearl 1984 [9] :
Dual*
Dual* is the dual counterpart of SSS* by Tony Marsland et al [10] . The dual version of SSS* can be created by inverting SSS*’s operations: use an ascendingly sorted list instead of descending, swap max and min operations, and start at -oo instead of +oo.
RecSSS* and RecDual*
The development of recursive variants was driven by the need for a better understanding of SSS*’s node expansion process and by the demand for more efficient implementations. Two recursive variants were proposed 1990: RecSSS* [11] by Subir Bhattacharya and Amitava Bagchi and SSS-2 [12] by Wim Pijls and Arie de Bruin. In 1993 Alexander Reinefeld improved RecSSS*, making it both faster and more space efficient, using an OPEN- array rather than dynamic list structures [13] .
Pseudo C-Code
based on Alexander Reinefeld’s Pascal pseudo code:
SSS* and Dual* as MT
Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin proved with their Memory Test framework, that both SSS* and Dual* can be reformulated as a sequence of alpha-beta null window calls with a Transposition Table [14] :
Pseudo C-Code
At the 8th Advances in Computer Chess conference 1996, SSS* was finally declared “dead” by Wim Pijls and Arie de Bruin [15] [16] .
See also
Publications
1979
- George Stockman (1979). A Minimax Algorithm Better than Alpha-Beta? Artificial Intelligence, Vol. 12, No. 2.
1980 …
- Igor Roizen, Judea Pearl (1983). A Minimax Algorithm Better than Alpha-Beta? Yes and No. Artificial Intelligence, Vol. 21
- Murray Campbell, Tony Marsland (1983). A Comparison of Minimax Tree Search Algorithms. Artificial Intelligence, Vol. 20, No. 4, pp. 347-367. ISSN 0004-3702, pdf
- Nanda Srimani (1985). A New Algorithm (PS*) for Searching Game Trees. Master’s thesis, University of Alberta
- Daniel B. Leifker, Laveen N. Kanal (1985). A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees. IJCAI'85
- Toshihide Ibaraki (1986). Generalization of Alpha-Beta and SSS* Search Procedures. Artificial Intelligence, Vol. 29
- Tony Marsland, Nanda Srimani (1986). Phased State Search. Fall Joint Computer Conference, pdf
- Tony Marsland, Alexander Reinefeld, Jonathan Schaeffer (1987). Low Overhead Alternatives to SSS*. Artificial Intelligence, Vol. 31, No. 2, pp. 185-199. ISSN 0004-3702.
- Burkhard Monien, Oliver Vornberger (1988). Parallel Alpha-Beta versus Parallel SSS*. Proc. of the IFIP WG 10.3 Working Conference on Distributed Processing, North Holland
- Yoshiroh Katoh, Toshihide Ibaraki (1988). Game Solving Procedure SSS* is Unsurpassed. Systems and Computers in Japan, Vol. 19, No. 7
1990 …
- Subir Bhattacharya, Amitava Bagchi (1990). Unified Recursive Schemes for Search in Game Trees. Technical Report WPS-144, Indian Institute of Management, Calcutta
- Hans-Joachim Kraas (1990).Zur Parallelisierung des SSS*-Algorithmus. Ph.D thesis, TU Braunschweig (German)
- Wim Pijls, Arie de Bruin (1990). Another View on the SSS* Algorithm. International Symposium SIGAL ‘90
- Claude G. Diderich (1992). Evaluation des performance de l’algorithme SSS* avec phases de synchronisation sur une machine parallèle à mémoires distribées. Technical report LITH-99, Swiss Federal Institute of Technology, Computer Science Theory Laboratory, Lausanne, Switzerland (French)
- Wim Pijls, Arie de Bruin (1993). SSS*-like Algorithms in Constrained Memory. ICCA Journal, Vol. 16, No. 1
- Alexander Reinefeld (1994). A Minimax Algorithm Faster than Alpha-Beta. Advances in Computer Chess 7
- Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1994, 2014). SSS* = Alpha-Beta + TT. TR-CS-94-17, University of Alberta, arXiv:1404.1517
- Alexander Reinefeld, Peter Ridinger (1994). Time-Efficient State Space Search. Artificial Intelligence, Vol. 71, No. 2, CiteSeerX
- Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1996). An Algorithm Faster than NegaScout and SSS* in Practice. pdf from CiteSeerX » MTD(f)
- Arie de Bruin, Wim Pijls (1997). SSS†. Advances in Computer Chess 8
2000 …
2010 …
- Bojun Huang (2015). Pruning Game Tree by Rollouts. AAAI » MT-SSS*, MCTS [17]
External Links
- SSS* from Wikipedia
- State space search from Wikipedia
- Aziza Mustafa Zadeh - Stars Dance, Leverkusener Jazztage, November 7, 2006, 3sat, YouTube Video
References
- ↑ M. C. Escher, Stars, 1948, Picture gallery “Back in Holland 1941 - 1954” from The Official M.C. Escher Website
- ↑ George Stockman, Laveen Kanal (1983). Problem Reduction Representation for the Linguistic Analysis of Waveforms. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 5, No 3
- ↑ George Stockman (1979). A Minimax Algorithm Better than Alpha-Beta? Artificial Intelligence, Vol. 12, No. 2
- ↑ Igor Roizen, Judea Pearl (1983). A Minimax Algorithm Better than Alpha-Beta? Yes and No. Artificial Intelligence, Vol. 21
- ↑ Toshihide Ibaraki (1986). Generalization of Alpha-Beta and SSS* Search Procedures. Artificial Intelligence, Vol. 29
- ↑ Burkhard Monien, Oliver Vornberger (1988). Parallel Alpha-Beta versus Parallel SSS*. Proc. of the IFIP WG 10.3 Working Conference on Distributed Processing, North Holland
- ↑ Hans-Joachim Kraas (1990). Zur Parallelisierung des SSS*-Algorithmus. Ph.D thesis, TU Braunschweig (German)
- ↑ Alexander Reinefeld (2005). Die Entwicklung der Spielprogrammierung: Von John von Neumann bis zu den hochparallelen Schachmaschinen. slides as pdf, Themen der Informatik im historischen Kontext Ringvorlesung an der HU Berlin, 02.06.2005 (English paper, German title)
- ↑ Judea Pearl (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishers Co., Reading, MA. ISBN 0-201-05594-5.
- ↑ Tony Marsland, Alexander Reinefeld, Jonathan Schaeffer (1987). Low Overhead Alternatives to SSS*. Artificial Intelligence, Vol. 31, No. 2, pp. 185-199. ISSN 0004-3702.
- ↑ Subir Bhattacharya, Amitava Bagchi (1990). Unified Recursive Schemes for Search in Game Trees. Technical Report WPS-144, Indian Institute of Management, Calcutta
- ↑ Wim Pijls, Arie de Bruin (1990). Another View on the SSS* Algorithm. International Symposium SIGAL ‘90
- ↑ Alexander Reinefeld (1994). A Minimax Algorithm Faster than Alpha-Beta. Advances in Computer Chess 7
- ↑ Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1994, 2014). SSS* = Alpha-Beta + TT. TR-CS-94-17, University of Alberta, arXiv:1404.1517
- ↑ Arie de Bruin, Wim Pijls (1997). SSS†. Advances in Computer Chess 8
- ↑ Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin(1996). Best-First Fixed-Depth Minimax Algorithms. Artificial Intelligence, Vol. 87
- ↑ Re: Announcing lczero by Daniel Shawul, CCC, January 21, 2018 » Leela Chess Zero