最强围棋程序Alpha Go 浅析

去年谷歌的围棋程序Alpha Go一举打败所有已知的围棋AI程序，以及以5:0的大比分打败了专业棋手Fan Hui。随后在《nature》上报到了Alpha Go 的内幕。作为一个伪的围棋爱好者和一个机器学习爱好者，看了该文章，并看了其他的分析，写下自己的心得：

围棋的智能对弈程序最早当属我国的手谈，那个时期的自动对弈程序属于经验型的。随后从国外对围棋研究后，产生了蒙特卡洛树搜索的方法应运于围棋对弈，产生了一系列的强AI，可以达到业余水准，关于蒙特卡洛树搜索可以参看《基于蒙特卡洛树搜索的计算机围棋博弈研究》，可以说对该方法进行了详细的说明，阅读也较容易，可以得到围棋AI的一些背景，制约蒙特卡洛方法更近一步的原因是：树的展开，以及搜索的深度的确定。于此同时，神经网络，特别是深度神经网络的发展使机器学习的state-of-art 不断的刷新。于是就有[将Deep nueral network 应运于Go AI的研究上][3],主要采取预测专业选手的动作来下棋，预测的准确率在44%左右，可是取得的效果不错，可是任然距离高手遥远。这里用机器学习的方法来对弈的AI，主要存在着：特征原则的问题，学习目标的设定。这两个是机器学习里最基本也是较难规定的，和认识问题的本质有关。

Alpha Go的创新之处就像他的题目一样在于将深度神经网络和蒙特卡洛搜索树的方法结合起来，构造了一种可能的通用学习方法。该方法分为两个部分深度神经部分和蒙特卡洛搜索树部分。神经网络的的部分主要负责预测p(a|s)，以及估计v(s)，蒙特卡洛搜索树上的节点就是神经网络发挥作用的地方，然后通过蒙特卡洛搜索树来综合某个状态下的各种走法的选择。
1. 神经网络部分
神经网络部分的难点在于特征的选取，以及目标的设定。论文里的特征选取直接选取要预测的盘面状态作为特征，将盘面状态作为19*19的图像，论文里没有说图像的值的设定（据我猜测根据盘面上每个点的像素值取(1，128，255)表示黑，空，白，三种状态，也可以是(1,0,-1)）。目标的设定选取了两种：预测下着在盘面空位落子的概率p(a|s)；以及下完某着后的赢面v(s)。

p(a|s)可以看作落子选择器，它其中可以根据目标的不同可以分为：监督型的落子选择器，以及增强学习型的选择器。监督型是将KGS服务器上一些高级选手的对弈作为样本，其中选择某一棋盘状态s作为样本图像，s状态下的下一步棋的位置为目标，学习时可以置1(这里状态s为赢方将要下的下一手，置1时我猜测的，因为学习后是概率，这在样本里是确定的，同时，学习后的p(a|s)也是一个19*19的概率矩阵，所以，其他未知的值置0，-1)。这样就构成了一个典型的监督学习，看论文中学习的机器使用的是深度卷积网络，使用了多达13个隐含层，这里对于边框的处理很有技巧性。通过这样的学习，可以学习到一个p(a|s)，这样学习的效果确实惊人的好，能够达到57%的精度（虽然精度相比此前最好的44%提高了一点，但是效果惊人的好！）。同时，用较少的隐含层学习一个速度较快的p(a|s)。

接下来将训练好的监督学习器的参数，作为增强学习器的初始参数。增强学习的过程是使用监督学习产生的一系列p(a|s)，作为初始的对手，进行对弈，记录对弈过程，如果获胜，则选择某一状态及下一手动作作为样本进行参数调整，这样通过机器自己的对弈，让p(a|s)不断的优化，得到一个新的p(a|s)，最终这个新的落子策略能在85%的对弈中击败监督学习得到的落子策略。

v(s)是表征当前局面胜率的一个估计。实际中对于围棋中某一盘面下，胜率的估计几乎做不到，因为围棋的广度和深度都很大。所以，同样用深度神经网络进行估计。输入任然是盘面状态，与落子策略不同的是，它的目标函数是，在当前盘面下，结果是否是获胜，获胜取1，失败取-1，成为只有两个值分类问题。其结构与落子策略的结构相同，只不过最后只输出一个预测值。这里为了防止过学习，对于每盘的对弈只选择其中的一个状态和值。这样训练得到的v(s)与MCTS(蒙特卡洛树搜索)的进度相同，但少了大量的计算！
2. 蒙特卡洛搜索树部分

蒙特卡洛方法是一种概率估计方法，最经典的例子就是估计圆的面积，其实是一种用频率来推测概率的方法。论文中将前面训练得到深度神经网络与MCTS结合起来。MCTS的特点是随着样本数量的增多，其对真实情况的估计越准确，但不合理的样本分布，会让它失真。

在围棋中，每一种状态就是一个节点，按照落子范围，可以表示为某状态下伸展出的子节点的个数，落子的顺序显示着落子的深度。前面说过MCTS在围棋上应用的困难在于，围棋的广度和深度过大，使得MCTS的剪枝不合理以及搜索时间大。而前面的深度神经网络的学习刚好可以做出很好的估计。根据p(a|s)可以大量压缩当前状态s下，可能的落子位置，根据v(s)可以在不用对树的深度访问下，直接估计状态s下的盘面情形。实际上论文中为了更好的发挥MCTS和深度神经网络的优势。采取了一种更好的方法：
对盘面的估计方法，一方面直接使用v(s)进行估计，另一方面在状态s下进行机器间的对弈，对弈的AI采用之前在训练落子策略集中随机的一个，直接到对弈结束后的结果。对这两者进行综合得到V(sL)
V(sL)=(1-R)v(sL)+Rz z=（1获胜 ，-1失败），论文中说在实验中R=0.5最合适。 sL是在对弈过程中L步下的状态s。 这里有个问题就是L的选择为多少合适。
（后补。。。）

[3]: Training Deep Convolutional Neural Networks to Play Go