AlphaGo核心算法之一——蒙特卡洛树搜索
近来全球都在关注的一大热点就是谷歌的人工智能围棋程序AlphaGo对阵围棋职业九段李世石的人机大战了，在3月9号的第一场比赛里AlphaGo就取得胜利，可以说轰动了全世界。（这篇文章还没写完，第二盘AlphaGo又赢了。）虽然人工智能对于我这样的初初初级程序员来说有点遥不可及，但是对这样重大的技术突破保持好奇心和求知欲应该也是程序员要具备的素质吧……本着这样的想法，我在网上搜了些资料，了解了一下AlphaGo使用的核心算法之一——蒙特卡洛树搜索。水平所限，只能写一点自己的理解，肯定有很多不对的地方。
蒙特卡洛算法
首先从蒙特卡洛算法说起，这个算法其实不是什么新技术，是上世纪40年代美国在第二次世界大战中研制原子弹的“曼哈顿计划”计划的成员S.M.乌拉姆和J.冯·诺伊曼（计算机之父！）首先提出的。主要思想是通过大量随机样本的概率分布来得到所要计算的值。用它最经典的应用来举例——计算圆周率：
正方形内切圆，圆与正方形面积比是π/4：
在正方形内部随机产生10000个点，通过点的坐标(x,y)计算点与圆心的距离，从而判断该点是不是在圆的内部。
如果这些点均匀分布，那么圆内的点应该占到所有点的 π/4，因此将这个比值乘以4，就是π的值。
对这个例子进行推广，我们可以计算任意一个积分的值，例如计算函数y = x²在 [0, 1] 区间的积分，就是求出下图红色部分的面积。
这个函数在 (1,1) 点的取值为1，所以整个红色区域在一个面积为1的正方形里面。在该正方形内部，产生大量随机点，可以计算出有多少点落在红色区域（判断条件 y < x2）。这个比重就是所要求的积分值。
蒙特卡洛树搜索
蒙特卡洛树搜索（Monte-Carlo Tree Search，MCTS）是用于人工智能选择最优解的算法，典型应用是在博弈游戏中。基本思想也很简单，以围棋为例：
建立一个搜索树，节点是当前的局面，节点的子节点是下一步棋后形成的局面，根节点就是一无所有的空棋盘。首先在根节点中随机选择一个子节点，相当于在棋盘中随机下了一步棋，然后子节点继续随机选择子节点，直到叶子节点也就是分出胜负的状态。如果胜了，那把刚才路径上的所有节点权重都加1，这样下次随机时有更大的可能会随机到这些点。
上面的过程重复无数次，越是有可能胜利的下法，权重就会越来越高，最后选择胜率最大的那个方案落子。这个时候，这一步棋才真正下到棋盘上。
当然，如果完全按照这个原始的算法，要搜索的数量级实在太大了。围棋有19x19=361个点，那么搜索树的节点至少也是361!个，数量级大概是10的170次方，已经超过了宇宙中所有原子的数量。因此AlphaGo还采用了更加复杂的方法对搜索树进行剪枝。具体的内容无法在这里展开了，毕竟我只是关注算法……
最后附上链接，其中左右互搏，青出于蓝而胜于蓝？—阿尔法狗原理解析这篇文章比较清晰易懂，可以一看，感觉How AlphaGo Works这篇写的还不如前者好懂。
参考链接：
How AlphaGo Works 英文，里面有中文翻译的链接。
AlphaGo项目主页 其中有nature上发表的那篇论文的链接。