The effect of mobility on minimaxing of game trees with random leaf values

Random minimaxing, introduced by Beal and Smith [ICCA J. 17 (1994) 3-9], is the process: of using a random static evaluation function for scoring the leaf nodes of a full width game tree and then computing the best move using the standard minimax procedure. The experiments carried out by Beal and Sm ith, using random minimaxing in Chess, showed that the strength of play inc reases as the depth of the lookahead is increased. We investigate random mi nimaxing from a combinatorial point of view in an attempt to gain a better understanding of the utility of the minimax procedure and a theoretical jus tification for the results of Beal and Smith's experiments. The concept of domination is central to our theory. Intuitively, one move by white dominat es another move when choosing the former move would give less choice for bl ack when it is black's turn to move, and subsequently more choice for white when it is white's turn to move. We view domination as a measure of mobili ty and show that when one move dominates: another then its probability of b eing chosen is higher. We then investigate when the probability of a "good" move relative to the p robability of a "bad" move increases with the depth of search. We show that there exist situations when increased depth of search is "beneficial" but that this is not always the case. Under the assumption that each move is ei ther "good" or "bad", we are able to state sufficient conditions to ensure that increasing the depth of starch increases the strength of play of rando m minimaxing. If the semantics of the game under consideration match these assumptions then it is fair to say that random minimaxing appears to follow a reasonably "intelligent" strategy. In practice domination does not alway s occur, so it remains an open problem to find a more general measure of mo bility in the absence of domination. (C) 2001 Elsevier Science B.V. All rig hts reserved.