Mar, 2023

基于证明数的蒙特卡罗树搜索

PDF
TL;DR本文提出了一种新的游戏搜索算法，PN-MCTS，该算法将 Monte-Carlo 树搜索（MCTS）和证明数搜索（PNS）相结合。我们定义了三个领域，在这些领域中，在 MCTS 树中收集的证明和反证号所提供的额外知识可能会被使用。在不同的时间设置中测试了所有可能的组合，并与几个游戏进行了对抗。实验表明，PN-MCTS 在 5 个游戏领域中（Gomoku 除外）自信地优于 MCTS，Lines of Action 的胜率高达 96.2%。
pn-mctsmonte-carlo tree searchproof-number searchdecision makinggame domains
发现论文，激发创造
  • 蒙特卡罗树搜索与证明数搜索的结合

    本文介绍了一种称为 PN-MCTS 的新方法，它将 Proof-Number Search 和 Monte-Carlo Tree Search 相结合，将证明和证伪数的概念纳入 MCTS 的 UCT 公式中，实验结果表明，PN-MCTS 在几种游戏中表现优于基本的 MCTS，包括行动路线、MiniShogi、Knightthrough 和 Awari，取得了高达 94.0% 的胜率。

    Jun, 2022

  • 蒙特卡洛树搜索：近期修改和应用综述

    本文调查了 Monte Carlo Tree Search (MCTS) 在领域特定修改和混合方法方面的应用，这种方法依赖于智能树搜索并平衡探索和利用。

    Mar, 2021

  • 单智能体优化：通过蒙特卡罗树搜索进行策略迭代

    本文提出了一种使用基于 Monte-Carlo Tree Search 和深度强化学习相结合的方法的搜索算法，通过 1）用于潜在无限奖励问题的新颖行动价值规范机制，2）定义虚拟损失函数实现有效搜索并行化，以及 3）由自我对弈逐代训练的策略网络引导搜索，来提高搜索算法的效果。我们在同类游戏 SameGame 上进行实验，结果表明我们的算法在多个游戏宽度上优于基准算法，并与公共状态搜索问题的最新算法竞争力相当。

    May, 2020

  • 蒙特卡罗树搜索中的贝叶斯推断

    本文介绍了一种基于贝叶斯框架与高斯近似算法的 Monte-Carlo Tree Search 方法，旨在更准确地估算节点价值和不确定性，并证明了该方法的在策略和非策略情境下的收敛性和实现的优越性。

    Mar, 2012

  • 使用 MCTSnets 学习搜索

    该论文提出了一种名为 MCTSnet 的体系架构，其将基于模拟的搜索嵌入神经网络中，并通过向量嵌入扩展，评估和备份。该网络的参数进行端到端的训练优化，应用于小范围的搜索中，显著优于 MCTS 基线的性能。

    Feb, 2018

  • 用概率树状态抽象加速蒙特卡罗树搜索

    通过引入概率树状态抽象（PTSA）算法，改善了常见的蒙特卡罗树搜索（MCTS）算法的搜索效率，并且与最先进的算法结合使用，降低了 10% 至 45% 的搜索空间。

    Oct, 2023

  • 数学游戏

    Holophrasm 是使用 MCTS 和神经网络进行策略和评估的神经定理证明器，本文旨在通过其他游戏树搜索算法提高 Holophrasm 定理证明器的性能。

    Sep, 2023

  • 策略梯度搜索：无需搜索树的在线规划和专家迭代

    本研究提出一种用于模拟搜索的政策梯度搜索方法，通过在线更新神经网络模拟策略，实现避免使用搜索树的效果。在 Hex 上，与 MCTS 相比，PGS 取得了相当的性能，并且使用 PGS 进行专家迭代训练的代理能够在 9x9 Hex 中击败最强的开源 Hex 代理 MoHex 2.0。

    Apr, 2019

  • 达芬奇密码游戏策略模拟的蒙特卡罗树搜索算法的开发与应用

    通过比较分析基于 CPU 和 GPU 的 MCTS 算法在分支分歧情况下的性能，我们发现 CPU 实现呈线性改进趋势，而 GPU 实现呈现出非线性的增强模式和明显的性能下降。这些发现对于优化并行计算架构上的游戏策略算法具有重要的考虑价值。

    Mar, 2024

  • 通过 Monte Carlo 树自我精化和 LLaMa-3 8B 获得 GPT-4 级数学奥赛解题方法

    这篇论文介绍了 MCT Self-Refine (MCTSr) 算法，它是大型语言模型（LLM）与蒙特卡洛树搜索（MCTS）的创新集成，在复杂的数学推理任务中提高性能。通过解决 LLM 在战略和数学推理中的准确性和可靠性挑战，MCTSr 利用系统化的探索和启发式自我精炼机制来改进 LLM 内的决策框架。该算法通过选择、自我精炼、自我评估和反向传播的迭代过程构建蒙特卡洛搜索树，利用改进的 Upper Confidence Bound（UCB）公式优化探索 - 利用平衡。广泛的实验证明了 MCTSr 在解决奥林匹克数学问题方面的效果，显著提高了多个数据集的成功率，包括 GSM8K、GSM Hard、MATH 以及 Math Odyssey、AIME 和 OlympiadBench 等奥林匹克级别基准。该研究推动了 LLM 在复杂推理任务中的应用，为未来的人工智能集成奠定了基础，提高了 LLM 驱动应用中的决策准确性和可靠性。

    Jun, 2024