Decision Quality As a Function of Search Depth on Game Trees
Dana S. Nau · Journal of the ACM · 1983
One important application of tree searching ~s "looking ahead" on a decision tree or game tree to try to predict the results of a decision.To guarantee correct results, substantial portions of the tree must be completely searched, which is physically impossible for very large trees.Aruficial intelligence researchers have obtained good results by searching the tree to some arbitrary depth and using a static evaluation function to estimate the values of the nodes at that depth.It is generally believed that when this is done, the quality of the decision improves as the search depth increases.This belief is based purely on empirical evidence.The author has developed a mathematical theory modeling the effects of search depth on the probability of making a correct decision.In this theory, the errors made by the evaluation function are modeled as independent, identically distributed random errors superimposed on the true values of the nodes evaluated.This research has produced the surprising result that there is an infinite class of game trees for which searching deeper does not increase the probability of making a correct decision, but instead causes the decision to become more and more random.The paper contains a mathematical proof of this statement, experimental verification of it, and a discussion of its significance.