蒙特卡洛搜索树python,蒙特卡洛决策树算法

　　关于蒙特卡罗树搜索，国内真的很难找到特别好的入门资料，很多还是错的。这篇文章是前段时间为了实现自己的一个AI而写的，看了几十篇国内外的文章，根据自己的理解。主要指的是一篇英文博文《蒙特卡罗树搜索——初学者指南INT8的机器学习》。不过，虽然我已经尽力让它普及了，但是蒙特卡罗搜索树比博弈树要难两级，没有太多算法基础的我也不用去了解每一个细节。

　　介绍

　　长期以来，学术界普遍认为，机器在围棋领域战胜人类是完全不现实的，并将其视为人工智能的“圣杯”。虽然深蓝在二十年前就打败了lhzdjc，但是人工智能在围棋上的表现还是很弱。

　　2016年3月，谷歌Deepmind开发的ALphaGo程序4-1击败李世石，一年后AlphaGo Zero以100-0击败其前身——。人类世界毫无疑问没有对手，wmdzm也远没有。

　　alpha/zero系统将几种方法结合成一个伟大的项目：蒙特卡罗树搜索。

　　残差卷积神经网络-游戏评估和移动先验概率估计的策略和价值网络

　　自博弈训练网络的强化学习

　　在本文中，我们将重点介绍卡特门罗树搜索算法。

　　说到关注，我想到下半年…中美合拍…两种风格百花齐放…多关注…

　　在此之前，象棋AI基本上使用的是博弈树算法——，但在围棋中使用时，效果很差，原因有二：象棋的评价能力更高。

　　棋牌游戏的评价一般是用估值函数来评价的。棋局态势特征明显。最容易想到的是，每个棋子和位置可以设置不同的分数。如果棋子和其他特征之间的保护关系，对情况的评价就已经很可靠了。但以上方法对围棋基本没有影响。

　　更高的计算能力要求。

　　首先，国际象棋的棋盘大小是64，围棋的棋盘大小是361。由于棋盘大小不同，象棋和围棋每一步的计算要求都不一样，围棋显然要求更高。这在博弈论中一般称为分支因子，即每次走法后的平均合法走法。国际象棋的分支因子约为35，而围棋的分支因子约为250。另一个可以解释计算能力不同要求的指标是搜索空间。这两个指标之间也存在指数差异。国际象棋是10 ^ 50，而围棋是10 ^ 171。我们知道宇宙的原子总数只有10 ^ 80左右，所以围棋的搜索空间绝对是天文数字，不是几千万可以描述的。

　　但是说到几千万，我就想到axdhxc的头发…下半年…

　　方法蒙特卡罗

　　先说蒙特卡罗方法，注意！这和蒙特卡罗树搜索算法不一样。很多科普文章混淆了这两个概念，声称AlphaGO使用了蒙特卡罗方法。

　　蒙特卡洛方法是什么？这是一种判断棋盘形势的方法。我们上面说过，围棋很难写出好的估值函数，于是在上个世纪有人提出了一个神奇的方法：双方在某一种情况下“随机”行走，注意“随机”行走到最后或者残局，多次计算胜率(比如一万盘)。胜率越高，情况越好。

　　我是在高三的时候在《围棋世界》里看到这个方法的。有一篇文章是关于alphago使用的这种方法的。我当时就发了大财，因为这个方法太奇妙了。我不用写极其复杂的估值函数，就随机玩了很多游戏。太棒了！然后我们将应用我们在上一篇文章中讨论的博弈树的最大最小算法。完美！

　　但实际上，这是一个伪算法。我们举个极端的例子。比如我下了某一盘棋后，对手对33，354，99有100个回应会导致劣势。但是，这盘棋，如果有一个赢家，我是绝对下不了的。

　　但是“蒙特卡罗树搜索”是一个真正的算法，它其实早在alphago之前就存在了，而且在当时是一个很大的突破，比业余段位棋手都强。

　　基本概念

　　蒙特卡洛搜索(MCTS)由Rmi Coulom于2006年在其围棋人机对战引擎“疯狂的石头”中首次发明并使用，取得了不错的效果。

　　先说它使用的原始MCTS算法(ALphago有一些改进)

　　树搜索，首先必须是搜索树。

　　让我们回忆一下下棋时的思维。——并没有把我们脑子里所有的可能性都列出来，而是根据“棋感”在脑子里大致筛选出几个“最有可能”的棋步，然后思考这些棋步之后对手“最有可能”的棋步，再思考我们接下来“最有可能”的棋步。实际上，这是MCTS算法的设计思想。

　　上面这一段很重要，可以反复品味。

　　它经历了以下三个过程(重复千千一万次)的选择。

　　膨胀(扩张)

　　模拟(仿真)

　　反向传播

　　这四个概念有点难，就不按顺序解释了。

　　模拟(仿真)

　　先说模拟，无序。模拟借鉴了我们上面提到的蒙特卡罗方法。我们可以走得很快，只有一盘，输赢。

　　我们的每个节点(每个节点代表每个不同的情况)都有两个值，分别代表这个节点及其子节点的模拟次数和获胜次数。比如我们模拟10次，赢了4盘，记为4/10。

　　让我们再看一遍这张照片。如图所示，每个节点都将标记有这两个值。

　　选择(选择)

　　我们将节点分为三类：未访问：当前情况未评估。

　　未完全展开：至少评估过一次，但是子节点(下一种情况)没有全部访问过，所以可以进一步展开。

　　完全扩展：已经访问了所有子节点。

　　我们找到一个我们认为目前“最有可能去”的未评估的情况(双方都聪明的时候)，选择它。

