Some Theoretical Results Concerning Automated Game-Playing

T. Brian BoffeyIJCAI 1973

Abstract

This paper establishes a formal mathematical bridge between the decision-making processes of game-playing agents and the evaluation functions that guide them. By employing graph theory and inductive proofs, the author demonstrates that any consistent set of move preferences (a decision rule) can be represented by a numerical evaluation function. This work provides a theoretical foundation for the heuristic search methods prevalent in early artificial intelligence, extending these proofs to both deterministic game trees and probabilistic models of human-like variability.

Introduction

In the formative years of artificial intelligence, programs designed for games such as chess or checkers relied heavily on evaluation functions (EFs). These mathematical formulas assign scores to game states to determine the optimal move. However, these functions were often constructed ad-hoc for specific domains. T.B. Boffey identifies a critical theoretical gap: the lack of a formal proof that a player's complex decision-making process can always be captured by a simple numerical evaluation. The central question of this research is whether a mathematical evaluation function can always be found to reproduce the observed choices of a master player.

Theoretical Framework and Methods

The paper models games as directed graphs $(X, P)$ or rooted trees $(V, T)$, where vertices represent game states and arcs represent possible moves. To bridge the gap between decisions and evaluations, the author utilizes several key formalisms:

  • Minimax Extension: The standard minimax procedure is formalized to extend terminal payoffs (win, loss, or draw) back up the tree, assigning values to non-terminal states.
  • Preference Pairs: A formal notation $\sigma = (\sigma_M, \sigma_N)$ is introduced to represent the moves chosen by players (MAX or MIN) in any given position.
  • Lookahead Depth: The paper links the depth of a search ($d$-depth) to the reproduction of a decision rule, showing how an EF used with lookahead can mimic a specific strategy.

The Equivalence of Decisions and Evaluations

The core insight of the paper is the "Equivalence Principle." The author proves that a decision rule and an evaluation function are essentially two sides of the same coin. Theorem 3.1.3 states that for any constant decision rule on a game tree, there exists an evaluation function $f^d$ that perfectly reproduces that rule. This provides a rigorous definition of "better": a position $x$ is mathematically better than $y$ if $f(x) > f(y)$, and this mathematical ranking aligns with a player's actual choices under specific conditions.

Modeling Variability with Probabilistic Evaluation Functions

To account for players who do not always make the same move in identical situations—such as human players or stochastic agents—the author introduces Probabilistic Evaluation Functions (PEFs). Instead of a single scalar value, a PEF assigns a probability distribution of values to a position.

Mathematical definition of a Probabilistic Evaluation Function (PEF) distribution.

As shown in the formal definition above, a PEF can be modeled such that the probability $p(x, r)$ of a position $x$ having a value $r$ is defined over a specific interval. Theorem 3.2.2 extends the equivalence principle to this realm, proving that for variable decision rules on a tree, there exists a PEF that reproduces the observed strategy. This shows that even "human-like" variability can be formally mapped back to an underlying probabilistic evaluation framework.

Discussion and Limitations

While the paper provides robust proofs for game trees, it acknowledges significant hurdles in practical application and general graph structures:

  • Computational Feasibility: Although these functions are proven to exist, calculating them for complex games like chess is computationally impossible. The author estimates the chess game tree at $10^{40}$ positions, far exceeding the capacity of contemporary (and many modern) systems.
  • Graph Complexity: Results for general game graphs, where positions can repeat (cycles), are more complex. The existence of an EF in these cases depends heavily on the geometry of the graph and the consistency of paths.
  • Static vs. Dynamic Rules: The proofs assume decision rules are either constant or follow a fixed probability. The paper does not address how these rules might evolve through learning, a concept that has since become the cornerstone of modern reinforcement learning.

Conclusion

By formalizing the relationship between how an agent decides and how it evaluates, Boffey provides a rigorous justification for the use of heuristic evaluation functions in AI. While the computational limits of the era restricted the direct application of these theorems to complex games, the work remains a foundational piece in the theoretical study of automated game-playing.

Summary updated

BibTeX
@inproceedings{boffey1973some,
  author = {T. Brian Boffey},
  title = {{Some Theoretical Results Concerning Automated Game-Playing}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1973},
}
Figure