The alpha beta heuristic has been used extensively as a means for reducing the tree-searching effort in computer game-playing programs. It is well known that if the number of terminal nodes in a tree is N, then under optimal circumstances the alpha beta heuristic reduces the actual number of nodes examined to about 2N½. This is a substantial reduction in the case that N is on the order of ten thousand to a million. Unfortunately these optimal conditions are equivalent, in the case of game playing, to having immediate knowledge for every position in the tree as to which alternative is the best one; and this amount of foreknowledge would make tree searching unnecessary in the first place! This paper explores quantitively the performance of the alpha beta heuristic under a wide variety of conditions other than the optimal one, including several situations occurring in actual game-playing programs.

A particular decision-theoretic approach to the problem of detecting straight edges and lines in pictures is discussed. A model is proposed of the appearance of scenes consisting of prismatic solids, taking into account blurring, noise, and smooth variations in intensity over faces. A suboptimal statistical decision procedure is developed for the identification of a line within a narrow band in the field of view, given an array of intensity values from within the band. The performance of this procedure is illustrated and discussed.

A system of programs is described for the detection of the straight edge lines in simple scenes. Distinct lines are detected by a procedure that is relatively inexpensive. The more subtle lines are then located by a search that is much more costly per unit area, but which is only applied to certain areas suggested by the locations of the lines already found. The considerable efficiency of this approach to edge detection is discussed both theoretically and in relation to the performance of the present system. The heuristics used in proposing possible subtle lines are described in detail. In addition, considerable attention is devoted to other aspects of the procedure such as: local edge-detection operators, vertex finding, and the extraction of lines from local evidence.