Game Solving Procedure SSSR is Unsurpassed
Yoshiroh Katoh, Toshihide Ibaraki · Systems and Computers in Japan · 1988
Abstract Two‐person zero‐sum games with perfect information can be represented by minimax game trees. By solving such game trees, it is possible to compute the game values that are realized when both players always choose the best moves. Various search algorithms, such as α ‐β, SSS*, dual SSS*, B*, H*, are known for this purpose. Let A and B be two search algorithms; A surpasses B if, for any game tree, the region explored by A before computing the game value is contained in the region explored by B; A strictly surpasses B if A surpasses B and the region explored by A is properly contained in the region explored by B for at least one game tree. In this paper, we prove that no search algorithm strictly surpasses SSS* or dual SSS*.