Google DeepMind AlphaGO分析

AlphaGO是第一个击败人类职业围棋选手、第一个战胜围棋世界冠军的人工智能程序，由谷歌（Google）旗下DeepMind公司戴密斯·哈萨比斯领衔的团队开发。其主要工作原理是深度学习。以下是对其实现过程及算法的简析。

围棋棋盘是19x19路，所以一共是361个交叉点，每个交叉点有三种状态，可以用1表示黑子，-1表示白字，0表示无子，考虑到每个位置还可能有落子的时间、这个位置的气等其他信息，可以用一个361 * n维的向量来表示一个棋盘的状态。将一个棋盘状态向量记为s。

当状态s时，在不考虑某位置无法落子的情况下，可供下一步落子的空间也是361个，因此将下一步的落子的行动也用361维的向量来表示，记为a。

至此，可将设计围棋人工智能的程序转换成为在任意给定一个s状态下，寻找最好的应对策略a，使程序按照该策略可获得棋盘上最大的地盘的程序。

一、深度卷积神经网络

深度卷积神经网络早在98年就攻克了手写数字识别，近年在人脸识别、图像分类、天气预报等领域亦有显著突破，接连达到或超过人类的水平。2015年，AlphaGO主要设计师黄士杰在ICLR的论文发表利用“深度神经网络”从围棋对战平台KGS获取人类选手的围棋对弈的棋局进行学习，实现人机交战的论文。

在这些棋局中，每一个状态s，都会有一个人类做出的落子a（训练样本）。将s看做一个19x19的二维图像（实际为19x19 x n，其中n表示其他feature），输入一个卷积神经网络进行分类，分类的目标是落子向量a’，不断训练网络，尽可能让计算机得到的a’接近人类高手的落子结果a，既可得到了一个初步模拟人类棋手下围棋的神经网络。

设置一可以模拟人类棋手的策略函数P_human，对于给定的某个棋局状态s，计算出人类选手可能在棋盘上落子的概率分布a = P_human(s)，如下图：

红圈既P_human认定的最好的落子方案。每一步都选择概率最高的落子，对方对子后再重新计算一遍，如此往复就可以得到一个棋风类似人类的围棋程序。经检测，P_human方案达到的围棋水平在人类选手业余6段左右，但未能超过彼时最强的电脑程序CrazyStone[1,5]（利用MCTS实现）。

二、蒙特卡洛搜索树（MCTS）

蒙特卡洛搜索树（Monte-Carlo Tree Search）由黄士杰的老师Remi Coulum于2006年提出，是围棋AI史上的重大突破。

面对一个空白棋盘S0，假设所有落子方法分值都相等，设为1。从361种落子方法中随机选择一个走法a0，落子之后，棋盘状态变成S1。假设对手进行相同操作，随机落子，棋盘状态变成S2。至Sn时，分出胜负r，赢r记为1，输则为0。

假设这第一次r=1。将上一次的落子方法（S0,a0）记录下来，分值进行以下修改：

新分数=初始分+ r

此时r=1，新分数=2。将随机出的局面所对应落子方法(Si,ai)的分数设为2。既除（S0, a0）的分值是2外，其他落子方法的分数仍为1。再次选择a0的概率比其他方法略高。

设置对手也用同样的方法更新其新分数，假设选择一个a1作为应对，继续第一次的操作。假设此次结果仍为赢，继续调整模拟路径上相应的分数，将其均+1。随着模拟棋局数量增加，优秀的落子方案分数会越来越高，而这些落子方案越是有前途，就会被更多的选中进行推演，既可得到最优秀的落子方案。

蒙特卡洛搜索树存在的两个优点：

1）没有任何人工的feature，完全依靠规则本身，通过不断想象自对弈来提高能力。

2）MCTS可以连续运行，在对手思考对策的同时自己也可以思考对策。在下完第一步后，不必要停下，可以继续进行模拟对弈，直到对手落子，随后从对手落子之后的状态开始计算。因为对手的落子可能出现在之前的模拟对弈中，所以之前的模拟对弈可以保留。

蒙特卡洛搜索树存在的缺点：

初始策略太简单，需要更高效地随机落子。

三、深度卷积神经网络与蒙特卡洛搜索树结合

改进MCTS，先根据P_human的计算结果得到a可能的概率分布，以此概率挑选下一步的动作。新分数按照如下方式更新：

新分数=调整后的初始分+ 通过模拟得到的赢棋概率

如某一步被随机到很多次，就应该主要依据模拟得到的概率而非P_human，因此调整P_human的初始分算法：

调整后的初始分= P_human/（被随机到的次数+ 1）

