当前位置：首页 > backend >正文

深入理解蒙特卡洛树搜索（MCTS）：python从零实现

backend 2025/5/20 7:40:16

引言：强化学习中的搜索与规划

虽然许多强化学习算法直接从经验中学习策略或价值函数（无模型），但还有一种强大的方法涉及规划。规划方法使用环境的模型（可以是预先已知的，也可以是学习得到的）来模拟未来可能性，并据此做出明智的决策。蒙特卡洛树搜索（MCTS）是一种非常成功的规划算法，它能够智能地探索从当前状态出发的潜在未来轨迹。

与 DQN 或 PPO 等算法不同，这些算法会生成适用于任何遇到的状态的策略，而 MCTS 通常是在线使用的。给定一个当前状态，它会执行搜索以确定最佳的立即动作，然后丢弃大部分搜索树，并从下一个状态重新开始这个过程。

什么是 MCTS？

蒙特卡洛树搜索是一种基于最佳优先搜索的算法，由随机模拟（蒙特卡洛模拟）的结果引导。它逐步构建一个搜索树，其中节点代表状态，边代表动作。它不需要显式的状态评估函数，而是基于从这些状态和动作启动的模拟结果来估计树中状态和动作的价值。

核心思想：引导式模拟

MCTS 迭代地通过状态空间模拟轨迹。它不会随机或穷尽地探索，而是利用之前模拟收集的统计数据（例如访问次数和平均奖励）来引导搜索朝着更有希望的状态-动作空间区域进行，同时仍然确保一定程度的探索。

MCTS 与其他搜索方法的对比

与 Minimax/Alpha-Beta 对比： MCTS 不需要评估到某一深度的所有可能游戏状态。它通过采样轨迹来进行搜索，这使得它适用于分支因子巨大（如围棋）的领域。
与动态规划对比： 动态规划需要一个完整的模型，并且会对整个状态空间进行迭代。MCTS 从当前状态开始集中搜索精力，而不需要全局迭代。
与无模型强化学习对比： MCTS 是一种规划算法，需要一个模型（或模拟器访问）。无模型强化学习则直接从真实交互中学习。

为什么选择 MCTS？它的优势在哪里

随时可用的算法： MCTS 可以在任何时间（给定计算预算）被停止，并提供目前为止找到的最佳动作。更多的计算通常会带来更好的决策。
非对称树增长： 它自然地将计算精力集中在更有希望的搜索树分支上。
无需启发式评估函数（用于搜索）： 节点价值通过模拟估计，避免了手工设计启发式函数的麻烦（尽管好的模拟策略可以帮助）。
可并行化： 迭代中的独立模拟通常可以并行化。

MCTS 的应用场景

MCTS 因在计算机围棋（如 AlphaGo 和 AlphaZero）中的成功而广为人知，但它适用于广泛的问题：

游戏： 围棋、国际象棋、将棋、六边棋，以及许多其他棋盘游戏和视频游戏。
规划问题： 机器人技术、调度、一般决策问题（只要有模拟器可用）。
与深度学习的结合： AlphaGo/AlphaZero 将 MCTS 与深度神经网络（学习到的策略和价值函数）相结合，用于引导搜索和评估位置，实现了超越人类的表现。

MCTS 特别适用于以下情况：

状态空间很大或无限。
分支因子（可能的动作数量）很大。
有环境的模拟器或前向模型可用。
没有精确的评估函数，或者难以计算。
需要在有限的计算预算下在线做出决策。

MCTS 的数学基础

树结构：节点和边

节点： 代表环境中的状态。
边：代表从一个状态（父节点）采取的动作，导致潜在的下一个状态（子节点）。
节点统计信息： 每个节点 (s) 通常存储：
- (N(s))：访问次数（有多少模拟经过这个节点）。
- (W(s))：经过这个节点的模拟所累积的总奖励（或价值）。
- (Q(s) = W(s) / N(s))：节点的平均价值估计。
边统计信息： 每条边 ((s, a)) 从节点 (s) 出发可能会存储：
- (N(s, a))：从状态 (s) 采取动作 (a) 的访问次数。
- (W(s, a))：从状态 (s) 采取动作 (a) 后开始的模拟的总奖励。
- (Q(s, a) = W(s, a) / N(s, a))：在状态 (s) 中采取动作 (a) 的平均价值估计。

MCTS 迭代的四个步骤

每次 MCTS 迭代从根节点（当前状态）开始，包含以下四个阶段：

