基于蒙特卡洛树搜索的Python寻路器实现与调参指南

差不多三年前，有朋友问我：如果不想用A*这类带启发式的经典寻路算法，还有没有别的路子？我当时给他推荐了蒙特卡洛树搜索（MCTS），他第一反应是“这不是下围棋那套吗，拿来寻路能行？”后来我把一个简单的Demo发给他，他跑完说了一句话：“这东西看着笨，但结果竟然靠谱。”

这就引出了今天这篇东西的核心：用Python写一个基于蒙特卡洛树搜索（MCTS）的寻路器，在二维网格地图上找一条从起点到终点的可行路径。我会把为什么选MCTS、四个阶段怎么落到寻路上、完整代码怎么组织、参数怎么调、以及和UCS、GBFS对比的结果都拆开讲一遍。适合两类人看：一类是想找“A之外的新玩法”来学习算法思想的初学者，另一类是遇到状态空间很大、启发式函数很难写的搜索问题，想换个通用框架试试的开发者。这篇文章不吹MCTS替代A，而是让你理解它适合什么、不适合什么，并且拿到一套能直接改用的Python实现。

1. 寻路方案选型：什么时候轮到MCTS出场

1.1 不是来替代A*，而是换一种思路

绝大部分寻路需求，A或者Dijkstra就够了：网格地图、路网、游戏寻路，这类问题状态空间明确、图的结构固定、计算代价低，A配合一个曼哈顿距离或欧氏距离的启发式，跑得又快又稳。MCTS在这种场景下并没有性能优势，它甚至会更慢、更“笨”。那为什么还要研究它？

原因在于MCTS有一个A*没有的特性：它不要求你事先设计一个好的启发式函数，不要求你知道整个地图的全局信息，也不需要一次性把整个搜索空间展开。它靠的是“随机模拟 + 统计回溯”，通过大量采样逐步把搜索树的注意力集中到更有希望的区域。换句话说，你只要能写一个“从某个状态开始随机走，判断走到终点算赢”的模拟器，剩下的交给统计规律。

这在某些场景里非常占便宜。举个例子：状态空间大且分支多，启发式很难设计；或者地图本身就是动态变化的，上一秒的路下一秒就被堵住；又或者你希望算法能随时被打断，给一个“截止目前最好”的答案，而不是必须完整算完才出结果。这些场景里，MCTS这种增量式、在线式的搜索方式，比一次性暴搜更合适。

所以我一直觉得，MCTS做寻路，目标不是“打败A*”，而是提供另一种搜索策略：用采样换启发式，用统计换全局贪心。理解了这个定位，后面看代码和调参就不会拧巴。

1.2 适合MCTS的寻路场景

你可以把MCTS想象成一个做事很谨慎的人：每到一个路口，他不会立刻拍板走哪边，而是把每条路都先试探着走几遍，心里大概有个数，再选他觉得最靠谱的那条走下去。试探得越多，他对每条路的好坏把握就越大。

基于这个特性，MCTS特别适合下面几类寻路问题：

• 地图规模大且动态变化的场景。传统做法要先把地图预处理成图结构再搜索，MCTS可以直接在原始状态上用模拟器判断，不需要维护全局拓扑。
• 代价函数复杂甚至说不清楚精确代价的场景。比如路径不仅要短，还要避开某些“说不清规则”的风险区域，这时候A*的启发式很难写，但模拟器里加一条“走到某些格子就扣分”的规则很简单。
• 需要实时决策的场景。MCTS可以在任意时刻截断，从当前根节点往下选一条最被看好的子路径，这就是“随时可以给答案”的特性。
• 教学和框架研究场景。MCTS的结构非常模块化：选择、扩展、模拟、回溯四步各管一段，改一块不影响其他三块，很适合用来做算法实验。

当然，它也有明显的短板：如果模拟策略太差，或者迭代次数不够，搜出来的路径可能明显绕路；如果地图特别大而目标特别远，纯随机模拟的成功率低，搜索会浪费大量模拟在无效路径上。这些问题我会在后面调参部分给出对应的解法，比如引入距离引导、partial reward、贪心模拟等。

