In 1979 Stockman introduced the SSS* minimax search algorithm that dominates alpha-beta in the number of leaf nodes expanded. Further investigation of the algorithm showed that it had three serious drawbacks, which prevented its use by practitioners: it is difficult to understand, it has large memory requirements, and it is slow. This paper presents an alternate formulation of SSS*, in which it is implemented as a series of alpha-beta calls that use a transposition table (ABSSS). The reformulation solves all three perceived drawbacks of SSS*, making it a practical algorithm. Further, because the search is now based on alpha-beta, the extensive research on minimax search enhancements can be easily integrated into ABSSS. To test ABSSS in practise, it has been implemented in three state-of-the-art programs: for checkers, Othello and chess. ABSSS is comparable in performance to alpha-beta on leaf node count in all three games, making it a viable alternative to alpha-beta in practise. Whereas SSS* has usually been regarded as being entirely different from alpha-beta, it turns out to be just an alpha-beta enhancement, like null-window searching. This runs counter to published simulation results. Our research leads to the surprising result that iterative deepening versions of alpha-beta can expand fewer leaf nodes than iterative deepening versions of SSS* due to dynamic move re-ordering.

SSS* minimax search algorithm, transposition table
hdl.handle.net/1765/1441
Erasmus School of Economics

Plaat, A, Schaeffer, J, Pijls, W.H.L.M, & de Bruin, A. (1995). SSS* = AB+TT. Retrieved from http://hdl.handle.net/1765/1441