Implicit Search via Discrete Diffusion: A Study on Chess

📄 arXiv: 2502.19805v1 📥 PDF

作者: Jiacheng Ye, Zhenyu Wu, Jiahui Gao, Zhiyong Wu, Xin Jiang, Zhenguo Li, Lingpeng Kong

分类: cs.LG, cs.AI

发布日期: 2025-02-27

备注: ICLR 2025

🔗 代码/项目: GITHUB

💡 一句话要点

提出DiffuSearch，通过离散扩散模型进行隐式搜索，提升AI在棋类游戏中的规划能力。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 隐式搜索 离散扩散模型 棋类游戏 长期规划 人工智能

📋 核心要点

  1. 现有基于next-token预测的模型缺乏长期规划能力，限制了其在复杂决策任务中的表现。
  2. DiffuSearch通过离散扩散模型进行隐式搜索，模拟未来状态，从而增强模型的规划能力。
  3. 实验表明，DiffuSearch在国际象棋中优于无搜索和显式搜索策略，显著提升了行动准确率和解谜能力。

📝 摘要（中文）

在后AlphaGo时代，蒙特卡洛树搜索（MCTS）等搜索技术重新引起人们的兴趣，尤其是在大型语言模型（LLM）中的应用。这是因为人们认识到，当前的下一个token预测模型通常缺乏长期规划能力。本文旨在探讨是否可以在模型中注入类似搜索的能力，以增强其规划能力，而无需依赖显式搜索。为此，我们提出了DiffuSearch，该模型通过离散扩散建模来观察未来世界，从而进行“隐式搜索”。我们在经典的棋盘游戏——国际象棋上实例化DiffuSearch，在国际象棋中，显式搜索至关重要。通过广泛的对照实验，我们表明DiffuSearch优于无搜索策略和显式搜索增强策略。具体而言，DiffuSearch在行动准确率上优于一步策略19.2%，优于MCTS增强策略14%。此外，与基于显式搜索的策略相比，DiffuSearch在解谜能力方面显著提高了30%，在游戏强度评估方面显著提高了540 Elo。这些结果表明，通过离散扩散进行的隐式搜索是优于一步策略的显式搜索的可行替代方案。所有代码均可在https://github.com/HKUNLP/DiffuSearch上公开获取。

🔬 方法详解

问题定义：论文旨在解决AI在棋类游戏中长期规划能力不足的问题。现有方法，如一步策略，缺乏对未来状态的预测能力。而显式搜索方法，如MCTS，计算成本高昂，且可能陷入局部最优。

核心思路：论文的核心思路是利用离散扩散模型进行隐式搜索。通过学习从噪声到棋局状态的逆向扩散过程，模型可以预测未来的棋局状态，从而在决策时考虑到更长远的规划。这种方法避免了显式搜索的计算开销，同时能够捕捉到潜在的有利局面。

技术框架：DiffuSearch的整体框架包含以下几个主要模块：1) 棋局状态编码器：将棋局状态编码为向量表示。2) 离散扩散模型：学习从噪声到棋局状态的逆向扩散过程，用于预测未来的棋局状态。3) 策略网络：根据当前棋局状态和扩散模型预测的未来状态，选择最佳的行动。4) 训练过程：通过模仿学习或强化学习，训练策略网络和扩散模型。

关键创新：DiffuSearch的关键创新在于使用离散扩散模型进行隐式搜索。与传统的显式搜索方法不同，DiffuSearch不需要显式地枚举所有可能的未来状态，而是通过学习扩散过程来隐式地模拟未来状态。这大大降低了计算复杂度，并提高了模型的泛化能力。

关键设计：DiffuSearch的关键设计包括：1) 离散扩散模型的选择：论文选择了离散扩散模型，因为棋局状态是离散的。2) 损失函数的设计：论文使用了交叉熵损失函数来训练策略网络，并使用扩散模型的负对数似然来训练扩散模型。3) 网络结构的设计：论文使用了卷积神经网络来编码棋局状态，并使用Transformer网络来实现扩散模型。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

DiffuSearch在国际象棋游戏中取得了显著的性能提升。在行动准确率方面，DiffuSearch优于一步策略19.2%，优于MCTS增强策略14%。在解谜能力方面，DiffuSearch比基于显式搜索的策略提高了30%。在游戏强度评估方面，DiffuSearch的Elo等级提升了540分。这些结果表明，DiffuSearch是一种有效的隐式搜索方法，可以显著提升AI在棋类游戏中的表现。

🎯 应用场景

DiffuSearch的潜在应用领域包括棋类游戏、战略游戏、机器人路径规划、自动驾驶等需要长期规划和决策的任务。该研究的实际价值在于提供了一种高效且可泛化的隐式搜索方法，可以提升AI在复杂环境中的决策能力。未来，该方法可以应用于更广泛的领域，例如金融交易、供应链管理等。

📄 摘要（原文）

In the post-AlphaGo era, there has been a renewed interest in search techniques such as Monte Carlo Tree Search (MCTS), particularly in their application to Large Language Models (LLMs). This renewed attention is driven by the recognition that current next-token prediction models often lack the ability for long-term planning. Is it possible to instill search-like abilities within the models to enhance their planning abilities without relying on explicit search? We propose DiffuSearch , a model that does \textit{implicit search} by looking into the future world via discrete diffusion modeling. We instantiate DiffuSearch on a classical board game, Chess, where explicit search is known to be essential. Through extensive controlled experiments, we show DiffuSearch outperforms both the searchless and explicit search-enhanced policies. Specifically, DiffuSearch outperforms the one-step policy by 19.2% and the MCTS-enhanced policy by 14% on action accuracy. Furthermore, DiffuSearch demonstrates a notable 30% enhancement in puzzle-solving abilities compared to explicit search-based policies, along with a significant 540 Elo increase in game-playing strength assessment. These results indicate that implicit search via discrete diffusion is a viable alternative to explicit search over a one-step policy. All codes are publicly available at \href{https://github.com/HKUNLP/DiffuSearch}{https://github.com/HKUNLP/DiffuSearch}.