Pathology on game trees: A summary of results

PATHOLOGY ON GAME TREES: A SUMMARY OF RESULTS* Dana S. Nau Department of Computer Science University of Maryland College Park, MD 20742 ABSTRACT Game trees are widely used as models of various decision-making situations. Empirical results with game-playing computer programs have led to the general belief that searching deeper on a game tree improves the quality of a decision. The surprising result of the research summarized in this paper is that there is an infinite class of game trees for which increasing the search depth does not improve the decision quality, but instead makes the decision more and more random. This research has produced the surprising result that there is an infinite class of game trees for which as long as the search does not reach the end of the tree (in which case the best possible decision could be guaranteed), deeper search does not improve the decision quality, but instead makes the decision more and more random. For example, probability of I INTRODUCTION - Many decision-making processes are naturally modeled as perfect information games between two players [3, 71.