25,161
edits
Changes
Created page with "'''Home * Search * SSS* and Dual'''* FILE:EschersStars.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/back-bmp/LW359.jpg|[[Arts#Escher|M. C...."
'''[[Main Page|Home]] * [[Search]] * SSS* and Dual'''*
[[FILE:EschersStars.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/back-bmp/LW359.jpg|[[Arts#Escher|M. C. Escher]], Stars, 1948 <ref>[[Arts#Escher|M. C. Escher]], Stars, 1948, [http://www.mcescher.com/Gallery/gallery-back.htm Picture gallery "Back in Holland 1941 - 1954"] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref> ]]
'''SSS'''*,<br/>
a [[Best-First|best-first]] [https://en.wikipedia.org/wiki/State_space_search state space search] developed in 1977 by [[George Stockman|George C. Stockman]] for the [https://en.wikipedia.org/wiki/Linguistics linguistic] analysis of waveforms <ref>[[George Stockman]], [[Laveen Kanal]] ('''1983'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?isnumber=4767384&arnumber=4767391&count=16&index=6 Problem Reduction Representation for the Linguistic Analysis of Waveforms]''. [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 5, No 3</ref> . In a later paper Stockman ([[Timeline#1979|1979]]) <ref>[[George Stockman]] ('''1979'''). ''A Minimax Algorithm Better than Alpha-Beta?'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 12, No. 2</ref> 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]] <ref>[[Igor Roizen]], [[Judea Pearl]] ('''1983'''). ''A Minimax Algorithm Better than Alpha-Beta? Yes and No''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 21, pp. 199-230. ISSN 0004-3702</ref> , [[Toshihide Ibaraki]] <ref>[[Toshihide Ibaraki]], ('''1986'''). ''Generalizations of alpha-beta and SSS* search procedures.''[https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], 29, 73-117</ref> , [[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* <ref>[[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</ref> and in 1990, [[Hans-Joachim Kraas]] wrote his Ph.D thesis about how to parallelize '''SSS'''* <ref>[[Hans-Joachim Kraas]] ('''1990'''). ''Zur Parallelisierung des SSS*-Algorithmus''. Ph.D thesis, [https://en.wikipedia.org/wiki/Technical_University_of_Braunschweig TU Braunschweig] (German)</ref> .
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|alpha-beta]] [[Null Window|null window]] calls with a [[Transposition Table]].
=SSS*=
[[Aske Plaat]] et al. about '''SSS'''*:
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 <ref>[[Alexander Reinefeld]] ('''2005'''). ''Die Entwicklung der Spielprogrammierung: Von John von Neumann bis zu den hochparallelen Schachmaschinen''. [http://www.informatik.hu-berlin.de/studium/ringvorlesung/ss05/slides/05-06-02.pdf slides as pdf], Themen der Informatik im historischen Kontext Ringvorlesung an der [https://en.wikipedia.org/wiki/Humboldt_University_of_Berlin HU Berlin], 02.06.2005 (English paper, German title)</ref>:
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
* <code>a node identifier</code> '''n'''
* <code>a status</code> '''s'''
** <code>LIVE: n is still unexpanded and h is an upper bound on the true value</code>
** <code>SOLVED: h is the true value</code>
* <code>a merit</code> '''h'''
'''SSS*'s''' two search phases:
# <code>Node Expansion Phase: Top down expansion of a MIN strategy.</code>
# <code>Solution Phase: Bottom up search for the best MAX strategy.</code>
==Pseudo C-Code==
<pre>
int SSS* (node n; int bound)
{
push (n, LIVE, bound);
while ( true ) {
pop (node);
switch ( node.status ) {
case LIVE:
if (node == LEAF)
insert (node, SOLVED, min(eval(node),h));
if (node == MIN_NODE)
push (node.1, LIVE, h);
if (node == MAX_NODE)
for (j=w; j; j--)
push (node.j, LIVE, h);
break;
case SOLVED:
if (node == ROOT_NODE)
return (h);
if (node == MIN_NODE) {
purge (parent(node));
push (parent(node), SOLVED, h);
}
if (node == MAX_NODE) {
if (node has an unexamined brother)
push (brother(node), LIVE, h);
else
push (parent(node), SOLVED, h);
}
break;
}
}
}
</pre>
SSS* is too complex and too slow!
* <code>In each step, the node with the maximum h-value is removed from OPEN.</code>
* <code>Whenever an interior MAX-node gets SOLVED, all direct and indirect descendants must be purged from OPEN</code>
</code>These two steps alone take 90% of the CPU time!</code>
[[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 <ref>[[Judea Pearl]] ('''1984'''). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishers Co., Reading, MA. ISBN 0-201-05594-5.</ref> :
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 [[Alpha-Beta|alphabeta]] will continue to monopolize the practice of computerized game playing.
=Dual*=
'''Dual'''* is the dual counterpart of '''SSS'''* by [[Tony Marsland]] ''et al'' <ref>[[Tony Marsland]], [[Alexander Reinefeld]], [[Jonathan Schaeffer]] ('''1987'''). Low Overhead Alternatives to SSS*. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 31, No. 2, pp. 185-199. ISSN 0004-3702.</ref> . 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.
<span id="RecSSS"></span>
=RecSSS* and RecDual*=
The development of [[Recursion|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'''* <ref>[[Subir Bhattacharya]], [[Amitava Bagchi]] ('''1990'''). ''Unified Recursive Schemes for Search in Game Trees.'' Technical Report WPS-144, [https://en.wikipedia.org/wiki/Indian_Institute_of_Management_Calcutta Indian Institute of Management, Calcutta]</ref> by [[Subir Bhattacharya]] and [[Amitava Bagchi]] and '''SSS-2''' <ref>[[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.</ref> 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|array]] rather than dynamic list structures <ref>[[Alexander Reinefeld]] ('''1994'''). ''A Minimax Algorithm Faster than Alpha-Beta''. [[Advances in Computer Chess 7]]</ref> .
==Pseudo C-Code==
based on [[Alexander Reinefeld|Alexander Reinefeld's]] [[Pascal]] pseudo code:
<pre>
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);
}
</pre>
<pre>
int main()
{
insert (root, UNEXPANDED, oo);
do
h = RecSSS*(root);
while ( s(n) != SOLVED );
}
</pre>
<span id="SSStarandDualStarAsMT"></span>
=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|alpha-beta]] [[Null Window|null window]] calls with a [[Transposition Table]] <ref>[[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1995'''). ''SSS* = Alpha-Beta + TT'' Technical Report EUR-CS-95-02, [http://publishing.eur.nl/ir/repub/asset/1441/eur-few-cs-95-02.pdf pdf]</ref> :
==Pseudo C-Code==
<pre>
int MT-SSS*( n )
{
g := +oo;
do {
G := g;
g := Alpha-Beta(n, G-1, G );
} while (g != G);
return g;
}
</pre>
<pre>
int MT-DUAL*(n)
{
g := -oo;
do {
G := g;
g := Alpha-Beta(n, G, G+1 );
} while (g != G);
return g;
}
</pre>
At the [[Advances in Computer Chess 8|8th Advances in Computer Chess]] conference 1996, '''SSS'''* was finally declared "dead" by [[Wim Pijls]] and [[Arie de Bruin]] <ref>[[Arie de Bruin]], [[Wim Pijls]] ('''1997'''). ''SSS†.'' [[Advances in Computer Chess 8]]</ref> <ref>[[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]]('''1996'''). ''Best-First Fixed-Depth Minimax Algorithms.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 87, Nos. 1-2, [http://www.ldc.usb.ve/%7Ebonet/courses/ci5437/papers/mtd.pdf pdf]</ref> .
=See also=
* [[MTD(f)]]
* [[NegaC*]]
* [[NegaScout]]
* [[Scout]]
=Publications=
==1979==
* [[George Stockman]] ('''1979'''). ''A Minimax Algorithm Better than Alpha-Beta?'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 12, No. 2.
==1980 ...==
* [[Igor Roizen]], [[Judea Pearl]] ('''1983'''). ''A Minimax Algorithm Better than Alpha-Beta? Yes and No''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 21
* [[Murray Campbell]], [[Tony Marsland]] ('''1983'''). ''A Comparison of Minimax Tree Search Algorithms''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 20, No. 4, pp. 347-367. ISSN 0004-3702, [http://webdocs.cs.ualberta.ca/~tony/OldPapers/TR82-3.pdf pdf]
* [[Nanda Srimani]] ('''1985'''). ''A New Algorithm (PS*) for Searching Game Trees''. Master's thesis, [[University of Alberta]]
* [http://www.informatik.uni-trier.de/~ley/pers/hd/l/Leifker:Daniel_B=.html Daniel B. Leifker], [[Laveen Kanal|Laveen N. Kanal]] ('''1985'''). ''[http://dl.acm.org/citation.cfm?id=1623687 A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees]''. [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai85.html#LeifkerK85 IJCAI'85]
* [[Toshihide Ibaraki]] ('''1986'''). ''Generalizations of alpha-beta and SSS* search procedures.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], 29, 73-117
* [[Tony Marsland]], [[Nanda Srimani]] ('''1986'''). ''Phased State Search''. [http://www.informatik.uni-trier.de/~ley/db/conf/fjcc/fjcc86.html#MarslandS86 Fall Joint Computer Conference], [http://webdocs.cs.ualberta.ca/~tony/OldPapers/fjcc.1986.pdf pdf]
* [[Tony Marsland]], [[Alexander Reinefeld]], [[Jonathan Schaeffer]] ('''1987'''). Low Overhead Alternatives to SSS*. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 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
==1990 ...==
* [[Subir Bhattacharya]], [[Amitava Bagchi]] ('''1990'''). ''Unified Recursive Schemes for Search in Game Trees.'' Technical Report WPS-144, [https://en.wikipedia.org/wiki/Indian_Institute_of_Management_Calcutta Indian Institute of Management, Calcutta]
* [[Hans-Joachim Kraas]] ('''1990''').''Zur Parallelisierung des SSS*-Algorithmus''. Ph.D thesis, [https://en.wikipedia.org/wiki/Technical_University_of_Braunschweig TU Braunschweig] (German)
* [[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, [https://en.wikipedia.org/wiki/%C3%89cole_Polytechnique_F%C3%A9d%C3%A9rale_de_Lausanne Swiss Federal Institute of Technology], Computer Science Theory Laboratory, Lausanne, Switzerland (French)
* [[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'''). ''[http://arxiv.org/abs/1404.1517?context=cs.AI SSS* = a-b TT]''. TR-CS-94-17, [[University of Alberta]]
* [[Alexander Reinefeld]], [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/r/Ridinger:Peter.html Peter Ridinger] ('''1994'''). ''[http://www.sciencedirect.com/science/article/pii/0004370294900493 Time-Efficient State Space Search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 71, No. 2, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.1934 CiteSeerX]
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1996'''). ''An Algorithm Faster than NegaScout and SSS* in Practice'', [http://citeseerx.ist.psu.edu/showciting;jsessionid=04E25D5F074D8B5BABB68D2AC5BA5D39?cid=3161130 pdf] from [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.8641 CiteSeerX], covers [[MTD(f)]]
* [[Arie de Bruin]], [[Wim Pijls]] ('''1997'''). ''SSS†.'' [[Advances in Computer Chess 8]]
* [[Aske Plaat]], [[Arie de Bruin]], [[Jonathan Schaeffer]], [[Wim Pijls]] ('''1999'''). ''A Minimax Algorithm better than SSS*.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 87
==2010 ...==
* [[Bojun Huang]] ('''2015'''). ''[https://www.semanticscholar.org/paper/Pruning-Game-Tree-by-Rollouts-Huang/a38b358745067f71a9c780db117ae2471e693d63 Pruning Game Tree by Rollouts]''. [[AAAI]] » [[SSS* and Dual*#SSStarandDualStarAsMT|MT-SSS*]], [[Monte-Carlo Tree Search|MCTS]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66280&start=67 Re: Announcing lczero] by [[Daniel Shawul]], [[CCC]], January 21, 2018 » [[LCZero]]</ref>
=External Links=
* [https://en.wikipedia.org/wiki/SSS* SSS* From Wikipedia]
* [https://en.wikipedia.org/wiki/State_space_search State space search From Wikipedia]
* [http://www.murrayc.com/learning/AI/statespace.shtml State Space Search] from [http://www.murrayc.com/index.shtml Murray's Web Pages]
* [[Videos#AzizaMustafaZadeh|Aziza Mustafa Zadeh]] - Stars Dance, [https://en.wikipedia.org/wiki/Leverkusener_Jazztage Leverkusener Jazztage], November 7, 2006, [https://en.wikipedia.org/wiki/3sat 3sat], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=sSLKj9ghovk|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one level]]'''
[[FILE:EschersStars.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/back-bmp/LW359.jpg|[[Arts#Escher|M. C. Escher]], Stars, 1948 <ref>[[Arts#Escher|M. C. Escher]], Stars, 1948, [http://www.mcescher.com/Gallery/gallery-back.htm Picture gallery "Back in Holland 1941 - 1954"] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref> ]]
'''SSS'''*,<br/>
a [[Best-First|best-first]] [https://en.wikipedia.org/wiki/State_space_search state space search] developed in 1977 by [[George Stockman|George C. Stockman]] for the [https://en.wikipedia.org/wiki/Linguistics linguistic] analysis of waveforms <ref>[[George Stockman]], [[Laveen Kanal]] ('''1983'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?isnumber=4767384&arnumber=4767391&count=16&index=6 Problem Reduction Representation for the Linguistic Analysis of Waveforms]''. [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 5, No 3</ref> . In a later paper Stockman ([[Timeline#1979|1979]]) <ref>[[George Stockman]] ('''1979'''). ''A Minimax Algorithm Better than Alpha-Beta?'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 12, No. 2</ref> 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]] <ref>[[Igor Roizen]], [[Judea Pearl]] ('''1983'''). ''A Minimax Algorithm Better than Alpha-Beta? Yes and No''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 21, pp. 199-230. ISSN 0004-3702</ref> , [[Toshihide Ibaraki]] <ref>[[Toshihide Ibaraki]], ('''1986'''). ''Generalizations of alpha-beta and SSS* search procedures.''[https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], 29, 73-117</ref> , [[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* <ref>[[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</ref> and in 1990, [[Hans-Joachim Kraas]] wrote his Ph.D thesis about how to parallelize '''SSS'''* <ref>[[Hans-Joachim Kraas]] ('''1990'''). ''Zur Parallelisierung des SSS*-Algorithmus''. Ph.D thesis, [https://en.wikipedia.org/wiki/Technical_University_of_Braunschweig TU Braunschweig] (German)</ref> .
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|alpha-beta]] [[Null Window|null window]] calls with a [[Transposition Table]].
=SSS*=
[[Aske Plaat]] et al. about '''SSS'''*:
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 <ref>[[Alexander Reinefeld]] ('''2005'''). ''Die Entwicklung der Spielprogrammierung: Von John von Neumann bis zu den hochparallelen Schachmaschinen''. [http://www.informatik.hu-berlin.de/studium/ringvorlesung/ss05/slides/05-06-02.pdf slides as pdf], Themen der Informatik im historischen Kontext Ringvorlesung an der [https://en.wikipedia.org/wiki/Humboldt_University_of_Berlin HU Berlin], 02.06.2005 (English paper, German title)</ref>:
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
* <code>a node identifier</code> '''n'''
* <code>a status</code> '''s'''
** <code>LIVE: n is still unexpanded and h is an upper bound on the true value</code>
** <code>SOLVED: h is the true value</code>
* <code>a merit</code> '''h'''
'''SSS*'s''' two search phases:
# <code>Node Expansion Phase: Top down expansion of a MIN strategy.</code>
# <code>Solution Phase: Bottom up search for the best MAX strategy.</code>
==Pseudo C-Code==
<pre>
int SSS* (node n; int bound)
{
push (n, LIVE, bound);
while ( true ) {
pop (node);
switch ( node.status ) {
case LIVE:
if (node == LEAF)
insert (node, SOLVED, min(eval(node),h));
if (node == MIN_NODE)
push (node.1, LIVE, h);
if (node == MAX_NODE)
for (j=w; j; j--)
push (node.j, LIVE, h);
break;
case SOLVED:
if (node == ROOT_NODE)
return (h);
if (node == MIN_NODE) {
purge (parent(node));
push (parent(node), SOLVED, h);
}
if (node == MAX_NODE) {
if (node has an unexamined brother)
push (brother(node), LIVE, h);
else
push (parent(node), SOLVED, h);
}
break;
}
}
}
</pre>
SSS* is too complex and too slow!
* <code>In each step, the node with the maximum h-value is removed from OPEN.</code>
* <code>Whenever an interior MAX-node gets SOLVED, all direct and indirect descendants must be purged from OPEN</code>
</code>These two steps alone take 90% of the CPU time!</code>
[[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 <ref>[[Judea Pearl]] ('''1984'''). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishers Co., Reading, MA. ISBN 0-201-05594-5.</ref> :
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 [[Alpha-Beta|alphabeta]] will continue to monopolize the practice of computerized game playing.
=Dual*=
'''Dual'''* is the dual counterpart of '''SSS'''* by [[Tony Marsland]] ''et al'' <ref>[[Tony Marsland]], [[Alexander Reinefeld]], [[Jonathan Schaeffer]] ('''1987'''). Low Overhead Alternatives to SSS*. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 31, No. 2, pp. 185-199. ISSN 0004-3702.</ref> . 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.
<span id="RecSSS"></span>
=RecSSS* and RecDual*=
The development of [[Recursion|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'''* <ref>[[Subir Bhattacharya]], [[Amitava Bagchi]] ('''1990'''). ''Unified Recursive Schemes for Search in Game Trees.'' Technical Report WPS-144, [https://en.wikipedia.org/wiki/Indian_Institute_of_Management_Calcutta Indian Institute of Management, Calcutta]</ref> by [[Subir Bhattacharya]] and [[Amitava Bagchi]] and '''SSS-2''' <ref>[[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.</ref> 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|array]] rather than dynamic list structures <ref>[[Alexander Reinefeld]] ('''1994'''). ''A Minimax Algorithm Faster than Alpha-Beta''. [[Advances in Computer Chess 7]]</ref> .
==Pseudo C-Code==
based on [[Alexander Reinefeld|Alexander Reinefeld's]] [[Pascal]] pseudo code:
<pre>
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);
}
</pre>
<pre>
int main()
{
insert (root, UNEXPANDED, oo);
do
h = RecSSS*(root);
while ( s(n) != SOLVED );
}
</pre>
<span id="SSStarandDualStarAsMT"></span>
=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|alpha-beta]] [[Null Window|null window]] calls with a [[Transposition Table]] <ref>[[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1995'''). ''SSS* = Alpha-Beta + TT'' Technical Report EUR-CS-95-02, [http://publishing.eur.nl/ir/repub/asset/1441/eur-few-cs-95-02.pdf pdf]</ref> :
==Pseudo C-Code==
<pre>
int MT-SSS*( n )
{
g := +oo;
do {
G := g;
g := Alpha-Beta(n, G-1, G );
} while (g != G);
return g;
}
</pre>
<pre>
int MT-DUAL*(n)
{
g := -oo;
do {
G := g;
g := Alpha-Beta(n, G, G+1 );
} while (g != G);
return g;
}
</pre>
At the [[Advances in Computer Chess 8|8th Advances in Computer Chess]] conference 1996, '''SSS'''* was finally declared "dead" by [[Wim Pijls]] and [[Arie de Bruin]] <ref>[[Arie de Bruin]], [[Wim Pijls]] ('''1997'''). ''SSS†.'' [[Advances in Computer Chess 8]]</ref> <ref>[[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]]('''1996'''). ''Best-First Fixed-Depth Minimax Algorithms.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 87, Nos. 1-2, [http://www.ldc.usb.ve/%7Ebonet/courses/ci5437/papers/mtd.pdf pdf]</ref> .
=See also=
* [[MTD(f)]]
* [[NegaC*]]
* [[NegaScout]]
* [[Scout]]
=Publications=
==1979==
* [[George Stockman]] ('''1979'''). ''A Minimax Algorithm Better than Alpha-Beta?'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 12, No. 2.
==1980 ...==
* [[Igor Roizen]], [[Judea Pearl]] ('''1983'''). ''A Minimax Algorithm Better than Alpha-Beta? Yes and No''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 21
* [[Murray Campbell]], [[Tony Marsland]] ('''1983'''). ''A Comparison of Minimax Tree Search Algorithms''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 20, No. 4, pp. 347-367. ISSN 0004-3702, [http://webdocs.cs.ualberta.ca/~tony/OldPapers/TR82-3.pdf pdf]
* [[Nanda Srimani]] ('''1985'''). ''A New Algorithm (PS*) for Searching Game Trees''. Master's thesis, [[University of Alberta]]
* [http://www.informatik.uni-trier.de/~ley/pers/hd/l/Leifker:Daniel_B=.html Daniel B. Leifker], [[Laveen Kanal|Laveen N. Kanal]] ('''1985'''). ''[http://dl.acm.org/citation.cfm?id=1623687 A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees]''. [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai85.html#LeifkerK85 IJCAI'85]
* [[Toshihide Ibaraki]] ('''1986'''). ''Generalizations of alpha-beta and SSS* search procedures.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], 29, 73-117
* [[Tony Marsland]], [[Nanda Srimani]] ('''1986'''). ''Phased State Search''. [http://www.informatik.uni-trier.de/~ley/db/conf/fjcc/fjcc86.html#MarslandS86 Fall Joint Computer Conference], [http://webdocs.cs.ualberta.ca/~tony/OldPapers/fjcc.1986.pdf pdf]
* [[Tony Marsland]], [[Alexander Reinefeld]], [[Jonathan Schaeffer]] ('''1987'''). Low Overhead Alternatives to SSS*. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 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
==1990 ...==
* [[Subir Bhattacharya]], [[Amitava Bagchi]] ('''1990'''). ''Unified Recursive Schemes for Search in Game Trees.'' Technical Report WPS-144, [https://en.wikipedia.org/wiki/Indian_Institute_of_Management_Calcutta Indian Institute of Management, Calcutta]
* [[Hans-Joachim Kraas]] ('''1990''').''Zur Parallelisierung des SSS*-Algorithmus''. Ph.D thesis, [https://en.wikipedia.org/wiki/Technical_University_of_Braunschweig TU Braunschweig] (German)
* [[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, [https://en.wikipedia.org/wiki/%C3%89cole_Polytechnique_F%C3%A9d%C3%A9rale_de_Lausanne Swiss Federal Institute of Technology], Computer Science Theory Laboratory, Lausanne, Switzerland (French)
* [[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'''). ''[http://arxiv.org/abs/1404.1517?context=cs.AI SSS* = a-b TT]''. TR-CS-94-17, [[University of Alberta]]
* [[Alexander Reinefeld]], [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/r/Ridinger:Peter.html Peter Ridinger] ('''1994'''). ''[http://www.sciencedirect.com/science/article/pii/0004370294900493 Time-Efficient State Space Search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 71, No. 2, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.1934 CiteSeerX]
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1996'''). ''An Algorithm Faster than NegaScout and SSS* in Practice'', [http://citeseerx.ist.psu.edu/showciting;jsessionid=04E25D5F074D8B5BABB68D2AC5BA5D39?cid=3161130 pdf] from [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.8641 CiteSeerX], covers [[MTD(f)]]
* [[Arie de Bruin]], [[Wim Pijls]] ('''1997'''). ''SSS†.'' [[Advances in Computer Chess 8]]
* [[Aske Plaat]], [[Arie de Bruin]], [[Jonathan Schaeffer]], [[Wim Pijls]] ('''1999'''). ''A Minimax Algorithm better than SSS*.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 87
==2010 ...==
* [[Bojun Huang]] ('''2015'''). ''[https://www.semanticscholar.org/paper/Pruning-Game-Tree-by-Rollouts-Huang/a38b358745067f71a9c780db117ae2471e693d63 Pruning Game Tree by Rollouts]''. [[AAAI]] » [[SSS* and Dual*#SSStarandDualStarAsMT|MT-SSS*]], [[Monte-Carlo Tree Search|MCTS]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66280&start=67 Re: Announcing lczero] by [[Daniel Shawul]], [[CCC]], January 21, 2018 » [[LCZero]]</ref>
=External Links=
* [https://en.wikipedia.org/wiki/SSS* SSS* From Wikipedia]
* [https://en.wikipedia.org/wiki/State_space_search State space search From Wikipedia]
* [http://www.murrayc.com/learning/AI/statespace.shtml State Space Search] from [http://www.murrayc.com/index.shtml Murray's Web Pages]
* [[Videos#AzizaMustafaZadeh|Aziza Mustafa Zadeh]] - Stars Dance, [https://en.wikipedia.org/wiki/Leverkusener_Jazztage Leverkusener Jazztage], November 7, 2006, [https://en.wikipedia.org/wiki/3sat 3sat], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=sSLKj9ghovk|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one level]]'''
