Abstract
Monte Carlo (MC) methods in game-playing algorithms rely heavily on the quality of simulation policies. Traditional tuning methods often require computationally expensive ground-truth evaluations. This paper presents "Simulation Adjusting," a gradient descent-based approach that utilizes expert moves as a learning signal. By minimizing the discrepancy between the winning rates of the policy's preferred move and the expert's move, the method improves simulation accuracy. Experiments on $4 \times 4$ Go problems demonstrate that this approach effectively reduces the objective function and outperforms standard Minorization-Maximization (MM) baselines, even with limited training data.
Introduction
In complex games like Go, Monte Carlo Tree Search (MCTS) uses "playouts"—simulated games from a given state to the end—to estimate move values. The reliability of these estimates is directly tied to the quality of the simulation policy. Poor policies lead to inaccurate evaluations and suboptimal play.
Existing policy refinement techniques, such as simulation balancing, typically require "ground truth" signals, such as minimax values or deep-search results. However, obtaining these values is computationally prohibitive for large-scale applications. This paper proposes a novel "Simulation Adjusting" method that leverages expert game records. Since expert moves are readily available, they serve as a practical proxy for ground truth, allowing for more efficient policy training.
Methodology
The proposed method adjusts the weights ($\theta$) of a softmax simulation policy using a gradient descent framework.
- Objective Function: The core objective $J(\theta)$ is to minimize the squared difference between the winning rate of the move selected by the current policy ($a^{max}$) and the winning rate of the "correct" or "teacher" move ($a^*$).
- Gradient Descent: The authors derive the gradient $\nabla_\theta J(\theta)$ based on expected game outcomes ($z$) and feature vectors ($\psi$) encountered during simulations.
- Learning Algorithm: For each training position, the algorithm performs multiple simulations to estimate winning rates ($V$) for all legal moves. It identifies the discrepancy between the policy's best move and the teacher's move, then updates $\theta$ with a decaying step size $\alpha$ to ensure convergence.
- Feature Set: The policy incorporates local $3 \times 3$ patterns, spatial distance to previous moves, and tactical Go concepts such as atari (immediate capture threat), nakade (internal eye-space shapes), and semeai (capturing races).
Experimental Setup
The method was evaluated using the "Kuroneko-no Yonro" dataset, consisting of $4 \times 4$ Go problems with unique, known correct moves.
- Training Set: 60 problems used for weight adjustment.
- Test Set: 10 problems used for "open testing" to evaluate generalization to unseen positions.
Results and Discussion
The experimental results confirm the efficacy of the Simulation Adjusting approach. The objective function for the closed test (training data) showed a steady decline, indicating that the algorithm successfully learned to align its evaluations with the teacher moves.
As shown in the figure above, the number of Correct Answers (CA) on the open test set increased significantly during the initial learning loops. Notably, the proposed method achieved a higher CA rate than the Minorization-Maximization (MM) method, which was a standard move-prediction baseline at the time. Most of the performance gains were realized within the first 10 iterations, suggesting that the method rapidly identifies critical features.
However, the results also exhibited oscillation in accuracy on the test set after the initial improvement phase. This suggests potential overfitting to the small training set or a need for more sophisticated step-size scheduling to stabilize convergence.
Conclusion
Simulation Adjusting provides a viable path for improving Monte Carlo simulation policies without the need for expensive minimax evaluations. By bridging the gap between simulation balancing and move prediction, the method achieves superior accuracy on small-board Go problems. Future work will focus on scaling the approach to $9 \times 9$ and $19 \times 19$ boards, increasing training dataset sizes, and optimizing hyperparameters to mitigate oscillation and improve stability.
Summary updated