选择阶段：
- 从根节点开始。
- 基于树策略递归选择子节点，该策略平衡探索和利用，直到到达一个叶节点（一个尚未完全展开或终端节点）。
- 常见的树策略是 UCT（Upper Confidence Bound for Trees），基于 UCB1。
扩展阶段：
- 如果选中的叶节点 (L) 不是终端节点且尚未完全展开（即从状态 (L) 有未尝试的动作），选择一个未尝试的动作 (a)。
- 使用环境模型/模拟器模拟采取动作 (a)，得到下一个状态 (s’)。
- 在树中添加一个新子节点，代表 (s’)，并通过边 (a) 与 (L) 连接。
- 新添加的节点成为模拟阶段的起始节点。
模拟（展开）阶段：
- 从新展开的节点（或者如果选中的叶节点是终端或已完全展开，则从该叶节点）开始，使用展开策略（通常是简单的，例如随机动作）模拟一个完整的剧集（或直到达到最大深度或折扣范围）。
- 收集在此模拟过程中获得的总折扣奖励 (R)。
反向传播阶段：
- 使用模拟结果 (R) 更新选择和扩展阶段访问的所有节点和边的统计信息（(N) 和 (W)）。
- 对于从根到模拟起始节点路径上的每个节点 (n)：
  - 增加访问次数 (N(n) \leftarrow N(n) + 1)。
  - 更新总价值 (W(n) \leftarrow W(n) + R)（或者根据游戏中的轮次更新）。
- 类似地更新边的统计信息（如果存储）。

树的上界置信区间（UCT/UCB1）

在选择阶段，从节点 (s) 到子节点 (s’) 的动作 (a) 通常被选择为最大化 UCB1 公式：
$\text{UCT}(s, a) = Q(s, a) + C \sqrt{\frac{\ln N(s)}{N(s, a)}}$
其中：

(Q(s, a)) 是当前的平均价值（利用项）。
(N(s)) 是父节点 (s) 的访问次数。
(N(s, a)) 是边（或采取动作 (a) 后的子节点）的访问次数。
(C) 是探索常数（超参数），平衡利用和探索。更高的 (C) 鼓励探索访问次数较少的动作。
如果 (N(s, a) = 0)，则 UCB 值被视为无穷大，以确保未访问的动作首先被选中。

展开策略

在模拟阶段使用的策略。它应该计算成本低廉。常见选择：

随机策略： 均匀随机选择动作。
简单启发式策略： 一个快速的、针对问题的启发式策略。
学习策略： 单独学习到的轻量级策略（在基本 MCTS 中不太常见）。
展开策略的质量会影响从模拟中获得的价值估计的准确性。

MCTS 的逐步解释（用于动作选择）

给定一个当前状态 (s_{\text{root}}) 和一个模拟预算（例如，迭代次数 (N_{\text{sim}})）：

初始化：为 (s_{\text{root}}) 创建一个根节点。
循环，对于 (i = 1) 到 (N_{\text{sim}})：
a. 选择阶段：从 (s_{\text{root}}) 开始。使用 UCT 遍历树以选择动作，直到到达一个叶节点 (L)。
b. 扩展阶段：如果 (L) 可以扩展，选择一个未尝试的动作 (a)，创建一个新子节点 (C)，对应于从 (L) 采取动作 (a) 后得到的状态。将模拟起始节点设置为 (C)。
c. 如果 (L) 已经完全展开或为终端节点，则将模拟起始节点设置为 (L)。
d. 模拟阶段：从模拟起始节点的状态开始，使用展开策略运行一个展开，直到终止或达到最大深度。记录总奖励 (R)。
e. 反向传播阶段：使用奖励 (R) 更新从根到模拟起始节点路径上所有节点/边的访问次数 (N) 和总价值 (W)。
选择动作：在 (N_{\text{sim}}) 次迭代后，选择从根节点出发的访问次数 (N(s_{\text{root}}, a^)) 最高的动作 (a^)（或者有时选择价值最高的 (Q(s_{\text{root}}, a^*))）。
返回 (a^*)。

MCTS 的关键组成部分

树节点

存储状态、父子链接、访问次数 (N)、总价值 (W)。

选择策略（UCB1）

在树遍历过程中平衡探索访问次数较少的动作和利用价值较高的动作。

扩展策略

如何添加新节点（通常每次迭代为一个未尝试的动作添加一个新节点）。

模拟（展开）策略

