MINIMAX ALGORITHM BETTER THAN ALPHA-BETA

An algorithm based on state space search is introduced for computing the minimax value of game trees. The new algorithm SSS* is shown to be more efficient than α-ß in the sense that SSS* never evaluates a node that α-ß can ignore. Moreover, for practical distributions of tip node values, SSS* can expect to do strictly better than α-ß in terms of average number of nodes explored. In order to be more informed than α-ß, SSS* sinks paths in parallel across the full breadth of the game tree. The penalty for maintaining these alternate search paths is a large increase in storage requirement relative to α-ß. Some execution time data is given which indicates that in some cases the tradeoff of storage for execution time may be favorable to SSS*. © 1979.