Statistical Feature Combination for the Evaluation of Game Positions

Michael Buro

Abstract

This article describes an application of three well-known statistical methods in the field of game-tree search: using a large number of classified Othello positions, feature weights for evaluation functions with a game-phase-independent meaning are estimated by means of logistic regression, Fisher's linear discriminant, and the quadratic discriminant function for normally distributed features. Thereafter, the playing strengths are compared by means of tournaments between the resulting versions of a world-class Othello program. In this application, logistic regression—which is used here for the first time in the context of game playing—leads to better results than the other approaches.

Introduction

In the domain of game-playing artificial intelligence, the evaluation function serves as the critical heuristic that guides search algorithms through the game tree. For games like Othello, these functions estimate the strength of a given board position to determine the most promising moves. Historically, these functions were constructed by manually assigning weights to specific features, such as corner occupancy or mobility. However, manual tuning is both labor-intensive and prone to inaccuracies.

Furthermore, traditional methods often lack a "global meaning." If an evaluation function is tuned via "move adaptation" (mimicking expert moves), the resulting values do not necessarily represent a true winning probability. This makes it difficult to compare positions across different phases of the game. This paper addresses these challenges by applying statistical "value adaptation" to develop an evaluation function that outputs a reliable conditional winning probability $P(W | x)$.

Statistical Methodology

The research compares three distinct statistical models to determine the optimal combination of game features:

  1. Quadratic Discriminant Function (QDF): This model assumes that features follow a multivariate normal distribution. It creates a non-linear decision boundary between winning and losing states, offering high mathematical flexibility at the cost of increased computational complexity.
  2. Fisher’s Linear Discriminant (FLD): A simplification of QDF, FLD assumes that both "win" and "loss" classes share the same covariance matrix. This results in a linear combination of features, which is faster to compute but potentially less expressive.
  3. Logistic Regression (LR): Applied here for the first time in game-playing AI, LR does not require features to be normally distributed. It utilizes a "logit" link function to map a linear combination of features directly to a probability between 0 and 1.

Data Acquisition and Labeling

Training these models required a massive dataset with high feature variance to ensure the models could distinguish between subtle positional advantages. The author utilized approximately 60,000 Othello games played by early versions of the programs LOGISTELLO and REV.

From these games, a dataset of 2.5 million classified positions was generated. To ensure the labels (win or loss) were accurate for early and mid-game positions, the author employed "NegaMax propagation." This technique pushes the final game result back through the search tree, providing more reliable ground-truth labels for positions encountered long before the game's conclusion.

Key Insights: The Superiority of Logistic Regression

The study revealed several critical insights into why certain statistical methods outperform others in a game-tree context:

  • Robustness to Non-Normality: Traditional discriminant analysis (QDF and FLD) relies on the assumption that features follow a bell curve. In Othello, many features (such as parity or specific edge configurations) are discrete or highly skewed. Logistic regression is far more robust to these distributions, leading to more accurate probability estimations.
  • The Speed-Complexity Trade-off: While QDF is theoretically more flexible due to its quadratic terms, it is computationally expensive. In competitive game-tree search, the number of nodes evaluated per second is a primary driver of strength. The slight theoretical accuracy gain of QDF was consistently negated by the reduction in search depth it caused.
  • Phase-Independent Evaluation: By training the model to output a probability, the evaluation becomes comparable across the entire game. A 60% win probability in the opening carries the same weight as a 60% probability in the endgame, which is essential for advanced search techniques like selective extensions.

Experimental Results and Impact

To validate these methods, the author conducted tournaments between versions of the program using different statistical engines. The Logistic Regression version (LOG) demonstrated clear superiority:

  • LOG vs. QUAD: LOG won decisively with a 61.8% winning percentage.
  • LOG vs. FISHER: LOG maintained a significant lead with a 55.3% winning percentage.
  • Efficiency: Even when the QUAD and FISHER versions were granted 50% more thinking time, the LR-based version remained the stronger player.

The resulting program, LOGISTELLO, became a dominant force in the Othello community. During the period surrounding the publication, it won 12 of the 14 international tournaments it entered, proving that statistically sound feature combination is a powerful alternative to manual heuristic tuning.

Conclusion and Future Directions

While this work revolutionized feature weighting, it still relied on human-defined features. The author notes that future improvements could involve the automated discovery of sub-configurations. Additionally, while the meaning of the output is phase-independent, the optimal weights for features like mobility still shift as the game progresses. Future research may look into continuous weight transitions or more complex non-linear models, such as neural networks, provided they can meet the rigorous speed requirements of real-time game-tree search.

Summary updated

Abstract

This article describes an application of three well-known statistical methods in the field of game-tree search: using a large number of classified Othello positions, feature weights for evaluation functions with a game-phase-independent meaning are estimated by means of logistic regression, Fisher's linear discriminant, and the quadratic discriminant function for normally distributed features. Thereafter, the playing strengths are compared by means of tournaments between the resulting versions of a world-class Othello program. In this application, logistic regression - which is used here for the first time in the context of game playing - leads to better results than the other approaches.
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},
}
Figure