1. 先聊聊为什么用蒙特卡洛树搜索来做寻路

一提到寻路，很多人第一反应就是经典的A或者Dijkstra。老实说，在大部分静态地图、环境信息完全已知的场景下，A已经是公认的最优解，效率和效果都拉满了。那为什么还要用蒙特卡洛树搜索（MCTS）来折腾寻路？这个念头最开始冒出来，是在我处理一个模拟项目X的路径规划问题时。当时的地图不是静态的，障碍物的分布会随着时间变化，而且整个图规模很大，如果每次环境一变就重新跑一轮A*，计算开销会非常可观。

MCTS的思路和传统寻路算法有着本质区别。传统算法基于图搜索，依赖启发式函数估算代价，每一步都追求“确定性”的最优路径。而MCTS是一种基于随机模拟的决策框架，它不依赖启发式函数，也不需要预先完整建模环境，而是通过反复模拟“走一步看多步”来逐步逼近最优策略。这个特性让它在环境动态变化、状态空间巨大、难以写出好的启发式函数的场景里特别吃香。

当然，用MCTS做寻路也有它的代价。它不像A*那样保证找到最短路径，找到的是“在有限模拟资源下最稳妥的路径”。所以它更适合那种“不需要绝对最优，但要求快速适应变化环境”的场合。这篇文章我会带你从零实现一个用MCTS解决网格地图寻路的Python方案，把每个关键步骤和参数掰开揉碎讲明白。

读这篇文章，你不需要已经精通强化学习。只要会基础的Python，了解递归和树这种数据结构的基本概念，就能跟上节奏。我会先拆解MCTS的核心四个阶段，再给出完整的可运行代码，最后聊聊我实际调参时踩过的坑。

2. 核心思路拆解：MCTS的四阶段循环

2.1 选择：从根节点出发，一路选到最优叶子

MCTS每一轮迭代都从根节点开始。根节点就是当前智能体所在的位置。如果根节点已经不是第一次被访问，我们不会盲目随机走，而是按照一个叫UCT的公式，在所有未走完的子节点中挑一个最有潜力的往下走。

UCT公式长这样：

[ UCT = \frac{w_i}{n_i} + C \times \sqrt{\frac{\ln(N)}{n_i}} ]

其中(w_i)是这个子节点累计的“胜利”次数，(n_i)是访问次数，(N)是当前节点的访问次数，C是探索常数。公式左边是“利用”——这个子节点历史表现越好，越值得选；右边是“探索”——这个子节点访问次数越少，越值得试试看。C就是平衡两者的权重。

这个逻辑很像你去一家新城市旅游，面对好几条通往景点的路。如果你每次都走之前走过且顺利的路，可能错过更好的捷径；如果每次都走没试过的路，可能反复走进死胡同。C值就是调控你“保守”还是“冒险”的旋钮。

2.2 扩展：遇到没走过的岔路就开一条新枝

当选择过程一路走到某个节点，发现它还有没被访问过的邻居节点时，就停下来，从这个节点扩展出一个新的子节点。这个新节点代表“从当前位置走一步到新位置”。

扩展这一步有一个关键点需要注意：不是所有邻居都能扩展。比如邻居是障碍物、超出地图边界，或者会直接导致路径成环回退到已经走过的格子，这些都应该被过滤掉。否则你会看到搜索树越建越深，但智能体实际上在原地转圈，纯粹浪费算力。

2.3 模拟：从新节点开始随机浪到底

扩展出子节点后，从那个子节点出发，进行随机模拟。模拟的策略可以很简单：在上下左右四个方向里随机挑一个可行的方向走，一直走到以下三种情况之一——到达终点（胜利）、走进死胡同（失败）、走的步数超过上限（失败）。

模拟阶段是你整个MCTS能否高效运转的关键。如果完全随机，大量模拟会浪费在没意义的长路径上。我后来的方案是加了一个“偏向目标方向的随机”：80%的概率优先选择能缩小与终点曼哈顿距离的方向，20%的概率随机乱走。这样既保留随机性带来的探索能力，又让模拟更快撞见终点，显著加速收敛。

2.4 回传：把模拟结果沿着访问路径传回去

模拟得到胜负结果后，从子节点一路回传到根节点，更新路径上每个节点的访问次数和胜利次数。如果模拟结果是找到终点，那路径上每个节点的胜利次数加1；否则只有访问次数加1。

