机器学习 alphaGo—monte carlo search tree（1）

alphaGo可能已经渐渐地淡出了人们的视野。但是他出现是有一定历史意义。alphaGo 两次登上自然杂志封面。第二次是因为 alpha zero 而登上自然杂志， 这次分享以 alphaGo 为基础进行分享，分别是两个话题一个是 神经网络，一个是今天将的蒙特卡罗搜索树方法。

图

我们回顾一下机器学习的历史，早在 1996 年，深蓝就曾经战胜过人类国际象棋冠军。在沉浸了将近 20 年后才再次在围棋上战胜人类。在过去的 20 年，究竟发生了什么，为什么 alphaGo 姗姗来迟呢？ 答案是我们在技术上遇到瓶颈，而这些年随着一些新技术和新概念出现的支持，才出现了alphaGo。

国际象棋和围棋比起来，

国际象棋的规则是由人类创造的，而围棋规则设计是如此的优雅，优雅经常被用来形容代码，这里也被用来形容围棋规则。这说明围棋规则严谨，他不仅属于人类。

我们通过一些数值来看一看国际象棋和围棋的复杂度对比国际象棋棋盘 8 * 8而围棋棋盘19*19 每一步考虑因数围棋是 250 而国际象棋是 35。 所以围棋根据状态的选择就像天上的星星是数不尽的。

在国际象棋中我们用到了minmax 规则，就是将决策树按层划分为分别属于自己和输入对手

决策树

由于国际象棋的复杂度远远不如围棋，所以通过决策树，就能计算所有的可能来做出正确的选择。

图

browne Cb 和 Edward powly 在 2012 提出了蒙特卡罗树搜索方法，为 AI 点亮一盏明灯。

蒙特卡罗

第一次接触蒙特卡罗这个概念，是在渲染效果图时使用到蒙特卡罗算法来进行渲染。蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。与它对应的是确定性算法。

在正式切入正题前，我想问大家一个问题就是什么是 pi 。我们在高中或是初中就已经学过如何计算pi 。今天我们通过随机模拟方式来演示一种全新的方式来算 pi 。我们画一个方形，方形中在画一个圆形，他们中心重合，并且圆的直径等于方形的变长。然后随机画点，点在园内外的数量比来获取 pi 的值。

图

蒙特卡洛搜索树分为四个阶段，如图 选择 展开 模拟 和 更新

展开

由于我们这里是根节点，没有选择的余地，所以选择根节点，然后进行展开。

图

在模拟阶段，然后我们以选中的节点，随机地进行展开其子节点，一层一层地展开树的直到结束的得出这次模拟的结果，可以是真假或者是赢或输。

更新阶段

然后我们把随机模拟得到值（w 我们用 w 表示赢）放回给这个节点值为 1/1 第一个 1 表示赢而第二个 1 表示进行 1 次模拟。

选择阶段

当所有子节点，也就是叶节点都遍历出之后，我们在这一个级别选择一个节点作为选择的节点，以此节点进行更深入的研究。这个三个节点值分别为 1/1 0/1 0/1。

图

通过对比 1/1 0/1 和 0/1 ，我们会选择第一个 1/1 这个节点，以此节点为基础，循环 expansion simulation update 这几个阶段

图

随着模拟次数增加我们的值也也就更接近真实值，待续