Proceedings of the AAAI Conference on Artificial Intelligence, 5
We present a characterization of heuristic evaluation functions which unifies their treatment in single-agent problems and two-person games. The central result is that a useful heuristic function is one which determines the outcome of a search and is invariant along a solution path. This local characterization of heuristics can be used to predict the effectiveness of given heuristics and to automatically learn useful heuristic functions for problems. In one experiment, a set of relative weights for the different chess pieces was automatically learned.