SSS* is a best-firststate space search developed in 1977 by George C. Stockman for the linguistic analysis of waveforms ^{[1]} . In a later paper Stockman (1979) ^{[2]} 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.

In 1979 Stockman introduced SSS*, which looked like a radically different approach from Alpha-Beta for searching fixed-depth minimax trees. It builds a tree in a so-called best-first fashion by visiting the most promising nodes first. Alpha-Beta, in contrast, uses a depth-first, left-to-right traversal of the tree. Intuitively, it would seem that a best-first strategy should prevail over a rigidly ordered depth-first one. Stockman proved that SSS* dominated Alpha-Beta; it would never evaluate more leaf nodes than Alpha-Beta. Numerous simulations have shown that on average SSS* evaluates considerably fewer leaf nodes. Why, then, has the algorithm been shunned by practitioners?

Alexander Reinefeld has a good answer, and explanation of SSS* in his Lecture ^{[8]}:

SSS* maintains an OPEN list with descriptors of the active nodes. Descriptors are sorted in decreasing order of their merit (h values). A descriptor (n, s, h) consists of

a node identifier n

a status s {LIVE, SOLVED}

LIVE: n is still unexpanded and h is an upper bound on the true value

SOLVED: h is the true value

a merit h

SSS*'s two search phases:

Node Expansion Phase: Top down expansion of a MIN strategy.

Solution Phase: Bottom up search for the best MAX strategy.

SSS*, as formulated by Stockman, has several problems. First, it takes considerable effort to understand how the algorithm works, and still more to understand its relation to Alpha-Beta. Second, SSS* maintains a data structure known as the OPEN list, similar to that found in single-agent search algorithms like A*. The size of this list grows exponentially with the depth of the search tree. This has led many authors to conclude that SSS* is effectively disqualified from being useful for real applications like game-playing programs. Third, the OPEN list must be kept in sorted order. Insert and (in particular) delete/purge operations on the OPEN list can dominate the execution time of any program using SSS*. Despite the promise of expanding fewer nodes, the disadvantages of SSS* have proven a significant deterrent in practice.

The meager improvement in the pruning power of SSS* is more than offset by the increased storage space and bookkeeping (e.g. sorting OPEN) that it requires. One can safely speculate therefore that alphabeta will continue to monopolize the practice of computerized game playing.

Dual*

Dual* is the dual counterpart of SSS* by Tony Marslandet 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]} .

int RecSS*(nodeType n){if(n is leaf){
s(n)= SOLVED;return min (evaluate(n), h(n));/* evaluate leaf */}if( s(n)== UNEXPANDED ){/* first descend? */
s(n)= LIVE;/* expand n */for(i =1 to width)if( n.i is leaf )
insert (n.i, UNEXPANDED, h(n));/* insert sons (= MIN leaves) of n */else
insert (n.i.1, UNEXPANDED, h(n));/* insert left grandsons of n */}
g = highest h-valued grandson (or son) of n in OPEN;while( h(g)== h(n)&& status(g)!= SOLVED ){
h(g)= RecSS*(g);/* get new upper bound */if( s(g)== SOLVED && g has a right brother )
replace g by (brother(g), UNDEXPANDED, h(g));/* next brother of g */
g = highest h-valued grandson (or son) of n in OPEN;/*resolve ties in lexicographical order*/}if( s(g)== SOLVED )
s(n)= SOLVED;return h(g);}

int main(){
insert (root, UNEXPANDED, oo);do
h = RecSSS*(root);while( s(n)!= SOLVED );}

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

Wim Pijls, Arie de Bruin (1990). Another View on the SSS* Algorithm. International Symposium SIGAL '90 (eds. T. Asano, T. Ibaraki, H. Imai, and T. Nishizeki), pp. 211-220. Tokyo, Japan. Lecture Notes in Computer Science, Vol. 450, Springer-Verlag, New York, NY. ISSN 0302-9743.

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)

^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

^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.

^Wim Pijls, Arie de Bruin (1990). Another View on the SSS* Algorithm. International Symposium SIGAL '90 (eds. T. Asano, T. Ibaraki, H. Imai, and T. Nishizeki), pp. 211-220. Tokyo, Japan. Lecture Notes in Computer Science, Vol. 450, Springer-Verlag, New York, NY. ISSN 0302-9743.

Home * Search * SSS* and Dual*SSS* is a best-first state space search developed in 1977 by George C. Stockman for the linguistic analysis of waveforms^{[1]}. In a later paper Stockman (1979)^{[2]}showed how to use this algorithm to determine the minimax value of game trees.SSS* and it counterpartDual* 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

^{[3]}, Toshihide Ibaraki^{[4]}, Tony Marslandet 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*^{[5]}and in 1990, Hans-Joachim Kraas wrote his Ph.D thesis about how to parallelizeSSS*^{[6]}.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.^{[7]}## Table of Contents

## SSS*

Aske Plaat et al. aboutSSS*:In 1979 Stockman introduced SSS*, which looked like a radically different approach from Alpha-Beta for searching fixed-depth minimax trees. It builds a tree in a so-called best-first fashion by visiting the most promising nodes first. Alpha-Beta, in contrast, uses a depth-first, left-to-right traversal of the tree. Intuitively, it would seem that a best-first strategy should prevail over a rigidly ordered depth-first one. Stockman proved that SSS* dominated Alpha-Beta; it would never evaluate more leaf nodes than Alpha-Beta. Numerous simulations have shown that on average SSS* evaluates considerably fewer leaf nodes. Why, then, has the algorithm been shunned by practitioners?Alexander Reinefeld has a good answer, and explanation of