调整后可用P_human快速定位较好的落子方案，并给其他位置一定的概率。

当前问题为P_human()计算过慢。一次P_human()计算需要3ms，相对于随机落子的不到1us，速度慢了3000倍。如果不能快速模拟对局，棋力就不能提高。

训练简化版的P_human_fast()，把神经网络层数、输入特征都减少，耗时下降到了2us，基本满足了要求。先以P_human()开局，落子越20步后，使用P_human_fast()快速走到最后，兼顾了准确度和效率。

围棋软件所使用的神经网络和蒙特卡洛方法都可以随着训练集的增长和计算力的加强而同步增强，可以实现棋力的稳步提升。

四、左右互搏，自我进化

同年2月，由Deepmind团队在顶级学术期刊nature上发表的《用神经网络打游戏》一文中提出，为进一步提高MCTS的棋力指明了前进的新方向。

Deepmind团队通过“强化学习”方法训练的程序在类似红白机的游戏机上打通了200多个游戏，大多数得分超过人类玩家。

“强化学习”是一类机器学习方法，Agent通过和环境s的交互，选择下一步的动作a，这个动作会影响环境s，给Agent一个reward，Agent然后继续和环境交互。游戏结束的时候，Agent得到一个最后总分r。将环境状态s、动作a匹配起来得到一系列，设定目标为最后的总得分r，可以训练一个神经网络拟合在状态s下，做动作a的总得分。下一次进行游戏时，就可以根据当前状态s，去选择最后总得分最大的动作a。通过不断进行游戏，对下总得分的估计会越来越准确，游戏得分会越来越好。

以打砖块游戏为例，强化学习的程序在600盘以后，学到球在快要把墙打穿的时候评价函数v的分值会急剧上升，既球打到墙的后面去，球会自动反弹得分。

在围棋中引入一个评价函数v(s)，在P_human()模拟开局20步后，不需要搜索到底，通过v(s)就可以直接判断是否能赢，得到最后的结果r，进而提高MCTS的学习速度。

首先利用P_human和P_human对弈获取大量棋谱（如进行一万局，就得到了一万个新棋谱。）。将棋谱加入到训练集中，训练出P_human_1（此时训练方法较之前稍有不同，P_human尽可能的模仿人类棋手下棋，而不区分每一步棋的好坏。P_human和P_human对弈之后，记录下状态s、下一步落子位置a、以及最终胜负情况z，得到一个训练数据(s,a,z)。如果z=1, 表示我方赢棋，则尽可能模仿此时自我对弈中的下棋位置；反之则尽可能避免选择自我对弈中的下棋位置。）。然后再使P_human_1和P_human_1对局，得到大量的新棋谱，以训练出P_human_2。如此往复，可以得到P_human_n。P_human_n得到了最多的训练，棋力理应比原来更强，将该策略记作P_human_plus。这时，P_human_plus和P_human对局，在不用任何搜索的情况下胜率可达80%，不加任何搜索策略的P_human_plus和开源的MCTS相比也有85%的胜率。

将P_human_plus代入MCTS中，用P_human_plus开局，然后用P_human_fast继续接下来的操作。因P_human_plus走棋的路数太集中，而MCTS需要发散出更多的选择，导致结果棋力反而不如用P_human。

进一步改进，开局仍先用P_human走L步，以有利于生成更多局面。为了进一步扩大搜索空间，在L+1步的时候，随机落子，记下当前状态SL+1，然后用P_human_plus对弈，直到结束获得结果r。经不断训练，由于L也是随机数，可得开局、中盘、官子不同阶段的局面s及其对应的结果r。利用这些训练样本，使用神经网络将最后一层的目标改成回归而非分类，得到v( )函数。v()可给出下一步落子在棋盘上任意位置后，如双方均用P_human_plus来落子，我方赢棋的概率。

五、AlphaGO

在MCTS框架之上融合局面评估函数v()。用P_human作为初始分开局，每局选择分数最高的方案落子，下到第L步之后，改用P_human_fast将剩余棋局走完，同时调用v(SL)，评估局面的获胜概率。按照如下规则更新树的分数：

新分数=调整后的初始分+ 0.5 * 通过模拟得到的赢棋概率 + 0.5 * 局面评估分

前两项与原来相同，如待更新的节点即为叶子节点，则局面评估分即是v(SL)。如为待更新的节点是上级节点，局面评估分是该节点所有叶子节点v()的平均值。

假设v()表示大局观，“P_human_fast模拟对局”表示快速验算，则方法为大局观和快速模拟验算并重。至此，AlphaGO初步实现。