用于估计未展开节点价值的快速策略（例如，随机）。

反向传播更新

模拟结果如何更新节点统计信息。

模拟预算

每次决策执行的迭代/模拟次数（控制思考时间）。

最终动作选择

在搜索后如何选择最佳动作（例如，访问次数最多的子节点）。

环境模型/模拟器

在扩展和模拟阶段，用于预测从状态 (s) 采取动作 (a) 的结果 ((s’, r))。

超参数

UCB1 中的探索常数 (C)。
模拟预算（迭代次数或时间）。
折扣因子 (\gamma)（如果展开是折扣的）。

实际示例：自定义网格世界

为什么选择网格世界来展示 MCTS？

正如前面提到的，网格世界具有离散的状态空间、明确的动作和现成的完美模型（环境代码本身），非常适合用来展示 MCTS 的步骤，而不会受到其他因素的干扰。我们可以看到树是如何探索路径的，以及如何利用模拟奖励来引导动作选择。

环境描述：（使用表格版本）

状态：一个 (行, 列) 元组。
动作：0-3（上、下、左、右）。
动态：基于 action_map 的确定性转换。
奖励：+10（目标），-1（墙壁），-0.1（步进）。

设置环境

导入必要的库。我们主要需要 math、random、copy（用于模拟状态）和 collections 或类用于树结构。

# 导入必要的库
import numpy as np
import matplotlib.pyplot as plt
import random
import math
import copy # 用于在模拟过程中复制状态
from collections import defaultdict
from typing import Tuple, Dict, Any, List, Optional, Set# 设置随机种子以确保可重复性
seed = 42
random.seed(seed)
np.random.seed(seed)%matplotlib inline

创建自定义环境

使用 GridEnvironmentTabular 类。

class GridEnvironmentTabular:""" 网格世界，返回状态元组，并添加状态复制方法。 """def __init__(self, rows: int = 10, cols: int = 10) -> None:self.rows: int = rowsself.cols: int = colsself.start_state: Tuple[int, int] = (0, 0)self.goal_state: Tuple[int, int] = (rows - 1, cols - 1)# 内部状态变量 - MCTS 将在此基础上操作self._internal_state: Tuple[int, int] = self.start_state self.action_dim: int = 4self.action_map: Dict[int, Tuple[int, int]] = {0: (-1, 0), 1: (1, 0), 2: (0, -1), 3: (0, 1)}self.actions = list(self.action_map.keys())def reset(self) -> Tuple[int, int]:""" 重置环境，返回状态元组。 """self._internal_state = self.start_statereturn self._internal_statedef get_state(self) -> Tuple[int, int]:""" 返回当前内部状态元组。 """return self._internal_statedef set_state(self, state: Tuple[int, int]) -> None:""" 手动设置内部状态（用于 MCTS 模拟）。 """if 0 <= state[0] < self.rows and 0 <= state[1] < self.cols:self._internal_state = stateelse:raise ValueError(f"状态 {state} 在 {self.rows}x{self.cols} 的网格中无效")def get_possible_actions(self, state: Optional[Tuple[int, int]] = None) -> List[int]:""" 返回给定状态（或当前状态）的可能动作列表。 """# 在这个简单的网格中，所有动作总是可用的（墙壁在 step 中处理）current_state = state if state is not None else self._internal_stateif current_state == self.goal_state:return [] # 目标状态没有动作return [action for action in self.actions if self.simulate_step(current_state, action)[0] != current_state]def is_terminal(self, state: Optional[Tuple[int, int]] = None) -> bool:""" 检查给定状态（或当前状态）是否为终端状态。 """current_state = state if state is not None else self._internal_statereturn current_state == self.goal_statedef step(self, action: int) -> Tuple[Tuple[int, int], float, bool]:""" 从当前内部状态执行一步。 """state = self._internal_state # 使用内部状态if state == self.goal_state:return state, 0.0, Truedr, dc = self.action_map[action]current_row, current_col = statenext_row, next_col = current_row + dr, current_col + dcreward: float = -0.1 # 步进成本if not (0 <= next_row < self.rows and 0 <= next_col < self.cols):next_row, next_col = current_row, current_col # 如果碰到墙壁则停留在原地reward = -1.0 # 墙壁惩罚self._internal_state = (next_row, next_col) # 更新内部状态next_state_tuple = self._internal_statedone: bool = (self._internal_state == self.goal_state)if done:reward = 10.0 # 目标奖励return next_state_tuple, reward, donedef simulate_step(self, current_state: Tuple[int, int], action: int) -> Tuple[Tuple[int, int], float, bool]:""" 模拟一步，但不改变内部状态。这是 MCTS 所需的。 """if current_state == self.goal_state:return current_state, 0.0, Truedr, dc = self.action_map[action]current_row, current_col = current_statenext_row, next_col = current_row + dr, current_col + dcreward: float = -0.1if not (0 <= next_row < self.rows and 0 <= next_col < self.cols):next_state_tuple = current_state # 如果碰到墙壁则返回原始状态reward = -1.0else:next_state_tuple = (next_row, next_col)done: bool = (next_state_tuple == self.goal_state)if done:reward = 10.0return next_state_tuple, reward, donedef get_action_space_size(self) -> int:return self.action_dim

