Home * Search * Pathology
Membranous_nephropathy_-_mpas_-_very_high_mag.jpg

Pathology in game-trees is a counterintuitive phenomenon where a deeper minimax 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.
Micrograph of membranous nephropathy [2]

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

  • 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

1980 ...

1985 ...

1990 ...

1995 ...

2000 ...

2005 ...

2010 ...


Forum Posts


External Links


References

  1. ^ Don Beal (1980). An analysis of minimax. Advances in Computer Chess 2
  2. ^ 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
  3. ^ Dana 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 Nau (2009). Error Minimizing Minimax: Avoiding Search Pathology in Game Trees. pdf

What links here?


Up one Level