蒙特卡洛树搜索（MCTS）是一种用于决策过程的启发式树搜索算法，尤其在玩棋盘游戏的软件中应用广泛。它通过聚焦于最有希望的走法来求解博弈树，基于对搜索空间的随机采样来扩展搜索树。MCTS于2016年与神经网络结合，此后被应用于国际象棋、将棋、跳棋、西洋双陆棋、合约桥牌、围棋、拼字游戏和Clobber等游戏，以及回合制策略视频游戏和其他领域。
该算法通过重复的模拟对局（或称滚动）运行，其中游戏以随机走法模拟至结束。这些模拟对局的结果用于对博弈树中的节点进行加权，引导后续选择朝向更有希望的走法。MCTS的每一轮包括四个步骤：选择、扩展、模拟和反向传播。
历史
蒙特卡洛方法（对确定性问题进行随机采样）可追溯至20世纪40年代。1987年，Bruce Abramson将极小化极大搜索与基于随机游戏模拟的期望结果模型相结合，并在井字棋及其他游戏中证明了其有效性。1989年，W. Ertel、J. Schumann和C. Suttner将类似方法应用于自动定理证明，改善了搜索时间。1992年，B. Brügmann在围棋程序中使用了该方法。2002年，Chang等人提出了自适应多阶段采样（AMS），在蒙特卡洛树中引入了基于UCB的探索与利用机制，为UCT奠定了基础。
2006年，Rémi Coulom创造了“蒙特卡洛树搜索”这一术语，同时L. Kocsis和Cs. Szepesvári开发了UCT（应用于树的置信上界）算法。S. Gelly等人在程序MoGo中实现了UCT，该程序于2008年在9x9围棋中达到段位水平。2012年，Zen程序在19x19棋盘上战胜了一位业余二段棋手。谷歌DeepMind的AlphaGo使用结合神经网络的MCTS，于2015年成为首个击败职业人类围棋选手的程序，并于2016年战胜了李世石。
工作原理
MCTS的重点是通过基于随机采样扩展搜索树来分析最有希望的走法。每次模拟对局将游戏模拟至结束，结果用于对节点进行加权，从而使更好的走法被更频繁地选择。基本的纯蒙特卡洛游戏搜索对每个合法走法应用等量的模拟对局，并选择获胜次数最多的走法。
MCTS的每一轮包括四个步骤：
- 选择：从根节点开始，依次选择子节点，直到到达叶节点。
- 扩展：除非游戏已结束，否则从叶节点创建一个或多个子节点。
- 模拟：从新节点完成一次随机对局。
- 反向传播：沿从新节点到根节点的路径更新节点统计信息。
UCT算法
UCT算法通过置信上界公式平衡探索与利用。它根据子节点的平均胜率以及一个针对访问较少节点的奖励来选择子节点，从而使树向有希望的走法扩展，同时仍探索替代方案。这种方法对MCTS的效率至关重要。
应用
MCTS已被用于Hex、Havannah、亚马逊棋和Arimaa等棋盘游戏的程序中，以及Ms. Pac-Man和Fable Legends等实时视频游戏中。它还适用于非确定性游戏，如斯卡特、扑克、万智牌和卡坦岛拓荒者。在游戏之外，MCTS还被探索用于规划和优化问题。
意义
MCTS与深度神经网络的结合（如AlphaGo）标志着人工智能和机器学习领域的一个里程碑。它展示了如何将启发式搜索与深度学习方法相结合，以在复杂领域实现超人类表现，并影响了后续在生成式人工智能及其他领域的研究。