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

蒙特卡洛算法一般指蒙特·卡罗方法，也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。

与它对应的是确定性算法。蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学（如粒子输运计算、量子热力学计算、空气动力学计算）等领域应用广泛。

特点和应用：

通常蒙特·卡罗方法通过构造符合一定规则的随机数来解决数学上的各种问题。对于那些由于计算过于复杂而难以得到解析解或者根本没有解析解的问题，蒙特·卡罗方法是一种有效的求出数值解的方法。一般蒙特·卡罗方法在数学中最常见的应用就是蒙特·卡罗积分。

蒙特卡罗方法在金融工程学，宏观经济学，生物医学，计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算、核工程)等领域应用广泛。

1、首先我们启动matlab，新建一个函数文件。

2、在d出的编辑窗口中输入如下代码。该代码的目的是创建蒙特卡洛主函数。

3、然后我们保存该函数文件。

4、再建立一个函数文件，输入代码如下。该代码的目的是构造积分函数，保存上面的积分函数文件。

5、在命令行窗口中直接调用该函数，如图所示为求得的结果。

6、绘制出积分区域即可。

---