实例化环境。

mcts_env = GridEnvironmentTabular(rows=5, cols=5) # 使用较小的网格以加快 MCTS 演示
n_actions_mcts = mcts_env.get_action_space_size()
start_state_mcts = mcts_env.reset()
print(f"MCTS 网格环境：{mcts_env.rows}x{mcts_env.cols}")
print(f"动作：{n_actions_mcts}")
print(f"起始状态：{start_state_mcts}")
print(f"目标状态：{mcts_env.goal_state}")

MCTS 网格环境：5x5
动作：4
起始状态：(0, 0)
目标状态：(4, 4)

实现 MCTS 算法

我们将定义节点结构以及四个关键函数：选择、扩展、模拟、反向传播，以及主搜索协调器。

定义 MCTS 节点

一个类，用于表示搜索树中的节点。

class MCTSNode:""" 表示蒙特卡洛树搜索中的一个节点。 """def __init__(self, state: Tuple[int, int], parent: Optional['MCTSNode'] = None, action_that_led_here: Optional[int] = None):self.state: Tuple[int, int] = stateself.parent: Optional[MCTSNode] = parentself.action_that_led_here: Optional[int] = action_that_led_here # 从父节点到达此节点的动作self.children: Dict[int, MCTSNode] = {} # 映射动作 -> 子节点self.untried_actions: List[int] = mcts_env.get_possible_actions(state) # 从这个节点尚未展开的动作self.visit_count: int = 0self.total_value: float = 0.0 # 通过这个节点的展开所累积的奖励总和def is_fully_expanded(self) -> bool:""" 检查从这个节点出发的所有可能动作是否都已展开。 """return len(self.untried_actions) == 0def is_terminal(self) -> bool:""" 检查这个节点所代表的状态是否为终端状态。 """return mcts_env.is_terminal(self.state)def get_average_value(self) -> float:""" 计算这个节点的平均价值 \(Q(s)\)。 """if self.visit_count == 0:return 0.0 # 或者或许可以使用负无穷大或其他默认值来表示未访问return self.total_value / self.visit_count

选择函数（最佳 UCT 子节点）

选择具有最高 UCT 值的子节点。

def select_best_child_uct(node: MCTSNode, exploration_constant: float) -> MCTSNode:"""选择具有最高 UCT 分数的子节点。UCT = \(Q(\text{child}) + C \sqrt{\frac{\ln N(\text{parent})}{N(\text{child})}}\)参数：- node (MCTSNode)：从中选择的父节点。- exploration_constant (float)：平衡探索和利用的常数 \(C\)。返回：- MCTSNode：具有最高 UCT 值的子节点。"""best_score = -float('inf')best_child = Nonefor action, child in node.children.items():if child.visit_count == 0:# 确保首先选择未访问的子节点uct_score = float('inf') else:exploit_term = child.get_average_value()explore_term = exploration_constant * math.sqrt(math.log(node.visit_count) / child.visit_count)uct_score = exploit_term + explore_termif uct_score > best_score:best_score = uct_scorebest_child = childif best_child is None:# 如果节点有子节点，这种情况理论上不应该发生raise RuntimeError("选择失败：未找到子节点或 UCT 计算出错。")return best_child

扩展函数

通过添加一个新子节点来扩展一个叶节点，该子节点对应于一个未尝试的动作。

