Comparing Minimax and Product in a Variety of Games

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 6

Automated Reasoning

This paper describes comparisons of the minimax back-up rule and the product back-up rule on a wide variety of games, including P-games, G-games, three-hole kalah, Othello, and Ballard’s incremental game. In three-hole kalah, the product rule plays better than a minimax search to the same depth. This is a remarkable result, since it is the first widely known game in which product has been found to yield better play than minimax. Furthermore, the relative performance of minimax and product is related to a parameter called the rate of heuristic flaw (rhf). Thus, rhf has potential use in predicting when to use a back-up rule other than minimax.