蒙特卡洛树搜索MCTS

AlphaGo Zero跟AlphaGo的最大区别是抛弃人类棋谱的，完全通过自我对弈来学会下棋的，并且仅用40小时就到达了AlphaGo的棋力。

过程是这样，首先生成棋谱，然后将棋谱作为输入训练神经网络，训练好的神经网络用来预测落子和胜率。如下图：

在AlphaGo Zero中蒙特卡洛树搜索主要是用来生成棋谱的

MCTS算法是一种决策算法，每次模拟（simulation）分为4步：

第一、二步的流程（遍历、拓展节点）：

1.从状态S0开始，要在下面两个动作中进行选择（假设只有两个动作可选），选择的标准就是 值， 选择最大化 UCT 的节点作为下一个节点 。初始情况两个 ,按顺序选择S1

2.判断目前的结点S1(current node)是不是叶节点，这里叶节点是指其没有被展开（expansion）过。

3.接下来，按照流程图，需要判断结点S1被访问的系数是否为0。是0，则要进行Rollout。(Rollout其实就是在接下来的步骤中每一步都随机采取动作，直到停止点（围棋中的对局结束），得到一个最终的value。)==假设Rollout最终值为20.

4.Backpropagation，即利用Rollout最终得到的value来更新路径上每个结点的T,N值。(之后把Rollout的结果删除：MCTS的想法就是要从出S0发不断的进行迭代，不断更新结点值，直到达到一定的迭代次数或者时间。)

5.如果没有达到一定的迭代次数或者时间，继续从根节点进行1-4

第三步rollout模拟:

例子说明见: 蒙特卡洛树搜索（MCTS）算法-计算过程 ，视频讲解见B站: 【MCTS】Youtube上迄今为止最好的蒙特卡罗树搜索讲解

相比极大极小法（minimax）。这个策略假定你的对手发挥了最好的博弈水平，然后以此调整策略来最大化你的收益。简单地说，给定状态，你想要找到一个能产生最大收益的 move ，假定你的对手想要最小化你的收益（最大化他自己的收益）。因此，名字叫作 极小化极大 。

极小化极大算法的最大劣势 是，需要扩展整个博弈树。对于分支因子较高的博弈（例如围棋或者国际象棋），这会导致庞大的博弈树从而失败。

UCT是一个让我们从已访问的节点中选择下一个节点来进行遍历的函数，也是MCTS的核心函数。

第一部分是 ，也称作exploitation component

可以看做是子节点Vi的胜率估计（总收益/总次数=平均每次的收益）。但是不能只选择胜率高的下一步，因为这种贪婪方式的搜索会很快导致游戏结束，这往往会导致搜索不充分，错过最优解。

举个简单的例子。现在假设MCTS的UCT函数只用了探索成分，从根节点开始，我们对所有子节点进行了一次模拟，然后在下一步中只访问至少赢了一次的子节点。那么在第一次模拟中那些不幸未被选中的节点（实际中rollout策略函数通常是随机的）将会被立刻抛弃

，这个成分更倾向于那些想对较少被探索的节点N(Vi)小。

参数c是exploitation和exploration之间的折中系数。

终止条件(or)：

当MSCT程序结束时，最佳的移动通常是访问次数最多的那个节点，也是UCT最大的点。

深度学习入门：AlphaGo Zero蒙特卡洛树搜索

蒙特卡洛树搜索（MCTS）算法-计算过程

【MCTS】Youtube上迄今为止最好的蒙特卡罗树搜索讲解

python实现的基于蒙特卡洛树搜索(MCTS)与UCB的五子棋游戏

mctspy：蒙特卡洛树搜索算法的python实现

阿法狗用的什么算法？

阿尔法围棋（AlphaGo）的主要工作原理是“深度学习”。“深度学习”是指多

层的人工神经网络和训练它的方法。一层神经网络会把大量矩阵数字作为输入，通过非线性激活方法取权重，再产生另一个数据**作为输出。这就像生物神经大脑的工作机理一样，通过合适的矩阵数量，多层组织链接一起，形成神经网络“大脑”进行精准复杂的处理，就像人们识别物体标注图片一样。　

主要包括4个部分：

1. 走棋网络（Policy Network），给定当前局面，预测/采样下一步的走棋。

2. 快速走子（Fast rollout），目标和1一样，但在适当牺牲走棋质量的条件下，速度要比1快1000倍。

3. 估值网络（Value Network），给定当前局面，估计是白胜还是黑胜。

4. 蒙特卡罗树搜索（Monte Carlo Tree Search，MCTS)，把以上这三个部分连起来，形成一个完整的系统。

阿尔法围棋（AlphaGo）是通过两个不同神经网络“大脑”合作来改进下棋。这些大脑是多层神经网络跟那些Google图片搜索引擎识别图片在结构上是相似的。它们从多层启发式二维过滤器开始，去处理围棋棋盘的定位，就像图片分类器网络处理图片一样。经过过滤，13 个完全连接的神经网络层产生对它们看到的局面判断。这些层能够做分类和逻辑推理。

|阿尔法核心技术

一、 AlphaGo的两大核心技术

MCTS(Monte Carlo Tree Search)

MCTS之于围棋就像Alpha-Beta搜索之于象棋，是核心的算法，而比赛时的搜索速度至关重要。就像深蓝当年战胜时，超级计算机的运算速度是制胜的关键因素之一。

MCTS的4个步骤：Selection，Expansion，Evaluation(rollout)和Backup

MCTS的并行搜索：

(1) Leaf Parallelisation

最

简单的是Leaf Parallelisation，一个叶子用多个线程进行多次Simulation，完全不改变之前的算法，把原来的一次

Simulation的统计量用多次来代替，这样理论上应该准确不少。但这种并行的问题是需要等待最慢的那个结束才能更新统计量；而且搜索的路径数没有增

多。

(2) Root Parallelisation

多个线程各自搜索各自的UCT树，最后投票

(3) Tree Parallelisation

这是真正的并行搜索，用多个线程同时搜索UCT树。当然统计量的更新需要考虑多线程的问题，比如要加锁。

另

外一个问题就是多个线程很可能同时走一样的路径（因为大家都选择目前看起来Promising的孩子），一种方法就是临时的修改

virtual loss，比如线程1在搜索孩子a，那么就给它的Q(v)减一个很大的数，这样其它线程就不太可能选择它了。当然线程1搜索完了之后要记

得改回来。

《A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm》使用了一种lock-free的算法，这种方法比加锁的方法要快很多，AlphaGo也用了这个方法。

Segal

研究了为什么多机的MCTS算法很难，并且实验得出结论使用virtual loss的多线程版本能比较完美的scale到64个线程(当然这是单机一个

进程的多线程程序）。AlphaGo的Rollout是用CPU集群来加速的，但是其它的三个步骤是在一台机器完成的，这个就是最大的瓶颈。