蒙特卡洛搜索树

对于围棋，象棋，五子棋，黑白棋，井字棋这类游戏来说，都属于有限两人零和回合制游戏，这种游戏都可以用博弈树来解决，以井字棋为例，如下图所示：

这就是一棵井字棋的博弈树，当然节点没有完全的展开，我们现在关注显示棋盘的这条路径，从上到下我们可以看到这就是完整的一局游戏，每个分支就代表我们的落子。而且相邻树的层次是对应不同的玩家，这一层是圈，则相邻层都是叉。

那么我们可以把所有的状态都列出来，这样根据当前棋面，我们可以找到最优的路径。但是井字棋我们的确可以这样做，象棋和围棋这类空间很大的棋我们无法做到，因为博弈树太大了，无论是深度还是宽度。

为了解决大空间的问题，这时候蒙特卡洛树搜索就是一种很好的选择，蒙特卡洛搜索树也是一种博弈树，只不过进行搜索时，它不会像上面的极大极小搜索树一样全部搜索，而是启发式搜索。下面具体介绍MCTS的工作流程。

MCTS主要工作流程如下图，分为四步 ：

• 选择
• 扩展
• 模拟
• 回传

选择

 就是选择一个节点，刚开始时，只有根节点，没有子节点可以选择就跳到下一步，扩展，如果有子节点，就根据子节点的价值抽样选择一个，然后再看选择的这个子节点还有没有子节点，如果有，继续往下选择，直到选择到叶子结点。然后进入下一步。

具体，如上图所示，按照一定的策略选择节点，这个策略通常既要兼顾开发，又要兼顾探索，也就说是一个权衡问题。一般采用树的置信上限算法，也就是UCT算法，或者UCT算法的变体，比如AlphaGo算法中的变体。

UCT算法的UCT值越大代表选择到的几率越大，或者说每次选择最大的UCT值，根据实际而定。UCT由两项组成，前者控制开发，后者控制探索，c是控制两者权衡的参数。其中Q是这个节点的价值，Nvi是vi节点的访问次数，Nv是其父节点的访问次数。由此可见，假如只有前一项的话，第一次对根节点下所有的子节点进行模拟时，不幸失败的节点都会被抛弃，再也不会被选择到，这显然是很不合理的，所以加入第二项，节点选择越少，这一项越大，选择到的概率也就越大，这促使我们的策略选择以前没有试过的节点，也就鼓励了探索。

扩展

选择到叶子节点之后，就可以进行扩展，将叶子结点的子节点展开，可以展开一个，也可以展开多个，要根据实际情况而定。比如我们熟知的阿尔法狗算法，每次都展开所有的子节点，然后根据神经网络输出的概率给每个子节点赋值先验概率，这里不多说，感兴趣的去了解阿尔法狗的论文。而正常的MCTS，展开一个的较为常见，其实本质上区别不大，因为我们会记录节点是否已完全展开，没有完全展开的节点，接下来的模拟中会继续展开的，所以本质上展开一个和多个区别不大，因为最终基本都会展开。

具体，如上图所示，当我们选择到一个未被完全展开的节点时，就对该节点进行扩展，展开任意一个未展开的子节点。

模拟

这也是MCTS中较为重要的一步，根据一个策略，通常随机策略的效果就非常不错，借用阿尔法狗第一作者David Silver在伦敦大学强化学习课程中说的一句话：不要以为随机策略是很糟糕的策略，它常常可以取得非常不错的效果。  所以这里我们一般就是采用随机策略，从刚才扩展的叶子结点开始一直模拟到游戏结束。具体什么意思呢？就是从这个叶子结点的局面开始，博弈双方都随机的从可用的地方落子一直到比赛胜负，这个胜负的结果一定程度上就反映了了这个局面的情况，如果胜了，至少可以有种落子的方式可以赢一次不是吗，当然我们也能想象到这个结果是很不可靠的，毕竟随机落子的，事实上确实是不可靠的，但是好处就是快，而且我们可以模拟很多次，上千次，这样即使是随机的，如果大部分都是赢的话，也足以说明这个局面的赢面是大的，所以本质上MCTS就是以频率逼近概率的算法。

