跳转至

文章背景与核心概要

本文探讨了将搜索算法与函数近似相结合在游戏AI领域的应用。长期以来，基于蒙特卡洛树搜索（MCTS）的自对弈方法一直是实现竞技级性能的标准方案，但也带来了沉重的计算开销。

作者通过在一系列中等规模且非平凡的游戏（如四子棋、7x7六子棋及合成基准）中训练一个极简的自对弈近似价值迭代（AVI）实现，并利用真实预言机（ground-truth oracles）进行精确评估，发现AVI的性能表现出人意料地强大。研究表明，AVI不仅能学习到比AlphaZero更准确的价值函数，而且其一步前瞻（one-step-lookahead）的贪婪策略在大幅降低训练和推理成本的同时，依然能够与基于MCTS的策略一较高下。在更大规模领域（如黑白棋和9x9围棋）的初步实验也证实了AVI具有稳定的训练行为和高效的价值学习能力。这些发现表明，现代深度学习工具使得更简单的强化学习方法重新具备极高的实用价值，过往对MCTS范式的过度依赖可能掩盖了这些简洁替代方案的光芒。

自对弈中近似价值迭代的惊人有效性 (The Surprising Effectiveness of Approximate Value Iteration in Self-Play)

作者： Raphael Boige, Amine Boumaza, Bruno Scherrer
提交时间： 2026年9月8日
主要学科： 人工智能 (cs.AI)
arXiv： 2609.09094 [cs.AI]
DOI： 10.48550/arXiv.2609.09094

执行摘要 (Executive Summary)

搜索算法与函数近似的融合从根本上推动了游戏AI的发展，使得自对弈方法成为实现竞争性能的标准。然而，依赖蒙特卡洛树搜索（MCTS）的流行技术引入了相当大的计算开销。

本文研究了在适度规模、非平凡的游戏（如四子棋、7x7六子棋和合成基准）中，更简单的强化学习方法是否依然可行且具有竞争力。通过训练一个极简的近似价值迭代（AVI）自对弈实现，并利用真实预言机进行精确评估，作者证明了AVI具有惊人的有效性： * 更高的准确性： AVI学习到的价值函数比AlphaZero更加准确。 * 成本效益： 其一步前瞻贪婪策略在仅需极少训练和推理成本的情况下，依然能与基于MCTS的策略保持竞争力。 * 可扩展性： 在黑白棋和9x9围棋等更大领域的初步实验显示出稳定的训练行为和高效的价值学习。

这些发现表明，以MCTS为中心的范式的巨大成功可能过早地掩盖了更简单的替代方案，而借助现代深度学习工具，这些替代方案如今已具有高度的实用性。

The integration of search algorithms with function approximation has fundamentally advanced game-playing AI, making self-play methods standard for competitive performance. However, popular techniques relying on Monte Carlo Tree Search (MCTS) introduce substantial computational overhead.

This paper investigates whether simpler reinforcement learning methods remain viable and competitive in moderately sized, non-trivial games (such as Connect Four, Hex (7x7), and synthetic benchmarks). By training a minimal self-play implementation of Approximate Value Iteration (AVI) and utilizing ground-truth oracles for exact evaluation, the authors demonstrate that AVI is surprisingly effective: * Higher Accuracy: AVI learns more accurate value functions than AlphaZero. * Cost Efficiency: Its one-step-lookahead greedy policies remain competitive with MCTS-based policies at a fraction of the training and inference cost. * Scalability: Preliminary experiments on larger domains like Othello and Go (9x9) show stable training behavior and effective value learning.

These findings suggest that the massive success of MCTS-centric paradigms may have prematurely overshadowed simpler alternatives, which are now highly practical thanks to modern deep learning tools.

摘要 (Abstract)

将搜索与函数近似相结合推动了棋类游戏程序的重大进展，使得自对弈算法比以往更具竞争力。尽管如此，基于蒙特卡洛树搜索（MCTS）的最流行方法的计算开销仍然相当可观。在这项工作中，我们研究了更简单的方法是否在诸如四子棋、7x7六子棋和合成游戏等非平凡、中等规模的游戏中保持竞争力。我们训练了一个极简的自对弈近似价值迭代（AVI）实现，并使用真实预言机进行精确评估。与预期相反，我们的结果证明了AVI令人惊异的有效性：它学习到了比AlphaZero更准确的价值函数，而它的一步前瞻贪婪策略在显著降低训练和推理成本的同时，依然能够与基于MCTS的策略相媲美。在黑白棋和9x9围棋上的初步实验表明，AVI在更大规模的游戏中能够稳定训练并学习到有效的价值函数。这些发现表明，基于MCTS的方法的成功可能掩盖了那些随着现代深度学习工具的发展而变得日益实用的更简单方法。

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.

附加信息与资源 (Additional Information & Resources)