Summary
Many smart game-playing computers use a method called Monte Carlo Tree Search (MCTS) combined with deep learning to get really good at games, but these methods can be slow and need a lot of computing power. This paper shows that a simpler method called Approximate Value Iteration (AVI) can learn game strategies that are just as good, or even better in some ways, while being faster and less costly. The authors tested AVI on several games like Connect Four and Hex, finding it produced accurate game evaluations and effective strategies without much overhead. Their results suggest that simpler approaches like AVI might be overlooked but can work well, especially with modern machine learning tools.
Approximate Value IterationMonte Carlo Tree SearchSelf-playFunction approximationGame playing AIValue functionConnect FourHexAlphaZeroDeep learning
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.