A 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∗.