期末复习最怕的不是知识点多而是知识点看起来“会了”一到计算题就露馅。第3章搜索求解最后一块内容——蒙特卡洛树搜索就是这么个东西。它跟前面讲的盲目搜索、启发式搜索完全不是一个路数很多同学第一次看到“蒙特卡洛”“UCB”“ rollout”这些词直接懵掉。这篇文章我按期末复习的逻辑帮你把蒙特卡洛树搜索彻底盘一遍从它要解决什么问题、四个阶段怎么走、UCB公式怎么算到考试会怎么考、代码怎么落笔全部展开讲透。1. 蒙特卡洛树搜索到底在干什么1.1 为什么要专门学一个带“蒙特卡洛”的树搜索先回答最直接的问题这门课前面已经有广度优先、深度优先、A* 这些搜索算法了为什么还要再学一个蒙特卡洛树搜索因为前面那些算法都建立在一个前提上——你能够完整地展开搜索空间或者至少能用启发函数给每个状态打一个比较靠谱的分。但现实里有很多问题是满足不了这个前提的。典型代表就是围棋合法落子点几百个棋局变化量远超宇宙原子数你根本不可能把整棵博弈树展开。这时候还需要一个能在“不知道哪个分支更好、又没办法全展开”的情况下做决策的算法。蒙特卡洛树搜索Monte Carlo Tree SearchMCTS解决的就是这个矛盾。它的核心思想很朴素我不把整棵树看完我用随机模拟去采样模拟得多的分支我就认为它更好。这个思路放到日常生活中特别好理解。你面前有十家外卖店你不知道哪家好吃怎么办你不可能把十家都点一遍展开整棵树代价太高更靠谱的办法是问朋友、看评价、点几次试试哪家被验证的次数多、评分高下次就继续点哪家。MCTS就是把这个“试试看凭反馈调整”的过程在博弈树里做得非常系统化。所以在人工智能引论这门课里MCTS属于基于采样和统计的搜索方法它跟A*这种基于完备展开的搜索方法形成了鲜明的对照。考试如果出简答题问“MCTS适用于什么场景”标准答案就是状态空间巨大、难以完整展开、缺少有效启发函数的决策问题。1.2 它和盲目搜索、启发式搜索的本质区别这里帮大家把三个搜索串成一条线期末复习时特别容易出对比题。盲目搜索BFS/DFS只知道“按层”或“按深度”挨个找不聪明但保证能找到解前提是搜索空间有限。启发式搜索A*、贪婪最佳靠启发函数 f(n)g(n)h(n) 指导方向比盲目搜索高效但它要求你能写出一个像样的估价函数并且搜索空间仍然要能管理。蒙特卡洛树搜索完全换了个思路它不指望启发函数它通过大量随机模拟的统计结果来评估哪个动作好。三者对比可以这样记忆方法决策依据搜索空间要求核心代价BFS/DFS遍历顺序必须完整枚举时间空间爆炸A* 等启发式启发函数估计需要可管理的空间难以构造启发函数MCTS随机模拟的统计回报无需完整展开模拟次数要够多A* 是“我觉得这条路好所以往这走”MCTS是“我跑了很多遍这条路赢的次数多所以往这走”。你Get到这个区别后面学四阶段就很顺了。1.3 蒙特卡洛方法这层老底既然叫蒙特卡洛树搜索里面一定有用到蒙特卡洛方法。蒙特卡洛方法本身是个很老的技术核心理念就是用随机数做大量抽样用统计结果逼近精确答案。最经典的解释是算圆周率你往一个正方形里随机撒点统计落在内切圆里的点占总数比例这个比例乘以4就逼近π。撒的点越多结果越准确。数学上这叫大数定律样本量足够大时样本均值会收敛到期望值。MCTS借用了这个思路——把“某个分支能赢棋的概率”当作一个未知的期望值每次模拟就是一次采样采样多了估计自然越来越准。理解这一层非常关键。因为很多考试计算题本质上不是让你算树搜索的“精确值”而是让你按MCTS规则推演若干次模拟后统计量怎么变化。你只要记得“每轮模拟都在给统计量增加样本”这个底层逻辑做题就不慌。2. 四个阶段逐段拆解这才是MCTS的心脏2.1 选择阶段往哪里走靠UCB打分说话MCTS每一轮迭代都从根节点出发沿着树往下走走到一个还没有完全展开的节点为止。这个“往下走”可不是随便走的全靠一个打分公式来选UCB1Upper Confidence Bound 1。公式长这样UCB1 v_i C × sqrt( ln(N) / n_i )v_i第 i 个子节点的平均胜率这个节点赢了多少次 / 被访问了多少次N当前节点的总访问次数n_i子节点 i 的访问次数C探索系数控制“探索新分支”和“利用已知好分支”的平衡这个公式设计的妙处在于两部分互补。前半部分 v_i 是“利用”哪个子节点赢面大倾向于选它。后半部分是“探索”ln(N)/n_i 这个项某个子节点被访问得越少分母越小整个加分项就越大于是那些“还没怎么试过”的分支也会有机会被选中。为什么要加 log因为 ln(N) 增长得慢意味着一个分支就算暂时落后只要被访问次数远小于总访问次数它依然能获得足够的探索动力。随着N变大探索项的权重会逐渐下降算法越来越倾向于利用模拟验证过的好分支。思路和“新店虽然评分未知但只要试的人少就值得尝一次尝多了就按口碑来”完全一致。考试题目如果给你一棵树、每个节点的胜利次数和访问次数让你算下一步选哪个孩子本质上就是套公式比大小。这里提醒注意两点一是 ln 是自然对数不是以10为底二是 C 在题目里通常直接给定如果没给默认取 sqrt(2)这是原始论文里推荐的常数。2.2 扩展阶段树什么时候长出新叶子选择阶段走到某个节点时会判断它是不是“叶子”。但这个“叶子”跟你在数据结构里学的不太一样。在MCTS里有两个概念要分清可达的完整叶子对局已经结束胜负已分这种节点不能再扩展。还有子节点没被探索的节点它还有合法动作没有尝试过。MCTS的扩展策略是只要当前节点还有没被访问过的子动作就选一个出来把这个动作对应的新局面添加到树里。这个新节点初始统计量都是0胜利次数0访问次数0。你可能会问一次扩展加一个节点还是加所有没访问过的节点标准做法是每次迭代只扩展一个节点。这样每轮模拟都保证树只长大一小步算法才有性子慢慢探索。这也是考试里画树推演时最容易出错的地方——别人画着画着一下长出一大串节点那一定是没理解“每次模拟只增加一个子节点”这个规定。提示从根节点到“未完全展开节点”的路径上走完全程走的都是选择阶段一旦到了未展开节点立即进入扩展阶段而不是继续往下凭空生成节点。2.3 模拟阶段随机Rollout一切交给命运扩展出新节点后算法进入模拟阶段英文叫 rollout 或者 playout。这个阶段做的事情很简单从新节点开始用随机策略把棋局一直下到分出胜负为止。随机策略就是完全不动脑子随便从合法动作里挑一个往下走。这一步看似很傻但它是MCTS统计估计的基础——正因为模拟是随机的、无偏的大量模拟的胜率才能反映出这个节点对应的局面“到底行不行”。模拟阶段有个关键细节它不进入搜索树。也就是说从新扩展节点之后的路都是临时模拟出来的不在树上留下结构。树上的节点只在选择、扩展阶段变更模拟走出来的那些临时局面不会添加进树结构里。很多教材里的树图树主体就那么多节点模拟阶段是树外面一段虚线路径就是这个原因。模拟的终点是一个确定的结果比如围棋里的“黑赢/白赢”。这个结果会被记录成一个数值通常是黑棋视角1代表赢、0代表输或者白棋视角反过来。这个数值接下来就要往上回传。2.4 回溯阶段胜利的果实一路喂到根模拟得到结果后从刚扩展的节点开始沿着选择阶段走过的路径一路回溯到根节点把路径上所有节点的统计量更新一遍。更新规则是访问次数 n_i 全部加1胜利次数 w_i 按照当前模拟结果加1或加0如果模拟结果是当前节点视角获胜就加1否则不加。回到公式里看你就明白为什么这个更新重要v_i w_i / n_i访问次数变多、胜利次数可能变多都会影响下一轮选择阶段的 UCB1 打分。所以回溯阶段不是简单的“记录一下”它是整个搜索算法学习进化的关键——每回溯一次树的统计信息就更新一次后续选择就更有依据。考试时如果让模拟一轮你画树标注每个节点的胜/败最常见错误就是漏更新根节点或者只看路径上的节点不更新。记住路径上每个经过的节点都要更新一个都不能漏。我把四阶段浓缩成一张“流程小抄”阶段在做什么是否改变树结构关键统计量选择用UCB1从根往下挑路径否维护访问次数、胜率扩展给未展开节点新增一个子节点是增加1个节点新节点初始0/0模拟从新节点随机下到终局否产生临时结果回溯路径所有节点统计更新否统计量更新访问1胜利按结果1/03. UCB1公式与UCT算法考试得分点全在这3.1 UCB1每一项的含义从第一性原理理解很多同学背公式背得溜但一被问“为什么分子分母放在这”就卡壳。期末复习别做这种“嘴上会了”的假把式。我们把 UCB1 拆开揉碎了看顺便应付论述题。第一部分v_i w_i / n_i就是被评估节点的胜率。这个胜率是历史模拟出来的经验它代表“我们已经知道的部分”。如果只看胜率选节点那就叫纯贪心策略问题在于一个节点可能只模拟了一次、恰好赢了胜率100%另一个节点模拟了一百次、胜率60%你怎么知道那个100%一定更好它很可能只是样本太少带来的虚假繁荣。于是第二部分就出来救场了sqrt( ln(N) / n_i )。这个项在 n_i 很小的时候会特别大给那些“试得太少”的节点加大分鼓励算法去试探它们随着 n_i 变大这个加分项快速缩小算法开始侧重于“已经被验证靠谱”的节点。这个思想在算法领域有个专门称呼——探索-利用权衡无论RL还是推荐系统都会遇到。参数C就是用来调节两个部分的权重的。C越大越喜欢探索C越小越倾向利用。理论上 Csqrt(2) 能保证遗憾界最优出自 Auer 等人的论文但实际应用比如AlphaGo里C经常要调。3.2 完整算法流程的伪代码复现考试不会让你默写整个MCTS但可能会给你伪代码填空或者让你判断某个写法对不对。所以我给你一份标准伪代码你拿它对照复习考试时看到碎片化表述能快速归位。def mcts(root, iterations): for _ in range(iterations): node root # 1. Selection while node.is_fully_expanded() and not node.is_terminal(): node best_child(node) # 2. Expansion if not node.is_terminal(): node node.expand() # 3. Simulation result simulate_random_playout(node) # 4. Backpropagation while node is not None: node.visits 1 node.wins result node node.parent def best_child(node): best None best_score -float(inf) for child in node.children: score child.wins / child.visits C * math.sqrt(math.log(node.visits) / child.visits) if score best_score: best_score score best child return best这个伪代码里有几个细节值得抠一下while node.is_fully_expanded() and not node.is_terminal()选择阶段唯一会停下来的条件要么节点不是完全展开还有没试过的子节点要么直接到终局了。simulate_random_playout返回的是从当前节点视角看的结果视角要是搞错了回溯加分会全错。比如从黑棋视角模拟赢了返回1输了返回0那么回溯路径上每个黑棋节点加的都是1/0但要是路径上有白棋节点逻辑怎么处理需要在一开始就约定清楚。考试做计算题通常用“当前模拟节点的视角”统一处理按题目说明来就行。UCB 公式里的math.log(node.visits)如果某个子节点访问次数为0分母炸掉。工程实现时通常先给所有未访问子节点一个“无限大”的UCB值保证每个子节点至少会被访问一次。考试题目一般不会故意为难你但面试题可能会问“n_i0怎么办”。3.3 为什么要选UCT这个上界而不是简单加权教材里管这种结合了UCB的MCTS叫UCT算法Upper Confidence bounds applied to Trees。把UCB上置信界应用到树搜索上核心保证是每个节点被选择的次数会渐进收敛到它的真实价值最优分支。为什么用“上界”因为 UCB 公式给出的不是一个确切的胜率而是一个置信上界——你可以理解成“这个节点表现的上限估计”。选择上界最高的节点就能在探索的同时不放走真正最优的选择。而随着模拟次数增多所有子节点访问次数都增多这个上界会不断向真实胜率收缩最终锁死到最优分支。这一层在考试论述题或概念辨析题中经常出现。你和A去做对比A靠启发函数给的估计值做排序梯度下降靠导数方向做更新MCTS则靠统计置信界来平衡探索和利用各自思路完全不同但都在“如何高效地找好解”这个母题下。期末简答题如果问到“MCTS为什么能高效搜索巨大博弈空间”答“通过UCB公式平衡探索与利用用统计采样代替全空间展开并且渐进收敛到最优策略”就是满分骨架。4. 拿一个简单博弈把算法完整走一遍4.1 简化场景设定井字棋的最简版本学算法只看公式很容易陷入“每个字都认识但串起来不会算”的状态。我带你手推一个小例子。考虑一个极度简化的“单步井字棋”。假设根节点状态下有两个可选动作 A 和 B。MCTS已经跑了若干轮当前搜索树统计如下根节点访问次数 N10子节点 A胜利次数 w3访问次数 n5胜率0.6子节点 B胜利次数 w2访问次数 n3胜率约0.667取探索系数 C1简化计算不是理论最优。4.2 一整套手算推演喂到你完全会算现在开始第11轮迭代。选择阶段根节点不是终局且完全展开A、B都已被访问过进入选择。分别计算两个子节点的UCB1A的UCB 0.6 1 × sqrt( ln(10) / 5 )B的UCB 0.667 1 × sqrt( ln(10) / 3 )ln(10)≈2.3026。A的探索项 sqrt(2.3026/5)sqrt(0.4605)≈0.6786UCB≈1.2786B的探索项 sqrt(2.3026/3)sqrt(0.7675)≈0.8761UCB≈1.5428B的UCB更高所以选择阶段选定走B在树上走到B节点。扩展阶段B节点如果还不是终局并且它还有未访问过的子动作比如B节点下还有动作X没被展开过于是从B节点的候选动作里挑一个比如X把新节点X加入搜索树X的初始统计量为 w0n0。模拟阶段从X节点开始随机下棋到终局。假设这次随机模拟的结果是X这方输了。记录 result0。回溯阶段沿B→根路径更新X节点w0n1B节点w202n314根节点n10111注意X节点自己也要更新尽管它初始是0/0但作为本轮扩展出的节点也必须纳入统计。更新后B胜率从2/3降为2/40.5。此时如果再做一轮选择A的胜率0.6高于B的0.5A的UCB可能就会把B压过去。这就是MCTS的自我修正过程——模拟结果会动态改变后续决策。这个例子我建议你亲自拿纸笔推一遍推完你对“选择→扩展→模拟→回溯”就不会只是死记顺序而能理解每步在动什么数字。4.3 迭代多次之后我们拿什么做最终决策搜索迭代了很多轮之后根节点该选哪个动作有两种策略看题目怎么要求max child直接选平均胜率最高的子节点。简单但方差大容易受噪声影响。robust child选被访问次数最多的子节点。这种策略更稳因为访问次数多意味着它在大量模拟中被验证过统计上更可靠。严格说robust child 是实际应用中更常用的选择。在AlphaGo的实现里最终落子选择的往往是访问次数最多、而非胜率最高的分支原因就是访问次数本身就是“被算法多轮选中的证据”融合了探索和利用的结果。期末如果出选择题问“MCTS最终决策选哪个子节点”常规答案是“访问次数最高的那个”有时候题干会说“选胜率最高”你按题干给的标准回答就行。这里不用钻牛角尖但可以在主观题里体现一下你懂两种策略的取舍。5. 必考数学表达与理论分析复习到这里心里才踏实5.1 UCB1 的数学推导与遗憾界如果你复习时间充裕顺便看一下 UCB1 为什么写成这样论述题里多写两句理论深度会显得不一样。Hoeffding不等式给了一个很直接的推导线索设某个子节点i的真实胜率为 μ_i当前模拟估计的胜率为 v_i那么通过大量样本估计的误差可以被概率不等式约束。UCB v_i sqrt( ln(N) / n_i ) 本质上就是给这个误差界一个上界。这意味着真实 μ_i 很大概率不会超过当前估计加上这个探索项。算法选择上界最大的节点就相当于同时保证历史表现好的分支会被利用历史样本少的分支也有机会被探索而不是因为“还没被试出来”就被彻底忽略。遗憾界Regret的结论可以这样记经过T轮模拟选择策略累积遗憾的增长被控制在 O(√(T log T)) 量级。对比纯贪心的线性遗憾这个结果说明 UCT 策略长期来看不会“一条道走到黑”而是能不断自我修正。5.2 为什么说MCTS是任意时间算法MCTS还有一个很工程化的优点它是anytime algorithm意思是随时可以停下来给你当前的最优答案。你要它迭代10次给你一个答案它可以要它迭代100万次也可以。搜索时间越长答案质量越高但不会出现“没跑完就完全没结果”的尴尬。这一点在期末复习时容易被忽略但特别重要。相比A*必须搜索到目标才敢停MCTS可以随时给出当前统计最优解这也是它能用在实时博弈程序里的原因。5.3 收敛性与局限性的双面思考收敛性方面理论上当模拟次数趋于无穷MCTS选择的节点会收敛到真正的最优动作。但实际场景中模拟次数有限加上随机策略的模拟质量可能不高收敛速度会受影响。正因为如此后续研究才把“模拟策略”从完全随机改成“快速走子策略”用少量领域知识提高模拟质量这是考试可能提的进阶考点。局限性方面MCTS存在几个明显短板简答题可能会让你列举在分支因子极高、奖励信号稀疏的问题中随机模拟效率极低。没有很强的约束机制去避免反复探索明显的坏分支虽然UCB在一定程度上缓解但不够。对于双人零和博弈效果很好但推广到一般决策问题比如非零和博弈需要额外设计。这些缺点不是要你背下来而是帮你建立对算法适用范围的直觉考试遇到“MCTS不适用于哪种场景”这类题就能答出“分支因子特别大但结果稀疏、需要大量模拟才能得到有效反馈的场景”。6. 现实应用与代码落地的串联6.1 从AlphaGo到游戏AIMCTS挑大梁如果你关注过AlphaGo那就知道MCTS是它的核心技术骨架之一。AlphaGo的突破点在于把MCTS和深度神经网络结合策略网络指导选择和扩展价值网络指导模拟阶段的评估大幅减少了随机模拟的盲目性。没有MCTSAlphaGo只有神经网络给出的“感觉”无法系统化地推演多种变化。MCTS在棋类游戏之外也遍地开花即时策略游戏比如《星际争霸》的AI脚本、卡牌游戏《炉石传说》AI、甚至机器人运动规划都能看到它的身影。期末论述题如果问“MCTS的实际应用有哪些”拿AlphaGo举例最稳妥再补一个“简化版可应用于井字棋、五子棋小游戏AI”就够接地气。6.2 简化版Python代码演示井字棋AI思路代码不要求你在考场上默写但复习时能在本地跑一跑你对算法的理解会完全不同。这里给一个极其精简的实现骨架方便你对应章节概念。import math import random class Node: def __init__(self, state, parentNone): self.state state self.parent parent self.children [] self.visits 0 self.wins 0 def is_terminal(self): return self.state.is_game_over() def is_fully_expanded(self): return len(self.children) len(self.state.get_legal_actions()) def expand(self): legal self.state.get_legal_actions() tried [child.state.last_action for child in self.children] untried [a for a in legal if a not in tried] action random.choice(untried) next_state self.state.move(action) child Node(next_state, parentself) self.children.append(child) return child def ucb1(node, cmath.sqrt(2)): if node.visits 0: return float(inf) return node.wins / node.visits c * math.sqrt(math.log(node.parent.visits) / node.visits) def best_child(node): return max(node.children, keyucb1) def simulate(node): state node.state while not state.is_game_over(): state state.move(random.choice(state.get_legal_actions())) return state.winner() def mcts(root, iterations1000): for _ in range(iterations): node root while node.is_fully_expanded() and not node.is_terminal(): node best_child(node) if not node.is_terminal(): node node.expand() result simulate(node) while node is not None: node.visits 1 node.wins 1 if result node.state.current_player else 0 node node.parent return max(root.children, keylambda n: n.visits)有两点值得说第一ucb1里对node.visits 0返回无穷大这正是前面说的“保证每个节点先被至少访问一次”的工程处理。第二simulate和wins的分支更新逻辑是按“当前节点视角”写的实际项目里要小心对齐视角否则回溯时加分方向就反了。6.3 复杂度与调参思路期末未必考但懂了好做事MCTS每轮迭代的复杂度主要消耗在选择和模拟这两步选择阶段要看每个子节点算一次UCB和当前节点的分支因子成正比模拟阶段取决于棋局深度。整体上它不需要显式枚举完整搜索树所以避免了BFS/DFS那种指数级空间消耗。实际使用MCTS最重要的参数就是这个 C。C取太小算法容易过早锁定一个分支探索不足C取太大算法会像无头苍蝇一样到处乱试迟迟不收敛到一个好策略。一个可行的调参方法是先用小规模随机对局做网格搜索比较不同C值下的胜率或者用“先大后小”的策略前期多探索后期多利用。项目里通常还会限制模拟次数或者时间预算让算法成为真正的anytime算法。7. 期末实战典型题型、易错点与速记清单7.1 考试常见出题方向汇总根据这门课的常见考法我把MCTS相关的出题方向列在下面概念简答题“简述蒙特卡洛树搜索的四个阶段”“说明UCB公式中每项含义”计算推演题给一棵带统计量的搜索树要求模拟1-2轮写出被选中的节点、新增节点和更新后的统计量对比分析题MCTS和A*、和纯蒙特卡洛方法的联系与区别应用分析题为什么AlphaGo使用MCTSMCTS与深度网络是如何结合的其中计算推演题是最容易失分的因为细节多。下面专门给你避坑清单。7.2 做题避坑清单都是前人用分换来的选择阶段的起点一定是根节点不是从上次扩到的节点继续而是每一轮都从根出发重新选路径。C的取值看清楚题目给没给C直接影响选择结果题目不给你就默认真实考题里最常用的 sqrt(2)但计算题一般会给。回溯路径别漏节点从扩展出的节点一直更新到根每一个祖先都要更新访问次数胜利次数按结果加1或加0。区分“节点访问次数”和“模拟次数”一次MCTS迭代包含一次模拟但路径上每个节点访问次数都加1所以根节点访问次数等于迭代次数这在验证自己推演是否正确时是很好的检查手段。ln 的计算用自然对数别用常用对数这是最离谱的丢分点没有之一。7.3 一张表帮你记住关键考点考点必备回答要点为什么用UCB1平衡探索与利用避免过早陷入局部最优四阶段顺序选择→扩展→模拟→回溯模拟与回溯的关系模拟产生结果回溯负责把结果传播回路径最终决策方式访问次数最多优先胜率作为辅助参考应用代表AlphaGo结合深度网络做策略价值评估7.4 考前速记口诀期末复习到最后一个晚上脑子里塞不下长段落我送你一套自编的速记口诀按MCTS的流程走一选二扩三到底随机rollout出输赢统计一路往回灌路径节点都要更UCB一加一根号探索利用都兼顾。“一选二扩三到底”对应选择、扩展、模拟“统计一路往回灌”对应回溯“UCB一加一根号”帮你记住公式结构前两项分别对应利用和探索。期末复习这件事最怕就是每个概念都“好像会了”一到手算就露馅。MCTS跟前面的搜索算法相比最大的特点就是“靠数据说话”所以你在复习时一定要亲自动手推几轮迭代把统计量变化算到和自己代码跑出来一致才算真的掌握。这套内容学完以后不管是在游戏AI、机器人决策还是面试题里碰到MCTS你都能知道它本质上就是个“用随机采样做树搜索决策”的方法公式只是它的外衣。这个理解比背多少遍定义都值钱。