def expand_node(node: MCTSNode) -> MCTSNode:"""通过选择一个未尝试的动作并模拟它来扩展给定的节点，并将得到的状态作为新子节点添加。参数：- node (MCTSNode)：要扩展的叶节点。返回：- MCTSNode：新创建的子节点。"""if not node.untried_actions:raise RuntimeError("无法扩展一个已经完全展开的节点。")# 选择一个动作进行扩展（例如，第一个未尝试的动作）action = node.untried_actions.pop() # 使用环境模型模拟这个动作next_state, _, _ = mcts_env.simulate_step(node.state, action) # 这里只需要下一个状态# 创建新的子节点child_node = MCTSNode(state=next_state, parent=node, action_that_led_here=action)# 将子节点添加到父节点的子节点字典中node.children[action] = child_nodereturn child_node

模拟（展开）函数

从给定状态开始，使用简单的展开策略（随机动作）模拟一个剧集。

def perform_rollout(start_node: MCTSNode, max_depth: int, gamma: float) -> float:"""从起始节点的状态开始执行蒙特卡洛模拟（展开）。使用随机策略进行展开。参数：- start_node (MCTSNode)：从哪个节点开始模拟。- max_depth (int)：展开的最大步数。- gamma (float)：展开奖励的折扣因子。返回：- float：在展开过程中获得的总折扣奖励。"""current_state = start_node.statetotal_discounted_reward: float = 0.0current_discount: float = 1.0depth = 0while not mcts_env.is_terminal(current_state) and depth < max_depth:# 随机选择一个动作（展开策略）possible_actions = mcts_env.get_possible_actions(current_state)if not possible_actions: # 如果不是终端状态，理论上不应该发生，但为了安全起见break action = random.choice(possible_actions)# 使用环境模型模拟这一步next_state, reward, done = mcts_env.simulate_step(current_state, action)total_discounted_reward += current_discount * rewardcurrent_state = next_statecurrent_discount *= gammadepth += 1return total_discounted_reward

反向传播函数

更新从根到模拟节点路径上所有节点的统计信息。

def backpropagate(node: MCTSNode, reward: float) -> None:"""更新路径上所有节点的访问次数和总价值。参数：- node (MCTSNode)：模拟开始的节点。- reward (float)：模拟的结果（总折扣奖励）。"""current_node: Optional[MCTSNode] = nodewhile current_node is not None:current_node.visit_count += 1current_node.total_value += reward # 移动到父节点current_node = current_node.parent

主 MCTS 搜索函数

协调指定次数的迭代。

def mcts_search(root_state: Tuple[int, int],num_simulations: int,exploration_constant: float,rollout_max_depth: int,gamma: float
) -> MCTSNode:"""执行蒙特卡洛树搜索（MCTS）过程，进行指定次数的模拟。参数：- root_state (Tuple[int, int])：搜索的起始状态。- num_simulations (int)：要执行的模拟次数。- exploration_constant (float)：UCT 公式中使用的探索常数（C）。- rollout_max_depth (int)：展开阶段的最大深度。- gamma (float)：展开奖励的折扣因子。返回：- MCTSNode：经过模拟后的搜索树的根节点。"""# 为当前状态创建根节点root_node: MCTSNode = MCTSNode(state=root_state)# 执行指定次数的模拟for _ in range(num_simulations):current_node: MCTSNode = root_node# --- 1. 选择阶段 ---# 使用 UCT 遍历树，直到找到一个叶节点while not current_node.is_terminal() and current_node.is_fully_expanded() and current_node.children:current_node = select_best_child_uct(current_node, exploration_constant)# --- 2. 扩展阶段 ---# 如果当前节点不是终端节点且尚未完全展开，则扩展它simulation_start_node: MCTSNode = current_nodeif not current_node.is_terminal() and not current_node.is_fully_expanded():simulation_start_node = expand_node(current_node)# --- 3. 模拟阶段 ---# 从扩展的节点开始进行展开并计算奖励rollout_reward: float = perform_rollout(simulation_start_node, rollout_max_depth, gamma)# --- 4. 反向传播阶段 ---# 更新路径上所有节点的统计信息backpropagate(simulation_start_node, rollout_reward)# 返回经过模拟后的根节点return root_node

在搜索后选择最佳动作

根据树中的统计信息选择最佳动作（例如，访问次数最多的子节点）。

