Product Propagation: A Backup Rule Better Than Minimaxing?
Authors:
- 17 December 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computational Intelligence and AI in Games
- Vol. 9 (2) , 109-122
Abstract
There is a gap between theory and practice regarding the assessment of minimaxing versus product propagation. The use of minimaxing in real programs for certain two-player games like chess is more or less ubiquitous, due to the substantial search space reductions enabled by several pruning algorithms. In stark contrast, some theoretical work supported the view that product propagation could be a viable alternative, or even superior on theoretical grounds. In fact, these rules have different conceptual problems. While minimaxing treats heuristic values as true values, product propagation interprets them as independent probabilities. So, which is the better rule for backing up heuristic values in game trees, and under which circumstances? We present a systematic analysis and results of simulation studies that compare these backup rules in synthetic trees with properties found in certain real game trees, for a variety of situations with characteristic properties. Our results show yet unobserved complementary strengths in their respective capabilities, depending on the size of node score changes (“quiet” versus “nonquiet” positions), and on the degree of advantage of any player over the opponent. In particular, exhaustive analyses for shallow depths show that product propagation can indeed be better than minimaxing when both approaches search to the same depth, especially for making decisions from a huge amount of alternatives, where deep searches are still prohibitive. However, our results also provide some justification for the more or less ubiquitous use of minimaxing in chess programs, where deep searches prevail and the pruning algorithms available for minimaxing make the difference.Keywords
This publication has 18 references indexed in Scilit:
- When is it better not to look ahead?Artificial Intelligence, 2010
- An analysis of decision quality of minimaxing vs. product propagation2009
- Learning to solve game trees2007
- Best-first minimax searchArtificial Intelligence, 1996
- Minimax search algorithms with and without aspiration windowsIEEE Transactions on Pattern Analysis and Machine Intelligence, 1991
- Comparison of the Minimax and Product Back-Up Rules in a Variety of Games1988
- Experiments on alternatives to minimaxInternational Journal of Parallel Programming, 1986
- On game graph structure and its influence on pathologyInternational Journal of Parallel Programming, 1983
- Pathology on game trees revisited, and an alternative to minimaxingArtificial Intelligence, 1983
- Experiments With a Multipurpose, Theorem-Proving Heuristic ProgramJournal of the ACM, 1968