Approximate value iteration achieves strong game play with less cost
The Surprising Effectiveness of Approximate Value Iteration in Self-Play
Artificial Intelligence
Summary
Playing games with computers often involves complex methods that are slow and require a lot of computing power. The authors show that a simpler approach called approximate value iteration can learn to play certain board games well, almost as well as fancy search methods, but faster and cheaper. They tested it on games like Connect Four and smaller versions of Go, finding it surprisingly effective. This suggests simpler methods might be a practical choice for game-playing AI than what is commonly used now.
What this means in practice
- •For game ai developers: Develop faster and less resource-intensive AI opponents for moderately sized board games using approximate value iteration instead of complex search techniques.
- •For reinforcement learning engineers: Implement simpler self-play training algorithms that reduce computational overhead while maintaining competitive performance in value estimation for sequential decision tasks.
Authors
Raphael Boige, Amine Boumaza, Bruno Scherrer
Abstract
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.