# The Surprising Effectiveness of Approximate Value Iteration in Self-Play

arXiv: https://arxiv.org/abs/2609.09094 · HTML: https://mlsanity.com/paper/2609.09094/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 25 references that are in the map.
- First posted on arXiv 8 Sep 2026.

## Builds on (most cited first, 7 of 7)

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Monte-Carlo Tree Search as Regularized Policy Optimization](https://mlsanity.com/paper/2007.12509/) (2020)
- [Pgx: Hardware-Accelerated Parallel Game Simulators for Reinforcement Learning](https://mlsanity.com/paper/2303.17503/) (2023)
- [MiniZero: Comparative Analysis of AlphaZero and MuZero on Go, Othello, and Atari Games](https://mlsanity.com/paper/2310.11305/) (2023)
- [Learning to Play Two-Player Perfect-Information Games without Knowledge](https://mlsanity.com/paper/2008.01188/) (2020)
- [Minimax Strikes Back](https://mlsanity.com/paper/2012.10700/) (2020)
- [Doubly-Asynchronous Value Iteration: Making Value Iteration Asynchronous in Actions](https://mlsanity.com/paper/2207.01613/) (2022)

## Abstract (arXiv)

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.