Predicting The Performance of Minimax and Product in Game-Tree
Ping-Chung Chi, Dana Nau
The discovery that the minimax decision rule performs poorly in some games has sparked interest in possible alternatives to minimax. Until recently, the only games in which minimax was known to perform poorly were games which were mainly of theoretical interest. However, this paper reports results showing poor performance of minimax in a more common game called kalah. For the kalah games tested, a non-minimax decision rule called the product rule performs significantly better than minimax.
This paper also discusses a possible way to predict whether or not minimax will perform well in a game when compared to product. A parameter called the rate of heuristic flaw (rhf) has been found to correlate positively with the. performance of product against minimax. Both analytical and experimental results are given that appear to support the predictive power of rhf.
PDF Link: /papers/86/p49-chi.pdf
AUTHOR = "Ping-Chung Chi
and Dana Nau",
TITLE = "Predicting The Performance of Minimax and Product in Game-Tree",
BOOKTITLE = "Proceedings of the Second Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-86)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "1986",
PAGES = "49--56"