Source-linked AI summary
The Surprising Effectiveness of Approximate Value Iteration in Self-Play
Raphael Boige, Amine Boumaza, Bruno Scherrer
TL;DR
MCTS-based self-play is effective but computationally expensive, motivating a test of whether simpler value learning remains competitive. The paper evaluates minimal self-play AVI with exact oracles and larger-game benchmarks, finding more accurate values than AlphaZero, competitive greedy policies at lower cost, and stable training on larger games.
Problem
MCTS-based self-play incurs substantial computational and engineering costs, while standard Elo and head-to-head evaluations provide little absolute information about learned value quality.
Method
The paper trains minimal AVI with self-play and evaluates it against AlphaZero using exact oracles on solved games, supplemented by MiniZero comparisons on larger games.
Results
AVI learns substantially more accurate value functions than the AlphaZero baseline, while its greedy policies remain competitive at lower cost and its values improve MiniZero’s MCTS strength.
Takeaways & Limitations
Direct value learning can remain effective and stable across non-trivial games, while learned values can still support richer search-based action selection.
Takeaways & Limitations
The strongest conclusions rely on exact evaluation for Connect Four, Hex(7x7), and F-Games; larger-game results use only a fixed MiniZero baseline, and Go(19x19) and Chess were not tested.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper revisits simple Approximate Value Iteration as a lower-cost alternative to MCTS-based self-play, evaluating it with exact oracles and larger-game benchmarks. AVI learns highly accurate values, remains competitive for greedy decisions, and can strengthen deeper search.
- MCTS-based self-play is powerful but costly because it requires many neural-network calls and complex interactions among search, policy learning, and value learning.
- AVI trains stably across domains and random seeds despite combining function approximation, bootstrapping, and off-policy learning.The experiments examine value accuracy, decision quality, and the limits of AVI’s exploration and inference mechanisms.
- The study compares AVI and AlphaZero on solved games using value error, policy regret, oracle play, and computational cost.The evaluated games are Connect Four, Hex(7x7), and synthetic F-Games.
- AVI learns substantially more accurate value functions than the AlphaZero baseline, while its one-step-lookahead policies remain competitive at substantially lower cost.
- On Othello and Go(9x9), AVI again trains stably and improves MiniZero’s playing strength when inserted into the same MCTS inference procedure.
- Accurate AVI values can guide stronger deeper search, while advanced inference such as MCTS remains valuable for converting values into strong decisions.
2 Related Work
The related work connects modern MCTS-based self-play to earlier value-learning and approximate dynamic-programming approaches. This paper studies a particularly elementary one-step negamax value-learning method within that broader lineage.
- AlphaZero and later methods established MCTS-based policy improvement as a central structure for neural self-play.
- Earlier systems learned values directly or combined learned values with game-tree search, including master-level Chess with linear function approximation.
- Approximate dynamic programming frames value iteration and policy iteration as endpoints of approximate modified policy iteration, with extensions to two-player zero-sum Markov games.
- Against this background, the paper investigates a more elementary approach based on one-step negamax backups.
3 Problem Formulation and Algorithms
The paper formulates alternating zero-sum games with negamax values and derives exact and approximate value-iteration procedures. AVI replaces exhaustive state updates with sampled self-play data, replay-buffer regression, and a neural value function, while AlphaZero supplies the comparison baseline.
- 3.1 Alternating Two-Player Zero-Sum Games: In alternating zero-sum games, values and rewards are expressed from the player-to-move perspective, so one negamax equation replaces separate maximization and minimization equations.
- 3.1 Alternating Two-Player Zero-Sum Games: For any value estimate, the one-step-lookahead policy selects actions using immediate reward and the discounted successor value.
- 3.2 Value Iteration in Games: Value Iteration repeatedly applies the optimality operator to every state, recovering exact values within at most h iterations in a game of horizon h.
- 3.2 Value Iteration in Games: Exact Value Iteration is computationally infeasible in large state spaces because each iteration updates every state and enumerates all legal actions.
- 3.3 Approximate Value Iteration: AVI replaces tabular values and exhaustive updates with a neural function approximator trained by regression on sampled states and one-step negamax targets.
- 3.3 Approximate Value Iteration: ϵ-greedy self-play generates state-target data, retains it in a circular replay buffer, and alternates fixed-network collection with optimization.
- 3.4 AlphaZero Baseline: The AlphaZero baseline predicts both values and policies, uses MCTS visit counts for policy targets, and uses episode outcomes as value targets.
4 Experimental Setup
The study evaluates AVI across solved games with exact oracles and larger games without exact optimality references, using complementary measures of value accuracy, decision quality, and complete-game behavior. It also standardizes implementations, comparisons, datasets, and compute accounting to compare AVI with AlphaZero and MiniZero.
- Games and evaluation regimes: The primary regime uses Connect Four, Hex(7x7), and synthetic F-Games with exact values or optimal actions, while Othello and Go(9x9) are evaluated against MiniZero.The oracle-based games permit independent evaluation of learned values and decisions; the larger games test stability and usefulness at scale without absolute optimality measures.
- Oracle-based metrics: Exact oracles support three evaluations: value estimates, immediate decisions, and complete-game behavior against a perfect solver.The protocol measures value error, policy regret, and outcomes from fixed openings; oracle play is stricter because the opponent exploits consequential mistakes.
- Oracle-based metrics: The study reports mean absolute value error against ground truth and policy regret for the one-step-lookahead policy induced by AVI’s value function.AVI does not learn an explicit policy, so the evaluation uses G(Vθ) unless otherwise specified.
- Oracle-based metrics: Complete games against the oracle measure the fraction of openings where the agent achieves a worse outcome than the theoretical value, with Connect Four also reporting blunder rate.Each opening is played twice with exchanged player roles when no oracle is available, producing a score in [−1, 1].
- Match-based evaluation: Direct comparisons use greedy AVI actions versus MCTS actions from AlphaZero or MiniZero under the stated simulation budgets.Cross-inference keeps the learned policy prior and simulation count fixed while replacing the leaf evaluator with AVI’s value function, but requires two backbone evaluations.
- Implementation and compute: AVI and AlphaZero share environments, replay buffers, optimization code, and neural-network backbones, while training rows and optimization budgets are matched on Connect Four and Hex(7x7).Because AVI evaluates every one-step successor and AlphaZero performs S tree simulations, compute is reported with a forward-equivalent proxy, Nforward + 3Nbackward.
5 Results
Across exact-evaluation games and larger domains, AVI learns accurate values stably, supports competitive decisions, and can improve deeper search at lower inference cost. Its main boundary is that greedy inference remains weaker in complex games, while exact-oracle evaluation limits the breadth of conclusions.
- Accurate Values and Competitive Policies under Exact Evaluation: AVI trains stably and achieves lower value error than AlphaZero in Connect Four and Hex(7x7), with the gap growing during training.Even AlphaZero at its largest search budget retains higher value error, while AVI shows no divergence across 20 runs.
- Accurate Values and Competitive Policies under Exact Evaluation: Greedy AVI achieves regret and oracle error rates close to the strongest AlphaZero configurations on Connect Four and below every AlphaZero budget on Hex(7x7).Head-to-head results also show greedy AVI performing similarly or better than the strongest AlphaZero variant using 512 MCTS simulations.
- Accurate Values and Competitive Policies under Exact Evaluation: AVI requires at most 7 neural-network evaluations per Connect Four decision and 49 per Hex(7x7) decision, versus 512 for the strongest AlphaZero agent.AVI constructs targets without tree search and uses one-step lookahead at inference.
- AVI Values Provide Stronger Search Guidance: AVI's values remain stronger under cross-inference and value-only minimax, reducing error with AlphaZero's policy and outperforming AlphaZero values without policy guidance.These tests indicate that AVI values provide stronger guidance across different inference procedures.
- Scaling to Othello and Go(9x9): Exact-oracle evaluation enables exact metrics but restricts the size of games studied, limiting the breadth of the conclusions.Larger games are therefore evaluated against a fixed reference rather than by absolute optimality.
- Scaling to Othello and Go(9x9): On Othello and Go(9x9), AVI trains stably and its greedy policy improves steadily, but remains weaker than MiniZero's search-based agent in direct matches.Greedy inference evaluates every legal action once and cannot concentrate additional computation on promising lines.
- Scaling to Othello and Go(9x9): When embedded in MiniZero's MCTS, AVI's learned values improve playing strength in both Othello and Go(9x9) under the same search budget.This extends the value-function result beyond games with exact evaluation.
6 Discussion and Limitations
AVI learns accurate values stably and can support either simple greedy decisions or richer search at deployment. The paper’s strongest evidence comes from solved games, while larger-game and computational conclusions remain bounded by evaluation and proxy limitations.
- Discussion: Stability may reflect alternating negamax errors, where an overestimate for one player becomes an underestimate one ply earlier.This is offered as one plausible explanation rather than an established causal account.
- Discussion: AVI’s accurate values can support richer action selection through MCTS, so training and inference need not use the same policy mechanism.The paper separates direct value learning from deployment-time search, especially when games have many legal actions.
- Limitations: The strongest claims concern exact evaluations on Connect Four, Hex(7x7), and F-Games, not optimality in Othello or Go(9x9).The larger games use a fixed MiniZero baseline, and the study does not test Go(19x19) or Chess.
- Limitations: The forward-equivalent compute proxy omits some wall-clock costs, including building and populating MCTS trees.Thus, reported computational comparisons do not capture every source of runtime overhead.
- Implications: The results do not show that MCTS is unnecessary; they suggest search may matter more for allocating inference computation than for learning useful values.Future work includes sampled-action exploration and hybrid AVI-value/policy-prior agents.
B AlphaZero.jl Baseline
AlphaZero.jl is used only as an external Connect Four calibration, not as a controlled algorithmic baseline. Its differing architecture, training procedure, and compute budget prevent causal comparison with the in-house agents.
- Implementation differences: AlphaZero.jl differs through replay-state averaging, a convolutional network, temperature decay, and scheduled replay-buffer capacity.These choices may affect both learning efficiency and final performance.
- External calibration: Figure 4 compares AVI and in-house AlphaZero with AlphaZero.jl using value error, policy regret, and oracle error rate.The AlphaZero.jl result is a horizontal dashed line because only its final checkpoint is evaluated.
- Interpretation: The external result calibrates the absolute scale of the in-house AlphaZero agent rather than identifying an algorithmic cause of performance differences.The main comparison keeps AVI and AlphaZero aligned on environments, replay buffer, optimization code, and network backbone.
C Experiment Details
The experiments use matched training conditions for the main AVI–AlphaZero comparison, specialized neural representations, and exact Connect Four evaluation alongside broader experimental protocols. Larger-game experiments reuse the AVI procedure with reduced exploration and MiniZero-based evaluation.
- Connect Four and Hex: AVI and AlphaZero use residual MLP networks with separate value and policy heads, while board inputs encode current-player and opponent stones.Symmetry is handled by evaluating reflected inputs and averaging outputs for Connect Four and Hex.
- Hyperparameters: AVI exploration is selected as ϵ = 0.3, while AlphaZero’s strongest searched configuration uses cpuct = 3.Evaluation additionally uses τ = 0.2 and Dirichlet noise fraction ϵ = 0.05.
- Larger games: Othello and Go(9x9) use MiniZero-matched backbones, symmetry augmentation, five AVI seeds, and 5.12M gradient steps with ϵ = 0.15.Evaluation uses 200 MCTS simulations and compares native MiniZero with cross-inference using AVI leaf values.
- Oracle evaluation: Connect Four is evaluated with a strong alpha-beta oracle that reports both theoretical outcomes and distance to termination.This permits strict action comparisons, including quickest wins and longest delays of forced losses.
D.4 Detailed results
Detailed evaluation covers different game phases and difficulty levels, with separate oracle characteristics for Connect Four and Hex. The reported figures average multiple seeds and display uncertainty intervals for value error and policy regret.
- Connect Four: Figure 5 reports Connect Four value error (MAE) and policy regret on the ϵ-optimal dataset.AVI curves average 20 random seeds, AlphaZero curves five seeds, and shaded regions show 95% Student’s t confidence intervals.
- State-type breakdown: Figure 6 breaks down value error and policy regret across Opening, Midgame, and Endgame subsets and Easy, Medium, and Hard difficulty levels.The curves use 20 AVI seeds and five AlphaZero seeds with 95% confidence intervals.
- Hex oracle: MoHex provides exact Win/Loss values for Hex(7x7) but does not distinguish moves sharing the same theoretical outcome.Accordingly, the Hex oracle is weak for play-vs-oracle evaluation because winning or losing moves are treated as equal.
E.3 Datasets
The experiments use solver-evaluated Connect Four positions and procedurally generated F-Games with explicit minimax ground truth. F-Games preserve minimax consistency by conditioning child values on each parent value and can include prematurely terminated branches.
- Solver-based datasets: 445 positions sampled by uniform random play form the single evaluation dataset for solver-based empirical evaluations.The expensive MoHex solver prevents evaluation at Connect Four’s finer state granularity.
- Solver-based datasets: The Dopenings play-vs-oracle dataset contains 128 positions after exactly two plies, split evenly between solver-labeled wins and losses.It includes 64 winning and 64 losing positions.
- Synthetic F-Games: F-Games are generated top-down so child values are conditioned on parent values, preserving minimax consistency and exposing every node’s ground-truth value.This contrasts with independently sampled leaf values propagated upward through minimax.
- Synthetic F-Games: Generation samples a root value, assigns one child the parent’s negation, and samples remaining children subject to a value constraint before recursing.The special-child construction and restricted sampling ensure the parent value equals the minimax value of its children.
- Synthetic F-Games: Premature termination probability β creates unbalanced F-Game trees whose branches can end before maximum depth.At nonmaximum-depth nodes, generation halts with probability β and turns the node into a terminal leaf.
F.3 Experiment setting
F-Game experiments use ternary outcomes, a fixed winning root, and a small probability of unbalanced termination. They compare Value Iteration across deep-narrow, balanced, and shallow-wide tree structures using independently generated instances.
- Game generation: F-Game values are −1, 0, or 1 for loss, draw, and win, with a uniformly distributed value prior and fixed root value 1.The fixed winning root ensures the games are not all-draw games.
- Game generation: The unbalanced-tree termination probability is fixed at β = 0.05 across experiments.This allows branches to end before maximum depth while retaining a controlled setting.
- Tree structures: Experiments span deep and narrow trees (h = 20, b = 2), balanced trees (h = 10, b = 5), and shallow and wide trees (h = 5, b = 20).These configurations vary depth and branching factor to test different algorithmic complexities.
- Evaluation design: Each tree configuration has 10 independently generated game instances to average topology- and outcome-related variance.The results from these instances are reported in Figure 7.
F.4 Datasets
Synthetic-domain evaluation samples diverse valid states, while the Connect Four and F-Game results compare value error and policy regret across computational settings. The figures emphasize error and regret as the principal evaluation measures.
- Evaluation datasets: Each F-Game contributes 4096 distinct valid states sampled from trajectories generated by a fully random uniform policy.The sampling procedure is intended to visit diverse trajectories for evaluation.
- Connect Four evaluation: Figure 6 reports value error (MAE) and policy regret across Connect Four datasets, game stages, and difficulty levels.AVI is compared with AlphaZero variants, with AVI curves averaging 20 seeds and AlphaZero curves averaging five.
- F-Game evaluation: Figure 7 reports value-function MAE and policy regret against neural-network forward-pass cost for deep-narrow, balanced, and shallow-wide F-Games.Shaded regions represent standard error across 10 random game instances.