蒙特卡洛树搜索实战：从UCT公式到代码实现与优化

第一次让一个只会随机下棋的程序通过蒙特卡洛树搜索在几秒钟内超过我自己手工编写的策略逻辑时我对这种看起来“碰运气”的算法彻底改观了。后来在棋盘游戏引擎、资源调度和机器人路径规划里反复使用它我必须说蒙特卡洛树搜索Monte Carlo Tree Search简称MCTS是我见过最优雅的通用决策算法之一代码量不大却能在分支因子极高的搜索空间中用统计抽样的方式逼近足够好的决策。这篇文章不打算讲成论文我会从“为什么要用它”“它的四个阶段到底在干嘛”“UCT公式怎么理解”“怎么从零写出能跑的代码”这几个角度展开最后聊聊我在工程和竞赛里踩过的一些坑。不管你是刚接触博弈树的新手还是已经会写minimax但想换一条路的老手这篇内容都可以直接当参考。1. 先搞清楚蒙特卡洛树搜索到底在解决什么问题1.1 搜索树与Minimax的边界在MCTS出现之前解决这类“轮流决策”问题最主流的工具是minimax加alpha-beta剪枝。它的逻辑很漂亮把我方收益最大化、对方收益最小化然后沿着博弈树往下搜索。当搜索深度受限时再用评估函数做静态打分剪枝则负责砍掉明显不优的分支。这套方案在象棋、国际跳棋这类游戏里统治了很多年。但有一个硬伤当每一步的可行动作非常多或者局面极其开放时博弈树会以指数级膨胀剪枝也救不回来。比如围棋状态空间大到传统搜索完全无法靠深度优先遍历找到好棋。另一个问题是很多真实决策问题根本没有清晰的“胜负”评估函数外部环境还有大量随机性这种情况下手工设计启发式非常痛苦。蒙特卡洛树搜索的思路完全不同不追求把整棵树都展开而是用随机抽样来“估计”一个节点的胜率。它的核心信念是一个局面好不好可以通过大量随机模拟的结果来判断。这就把“评估函数设计”这个老大难问题变成了一把“生成足够多的随机对阵”的锤子。1.2 MCTS的直观思路用随机抽样指导选择我不是第一次见这类想法时就能接受。大多数人听到“随机模拟一万次看谁赢得多”都会觉得不靠谱单次模拟的方差那么大怎么可能靠这个选出好棋早期的蒙特卡洛搜索确实有这个毛病纯粹随机摆棋赢了几次就觉得某一步好经常选到非常浅显的陷阱。MCTS真正的突破在于它不搞“平均用力”。它会用树结构记住哪些分支已经被验证过让后续的模拟尽量集中在有希望的分支上同时仍然保留一部分探索空间。这个思想本质上就是计算机科学里最经典的“探索与利用”问题你是继续深挖目前看起来最好的选项还是花一点资源去看看那些没怎么试过的选项MCTS把这个权衡变成了一套优雅的树上策略也就是后面要讲的UCT公式。理解了这一点你就抓住了整个算法的灵魂。后面写的代码、调的参数、做的改进全都是在“探索”和“利用”之间找平衡。2. 四个阶段看懂一棵树怎么“长大”MCTS的每一次迭代可以拆成四个阶段选择Selection、扩展Expansion、模拟Simulation、回传Backpropagation。听起来很正式但拆开看每一步都很简单我一个个说。2.1 Selection每次从根节点往下选一条“最值得”的路从一个根节点出发代表的是当前局面的空树或者小树。Selection的目标是从根节点开始沿着已建好的子树往下走走到一个还没有完全展开、但又值得继续深入的节点。怎么判断“值得”每个节点都保存了两个统计量被访问的次数和累计的胜负分。我们用这两个数算出一个“得分”得分最高的子节点就是当前路径的最佳选择。这个过程一直重复直到我们到达一个叶子节点且这个节点还有没展开过的动作或者它已经是终局。如果某一步的子树还没建完全但某些子节点已经被访问过一次Selection就不会总往同一个方向走因为那个访问次数多的子节点“探索值”会下降其他没怎么访问的子节点会得到更高的探索加分从而被选中。这就是“雨露均沾”的数学实现。2.2 Expansion什么时候新增一个节点走到一个“有潜力但没完全展开”的节点后算法就会从它的未尝试动作列表里挑一个动作生成新的状态再把这个新状态包装成子节点挂到树上。这里有个细节每次迭代只展开一个子节点而不是一下子把所有合法动作全展开。原因很朴素——一下子全展开计算量太大而且很多动作可能根本没意义不如先随机试一个让统计结果决定哪些分支值得被继续深入。这种“渐进展开”的思想也是MCTS能应对高分支因子的关键。我当年的误区是觉得“既然是搜索多展开几个节点总没坏处”。结果发现树的内存和计算开销会迅速失控而且前期大量展开的节点未必有人访问浪费非常严重。按需生长才是MCTS的正确姿势。2.3 Simulation到终点最快的方式从新增的子节点出发算法会启动一次“快速对局”不依靠树结构直接在当前状态下随机选合法动作一路模拟到终局并返回结果胜、负、平。Simulation是整个算法里最耗CPU时间但逻辑最简单的部分。因为它要跑很多次所以性能优化都会盯上这里。一般不会用特别复杂的策略去做随机模拟因为模拟本身只是给树提供统计样本。你可以用均匀随机也可以加入一点简单启发式比如优先走中间、优先吃子但不要做太重的评估——那样会让“每轮模拟”变慢收益却不一定更高。我见过有人把Simulation写成一个深度递归、里面再做一次小搜索的版本结果一轮迭代要几毫秒一万次模拟就卡到怀疑人生。这里记住一个原则模拟要快快比“聪明”更重要。因为统计数量能弥补单次模拟的粗糙。2.4 Backpropagation把结果一层层反馈回树模拟出了结果不代表算法就结束了。还要把这个结果从当前节点一路沿着刚才选中路径传回根节点把路径上每个节点的访问次数都加1胜负分也累加上去。这样下一次Selection才能用更新过的统计量做判断。我觉得这里有一层特别容易被忽略的思想MCTS并不是每棵树都完整“看出”终局之后才决定走哪步的。它是在不断迭代的过程中让状态分布越来越偏向“已知较好的分支”模拟次数越多统计越稳定根节点下一步的选择才越可靠。回传就是让信息流动起来的那条血管。以上四个阶段组成一次完整迭代。通常我们不会设置固定的模拟次数上限而是给定一个时间预算比如“每秒迭代2000次”或者给定迭代次数上限。迭代完成后选择根节点中访问次数最多不是胜率最高的子节点作为最终动作。这个“按访问次数选”的原则后面我会解释。3. UCT公式与探索常数决定走多远、看多细3.1 数学公式逐项拆解MCTS最经典的节点打分公式是UCTUpper Confidence Bound for Trees。它长这样[ UCT \frac{w_j}{n_j} C \cdot \sqrt{\frac{\ln N}{n_j}} ]其中 (w_j) 是节点 (j) 的累计得分(n_j) 是节点 (j) 被访问的次数(N) 是当前父节点的访问次数(C) 是探索常数。你可以把这个公式拆成两块看。左边 (\frac{w_j}{n_j}) 是平均收益也就是“利用”部分历史上越优势分越高。右边则是一个探索奖励当某个节点被访问的次数 (n_j) 很小而父节点访问总数 (N) 很大时(\sqrt{\frac{\ln N}{n_j}}) 会比较大相当于给“还没看够”的分支加分。随着 (n_j) 增大这部分逐渐衰减。实际操作中如果某个孩子节点的 (n_j 0)对数分母会除零这时候直接返回一个无穷大的值保证“没试过的子节点优先被摸一遍”。等到所有孩子都被摸过一轮UCT才真正开始做平衡。3.2 C值到底怎么调探索常数 (C) 就是用来控制探索奖励权重的旋钮。调大C算法更愿意探索看似不佳的分支调小C算法更倾向于使用已经验证过的优势分支。标准取值通常在1.0到2.0之间很多开源实现直接用1.414即根号2但不要迷信这个值它是游戏相关的。我有一个比较朴素的经验先在简单棋盘游戏里跑参数扫描从0.5、0.8、1.0、1.5、2.0各跑一轮对比测试集上的胜率。真实比赛里有时候你把C从1.2调到1.5成绩会有几个百分点的变化这在对抗场景里是非常巨大的优势。C取太小树会像“急功近利”的人一样周围稍微好一点就只往那边钻一旦估计偏差大就可能漏掉隐藏的优步。C取太大树会像一个每天到处乱逛、哪里都好奇但样样不精的人深度永远不够搜索到后期还在大量尝试明显很差的动作。3.3 为什么不是纯随机或纯贪心如果完全随机展开那得到一个巨大的扁平树每个节点都被均匀地模拟等于把“搜索”变成了“抽样”却丢掉了利用历史信息深度挖掘的能力。如果完全贪心总是选当前胜率最高的子节点那只要前几次随机模拟产生偏差就可能被锁在一个局部最优分支里再也出不来。MCTS恰好落在中间。它有两层防护第一层是未访问节点优先保证每步至少被尝试过一次第二层是UCT公式里跟父节点访问次数相关的探索项让长时间没被“翻牌子”的分支有机会被重新考虑。这就是为什么它能在高分支因子环境下仍然保持比较稳定的表现。4. 从零实现一个可运行的MCTS4.1 抽象游戏接口设计如果你想把MCTS用到不同游戏上第一步应该是抽一个通用状态接口而不是把游戏逻辑和搜索逻辑焊死在一起。我习惯把一个状态需要的能力定义成四个方法获取合法动作、执行动作产生新状态、判断是否终局、返回终局结果。以经典的“拿石子”游戏为例一堆石子双方轮流取1到3颗谁取走最后一颗谁赢。这个游戏规则极简非常适合拿来看MCTS的运转。下面是我通常用的界面设计class GameState: 抽象游戏状态接口 def get_legal_actions(self): raise NotImplementedError def apply_action(self, action): raise NotImplementedError def is_terminal(self): raise NotImplementedError def get_result(self): 以先手方视角返回终局结果1.0 胜0.0 负0.5 平 raise NotImplementedError你可能会问为什么要统一成“先手方视角”而不是“当前行动方视角”。因为在Backpropagation时一条路径上不同深度的节点立场相反如果每个节点返回不同视角的胜负累加时还得做符号翻转很容易出错。固定从某一个视角看终局结果回传时直接用统一符号累加代码简单一倍。这是我在第一个自己实现版本里吃过大亏后总结出的经验。4.2 节点类的核心字段与选择函数节点保存的信息不必太复杂。我建议至少保留当前状态、父节点、子节点列表、未尝试动作列表、访问次数、累计得分。不要把“胜率”单独存一个字段因为它是访问次数和累计得分算出来的单独存反而容易出现不一致。class Node: def __init__(self, state, parentNone): self.state state self.parent parent self.children [] self.visits 0 self.wins 0.0 self.untried_actions state.get_legal_actions() def q_value(self): return self.wins / self.visits if self.visits 0 else 0.0 def uct_value(self, c1.4): if self.visits 0: return float(inf) parent_visits self.parent.visits if self.parent else 1 return self.q_value() c * math.sqrt(math.log(parent_visits) / self.visits)这里有一个细节如果unvisited子节点的uct直接返回无穷大那么max在选择时就会优先选中它。如果把返回值设为0可能会被其他访问过的节点压过导致有些分支永远不被尝试。Selection函数则负责从根节点开始沿着UCT最优点下钻def select_best_child(node, c1.4): return max(node.children, keylambda n: n.uct_value(c))标准迭代流程可以选择在当前节点没有未尝试动作且还有孩子时一路下钻def tree_policy(node, c1.4): while not node.state.is_terminal() and not node.untried_actions: node select_best_child(node, c) return node4.3 主循环与模拟策略有了节点和选择策略就能写完整迭代了def mcts_iter(root, iterations1000, c1.4): for _ in range(iterations): node tree_policy(root, c) # 扩展选择一个未被尝试的动作 if node.untried_actions and not node.state.is_terminal(): action node.untried_actions.pop() child_state node.state.apply_action(action) child Node(child_state, parentnode) node.children.append(child) node child # 模拟 result rollout(node.state) # 回传 while node is not None: node.visits 1 node.wins result node node.parent模拟策略可以极简均匀随机选动作即可def rollout(state): while not state.is_terminal(): actions state.get_legal_actions() action random.choice(actions) state state.apply_action(action) return state.get_result()注意我没有在Rollout里创建新节点因为Rollout过程不对树做持久化它只是产生一条模拟轨迹。每轮模拟结束轨迹上的状态就被丢弃了只把最终结果反馈给树路径上的节点。4.4 在“拿石子”游戏上验证写完后我习惯用一个小游戏快速验证“MCTS到底学没学到东西”。拿石子游戏的终局很简单所以跑起来特别直观。我先跑一个对照实验让MCTS迭代1000次然后统计根节点下各个子节点的访问次数和胜率看看它是不是真的偏爱正确的那一步。假设当前石子数是4轮到先手方。那正确策略是先拿走3颗留给对手1颗这样对手只能拿走最后一颗稳赢。换成树视角MCTS应该在经过几百次迭代后对“取3”这个子节点给出最高的访问次数。如果访问次数最高的动作不是“取3”我第一个怀疑方向是UCT的C值设置和模拟策略是否出了问题。对这个只赢不败的简单局面C取1.4甚至2.0都不该失误。出现失误通常意味着访问次数还没收敛或者模拟里产生了不正确的角色胜负统计。我会把迭代次数提到5000再看一次。把MCTS实际接到游戏循环里还有一个常见习惯是第一手动作固定用最大访问次数不按最大胜率选。虽然胜率高的节点“看起来更好”但访问次数多的节点统计更可靠。在高不确定性的搜索场景里鲁棒性往往比“高均值”更重要。尤其是根节点子节点访问次数差异不大时只看胜率很容易被前几次模拟噪声带偏。5. 实战中常见的坑与排查思路5.1 访问次数为0时的除零问题这是新手最常见的运行时崩溃。某个子节点还没有被访问过但它的uct_value里已经做了除法直接抛ZeroDivisionError。解决办法在上面的代码里已经写了把未访问节点的UCT设为无穷大让它必然先于其他节点被选中。这个设计不仅避免崩溃还能加强探索一致性。如果是工程化项目我更建议把无穷大写成float(inf)而不是999999。原因很简单如果有两个未访问节点max遇到相同值时会取第一个这没关系但如果用固定大数万一你的得分本身也可能接近这个数量级比较逻辑就会出问题。用真正的无穷大最安全。5.2 时间预算 vs 模拟次数不少新手会问“到底该迭代多少次”这个问题没有标准答案因为它取决于游戏分支因子、模拟速度和硬件性能。我只建议用时间预算而不是固定迭代次数作为终止条件尤其在比赛场景中双方都需要在统一时间内给出落子。比如给每次决策1秒钟那么在循环开始前记录时间循环里每迭代一定次数检查一下耗时超时就停止。以前我在一个象棋类项目里固定8万次迭代结果换到不同机器上成绩完全不一样后来改成时间预算成绩立刻稳定下来。简单说迭代次数是物理量时间预算才是用户体验。5.3 随机性与结果稳定性MCTS是随机算法同一个局面跑两次选的落子可能不同。这很容易让第一次接触它的人焦虑但其实是它发挥统计优势的前提。如果想调试可以给随机数生成器设置固定种子让每次运行结果可复现。不过生产环境里我建议不要固定种子。因为在竞技场景下固定种子会让对手通过观察你的历史行为预测你的选择偏好。让每次决策保留随机性反而能增加自身的“不确定性”让对手难以针对。尤其在在线对战系统里稳定性不如“不可捉摸性”值钱。5.4 树内存膨胀与对称状态树随着迭代不断上涨节点数可以到百万级内存开始成为瓶颈。一个常见的补救方法是用“每次决策重建根节点池”的机制走完一步棋后把原来代表当前棋盘局面的那个子节点直接提升为新根丢弃兄弟节点。这样做的意思是父节点视角里大部分旧树分支已经没用了他们只会占据内存却没有新的访问机会。另一个可以显著提升效率的思路是合并对称状态。像棋类游戏里棋盘经过旋转或镜像后本质上是同一个局面。我见过一个开源框架在生成子状态时同时计算规范化哈希把同构状态复用同一个节点节点数量直接下降了接近一半。代价是存取哈希表有额外开销如果你本来内存不紧张可以先不急着做。6. 进阶方向从随机模拟到神经网络先验6.1 RAVE与渐进宽化纯随机模拟的MCTS在很多中小型游戏里已经很强但面对非常复杂的游戏时每个模拟都从零开始随机走噪声太大收敛变慢。改进方案里最经典的是RAVERapid Action Value Estimation它基于一个直观假设在整个模拟过程中某个动作如果在很多不同局面里都出现过那么这个动作整体的历史表现可以通过全局统计来给树节点提供参考。具体说RAVE在计算节点得分时不只是看当前孩子节点的胜率还会把它与一个“快速估值”混合起来。快速估值反映的是这个动作在所有模拟中被使用时的胜率。这个混合能让树在早期迅速去掉很多明显糟糕的动作。它已经在一些棋类程序中被证明有效。另一个重要的改进是“渐进宽化”Progressive Widening。原始MCTS每次都只展开一个孩子但在分支因子极高时你会希望先放开试几个动作再慢慢根据统计信息决定要不要扩展到第10个、第50个动作。渐进宽化通过控制“当前每个节点的子节点数量上限”与访问次数的关系让树从“粗看”逐步到“精看”保持高效的同时避免过早锁定单一分支。6.2 先验概率与神经网络的结合如果告诉我可以大刀阔斧改进MCTS我会直接说用神经网络替换掉随机模拟。这也是AlphaGo相关技术公开后的核心启发。常规MCTS在扩展新节点时会把所有合法动作当作等概率候选项。但神经网络可以被用来估算每个动作的先验概率 (P(a|s))于是节点在初始化时不只是把动作放进untried_actions而是可以把“先验概率”存入节点。Selection时的UCT公式右侧探索项可以乘以或至少加权先验概率。这样一来算法会更早走向那些“看起来专业”的分支而不是完全靠随机尝试去发现好棋。Rollout部分也可以直接用神经网络的策略输出替代随机动作甚至可以在极少数局面直接调用价值网络评估。这样树可能在很浅的深度就已经有了相当强的判断力从根本上改变了模拟速度与质量之间的权衡。在工业级的博弈AI里这种“神经网络先验MCTS树搜索”已经成为事实标准。即使你对深度学习不熟悉也可以先在简单游戏里用一些规则启发式生成“伪先验”比如优先走中心、优先占据分值更高的格子验证一下这类先验启发式能提升多少收敛速度。6.3 多线程和并行模拟的注意点MCTS天然适合并行化因为大量迭代之间是相互独立的随机模拟。但并行时需要处理好共享树节点的数据竞争。最简单的方案是每几个分叉共用一把锁只在访问次数和累计得分更新时加锁。再激进一点可以用“虚拟损失”。虚拟损失的做法是在选择节点时暂时把节点的访问次数加一个大数比如3或5等该线程完成一次迭代并真正回传时再减去这部分虚拟损失并按实际结果更新。这样多个线程在模拟时会天然“避开”彼此正在处理的路线减少冲突。我在多线程环境里用这个技巧后迭代吞吐量提升很明显但要小心虚拟损失改得太大有些分支可能永远不被选中。7. 什么时候应该用MCTS什么时候别用7.1 适合MCTS的场景特征MCTS不是万能药但它非常擅长处理这类问题分支因子大、评估函数难写、搜索深度可以很深但你有能力进行终局模拟。比如棋牌游戏、拼图规划、资源调度、带随机性的路线规划都属于典型场景。它也很适合那些“你知道怎么判断终局但不知道如何给中间局面打分”的问题。如果你能写出一套可以快速随机模拟的规则但写不出合适的启发式评估函数MCTS就是很好的选择。它把“评估中间局面的难度”转移成了“运行足够多次模拟的计算成本”。7.2 不适合的典型场景如果分支因子很小、深度也不深传统的minimax加alpha-beta剪枝会更快更准。MCTS是统计近似算法它给出的落子带有随机性在确定性很强的小型博弈里反而不如全量搜索可靠。如果终局无法自然定义或者根本没有明确的胜负结果MCTS的统计框架就会比较尴尬。你需要自己设计“模拟终止条件”和“结果打分函数”这个过程又变回了“设计评估函数”的老问题MCTS的免评估优势就消失了。另外如果你的动作空间是连续值比如无人车转弯角度、机械臂关节角度直接用MCTS枚举离散动作会非常吃力。此时更合适的通常是强化学习或者连续优化算法。MCTS更偏向离散动作空间强行离散化连续空间会导致分支因子爆炸。7.3 一个简单的决策清单我会在动手前问自己几个问题能不能在毫秒级内完成一次随机模拟如果能MCTS很可能适用。我有没有一套可靠的终局判胜逻辑没有的话就得先补这块。分支因子是否大到让穷举无法承受如果只有十几种动作且深度很浅minimax更靠谱。中间局面能不能写出有效评分函数如果写不出来MCTS的优势更大。这个清单帮我避免过不少“为了用MCTS而用MCTS”的弯路。技术选型从来不是“越高级越好”而是匹配问题本身的结构。根据我个人做这些项目下来的体会MCTS最让我欣赏的一点就是它把复杂的决策问题拆成了无数个极其简单的随机实验再用统计的力量把噪声压下去得到一个非常抗干扰的决策。你在实际项目里遇到的大部分问题其实不是算法本身的数学错误而是节点统计的一致性问题、模拟效率问题和搜索策略过偏的问题。调试的时候先不要急着改公式先把树画出来看看访问次数分布是否已经符合直觉再动手改代码这样往往几轮就能定位到病根。