蒙特卡洛树搜索MCTS游戏AI

可视化演示

展示MCTS选择扩展模拟回传四阶段循环、UCB1公式平衡利用与探索的节点选择、搜索树迭代生长访问次数收敛及棋类博弈落子评估决策，含流动波形背景动画。

蒙特卡洛思想

小蒙没有把乐园地图上每条路都走一遍——那要走上好几年。他另辟蹊径：在人流量最大的出口拦住五十位刚玩完的游客，挨个问“刚才那个项目好玩吗”。五十个答案里，四十一人说好玩。他据此拍板：这片园区值得去。这就是“用少量抽样推断整体”，先试再议，不必尽知。

蒙特卡洛（Monte Carlo）本是摩纳哥的赌城名字，科学家借用它指代“用随机实验做统计计算”的方法。比如要算一块不规则图形的面积，可以往图形上随机撒豆子，数一数落在图形里的豆子比例，乘以总区域面积，就能近似得到真实面积。豆子撒得越多，答案越准。AI 里的蒙特卡洛方法同理：反复随机模拟，把结果平均，用统计逼近真相。

在游戏 AI 中，我们想评估某个局面 s 到底“偏谁赢”。精确评估需要遍历所有后续可能，做不到；蒙特卡洛方法则随机模拟 N 局（比如随机走棋直到分出胜负），把每局结果记下来取平均，得到局面价值的估计值。这就是“以少代多”的统计决策。

小蒙没有走遍乐园，却对园区有了大致判断；MCTS 也用同样的“以少代多”思想，让 AI 在算不完的棋局里，也能估计出哪一步更可能通向胜利——这就是蒙特卡洛思想的核心魔法。

树搜索框架

有了“随机试玩”的底气，小蒙开始画“探索地图”。他把园区画成一棵树：树根是他现在站的位置，每根树枝对应一条岔路，岔路尽头又是一个新的小广场，再分出新的岔路。玩过、见过的路口，他就在树上标一个点；没见过的，先空着。地图不是一次画完的，而是边逛边补。

游戏 AI 里的“搜索树”正是这样：节点（Node）表示一个局面状态，边（Edge）表示一步动作。从根节点出发，沿着边走到子节点，就是对局向前推进了一步。注意，MCTS 不是一次性把整棵树建好——那叫穷举——而是边玩边画，每轮迭代只在树上“长出”一点点。

搜索树的规模由分支因子 b 和深度 d 决定。围棋的分支因子 b≈250、对局深度 d≈150，若穷举所有路径，状态数会指数爆炸，主流计算机几万年也算不完。MCTS 只挑有希望的路径反复走，所以它的树“长得高但很窄”。

小蒙明白了一个道理：在巨大的乐园里，把地图画完本身就是不可能的。与其纠结“全画完”，不如先画一棵“够用”的小树，再让它在实践中慢慢长大——这正是搜索树交给 MCTS 的使命。

选择与UCB

小蒙的小本本越来越厚，每个路口都记着“试玩次数”和“好评次数”。下一次该往哪走？他心里有个小算盘：既想去“大家都说好”的网红项目（利用），又想去“还没几个人去过、说不定有宝藏”的冷门角落（探索）。两条腿走路，才不辜负半天时间。

这就是 MCTS 的“选择（Selection）”阶段：从根节点出发，沿着树往下，逐步选一个最有潜力的子节点。但“最有潜力”不能只看胜率——一个只试玩过 1 次、胜率 100% 的项目，未必比试玩过 100 次、胜率 80% 的项目更靠谱。样本太少的统计结果，信不过。

于是科学家设计了 UCB（Upper Confidence Bound，置信上界）打分公式：每个子节点 j 的分数 = 已知平均胜率 + 一个“未知加分”。被访问次数越少的节点，加分越高。选择时永远挑分数最大的子节点往下走。这既尊重既有口碑，又鼓励探索新鲜角落。

小蒙恍然大悟：原来“口碑好”和“新鲜感”要一起算账。正是这个公式，让 AI 在“利用已知优势”与“探索未知可能”之间保持动态平衡，既不死磕一个项目，也不漫无目的地乱逛。

扩展与模拟

选定一条路后，小蒙走到小广场，发现旁边有条没标注过的岔路，通向一个他从没见过的新项目。他小心翼翼地把它画上地图，标上“待试玩”。这就是“扩展（Expansion）”：给搜索树添一个全新节点，代表一个新的可达局面。

画完新节点，小蒙决定“快速试玩”：冲进项目，以最快的速度体验完整流程，心里默默打个分。在 MCTS 里这叫作“模拟（Simulation）”，也叫快速走子（Rollout）：从新节点出发，双方随机走棋，一直走到分出胜负为止。模拟的结果，就是这次扩展的“试玩报告”。

注意，模拟虽然是“随机”，但通常会用“快速走子策略”让它更合理：优先吃对方棋子、抢占中心位置、避免自杀式送子等启发式规则。模拟策略越贴近真实对局，模拟结果的参考价值就越高——这正是“模拟策略改进”的核心思路：给随机性装上经验的翅膀。

小蒙发现，试玩并不是瞎玩，玩得越贴近真实游客的感受，记录越有价值。MCTS 的模拟策略也因此从“纯随机”一步步进化为“带经验的快速走子”，让 AI 的估计变得越来越靠谱。

回溯与更新

试玩结束，小蒙拿着分数回到小本本前：不只是新项目要记一笔，从入口一路走过来的每一个路口，全都得更新！毕竟新项目好不好玩，也会影响游客对这条路线整体的判断。他沿着来路，一级一级地往回改记录。

