Difference between revisions of "Search Pathology"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
| Line 6: | Line 6: | ||
=Decision vs Evaluation= | =Decision vs Evaluation= | ||
| − | Independently, pathology in game trees was coined by [[Dana Nau]], who discovered pathology to exist in a large class of games <ref>[[Dana Nau]] ('''1982'''). ''An Investigation of the Causes of Pathology in Games.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 19, 257–278, [https://en.wikipedia.org/wiki/University_of_Maryland,_College_Park University of Maryland, College Park], Recommended by [[Judea Pearl]], [http://www.cs.umd.edu/%7Enau/papers/nau82investigation.pdf pdf]</ref> 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 <ref>[[Don Beal]] ('''1982'''). ''Benefits of minimax search''. [[Advances in Computer Chess 3]]</ref>, as well as [[Ivan Bratko|Bratko]] and [[Matjaž Gams|Gams]] <ref>[[Ivan Bratko]], [[Matjaž Gams]] ('''1982'''). ''Error Analysis of the Minimax Principle''. [[Advances in Computer Chess 3]]</ref> were concerned with evaluation accuracy. | + | Independently, pathology in game trees was coined by [[Dana S. Nau]], who discovered pathology to exist in a large class of games <ref>[[Dana S. Nau]] ('''1982'''). ''An Investigation of the Causes of Pathology in Games.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 19, 257–278, [https://en.wikipedia.org/wiki/University_of_Maryland,_College_Park University of Maryland, College Park], Recommended by [[Judea Pearl]], [http://www.cs.umd.edu/%7Enau/papers/nau82investigation.pdf pdf]</ref> 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 <ref>[[Don Beal]] ('''1982'''). ''Benefits of minimax search''. [[Advances in Computer Chess 3]]</ref>, as well as [[Ivan Bratko|Bratko]] and [[Matjaž Gams|Gams]] <ref>[[Ivan Bratko]], [[Matjaž Gams]] ('''1982'''). ''Error Analysis of the Minimax Principle''. [[Advances in Computer Chess 3]]</ref> were concerned with evaluation accuracy. |
<span id="RandomEvaluations"></span> | <span id="RandomEvaluations"></span> | ||
=Random Evaluations= | =Random Evaluations= | ||
| − | Quite contrary to pathology in chess, Beal and others demonstrated <ref>[[Don Beal]], [[Martin C. Smith]] ('''1994'''). ''Random Evaluations in Chess''. [[ICGA Journal#17_1|ICCA Journal, Vol. 17, No. 1]]</ref>, that deeper [[Search with Random Leaf Values|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 <ref>[[Brandon Wilson]], [[Austin Parker]], [[Dana Nau]] ('''2009'''). ''Error Minimizing Minimax: Avoiding Search Pathology in Game Trees''. [http://www.cs.umd.edu/~nau/papers/wilson2009error.pdf pdf]</ref> . | + | Quite contrary to pathology in chess, Beal and others demonstrated <ref>[[Don Beal]], [[Martin C. Smith]] ('''1994'''). ''Random Evaluations in Chess''. [[ICGA Journal#17_1|ICCA Journal, Vol. 17, No. 1]]</ref>, that deeper [[Search with Random Leaf Values|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 <ref>[[Brandon Wilson]], [[Austin Parker]], [[Dana S. Nau]] ('''2009'''). ''Error Minimizing Minimax: Avoiding Search Pathology in Game Trees''. [http://www.cs.umd.edu/~nau/papers/wilson2009error.pdf pdf]</ref> . |
=See also= | =See also= | ||
| Line 22: | Line 22: | ||
=Publications= | =Publications= | ||
==1979== | ==1979== | ||
| − | * [[Dana Nau]] ('''1979'''). ''Quality of Decision Versus Depth of Search on Game Trees.'' Ph.D. dissertation, [[Duke University]] | + | * [[Dana S. 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, | + | * [[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, [http://www.cs.umd.edu/%7Enau/papers/nau79preliminary.pdf pdf] |
==1980 ...== | ==1980 ...== | ||
* [[Don Beal]] ('''1980'''). ''An analysis of minimax''. [[Advances in Computer Chess 2]] | * [[Don Beal]] ('''1980'''). ''An analysis of minimax''. [[Advances in Computer Chess 2]] | ||
| − | * [[Dana Nau]] ('''1980'''). ''Pathology on game trees: A summary of results.'' In Proceedings of the National Conference on Artificial Intelligence (AAAI), pp. 102–104, [http://www.cs.umd.edu/%7Enau/papers/pathology-aaai80.pdf pdf] | + | * [[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, [http://www.cs.umd.edu/%7Enau/papers/pathology-aaai80.pdf pdf] |
| − | * [[Dana Nau]] ('''1982'''). ''An Investigation of the Causes of Pathology in Games.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 19, 257–278, [https://en.wikipedia.org/wiki/University_of_Maryland,_College_Park University of Maryland, College Park], Recommended by [[Judea Pearl]], [http://www.cs.umd.edu/%7Enau/papers/nau82investigation.pdf pdf] | + | * [[Dana S. Nau]] ('''1982'''). ''An Investigation of the Causes of Pathology in Games.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 19, 257–278, [https://en.wikipedia.org/wiki/University_of_Maryland,_College_Park University of Maryland, College Park], Recommended by [[Judea Pearl]], [http://www.cs.umd.edu/%7Enau/papers/nau82investigation.pdf pdf] |
* [[Ivan Bratko]], [[Matjaž Gams]] ('''1982'''). ''Error Analysis of the Minimax Principle''. [[Advances in Computer Chess 3]] | * [[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]] | * [[Don Beal]] ('''1982'''). ''Benefits of minimax search''. [[Advances in Computer Chess 3]] | ||
| − | * [[Dana Nau]] ('''1983'''). ''Decision quality as a function of search depth on game trees.'' Journal of the ACM 30(4):687–708, [http://www.cs.umd.edu/%7Enau/papers/nau83decision.pdf pdf] | + | * [[Dana S. Nau]] ('''1983'''). ''Decision quality as a function of search depth on game trees.'' Journal of the ACM 30(4):687–708, [http://www.cs.umd.edu/%7Enau/papers/nau83decision.pdf pdf] |
| − | * [[Dana Nau]] ('''1983'''). ''Pathology on game trees revisited, and an alternative to minimaxing.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 21, No. 1-2, Reprinted in [[Judea Pearl]] (ed.), Search and Heuristics, North-Holland Publishing Company, Amsterdam, [http://www.cs.umd.edu/%7Enau/papers/nau83pathology.pdf pdf] | + | * [[Dana S. Nau]] ('''1983'''). ''Pathology on game trees revisited, and an alternative to minimaxing.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 21, No. 1-2, Reprinted in [[Judea Pearl]] (ed.), Search and Heuristics, North-Holland Publishing Company, Amsterdam, [http://www.cs.umd.edu/%7Enau/papers/nau83pathology.pdf pdf] |
* [[Judea Pearl]] ('''1983'''). ''On the Nature of Pathology in Game Searching''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 20, 427-453. | * [[Judea Pearl]] ('''1983'''). ''On the Nature of Pathology in Game Searching''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 20, 427-453. | ||
==1985 ...== | ==1985 ...== | ||
| Line 55: | Line 55: | ||
* [[Aleksander Sadikov]], [[Ivan Bratko]], [[Igor Kononenko]] ('''2005'''). ''[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-4HCN79X-1&_user=10&_coverDate=12%2F14%2F2005&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=79f966215bea9b7461b6877c9373b0bf Bias and Pathology in Minimax Search]''. [https://en.wikipedia.org/wiki/Theoretical_Computer_Science_%28journal%29 Theoretical Computer Science],, Vol. 349, 2, [http://lkm.fri.uni-lj.si/xaigor/slo/clanki/Sadikov_final.pdf pdf] | * [[Aleksander Sadikov]], [[Ivan Bratko]], [[Igor Kononenko]] ('''2005'''). ''[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-4HCN79X-1&_user=10&_coverDate=12%2F14%2F2005&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=79f966215bea9b7461b6877c9373b0bf Bias and Pathology in Minimax Search]''. [https://en.wikipedia.org/wiki/Theoretical_Computer_Science_%28journal%29 Theoretical Computer Science],, Vol. 349, 2, [http://lkm.fri.uni-lj.si/xaigor/slo/clanki/Sadikov_final.pdf pdf] | ||
* [[Mitja Luštrek]], [[Matjaž Gams]], [[Ivan Bratko]] ('''2006'''). ''Is Real-Valued Minimax Pathological''? [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 170, [https://dis.ijs.si/MitjaL/documents/Is_Real-Valued_Minimax_Pathological-AIJ-06.pdf pdf] | * [[Mitja Luštrek]], [[Matjaž Gams]], [[Ivan Bratko]] ('''2006'''). ''Is Real-Valued Minimax Pathological''? [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 170, [https://dis.ijs.si/MitjaL/documents/Is_Real-Valued_Minimax_Pathological-AIJ-06.pdf pdf] | ||
| − | * [[Brandon Wilson]], [[Austin Parker]], [[Dana Nau]] ('''2009'''). ''Error Minimizing Minimax: Avoiding Search Pathology in Game Trees''. [http://www.cs.umd.edu/~nau/papers/wilson2009error.pdf pdf] | + | * [[Brandon Wilson]], [[Austin Parker]], [[Dana S. Nau]] ('''2009'''). ''Error Minimizing Minimax: Avoiding Search Pathology in Game Trees''. [http://www.cs.umd.edu/~nau/papers/wilson2009error.pdf pdf] |
==2010 ...== | ==2010 ...== | ||
| − | * [[ | + | * [[Dana S. Nau]], [[Mitja Luštrek]], [[Austin Parker]], [[Ivan Bratko]], [[Matjaž Gams]] ('''2010'''). ''[http://www.sciencedirect.com/science/article/pii/S0004370210001402 When is it better not to look ahead?]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 174, No. 16–17, [http://dis.ijs.si/mitjal/documents/Nau-When_is_it_better_not_to_look_ahead-AIJ-10.pdf preprint as pdf] |
* [[Mitja Luštrek]], [[Ivan Bratko]], [[Matjaž Gams]] ('''2011'''). ''[http://www.sciencedirect.com/science/article/pii/S0304397511009522 Independent-valued minimax : Pathological or beneficial?]'' [https://en.wikipedia.org/wiki/Theoretical_Computer_Science_%28journal%29 Theoretical Computer Science], Vol. 422, [http://dis.ijs.si/MitjaL/documents/Independent-valued_minimax-Pathological_or_beneficial-TCS-12.pdf pdf] | * [[Mitja Luštrek]], [[Ivan Bratko]], [[Matjaž Gams]] ('''2011'''). ''[http://www.sciencedirect.com/science/article/pii/S0304397511009522 Independent-valued minimax : Pathological or beneficial?]'' [https://en.wikipedia.org/wiki/Theoretical_Computer_Science_%28journal%29 Theoretical Computer Science], Vol. 422, [http://dis.ijs.si/MitjaL/documents/Independent-valued_minimax-Pathological_or_beneficial-TCS-12.pdf pdf] | ||
| + | * [[Inon Zuckerman]], [[Brandon Wilson]], [[Dana S. Nau]] ('''2018'''). ''[https://onlinelibrary.wiley.com/doi/abs/10.1111/coin.12162 Avoiding game-tree pathology in 2-player adversarial search]''. [https://en.wikipedia.org/wiki/Computational_Intelligence_(journal) Computational Intelligence], Vol. 34, No. 2 | ||
=Forum Posts= | =Forum Posts= | ||
Revision as of 12:42, 19 February 2019
Micrograph of membranous nephropathy [1]
Pathology in game-trees is a counterintuitive phenomenon where a deeper minimax search results in worse play. It was discovered by Don Beal [2], 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.
Contents
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 [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 S. Nau et al. suggested an Error minimizing minimax search in their recent paper [7] .
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 30(4):687–708, 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, 427-453.
1985 ...
- 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.
- 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
- 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
- ↑ Very high magnification micrograph of membranous nephropathy, abbreviated MN. MN may also be referred to as membranous glomerulonephritis, abbreviated MGN. Kidney biopsy. Jones stain, Pathology from Wikipedia
- ↑ Don Beal (1980). An analysis of minimax. Advances in Computer Chess 2
- ↑ 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
- ↑ Don Beal (1982). Benefits of minimax search. Advances in Computer Chess 3
- ↑ Ivan Bratko, Matjaž Gams (1982). Error Analysis of the Minimax Principle. Advances in Computer Chess 3
- ↑ Don Beal, Martin C. Smith (1994). Random Evaluations in Chess. ICCA Journal, Vol. 17, No. 1
- ↑ Brandon Wilson, Austin Parker, Dana S. Nau (2009). Error Minimizing Minimax: Avoiding Search Pathology in Game Trees. pdf
