Minimaxing: Theory and Practice

Hermann Kaindl

Abstract


Empirical evidence suggests that searching deeper in game trees using the minimax propagation rule usually improves the quality of decisions significantly. However, despite many recent theoretical analyses of the effects of minimax look ahead, however, this phenomenon has still not been convincingly explained. Instead, much attention has been given to so-called pathological behavior, which occurs under certain assumptions. This article supports the view that pathology is a direct result of these underlying theoretical assumptions. Pathology does not occur in practice, because these assumptions do not apply in realistic domains. The article presents several arguments in favor of minimaxing and focuses attention on the gap between their analytical formulation and their practical meaning. A new model is presented based on the strict separation of static and dynamic aspects in practical programs. finally, certain methods of improving minimax look-ahead are discussed, drawing on insights gained from this research.

Full Text:

PDF


DOI: http://dx.doi.org/10.1609/aimag.v9i3.944

Copyright © 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.