SSS* = AB+TT
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.
|Keywords||SSS* minimax search algorithm, transposition table|
Plaat, A., Schaeffer, J., Pijls, W.H.L.M., & de Bruin, A.. (1995). SSS* = AB+TT. Retrieved from http://hdl.handle.net/1765/1441