SSS* = α-β + TT

• Author(s) / Creator(s)

  • Schaeffer, Jonathan
  • Pijls, Wim
  • Plaat, Aske
  • de Bruin, Arie

• Technical report TR94-17. 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 (AB-SSS). 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 AB-SSS. To test AB-SSS* in practise, it has been implemented in three state-of-the-art programs: for checkers, Othello and chess. AB-SSS* 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. | TRID-ID TR94-17

• Date created

  1994

• Subjects / Keywords

  • Algorithms
  • SSS*
  • AB-SSS*

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3S17T02W

• License

  Attribution 3.0 International