The Bandwidth Heuristic Search

Abstract

By placing various restrictions on heuristic estimator it is possible constrain the heuristic search process to specific needs. This paper introduces a restriction upon the heuristic, called "bandwidth" condition, that enables ordered search to better cope with time space difficulties. In particular, effect of error within the heuristic considered in detail . the to fit new the the and the is Beyond this the bandwidth condition quite naturally allows for the extension of the heuristic search to 11IN/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 searchs. 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. Furthermore, the use of an ordered search of !1IN/!-1AX trees brings about a rather provocative departure from the conventional approach to computer game playing.