Organizations: Department of Computer Science, National Yang Ming Chiao Tung University, Taiwan · Institute of Information Science, Academia Sinica, Taiwan · College of Computing, Georgia Institute of Technology
Reinforcement learning (RL) agents achieve remarkable performance but remain far less learning-efficient than humans. While RL agents require extensive self-play games to extract useful signals, humans often need only a few games, improving rapidly by repeatedly revisiting states where mistakes occurred. This idea, known as search control, aims to restart from valuable states rather than always from the initial state. In AlphaZero, prior work Go-Exploit applies this idea by sampling past states from self-play or search trees, but it treats all states equally, regardless of their learning potential. We propose Regret-Guided Search Control (RGSC), which extends AlphaZero with a regret network that learns to identify high-regret states, where the agent's evaluation diverges most from the actual outcome. These states are collected from both self-play trajectories and MCTS nodes, stored in a prioritized regret buffer, and reused as new starting positions. Across 9x9 Go, 10x10 Othello, and 11x11 Hex, RGSC outperforms AlphaZero and Go-Exploit by an average of 77 and 89 Elo, respectively. When training on a well-trained 9x9 Go model, RGSC further improves the win rate against KataGo from 69.3% to 78.2%, while both baselines show no improvement. These results demonstrate that RGSC provides an effective mechanism for search control, improving both efficiency and robustness of AlphaZero training. Our code is available at https://rlg.iis.sinica.edu.tw/papers/rgsc.
Figures & tables
Figure 1: Humans focus on correcting mistakes, whereas RL always starts from the initial state.
Figure 2: Overview of RGSC. The regret network selects high-regret states (red circles) from both self-play ( A ) or MTCS search node ( B ), which serve as restart points for further self-play. The newly generated trajectories can further branch out, e.g., state D originates from a restart at state C .
Figure 3: A toy example on n -level binary tree. (a) and (c) show the average rewards during the training, while (b) and (d) show the mean squared error (MSE) of the optimal Q-values during the training. The shaded area is a 95% confidence interval for the mean.
Figure 4: Playing performance of AlphaZero, Go-Exploit, and RGSC on three different board games. The shaded area is a 95% confidence interval for the mean.
AlphaZero
Go-Exploit
RGSC
9x9 Go
45.5% ± 1.5%
49.5% ± 2.0%
53.6% ± 2.4%
10x10 Othello
51.7% ± 2.5%
52.9% ± 3.3%
57.8% ± 3.2%
11x11 Hex
83.6% ± 1.6%
89.2% ± 1.8%
91.1% ± 2.0%
Table 1: Win rate against established open-source programs on three board games.
Figure 5: Playing performance of AlphaZero, Go-Exploit, and RGSC when continued from well-trained models. The shaded area is a 95% confidence interval for the mean.
Figure 6: Playing performance of RGSC using regret value network and regret ranking network. The shaded area is a 95% confidence interval for the mean.
Figure 7: The regret values for nodes selected by Go-Exploit, regret value and ranking network. The shaded area is a 95% confidence interval for the mean.
Figure 8: Regret distributions of states in the prioritized regret buffer at entry and before removal.
Appendix figures & tables15 assets
Supplementary material from the paper’s appendix.
Appendix
from scratch
from well-trained
Parameter
Go
Hex
Othello
Go
Board size
9
11
10
9
Optimizer
SGD
SGD
SGD
SGD
Optimizer: learning rate
0.02
0.02
0.02
0.001
Optimizer: momentum
0.9
0.9
0.9
0.9
Optimizer: weight decay
0.0001
0.0001
0.0001
0.0001
Appendix
Table 2: Hyperparameters for training from scratch ( subsection 4.2 ) and from well-trained model ( subsection 4.3 ).
# blocks
3
6
9
12
15
18
20
RGSC
139.5%
109.1%
105.4%
103.5%
102.7%
101.8%
101.9%
AlphaZero
100.0%
100.0%
100.0%
100.0%
100.0%
100.0%
100.0%
Appendix
Table 3: Forwarding time across different blocks of the network.
ID
Version
# blocks
Elo ratings
1
kata1-b6c96-s152505856-d23152636
6
9833.3 ± 16.1
2
kata1-b6c96-s165180416-d25130434
6
9900.6 ± 16.2
3
kata1-b6c96-s175395328-d26788732
6
9958.6 ± 16.9
4
kata1-b10c128-s41138688-d27396855
10
10138.6 ± 18.3
5
kata1-b15c192-s86740736-d72259836
15
11180.1 ± 16.1
Appendix
Table 4: The versions of the selected KataGo models for 9x9 Go.
Figure 9: Playing performance of different sampling probabilities ( λ ) across three games. The orange curve is the final RGSC setting.
Figure 10: Playing performance of different buffer sampling temperatures ( τ ) across three games. The orange curve is the final RGSC setting.
Figure 11: Playing performance of different buffer sizes ( κ ) across three games. The orange curve is the final RGSC setting.
Figure 12: Playing performance of different EMA coefficients ( α ) across three games. The orange curve is the final RGSC setting.
Figure 13: High-regret state examples. Blue triangles indicate the last moves.
Figure 14: Win rates of high-regret states during RGSC training.
Figure 15: Relationship between game outcomes and regrets during training.
Figure 16: Change in the proportion of openings with different lengths across training in 9×9 Go.
Figure 17: Change in the proportion of openings with different lengths across training in 10×10 Othello.
Figure 18: Change in the proportion of openings with different lengths across training in 11×11 Hex.
Figure 19: Changes in the values of openings from their first appearance to the final update during training.
Figure 20: Playing performance of MuZero, and RGSC on Ms. Pac-Man. The shaded area is a 95% confidence interval for the mean.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
AlphaZero has demonstrated that a neural-guided Monte Carlo Tree Search can achieve superhuman performance, but strong play does not necessarily imply perfect play. We study this gap in two oracle-evaluable domains with contrasting structure: Connect Four, a solved partisan game with exact game-theoretic values, and Chomp, an impartial game whose optimal play is governed by Grundy-number structure. Under a unified self-play + MCTS pipeline, we compare vanilla AlphaZero, a multi-frame variant (limited to Chomp), and an AlphaZero Auxiliary Loss (AZAL) that adds oracle-derived policy supervision. We find that vanilla AlphaZero achieves strong play across both domains but cannot preserve the exact trajectories required for optimal play: in Connect Four, it fails to maintain the optimal line of play, while in Chomp, it fails to consistently restore the g=0 invariant. On rectangular Chomp boards, multi-frame inputs alone do not remove this gap. Nevertheless, AZAL substantially improves oracle consistency across multi-seeded full-game traces and sampled-state evaluations. On Chomp, AZAL reaches perfect full-game oracle consistency on 10x11 and high but not complete consistency on 9x10; on Connect Four, AZAL improves oracle-match rate and delays the first oracle mistake, but does not reach perfect play.
Brent Kong, Tejas Ram, Tony Yue Yu
Department of Mathematics · California Institute of Technology · Department of Computer Science
Recent advancements in Computer Go, driven by AlphaZero and MuZero, rely heavily on Monte Carlo Tree Search (MCTS) to correct the errors of the neural network policy. While effective on massive computational clusters, this dependence creates a critical bottleneck on consumer-grade hardware, where the computational cost of tree management severely limits inference rates. Furthermore, without deep search, these models suffer from hallucination, proposing moves with high confidence that are strategically fatal. This paper introduces a novel Belief-Guided architecture that disentangles the Policy head from a distinct Belief head. Unlike traditional value functions, the Belief head acts as an internal simulator and independent critic, modeling epistemic uncertainty and strategic stability. By integrating memory mechanisms (Transformer/GRU) to handle long-term dependencies and the Ko rule, and utilizing a gating mechanism to filter overconfident policy errors, our model shifts the burden of intelligence from runtime search to parametric "intuition." Experimental results demonstrate that this approach significantly improves search-free win rates and reduces hallucination, enabling professional-level play on limited hardware where massive MCTS is infeasible.
Mehrad Yaghoubi, Azam Bastanfard, Abbas Jalilvand +1
Department of Computer Engineering, Ka.C, Islamic Azad University, Karaj, Iran
Imperfect-information games (IIGs) are challenging, as players must make decisions without fully observing the true game state. While AlphaZero has achieved remarkable success in perfect-information games, extending it to IIGs remains difficult. Existing search-based approaches, such as Perfect Information Monte Carlo (PIMC), suffer from strategy fusion, while Information Set Monte Carlo Tree Search (IS-MCTS) incurs high computational cost when combined with neural networks. In this paper, we propose Multi-State Aggregated PoLicy Evaluation (MAPLE), a tree search method that aggregates policy and value evaluations from multiple sampled world states within a single search tree, combining the advantages of PIMC and IS-MCTS while maintaining a controllable computational cost. We further incorporate a Siamese-based sampling strategy to select informative world states from the information set. Experiments on Phantom Go and Dark Hex show that MAPLE significantly outperforms the PIMC-based AlphaZero baseline, achieving Elo improvements of 291 and 136, respectively. These results demonstrate that MAPLE is an effective approach for AlphaZero-style learning in imperfect-information games.
Qian-Rong Li, Hung Guei, I-Chen Wu +1
Department of Computer Science, National Yang Ming Chiao Tung University, Taiwan · Institute of Information Science, Academia Sinica, Taiwan