这就是“回溯（Backpropagation）”：把模拟结果沿着刚才选择的那条路径，从叶子节点一路传回根节点。路径上每个节点的访问次数加 1，胜场按模拟结果累加。这样一来，上层节点对“这半边园区值不值得去”的印象，也会被一并刷新。

回溯的本质是维护统计量：每个节点用“胜场/访问次数”记录胜率。假设某个第二层节点原本 3 胜 7 负，这次模拟赢了，它就变成 4 胜 8 负，胜率从 30% 升到 33.3%。下次选择时，UCB 公式就能用到这份新数据——小本本上的每一个数字，都在为明天做铺垫。

每一次试玩，都是对小本本的一次“全链路刷新”。小蒙越来越熟练，他也终于明白：MCTS 从不下“一个死结论”，而是不断用新数据修正旧印象——这正是它在动态博弈中保持灵活的关键。

应用与对比

几个月后，小蒙成了游乐园的“民间攻略王”。他用小本本上的经验，给无数游客推荐了最值得玩的项目。可有一天他发现，有些项目自己明明没怎么玩过，推荐却特别准——因为他学会了“在口碑之外看新鲜感”，这正是探索的力量在起作用。

MCTS 在真实游戏 AI 中战绩斐然。2016 年 AlphaGo 击败李世石，核心引擎之一就是“MCTS + 深度神经网络”：用策略网络指导选择和模拟、用价值网络评估局面，大幅替代耗时随机的模拟走子。今天，从围棋、象棋、五子棋到《星际争霸》式的策略游戏，MCTS 已是游戏 AI 的标配。

传统搜索（如极大极小搜索）需要人工设计精确的评估函数，面对巨大分支因子时常力不从心；MCTS 则几乎不需要领域知识，靠随机模拟和统计就能干活，还能随时用启发式规则、神经网络“打辅助”。它用“只采样 M 条完整路径”代替“穷举全部状态”，这就是它能在巨型博弈里存活的原因。

小蒙合上小本本，望向那座熟悉又陌生的乐园。他终于明白：完整的信息从来不是决策的前提，聪明的抽样和持续的修正才是。从游乐园到围棋棋盘，MCTS 用同一种智慧，让 AI 在巨大的不确定性中，一步步打出好牌。

AI 应用场景

Python 演示

import mathimport random  class Node:    def __init__(self, state, action=None, parent=None):        self.state = state      # 当前棋盘局面        self.action = action    # 到达该节点所走的落子        self.parent = parent    # 父节点        self.children = []      # 子节点列表        self.wins = 0           # 累计获胜次数        self.visits = 0         # 被访问次数     def ucb(self, c=1.4):        if self.visits == 0:            return float('inf')        return self.wins / self.visits + c * math.sqrt(            math.log(self.parent.visits) / self.visits)  def get_legal_moves(board):    return [i for i, v in enumerate(board) if v == 0]  def apply_move(board, move, player):    nb = board[:]    nb[move] = player    return nb  def check_winner(board):    lines = [        [0, 1, 2], [3, 4, 5], [6, 7, 8],        [0, 3, 6], [1, 4, 7], [2, 5, 8],        [0, 4, 8], [2, 4, 6]]    for a, b, c in lines:        if board[a] != 0 and board[a] == board[b] == board[c]:            return board[a]    return 0  def turn_of(board):    return 1 if len(get_legal_moves(board)) % 2 == 1 else 2  def rollout(board):    b = board[:]    while check_winner(b) == 0 and 0 in b:        p = turn_of(b)        b = apply_move(b, random.choice(get_legal_moves(b)), p)    w = check_winner(b)    if w == 1:        return 1.0    if w == 0:        return 0.5    return 0.0  def backprop(node, result):    while node is not None:        node.visits += 1        node.wins += result        node = node.parent  def select(node):    while node.children:        node = max(node.children, key=lambda ch: ch.ucb())    return node  def expand(node):    for move in get_legal_moves(node.state):        node.children.append(            Node(apply_move(node.state, move, turn_of(node.state)), move, node))    return random.choice(node.children)  def best_move(board, iterations=800):    root = Node(board)    for _ in range(iterations):        leaf = select(root)        if check_winner(leaf.state) == 0 and get_legal_moves(leaf.state):            leaf = expand(leaf)        result = rollout(leaf.state)        backprop(leaf, result)    best = max(root.children, key=lambda ch: ch.visits)    return best.action  def human_move(board):    while True:        try:            m = int(input('输入落子位置(0-8): '))            if m in get_legal_moves(board):                return m        except ValueError:            pass        print('位置无效, 请重试')  def play_game():    board = [0] * 9    print('AI(X)先手, 你执O. 位置编号 0-8:')    while check_winner(board) == 0 and 0 in board:        if turn_of(board) == 1:            board = apply_move(board, best_move(board), 1)            print('AI 落子:', board)        else:            board = apply_move(board, human_move(board), 2)            print('棋盘:', board)    w = check_winner(board)    if w == 0:        print('平局')    else:        print('AI 获胜' if w == 1 else '你赢了')  if __name__ == '__main__':    play_game()

1. return self.wins / self.visits + c * math.sqrt(...)UCB 打分：利用项（口碑分）+ 探索项（新鲜感加分）。
2. node = max(node.children, key=lambda ch: ch.ucb())选择阶段：沿 UCB 分数最高的子节点一路下行。
3. node.children.append(Node(..., move, node))扩展阶段：把所有合法落子都挂成新子节点。
4. result = rollout(leaf.state)模拟阶段：从叶子节点随机走子到终局，返回回报值。
5. backprop(leaf, result)回溯阶段：把结果沿父链传回根节点，更新访问次数与胜场。
6. return max(root.children, key=lambda ch: ch.visits)决策：不再看胜率，而是选访问次数最多的子节点，这也是 MCTS 的标准做法。

常见误区

面试题