1.3 我做的Demo长什么样

我自己搭的Demo是很直白的网格地图：一个二维数组，0代表可走，1代表障碍物，起点在左上角，终点在右下角。用MCTS去搜索一条从起点到终点的路径，输出一串坐标序列，同时还会统计搜索树的访问次数、平均奖励这些内部指标，方便观察算法到底在“想”什么。

地图选的是带障碍的迷宫样式，故意制造一些“看起来能走但其实是死路”的通道，这样MCTS的模拟阶段才有效果。如果是全空地，随机模拟几乎每次都能走到终点，MCTS的优势就体现不出来了。后面我会把具体代码贴出来，你也可以换成任意地图数据来试。

2. 先把MCTS的四个阶段吃透，再用到寻路上

MCTS的每一轮搜索，都按“选择-扩展-模拟-回溯”的顺序循环。你把它理解成一个逐渐长出来的树：根节点是起点，每一条边是一次移动，每一个节点是一个格子坐标。下面我结合寻路场景把这四步拆开讲。

2.1 选择：拿UCB1去挑孩子

选择阶段做的事情，是从根节点出发，沿着“当前最值得探索”的子节点一层层往下走，直到走到一个还没完全展开的节点。

这里的“最值得探索”不是随便挑的，用的是UCB1公式：

[ UCB1 = \frac{w_i}{n_i} + C \sqrt{\frac{\ln N}{n_i}} ]

其中 (w_i) 是子节点累计获得的奖励，(n_i) 是它被访问的次数，(N) 是父节点总的访问次数，(C) 是探索常数。

这个公式前半部分是“利用”：(w_i / n_i) 越大，说明这个方向之前模拟成功的概率越高，值得走。后半部分是“探索”：如果一个子节点访问次数太少，分母 (n_i) 小，整个值就会很大，于是搜索就会倾向去尝试那些还没怎么走过的方向。(C) 调节这两者的权重：C大了爱探索新路，C小了爱走成熟路线。

放到寻路语境里，UCB1就像一个决策者，在“按老经验走熟悉的路线”和“去没走过的地方碰碰运气”之间做权衡。节点被访问的次数越多，它的统计结果越可靠，同时也意味着探索空间里它的“新鲜度”下降了，需要去别处看看。

2.2 扩展：走出第一步

当选择阶段走到了一个还没被完全展开的节点，扩展阶段就会从它所有的合法动作里拿出一个还没试过的动作，创建对应的子节点。比如在某个格子上，上下左右里有三个方向可以走，当前节点已经试过两个方向了，那么扩展就是把这个方向上没走过的那条路也加进树里。

这一步很直白，但有一个关键点：一个节点被创建的时候，它会把“所有可能的下一步动作”先记录下来，每扩展一次就少一个待尝试动作，直到所有动作都被扩展过，这个节点就变成“完全展开”状态。这个设计保证了搜索不会疯狂地重复扩展同一个节点，而是先把所有可能性都铺开，再通过UCB1决定重点深挖哪个分支。

2.3 模拟与回溯：搜没搜到，结果都要回传

模拟阶段从新扩展的节点出发，用某种策略快速往前走若干步，直到走到终点、走入死路、或者超过步数上限。最朴素的策略就是随机走，上下左右随机挑合法的方向走。

模拟结束后得到一个奖励值：走到终点给正奖励，走进死胡同或者超时给0。然后进入回溯阶段，把这个奖励值一路往上传，从当前节点传到根节点，路径上每个节点的访问次数加1，总奖励加上这个值。

这轮做完，搜索树里就积累了一条“经验”：从根到某个节点的路线，后面的随机模拟成功了多少次。下一轮选择阶段，UCB1就会利用这些统计信息，更多地去走那些历史上“成功率高”的分支。

2.4 为什么这套循环能搜出路径

你可以把整个过程想象成一个团队在做“盲试”：一开始所有人都随机走，每次走到终点就记录一下“我走的这条路线中的每一段”都得到好评。走多了，那些经常出现在成功路径里的路段，评价自然越来越高；而经常走进死路的路段，评价会越来越差。于是下一批人更愿意沿着好路段走，慢慢地，一条相对靠谱的路径就浮现出来了。