SSS* in his Lecture^{[8]}:SSS* maintains an OPEN list with descriptors of the active nodes. Descriptors are sorted in decreasing order of their merit (h values). Adescriptor (n, s, h)consists ofns{LIVE, SOLVED}hSSS*'stwo search phases:## Pseudo C-Code

SSS* is too complex and too slow!These two steps alone take 90% of the CPU time!Aske Plaat et al. continue:

SSS*, as formulated by Stockman, has several problems. First, it takes considerable effort to understand how the algorithm works, and still more to understand its relation to Alpha-Beta. Second, SSS* maintains a data structure known as the OPEN list, similar to that found in single-agent search algorithms like A*. The size of this list grows exponentially with the depth of the search tree. This has led many authors to conclude that SSS* is effectively disqualified from being useful for real applications like game-playing programs. Third, the OPEN list must be kept in sorted order. Insert and (in particular) delete/purge operations on the OPEN list can dominate the execution time of any program using SSS*. Despite the promise of expanding fewer nodes, the disadvantages of SSS* have proven a significant deterrent in practice.Quote by Judea Pearl 1984

^{[9]}:The meager improvement in the pruning power of SSS* is more than offset by the increased storage space and bookkeeping (e.g. sorting OPEN) that it requires. One can safely speculate therefore that alphabeta will continue to monopolize the practice of computerized game playing.## Dual*

Dual* is the dual counterpart ofSSS* by Tony Marslandet al^{[10]}. The dual version ofSSS* can be created by invertingSSS*’soperations: 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 ofSSS*'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 andSSS-2^{[12]}by Wim Pijls and Arie de Bruin. In 1993 Alexander Reinefeld improvedRecSSS*, 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 bothSSS* andDual* 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

1979).A Minimax Algorithm Better than Alpha-Beta?Artificial Intelligence, Vol. 12, No. 2.## 1980 ...

1983).A Minimax Algorithm Better than Alpha-Beta? Yes and No. Artificial Intelligence, Vol. 211983).A Comparison of Minimax Tree Search Algorithms. Artificial Intelligence, Vol. 20, No. 4, pp. 347-367. ISSN 0004-3702, pdf1985).A New Algorithm (PS*) for Searching Game Trees. Master's thesis, University of Alberta1985).A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees. IJCAI'851986).Generalizations of alpha-beta and SSS* search procedures.Artificial Intelligence, 29, 73-1171986).Phased State Search. Fall Joint Computer Conference, pdf1987). Low Overhead Alternatives to SSS*. Artificial Intelligence, Vol. 31, No. 2, pp. 185-199. ISSN 0004-3702.1988).Parallel Alpha-Beta versus Parallel SSS*. Proc. of the IFIP WG 10.3 Working Conference on Distributed Processing, North Holland## 1990 ...

1990).Unified Recursive Schemes for Search in Game Trees.Technical Report WPS-144, Indian Institute of Management, Calcutta1990).Zur Parallelisierung des SSS*-Algorithmus. Ph.D thesis, TU Braunschweig (German)1990).Another View on the SSS* Algorithm.International Symposium SIGAL '90 (eds. T. Asano, T. Ibaraki, H. Imai, and T. Nishizeki), pp. 211-220. Tokyo, Japan. Lecture Notes in Computer Science, Vol. 450, Springer-Verlag, New York, NY. ISSN 0302-9743.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)1994).A Minimax Algorithm Faster than Alpha-Beta. Advances in Computer Chess 71994).SSS* = a-b TT. TR-CS-94-17, University of Alberta1994).Time-Efficient State Space Search. Artificial Intelligence, Vol. 71, No. 2, CiteSeerX1996).An Algorithm Faster than NegaScout and SSS* in Practice, pdf from CiteSeerX, covers MTD(f)1997).SSS†.Advances in Computer Chess 81999).A Minimax Algorithm better than SSS*.Artificial Intelligence, Vol. 87## External Links

## References

1983).Problem Reduction Representation for the Linguistic Analysis of Waveforms. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 5, No 31979).A Minimax Algorithm Better than Alpha-Beta?Artificial Intelligence, Vol. 12, No. 21983).A Minimax Algorithm Better than Alpha-Beta? Yes and No. Artificial Intelligence, Vol. 21, pp. 199-230. ISSN 0004-37021986).Generalizations of alpha-beta and SSS* search procedures.Artificial Intelligence, 29, 73-1171988).Parallel Alpha-Beta versus Parallel SSS*. Proc. of the IFIP WG 10.3 Working Conference on Distributed Processing, North Holland1990).Zur Parallelisierung des SSS*-Algorithmus. Ph.D thesis, TU Braunschweig (German)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)1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishers Co., Reading, MA. ISBN 0-201-05594-5.1987). Low Overhead Alternatives to SSS*. Artificial Intelligence, Vol. 31, No. 2, pp. 185-199. ISSN 0004-3702.1990).Unified Recursive Schemes for Search in Game Trees.Technical Report WPS-144, Indian Institute of Management, Calcutta1990).Another View on the SSS* Algorithm.International Symposium SIGAL '90 (eds. T. Asano, T. Ibaraki, H. Imai, and T. Nishizeki), pp. 211-220. Tokyo, Japan. Lecture Notes in Computer Science, Vol. 450, Springer-Verlag, New York, NY. ISSN 0302-9743.1994).A Minimax Algorithm Faster than Alpha-Beta. Advances in Computer Chess 71995).SSS* = Alpha-Beta + TTTechnical Report EUR-CS-95-02, pdf1997).SSS†.Advances in Computer Chess 81996).Best-First Fixed-Depth Minimax Algorithms.Artificial Intelligence, Vol. 87, Nos. 1-2, pdf## What links here?

Up one level