自我对弈中近似值迭代的惊人效果

将搜索与函数逼近相结合推动了游戏程序的重大进步,，使自玩算法比以往任何时候都更具竞争力。尽管如此，, 基于蒙特卡罗树搜索的最流行方法, 的计算开销(MCTS), 可能相当大。在这项工作, 中，我们研究了更简单的方法是否在非平凡的, 中等大小的游戏（例如 Connect Four, Hex(7x7) 和合成游戏）中保持竞争力。我们训练近似值迭代 (AVI) 的最小自我对弈实现，并使用真实的预言机进行精确评估。与预期相反,，我们的结果证明了 AVI: 令人惊讶的有效性，它比 AlphaZero, 学到的价值函数更准确，同时其一步前瞻贪婪策略与基于 MCTS 的策略相比仍具有竞争力，且训练和推理成本要低得多。在 Othello 和 Go(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.

科目:人工智能(cs.AI)

Subjects: Artificial Intelligence (cs.AI)