蒙特卡洛树搜索（MCTS）

前向搜索

前向搜索算法从当前状态节点 $S_{t}$ 开始，对该状态节点所有可能的动作进行扩展，建立一颗以 $S_{t}$ 为根节点的搜索树

前向搜索

前向搜索在状态动作数量都很少的时候没有问题，但是只要稍微状态动作数量多一点，每个状态的选择就都特别慢了

简单蒙特卡洛搜索

简单蒙特卡罗搜索基于一个强化学习模型 $M_{v}$ 和一个模拟策略 $\pi$ .在此基础上，对于当前我们要选择动作的状态 $S_{t}$ , 对每一个可能采样的动作 $a\in A$ ,都进行 $K$ 轮采样，这样每个动作 $a$ 都会得到 $K$ 组经历完整的状态序列(episode)。即：

$\left\{ S_{t} ,a,R_{t},S_{t+1}^k,A_{t+1}^k,......S_{T}^k \right\} _{k=1}^K$ ~ $M_{v} ,\pi$

现在对于每个 $(S_{t} ,a)$ 组合，我们可以基于蒙特卡罗法来计算其动作价值函数并选择最优的动作了。

$Q(S_{t} ,a)=\frac {1}{K} \sum_{k=1}^K G_{t}$

$a_{t} =argmax_{a\in A} Q(S_{t} ,a)$

简单蒙特卡罗搜索和起前向搜索比起来，对于状态动作数量的处理能力上了一个数量级,可以处理中等规模的问题。但是假如我们的状态动作数量达到非常大的量级，比如围棋的级别,那么简单蒙特卡罗搜索依然很慢

蒙特卡洛树搜索

上限置信区间算法（UCT)

考虑这样一种情况：在状态 $S_{t}$ 下有两个动作可以选择：第一个动作的历史模拟结果为0胜1负，第二个动作的历史模拟结果为4胜6负，那么现在应该选择哪一个动作？

如果按照 $\epsilon -greedy$ 的方法，那么选择第二个动作的概率会很大，但是，第一个动作的胜率为0很可能是因为历史数据过少，也许第一个动作模拟10次之后的结果是6胜4负

UCT算法首先计算每一个可选动作对应的分数，这个分数考虑了模拟结果和探索度

$score=\frac{w_{i} }{n_{i} } +c\sqrt{\frac{\ln N_{i} }{n_{i} } }$

其中， $w_{i}$ 是节点 $i$ 的胜利次数， $n_{i}$ 是节点 $i$ 的模拟次数， $N_{i}$ 是所有模拟次数， $c$ 是探索常数，理论值为 $\sqrt{2}$ ，可根据经验调整， $c$ 越大就越偏向于广度搜索， $c$ 越小就越偏向于深度搜索。最后我们选择分数最高的动作。

棋类游戏的MCTS搜索

蒙特卡洛树的结点中保存状态对应的历史记录，边中保存选择的动作

MCTS的搜索步骤

每一次MCTS搜索都要进行以下4步：

第一步是选择(Selection):这一步会从根节点开始，每次都选一个“最值得搜索的子节点”，一般使用UCT选择分数最高的节点，直到来到一个“存在未扩展的子节点”的节点，如图中的 3/3 节点。之所以叫做“存在未扩展的子节点”，是因为这个局面存在未走过的后续着法，也就是MCTS中没有后续的动作可以参考了（注：只要当前结点存在没有被搜索的动作就停止）。这时我们进入第二步。

第二步是扩展(Expansion)，在这个搜索到的存在未扩展的子节点，加上一个0/0的子节点，表示没有历史记录参考。这时我们进入第三步。

第三步是仿真(simulation)，从上面这个没有试过的着法开始，用一个简单策略比如快速走子策略（Rollout policy）走到底，得到一个胜负结果。快速走子策略一般适合选择走子很快可能不是很精确的策略。因为如果这个策略走得慢，结果虽然会更准确，但由于耗时多了，在单位时间内的模拟次数就少了，所以不一定会棋力更强，有可能会更弱。这也是为什么我们一般只模拟一次，因为如果模拟多次，虽然更准确，但更慢。