这个思路和强化学习里的“奖励回传”非常像，只不过MCTS用树结构显式地管理不同前缀路径的统计，比单纯的策略函数更容易控制和观察。理解这一点，你就能明白为什么模拟策略的质量那么重要——如果随机模拟总也到不了终点，那回溯上去的所有节点都拿不到正奖励，搜索树就没有信号去区分好方向与坏方向。这是个核心问题，后面调参部分会重点讲。

3. Python代码：从零写一个MCTS寻路器

下面这段代码我尽量保持精简，不引入第三方库，只靠标准库里的math和random就能跑起来。我把它拆成几个小块分别说明，最后再给出完整可运行的版本。

3.1 定义节点和合法动作

首先是寻路的地图环境，这里我直接用二维数组加一个valid_moves函数，返回某个格子所有可以走的下一步坐标。边界检查和障碍检查都放在这里：

def valid_moves(state, grid): x, y = state rows, cols = len(grid), len(grid[0]) out = [] for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)): nx, ny = x + dx, y + dy if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0: out.append((nx, ny)) return out

然后是MCTS节点。节点保存了当前坐标、父节点引用、动作对应的子节点字典、还没尝试过的动作列表、访问次数和累计奖励：

class MCTSNode: def __init__(self, state, parent=None, action=None): self.state = state self.parent = parent self.action = action self.children = {} self.untried_actions = [] self.visits = 0 self.total_reward = 0.0 def is_fully_expanded(self): return len(self.untried_actions) == 0 def best_child(self, c_param=1.4): if not self.children: return None best = None best_score = float("-inf") log_n = math.log(max(self.visits, 1)) for child in self.children.values(): if child.visits == 0: score = float("inf") else: score = (child.total_reward / child.visits + c_param * math.sqrt(log_n / child.visits)) if score > best_score: best_score = score best = child return best

这里有个细节：child.visits == 0时，UCB1公式会除零，所以直接给一个无穷大的分数，让从未被访问过的节点天然具有最高优先级。调用max(self.visits, 1)是为了防止根节点上log里的参数为0。这个细节平时搜围棋、搜游戏AI的代码里都会出现，属于MCTS的标准写法。

3.2 四个方法组合成完整搜索

扩展和树策略函数负责把选择阶段落到具体实现：

def expand(node, grid): action = node.untried_actions.pop() child = MCTSNode(action, parent=node, action=action) child.untried_actions = valid_moves(action, grid) node.children[action] = child return child def tree_policy(root, goal, grid, max_depth=300): node = root depth = 0 while node.state != goal and depth < max_depth: if not node.is_fully_expanded(): return expand(node, grid) child = node.best_child() if child is None: return node node = child depth += 1 return node

注意这里expand创建子节点时，会立刻计算并填上它自己的untried_actions，这样下一轮循环到这个子节点时，可以直接判断要不要继续扩展。这个设计稍微有点“预计算”的味道，但能减少状态生成时的重复调用。

模拟阶段是另一个重点。最朴素的做法是纯随机走：

def simulate(state, goal, grid, max_steps=300): for _ in range(max_steps): if state == goal: return 1.0 moves = valid_moves(state, grid) if not moves: return 0.0 state = random.choice(moves) return 0.0

模拟的每一步，如果走到了终点就返回1.0，走进死路返回0.0，超过步数也算0.0。这个模拟函数是整个MCTS里最值得优化的地方，后面我会说怎么把它从“纯随机”改成“带引导的随机”，效果会有明显提升。

回溯阶段就是把奖励沿着父节点链传上去：

def backpropagate(node, reward): while node is not None: node.visits += 1 node.total_reward += reward node = node.parent

3.3 跑一把：地图、起点、终点、输出路径

主函数负责组装整个流程：初始化根节点，循环迭代若干次，结束后从根节点出发沿访问次数最多的子节点往下读出一条推荐路径：

