Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
An Explanation of and Cure for Minimax Pathology
Bruce Abramson
Abstract:
The traditional approach to choosing moves in game-playing programs is the minimax procedure. The general belief underlying its use is that increasing search depth improves play. Recent research has shown that given certain simplifying assumptions about a game tree's structure, this belief is erroneous: searching deeper decreases the probability of making a correct move. This phenomenon is called game tree pathology. Among these simplifying assumptions is uniform depth of win/loss (terminal) nodes, a condition which is not true for most real games. Analytic studies in [10] have shown that if every node in a pathological game tree is made terminal with probability exceeding a certain threshold, the resulting tree is nonpathological. This paper considers a new evaluation function which recognizes increasing densities of forced wins at deeper levels in the tree. This property raises two points that strengthen the hypothesis that uniform win depth causes pathology. First, it proves mathematically that as search deepens, an evaluation function that does not explicitly check for certain forced win patterns becomes decreasingly likely to force wins. This failing predicts the pathological behavior of the original evaluation function. Second, it shows empirically that despite recognizing fewer mid-game wins than the theoretically predicted minimum, the new function is nonpathological.
Keywords: Minimax, Patuology
Pages: 495-504
PS Link:
PDF Link: /papers/85/p495-abramson.pdf
BibTex:
@INPROCEEDINGS{Abramson85,
AUTHOR = "Bruce Abramson ",
TITLE = "An Explanation of and Cure for Minimax Pathology",
BOOKTITLE = "Uncertainty in Artificial Intelligence Annual Conference on Uncertainty in Artificial Intelligence (UAI-85)",
PUBLISHER = "Elsevier Science",
ADDRESS = "Amsterdam, NL",
YEAR = "1985",
PAGES = "495--504"
}


hosted by DSL   •   site info   •   help