The Surprising Effectiveness of Approximate Value Iteration in Self-Play
Minimal approximate value iteration self-play learns more accurate value functions than AlphaZero in Connect Four and Hex while cutting training and inference costs.
The paper trains a minimal self-play implementation of Approximate Value Iteration (AVI) without MCTS and uses ground-truth oracles for exact evaluation in Connect Four, 7x7 Hex, and synthetic games. AVI learns more accurate value functions than AlphaZero, and its one-step-lookahead greedy policies remain competitive with MCTS-based policies at substantially lower training and inference cost. Preliminary experiments on Othello and 9x9 Go show AVI trains stably on larger games, suggesting simpler approaches have become increasingly practical with modern deep-learning tools.
- AVI outperforms AlphaZero on value-function accuracy in moderate-sized games.
- One-step greedy policies stay competitive with MCTS at much lower cost.
- Stable training shown on Othello and 9x9 Go in preliminary tests.
Full article160 words · extracted from arxiv.org · click to collapse
Combining search with function approximation has driven major advances in game-playing programs, making self-play algorithms more competitive than ever. Still, the computational overhead of the most popular methods, based on Monte Carlo Tree Search (MCTS), can be substantial. In this work, we investigate whether simpler methods remain competitive in non-trivial, moderately sized games such as Connect Four, Hex(7x7) and synthetic games. We train a minimal self-play implementation of Approximate Value Iteration (AVI) and use ground-truth oracles for exact evaluation. Contrary to expectations, our results demonstrate the surprising effectiveness of AVI: it learns more accurate value functions than those learned by AlphaZero, while its one-step-lookahead greedy policies remain competitive with MCTS-based policies at substantially lower training and inference costs. Preliminary experiments on Othello and Go(9x9) show that AVI trains stably on larger games and learns effective value functions. These findings suggest that the success of MCTS-based methods may have eclipsed simpler approaches that have become increasingly practical with modern deep-learning tools.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.09094