Search Pathology

From Chessprogramming wiki
Jump to: navigation, search

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

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

Up one Level