蒙特卡洛树搜索（MCTS）详解

蒙特卡洛树搜索是一种经典的树搜索算法，名镇一时的 AlphaGo 的技术背景就是结合蒙特卡洛树搜索和深度策略价值网络，因此击败了当时的围棋世界冠军。它对于求解这种大规模搜索空间的博弈问题极其有效，因为它的核心思想是 把资源放在更值得搜索的分枝上，即 算力集中在更有价值的地方。

MCTS算法的基本过程

MCTS的算法主要分为四个步骤，分别为 选择、扩展、模拟、回溯。

STEP 1：选择（Selection）

从根节点开始，递归选择最优的子节点，最终到达一个叶子结点。

根据什么去判断节点的优劣呢？Upper Confidence Bounds（UCB）
$$UCB1\left(S_i\right)=\overline{V_i}+c\sqrt{\frac{\log N}{n_i}},c=2$$
其中，$\overline{V_i}$ 为该节点的平均价值大小；$c$ 为常数，通常取2；$N$ 为总探索次数；$n_i$ 为当前节点的探索次数。

有了上面的 UCB 公式，就可以计算所有子节点的 UCB 值，并选择 UCB 值最大的子节点进行迭代。

STEP 2：扩展（Expansion）

如果当前叶子结点不是终止节点，那么就创建一个或者更多的子节点，选择其中一个进行扩展。

STEP 3：模拟（Simulation）

从扩展节点开始，运行一个模拟的输出，直到博弈游戏结束。比如，从该扩展节点出发，模拟了十次，最终胜利九次，那么该扩展节点的得分就会比较高，反之则比较低。这里也给出一个模拟过程的伪代码：

def Rollout(S_i): 
  ## S_i：当前状态
	loop forever: 
    ## 无限循环
		if S_i a terimal state: 
      ## 如果当前状态是博弈的终止状态
      ## 则返回对 S_i 这个状态的价值，跳出循环
			return value(S_i)   
		
		## 如果还没到终止状态
    ## 随机选取当前状态下能够采取的一个动作
		A_i = random(available_action(S_i)) 
    ## 通过当前状态 S_i 与随机选取的动作 A_i 来计算出下一步的状态并赋值给 S_i
		S_i = transform(A_i, S_i)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

STEP 4：回溯（Backpropagation）

使用第三步模拟的结果，反响传播以更新当前动作序列。

举个例子

这个博文里面的例子已经很形象了！这里自己再写一次，加深印象。

https://blog.csdn.net/qq_41033011/article/details/109034887

初始化：最初有一个根节点 $S_0$，树中每个节点都有两个值，节点的价值 $T$ 和 该节点的访问次数 $N$。

第 1 次迭代：节点 $S_0$ 为根节点也是叶节点，并且不是终止节点，因此对其进行扩展。假设 $S_0$ 后有两个策略，转移后分别为 $S_1$ 和 $S_2$。

随后，可以使用 UCB 公式来选择对 $S_1$ 扩展还是对 $S_2$ 扩展。这里 $N_1$ 和 $N_2$ 均为 0，因此两个节点的 UCB 值都是无穷大，因此选哪个节点都可以，这里选择 $S_1$ 进行模拟。模拟后，发现最终值为 20，于是回溯更新。$T_1=20$，$N_1=1$，$T_0=20$，$N_0=1$。

第 2 次迭代：从 $S_0$ 出发进行选择，此时 $S_1$ 的 UCB 值已经不是无穷大了，而 $S_2$ 的 UCB 值仍是无穷大，因此选择 $S_2$ 进行扩展。到了 $S_2$ 后，发现 $S_2$ 为叶子结点，并且没有被探索过，因此对其进行模拟。模拟的结果假设为 10，那么进行回溯。$T_2=10$，$N_2=1$，$T_0=30$，$N_0=2$。

第 3 次迭代：从 $S_0$ 出发，计算 $S_1$ 和 $S_2$ 的 UCB 值，选择较大的进行扩展。
U C B ( S 1 ) = 20 + 2 ∗ ln ⁡ 2 1 = 21.67 U C B ( S 2 ) = 10 + 2 ∗ ln ⁡ 2 1 = 11.67 UCB(S1)=20+2∗√ln21=21.67UCB(S2)=10+2∗√ln21=11.67

​UCB(S1​)=20+2∗1ln2​ ​=21.67UCB(S2​)=10+2∗1ln2​ ​=11.67​
因此，选择 $S_1$ 进行扩展。到了 $S_1$ 后，发现它是叶节点，并且已经被探索过，那么就枚举出当前节点的所有可能的动作，并添加到树中。

然后就可以像之前一样，随机选择 $S_3$ 或者 $S_4$ 进行扩展，以此类推。

Reference

蒙特卡洛树搜索 MCTS 入门：https://blog.csdn.net/qq_41033011/article/details/109034887