Difference between heuristic function and evaluation function

Question

I'm reading about searching algorithms and heuristic search and I am slightly confused about heuristic and evaluation functions. People seem to use them quite freely to describe seemingly same things. What am I missing?

Answer 1

An evaluation function (or score function) checks if a solution is feasible and how good it is. By comparing the score of 2 solutions, you can see which one is better (if they are both feasible). For example: if you go from Brussels to Madrid through Paris, Lyon and Marseille the distance is 1000 km (= the actual road distance).

A heuristic function also returns something like a score, but it works on a partial solution and it doesn't need to be accurate. For A* search it needs to be admissible (= underestimating). For example: If you go from Brussels to Madrid through Paris (and the rest you don't know yet), the distance is 800km (= the actual road distance from Brussels to Paris plus the as-the-crow-flighs distance from Paris to Madrid).

Answer 2

There can be confusion around this issue because heuristics mean different things in different contexts. So, let me talk about the different meaning of heuristics. Then we can return to evaluation functions.

Single Agent Heuristic Search

In single-agent heuristic search (eg A*, IDA*) heuristics are usually qualified with the words admissible or consistent. In this context heuristics are lower bounds on the cost to reach the goal. That is, they are the result of a function which returns a numerical value. If the heuristic is admissible, the value returned does not overestimate the true distance to the goal. If the heuristic is consistent, the heuristic between adjacent states never changes more than the edge cost. Consistent heuristics are admissible if the goal has a heuristic of 0, but not all admissible heuristics are consistent.

There are many properties proven on the combinations of heuristics and algorithms. A* and IDA* will find optimal paths with a consistent heuristic. A* is optimal in necessary node expansions with a consistent heuristic, but with a inconsistent heuristic A* can perform 2^N expansions of N states. (See this demo for an example of where this occurs.)

Game Playing

In game playing programs using algorithms like alpha-beta or Monte Carlo tree search (MCTS), heuristics represent approximations of the win/loss value of a game. For instance, the value might be scaled between -1 (loss) and +1 (win), with values in between representing uncertainty about the true value. Here there are no guarantees on underestimate or overestimation, but the better ordering of values (wins > draws > losses) the better the performance of the algorithms. Alpha-beta pruning will return the same result even if an affine transform is applied to the heuristic, because alpha-beta uses the relative ordering of values to search. See, this paper for an example of heuristics in MCTS. Note that in this context a heuristic still has a numerical value.

Optimization

In search for optimization problems like SAT (satisfiability problems) or CSP (constraint satisfaction problems), algorithms are much more efficient if they can find good solutions quickly. Thus, instead of searching in a naive manner, they order their search in a way that is expected to be more efficient. If the ordering is good the search might be able to terminate earlier, but this isn't guaranteed. In this context a heuristic is a way of ordering choices that is likely to end up with finding a solution more quickly. (A satisfying assignment of variables in SAT or in a CSP.) Here is an example of work that explores different ordering heuristics for these problems.

In this context a heuristic is used for ordering, so it doesn't have to be numerically based. If it is numerically based, the numbers would not necessarily have global meaning as heuristics do in other types of search. There are many, many variants of optimizations problems besides SAT and CSP where heuristics are used in this manner.

Evaluation Function

So, then, what is an evaluation function? It is probably most commonly used in the second context of games, where heuristic and evaluation function can be interchanged, but it is more generally referring to the numerical evaluation of a state. The primary point would be that an evaluation function is more specific than a heuristic function, as a heuristic has broad use in wider contexts.