A faster alternative to \(SSS^*\) with extension to variable memory (Q689627)

We describe a new recursive algorithm called RecSSS\(^*\). RecSSS\(^*\) examines the same sequence of terminals as SSS\(^*\) and has a runtime performance comparable to that of Alpha-Beta. Specifically, our algorithm achieves the following goals: (a) A marked increase in the speed of execution of SSS\(^*\). RecSSS\(^*\) has very little overhead since the need for purging nodes from OPEN has been eliminated and the search effort to find the most promising solution tree has been minimized. (b) Some degree of control over the use of memory. A modified version of RecSSS\(^*\), called MRecSSS\(^*\), runs even when sufficient storage to store all of OPEN is not available. A similar algorithm has been developed recently for best-first search [\textit{A. K. Sen} and \textit{A. Bagchi}, IJCAI 89, Proc. Int. Conf., Detroit, MI/USA, 297-302 (1989; Zbl 0707.68077)].