Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The authors benchmark a minimal self-play implementation of Approximate Value Iteration (AVI) against AlphaZero across Connect Four, Hex(7x7), Othello, and 9x9 Go, using ground-truth game oracles to measure value function precision directly. While Monte Carlo Tree Search (MCTS) has become the de facto standard for competitive self-play, its heavy compute footprint at both training and inference time poses significant scaling challenges. Surprisingly, AVI learns more accurate value functions than AlphaZero, and its simple one-step-lookahead greedy policy matches MCTS-based performance at a fraction of the computational budget.
Tree search might be computational overkill in self-play: a minimal Approximate Value Iteration baseline learns more accurate value functions than AlphaZero while matching competitive play with just one-step lookahead.
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.