　　最有可能去哪个节点？最直观的想法就是直接看节点的胜率(胜率/访问量)，哪个节点选哪个最大，但是这个不行！因为如果在某个节点模拟开始的时候，虽然这个节点不怎么样，但是在随机游走开始的时候，你赢了一盘，你会一直在这个节点游走。

　　所以人们创造了一个函数。

　　Q(v)是这个节点获胜的次数，N(v)是这个节点模拟的次数，c是常数。

　　所以每次选择的过程是这样的：3354从根节点开始，遵循最大最小原则，我们每次选择UCT值最好的节点，向下搜索，直到找到一个。

　　“不完全节点”，根据我们上面的定义，不完全节点一定有未探索的子节点，所以只需选择一个进行扩展即可。

　　虽然我们不能做出这个公式，但我们可以欣赏它的别出心裁。第一，加号前面部分是我们刚才说的胜率，然后加号后面部分的作用是这样的：

　　随着访问次数的增加，加号后面的值越来越小，所以我们的选择会更倾向于选择那些还没有统计过的节点，避开我们刚刚提到的蒙特卡罗树搜索会遇到的陷阱3354。起初，我们误入歧途。

　　膨胀(扩张)

　　在刚刚选择的节点上添加一个统计信息为“0/0”的节点，然后进行下一次模拟。

　　反向传播

　　反向传播将大量数据转化为反向传播，但我认为它实际上非常类似于递归中的回溯，即从子节点开始，沿着刚好向下的路径往回走，一路上更新每个父节点的统计信息。

　　再放一遍这个图，可以观察到模拟之后，新的0/0节点，比如这里模拟输了，变成了0/1，然后根节点上的节点统计信息的访问次数都增加了1，赢的次数不变。

　　实现伪代码(python)

　　def monte_ygdlc_tree_search(根):

　　while resources_left(时间，计算能力):

　　leaf=遍历(根)# leaf=未访问的节点

　　simulation_result=卷展栏(叶)

　　反向传播(叶，模拟结果)

　　返回best_child(根)

　　定义遍历(节点):

　　完全展开时(节点):

　　node=best_uct(节点)

　　如果没有子节点/节点是终端，则返回pick_univisted(node.children)或node #

　　定义卷展栏(节点):

　　while非_终端(节点):

　　node=rollout_policy(节点)

　　返回结果(节点)

　　定义卷展栏_策略(节点):

　　返回pick_random(node.children)

　　定义反向传播(节点，结果):

　　如果是_根(节点)返回

　　node.stats=update_stats(node，result)

　　反向传播(node.parent)

　　定义最佳子节点(节点):

　　选择访问次数最多的孩子

　　什么时候可以终止算法？

　　这取决于你想让他什么时候停下来。比如可以设置一个时间，比如五秒后停止计数。

　　一般来说，最好的方式是访问量最高的节点，这可能有点违反直觉。之所以这样评价，是因为蒙特卡罗树搜索算法的核心是越好的节点越有可能去。另一方面，节点越多越好。

　　实际上，蒙特卡罗树搜索算法已经完成。我相信大多数人对算法正确性的证明并不感兴趣。基于上面说的纯蒙特卡罗树搜索，居然能打得过一百个我！所以今天就到此为止吧.等等，我们还没谈过一件事。——阿尔法狗改进了什么，使它成为世界上最好的狗？

　　他们对狗做了什么？

　　Deepmind将MCTS与近年来取得突破性进展的神经网络相结合，主要对上述两步进行了改进：

　　1.模拟：

　　首先，以上四个步骤中，最玄学最不靠谱的一步是“模拟”，通过随机快速行走的方式完成一局棋，然后记录下赢的局和下的局数。虽然这一步是蒙特卡罗树搜索的核心，但并不是那么准确。

　　在alphago Lee中，叶节点的评价是两部分的加权和：一个具有人工特征的浅层softmax神经网络，和一个具有自定义快速下棋策略的标准下棋评价。

　　估值网络：基于13层卷积神经网络的位置评估，从Alpha Go自对局的3000万个不同位置训练而来(没有两个点来自同一局)

　　Alphago zero更进了一步。他们根本不用模拟，而是用一个19层的CNN残差神经网络直接评估当前节点。(神经网络可以输出位置评估，得到每个位置的概率向量)

　　也就是说，每个位置的概率都可以不用模拟，直接用神经网络计算出来，可以说是直接消除了形而上的问题。

　　2.选择：

　　由于已经通过“模拟”评估的获胜次数和次数不再是真实的，所以我们之前通过UCT值向下搜索并选择未访问的叶节点的方法也需要相应地修改。

　　该功能变为：

　　UCT(v_i，V)表示从状态(节点)v_i到V的转移的值评估，P(v_i，V)表示从状态v_i到V的转移的概率，或者一个术语叫做“运动的先验概率”。这个概率由策略网络训练，并基于人类游戏数据集的监督学习。

　　有趣的是，在Deepmind的蒙特卡罗树搜索变体中，监督学习策略网络在实践中的表现更好，因此其结果用于估计行动的先验概率)。那么强化学习策略网络的目的就是产生3000万个位置数据集，用于训练评估网络(评估网络就是我们上一步提到的代替“模拟”的网络)。

　　Alphago Zero只有一个网络，既是估值网络，也是策略网络。完全是从随机的初始状态通过自我游戏训练。并行训练多个网络，在每个检查点，基于当前最优神经网络，选择最优网络生成训练数据。

　　原来如此。

　　然后今年，这项技术在微信官方账号开花了.风格和样式.多注意一下。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。