def mcts_search(grid, start, goal, iterations=3000, c_param=1.4): root = MCTSNode(start) root.untried_actions = valid_moves(start, grid) if not root.untried_actions: return [] for _ in range(iterations): leaf = tree_policy(root, goal, grid) reward = simulate(leaf.state, goal, grid, max_steps=300) backpropagate(leaf, reward) path = [] node = root while node is not None: path.append(node.state) if not node.children: break node = max(node.children.values(), key=lambda c: c.visits) return path if __name__ == "__main__": grid = [ [0, 0, 0, 0, 1], [1, 1, 0, 1, 0], [0, 0, 0, 1, 0], [0, 1, 1, 0, 0], [0, 0, 1, 0, 0], ] start, goal = (0, 0), (4, 4) path = mcts_search(grid, start, goal, iterations=2000, c_param=1.4) print("MCTS 找到的路径:", path) print("路径长度:", len(path))

这段代码直接在命令行跑就能看到输出。需要注意，输出路径是“从根开始按访问次数最多一路走到叶子”的结果，它不一定每次都能走到终点，也不一定是最短路径。如果搜索预算不够，路径可能只走到中途就停了。这个问题在真实使用时通过“走一步、重新规划”的在线模式解决，后面我会展开说。

4. 调参和避坑：想让路径靠谱，这几点得注意

MCTS最让人头疼的地方就是参数。我跑这个Demo的时候也踩了不少坑，下面这些是我觉得最值得说的经验。

4.1 迭代预算：太少就是随机游走，太多就是浪费

迭代次数是最直观的参数。我测试下来，同一张5x5地图上，如果迭代次数少于200，搜出来的路径基本是乱的，因为UCB1的统计还没收敛，大多数分支访问次数只有几次，根本分不出好坏。到2000次左右，路径开始稳定下来。到10000次，路径质量几乎不再提升，纯粹是浪费计算。

你可以把迭代次数理解成“投票人数”：人数太少，投票结果全看运气；人数够了才谈得上统计意义。实际使用中，迭代预算要结合地图大小和目标距离来定。我的经验是，先设一个基准值，比如grid格子数 * 50，然后跑一次看路径质量，再翻倍试一轮，直到质变的拐点出现。

4.2 探索常数C：路径质量和探索广度之间的旋钮

探索常数C控制UCB1里“探索”项的权重。C设得太小，比如0.1，搜索会很快锁定一条早期看起来还不错的路，之后就一直在那条路上打转，几乎不去碰其他方向，结果经常陷入局部最优。C设得太大，比如10，那么几乎每个子节点的探索项都在初期占主导，搜索会像没头苍蝇一样到处乱试，真正的利用信息被淹没了。

我在这张5x5地图上试下来，C在1.0到2.0之间表现都比较稳。C取1.4是很多MCTS应用里的常用默认值，一开始可以直接用它，然后根据路径长度和方差微调。调C的时候注意观察一个指标：如果搜索结束后根节点的子节点访问次数分布特别极端，比如某一个子节点占了九成以上的访问，说明C偏小了；如果分布非常平均，说明C偏大，搜索没有聚焦。

4.3 模拟策略与额外奖励引导

这个坑是最有实战价值的。纯随机模拟在迷宫稍微复杂一点的时候，走到终点的概率会低得惊人。我在一张比较大的地图上测过，纯随机模拟的成功率可能只有百分之几，这就导致很多节点拿不到正奖励，搜索树学不到东西。

解决办法有两个方向。第一个是在模拟阶段加入引导：走每一步时，以一个高概率选择“让曼哈顿距离更小”的动作，留一点随机性去探索。这样模拟不再是完全盲走，而是“大致朝着目标方向但偶尔拐弯”的探索，成功率会高很多。

第二个方向是给没到达终点的模拟一个partial reward，比如：

def simulate_with_guide(state, goal, grid, max_steps=300, epsilon=0.2): for _ in range(max_steps): if state == goal: return 1.0 moves = valid_moves(state, grid) if not moves: return 0.0 greedy = min(moves, key=lambda m: manhattan(m, goal)) if random.random() < epsilon: state = random.choice(moves) else: state = greedy return 1.0 / (1.0 + manhattan(state, goal))

