Pathology on Game Trees: A Summary of Results

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. Many decision-making processes are naturally modeled as perfect information games between two players [3, 71. Such games are generally