蒙特卡洛树搜索

1. MCTS 核心思想

对于像围棋这样分支因子极大的应用，传统的Minimax及其变种算法因计算量过大而不再适用。蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS） 为此类问题提供了强大的解决方案。

MCTS基于两个核心理念：

1. 通过模拟进行评估 (Evaluation by Rollouts)：从一个状态 $s$ 开始，使用一个固定的策略（例如，完全随机的策略）进行多次模拟，直到游戏结束。通过统计这些模拟中的胜率来评估状态 $s$ 的好坏。
2. 选择性搜索 (Selective Search)：不设搜索深度限制，而是智能地、非对称地探索博弈树。将更多的计算资源投入到那些看起来更有希望或更不确定的部分，从而有效地指导根节点的决策。

2. 探索与利用的权衡

在MCTS中，一个核心问题是如何分配有限的模拟次数。

• 利用 (Exploitation)：我们应该把更多的模拟次数分配给当前看起来胜率最高的行动，以确认它的优势。
• 探索 (Exploration)：我们也应该给那些模拟次数较少的行动一些机会。因为它们的胜率估算可能因为样本太少而方差很大，也许其中就隐藏着真正的最优解。

MCTS通过一个精妙的准则来平衡这两者。

$a.$ UCB1 (Upper Confidence Bound 1) 公式

UCB1算法为博弈树中的每个节点 $n$ 计算一个分数，用于在搜索过程中选择下一个要探索的节点。这个分数完美地体现了探索与利用的权衡。

公式各项的含义如下：

• $N(n)$：节点 $n$ 被访问（经历模拟）的总次数。
• $U(n)$：在经过节点 $n$ 的所有模拟中，其父节点的玩家获胜的总次数。
• $PARENT(n)$：节点 $n$ 的父节点。
• $C$：一个用户指定的探索常数。$C$ 值越大，算法越倾向于探索未知或访问次数少的节点。
• $\frac{U(n)}{N(n)}$ 就是节点 $n$ 的平均胜率。这个值越高，说明这个节点越“有希望”。
  • 分母是 $N(n)$，这意味着一个节点被访问的次数越多，这一项的值就越小，探索的紧迫性就越低。
  • 分子包含 $\log N(PARENT(n))$，确保随着模拟总数的增加，所有子节点最终都会被充分探索。

3. MCTS 的 UCT 算法流程

UCT（Upper Confidence bounds for Trees） 是将UCB1准则应用于树搜索的标准MCTS算法。它在一个循环中反复执行以下四个步骤：

1. 选择 (Selection)
   从根节点开始，递归地使用UCB1公式选择子节点。在每一层都选择UCB1分数最高的那个子节点，直到到达一个未被完全扩展的节点（即该节点有尚未被创建的子节点）或叶子节点。
2. 扩展 (Expansion)
   如果选择阶段停止的节点 $L$ 不是终止状态，就在其下创建一个或多个新的子节点。从中选择一个新节点 $C$（例如，随机选择）。
3. 模拟 (Simulation)
   从新节点 $C$ 开始，使用一个快速的默认策略（Default Policy）（通常是随机选择合法行动）进行一次完整的游戏模拟，直到游戏结束。
4. 反向传播 (Backpropagation)
   将模拟的结果（赢或输）从新节点 $C$ 开始，沿着选择阶段的路径一路向上传播回根节点。在路径上的每个节点，都要更新其统计数据：
   • 访问次数 $N(n)$ 加一。
   • 如果模拟结果是胜利，则获胜次数 $U(n)$ 加一。

这个“选择-扩展-模拟-反向传播”的循环会重复进行成千上万次。

最终决策

当分配的计算时间或模拟次数用尽后，算法停止。最终的决策非常简单：在根节点的所有子节点中，选择那个被访问次数 $N(n)$ 最多的节点所对应的行动。

因为UCT算法的内在机制会使得更有希望的子节点被访问得更多，所以访问次数最多的那个通常就是最优的选择。随着模拟次数趋于无穷，UCT算法的行为会收敛于完美的Minimax玩家。