Abstract
In computer game-playing, traditional training methods focus on "mimicking the experts," but high imitation accuracy does not always translate to maximum playing strength. This paper introduces a meta-optimization technique that tunes the parameters of the learning objective function itself to maximize actual playing strength (Elo rating) rather than just move-prediction accuracy. By employing a two-level optimization framework, the authors demonstrate significant strength gains in Shogi programs, particularly by accounting for the differing characteristics of game phases. The resulting programs achieved a 61.5% win rate against the state-of-the-art engine BONANZA 6.0.
Introduction
Most state-of-the-art game engines, such as those for Shogi or Chess, utilize "comparison training" to develop evaluation functions. This process involves adjusting internal weights so the engine's preferred moves align with those found in expert game records. However, a fundamental "mimicry gap" exists: high agreement with experts does not strictly correlate with playing strength. A program might mimic an expert 90% of the time but make catastrophic blunders in the remaining 10%.
Furthermore, standard objective functions typically use fixed parameters—such as the slope of a sigmoid function—that are tuned manually. These fixed values fail to account for the varying characteristics of different game phases. For instance, a "good enough" move in the opening might be acceptable, whereas a slight inaccuracy in the endgame is often fatal. This research addresses these limitations by optimizing the objective function parameters dynamically.
Methodology
The authors propose a two-level optimization framework designed to bridge the gap between imitation and strength:
- The Lower Level (Evaluation Learning): A standard gradient descent method trains the evaluation function parameters ($v$) using a specific objective function.
- The Upper Level (Objective Function Optimization): An evolutionary algorithm called Continuous Population-Based Incremental Learning (PBILc) is used to optimize the parameters of the objective function itself.
Context-Aware Weighting
Instead of global constants, the system categorizes training positions based on three key metrics to provide context-aware weighting:
- Progress Ratio: The stage of the game (opening vs. endgame).
- Best-move Change: The "instability" of a position, measured by how often the best move changes as search depth increases.
- Correct Depth: The search depth required to identify the expert's move.
The "fitness" score for the evolutionary algorithm was the actual Elo rating of the resulting program, estimated by conducting 4,000 games per individual in the population.
Key Insights and Results
The optimization process revealed a critical "Aha" moment regarding endgames. As the game progresses (indicated by a higher Progress Ratio), the objective function must become more sensitive to value differences. In the endgame, moves are often binary—leading directly to a win or a loss—so the learning process must emphasize the margin between the correct move and alternatives more heavily than in the opening.
Performance Metrics
- Superiority over Baselines: The proposed method achieved a 61.9% win rate against a program trained with standard comparison training.
- Beating the State-of-the-Art: When tested against BONANZA 6.0 (at 12,000 nodes/move), the proposed method achieved a 61.5% win rate, whereas the standard comparison training baseline only managed 49.7%.
- Meta-Learning Reusability: Interestingly, an objective function optimized for one set of features remained effective even when the underlying features of the evaluation function were changed. This suggests the optimization captured fundamental properties of game-playing strength.
Conclusion and Future Work
This study demonstrates that optimizing the objective function for strength rather than imitation leads to significantly more robust game-playing agents. While the computational intensity of estimating Elo for every individual in an evolutionary population is high (requiring approximately 10 days of computation in this study), the results justify the investment.
Future work may involve automating the definition of contextual categories using neural networks and extending this meta-optimization framework to Monte Carlo Tree Search (MCTS) engines to optimize simulation policies in games like Go.
Summary updated