ISSN:
1573-7640
Keywords:
Artificial intelligence
;
decision analysis
;
decision trees
;
games
;
game trees
;
minimaxing
;
pathology
;
problem solving
;
search
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract Almost all game tree search procedures used in Artificial Intelligence are variants on minimaxing. Until recently, it was almost universally believed that searching deeper on game trees with such procedures would in general yield a better decision. However, recent investigations show that there are many “pathological” game trees for which searching deeper consistentlydegrades the decision. This paper investigates one possible cause of pathology. In particular, a class of games that is normally pathological is shown to become nonpathological when the games are modified so that game positions can be reached by more than one path. This result suggests that in general, pathology is less likely when game positions can be reached by more than one path. This may be one reason why games such as chess and checkers are nonpathological. In addition, this result supports the hypothesis(9) that pathology is less likely when sibling nodes have similar minimax values. This paper also investigates a possible cure for pathology-an alternative to minimaxing called probability estimation which has been shown to avoid pathology and thus produce more accurate decisions than minimaxing on at least one pathological game. (11) The current paper shows that depending on what evaluation function is used, probability estimation can also produce more accurate decisions than minimaxing on at least one nonpathological game. Probability estimation or other related procedures could conceivably become attractive alternatives to minimaxing if suitable tree pruning procedures could be developed for use with them.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00977966
