Nau, D. S.



General branch and bound, and its relation to A* and AO*

Classics

Branch and Bound (B&B) is a problem-solving technique which is widely used for various problems encountered in operations research and combinatorial mathematics. Various heuristic search procedures used in artificial intelligence (AI) are considered to be related to B&B procedures. However, in the absence of any generally accepted terminology for B&B procedures, there have been widely differing opinions regarding the relationships between these procedures and B&B. This paper presents a formulation of B&B general enough to include previous formulations as special cases, and shows how two well-known AI search procedures (A and AO) are special cases of this general formulation.


Pathology on game trees revisited, and an alternative to minimaxing

Classics

Almost all game tree search procedures used in artificial intelligence are variants on minimaxing. Until recently, it was almost universally believed that searching deeper on the game tree with such procedures would in general yield a better decision. However, recent investigations have revealed the existence of many game trees and evaluation functions which are'pathological' in the sense that searching deeper consistently degrades the decision. First, it is shown that whenever the evaluation function satisfies certain properties, pathology will occur on any game tree of high enough constant branching factor.


Pathology on game trees: A summary of results

Classics

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. However, good results have been obtained by searching the tree to some limited depth, estimating the minimax values of the nodes at that depth using a heuristic evaluation function, and computing the minimax values for shallower nodes as if the estimated values were correct [2, 71. " max nodes (which we call S nodes) may have both " " and 1(-(1 children; " " min nodes (T nodes) have only " " children; *-II min nodes (U nodes) may have both " " and 11-(1 children; and --II max nodes (V nodes) have only 11-11 children. This pathological behavior occurs because as the search depth increases it becomes increasingly likely that all children of a critical node receive the same minimax value, whence a choice must be made at random among them.