蒙特卡洛树搜索入门教程( 二 ) _蒙特卡洛树

Rollout Policy也被称作快速走子策略，基于一个状态选择一个动作。为了让这个策略能够simulation快，一般选用随机分布(uniform random) 。如下图所示

文章插图

2.1.1 Alpha Zero中的Playout/Simulation在AlphaGo Zero里面DeepMind‘s直接用一个CNN残差网络输出position evaluation和moves probability 。
2.2 博弈树节点的扩展-全扩展、访问节点一个节点如果被访问过了，意味着某个某个simulation是以它为起点的。如果一个节点的所有子节点都被访问过了，那这个节点就称为是完全扩展的，否则就是未完全扩展的。如下图对比所示：

文章插图

在实际过程中，一开始根节点的所有子节点都未被访问，从中选一个，第一次simulation就开始了。
Simulation过程中rollout policy选择子节点是不被考虑为这个子节点被访问过了，只有Simulation开始的节点被标记为访问过的。
2.3 反向传播Simulation结果从一个近期访问过的节点(有时候也叫做叶结点(left node))做Simulation，当他Simulation完成之后，得出来的结果就需要反向传播回当前博弈树的根结点，Simulation开始的那个节点被标记为访问过了。

文章插图

反向传播是从叶结点(simulation 开始的那个节点)到根结点。在这条路径上所有的节点统计信息都会被计算更新。
2.4 Nodes’ statistics拿到simulation的结果主要更新两个量：所有的simulation reward 和所有节点 (包括simulation开始的那个节点)的访问次数。

- 表示一个节点的 simulation reward和，最简单形式的就是所有考虑的节点的模拟结果之和。
- 表示节点的另一个属性，表示这个节点在反向传播路径中的次数(也表示它有多少次参与了total simulation reward)的计算。

2.5 遍历博弈树搜索开始时，没有被访问过的节点将会首先被选中，然后simulation，结果反向传播给根结点，之后根节点就可以被认为是全展开的。
为了选出我们路径上的下一个节点来开始下一次模拟，我们需要考虑的所有子节点 , , , 和其本身节点的信息，如下图所示：

文章插图

当前的状态被标记为蓝色，上图它是全展开的，因此它被访问过了并且存储了节点的统计信息：总的仿真回报和访问次数，它的子节点也具备这些信息。这些值组成了我们最后一个部分：树的置信度上界（Upper Confidence Bound Applied to Trees，UCT）。
2.6 置信度上界【蒙特卡洛树搜索入门教程】UCT是蒙特卡罗树搜索中的一个核心函数，用来选择下一个节点进行遍历：
蒙特卡洛树搜索的过程中选UCT最大的那个遍历。
UCT 中第一部分是，也被称作 exploitation component，可以看作是子节点的胜率估计(总收益/总次数=平均每次的收益) 。
看起来这一项已经有足够说服力，因为只要选择胜率高的下一步即可，但是为什么不能只用这一个成分呢？这是因为这种贪婪方式的搜索会很快导致游戏结束，这往往会导致搜索不充分，错过最优解。因此UCT中的第二项称为exploration component 。这个成分更倾向于那些未被探索的节点( 较小) 。在蒙特卡洛树搜索过程中第二项的取值趋势大概如下图所示，随着迭代次数的增加其值也下降：

文章插图

参数
用于平衡MCTS中的exploitation和exploration 。
2.6.1 UCT in Alpha Go and Alpha Zero在AlphaGo Lee和Alpha Zero算法里面，UCT公式如下：
是来自策略网络的move先验概率，策略网络是从状态得到move分布的函数，目的是为了提升探索的效率。
当游戏视角发生变化的时候exploitation component 也会发生变化。
2.6.2 Alpha Go和Alpha Zero中的策略网络在 AlphaGo 算法里，有两个policy网络：

SL Policy Network ：基于人类数据的监督学习所得的网络。
RL Policy Network ：基于强化学习自我博弈改进SL Policy Network 。

Interestingly – in Deepmind’s Monte Carlo Tree Search variant – SL Policy Network output is chosen for prior move probability estimation as it performs better in practice (authors suggest that human-based data is richer in exploratory moves). What is the purpose of the RL Policy Network then? The stronger RL Policy Network is used to generate 30 mln positions dataset for Value Network training (the one used for game state evaluation)