A minimax algorithm better than alpha-beta? Yes and No

摘要

This paper contains a probabilistic analysis of the performance of the game-searching SSS* algorithm which has been shown to be superior to α-β. Necessary and sufficient conditions for node expansion are established, and an expression for the average number of nodes expanded is derived. The branching factor of SSS* is shown to coincide with that of α-β, thus rendering the two algorithms asymptotically equivalent. Numerical comparison of the expected complexities of the two algorithms is finally carried out over a wide spectrum of search depths and branching degrees. The latter shows that the savings in the number of positions evaluated by SSS* relative to that of α-β is rather limited and is not enough to offset the increase in other computational resources.