def choose_best_mcts_action(root_node: MCTSNode) -> int:"""在完成 MCTS 后，从根节点选择最佳动作。通常选择导致访问次数最多的子节点的动作。参数：- root_node (MCTSNode)：经过模拟后的搜索树的根节点。返回：- int：最佳动作。"""best_visit_count = -1best_action = -1if not root_node.children:  # 如果没有展开任何动作（例如，只进行了一次模拟）# 备选方案：如果可能，选择一个随机动作possible_actions = mcts_env.get_possible_actions(root_node.state)if possible_actions:return random.choice(possible_actions)else:return -1  # 或者进行错误处理# 找到导致访问次数最多的子节点的动作for action, child in root_node.children.items():if child.visit_count > best_visit_count:best_visit_count = child.visit_countbest_action = actionif best_action == -1:# 如果所有子节点的访问次数都为 0（在正确的 MCTS 中不应该发生）possible_actions = list(root_node.children.keys())if possible_actions:return random.choice(possible_actions)else:return -1return best_action

使用 MCTS 作为规划器运行

我们模拟一个代理在环境中行动。在每一步，它都使用 MCTS 来决定下一步的动作。

超参数设置

定义 MCTS 的超参数。

# MCTS 在自定义网格世界中的超参数
NUM_SIMULATIONS = 100       # 每次动作选择的 MCTS 迭代次数（预算）
EXPLORATION_C = 1.414       # UCT 探索常数（常见值为 \(\sqrt{2}\)）
ROLLOUT_MAX_DEPTH = 50      # 展开阶段的最大步数
GAMMA_MCTS = 0.99           # 展开奖励的折扣因子NUM_EPISODES_MCTS = 50      # 运行代理的总次数，用于可视化
MAX_STEPS_PER_EPISODE_MCTS = 200 # 每次运行的最大步数

使用 MCTS 的交互循环

代理与环境交互的主要循环，在每一步使用 MCTS。

print(f"开始使用 MCTS 的代理交互（每步模拟次数={NUM_SIMULATIONS}）...")# --- MCTS 交互循环 ---
mcts_run_rewards = []
mcts_run_lengths = []for i_episode in range(1, NUM_EPISODES_MCTS + 1):state: Tuple[int, int] = mcts_env.reset()episode_reward: float = 0.0episode_path: List[Tuple[int, int]] = [state] # 记录路径以供可视化for t in range(MAX_STEPS_PER_EPISODE_MCTS):if mcts_env.is_terminal(state):break # 已经到达目标# --- 使用 MCTS 选择最佳动作 --- root_node = mcts_search(state, NUM_SIMULATIONS, EXPLORATION_C, ROLLOUT_MAX_DEPTH, GAMMA_MCTS)action = choose_best_mcts_action(root_node)# --- ------------------------ ---if action == -1: # 在这个网格世界中，除非到达目标，否则不应该发生print(f"警告：MCTS 返回了无效动作 (-1) 在状态 {state}。")break# 在真实环境中执行选定的动作next_state, reward, done = mcts_env.step(action) # 使用 step() 来推进环境状态state = next_stateepisode_reward += rewardepisode_path.append(state)if done:break# --- 每次运行结束 --- mcts_run_rewards.append(episode_reward)mcts_run_lengths.append(t + 1)# 打印进度if i_episode % 10 == 0:avg_reward = np.mean(mcts_run_rewards[-10:])avg_length = np.mean(mcts_run_lengths[-10:])print(f"第 {i_episode}/{NUM_EPISODES_MCTS} 次运行 | 最近 10 次的平均奖励：{avg_reward:.2f} | 平均长度：{avg_length:.1f}")print("MCTS 代理交互完成。")

开始使用 MCTS 的代理交互（每步模拟次数=100）...
第 10/50 次运行 | 最近 10 次的平均奖励：6.64 | 平均长度：34.6
第 20/50 次运行 | 最近 10 次的平均奖励：6.80 | 平均长度：33.0
第 30/50 次运行 | 最近 10 次的平均奖励：6.54 | 平均长度：35.6
第 40/50 次运行 | 最近 10 次的平均奖励：3.21 | 平均长度：58.8
第 50/50 次运行 | 最近 10 次的平均奖励：7.50 | 平均长度：26.0
MCTS 代理交互完成。

可视化过程

绘制代理使用 MCTS 规划所获得的每次运行的奖励和长度。

可视化代理的路径

我们还可以绘制最后一次运行的路径。

