Catalogue of Artificial Intelligence Techniques
Keywords: evaluation function, games
Author(s): Maarten van Someren
A form of Heuristic Search that tries to find the cheapest path from the initial state to the goal. Its characteristic feature is the evaluation function. This is the sum of two components: the estimated minimum cost of a path from the initial state to the current state, and the estimated cost from the current state to the goal. The first component can be calculated if the Search Space is a tree, or it can be approximated by the cheapest known path if the search space is a graph. The second component must be defined, like any evaluation function, with respect to the domain. The heuristic power of this method depends on the properties of the evaluation function.
- Korf, R.E., Search: A Survey of Recent Results, Exploring Artificial Intelligence (Survey talks from the National Conferences on Artificial Intelligence)
, ed.), Morgan Kaufmann, San Mateo, California, 1988, pp.197--237 (Chapter 6).