The variance of two game tree algorithms
Yanjun Zhang · 1997
This article studies the variance of two game tree algorithms, ?-s search and SCOUT, in the stochastic i.i.d. model. The problem of determining the variance of the classic ?-s search algorithm in the i.i.d. model was long open. This article resolves this problem partially. It is shown, by the martingale method, that the standard deviation of the weaker ?-s search without deep cutoffs is of the same order as the expected number of leaves evaluated. A nearly optimal upper bound on the variance of the general ?-s search is obtained. A thorough treatment of the two-pass SCOUT algorithm is presented. The variance of the SCOUT algorithm is determined.