这里的逻辑是：即便超时没走完，只要你有一步算一步更接近终点，就给一个小的正奖励，让树里的节点也能获得梯度信号。这个技巧我在实测里非常有感，加了partial reward之后，搜索的收敛速度肉眼可见地加快。

4.4 容易踩的坑

有几个坑几乎每次写MCTS都会遇到，我列个清单：

• 死胡同节点的处理。一个格子如果四面都是墙，它创建时untried_actions就是空列表，best_child也可能返回None。我在tree_policy里加了if child is None: return node，否则下一轮循环会在is_fully_expanded上报错。
• 模拟阶段卡死。如果地图上有没有出口的封闭区域，纯随机模拟会一直在这个区域里反复横跳，直到步数上限才停。所以max_steps一定要设，而且要比理论最长路径略大，否则到不了终点。
• 根节点重复创建子节点。因为valid_moves里会把四个方向都试一遍，如果起点附近的地形可走方向重复，代码里直接以坐标作为children的key，天然避免了重复节点。
• 把“树里的路径”和“实际的连续规划”搞混。MCTS输出的路径是统计意义上的推荐轨迹，更适合滚动式执行，也就是每走一步或每走几步就重新跑一次MCTS，而不是期望它一次性给出完整全局路线。

5. 对照组实验：MCTS、UCS、GBFS在同一张地图上

写算法的人，最后总要拿个对比出来才算数。我在一张稍大一点的随机地图上，分别跑了统一代价搜索（UCS）、贪心最佳优先搜索（GBFS）、以及本文的MCTS，看路径质量和搜索开销。

5.1 实验设置

地图用的是10x10网格，随机生成30%的障碍，保证起点到终点存在可行路径，同时存在多条长度不等的可选路线。这样对比出来的结果才有区分度。三种算法都从同一个起点出发到同一个终点，MCTS的迭代预算设为4000，C取1.4，模拟采用带贪心引导和partial reward的版本。

统计指标有三个：路径长度、访问（扩展）的节点数、以及是否稳定找到完整路径。UCS和GBFS是完备的确定性算法，只要跑完一定有结果，重点看它们扩展了多少节点；MCTS不是确定性算法，我多跑了五组取典型值。

5.2 结果怎么看

我这张地图上的典型结果大致如下：

这个结果其实很说明问题：UCS用更多的扩展换来了最短路径；GBFS扩展最少但容易骗进“局部看起来很近”的死胡同；MCTS的模拟开销比前两者高一个量级，路径质量介于两者之间。

如果你问我现在工程上选哪个，我会说：单次静态寻路，直接用A*或UCS；需要频繁动态调整的，可以考虑MCTS或者它和其他算法的混合方案。MCTS在纯寻路任务里不占性能优势，它的价值在于框架的普遍性和可扩展性，换一个完全不同的状态定义和模拟规则，代码改动非常小。

6. 实操心得与扩展思路

跑完这轮实验，我最大的体会是：MCTS做寻路，图的不是“更快”，而是“更通用”。你只需要定义好状态、动作、模拟规则，剩下的事情交给统计。这个特性在做游戏AI、机器人实时规划、或者实验性算法研究的时候非常舒服，因为你不需要为了一个新环境重新设计启发式。

另外一个小技巧我前面也提到了：实际使用MCTS寻路时，不要指望它一次性给出高质量全局路径。更好的做法是走一步、重新规划一次。因为MCTS的搜索树可以保留，根节点移动后可以复用大部分统计信息，这样计算开销不会成倍增长，反而更符合在线决策的节奏。关于树的重用，标准做法是把当前节点变成新的根节点，丢弃旧的父节点统计，保留子节点数据，这会让后续迭代收敛得更快。

如果你看完想继续往下玩，我建议从三个方向改：第一，把模拟策略换成带学习能力的轻量模型，看看能不能再提升搜索效率；第二，把网格地图换成连续坐标状态，配合八方向移动，看看MCTS在高维状态空间里的表现；第三，把reward函数从“只关心到达终点”改成“路径越短奖励越高”，让搜索直接优化路径长度，而不是单纯找一条可行路。我自己试过第二种改法，效果很有意思，但那是另一个话题了。希望这份带代码的拆解能让你少踩几个坑，玩出自己的版本。