期末复习到这里很多同学会在“第3章 搜索求解”的最后一部分卡住前面刚把A*、启发式函数搞得焦头烂额突然来了个“蒙特卡洛树搜索”英文叫Monte Carlo Tree Search简称MCTS。教材上写着它是AlphaGo的核心组件之一但看半天也不知道它到底“搜”了个什么。更要命的是它既不像广度优先那样一层层扫也不像深度优先那样一条路走到黑反而带着一股浓烈的“随机碰运气”的味道——这和我们前两讲学的东西画风完全不同。先说结论蒙特卡洛树搜索是一个用“随机模拟”来替代“启发式评估”的搜索框架。它特别适合那些状态空间大到没法穷举、又找不到好用的估价函数、但能快速模拟出胜负结果的场景——比如棋类AI、游戏AI、机器人决策这类问题。对于正在备考人工智能引论的同学来说这一块是期末考试的重点也经常被用来当大作业选题对于想系统理解现代博弈AI的人来说它是理解AlphaGo、AlphaZero系列设计思路的第一块基石。这篇文章我按自己的复习思路来写先讲清楚MCTS在搜索求解这条主线里处于什么位置再把四步循环拆开揉碎最后用一个井字棋的实例带你亲手算一遍UCB公式和回溯更新。中间穿插我实际写代码和刷题时踩过的坑争取让你看完之后不是“背会了”而是“真的会了”。1. 期末复习先定位MCTS在搜索求解里的角色1.1 之前学的搜索方法有什么解决不了的问题在搜索求解这一章的前半部分我们处理的是这类问题给定一个图从起点出发用广度优先搜索、深度优先搜索找到目标节点或者用A*结合启发式函数让搜索路径更聪明。这类问题的共同点是状态空间是“明牌”——你知道整个地图、所有节点和边搜索就是在这些已知结构里找目标。但到了博弈类问题情况就变了。以围棋为例棋盘上有19×19个交叉点每一步可能落子的位置接近361个一盘棋通常要下200手以上。理论上我们也可以用DFS或BFS从当前局面出发把所有可能的对局全部推演一遍但状态数量大约是10的170次方比已知宇宙中的原子总数还多。这时候“明牌搜索”直接宣告失效——你根本建不出完整搜索树。另一个麻烦是很多博弈状态下我们找不到一个可靠的启发式函数。象棋里可以用棋子分值大概评估局面但围棋中一个局面的好坏很难用简单的打分公式来衡量。没有启发函数A*那一套就无从用起。那怎么办呢一个朴素的思路冒出来了既然我不能精确算出“走这步棋到底好不好”可不可以大量地“随便下”用统计结果来推测哪一步更好这就是蒙特卡洛方法的核心思想——用随机采样的平均值来逼近真实值。1.2 MCTS的思路把“评估局面”变成“统计胜负”你可以把MCTS理解为让计算机把棋局“快进”很多次。每一次快进都从当前局面出发先按照某种策略走几步下到某个值得关注的节点然后剩下的棋局全部随机乱下直到分出胜负。如果某个开局选择在大量随机对局中赢的次数更多我们就认为它更可能是好棋。很多人第一次看到这里会产生疑惑随机下棋的结果能说明问题吗我的理解是这样的一个真正的好棋即使在后续走法很随意的情况下也应当有较高的胜率而一个坏棋即使后面的对局碰运气也容易被对手翻盘。所以“随机模拟”其实是在用大量样本抹平运气成分让“局面本身的优劣”从胜率统计中浮出水面。MCTS的完整名字里有“树搜索”三个字因为它在进行统计的同时确实维持了一棵搜索树。只不过这棵树不是一次性建好的而是“用多少建多少”——每一轮迭代就向树里增加一个节点不断朝着看起来最有希望的方向生长。这种“一边探索一边建树”的方式既能控制计算量又能把算力集中到少数有潜力的分支上非常符合人类棋手“对关键变化多算几步”的习惯。1.3 它到底解决了什么问题以及期末会怎么考从考试角度看第3章关于MCTS的重点就三块第一能用一两句话解释MCTS的基本思想第二能把四步循环选择、扩展、模拟、回溯完整写出来第三会计算UCB1公式并判断该选哪个节点。部分考计算题的学校还会给你一棵部分搜索树和访问统计量让你手算一次迭代。从应用角度看MCTS不仅用在棋类游戏中也广泛应用于路径规划、机器人运动控制、超参数自动调优、量子电路优化、分子结构搜索等场景。它之所以这么“百搭”是因为它不需要问题本身具备好的导数或梯度信息也不需要启发式函数只要你能定义出“状态、动作、模拟到终结并给结果打分”这三件事MCTS就能拿过来用。对了如果你在找大作业题目MCTS做一个五子棋、黑白棋、井字棋AI是经典选择工作量适中可视化效果也好看还能在报告里讲清楚原理。2. 四步循环拆解选择、扩展、模拟、回溯MCTS的每一次迭代都由选择、扩展、模拟、回溯四个阶段组成。这四个词基本绑定了所有考卷上的简答题我建议你把英文也记一下Selection、Expansion、Simulation、Backpropagation。2.1 选择沿着“最值得探索”的路径往下走选择阶段的目标是从根节点当前局面出发顺着搜索树一路向下找到一个“还没被完全探索”的节点。这有点像你在一棵树上寻找一根没被折断的树枝——但关键在于到底选哪根树枝往下走MCTS不会每根树枝都平均分配探索次数而是使用一个叫UCB1的公式来打分每次优先选分数最高的子节点。UCB1全称是Upper Confidence Bound它长这样UCB1 \frac{W_i}{N_i} C \times \sqrt{\frac{\ln N}{N_i}}其中W_i是子节点i的累计获胜次数N_i是子节点i被访问的次数N是当前父节点被访问的总次数C是探索系数通常取\sqrt{2}≈1.414。这个公式是期末计算题的绝对核心。我拆开讲第一项\frac{W_i}{N_i}是“胜率”代表这个节点目前表现有多好。胜率越高越值得选——这叫做“利用”exploitation。第二项C \times \sqrt{\frac{\ln N}{N_i}}是“不确定性奖励”。如果一个子节点被访问的次数N_i很少那么\sqrt{\frac{\ln N}{N_i}}就会很大公式会给它加分鼓励你多去看看这个“还没摸清底细”的分支——这叫做“探索”exploration。C就是调节这两者权重的旋钮。C设得大探索欲望强搜索更平均C设得小更倾向于选择当前胜率高的节点搜索更“短视”。教材里默认取\sqrt{2}考试没特殊说明就按这个来但题目如果明确给了不同的C值你就按题目的来。选择阶段有一个循环判断如果当前节点还有未扩展过的子节点或者已经到了终局就停止选择否则就继续在它的子节点里用UCB1挑下一个。也就是说我们要一路走到“最底部的非叶子节点”或“未完全展开的节点”为止。2.2 扩展给搜索树加一个新节点找到那个节点之后如果它没有走到终局状态就可以扩展从这个节点出发挑选一个“尚未生成子节点”的合法动作在树中创建一个新的孩子节点。这个动作通常是随机选的也可以用一些简单规则辅助筛选。扩展这一步很轻量但有一个容易在考试里混淆的点扩展一次只增加一个节点不是一下子把当前节点的所有子节点全部生成出来。搜索树的每一个节点对应一个局面每一条边对应一个合法落子动作只有在后续迭代中再次走到这个节点时才会考虑继续扩展它的其他孩子。另外要注意如果选择阶段已经走到了一个终局节点比如棋已经下完分出胜负那就不需要扩展了直接进入模拟阶段。严格地说这时候模拟阶段也可以省略——结果已经确定直接把这个结果回溯上去就行。2.3 模拟随机下到终局得到随机胜负结果模拟阶段又叫Rollout或Playout。从刚刚扩展出来的新节点对应的局面出发双方轮流随机选择一个合法动作一直下到分出胜负或平局得到一个结果赢、输或者平。这里最容易引起误区的是“随机”两个字。很多初学者以为模拟就等同于“均匀随机乱走”其实不一定。模拟时使用的快速策略可以多种多样最简单的就是纯随机每一步在所有合法动作中均匀随机选一个。更高级一点可以用“偏向策略”比如五子棋模拟时优先考虑落子位置靠近已有棋子或者优先考虑能形成活三、冲四的位置。在AlphaGo的原始版本里模拟部分还会用一个轻量级的快速走子策略网络来指导随机方向。模拟策略越贴近真实对局胜率估计就越准但策略越复杂单次模拟耗时越长。所以工程上要在“模拟速度”和“模拟质量”之间做取舍。对考试来说你可以默认模拟就是随机走棋直到终局。模拟阶段的另一个重要细节是模拟时不需要把每一步都加入搜索树。模拟过程中的所有节点只是“走个过场”并不会永久保留在树里。只有扩展阶段产生的那个新节点会被正式挂到树上模拟只是给这个节点带回一个结果值。2.4 回溯把胜负结果沿原路传回去更新统计数据回溯阶段的任务很简单把模拟得到的胜负结果从刚扩展的节点开始沿着“选择阶段走过的路径”一路向上传播更新路径上每个节点的数据。每个节点要更新两个量N_i访问次数加1。你每走一次这条路路径上所有祖先节点都多了一次“被访问”记录。W_i若是本方胜利W_i加1如果输棋W_i不变或者按具体计分规则加分。在平局情况下可以给0.5的收益具体看题目的计分规则。这里有一个非常关键、也非常容易在考试和编程中犯错的点视角转换。我们保存每个节点的胜场W_i必须统一用“轮到该节点所在局面的那一方”视角来计数。举个例子当前轮到黑棋行棋模拟结果黑棋赢了那么从根节点到某个中间节点中间节点可能对应的是“轮到白棋行棋”的局面。对于白棋视角的节点来说黑棋胜利就是白棋失败如果把1直接传上去正负号就乱了。正确做法是每向上一层如果行棋方发生了切换收益的正负号也要翻转。考试中如果题目没有特别说明通常默认根节点视角你只要记住“上一层若是换对手走了胜利方向就反过来”就行。回溯完成之后本轮迭代结束下一轮重新从根节点开始执行这四个步骤。随着迭代次数增加搜索树慢慢生长节点的访问次数和胜率统计越来越稳定最终根节点的最优选择往往就是访问次数最多、胜率也最高的那个子节点。3. 手把手推一次完整迭代从UCB计算到回溯更新光背公式肯定不够我来带你把一次完整的MCTS迭代走一遍。为了手算方便用井字棋Tic-Tac-Toe作为例子。假设当前轮到玩家X走搜索树已经建立了根节点R它有三个孩子节点A、B、C分别对应三种不同的落子动作。树中已有的统计量如下节点访问次数N_iX视角下的胜利次数W_i平均胜率W_i/N_iA1070.7B850.625C520.4根节点R的总访问次数N_R 108523。设探索系数C\sqrt{2}≈1.414。下面计算三个子节点的UCB1值A0.7 1.414×\sqrt{\frac{\ln 23}{10}}B0.625 1.414×\sqrt{\frac{\ln 23}{8}}C0.4 1.414×\sqrt{\frac{\ln 23}{5}}代入ln23≈3.135A的探索项 1.414×\sqrt{0.3135}≈1.414×0.56≈0.79总得分约1.49B的探索项 1.414×\sqrt{0.3919}≈1.414×0.626≈0.88总得分约1.50C的探索项 1.414×\sqrt{0.627}≈1.414×0.792≈1.12总得分约1.52C的UCB1最高所以这一轮选择阶段走到C节点。虽然C目前胜率最低但因为访问次数少公式给它加了很高的“探索奖励”这正好展示了MCTS不会放过冷门但可能有潜力的分支。走到C节点后发现C还有未扩展过的合法动作假设它目前只建立了两个子节点D和E但还有第三个合法动作没试过。扩展阶段随机挑一个未尝试的动作生成新节点D。然后模拟阶段从D对应的局面开始让X和O随机乱下直到终局。假设这次模拟结果是“X胜利”。回溯开始。从D开始向上更新D访问次数从0变成1胜利次数W_D从0变成1。C访问次数从5变成6。由于模拟结果是X胜而C是X行棋后的节点以X视角记录C的胜利次数从2变成3。继续向上到根节点RR是X开局后的根节点X胜利R的胜利次数也1整体访问次数从23变成24。完成。这时搜索树多了一个节点DC的胜率从0.4略微提升到了3/60.5A、B、D的统计也都变了。下一轮迭代开始时由于C的访问次数变多了它的探索奖励会下降其他节点的排名可能又会发生变化。我把这个例子中“不同探索系数导致不同选择”的情况也算一下方便你理解C的意义。若把C从\sqrt{2}调低到0.5重新算UCB1A0.7 0.5×0.56≈0.98B0.625 0.5×0.626≈0.94C0.4 0.5×0.792≈0.80这时A胜出。这说明C调小时算法更倾向于选择当前胜率高的A节点“利用”占了上风C调大时会更多尝试访问量少的C节点也就是“探索”占了上风。这个手算例子在期末复习时特别值得自己多走两遍。我当年复习时第一次看到UCB公式觉得难看但当我用一个9×9简化棋盘手推了三轮迭代后整个框架就通了。考试遇到类似的题先列公式、再代入数据、再判断选择基本分就能稳稳拿到。顺便说一句如果你要自己写代码实现MCTS最核心的数据结构可以这样设计class MCTSNode: def __init__(self, state, parentNone, actionNone): self.state state # 当前局面 self.parent parent # 父节点 self.action action # 从父节点进入本节点的动作 self.children [] # 孩子节点列表 self.visits 0 # 访问次数 N self.wins 0 # 胜利次数 W self.untried_actions state.get_legal_actions() # 尚未尝试过的动作列表 def is_fully_expanded(self): return len(self.untried_actions) 0这个结构简单直接做井字棋级别的MCTS完全够用。等你要做更大规模的棋盘时再考虑把局面编码成向量、加进神经网络之类的优化。4. 期末高频考点与实操避坑清单4.1 简答题怎么答才能既不丢分又不啰嗦期末简答题里最常见的问法是“简述蒙特卡洛树搜索的基本流程”或者“说明MCTS四个阶段分别做了什么”。这类题我建议你按“总-分-总”的逻辑答先一句话交代思想MCTS通过在搜索树中反复执行“选择→扩展→模拟→回溯”用大量随机模拟得到的统计胜率来评估各个候选动作的优劣。然后分阶段展开选择阶段用UCB1公式在已有树内挑选最值得深入的节点扩展阶段为选中的节点增加一个新的孩子节点模拟阶段从新节点开始用快速随机策略对弈到终局并记录结果回溯阶段将结果沿路径回传更新各节点的访问次数和胜利次数。最后补一句随着迭代次数增加胜率统计趋于稳定最终选择访问次数最多或胜率最高的子节点作为实际动作。还要注意区分“模拟”和“回溯”的顺序模拟是得到结果回溯是把结果写回树。我见过不少同学把这两个词写反丢分很可惜。除了四步流程还有一些高频概念辨析比如“MCTS与A的区别”。你可以这样答A依赖启发式函数对节点估值MCTS依靠随机模拟统计胜率A*适用于状态空间相对小、启发信息容易获得的组合优化问题MCTS更适合大规模博弈决策问题。4.2 计算题的常见陷阱这三个地方最容易丢分第一忘记转换视角。前面讲过回溯到不同层时行棋方会切换胜利次数W的正负号要用统一视角记录。考题如果给你一棵现成的树通常会直接标好“胜率以根节点行动方视角统计”你按这个处理就行如果题目没明说就以根节点的行动方为准。第二混淆N是父节点总访问次数还是所有子节点访问次数之和。UCB公式里的N指的是当前节点也就是做选择时所在的父节点的总访问次数一般等于它所有子节点访问次数之和。题目如果给了父节点的visits直接用它如果只给了子节点统计就把它们加起来。第三搞错C的取值。在没有额外说明时用\sqrt{2}。但有的考题会故意把C设成0或特别大的数让你观察选择结果的变化。C0时蒙特卡洛树搜索退化成纯利用只选胜率最高的节点C非常大时探索项占主导几乎变成均匀随机探索。碰到这种题别慌代进公式算就完了。4.3 代码实现MCTS时新手最容易踩的四个坑第一个坑节点扩展后忘记把动作从untried_actions里移除。这样同一个动作会被反复扩展搜索树里出现重复子节点统计全部错乱。每当你创建一个孩子节点一定要从父节点的“未尝试动作列表”中删除对应动作。第二个坑回溯时仅更新了叶子节点没有把祖先节点的visits全部1。这会导致父节点的访问次数N不准进而影响后续UCB1公式中\frac{\ln N}{N_i}的计算。正确做法是写一个循环从当前节点一路popleft到根节点层层更新。第三个坑模拟阶段用了和正式规则不同的规则比如落地规则写错、胜负判断遗漏和棋。模拟的规则必须和真实对局完全一致否则统计胜率只是自欺欺人。我调试五子棋MCTS时曾经模拟里漏了“长连禁手”的判定结果AI在特定局面下总走出明显坏棋排查了很久才找到是规则不一致。第四个坑选择阶段不考虑“终局节点”。如果某个节点已经分出胜负它没有子节点也没法再扩展万一当前根节点本身就是终局那根本就没必要跑MCTS。写代码时要在选择循环里加一个“if node.is_terminal(): break”防止程序访问不存在的子节点。4.4 结合其他章节一起复习效果会更好MCTS不是孤岛。它和前面的“对抗搜索”章节有直接联系极大极小算法用Min-Max值和Alpha-Beta剪枝确定最佳走法代价是需要遍历全部搜索树MCTS则用统计手段绕开了“全树遍历”本质上是在“大幅度牺牲完整性换取深度的适应性”。如果考试问“为什么大型棋类不用Min-Max而用MCTS”你就要从“搜索空间爆炸”和“没有可靠启发式评估”两个角度回答。结合其他博弈算法对比记忆时可以做一个小表算法是否需要启发式函数是否遍历完整搜索树适用场景Minimax Alpha-Beta剪枝通常需要是剪枝后依然要访问大量节点搜索深度可控的棋类MCTS UCB1不需要否按需生长大规模博弈、实时决策另外如果在学AlphaGo相关科普记住一句话就够AlphaGo 深度神经网络 MCTS。深度神经网络负责提供先验概率和局面评估MCTS负责把这两种信息变成有序的搜索策略。期末不会深究细节但作为背景知识能让你回答“MCTS在现代AI中的应用”时更有底气。4.5 期末复习节奏的小建议最后说说我自己复习这一章的节奏。先花半小时把教材里MCTS的四步流程图和公式看懂再找一张A4纸照着井字棋示例自己手推两轮迭代然后找一个已经在课程群里流传的MCTS计算题做一遍。如果时间充裕动手写一个井字棋程序的MCTS实现不必追求代码多好能用就行——把选择、扩展、模拟、回溯四个函数分别写出来再跑几百次迭代看看棋力有没有提升。这个过程比刷十道题都管用。我个人踩过的最大坑就是一开始把复习重点放在了背诵公式上却一直没亲手推演过完整迭代。结果上考场遇到一道“给一棵树、给统计量、让你算下一轮选哪个节点”的题公式背得滚瓜烂熟代入时却连谁是谁的父节点都没看清。所以这次复习我特别建议你把重点放在“顺着树走一遍流程”上而不是干看公式。如果你正在准备大作业答辩有个小经验可以分享准备一个你自己修改过探索系数C的对比实验。比如分别用C0.3、C1.414、C2.5跑同一盘棋记录AI落子倾向和胜率变化最后在报告里解释为什么要平衡探索与利用。这个细节会让老师觉得你是真的理解了MCTS而不只是调了个库。