分层分阶蒙特卡洛树搜索用于 SMT 策略合成
内容提要
本文综述蒙特卡洛树搜索（MCTS）的改进与混合方法，涵盖AutoML、神经网络嵌入、路径规划、AlphaZero启发算法、SAT求解、逆合成规划及状态抽象等应用，通过备份操作与熵正则化提升收敛和探索，实验表明多数方法优于基线。
延伸解读
MCTS 改进的两条主线：领域定制与混合学习
文章梳理的多数工作可归为两类：一是针对特定问题定制 MCTS，如 AutoML 中的 Mosaic、路径规划中的多样化计划生成、SAT 求解中的 MCFS-SAT；二是将 MCTS 与神经网络、强化学习等结合，如 MCTSnet 将搜索嵌入网络端到端训练，AlphaZero 启发方法利用启发式近似策略优化解。这些改进共同指向提升搜索效率与泛化能力。
效率与资源：轻量化实现与搜索空间压缩
部分方法强调在有限计算资源下取得优势。例如，AlphaZero 启发的 MCTS 包装器与时间差分学习结合，无需 GPU 或 TPU 即可在复杂游戏中击败强敌；弹性 MCTS 通过状态抽象动态聚类节点，将树大小缩小 10 倍，同时提升性能。这表明 MCTS 的改进不仅追求更强，也注重更省。
理论保障与实验验证并重
文章提到，通过引入备份操作与熵正则化，可提高 MCTS 的收敛速率和探索程度，并提供强有力的理论保证。同时，多数应用在基准测试中取得了统计显著提升，如 MCFS-SAT 在 sgen 和 random 分布上运行时间快于 2021 年 SAT 竞赛最强非不可满足求解器。这反映了该领域既重视理论分析，也依赖实验验证。
Q&A
蒙特卡洛树搜索（MCTS）在AutoML任务中有哪些应用？
2021年3月的研究使用基于MCTS的方法Mosaic处理混合结构和参数昂贵的黑盒优化问题，在基准测试中获得了统计显著的性能提升。
MCTSnet是如何将神经网络与蒙特卡洛树搜索结合的？
MCTSnet将基于模拟的搜索嵌入神经网络中，通过向量嵌入扩展、评估和备份，网络参数进行端到端训练优化，应用于小范围搜索，显著优于MCTS基线。
AlphaZero启发的MCTS包装器在资源有限的情况下表现如何？
2020年7月的研究提出一种AlphaZero启发的MCTS包装器，与时间差异学习智能体结合，无需GPU或TPU等高性能计算资源，在多个复杂游戏中成功打败强劲对手。
Monte Carlo Forest Search（MCFS）在SAT求解中有什么优势？
MCFS是一种离线算法，用于自动合成强树搜索求解器，证明给定分布的不可满足性。MCFS-SAT是其实现，学习解决布尔可满足性问题的分支策略，在两个知名SAT分布上性能优于强基线，运行时间比2021年SAT竞赛中最强的非可满足求解器更快。
弹性MCTS如何利用状态抽象提高性能？
弹性MCTS使用状态抽象来玩策略游戏，通过动态聚类树节点，利用状态抽象带来的有效搜索同时避免其负面影响。在Stratega平台验证表明，相对于MCTS基线性能提高很多，同时将树的大小缩小了10倍。
有哪些方法可以提高蒙特卡洛树搜索的收敛速率和探索程度？
2022年5月的研究提出两种方法，基于引入的备份操作与熵正则化，提供强有力的理论保证，实验证明方法有效。
