Changes

[[FILE:EschersStars.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/back-bmp/LW359.jpg|[[Arts#:Category:M. C. Escher|M. C. Escher]], Stars, 1948 <ref>[[Arts#:Category:M. C. 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> ]]

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 [https://www.sciencedirect.com/science/article/abs/pii/0004370286900925 Generalization of alphaAlpha-beta Beta and SSS* search procedures.Search Procedures]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 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> .

</code>These two steps alone take 90% of the CPU time!</code>

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

[[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]] ('''19951994, 2014'''). ''SSS* = Alpha-Beta + TT'' Technical Report EUR. TR-CS-9594-0217, [[University of Alberta]], [httphttps://publishing.eurarxiv.nlorg/irabs/repub/asset/1441/eur-few-cs-95-021404.1517 arXiv:1404.pdf pdf1517]</ref> :

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

* [[Toshihide Ibaraki]] ('''1986'''). ''Generalizations [https://www.sciencedirect.com/science/article/abs/pii/0004370286900925 Generalization of alphaAlpha-beta Beta and SSS* search procedures.Search Procedures]'' . [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 29, 73-117

* [[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.

* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1994, 2014'''). ''[http://arxiv.org/abs/1404.1517?context=cs.AI SSS* = aAlpha-b Beta + TT]''. TR-CS-94-17, [[University of Alberta]], [https://arxiv.org/abs/1404.1517 arXiv:1404.1517]

* [[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;jsessionidviewdoc/download?doi=04E25D5F074D8B5BABB68D2AC5BA5D39?cid10.1.1.77.9111&rep=rep1&type=3161130 pdf pdf] from [httphttps://citeseerxen.ist.psuwikipedia.eduorg/viewdocwiki/summary?doi=10.1.1.50.8641 CiteSeerX CiteSeerX], covers » [[MTD(f)]]

==2000 ...==* [[Aske Plaat]], [[Arie de Bruin]], [[Jonathan Schaeffer]], [[Wim Pijls]] ('''19992003'''). ''A Minimax Algorithm better than SSS*[https://repub.eur.nl/pub/459 Trends in game tree search]'' . [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial IntelligenceErasmus_University_Rotterdam Erasmus University, Rotterdam], Vol. 87

* [[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 » [[LCZeroLeela Chess Zero]]</ref>

* [https://en.wikipedia.org/wiki/SSS* SSS* From from Wikipedia]* [https://en.wikipedia.org/wiki/State_space_search State space search From from Wikipedia]* [http[://www.murrayc.com/learning/AI/statespace.shtml State Space Search] from [httpCategory://www.murrayc.com/index.shtml Murray's Web Pages]* [[Videos#AzizaMustafaZadehAziza Mustafa Zadeh|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