Statistical Feature Combination for the Evaluation of Game Positions

Michael Buro

TL;DR

This paper demonstrates that logistic regression is a superior method for weighting features in game-playing evaluation functions compared to traditional discriminant analysis. By applying "value adaptation"—training a model to predict the final game outcome from board features—the author developed LOGISTELLO, a world-class Othello program that outperformed versions using linear or quadratic discriminant functions.

What Problem Does This Paper Address?

In game-playing AI (like chess or Othello), programs use "evaluation functions" to estimate a player's winning chances in a given position. Historically, these functions were built by manually tuning weights for specific features (e.g., "how much is a corner worth in Othello?").

The author identifies two main issues with traditional approaches:

  1. Manual Labor: Hand-tuning weights is tedious and often inaccurate.
  2. Lack of Global Meaning: Many tuning methods (like "move adaptation," where the AI tries to mimic expert moves) don't produce a value that represents a true winning probability. This makes it difficult to compare positions from different phases of the game (e.g., comparing an opening move to a mid-game state).

The paper seeks a statistically sound way to combine features into a single value that represents the conditional winning probability $P(W | x)$.

Methods

The author compares three statistical models for "value adaptation":

  • Quadratic Discriminant Function (QDF): Assumes features are multivariate normally distributed. It creates a complex, non-linear boundary between "win" and "loss" states.
  • Fisher’s Linear Discriminant (FLD): A simplified version of QDF that assumes the "win" and "loss" classes share the same covariance matrix, resulting in a linear combination of features.
  • Logistic Regression (LR): Unlike the others, LR does not require features to be normally distributed. It uses a "logit" link function to map a linear combination of features to a probability between 0 and 1.

While QDF and FLD were known in the field, this paper marks the first time logistic regression was applied to game-playing evaluation functions.

Datasets

To train these models, the author needed a massive amount of labeled data with significant "feature variance" (meaning the data needed to include both good and bad positions).

  • The Games: Approximately 60,000 Othello games played over two years by early versions of the programs LOGISTELLO and REV.
  • The Positions: From these games, the author generated a dataset of 2.5 million classified positions.
  • Labeling: Positions were labeled based on the final game result. To improve accuracy, the author used "NegaMax propagation," where the result of a game was pushed back through the search tree to ensure the labels for earlier positions were more reliable.

Key Insights and Ideas

  • The Normality Trap: Traditional discriminant analysis (QDF/FLD) relies on the assumption that game features follow a bell curve (normal distribution). In reality, game features like "castling status" or "parity" are often discrete or highly skewed. Logistic regression succeeds because it is robust to these non-normal distributions.
  • Complexity vs. Speed: While quadratic functions (QDF) are mathematically more "flexible" than linear ones, they are computationally expensive. In game-tree search, speed is king. The paper found that the slight theoretical gain of a quadratic model was wiped out by the fact that the AI could search fewer nodes per second.
  • Value Comparability: By training the model to output a probability, the evaluation becomes "phase-independent." A 60% win probability in the opening can be directly compared to a 60% win probability in the endgame, which is crucial for advanced search techniques like selective extensions.

Key Results

The author ran tournaments between three versions of the program, each using a different statistical method:

  • LOG (Logistic Regression) vs. QUAD (Quadratic): LOG won decisively with a 61.8% winning percentage.
  • LOG vs. FISHER (Linear): LOG won with a 55.3% winning percentage.
  • Efficiency: Even when the weaker models (QUAD and FISHER) were given significantly more thinking time (up to 50% more), the Logistic Regression version (LOG) remained stronger.

The resulting program, LOGISTELLO, became a dominant force in the Othello community, winning 12 of the 14 international tournaments it entered around the time of publication.

Limitations and Future Work

  • Feature Engineering: The paper focuses on how to combine features, but the features themselves (like specific edge patterns) still had to be human-defined. The author suggests that future work could involve automatically discovering these sub-configurations.
  • Phase Dependency: While the meaning of the value is phase-independent, the author noted that the optimal weights still change as the game progresses (e.g., mobility matters more in the mid-game than the endgame). The paper addresses this by grouping positions by disc count, but more continuous transitions could be explored.
  • Non-Linearity: While quadratic terms didn't help here, the author acknowledges that other non-linear approaches (like Artificial Neural Networks) might be powerful if they can be made fast enough for real-time search.

Summary updated

Abstract

No abstract
BibTeX
@article{buro1996statistical,
  author = {Michael Buro},
  title = {{Statistical Feature Combination for the Evaluation of Game Positions}},
  journal = {J. Int. Comput. Games Assoc.},
  year = {1996},
  url = {https://openreview.net/forum?id=tSpMX7Pi4Q},
}

Loading related content...

Figure