Pathology on Game Trees: A Summary of Results

Dana S. Nau

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 page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.