Mastering Board Games by External and Internal Planning with Language Models
作者: John Schultz, Jakub Adamek, Matej Jusup, Marc Lanctot, Michael Kaisers, Sarah Perrin, Daniel Hennes, Jeremy Shar, Cannada Lewis, Anian Ruoss, Tom Zahavy, Petar Veličković, Laurel Prince, Satinder Singh, Eric Malmi, Nenad Tomašev
分类: cs.AI, cs.CL, cs.LG
发布日期: 2024-12-02 (更新: 2025-05-23)
备注: 70 pages, 10 figures
💡 一句话要点
利用语言模型进行外部和内部规划，提升博弈游戏AI水平
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 大型语言模型 博弈游戏 蒙特卡洛树搜索 外部搜索 内部搜索
📋 核心要点
- 现有LLM在复杂领域的规划和推理能力不足，限制了其在实际应用中的可靠性。
- 论文提出外部搜索和内部搜索两种方法，利用LLM指导搜索过程，提升博弈游戏AI水平。
- 实验表明，该方法显著提高了LLM的游戏水平，在象棋中达到特级大师级别。
📝 摘要（中文）
本文旨在提升大型语言模型（LLM）在复杂领域中进行规划和推理的能力，并以博弈游戏（象棋、费舍尔随机象棋/Chess960、四子棋和六贯棋）为例进行论证。研究表明，基于搜索的规划能够显著提高LLM的游戏水平。论文提出了两种主要方法：外部搜索中，模型指导蒙特卡洛树搜索（MCTS）的 rollout 和评估，无需调用外部游戏引擎；内部搜索中，模型经过训练，可以在上下文中生成搜索的线性化树以及最终选择。两种方法都建立在预训练的语言模型之上，该模型具有相关的领域知识，能够可靠地捕获相应环境中的转移和价值函数，并最大限度地减少幻觉。通过与特定游戏的先进引擎进行评估，表明LLM搜索的实现显著提高了模型强度，并在象棋中达到了特级大师级别的性能，同时更接近人类的搜索预算。该方法结合了搜索和领域知识，不局限于博弈游戏，预示着更广泛的未来应用。
🔬 方法详解
问题定义：现有方法在博弈游戏中，依赖于大量的计算资源和复杂的算法，难以模拟人类的思考方式。大型语言模型虽然具备一定的推理能力，但在复杂博弈场景下，缺乏有效的规划和搜索机制，导致性能受限。因此，如何将LLM的知识和推理能力与搜索算法相结合，提升博弈游戏AI的水平，是一个亟待解决的问题。
核心思路：论文的核心思路是利用LLM的语言理解和生成能力，指导搜索过程，从而在有限的计算资源下，更有效地探索博弈树。通过外部搜索和内部搜索两种方式，将LLM的知识融入到搜索过程中，从而提升搜索效率和决策质量。
技术框架：论文提出了两种主要的技术框架：外部搜索和内部搜索。在外部搜索中，LLM作为MCTS的策略和价值函数，指导rollout和评估过程。LLM接收当前游戏状态的描述，输出下一步行动的概率分布和当前状态的价值估计。在内部搜索中，LLM被训练生成一个线性化的搜索树，其中包含一系列的行动和状态。LLM接收初始游戏状态的描述，输出一个包含搜索过程和最终选择的文本序列。
关键创新：论文的关键创新在于将LLM与搜索算法相结合，提出了外部搜索和内部搜索两种新的方法。与传统的博弈游戏AI方法相比，该方法能够利用LLM的知识和推理能力，更有效地进行搜索和决策。与直接使用LLM进行博弈游戏相比，该方法通过搜索过程，能够更好地探索博弈树，从而提升性能。
关键设计：在外部搜索中，LLM被训练预测下一步行动的概率分布和当前状态的价值估计。损失函数包括策略损失和价值损失，用于衡量LLM的预测与实际结果之间的差异。在内部搜索中，LLM被训练生成一个线性化的搜索树。训练数据包括一系列的博弈游戏过程，LLM需要学习如何生成一个包含搜索过程和最终选择的文本序列。论文中使用了Transformer架构的LLM，并针对博弈游戏的特点进行了优化。
🖼️ 关键图片
📊 实验亮点
实验结果表明，该方法显著提高了LLM在博弈游戏中的性能。在象棋游戏中，该方法达到了特级大师级别的水平，超过了许多传统的博弈游戏AI系统。与基线模型相比，该方法在各种博弈游戏中都取得了显著的提升，证明了其有效性。此外，该方法在有限的计算资源下，也能够取得良好的性能，使其更具实用价值。
🎯 应用场景
该研究提出的方法具有广泛的应用前景。除了博弈游戏，还可以应用于需要规划和推理的复杂领域，例如机器人控制、自动驾驶、任务调度等。通过将LLM的知识和推理能力与搜索算法相结合，可以提升这些领域中AI系统的性能和可靠性，使其能够更好地解决实际问题。
📄 摘要（原文）
Advancing planning and reasoning capabilities of Large Language Models (LLMs) is one of the key prerequisites towards unlocking their potential for performing reliably in complex and impactful domains. In this paper, we aim to demonstrate this across board games (Chess, Fischer Random / Chess960, Connect Four, and Hex), and we show that search-based planning can yield significant improvements in LLM game-playing strength. We introduce, compare and contrast two major approaches: In external search, the model guides Monte Carlo Tree Search (MCTS) rollouts and evaluations without calls to an external game engine, and in internal search, the model is trained to generate in-context a linearized tree of search and a resulting final choice. Both build on a language model pre-trained on relevant domain knowledge, reliably capturing the transition and value functions in the respective environments, with minimal hallucinations. We evaluate our LLM search implementations against game-specific state-of-the-art engines, showcasing substantial improvements in strength over the base model, and reaching Grandmaster-level performance in chess while operating closer to the human search budget. Our proposed approach, combining search with domain knowledge, is not specific to board games, hinting at more general future applications.