A Model of Two-Player Evaluation Functions

Bruce Abramson, Richard E. KorfAAAI 1987

Abstract

Traditional game-playing AI has long relied on heuristic evaluation functions designed by human experts to estimate the value of game states. This paper proposes a radical departure: the Expected-Outcome (EO) model. By defining the value of a position as its expected outcome under random play, the authors provide a domain-independent, mathematically rigorous framework for evaluating game states. Experimental results in Tic-Tac-Toe and Othello demonstrate that this model not only outperforms traditional expert-tuned heuristics but also allows for the automated learning of game strategies through regression analysis.

Introduction

In the early development of artificial intelligence, heuristic evaluation functions were often viewed as a "black art." While single-agent puzzles like the 15-puzzle have a clear metric—distance to the goal—two-player games present a more complex challenge. The standard approach was to approximate the minimax value, assuming perfect play from both sides. However, because the true minimax value is computationally unreachable for most games, developers relied on "vague" heuristics based on human intuition, such as piece counts or center control.

These ad-hoc functions are difficult to compare objectively and are heavily dependent on domain-specific expertise. This paper addresses these limitations by introducing the Expected-Outcome model, which shifts the focus from approximating perfect play to measuring the statistical strength of a position under random play.

The Expected-Outcome (EO) Model

The core of the EO model is the "Strong Position" hypothesis: a position that is advantageous for a perfect player is likely also advantageous for a random player. If a player holds a significant strategic lead, even a series of random moves is statistically likely to result in a win.

Mathematical Definition

The value of a game state is defined as the probability of winning if both players play randomly from that state until a terminal leaf is reached. Formally, the EO value is the sum of all possible terminal leaf values, each weighted by the probability of reaching that leaf under a uniform random move distribution. This provides an absolute standard for accuracy, allowing researchers to measure how closely any given heuristic correlates with the true expected outcome.

Methodology

Because game trees are too vast to calculate the exact EO value, the authors employed two primary techniques to make the model practical:

  1. Monte Carlo Estimation (Random Sampling): The EO value is estimated by conducting numerous random "playouts" from a specific position and averaging the results. This replaces the "horizon effect" of traditional search (uncertainty due to depth limits) with sampling error (uncertainty due to statistical variance).
  2. Regression Learning: To overcome the computational cost of real-time sampling, the authors used EO values as a "ground truth" dataset. They performed regression analysis to automatically determine the optimal weights for specific game features (e.g., board square values in Othello). This allowed the system to "learn" game strategies without human intervention.

Experimental Evaluation

The model was tested using Tic-Tac-Toe (3x3 and 4x4) and Othello (4x4, 6x6, and 8x8). The EO-based evaluators were compared against established expert heuristics, such as the "open-lines-advantage" in Tic-Tac-Toe and "weighted-squares" in Othello.

Key Results

  • Decision Accuracy: In Tic-Tac-Toe, where exact values could be verified, the EO model made only one-sixth as many errors as the standard expert evaluator.
  • Competitive Performance: In 8x8 Othello, a player using random sampling with no lookahead defeated a standard expert-designed evaluator with a dominant record of 48 wins to 2 losses.
  • Automated Weight Discovery: The coefficients discovered through regression analysis performed on par with those hand-tuned by human experts, proving that high-quality agents could be engineered automatically using the EO model as a guide.

Discussion and Limitations

While the EO model proved highly effective, the authors identified several constraints:

  • Computational Intensity: In 1987, the processing power required for random sampling was a significant bottleneck, sometimes requiring an hour for a single move. (Note: This approach laid the conceptual groundwork for modern Monte Carlo Tree Search, which is now standard in games like Go).
  • End-Game Sensitivity: The model is less reliable when the number of remaining moves is small. In the final stages of a game, the gap between random play and perfect play becomes more pronounced, potentially leading to errors.
  • Feature Selection: Although the model could learn the weights of features, the features themselves (e.g., which board positions to track) still required human definition.

Conclusion

The Expected-Outcome model provides a robust, domain-independent alternative to traditional heuristic design. By treating the remainder of a game as a random variable, it allows for the objective measurement of position strength and the automated acquisition of game-playing expertise. This shift from expert intuition to statistical sampling represents a foundational step toward modern simulation-based AI.

Summary updated

BibTeX
@inproceedings{abramson1987model,
  author = {Bruce Abramson and Richard E. Korf},
  title = {{A Model of Two-Player Evaluation Functions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure