Asymptotic properties of minimax trees and game-searching procedures

摘要

The model most frequently used for evaluating the behavior of game-searching methods consists of a uniform tree of height h and a branching degree d, where the terminal positions are assigned random, independent and identically distributed values. This paper highlights some curious properties of such trees when h is very large and examines their implications on the complexity of various game-searching methods.If the terminal positions are assigned a WIN-LOSS status with the probabilities P0 and 1 − P0, respectively, then the root node is almost a sure MIN or a sure LOSS, depending on whether P0 is higher or lower than some fixed-point probability P∗(d). When the terminal positions are assigned continuous real values, the minimax value of the root node converges rapidly to a unique predetermined value v∗, which is the (1 − P∗)-fractile of the terminal distribution.Exploiting these properties we show that a game with WIN-LOSS terminals can be solved by examining, on the average, O[(d)h2] terminal positions if positions if P0 ≠ P∗ and O[(P∗(1 − P∗))h] positions if P0 = P∗, the former performance being optimal for all search algorithms. We further show that a game with continuous terminal values can be evaluated by examining an average of O[(P∗(1 − P∗))h] positions, and that this is a lower bound for all directional algorithms. Games with discrete terminal values can, in almost all cases, be evaluated by examining an average of O[(d)h2] terminal positions. This performance is optimal and is also achieved by the ALPHA-BETA procedure.