# 绘制 MCTS 代理运行结果
plt.figure(figsize=(20, 5))# 奖励
plt.subplot(1, 3, 1)
plt.plot(mcts_run_rewards)
plt.title(f'MCTS 代理：每次运行的奖励（模拟次数={NUM_SIMULATIONS}）')
plt.xlabel('运行次数')
plt.ylabel('总奖励')
plt.grid(True)
if len(mcts_run_rewards) >= 10:rewards_ma_mcts = np.convolve(mcts_run_rewards, np.ones(10)/10, mode='valid')plt.plot(np.arange(len(rewards_ma_mcts)) + 9, rewards_ma_mcts, label='10 次运行的移动平均', color='orange')plt.legend()# 长度
plt.subplot(1, 3, 2)
plt.plot(mcts_run_lengths)
plt.title(f'MCTS 代理：每次运行的长度（模拟次数={NUM_SIMULATIONS}）')
plt.xlabel('运行次数')
plt.ylabel('步数')
plt.grid(True)
if len(mcts_run_lengths) >= 10:lengths_ma_mcts = np.convolve(mcts_run_lengths, np.ones(10)/10, mode='valid')plt.plot(np.arange(len(lengths_ma_mcts)) + 9, lengths_ma_mcts, label='10 次运行的移动平均', color='orange')plt.legend()# 路径可视化
plt.subplot(1, 3, 3)
if 'episode_path' in locals() and episode_path:rows = mcts_env.rowscols = mcts_env.colspath_grid = np.zeros((rows, cols))for i, (r, c) in enumerate(episode_path):path_grid[r, c] = i + 1 # 标记路径顺序plt.imshow(path_grid, cmap='viridis')plt.title(f"MCTS 代理路径 - 最后一次运行（第 {NUM_EPISODES_MCTS} 次运行）")plt.colorbar(label='步数顺序')# 标记起点和终点start_r, start_c = mcts_env.start_stategoal_r, goal_c = mcts_env.goal_stateplt.text(start_c, start_r, 'S', ha='center', va='center', color='red', weight='bold', fontsize=12)plt.text(goal_c, goal_r, 'G', ha='center', va='center', color='white', weight='bold', fontsize=12)
else:plt.text(0.5, 0.5, "没有路径数据可供可视化。", ha='center', va='center')plt.axis('off')plt.tight_layout()
plt.show()

在这里插入图片描述

MCTS 代理运行曲线分析（网格世界，模拟次数 = 100）：

每次运行的奖励与长度：
代理通常能够获得较高的奖励，并找到相对较短的路径，这从移动平均值接近最优奖励范围以及低步数（约 20-25 步）可以看出。然而，这两个指标都显示出显著的每次运行之间的波动性（例如，在第 32 次运行附近，奖励大幅下降，相应的长度急剧上升）。这种波动性是 MCTS 的典型特征，因为它依赖于每次步骤中的随机模拟来进行规划，而不是像 Q 学习那样收敛到稳定的值。
代理路径（最后一次运行）：
最后一次运行的路径可视化确认了 MCTS 能够找到通往目标的路径。然而，所采取的路径（在这种情况下为 34 步，而 5x5 网格的最优路径长度为 8 步）明显不是最优的。这表明，尽管 MCTS 能够解决问题，但单次运行中找到的路径质量高度依赖于该次运行中的搜索过程，如果没有大量的模拟次数，很难保证每次都找到全局最短路径。

总体结论：
MCTS 作为一种规划算法，每次使用 100 次模拟来决定下一步动作，能够在平均意义上找到通往目标的策略。然而，它的表现虽然强大，但存在较高的波动性，并且在单次运行中找到的路径不一定是全局最优的。这表明 MCTS 在利用模型（隐式模拟器）进行规划方面具有优势，但其每次运行的搜索过程受到随机性和模拟预算的显著影响。

