蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）

🗒️蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）

date

icon

password

Sub-item

Blocked by

Parent item

type

status

slug

summary

算法步骤

选择（Selection）

扩展（Expansion）

模拟（Simulation）

反向传播（Backpropagation）

1. 选择（Selection）

选择阶段从根节点开始，沿着树选择一个子节点，直到到达一个未完全扩展的节点。

这里解释下，什么节点，以及什么叫未完全扩展的节点

我们可以把每一个节点都认为是一种动作，假设我们现在处于A节点，那就意味着A节点下的abcd节点都是基于A动作而可能的行动

`未完全扩展的节点`指的就是该节点接下来所有可能的行动没有被完全探索过

选择的策略通常是基于“上置信区间应用于树（Upper Confidence Bound 1）”（UCB1）公式。

上置信区间

UCB1公式用于计算每个子节点的得分，选择得分最高的节点进行下一步操作。

是节点的胜利次数。

是节点的访问次数。

是父节点的访问次数。

是探索参数，通常取

公式记忆：

将公式想象成一个权衡装置，左边是当前已知的价值，右边是可能的未知潜力。

左边已知价值：，很简单，胜利次数除以总次数

右边未知潜力：, 也很简单，父节点的访问次数固定，节点被访问得越多，潜力就越小

2. 扩展（Expansion）

在选择阶段结束时，如果选择的节点是非终端状态且未完全扩展，则创建一个或多个子节点。

在选定的叶节点中，检查是否可以扩展。

如果该节点不是终局状态且还未完全展开，则从可能的动作中选择一个未被探索的动作。

根据这个动作生成一个新的子节点，并将其添加到树中。

3. 模拟（Simulation）

从扩展的节点进行随机模拟，直到到达终端状态。模拟的结果用于评估该节点。

4. 反向传播（Backpropagation）

将模拟的结果反向传播到路径上的所有节点，更新它们的访问次数和胜利次数。

举例说明

假设我们在一个简单的井字棋（Tic-Tac-Toe）游戏中使用MCTS。每个节点代表一个棋盘状态，模拟通过随机选择合法的下一个动作来进行。

选择：从根节点（初始棋盘状态）开始，选择具有最高UCB1值的子节点。

扩展：在选择的节点上扩展一个新的可能动作。

模拟：随机模拟直到游戏结束，并返回结果（胜、负、平）。

反向传播：将结果更新到路径上的每个节点。

通过多次迭代，MCTS可以有效地评估每个可能的动作，选择最优的策略

RLHF

简单欧洲史