当前栏目
蒙特卡洛树搜索(MCTS)详解
蒙特卡洛树搜索(MCTS)详解
蒙特卡洛树搜索是一种经典的树搜索算法,名镇一时的 AlphaGo 的技术背景就是结合蒙特卡洛树搜索和深度策略价值网络,因此击败了当时的围棋世界冠军。它对于求解这种大规模搜索空间的博弈问题极其有效,因为它的核心思想是 把资源放在更值得搜索的分枝上,即 算力集中在更有价值的地方。
MCTS算法的基本过程
MCTS的算法主要分为四个步骤,分别为 选择、扩展、模拟、回溯。
STEP 1:选择(Selection)
从根节点开始,递归选择最优的子节点,最终到达一个叶子结点。
根据什么去判断节点的优劣呢?Upper Confidence Bounds(UCB)
U
C
B
1
(
S
i
)
=
V
i
‾
+
c
log
N
n
i
,
c
=
2
U C B 1left(S_{i}
ight)=overline{V_{i}}+c sqrt{frac{log N}{n_{i}}}, c=2
UCB1(Si)=Vi+cnilogN,c=2
其中,
V
i
‾
overline{V_{i}}
Vi 为该节点的平均价值大小;
c
c
c 为常数,通常取2;
N
N
N 为总探索次数;
n
i
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 S_0 S0,树中每个节点都有两个值,节点的价值 T T T 和 该节点的访问次数 N N N。
第 1 次迭代:节点 S 0 S_0 S0 为根节点也是叶节点,并且不是终止节点,因此对其进行扩展。假设 S 0 S_0 S0 后有两个策略,转移后分别为 S 1 S_1 S1 和 S 2 S_2 S2。
随后,可以使用 UCB 公式来选择对 S 1 S_1 S1 扩展还是对 S 2 S_2 S2 扩展。这里 N 1 N_1 N1 和 N 2 N_2 N2 均为 0,因此两个节点的 UCB 值都是无穷大,因此选哪个节点都可以,这里选择 S 1 S_1 S1 进行模拟。模拟后,发现最终值为 20,于是回溯更新。 T 1 = 20 T_1 = 20 T1=20, N 1 = 1 N_1=1 N1=1, T 0 = 20 T_0 = 20 T0=20, N 0 = 1 N_0=1 N0=1。
第 2 次迭代:从 S 0 S_0 S0 出发进行选择,此时 S 1 S_1 S1 的 UCB 值已经不是无穷大了,而 S 2 S_2 S2 的 UCB 值仍是无穷大,因此选择 S 2 S_2 S2 进行扩展。到了 S 2 S_2 S2 后,发现 S 2 S_2 S2 为叶子结点,并且没有被探索过,因此对其进行模拟。模拟的结果假设为 10,那么进行回溯。 T 2 = 10 T_2=10 T2=10, N 2 = 1 N_2 = 1 N2=1, T 0 = 30 T_0=30 T0=30, N 0 = 2 N_0 = 2 N0=2。
第 3 次迭代:从
S
0
S_0
S0 出发,计算
S
1
S_1
S1 和
S
2
S_2
S2 的 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
egin{aligned} &mathrm{UCB}left(mathrm{S_1}
ight)=20+2 * sqrt{frac{ln 2}{1}}=21.67 \ &mathrm{UCB}left(mathrm{S_2}
ight)=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
S_1
S1 进行扩展。到了
S
1
S_1
S1 后,发现它是叶节点,并且已经被探索过,那么就枚举出当前节点的所有可能的动作,并添加到树中。
然后就可以像之前一样,随机选择 S 3 S_3 S3 或者 S 4 S_4 S4 进行扩展,以此类推。
Reference
蒙特卡洛树搜索 MCTS 入门:https://blog.csdn.net/qq_41033011/article/details/109034887
相关文章
- SpringBoot多环境配置,旧的已过时,新的有人还不知道
- Spring Boot集成Druid异常discard long time none received connection.
- SpringBoot集成Swagger3,还想来份离线文档?真酷炫
- 国内首个全接入模式WAF被看好,腾讯云WAF再获Gartner认可
- 一个HTTPS转HTTP的Bug,他们忍了2年,原谅我无法接受,加班改了
- 在elementui组件table的行内使用vue-treeselect无效
- H5 文件预览和下载
- springboot 同时启用http/https
- springboot 使用ResponseEntity实现文件流下载
- (一)Spring Cloud:概念、核心组件以及OpenFegin服务间调用
- 常见请求方式区别
- 动态加载JS文件
- 网页纯JS播放自定义语音播放
- 网页纯JS通过AudioContext播放声音
- 多个WebSecurityJAVA配置导致csrf().disable()配置失效
- Java Spring 框架重要概念整理
- 2022必备react面试题 附答案
- Vue3.0概要小卡片组件
- 网络安全工具集
- 2022社招react面试题 附答案