蒙特卡洛树搜索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实现

蒙特卡洛树搜索（Monte Carlo tree search；简称：MCTS）是一种用于某些决策过程的启发式搜索算法，最引人注目的是在游戏中的使用。一个主要例子是计算机围棋程序，它也用于其他棋盘游戏、即时电子游戏以及不确定性游戏。

比如围棋，棋手需要针对盘面的情况，选择下一步走哪个位置。这个决策过程可以认为是一个决策函数

a = f(s) ，即面对 可能的状态s ， 决策函数f 会提供一个 行动a （落子位置）。当然，我们希望 f 尽可能优秀，其决策a能够尽可能赢棋。

我们也可以将f构造为一颗决策树。从盘面初始状态开始（没有棋子），令初始状态为根节点，第一手棋有19*19=361个位置，因此根节点下面有361个子节点，第二手棋有360个可能的位置，即361个节点下，每个节点又有360个子节点......随着双方的落子，树的分枝越来越多，每个分支最终会进入叶子状态（对局结束，黑胜或白胜）。理论上可以列举所有可能的情况，做一棵完整的决策树，但实际上这个数据量大到不可能实现。因此，我们必须在有限的时间和空间之内，高效的构建一个子树，这是一个不完整但 尽量好的决策树 。

即便只是尽量好的决策，也是很困难的。因为一步棋的好坏通常不能立即判断出来，最终的评判要到下完的时候才能决定谁赢，况且即便赢了棋，也不代表其中每一步都是好的。

但是，无论怎样，必须提供某种方法让AI知道一步棋好不好，也就是要提供一些 启发 ，于是我们可以采用蒙特卡洛树搜索方法。

刚才我们说到下一盘棋不能判定其中走法的好坏，但如果下很多次呢？比如在某个特定盘面s1情况下，进行n次对局（接着s1盘面往后走），如果统计下来黑棋赢得多，说明s1情况对黑棋比较有利。这就是蒙特卡洛方法的思想，用大量随机事件逼近真实情况。

虽然通过蒙特卡罗方法可以近似估计一个状态的好坏，但我们依然无法对太多状态进行估算。因此，我们需要有选择的集中力量对决策树中的可能更有价值的那些节点进行估算。这就需要使用蒙特卡洛树搜索，它提供了一种选择机制，使我们能够尽量选择决策树中比较有潜力的节点进行蒙特卡洛模拟，从而使得树可以尽量集中在“较好”的策略上进行“生长”。

蒙特卡洛树搜索有四个主要步骤扰乎：

从根节点R开始，选择连续的子节点向下至叶子节点L。让决策树向最优的方向扩展，这是蒙特卡洛树搜索的精要所在。也就是要选择一个尽量”有潜力“的树节点，那么怎样的节点是有潜力呢？ 一个是胜率高，另一个是被考察的次数少 。

胜率高的节点（状态）意味着最后赢棋的概率较大，当然应该多花凳顷些精力分析其后续走法。被考察次数少的节点意味着该节点（状态）尚未经过充分研究，有成为黑马的可能。

具体来说，通常用UCB1（Upper Confidence Bound，上置信区间）公式来计算一个节点的”潜力“：

wi：第 i 次移动后取胜的次数

ni：第 i 次移动后仿真的次数

c：探索参数/权衡参数，理论上等于 根号2，在实际中通常可凭经验选择

t：仿真总次数，等于所有 ni 的和

看一个例缓粗悉子（参考 28 天自制你的 AlphaGo（五） ）

上图中每个节点代表一个局面。而 A/B 代表这个节点被访问 B 次，黑棋胜利了 A 次。例如一开始的根节点是 12/21，代表总共模拟了 21 次，黑棋胜利了 12 次。

图中展示了蒙特卡洛树搜索的四个步骤，我们先看左边第一个树（Selection）。假设根节点是轮到黑棋走。那么我们首先需要在 7/10、5/8、0/3 之间选择，采用上面的UCB1公式：

假设 C 比较小（比如C=1），上述3个分数为 1.25 1.245 1，于是我们选择 7/10 节点（它得分1.25是最高的）。然后接下来 7/10 下面的 2/4 和 5/6 之间选择。注意，由于现在是白棋走，需要把胜率估计倒过来。即图上黑棋胜率是 2/4 和 5/6，则白棋胜率是 (1 - 2/4) 和 (1 - 5/6)：

那么白棋应该选 2/4 节点。（图中扩展的是 5/6 节点，这不是很合理）。

在所选的叶子节点L，如果已经能判定输赢，则该轮游戏结束，否则创建一个或多个子节点并选取其中一个节点C。

看上图第2个树（Expansion），假设黑棋选择了（当前的）叶子节点 3/3，然后创建了一个子节点，初始状态 0/0。

从节点C开始，用随机策略进行游戏，直到分出输赢（获得一次准确的回报）。这一步骤又称为playout或者rollout。

虽然原则上蒙特卡洛方法是采用随机策略，不过实际中也可以采用一些“有经验”的策略，或者两者的结合。所谓有经验的策略就像一个有一定水平的棋手，ta 可以下出一些比较好的走法。我们可以在仿真的某个阶段采用棋手的走法，另外一些阶段采用随机走法。

不过总的来说，仿真需要很快速的完成，这样才能得到尽量多的仿真结果，使统计结果逼近真实的胜率。

看上图第3个树（Simulation），黑棋从 0/0 节点开始进行模拟游戏直到终局，假设黑棋输，所以得分是 0/1。

使用随机游戏的结果，更新从C到R的路径上的节点信息。

看上图第4个树（Backpropagation），从 0/0 节点开始遍历父节点，直到根节点R，这条路径上的每个节点都添加一个 0/1。

当构建了一棵蒙特卡洛树以后，需要用它来做决策时，应该选择访问量最大的节点，而不是胜率最高的节点，也不是UCB分数最高的节点。

访问量不够大的节点，即使胜率高，也不够可靠（因为模拟次数不够多）。而访问量最大的节点，通常也有一定的胜率，想想UCB公式，如果胜率不高是不会经常被选中的（访问量不会大）。所以采用访问量最大的节点，AI的表现会更加稳定。

对于围棋AI，仅使用蒙特卡洛树搜索是不够的，尤其是 AlphaGO 这样的顶级AI，更多分析请参考：

左右互搏，青出于蓝而胜于蓝？阿尔法狗原理解析

28 天自制你的 AlphaGo（五）

AlphaGo背后的力量：蒙特卡洛树搜索入门指南

蒙特卡洛树搜索（MCTS）算法

维基百科——蒙特卡洛树搜索

维基百科——蒙特卡罗方法

蒙特卡罗方法的解题过程可以归结为三个主要步骤:构造或描述概率过程实现从已知概率分布抽样建立各种估计量。

蒙特卡罗方法解题过程的三个主要步骤:

(1)构造或描肢扮述概率过程

(2)实现从已知概率分布抽样

(3)建立各种估计量

应用到期权上一定程度上你可以这么理解，但不完全相同，因为有的时候会过于简单，蒙特卡罗过程如果本身的历物灶设定是偏离实际的，会没有意义，所以二叉树是一种比较理想的状蚂帆态而已。

如果能知道自己喜欢的又觉得不错的就可以了用手机啦。

---