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:
- Manual Labor: Hand-tuning weights is tedious and often inaccurate.
- 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