蒙特卡洛树搜索
个人觉得，整个 AplphaGo 对于机器学习来说，最核心的算法就是深度学习（Deep Learning）和增强学习（Reinforcement Learning）。蒙特卡洛树搜索 MCTS 是一个搜索框架，将这些机器学习的技术融合在了一起。今天这篇文章的重点在深度学习，增强学习以后再说。
蒙特卡洛树搜索
每个博弈类的人工智能算法的基础都是一个搜索算法。比如我们上学时学习的 A-star 算法，alpha-beta 剪枝，极大极小搜索(min-max search)。蒙特卡洛树搜索也是其中一个。所有搜索算法大概的步骤都如下：
基于当前的状态，给出N种自己可以做出的选择
对于每种选择，评估一下这种选择对自己的好处
选择对自己好处最大的选择
但是这里有一个难点，就是如何评估每种选择对自己的好处，也就是如何设计出评价函数。比如说，如果我们设计出一个评价函数，结果发现在N种选择中，有M个选择得分一样，而且都是最高分，那这个时候我们怎么办？这里本质的原因是，如果基于当前的状态只看一步，其实很多时候看不出好坏。所以就要多看几步。比如
基于当前的状态，给出N种自己可以做出的选择
对于每种自己可以做出的选择，做出对手可能做出的N种选择
这个时候，我们最多可以面临 N^2 种局面，对每种局面进行评估
反推出自己应该做出什么选择
举个例子，比如给定一个评价函数Q，在当前局面下，自己有A，B两个选择，且评分一样 Q(A) = Q(B)。
但是，如果我做出A选择，对手可以做出A1选择，在这种选择下我就死了，对手就赢了。那么我肯定不能选A。这个时候，如果发现我选择B，对手的选择中，没有一种选择能让我立即就死了，那么至少B还是比A好的。这其实就是极大极小搜索的基本原理。而 Alpha-beta 剪枝是对极大极小搜索的一种优化。
当然，在上面的例子里我们只向前看了2步。但是也许看2步还是看不出局势的好坏。这个时候就要不断的扩展深度，直到能看出局势的好坏，然后再反推自己第一步怎么走。Alpha-beta 剪枝在国际象棋领域取得了很大的成功，深蓝就是基于这个算法的。但当人们把这个算法应用到围棋时就发现了一个问题：因为围棋每种状态下的选择远远大于象棋，造成在相同的算力下，围棋很难向前看太多步，但同时又很难设计出一个评价函数在搜索深度不大时，就能看清局势。
于是 MCTS 就诞生了。其实这个算法很早之前就诞生了，只是在围棋的领域里才找到了自己的出路。这个算法有如下的本质：
他对局势的评估，是基于自我对局进行模拟的。模拟的次数越多，估计的越准。这种评估基本能做到不需要太深的搜索，就能看清局势。
每次选择评估什么局势时，都是选择对当前胜率最大的节点进行评估
举个例子，比如棋局进行到X手时，轮到黑棋下，
黑棋找到10个自己可能下的位置，每个位置有两个数，一个是W，一个是T
找出10个位置中，黑棋下了胜率最大（胜率就是W/T， 当然出于探索的需要，一般会在这里使用多臂赌博机的模型，所以选择时并不完全考虑胜率，这个以后再细说)的位置，进行模拟对局。
对局结束后，T = T + 1, 如果黑棋胜了，W = W + 1，同时这个节点的祖先节点中，所有黑棋对应的节点的W都会加1。
假设经过一段时间后，黑棋可能下的10个位置都已经评估过了。这个时候就找出胜率最高的位置，开始考虑如果黑棋下在这个位置后，白棋怎么下。假设白棋也找10个可能下的位置。
当我们在评估白棋的位置好不好时，也要进行模拟对局。如果白棋胜了，那么这个节点的W ＝ W ＋ 1，同时这个节点的祖先节点中，所有的白色节点的W都加1。
上面这个过程其实是一种 min-max 搜索。为什么呢？我们考虑如果我们发现一个黑色节点，在之前的评估中胜率很高。但是，如果我们扩展了这个节点后，存在一个白色子节点的胜率很高（假设100%），那么我们在评估那个白色节点时，这个黑色节点的T会增加，但W不变，此时就会拉低黑色节点的胜率，直到这个节点降低到一定的程度。计算资源就不会再评估这个节点，而是去评估别的黑色节点了。
从上面的描述时，我们知道 MCTS 需要解决两个问题：
在每个状态下， 如果找出下一步的候选位置
如何评估每个状态的最终胜率。
在传统的 MCTS 里，是通过自己和自己下棋，一直下到最后确定胜负，然后下很多局可以计算出胜率。那么自己和自己下棋，也得有一个算法去给出下一步可能走在哪里。
AlphaGo 在这里有一个创新，就是不通过自我对局，而是直接通过神经网络基于当前局面，给出最后胜率的估计。
综合上面的讨论，下面这个问题显然是 AlphaGo 需要解决的第一个问题：
- 如果基于当前的局面，给出下一步的可能位置
这就是 AlphaGo 的 Policy Network 做的事情。在传统的围棋程序，比如 GnuGo 中，这一步大都是通过大量的规则去确定的。这里我们不考虑这种方法，只讨论如果通过机器学习，怎么实现。
预测下一步的传统机器学习实现
假设我们有一个数据集，包含了过去几十年人类高手对局的棋谱。那么我们就有了大量关于在某个盘面下，人类是怎么走下一步的例子。在19路棋盘上，总共有361个位置，如果我们对每个盘面能建立一个特征，那么就可以转化为一个361类的分类问题。这个时候最简单的就是可以用最大熵的分类器来解决这个问题。
更进一步，出于提高效率的考虑，我们也可以把这个361类的分类问题转化为一个两类分类问题。就是对于一个盘面S和一个合法的下一步p。判断y(S, p)是1， 还是0。是1表示人会下在p这个位置，是0表示人不会下。对于两类分类问题，我们的任务就是对于盘面S和位置p，抽取相关的特征。此时，我们的围棋知识就可以派上用场了：
如果我下在p，是不是就能吃掉对方几个子？
如果我下在p，是不是能救活我方的几个子？
如果我下在p，是不是能让对方的几个子处于危险之中？
如果我下在p，是不是能让我方几个子脱离危险？
如果我下在p，是不是能断开对方的大龙？
如果我下在p，是不是能让我方的大龙连回家？
如果我下在p，能否破对方的眼？
如果我下在p，是否能做我方的眼？
如果我下在p，是否征子有利？
如果我下在p，能否让一块棋活了？
……
基于围棋知识，我们可以设计出很多特征。
同时，在传统的机器学习中，也可以用模版法。直接抽去p这个位置的N邻域，hash出一个数做为特征。这个特征最终的权重代表在历史的对局中，当遇到这个局部时，人类会在p落子的可能性。
很不幸的是，当我们运用大量的围棋知识去设计各种特征，并加上各种邻域的模版特征之后，下一步预测的准确率只能达到30%~40%之间。这也是目前发表的paper中具有的水平。
预测下一步的 DCNN 实现
由于传统方法在这个问题上表现的很挫，因此 AlphaGo 用 DCNN（deep cnn）来解决这个问题。DCNN 之前在图片分类的问题中取得了很大的成功，给定一幅图，DCNN 可以知道这个图里是一棵树，还是一只猫，还是一艘船，还是一栋楼。由于围棋的棋盘其实可以看成一个19*19的图片，每个像素就是对应的位置的状态（是黑棋，还是白棋，还是没放棋）。因此我们可以把每个盘面表示成一个三通道的图片，对于位置p，
通道0 ＝ 1 表示p放的我方的子 （这里我方代表在这个盘面下，下一步走棋的子的颜色，对方反之）
通道1 ＝ 1 表示p放的对方的子
通道2 ＝ 1 表示p没放子
然后这个图片的类别就是下一步可能的位置，一共有361种可能性，因此就是一个361类的分类问题。然后用 DCNN 训练一下，结果发现预测下一步的准确率可以达到44%。这是很令人惊奇的，因为整个过程中我们没有利用到任何围棋知识，也没有提前任何特征。DCNN 就自动学习出44%的精度了。
当得到这个惊人的结果时，群众们觉得，还是加点围棋知识吧，于是有人把3通道扩展到了更多的通道，比如：
通道0 ＝ 1 表示p放的是我方的棋子
通道1 ＝ 1 表示p放的是对方的棋子
通道2 ＝ 1 表示没有放子
通道3 ＝ 1 表示p放的是我方的棋，且于p相连的棋串只有1口气
通道4 ＝ 1 表示p放的是我方的棋，且于p相连的棋串有2口气
通道5 ＝ 1 表示p放的是我方的棋，且于p相连的棋串有3口气
通道6 ＝ 1 表示p放的是我方的棋，且于p相连的棋串大于3口气
通道7 ＝ 1 表示p放的是对方的棋，且于p相连的棋串只有1口气
通道8 ＝ 1 表示p放的是对方的棋，且于p相连的棋串有2口气
通道9 ＝ 1 表示p放的是对方的棋，且于p相连的棋串有3口气
通道10 ＝ 1 表示p放的是对方的棋，且于p相连的棋串大于3口气
通道11 ＝ 1 表示p是上一步刚刚落的子
可以看到，这里只利用到了2个围棋知识，一个是棋串，一个是气。另外还利用到了上一步的信息。然后用 DCNN 训练一下，会发现下一步的预测准确率能达到53%左右了。在 AlphaGo 里，还利用到了更多的围棋知识，它们一共使用了48个通道（也就是每个点提取了48个特征），然后就可以达到57%的准确率了。
当我看到这个结果时，确实觉得 DCNN 的效果已经超出我之前的认识了，因此促使我开始全面的研究深度学习。
目前开源的围棋程序 Pachi (GitHub - pasky/pachi: A fairly strong Go/Baduk/Weiqi playing program) 已经支持了 DCNN 用来预测下一步，有兴趣的可以关注一下。按照我在网上的实测，配合不太多的模拟之后，棋力在业余2段到3段之间。关于这里用的网络的详细信息可以参考[Computer-go] CNN with 54% prediction on KGS 6d+ data