Generalization of alpha-beta and SSS∗ search procedures

摘要

Search procedures, such as alpha-beta and SSS∗, are used to solve minimax game trees. With a notable exception of B∗, most of these procedures assume the static model, i.e., the computation is done solely on the basis of static values given to terminal nodes. The first goal of this paper is to generalize these to the informed model, which permits the usage of heuristic information pertaining to nonterminal nodes, such as upper and lower bounds, and estimates, of the exact values realizable from the corresponding game positions. We provide a general framework, within which various conventional procedures including alpha-beta and SSS∗ can be naturally generalized to the informed model.For the static model, it is known that SSS∗ surpasses alpha-beta in the sense that it explores only a subset of the nodes which are explored by alpha-beta. The second goal of this paper is, assuming the informed model, to develop a precise characterization of the class of search procedures that surpass alpha-beta. It turns out that the class contains many search procedures other than SSS∗ (even for the static model). Finally some computational comparison among these search procedures is made by solving the 4 × 4 Othello game.