蒙特卡洛树搜索ucb_蒙特卡洛树搜索的主要流程[通俗易懂]

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

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

MCTS算法的基本过程

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

STEP 1：选择（Selection）

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

根据什么去判断节点的优劣呢？Upper Confidence Bounds（UCB）
$1\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)

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 值，选择较大的进行扩展。
$\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}$
因此，选择 $S_1$ 进行扩展。到了 $S_1$ 后，发现它是叶节点，并且已经被探索过，那么就枚举出当前节点的所有可能的动作，并添加到树中。