COMPLEXITY OF DECISION TREES, THE QUASI-OPTIMIZER, AND THE POWER OF HEURISTIC RULES

The power of certain heuristic rules is indicated by the relative reduction in the complexity of computations carried out, due to the use of the heuristics. A concept of complexity is needed to evaluate the performance of programs as they operate with a varying set of heuristic rules in use. We present such a complexity measure, which we have found useful for the quantitative evaluation of strategies in the context of a long-term research project on poker. We define our measure in terms of the level-complexity for decision trees and study the measure for the relevant class of decision trees with a fixed but arbitrary number of levels, h, and k leaves (all at the last level). We determine the best and worst case distributions for the levels in this measure. We show, for instance, that for the smallest value, Lh(k), and the largest value, Uh(k), which the level-complexity for such trees can have, limk→∞ Lh(k)/logh(k) = 1 and limk→∞ Uh(k)/log(k) = 1. We show also that the level-entropy assumes its maximum value of log(k) just when the path-entropy reaches its minimum value over all trees with k leaves but, in general, the values of either measure can vary in a rather unrelated manner. We give a detailed example of how the complexity measure is used in evaluating the power of heuristic rules used in assessing the performance of the Quasi-Optimizer (QO), a program currently under development. The objectives of the QO are explained, and the three main phases of operation of the program are described within the framework of the poker project. © 1979 Academic Press, Inc.