Difference between revisions of "Search Pathology"

From Chessprogramming wiki
Jump to: navigation, search
m
 
(6 intermediate revisions by the same user not shown)
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, pp. 210–217, [http://www.cs.umd.edu/%7Enau/papers/nau79preliminary.pdf pdf]
+
* [[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.'' [[ACM#Journal|Journal of the ACM]], Vol. 30, No. 4, [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
 +
* [[Chun-Hung Tzeng]], [[Paul W. Purdom]] ('''1983'''). ''[https://www.aaai.org/Library/AAAI/1983/aaai83-080.php A Theory of Game Trees]''. [[Conferences#AAAI-83|AAAI-83]]
 
==1985 ...==  
 
==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.
+
* [[Bruce Abramson]] ('''1985'''). ''A Cure for Pathological Behavior in Games that Use Minimax.'' [[Laveen Kanal#Uncertainty AI 1|Uncertainty in Artificial Intelligence 1]], [https://arxiv.org/abs/1304.3444 arXiv:1304.3444]
−
* [[Agata Muszycka-Jones|Agata Muszycka]] ('''1985'''). ''Game Trees: Searching Techniques and Pathological Phenomenon''. Master of Computer Science, Department of Computer Science, [https://en.wikipedia.org/wiki/Concordia_University Concordia University], [https://en.wikipedia.org/wiki/Montreal Montreal]
+
* [[Agata Muszycka-Jones|Agata Muszycka]] ('''1985'''). ''[https://spectrum.library.concordia.ca/3343/ Game Trees: Searching Techniques and Pathological Phenomenon]''. Masters thesis, Department of Computer Science, [https://en.wikipedia.org/wiki/Concordia_University Concordia University], [https://en.wikipedia.org/wiki/Montreal 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.
+
* [[Bruce Abramson]] ('''1986'''). ''[https://www.sciencedirect.com/science/article/pii/B9780444700582500413 An Explanation of and Cure for Minimax Pathology]''. [[Laveen Kanal#Uncertainty AI 2|Uncertainty in Artificial Intelligence 2]]
 
* [[Günther Schrüfer]] ('''1986'''). ''Presence and Absence of Pathology on Game Trees''. [[Advances in Computer Chess 4]]
 
* [[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''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]
 
* [[Ingo Althöfer]] ('''1988'''). ''Root Evaluation Errors: How they Arise and Propagate''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]
Line 52: Line 53:
 
* [[Mark Levene]], [[Trevor Fenner]] ('''2001'''). ''The Effect of Mobility on Minimaxing of Game Trees with Random Leaf Values''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 130, No. 1, Review in [[ICGA Journal#18_1|ICGA Journal, Vol. 24, No. 4]]
 
* [[Mark Levene]], [[Trevor Fenner]] ('''2001'''). ''The Effect of Mobility on Minimaxing of Game Trees with Random Leaf Values''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 130, No. 1, Review in [[ICGA Journal#18_1|ICGA Journal, Vol. 24, No. 4]]
 
==2005 ...==  
 
==2005 ...==  
−
* [[Mitja Luštrek]], [[Matjaž Gams]], [[Ivan Bratko]] ('''2005'''). ''[http://dl.acm.org/citation.cfm?id=1642327 Why Minimax Works: An Alternative Explanation]''. [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai2005.html#LustrekGB05 IJCAI 2005]
+
* [[Mitja Luštrek]], [[Matjaž Gams]], [[Ivan Bratko]] ('''2005'''). ''Why Minimax Works: An Alternative Explanation''. [[Conferences#IJCAI2005|IJCAI 2005]], [https://www.ijcai.org/Proceedings/05/Papers/1223.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]
 
* [[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, [http://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 Nau|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]
+
* [[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=
 +
* [https://www.stmintz.com/ccc/index.php?id=476965 Theory: Deeper Search creating worse performance due to PE] by [[Charles Roberson]], January 04, 2006
 
* [http://www.talkchess.com/forum/viewtopic.php?t=35538 Pathology on Game trees] by [[Gerd Isenberg]], [[CCC]], July 22, 2010
 
* [http://www.talkchess.com/forum/viewtopic.php?t=35538 Pathology on Game trees] by [[Gerd Isenberg]], [[CCC]], July 22, 2010
 
* [http://www.talkchess.com/forum/viewtopic.php?t=58527&start=10 Re: Null Move in Quiescent search] by [[Harm Geert Muller]], [[CCC]], December 10, 2015 » [[Null Move Pruning]], [[Quiescence Search]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=58527&start=10 Re: Null Move in Quiescent search] by [[Harm Geert Muller]], [[CCC]], December 10, 2015 » [[Null Move Pruning]], [[Quiescence Search]]
Line 75: Line 78:
 
=References=  
 
=References=  
 
<references />
 
<references />
−
 
 
'''[[Search|Up one Level]]'''
 
'''[[Search|Up one Level]]'''

Latest revision as of 11:13, 4 April 2021

Home * Search * Pathology

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.

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

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 ...

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

  1. ↑ 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
  2. ↑ Don Beal (1980). An analysis of minimax. Advances in Computer Chess 2
  3. ↑ 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
  4. ↑ Don Beal (1982). Benefits of minimax search. Advances in Computer Chess 3
  5. ↑ Ivan Bratko, Matjaž Gams (1982). Error Analysis of the Minimax Principle. Advances in Computer Chess 3
  6. ↑ Don Beal, Martin C. Smith (1994). Random Evaluations in Chess. ICCA Journal, Vol. 17, No. 1
  7. ↑ Brandon Wilson, Austin Parker, Dana S. Nau (2009). Error Minimizing Minimax: Avoiding Search Pathology in Game Trees. pdf

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=Search_Pathology&oldid=24144"