Consider complete game trees of height h and degree d. The randomized complexity C ( d , h ) of evaluating game trees is the minimum (over all randomized algorithms) of the maximum (over all game trees) of the expected number of leaves evaluated by the algorithm. It is known that an asymptotic branching factor exists, and is such that as d approaches infinity. The &agr; - &bgr; pruning procedure is a well-known method of evaluating game trees. This paper studies a randomized version (children of a parent node are evaluated in random order), for which we expect to have an analogous branching factor Bd. Zhang shows that Bd &slash; B*d approaches 1 as d approaches infinity: in this sense, randomized &agr; - &bgr; search is asymptotically optimal.
