3.5 Monte Carlo Tree Search (蒙特卡洛树搜索)
对于像围棋这样具有大分支因子的应用，minimax 无法再使用。对于此类应用，我们使用 Monte Carlo Tree Search (MCTS)（蒙特卡洛树搜索）算法。MCTS 基于两个想法：
- Evaluation by rollouts（通过模拟评估）：从状态 \(s\) 开始，使用某种策略（例如随机）进行多次博弈，并计算胜/负次数。
- Selective search（选择性搜索）：探索树的部分区域，不受视野限制，这将改善根节点的决策。
在围棋示例中，从给定状态开始，我们根据策略多次博弈直到结束。我们记录获胜的比例，这与状态的值有很好的相关性。
考虑以下示例：
从当前状态，我们有三种不同的可用动作（左、中和右）。我们对每个动作执行 \(100\) 次，并记录每个动作的获胜百分比。模拟之后，我们相当确信右边的动作是最好的。在这种情况下，我们为每个替代动作分配了相同数量的模拟。然而，经过几次模拟后可能会变得很清楚，某个动作不会带来很多胜利，因此我们可能会选择将计算精力分配给其他动作做更多的模拟。这种情况可以在下图中看到，我们决定将中间动作剩余的 \(90\) 次模拟分配给左边和右边的动作。
当某些动作产生相似的获胜百分比，但其中一个动作使用的模拟次数远少于估计该百分比所需的次数时，就会出现一个有趣的情况，如下图所示。在这种情况下，使用较少模拟次数的动作的估计值将具有较高的方差，因此我们可能希望为该动作分配更多的模拟次数，以便更确信真实的获胜百分比。
UCB algorithm（UCB 算法）通过在每个节点 \(n\) 使用以下标准来捕捉“有希望”和“不确定”动作之间的权衡：
\[UCB1(n)=\frac{U(n)}{N(n)}+C\times\sqrt{\frac{\log N(PARENT(n))}{N(n)}}\]其中 \(N(n)\) 表示从节点 \(n\) 开始的 rollouts（模拟）总数，\(U(n)\) 表示 \(Player(Parent(n))\) 的获胜总数。第一项捕捉节点的前景如何，而第二项捕捉我们要对该节点效用的不确定程度。用户指定的参数 \(C\) 平衡我们在两项中放置的权重（“exploration”（探索）和“exploitation”（利用）），并取决于应用程序以及任务的阶段（在后期阶段，当我们积累了许多试验时，我们可能会减少探索并增加利用）。
MCTS UCT 算法在树搜索问题中使用 UCB 标准。更具体地说，它多次重复以下三个步骤：
- 使用 UCB 标准从根节点向下移动树的层级，直到到达未展开的叶节点。
- 向该叶节点添加一个新的子节点，并从该子节点运行 rollout（模拟）以确定该节点的获胜次数。
- 我们将子节点的获胜次数更新回根节点。
一旦上述三个步骤重复足够多次，我们选择导致具有最高 \(N\) 的子节点的动作。请注意，因为 UCT 本质上会更多次地探索更有希望的子节点，随着 \(N \rightarrow \infty\)，UCT 接近 minimax 代理的行为。