蒙特卡洛树搜索（MCTS）是一种用于决策过程的启发式树搜索算法，尤其是在玩棋盘游戏的软件中。它通过聚焦于最有希望的走法来求解博弈树，并基于搜索空间的随机采样来扩展博弈树。MCTS 于 2016 年与神经网络相结合，此后被应用于国际象棋、将棋、跳棋、西洋双陆棋、定约桥牌、围棋、拼字游戏和 Clobber 等游戏，以及回合制策略视频游戏和非游戏应用。
该算法通过重复的模拟（称为 rollout）来运行，即在模拟中随机走子直至对局结束。这些模拟的结果用于对博弈树中的节点进行加权，从而使更好的节点在未来的模拟中更有可能被选中。这种方法不同于传统的极小化极大搜索，因为它不依赖静态评估函数，而是依靠模拟结果。
历史
蒙特卡洛方法（一种用于确定性问题的随机采样方法）的历史可以追溯到 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 年达到了 9 路围棋的段位水平。大约在同一时期，Fuego 程序也开始在 9 路围棋中击败强业余棋手。2012 年 1 月，Zen 程序在 19 路棋盘上以 3:1 战胜了一位业余 2 段棋手。
Google DeepMind 开发了 AlphaGo，该程序于 2015 年 10 月成为首个在没有让子的情况下于标准尺寸棋盘上击败职业围棋棋手的程序。2016 年 3 月，AlphaGo 以 4:1 战胜了李世石，获得了荣誉九段。AlphaGo 将 MCTS 与人工神经网络（一种深度学习方法）相结合，用于策略和价值评估，这标志着机器学习领域的一个重要里程碑。
工作原理
MCTS 通过聚焦于最有希望的走法来扩展搜索树，并基于搜索空间的随机采样进行扩展。每次迭代包含四个步骤：
- 选择：从根节点（当前棋局状态）开始，依次选择子节点，直到到达一个叶节点。选择过程偏向于有希望的走法，通常使用 UCT 算法。
- 扩展：除非叶节点已经结束对局，否则创建一个或多个代表合法走法的子节点。
- 模拟：从选定的子节点开始，随机走子直至对局结束。
- 回溯：将模拟结果沿路径从子节点回传至根节点，并相应地更新沿途节点的访问次数和胜率。
对于平局的情况，平局结果会使该节点的胜场计数增加 0.5，访问计数增加 1，这对双方玩家都是如此。这确保了每个玩家的选择都会朝着最大化自身胜率的方向扩展。
UCT 算法
UCT 算法于 2006 年提出，它将上置信界（UCB）方法应用于树搜索。它通过基于节点的平均回报以及一个针对访问次数较少节点的奖励项来选择子节点，从而在探索（尝试新走法）与利用（选择已知好走法）之间取得平衡。这使得搜索树能够朝着最有希望的走法扩展，同时仍会探索其他备选方案。UCT 已成为 MCTS 实现的标准算法，并被 MoGo 及后续程序所采用。
应用
MCTS 已被用于多种棋盘游戏程序中，例如 Hex、Havannah、Amazons 游戏和 Arimaa，以及实时视频游戏，如《吃豆人女士》和《Fable Legends》。它也能处理非确定性游戏，如 Skat、扑克、万智牌和卡坦岛拓荒者。在回合制策略游戏中，《全面战争：罗马 II》在其高级 AI 中使用了 MCTS。除了游戏之外，MCTS 还应用于规划和优化问题。
MCTS 与神经网络的结合（如 AlphaGo 所采用的）已被证明非常有效。这种混合方法利用神经网络来指导走法选择并评估局面，从而减少了对大量随机模拟的依赖。随后的程序（如 AlphaZero）已将这种方法扩展到国际象棋和将棋，并达到了超越人类顶尖水平的性能。