Pathology in game-trees is a counterintuitive phenomenon where a deeperminimax search results in worse play. It was discovered by Don Beal[1], who constructed a simple mathematical model to analyze the minimax algorithm. To his surprise, the analysis of the model showed that the backed-up values were actually somewhat less trustworthy than the heuristic values themselves.
Independently, pathology in game trees was coined by Dana Nau, who discovered pathology to exist in a large class of games [3] under the assumption of independence of sibling values of trees with low branching factor (i.e. binary trees) with game theoretic leaf values of win and loss {1, -1}. In a simulation, Nau introduced strong dependencies between sibling nodes and discovered that this can cause search-depth pathology to disappear. While Nau was primarily concerned with decision accuracy, Beal [4], as well as Bratko and Gams[5] were concerned with evaluation accuracy.
Random Evaluations
Quite contrary to pathology in chess, Beal and others demonstrated [6], that deeper search with random leaf values yields to better play. As a quintessence, Dana Nau et al. suggested an Error minimizing minimax search in their recent paper [7] .
Dana Nau (1979). Quality of Decision Versus Depth of Search on Game Trees. Ph.D. dissertation, Duke University
Dana Nau (1979). Preliminary results regarding quality of play versus depth of search in game playing. First Internat. Symposium on Policy Analysis and Information Systems, pp. 210–217, pdf
Dana Nau (1980). Pathology on game trees: A summary of results. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pp. 102–104, pdf
Dana Nau (1983). Decision quality as a function of search depth on game trees. Journal of the ACM 30(4):687–708, pdf
Dana Nau (1983). Pathology on game trees revisited, and an alternative to minimaxing.Artificial Intelligence, Vol. 21, No. 1-2, Reprinted in Judea Pearl (ed.), Search and Heuristics, North-Holland Publishing Company, Amsterdam, pdf
Bruce Abramson (1985). A Cure for Pathological Behavior in Games that Use Minimax. Proceedings of the Workshop on Uncertainty in Artificial Intelligence, 1985, 225-231.
Agata Muszycka (1985). Game Trees: Searching Techniques and Pathological Phenomenon. Master of Computer Science, Department of Computer Science, Concordia University, Montreal
Bruce Abramson (1986). An Explanation of and Cure for Minimax Pathology. Uncertainty in Artificial Intelligence, Laveen Kanal and John Lemmer, eds. (Amsterdam: North Holland, 1986), 495-504.
Ingo Althöfer (1991). On Pathology in Game Tree and other Recursion Tree Models, Habilitation Thesis (June 1991), Faculty of Mathematics, University of Bielefeld
Table of Contents
Decision vs Evaluation
Independently, pathology in game trees was coined by Dana Nau, who discovered pathology to exist in a large class of games [3] under the assumption of independence of sibling values of trees with low branching factor (i.e. binary trees) with game theoretic leaf values of win and loss {1, -1}. In a simulation, Nau introduced strong dependencies between sibling nodes and discovered that this can cause search-depth pathology to disappear. While Nau was primarily concerned with decision accuracy, Beal [4], as well as Bratko and Gams [5] were concerned with evaluation accuracy.Random Evaluations
Quite contrary to pathology in chess, Beal and others demonstrated [6], that deeper search with random leaf values yields to better play. As a quintessence, Dana Nau et al. suggested an Error minimizing minimax search in their recent paper [7] .See also
Publications
1979
1980 ...
1985 ...
1990 ...
1995 ...
2000 ...
2005 ...
2010 ...
Forum Posts
Re: Null Move in Quiescent search by Marcel van Kervinck, CCC, December 10, 2015 » PDS
Re: Null Move in Quiescent search by Harm Geert Muller, CCC, December 12, 2015
External Links
References
What links here?
Up one Level