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

Oct, 2023

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

Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction

Yangqing Fu, Ming Sun, Buqing Nie, Yue Gao

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

Abstract

monte carlo tree search (MCTS) algorithms such as AlphaGo and MuZero have achieved superhuman performance in many challenging tasks. However, the computational complexity of MCTS-based algorithms is influenced by the size of the search space. To address this issue, we propose a novel p

monte carlo tree search probability tree state abstraction search efficiency state-of-the-art algorithms search space reduction

发现论文，激发创造

通过即时状态条件的动作抽象实现高效蒙特卡罗树搜索

基于组合结构的行为抽象可以提高蒙特卡洛树搜索在具有复杂动作空间问题上的效率。本研究通过学习一个潜在的动态模型和辅助网络，构建了一种状态条件行为抽象方法，用于减少搜索空间并提高采样效率，并在实验中展示了其比传统 MuZero 方法更好的采样效率。

Jun, 2024

使用状态抽象的弹性蒙特卡罗树搜索在策略游戏中的应用

本文提出了一种名为弹性 MCTS 的算法，该算法使用状态抽象来玩策略游戏，通过动态聚类树节点，利用状态抽象带来的有效搜索同时避免了使用状态抽象对整个搜索的负面影响，并通过 Stratega 平台进行验证实验，结果表明 Elastic MCTS 相对于 MCTS 基线的性能提高了很多，同时将树的大小缩小了 10 倍。

May, 2022

在转移不确定性条件下的蒙特卡洛树搜索

研究纸中提出了一种改进 Monte Carlo Tree Search (MCTS) 框架的算法，它能够在环境模型存在不完全时搜索更加确定的转换，从而提高搜索行为和性能。

Dec, 2023

蒙特卡罗树搜索与证明数搜索的结合

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

Jun, 2022

学习停止：动态模拟蒙特卡罗树搜索

本文提出一种名为 Dynamic Simulation MCTS 的算法，它通过预测当前状态的不确定性来决定是否停止搜索，实现了在不降低胜率的情况下，将 NoGo 智能体训练速度提高了 2.5 倍，并在同样的平均模拟次数下，取得了 61% 的胜率。

Dec, 2020

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

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

Mar, 2023

使用 MCTSnets 学习搜索

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

Feb, 2018

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

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

Mar, 2012

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

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

Apr, 2019

通过 GPT 引导的蒙特卡罗树搜索从数据中发现数学公式

SR-GPT 是一种新的符号回归算法，通过将 MCTS 与 GPT 相结合，显著提高了 MCTS 的搜索效率，并利用 MCTS 结果进一步完善 GPT，从而在正确恢复符号表达式方面优于现有的最先进算法。

Jan, 2024