A Partial Analysis of Minimaxing Game Trees with Random Leaf Values

Abstract

Random minimaxing, introduced by Beal and Smith, 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. Their experiments using random minimaxing in chess showed that the strength of play increases with the depth of the lookahead. We investigate random minim axing combinatorially in order to obtain a theoretical justification for Beal and Smith’s experiments. In particular, we show that, with respect to chess, random minim axing with the depth of lookahead equal to two is ‘stronger’ than the same with its depth equal to unity, under the assumption that a move by the first player is better the more it restricts the second player’s choice of moves (i.e., his mobility). We conjecture that these results can be generalized for depths of lookahead greater than two.