蒙特卡洛树搜索(MCTS)

蒙特卡洛树搜索(Monte Carlo Tree Search,简称 MCTS)是一种用于序贯决策问题的启发式搜索算法,通过大量随机模拟来评估动作优劣,并把算力集中到最有希望的分支上。2006 年,法国研究者雷米·库仑(Rémi Coulom)在围棋程序 Crazy Stone 中提出这一框架;同年科奇什(Levente Kocsis)与塞派什瓦里(Csaba Szepesvári)提出 UCT 算法,把多臂老虎机的置信上界策略引入树搜索,奠定了现代 MCTS 的标准形态。

概述

传统博弈搜索如 Alpha-Beta 剪枝依赖人工设计的局面评估函数,而围棋这类分支巨大、局面难以静态评估的游戏令其束手无策。MCTS 不需要先验评估函数:用随机对局跑到终局的胜负作为价值信号,统计意义上逼近真实胜率,并且是随时可停的算法,给多少时间就给出多好的答案。

核心原理

每次迭代包含四个阶段:

• 选择:从根出发,按 UCB 公式在利用(选胜率高的孩子)与探索(选访问少的孩子)间权衡,一路下行到叶节点。
• 扩展:为叶节点添加一个或多个尚未尝试的子节点。
• 模拟:从新节点起用快速走子策略随机下到终局,得到胜负结果。
• 回传:把结果沿路径向上更新各节点的访问次数与胜率统计。

迭代结束后,通常选访问次数最多的根子节点作为落子。AlphaGo 及其后继 AlphaZero 用策略网络指导选择、价值网络取代随机模拟,把 MCTS 与深度学习结合到极致。

应用场景

MCTS 是计算机围棋革命的引擎,从 Crazy Stone、MoGo 到 2016 年 AlphaGo 战胜李世石一脉相承;此外它还被用于国际象棋与将棋(AlphaZero)、通用游戏对弈、即时战略与卡牌游戏 AI、组合优化、化学分子逆合成规划以及机器人规划等需要在巨大决策树中试探的场景。

常见问题

问:MCTS 和 Alpha-Beta 剪枝该怎么选？答:分支因子小、评估函数成熟的游戏(如国际象棋传统引擎)适合 Alpha-Beta;分支巨大、局面难评估或缺乏领域知识时 MCTS 更有优势。

问:MCTS 一定要随机模拟到终局吗？答:不一定,现代实现常用训练好的价值网络直接估值代替随机走子,AlphaZero 就完全省去了随机模拟阶段。

问:UCT 中的探索常数起什么作用？答:它控制探索与利用的平衡,取值大则更愿意尝试访问少的分支,取值小则更快收敛到当前最优分支,实践中需按问题调参。