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

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

MCTS算法的基本过程

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

STEP 1：选择（Selection）

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

根据什么去判断节点的优劣呢？Upper Confidence Bounds（UCB）

(

)

‾

log

⁡

U C B 1\left(S_{i}\right)=\overline{V_{i}}+c \sqrt{\frac{\log N}{n_{i}}}, c=2

UCB1(Si)=Vi+cnilogN
,c=2

其中，

‾

\overline{V_{i}}

Vi 为该节点的平均价值大小；

c 为常数，通常取2；

N 为总探索次数；

n_i

ni 为当前节点的探索次数。

有了上面的 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)

STEP 4：回溯（Backpropagation）

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

举个例子

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

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

初始化：最初有一个根节点

S_0

S0，树中每个节点都有两个值，节点的价值

T 和该节点的访问次数

N。

第 1 次迭代：节点

S_0

S0 为根节点也是叶节点，并且不是终止节点，因此对其进行扩展。假设

S_0

S0 后有两个策略，转移后分别为

S_1

S1 和

S_2

S2。

随后，可以使用 UCB 公式来选择对

S_1

S1 扩展还是对

S_2

S2 扩展。这里

N_1

N1 和

N_2

N2 均为 0，因此两个节点的 UCB 值都是无穷大，因此选哪个节点都可以，这里选择

S_1

S1 进行模拟。模拟后，发现最终值为 20，于是回溯更新。

T_1 = 20

T1=20，

N_1=1

N1=1，

T_0 = 20

T0=20，

N_0=1

N0=1。

第 2 次迭代：从

S_0

S0 出发进行选择，此时

S_1

S1 的 UCB 值已经不是无穷大了，而

S_2

S2 的 UCB 值仍是无穷大，因此选择

S_2

S2 进行扩展。到了

S_2

S2 后，发现

S_2

S2 为叶子结点，并且没有被探索过，因此对其进行模拟。模拟的结果假设为 10，那么进行回溯。

T_2=10

T2=10，

N_2 = 1

N2=1，

T_0=30

T0=30，

N_0 = 2

N0=2。

第 3 次迭代：从

S_0

S0 出发，计算

S_1

S1 和

S_2

S2 的 UCB 值，选择较大的进行扩展。

(

)

∗

⁡

21.67

(

)

∗

⁡

11.67

\begin{aligned} &\mathrm{UCB}\left(\mathrm{S_1} \right)=20+2 * \sqrt{\frac{\ln 2}{1}}=21.67 \\ &\mathrm{UCB}\left(\mathrm{S_2}\right)=10+2 * \sqrt{\frac{\ln 2}{1}}=11.67 \end{aligned}

UCB(S1)=20+2∗1ln2
=21.67UCB(S2)=10+2∗1ln2
=11.67

因此，选择

S_1

S1 进行扩展。到了

S_1

S1 后，发现它是叶节点，并且已经被探索过，那么就枚举出当前节点的所有可能的动作，并添加到树中。