A Unified Theory of Heuristic Evaluation Functions and its Application to Learning

Jens Christensen, Richard E. KorfAAAI 1986

Introduction

Artificial intelligence research has traditionally distinguished between single-agent problem solving, such as the Fifteen Puzzle, and two-player adversarial games like Chess. In the former, heuristics typically estimate the remaining cost to a goal (e.g., Manhattan distance). In the latter, heuristics serve as a proxy for "board strength." This paper, originally presented at AAAI-86, proposes a unified theoretical framework to bridge these domains, defining the properties of a "perfect" heuristic and demonstrating how these properties can be leveraged for automated learning.

The Unified Theory: Outcome Determination and Move Invariance

The authors argue that the discrepancy between heuristic types leads to performance anomalies. For instance, the Manhattan distance is highly effective for the Fifteen Puzzle but fails for Rubik’s Cube. To resolve this, they define a perfect heuristic through two core principles:

  1. Outcome Determination: At any terminal or goal state, the evaluation function must return the exact true value (the final payoff or cost).
  2. Move Invariance: Along an optimal solution path, the value of the evaluation function should remain constant.

In the context of A* search, where $f(n) = g(n) + h(n)$, the function $f(n)$ is move-invariant along an optimal path: as the cost-to-date ($g$) increases, the estimated cost-to-go ($h$) decreases by an equal amount. This unification allows the same mathematical rigor applied to pathfinding to be applied to game-playing heuristics.

Learning Heuristics through Iterative Regression

The principle of move invariance provides a powerful signal for machine learning. If a heuristic is perfect, its value at a state should match its value at a successor state on the optimal path. Assuming that a deeper look-ahead search provides a more accurate estimate than a shallow static evaluation, the authors developed an iterative learning algorithm:

  • Search and Backup: Perform a minimax search to a fixed depth and use the minimax algorithm to back up values from the search frontier to the current state.
  • Weight Adjustment: Treat the backed-up value as a target and the current state's features (e.g., piece counts) as independent variables.
  • Linear Regression: Use linear regression to update feature weights so that the static evaluation better predicts the backed-up value.
  • Convergence: Repeat the process until the weights stabilize.

Experimental Results in Chess

The most striking application of this theory was in the domain of Chess. Starting with no prior knowledge of piece values, the system played games against itself to generate training data. Through iterative regression, the algorithm "discovered" the relative values of chess pieces:

Piece Learned Weight Classical Value
Queen 8.0 9
Rook 4.0 5
Bishop 4.0 3
Knight 3.0 3
Pawn 2.0 1

While not identical to the centuries-old "classical" weights taught to beginners, the learned values are remarkably similar. In a 100-game test match, the learned evaluation function proved competitive against the classical weights, securing 17 wins and 67 draws against 16 losses.

Discussion and Limitations

The study highlights the "Continuity Principle": successful heuristics are essentially continuous over the state space. High variance over a single move—as seen with Manhattan distance in Rubik's Cube—indicates a failure to capture the local structure of the problem.

However, the authors note several limitations. The iterative regression is a form of hill-climbing and can become trapped in local maxima. Furthermore, the model assumes a linear combination of features, whereas high-level play likely requires non-linear evaluations. Finally, the weights were static, ignoring the fact that piece values often shift during different phases of a game (e.g., the increased power of rooks in the endgame).

Despite these constraints, the paper provides a robust theoretical foundation for understanding heuristics and a practical method for learning them without human expertise.

Summary updated

BibTeX
@inproceedings{christensen1986unified,
  author = {Jens Christensen and Richard E. Korf},
  title = {{A Unified Theory of Heuristic Evaluation Functions and its Application to Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}

Loading related content...

Figure