Accession Number : AD0766953
Title : The Bandwidth Heuristic Search.
Descriptive Note : Technical rept.,
Corporate Author : DARTMOUTH COLL HANOVER N H DEPT OF MATHEMATICS
Personal Author(s) : Harris,Larry R.
Report Date : FEB 1973
Pagination or Media Count : 30
Abstract : By placing various restrictions on the heuristic estimator it is possible to constrain the heuristic search process to fit specific needs. The 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. In particular, the effect of error within the heuristic is considered in detail. 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 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 trees. Furthermore, the use of an ordered search of MIN/MAX trees brings about a rather provocative departure from the conventional approach to computer game playing. (Author)
Descriptors : (*SEARCH THEORY, MINIMAX TECHNIQUE), GAME THEORY, ARTIFICIAL INTELLIGENCE, GRAPHICS, ALGORITHMS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE