Heuristic Evaluation Function

A heuristic evaluation function is a function that assigns an estimated numerical value to a state or search node, allowing an artificial intelligence system to compare alternatives without exploring every possible continuation. It embodies a heuristic: information that guides computation toward promising choices. The term is especially common in game-playing programs, where it estimates the strength of a position; closely related functions in pathfinding estimate the remaining cost of reaching a goal. These uses have different score conventions and mathematical requirements. (inst.eecs.berkeley.edu)

Evaluation in game playing

In a large game tree, examining every continuation until the game ends is usually computationally impractical. A depth-limited minimax search therefore stops at a specified depth and evaluates nonterminal positions using an approximation $E(s)$ to their true minimax values. For a designated maximizing player, higher scores represent more favorable positions. Terminal positions instead have utilities determined by the game’s outcome. (inst.eecs.berkeley.edu)

The distinction between evaluation and search is important: the evaluator estimates the value of a position, while the search algorithm propagates these estimates through possible moves to select an action. Alpha–beta pruning can avoid examining branches that cannot affect the minimax result, but it does not make approximate leaf evaluations exact. Consequently, depth-limited minimax generally loses the optimal-play guarantee available when the full tree is searched to terminal outcomes. (inst.eecs.berkeley.edu)

Feature-based and learned evaluators

A common handcrafted evaluator is a linear combination of numerical features:

E(s)=\sum_{i=1}^{k}w_i\phi_i(s),

where $\phi_i(s)$ describes some property of state $s$ , and $w_i$ determines its contribution. Feature engineering identifies relevant properties, while the weights encode their relative importance. For example, a simple checkers evaluator can count each side’s ordinary pieces and kings, assigning positive contributions to the maximizing player’s pieces and negative contributions to the opponent’s. Such a formula is an approximation, not a rule establishing a position’s true value. (inst.eecs.berkeley.edu)

Evaluation functions need not be linear or manually specified. Artificial neural networks can learn nonlinear position evaluations through machine learning. In the AlphaZero approach, a network produces both move probabilities and a scalar estimate of the expected game outcome. These quantities are learned through self-play reinforcement learning and used to guide search. The scalar output serves as a learned evaluation, whereas the move probabilities guide which actions the search explores. (arxiv.org)

Evaluation in pathfinding

For the shortest-path problem, a heuristic function $h(n)$ estimates the minimum remaining cost from node $n$ to a goal. Lower estimates are preferable, unlike the higher-is-better convention commonly used for game positions. Greedy best-first search prioritizes nodes using this remaining-cost estimate alone. (artint.info)

A* search distinguishes the heuristic estimate from the overall evaluation:

f(n)=g(n)+h(n),

where $g(n)$ is the cost of the particular path already found from the start to $n$ . Thus, $h(n)$ estimates the unfinished part of a solution, while $f(n)$ estimates the total cost of completing the current path. Calling both quantities “heuristic evaluation functions” can obscure this distinction. (artint.info)

Admissibility and consistency

Cost estimates can satisfy formal conditions that support optimal search:

Admissibility: under the usual nonnegative-cost convention, $0\leq h(n)\leq h^*(n)$ , where $h^*(n)$ is the actual minimum remaining cost. The heuristic never overestimates.
Consistency: for every transition from $n$ to $n'$ with cost $c(n,n')$ ,
$h(n)\leq c(n,n')+h(n'),$
with $h=0$ at goal nodes.

Consistency implies admissibility for nodes that can reach a goal and ensures that A* evaluation values do not decrease along a path. It supports graph-search implementations that permanently close expanded states; an admissible but inconsistent heuristic may require reopening states when cheaper paths are discovered. Optimality also depends on the search procedure and its termination conditions, not merely on the heuristic’s name. (inst.eecs.berkeley.edu)

These lower-bound conditions concern remaining-cost estimates. They are not normally requirements for a game-position evaluator, whose purpose is to approximate a position’s strategic value rather than bound the cost of reaching a goal. (inst.eecs.berkeley.edu)

Construction and computational trade-offs

Search heuristics can be constructed by solving a relaxed version of a problem in which some constraints are removed. Its optimal cost provides a lower bound on the original problem’s cost. If several heuristics are admissible, their pointwise maximum is also admissible and is at least as informative as each component. (inst.eecs.berkeley.edu)

An evaluator’s usefulness depends on both its information and its computational cost. A more informative admissible heuristic can reduce the number of paths A* expands, but the total expense also includes calculating that heuristic. In game search, more accurate evaluation and deeper lookahead can improve decisions, yet approximate evaluation remains a source of error. Evaluation quality therefore has to be considered together with the search method and available computational resources. (artint.info)

References

2 Minimax | Introduction to Artificial Intelligenceinst.eecs.berkeley.edu
6 Summary | Introduction to Artificial Intelligenceinst.eecs.berkeley.edu
CS 188 Introduction to Artificial Intelligence, Fall 2022, Note 5inst.eecs.berkeley.edu
6 Informed (Heuristic) Search — Artificial Intelligence: Foundations of Computational Agents, 3rd Editionartint.info
4 Informed Search | Introduction to Artificial Intelligenceinst.eecs.berkeley.edu
Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmarxiv.org