第四步是回溯(backpropagation), 将我们最后得到的胜负结果回溯加到MCTS树结构上。注意除了之前的MCTS树要回溯外，新加入的节点也要加上一次胜负历史记录，如上图最右边所示。

以上就是MCTS搜索的整个过程。这4步一般是通用的，但是MCTS树结构上保存的内容而一般根据要解决的问题和建模的复杂度而不同。

AlphaGo Zero 强化学习原理

AlphaGo Zero的两个模型

MCTS：如上文，用于指导行棋

神经网络：输入为当前棋局状态，输出每一个动作选择的概率 $p$ 以及对当前状态的胜负的预测 $v$ ，神经网络为MCTS提供“简单策略”

对于每一个对局，AlphaGo Zero会从初始状态 $S_{1}$ 开始，对该状态进行1600次MCTS模拟，使用神经网络作为简单策略，在模拟过后，MCTS会对该状态下的每一个动作的打分产生策略 $\pi$ ，MCTS会选择落子位置，得到下一个状态 $S_{2}$ 。重复执行上述过程，直到分出胜负 $z$ ，神经网络使用 $(S,\pi ,z)$ 进行更新，损失函数为

$L=(z-v)^2-\pi ^T\ln p+c\vert \vert \theta \vert \vert ^2$

AlphaGo Zero神经网络的输入和输出

神经网络的输入

神经网络的输入是一个19x19x17的张量。里面包含黑棋和白棋的最近8步行棋状态和当前行棋方的信息。

神经网络的输出包括策略部分和价值部分。策略部分预测当前各个行棋点落子的概率。由于围棋有361个落子点，加上还可以Pass一手，因此一共有362个策略端概率输出。价值端输出就是当前局面胜负的评估值，在[-1,1]之间。

AlphaGo Zero的MCTS搜索

MCTS结点保存的信息：

边访问次数 $N(s,a)$

合计行动价值 $W(s,a)$

平均行动价值 $Q(s,a)$

选择该边的先验概率 $P(s,a)$

MCTS中UCT的计算公式：

$U(s,a)=c_{puct} P(s,a)\frac{\sqrt{\sum N(s,b) } }{1+N(s,a)}$

$a_{t} =argmax_{a} (Q(s,a)+U(s,a))$

MCTS是如何拓展结点的

$\left\{ N(s_{L} ,a)=0,W(s_{L},a )=0,Q(s_{L},a )=0,P(s_{L},a )=P_{a} \right\}$

其中 $P_{a}$ 为神经网络预测的该动作的执行概率

MCTS的回溯

$N(s_{t} ,a_{t} )=N(s_{t} ,a_{t} )+1$

$W(s_{t} ,a_{t} )=W(s_{t} ,a_{t} )+v$

$Q(s_{t},a_{t} )=\frac{W(s_{t},a_{t} )}{N(s_{t},a_{t} )}$

MCTS计算动作选择的概率

$\pi (a\vert s)=\frac{N(s,a)^\frac{1}{\tau } }{\sum\nolimits N(s,b)^\frac{1}{\tau } }$

其中， $\tau$ 为温度参数，控制探索的程度， $\tau$ 越大，不同走法间差异变小，探索比例增大，反之，则更多选择当前最优操作。每一次完整的自我对弈的前30步，参数 $\tau =1$ ，这是早期鼓励探索的设置。游戏剩下的步数，该参数将逐渐降低至0。

AlphaGo Zero的MCTS和神经网络

上图显示的是AlphaGo Zero的训练过程，对于每一场对局，从初始状态 $s_{1}$ 开始，使用MCTS进行搜索（在搜索过程中使用神经网络进行拓展），得到该状态下的"最佳"策略 $\pi _{1}$ ，从中选择动作 $a_{1}$ ，得到下一个状态 $s_{2}$ ，重复执行上述过程直到一场对局结束得到奖励 $z$ 。接着，用 $z$ 和 $\pi _{i}$ 反过来对神经网络进行训练（神经网络输入为 $s_{i}$ ）