def plot_mcts_derived_policy(env: GridEnvironmentTabular,num_simulations: int, exploration_constant: float, rollout_max_depth: int, gamma: float) -> None:""" 通过从每个状态运行 MCTS 来推导并绘制策略。 """rows: int = env.rowscols: int = env.colspolicy_grid: np.ndarray = np.empty((rows, cols), dtype=str)action_symbols: Dict[int, str] = {0: '↑', 1: '↓', 2: '←', 3: '→'}print("正在推导策略网格（这可能需要一些时间）...")fig, ax = plt.subplots(figsize=(cols * 0.6, rows * 0.6))for r in range(rows):for c in range(cols):state: Tuple[int, int] = (r, c)if env.is_terminal(state):policy_grid[r, c] = 'G'ax.text(c, r, 'G', ha='center', va='center', color='green', fontsize=12, weight='bold')else:# 从这个状态运行 MCTS 来找到最佳动作root_node = mcts_search(state, num_simulations, exploration_constant, rollout_max_depth, gamma)best_action = choose_best_mcts_action(root_node)if best_action != -1:symbol = action_symbols[best_action]else: # 除非状态没有可能的动作（除了目标状态外，这里不会发生）symbol = '?' policy_grid[r, c] = symbolax.text(c, r, symbol, ha='center', va='center', color='black', fontsize=12)print(f"  第 {r+1}/{rows} 行完成。") # 进度提示ax.matshow(np.zeros((rows, cols)), cmap='Greys', alpha=0.1)ax.set_xticks(np.arange(-.5, cols, 1), minor=True)ax.set_yticks(np.arange(-.5, rows, 1), minor=True)ax.grid(which='minor', color='black', linestyle='-', linewidth=1)ax.set_xticks([])ax.set_yticks([])ax.set_title(f"MCTS 推导的策略（模拟次数={num_simulations}）")plt.show()# 绘制推导的策略（可能需要较长时间，尤其是对于较大的网格或较多的模拟次数）
print("\n绘制 MCTS 推导的策略（可能需要较长时间）：")
plot_mcts_derived_policy(mcts_env, NUM_SIMULATIONS // 10, EXPLORATION_C, ROLLOUT_MAX_DEPTH // 2, GAMMA_MCTS) # 使用较少的模拟次数以加快绘图速度

绘制 MCTS 推导的策略（可能需要较长时间）：
正在推导策略网格（这可能需要一些时间）...第 1/5 行完成。第 2/5 行完成。第 3/5 行完成。第 4/5 行完成。第 5/5 行完成。

MCTS 的常见挑战和扩展

挑战：计算成本

问题： 每次步骤中运行大量模拟可能会带来较高的计算成本，限制了其在实时应用中的可行性。
解决方案：
- 并行化： 在多核处理器或多台机器上并行运行模拟。
- 预算调整： 根据可用时间调整模拟次数。
- 更好的展开策略： 更具信息性的展开策略可以减少所需的模拟次数，从而提高价值估计的准确性。
- 函数近似（例如 AlphaZero）： 使用神经网络为动作选择提供先验概率（引导搜索），并直接评估叶节点，减少对深度展开的需求。

挑战：高分支因子

问题： 如果每个状态都有许多可能的动作，那么在扩展阶段探索所有动作会变得非常困难。
解决方案：
- 渐进式扩展（UCT 用于连续动作）： 根据访问次数限制在某个节点展开的动作数量。
- 策略引导： 使用学习到的策略网络（如 AlphaZero 中的）来优先探索有希望的动作。

挑战：模拟质量

问题： MCTS 的准确性依赖于从展开中获得的价值估计。随机展开可能会产生很高的方差，尤其是在奖励稀疏或时间范围较长的环境中。
解决方案：
- 特定领域的展开策略： 如果可用，引入简单的启发式规则。
- 价值网络集成： 使用学习到的价值函数直接评估叶节点，而不是执行完整的展开。

挑战：大状态空间

问题： 在非常大或连续的状态空间中，显式表示树变得不可行，且相同的状态可能很少被访问两次。
解决方案：
- 状态抽象/离散化： 对相似的状态进行分组（可能会丢失一些信息）。
- 函数近似： 在 MCTS 框架中使用神经网络来表示策略和价值估计（例如 AlphaZero、MuZero）。

扩展：

RAVE（快速动作价值估计）： 使用兄弟节点的统计信息来改进价值估计。
渐进式扩展： 处理大/连续的动作空间。
AlphaGo/AlphaZero/MuZero： 将 MCTS 与深度神经网络相结合，用于策略和价值估计，甚至可能用于模型学习。

总结

蒙特卡洛树搜索（MCTS）是一种强大的在线规划算法，能够有效地在复杂的决策问题中平衡探索和利用，以找到好的动作。通过迭代地构建一个由模拟结果（展开）引导的搜索树，它可以在不需要显式启发式评估函数的情况下处理大型状态空间和分支因子。

它在游戏（如围棋）中的成功尤其突出，这突显了它在有模拟器可用的领域中的强大能力。尽管基本的 MCTS 使用随机展开，但其真正的力量往往在于与领域知识或学习组件（如 AlphaZero 中的策略和价值网络）相结合，以更有效地引导搜索和模拟。理解 MCTS 为解决复杂的规划问题提供了基础，并且有助于我们欣赏搜索、模拟和学习在人工智能中的协同作用。

查看全文

http://www.xdnf.cn/news/7393.html