蒙特卡洛树搜索

靠大量随机模拟估计每个选择的好坏、边搜边长出搜索树的决策算法。

蒙特卡洛树搜索用来在「一步步做选择」的问题里找好决策。2006 年 Rémi Coulom 起了这个名字，同年 Kocsis 和 Szepesvári 提出了最常用的 UCT 版本。每轮迭代四步：选择（从根节点往下挑当前最值得试的分支）、扩展（加一个新节点）、模拟（从新节点随机或按策略推演到结束，得到一个结果）、回传（把结果沿路径更新到各节点的统计）。选择时常用 UCB 公式 w/n + c·√(ln N / n)：w/n 是该分支的平均得分，n 是它被试过的次数，N 是父节点的访问次数，c 调节偏向探索新分支还是利用已知好分支。它不需要人工写局面评估函数，搜到一半也能给出当前最好的答案。2016 年击败李世石的 AlphaGo 把它和神经网络结合；机器人里用于任务规划、部分可观测下的决策和接触序列规划。

例子足式机器人跨越踏脚石：Dhédin 等人 2025 年的工作用 MCTS 在离散层面搜索「哪条腿、按什么顺序、踩哪块落脚区」，每个候选序列交给全身轨迹优化检验能否做到，再用结果更新搜索树。

也叫

蒙特卡罗树搜索

相关

任务规划、探索与利用、部分可观测马尔可夫决策过程、MuZero、多接触规划、价值函数

来源

Wikipedia: Monte Carlo tree search
Simultaneous Contact Sequence and Patch Planning for Dynamic Locomotion (arXiv 2508.12928)