Harris, L. R.

The heuristic search under conditions of error


This paper introduces a new restriction upon the heuristic, called the "bandwidth" condition, that enables the ordered search to better cope with time and space difficulties. Beyond this, the bandwidth condition quite naturally allows for the extension of the heuristic search to MIN/MAX trees. The resulting game playing algorithm affords many desirable practical features not found in minimax based techniques, as well as maintaining the theoretical framework of ordered searches. The development of this algorithm provides some additional insight to the general problem of searching game trees by showing that certain, somewhat surprising changes in the cost estimates are required to properly search the tree.