回传这一步就是MCTS“总结经验教训”的方式。下一次迭代在选择阶段，那些历史胜率高的节点会被更大概率选中，而访问次数少的新节点依然有机会被探索。随着迭代次数不断增加，树对地图的认知越来越准，最终根节点的最优子节点链就是你要的答案。

3. 完整Python实现：网格寻路的MCTS实战

3.1 环境搭建与数据结构设计

我先假设一个10x10的网格地图，用0表示空地，1表示障碍物。起点坐标是(0,0)，终点坐标是(9,9)。MCTS的核心数据结构有两种：一是地图矩阵，二是树节点。

import random import math from collections import defaultdict class GridWorld: def __init__(self, width=10, height=10, obstacles=None): self.width = width self.height = height # 默认地图全空，然后撒一些障碍物 self.grid = [[0 for _ in range(width)] for _ in range(height)] if obstacles: for (x, y) in obstacles: self.grid[y][x] = 1 def is_valid(self, x, y): return 0 <= x < self.width and 0 <= y < self.height and self.grid[y][x] == 0 def get_neighbors(self, x, y): dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)] neighbors = [] for dx, dy in dirs: nx, ny = x + dx, y + dy if self.is_valid(nx, ny): neighbors.append((nx, ny)) return neighbors def manhattan_distance(self, x1, y1, x2, y2): return abs(x1 - x2) + abs(y1 - y2)

3.2 节点类的设计

树节点需要记录位置、父节点、子节点列表，以及累计的访问次数n和胜利次数w。

class MCTSNode: def __init__(self, x, y, parent=None): self.x = x self.y = y self.parent = parent self.children = [] self.n = 0 self.w = 0 self.untried_neighbors = None # 懒加载，首次访问时再算 def is_root(self): return self.parent is None

这里我留了一个untried_neighbors属性，目的是推迟邻居节点的计算。在地图比较大的时候，每个节点都提前算好所有可行邻居会占用不少内存，懒加载能省掉这笔开销。

3.3 UCT选择逻辑的实现

def ucb_score(node, total_visits, c): if node.n == 0: return float('inf') exploitation = node.w / node.n exploration = c * math.sqrt(math.log(total_visits) / node.n) return exploitation + exploration def select_child(node, c): best_score = -float('inf') best_child = None for child in node.children: score = ucb_score(child, node.n, c) if score > best_score: best_score = score best_child = child return best_child

注意这里有个细节：如果某个子节点的n为0，也就是一次都没被访问过，UCB公式里的ln(N)/n会变成无穷大。所以代码里我对node.n == 0的情况直接返回无穷大，保证每个新扩展的子节点都会被优先尝试一次，避免某些子节点永远没机会被选中，从而保证探索的公平性。

3.4 扩展与模拟策略的实现

扩展阶段从当前节点出发，取一个未尝试过的邻居作为新子节点。模拟阶段使用带目标偏置的随机策略。

def expand(node, world): if node.untried_neighbors is None: node.untried_neighbors = world.get_neighbors(node.x, node.y) if not node.untried_neighbors: return None nx, ny = node.untried_neighbors.pop() child = MCTSNode(nx, ny, parent=node) node.children.append(child) return child def simulate(node, world, end, max_steps=50): x, y = node.x, node.y visited = set() visited.add((x, y)) for _ in range(max_steps): if (x, y) == end: return 1.0 neighbors = world.get_neighbors(x, y) # 过滤掉往回走的 valid = [n for n in neighbors if n not in visited] if not valid: valid = neighbors if not valid: # 死胡同 return 0.0 # 偏向目标的随机选择 sorted_neighbors = sorted( valid, key=lambda n: world.manhattan_distance(n[0], n[1], end[0], end[1]) ) # 80%概率选最近目标方向，20%概率完全随机 if random.random() < 0.8: next_pos = sorted_neighbors[0] else: next_pos = random.choice(valid) visited.add(next_pos) x, y = next_pos return 0.0

模拟里加了一个visited集合，避免模拟过程中反复横跳。这一步很关键，不然随机游走很容易在两个格子之间来回弹跳，白白消耗步数上限。

3.5 主循环：迭代搜索与路径还原

