Predicting The Performance of Minimax and Product in Game-Tree
This addresses the issue of suboptimal decision-making in game AI for researchers and practitioners, offering a predictive tool for game performance, though it is incremental as it builds on known alternatives to minimax.
The paper tackles the problem of minimax performing poorly in certain games, showing that in kalah, the product rule significantly outperforms minimax, with concrete experimental results indicating better performance. It also introduces a parameter called the rate of heuristic flaw (rhf) to predict when minimax will underperform compared to product, supported by analytical and experimental evidence.
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.