回传

上一步模拟出胜负结果之后，这个结果一般是1，-1和0，代表胜负平，然后把这个结果回传，更新这个路径上的节点的值。举个具体的例子，比如说模拟的结果是胜利，也就是1，那么第二步那个叶子结点的价值就加1，当然还有其他的值需要更新，比如选择的次数也要加1，然后它的父节点的值就要加-1，因为是博弈，对对手是胜利，对自己就是失败，所以取相反数，然后父节点的父节点就是加1，依次递归到根节点，更新整个路径上的节点的值。

具体，如上图所示，递归更新整条路径上的节点的值，包括N,Q，等等

最终，上面四个步骤重复了上千次以后，如下图所示，根节点下第二层子节点访问次数最多的那个子节点就作为下一步的实际落子。

阿尔法系列算法

由于传统的蒙特卡洛算法在围棋领域的效果并不理想，远远达不到职业选手的水平，所以DeepMind提出并发展了阿尔法系列算法，大体上是AlphaGo，AlphaGo Zero，AlphaZero。

象棋领域也有相似的特点，也可以用阿尔法算法研究。

相比传统MCTS的改进

前面已经详细的介绍过MCTS了，是一种启发式的博弈树，因为其优越的特性，所以AlphaZero同样没有抛弃MCTS，而是把MCTS和深度学习结合起来。

下图是刚才介绍的MCTS的工作流程：

下图则是AlphaZero中MCTS的工作流程：

首先列出几点区别：

1， 前者节点存储计数N和价值Q，而后者不仅存储了N和Q，还存储了先验概率P，这个P由神经网络输出。

2， 前者和后者的选择阶段的依据公式有区别，前者根据前面提到的UCT算法，后者还在其中加入了先验概率P和一些狄利克雷噪声。

从图中可以清楚看到后者没有模拟了，也就是没有第三步根据随机策略模拟到游戏结束这一步了，而是直接从神经网络获取价值v，而之前的MCTS的这个v需要根据模拟获得，胜为1，负为-1，平为0.现在则是直接从网络输出

具体算法

• 自博弈阶段

  主要进行自博弈，也就是MCTS vs MCTS，目的是为了产生棋谱，这样就可以训练网络了，具体的博弈过程是这样的：首先看S1状态，也就是开局，双方都进行MCTS模拟，这里用的是改进后的MCTS，也就是加入神经网络的MCTS算法，具体模拟过程参考2.1章的介绍，模拟了上千次之后，根据根节点下一层的节点的计数N和一个温度系数计算概率分布，正比于N，也就是说访问次数越多，选择机会越大，但是这里加了温度系数，也是为了鼓励探索未知的节点，这个概率分布就是上图中的π1，这样我们就获得了(S1, π1)数据了，然后根据这个概率分布采样落子，就进入了状态2，也就是S2，同样上面的模拟，模拟上千次以后获得了(S2, π2)数据，这样一直下去就得到了（S3, π3），……，（ST, πT），T就是游戏结束的那一步。最后游戏结束时还获得了这盘棋的胜负情况z，吧z加入到之前所有的数据中，我们就获得了(S1, π1，z)，(S2, π2，z)，……,(ST, πT，z)的数据了，这个数据就是我们神经网络的训练样本，其中S1作为输入特征，π1，z作为标签，前面我们正好也说到，节点的先验概率P由神经网络输出，叶子结点的价值V也是由神经网络输出，P和V其实正好对应这里的π1和z 。

• 训练阶段

  前面我们已经获得了数据样本了，就可以训练神经网络了。

  对应的神经网络结构大致如下：

• 最后附上我用传统的MCTS(蒙特卡洛树搜索)实现的简单井字棋游戏的代码，我的 Github