def mcts_search(world, start, end, iterations=3000, c=1.4, max_steps=50): root = MCTSNode(start[0], start[1]) for _ in range(iterations): node = root # 选择 while node.children: if any(child.n == 0 for child in node.children): break node = select_child(node, c) # 如果到达终点，回传胜利 if (node.x, node.y) == end: node.w += 1 continue # 扩展 child = expand(node, world) if child is not None: node = child # 模拟 reward = simulate(node, world, end, max_steps) # 回传 while node is not None: node.n += 1 node.w += reward node = node.parent # 从根节点逐步选择最优子节点，还原路径 path = [(root.x, root.y)] node = root while node.children: node = select_child(node, c) path.append((node.x, node.y)) if (node.x, node.y) == end: break return path

3.6 跑一个完整示例

world = GridWorld(width=10, height=10, obstacles=[ (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (6, 5), (6, 6), (6, 7), (6, 8), (1, 8), (2, 8), (4, 8) ]) start, end = (0, 0), (9, 9) path = mcts_search(world, start, end, iterations=3000, c=1.4) print("找到路径：", path) print("路径长度：", len(path))

我实际跑下来，迭代3000次的情况下，路径长度通常在22到28之间波动，找到一个可行解基本没问题。对比一下最优解——在这个障碍布局下，A*算出来的最短路径长度是21。MCTS能找到接近最优的路径，而且整个过程无需设计任何启发式函数。

4. 参数调优与效果对比：不要盲目抄默认值

4.1 迭代次数：越多越好？大错特错

迭代次数是MCTS最直观的参数。迭代越多，树越深，路径质量越高，但耗时线性增长。真正的问题在于，迭代到后期出现收益递减。最初的500次迭代能快速把路径从“完全随机乱走”提升到“能走到终点附近”，但从2000次到5000次，路径长度可能只缩短一两格，时间却翻倍。

我在实际项目里常用一个策略：先跑1000次快速迭代看结果稳不稳定，如果路径长度波动大再逐步加大迭代次数。另外，如果你的场景限时严格，宁可减少迭代次数也要保证每次模拟的质量。

提示：迭代次数不要设计成固定值。更优的做法是设定一个时间预算，每轮迭代前检查当前耗时，超时就停止搜索，返回当前最优路径。这样在真实场景中才能稳定可控。

4.2 探索常数C：调大调小各有体验

C值决定搜索是偏保守还是偏激进。C设置太小时，搜索会集中在少数几条历史上表现好的路径上，可能过早陷入局部最优——看起来找到了路径，代价其实是绕了一大圈。C设置太大时，搜索会浪费大量时间在明显没希望的岔路上，收敛速度让人着急。

我用的基准是C=1.4，这个值在10x10的网格上表现不错，但如果你换到20x20或者更大的地图，建议把C加到1.8到2.0之间，因为地图变大后，仅凭贪心利用很容易错过真正的好路径。

4.3 与A*和Dijkstra的对比实测

我用同一张地图跑了三组实验对比：

A在静态地图上几乎碾压MCTS。但把地图设成动态的——比如每跑5步就随机添一个障碍物——A每次都要重新规划，累积耗时迅速上升；MCTS则可以直接在上一轮的树上继续搜索，只需要删掉非法节点、重新模拟若干轮就行。这个特性在长时间运行、频繁小规模变动的场景中尤其值钱。

4.4 模拟步数上限的设定

模拟步数上限如果设得太小，大量模拟会因为“步数耗尽”被判失败，导致胜率信号变得几乎无意义——所有节点都拿不到正奖励，就好比给每个考生一份永远做不完的试卷，根本无法区分水平高低。设得太大的话，模拟一旦误入死胡同区域，会在里面反复绕很久，浪费算力。

我的经验是：取地图对角线长度的两倍左右作为上限。以10x10的地图为例，对角线格数约14，上限设成30左右就比较合适。如果地图有大量狭长通道，可以再往上加。

5. 我踩过的坑：MCTS寻路高频问题排查

5.1 路径反复横跳，树深得离谱

这个问题在早期版本里特别严重。模拟策略没有对已访问节点做约束，随机游走可以在两个相邻格子之间来回弹跳，直到步数上限耗尽。解决办法是模拟时维护一个visited集合，过滤掉已经走过的邻居。另一种做法是禁止模拟步法里出现连续两次相反方向的移动，但前者实现更简单，效果也更稳健。

5.2 子节点访问次数一直是0

如果某些子节点一直不被选中，UCB公式里的无穷大机制会强迫它们被尝试。但如果你发现所有子节点的n都是0，说明代码里选择阶段出了问题。最常见的原因是忘了判断子节点的untried状态就提前返回，导致树完全没生长。

另一个隐性问题是：如果扩展节点时使用了随机弹出untried_neighbors，而某个子节点虽然存在但对应的位置已经被父节点的其他子节点覆盖（比如两个扩展路径最终汇合到同一个格子），这棵树实际上变成了图。MCTS是构建在树结构上的算法，如果在图环境上运行，会出现同一节点的n值被重复更新、回传逻辑错乱的问题。因此，每次扩展前要检查新子节点坐标是否与已有子节点重复。

5.3 模拟结果不稳定，多次运行路径差异很大

MCTS本质是随机算法，结果不稳定是正常现象。但如果你发现路径质量差异大到离谱，首先检查随机种子。调试阶段固定随机种子能帮你复现问题：

random.seed(42)

其次，检查探索常数C，C太小会导致每次运行锁定到不同的局部最优路径。最后，检查终止条件——如果你在模拟中把“达到终点”和“走到步数上限”都判为失败，也会压缩胜利信号，让结果变得随机。

5.4 大地图性能不够，怎么办

10x10的格子跑3000次迭代没问题，但如果地图扩到50x50，性能就开始难受了。我试过几种优化方式，按性价比排序如下：

第一，减少模拟开销。把每次模拟的随机游走限制在更少的步数以内，比如只模拟20步，提前结束，虽然单次模拟的“智能”程度下降，但相同时间内可以跑更多轮模拟，总体效果反而更好。

第二，实现树复用。环境变化后不清空整棵树，只把受障碍物影响的节点修剪掉，在保留的树上继续迭代。这个改动能把动态场景的响应时间缩到原来的三分之一。

第三，做并行模拟。MCTS天然的并行点是每次迭代的模拟阶段互相独立，可以开多线程或进程池。Python里由于GIL限制，多线程对CPU密集型任务提升有限，更推荐用多进程。不过进程间传递数据有额外开销，地图太小不一定划算。

5.5 障碍物贴墙场景下会“钻墙”

还有一个隐蔽的问题：如果你扩展时只检查目标格子本身是否合法，没检查“从当前格子走到目标格子”的移动路径是否合法，那么在对角线或贴墙场景下，可能穿墙而过。解决办法是在get_neighbors里直接根据当前坐标和邻居坐标的差值，把两格中间可能经过的边界也纳入检查。对网格地图来说，最简单的方式是禁止斜向移动，只允许上下左右四个方向移动，这样就不存在跨墙问题。

6. 后续扩展：从网格寻路到更广阔的应用

MCTS在寻路上的价值远远不止“找一个能走的路径”。它真正的核心竞争力是“在信息不完全或者环境不断变化时，依然能做出合理决策”。把网格寻路的代码稍微改一改，就能迁移到很多场景里。

比如在策略游戏中做NPC的移动决策。地图很大，敌人位置不断变化，NPC不需要每次都算出全局最短路径，只需要根据当前能感知到的局部信息做短视野决策，MCTS天然适配这种“局部感知+反复规划”的模式。

再比如做机器人在未知地图中的探索路径规划。机器人每前进一步，传感器更新一次地图，MCTS在更新后的地图上继续搜索，效率和稳定性都比重跑一遍全局规划更好。

如果追求更高阶性能，还可以把神经网络和MCTS结合起来——用神经网络替代随机模拟策略，收敛速度能提升一个量级。这个方向感兴趣的可以去找AlphaGo相关公开资料深入了解，这里不展开。

7. 一点实操体会

用MCTS做寻路，最开始有很强的“杀鸡用牛刀”的感觉。A*几毫秒出结果的事情，偏要弄一个几十毫秒的随机搜索出来，看起来确实有点自找麻烦。但当你把地图换成持续有变化的环境，当你不确定每个格子的穿越代价是不是一成不变时，MCTS那种“不需要精确已知环境也能逐步逼近答案”的品性就显现出来了。

实际操作中，我的习惯是先跑一遍A*拿到最优路径作为质量基准，再跑MCTS看结果与最优解差多少。如果差距在可接受范围内，就说明MCTS参数配置合理。这个验证方法推荐给你，能省去很多试错时间。

另外，调试MCTS代码时不要聚焦最终路径本身，而要看树的生长过程。打印每个根节点的子节点n值和w值，观察它们如何随迭代变化，会比直接看路径更容易发现逻辑漏洞。

如果你也想在自己的寻路项目里尝试MCTS，建议从这篇文章的代码开始，先改成你自己的地图格式，再逐步调参和优化。遇到连续随机结果不理想的时候，优先检查模拟策略和探索常数，绝大多数问题都出在这两个地方。