Search Pathology

Home * Search * Pathology

Micrograph of membranous nephropathy ¹

Pathology in game-trees is a counterintuitive phenomenon where a deeper minimax search results in worse play. It was discovered by Don Beal ¹, 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.

Decision vs Evaluation

Independently, pathology in game trees was coined by Dana S. Nau, who discovered pathology to exist in a large class of games ² 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 ³, as well as Bratko and Gams ⁴ were concerned with evaluation accuracy.

Random Evaluations

Quite contrary to pathology in chess, Beal and others demonstrated ⁵, that deeper search with random leaf values yields to better play. As a quintessence, Dana S. Nau et al. suggested an Error minimizing minimax search in their recent paper ⁶ .

See also

• Conspiracy Numbers
• Depth
• Diminishing Returns
• Score Granularity
• Search Instability
• Search with Random Leaf Values
• Singularity and Pathology

Publications

1979

• Dana S. Nau (1979). Quality of Decision Versus Depth of Search on Game Trees. Ph.D. dissertation, Duke University
• Dana S. Nau (1979). Preliminary results regarding quality of play versus depth of search in game playing. First Internat. Symposium on Policy Analysis and Information Systems, pdf

1980 ...

• Don Beal (1980). An analysis of minimax. Advances in Computer Chess 2
• Dana S. 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 S. Nau (1982). An Investigation of the Causes of Pathology in Games. Artificial Intelligence, Vol. 19, 257–278, University of Maryland, College Park, Recommended by Judea Pearl, pdf
• Ivan Bratko, Matjaž Gams (1982). Error Analysis of the Minimax Principle. Advances in Computer Chess 3
• Don Beal (1982). Benefits of minimax search. Advances in Computer Chess 3
• Dana S. Nau (1983). Decision quality as a function of search depth on game trees. Journal of the ACM, Vol. 30, No. 4, pdf
• Dana S. 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
• Judea Pearl (1983). On the Nature of Pathology in Game Searching. Artificial Intelligence, Vol. 20
• Chun-Hung Tzeng, Paul W. Purdom (1983). A Theory of Game Trees. AAAI-83

1985 ...

• Bruce Abramson (1985). A Cure for Pathological Behavior in Games that Use Minimax. Uncertainty in Artificial Intelligence 1, arXiv:1304.3444
• Agata Muszycka (1985). Game Trees: Searching Techniques and Pathological Phenomenon. Masters thesis, Department of Computer Science, Concordia University, Montreal
• Bruce Abramson (1986). An Explanation of and Cure for Minimax Pathology. Uncertainty in Artificial Intelligence 2
• Günther Schrüfer (1986). Presence and Absence of Pathology on Game Trees. Advances in Computer Chess 4
• Ingo Althöfer (1988). Root Evaluation Errors: How they Arise and Propagate. ICCA Journal, Vol. 11, Nos. 2/3
• Liwu Li (1989). Probabilistic Analysis of Search. Ph.D. thesis, University of Alberta, advisor Tony Marsland

1990 ...

• Liwu Li, Tony Marsland (1990). On Minimax Game Tree Search Pathology and Node-value Dependence. TR90-24, University of Alberta, pdf
• Ingo Althöfer (1991). On Pathology in Game Tree and other Recursion Tree Models, Habilitation Thesis (June 1991), Faculty of Mathematics, University of Bielefeld
• Don Beal, Martin C. Smith (1994). Random Evaluations in Chess. ICCA Journal, Vol. 17, No. 1
• Don Beal, Martin C. Smith (1994). Random Evaluations in Chess. Advances in Computer Chess 7

1995 ...

• Mark Levene, Trevor Fenner (1995). A Partial Analysis of Minimaxing Game Trees with Random Leaf Values. ICCA Journal, Vol. 18, No. 1
• Ingo Althöfer, Imre Leader (1995). Correlation of Boolean Functions and Pathology in Recursion Trees. SIAM Journal on Discrete Mathematics, Vol. 8, No. 4
• Don Beal (1999). The Nature of MINIMAX Search. Ph.D. thesis, IKAT, ISBN 90-62-16-6348

2000 ...

• Mark Levene, Trevor Fenner (2001). The Effect of Mobility on Minimaxing of Game Trees with Random Leaf Values. Artificial Intelligence, Vol. 130, No. 1, Review in ICGA Journal, Vol. 24, No. 4

2005 ...

• Mitja Luštrek, Matjaž Gams, Ivan Bratko (2005). Why Minimax Works: An Alternative Explanation. IJCAI 2005, pdf
• Aleksander Sadikov, Ivan Bratko, Igor Kononenko (2005). Bias and Pathology in Minimax Search. Theoretical Computer Science,, Vol. 349, 2, pdf
• Mitja Luštrek, Matjaž Gams, Ivan Bratko (2006). Is Real-Valued Minimax Pathological? Artificial Intelligence, Vol. 170, pdf
• Brandon Wilson, Austin Parker, Dana S. Nau (2009). Error Minimizing Minimax: Avoiding Search Pathology in Game Trees. pdf

2010 ...

• Dana S. Nau, Mitja Luštrek, Austin Parker, Ivan Bratko, Matjaž Gams (2010). When is it better not to look ahead?. Artificial Intelligence, Vol. 174, No. 16–17, preprint as pdf
• Mitja Luštrek, Ivan Bratko, Matjaž Gams (2011). Independent-valued minimax : Pathological or beneficial? Theoretical Computer Science, Vol. 422, pdf
• Inon Zuckerman, Brandon Wilson, Dana S. Nau (2018). Avoiding game-tree pathology in 2-player adversarial search. Computational Intelligence, Vol. 34, No. 2

Forum Posts

• Theory: Deeper Search creating worse performance due to PE by Charles Roberson, January 04, 2006
• Pathology on Game trees by Gerd Isenberg, CCC, July 22, 2010
• Re: Null Move in Quiescent search by Harm Geert Muller, CCC, December 10, 2015 » Null Move Pruning, Quiescence Search

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

• random evaluation perturbation factor by Stuart Cracraft, CCC, April 24, 2017

External Links

• Pathology (disambiguation) from Wikipedia
• Pathological (mathematics) from Wikipedia
• Pathology from Wikipedia
• Pathological science from Wikipedia

References