25,161
edits
Changes
no edit summary
'''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 [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> .
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]].
* [[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 [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
* [[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
* [https://dblp.uni-trier.de/pers/hd/k/Katoh:Yoshiroh Yoshiroh Katoh], [[Toshihide Ibaraki]] ('''1988'''). ''[https://onlinelibrary.wiley.com/doi/pdf/10.1002/scj.4690190710 Game Solving Procedure SSS* is Unsurpassed]''. [https://onlinelibrary.wiley.com/journal/1520684x 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, [https://en.wikipedia.org/wiki/Indian_Institute_of_Management_Calcutta Indian Institute of Management, Calcutta]
