解密AlphaGO是如何下围棋的
作者：别想多了

0. 前言 

当写这篇文时，李世石对AlphaGO比赛四局围棋已经输了三局，形势不好，机似乎超过人。AlphaGO到底是怎样做到的？我自己不是人工智能背景但对这方面时不时有兴趣，去读了在自然杂志上发表的AlphaGO论文，仍有不少地方有疑问。有时遇到不明白的最好的办法就是设法说出来看能不能解释清楚，虽然可能说错，但说着说着细节就变得清晰了。写这篇文就是想说说AlphaGO到底是怎样做到的，从解释中我自己也可学到明白种种细节。有错请指教。

1. 总览 

AlphaGO主要混合采用了两个技巧： 卷积神经网络(convolutional neural network)和蒙地卡罗搜索(monte carlo
tree search)，神经网络又分为三个网络： 1.方针预测神经网络(policy
network)，2.快速推展神经网络(fast
rollout network)，3.估值神经网络(value
network)。它大量使用人下过的棋局用作监督学习(supervised
learning)训练神经网络去预测下一步怎样走，用增强学习(reinforcement
learning)自我训练提高准确度。下棋时它用方针预测网络评估当前的棋板棋子位置，列出比较好的候选回应步和概率，然后输入蒙地卡罗搜索，搜索时结合方针预测网络，快速推展网络和估值网络一步步在人机之间下子演译，最后选择演译出最好的致胜步法。卷积神经网络和蒙地卡罗搜索的混合使用取得惊人的成果，足已能击败职业棋手。

2. 蛮力搜索 

首先说说一般电脑是怎样用蛮力搜索来下棋的。当人下一步棋例如在c4位置时，电脑开始在棋板上用蛮力搜索下一步，每个位置下一下，例如在c5，然后计算人从每个位置的回应，一直下下去，最后选择有高获胜机会的一系列步序，用那个起始位置c5去回应人的c4。蛮力搜索要搜的步数非常非常多，19x19棋板有361个位置，每一步后有360个位置，下一步有359个，基本上是361!阶乘，考虑一局大概有150步那就大约有10^367个可能，用世界上所有的电脑来计算直到宇宙终结也搜不完。

神经网络和蒙地卡罗搜索都是用来缩短搜索篇幅的，首先说说蒙地卡罗搜索，这个比较容易解释。 

3. 蒙地卡罗搜索

简单来说蒙地卡罗其实就是掷骰子，蒙地卡罗是赌场嘛，蒙地卡罗搜索在走每一子前用掷骰子模拟人和电脑来回依次下，下的每步都是随机掷骰子决定下的位置，直到一方赢。一个模拟输赢叫一个rollout
(fast rollout神经网络跟这有关系)，随机模拟可以运行1千次1万次，抽样输赢规律就出来了，知道大约这一子的输赢机会。例如人下一子在c4，电脑要决定走c3或c5，它会从c3开始随机模拟1百次玩下去，再从c5开始随机模拟1百次玩下去，如果c3在1百次赢了30次，c5在1百次赢了10次，那c3有更好的获胜机会。 

蒙地卡罗搜索大大缩短搜索篇幅，361个位置不用搜索每一个，随机选几十个随机模拟就成了。但随机选择概率太差了，随机选择大多数都是垃圾浪费搜索时间。蒙地卡罗搜索用一系列正规的选择，扩展，模拟，结算阶段来建造一层层候选步棋树层并记录模拟的统计结果。AlphaGO没有用正规函数来选择和模拟，它是结合了神经网络用在选择和模拟阶段。

蒙地卡罗搜索的好处是不需要知道游戏的特定战略或战术知识，只要知道游戏的输赢就成了，不需要知道围棋的技巧和知识，不需要知道开局，中局，终盘，眼，劫杀，等等。另外好处是树层会集中在有好结果的方向增长，还可以作并行处理同时使用多个电脑，还有的好处是可以随时停，时间到了就停，到时有什么最好的就用什么。坏处是它的搜索篇幅仍然相当大，复杂些游戏它就没时间搜到好结果，会出弱招。还有蒙地卡罗不能累积知识累积经验，不知道利用人类积累的知识经验或以前玩过的。这就需要神经网络来解决。


4. 神经网络

神经网络的好处是它的可训练性，用大量已知的知识可以训练一个神经网络去辨认这些知识，注意，是辨认这些相同种类的知识。例如输入大量猫照片，神经网络就可辨认相似的猫照片。


AlphaGO应用神经网络有几个方面，例如方针预测，目的很简单，当遇到一个棋板和它现有棋子位置时，预测对手下一步的回应。这里连上一步在哪位置都不需要知道，只要知道棋板和它现有棋子位置就成了。这个很重要，AlphaGO就是这样开始评估每一步的。这样训练神经网络的问题也变得简单了，只需要找人下过的棋局，把每一步的棋板棋子位置输入网络，再对应对手的回应棋子就成了，每一步的延续性不重要，可以分开单独处理。AlphaGO从人公开赛找来了160，000局3千万步的棋板棋子位置和回应棋子位置来训练第一代神经网络，类似棋板位置和类似回应通过神经网络归纳成下子经验。真正下棋时，当遇到类似棋板位置时，神经网络知道应该如何回应，网络出的结果是下下一步的概率，高概率的回应步就是好的下一步。出来的结果可能有几个或几十个好位置，这些成为下一阶段计算的方向方针。

5. AlphaGO的神经网络 

AlphaGO训练棋板的输入是19x19的棋板图像，外加x48额外信息，每一个位置要输入棋黑白颜色，局走了多少步，周围多少空位，等等48特征，合计19x19x48个信息。AlphaGO的神经网络是深层神经网络，用了13层。13层里每两层有一层是卷积过滤器(convolution
filters)将棋子过滤出主要特征(feature)，这些是棋子的形状形态特征，另一层是整流器(rectifier
nonlinearity)用作激活函数。第一层卷积过滤是5x5迈1步，这是说5x5棋位的形态会被扫描提取，迈1步，下一个5x5棋位的形态被扫描提取。之后所有的积过滤层是4x4迈1步。最后一层用softmax函数计算出分类概率。

6. 卷积过滤神经网络 

卷积过滤可能大家已经用过，处理照片时使照片更清晰，更模糊，或周边突出，这些都是卷积过滤作用。使周边突出的作用非常有用，在围棋里要识别一大块接连的棋子，只要识别这块的周边就可以了。卷积过滤神经网络利用卷积过滤去提取照片信息中的特征，第一层的结果再用卷积过滤去提取，一层一层的去提取，最后可以获得照片的抽象特征。棋子的各种形状外形经过过滤成为识别特征，当下棋时棋板棋子位置被输入经过同样的卷积过滤处理，将它出来的特征比较存有的特征，就知道如何应对了。

7. 第一代的神经网络 

第一代的神经网络是用监督学习(supervised learning)的。训练用的公开赛有赢输，训练时赢的一方每步的回应有更多的重视。听闻训练第一代要三个多星期的时间，完成后第一代预测对手下一步的回应准确程度达到55.7%。这时AlphaGO已经可以用神经网络来下棋了，基本上在下每一步时，将当前的棋板棋子位置输入神经网络，计算出来的下棋位置就是回应子。

8. 第N代的神经网络 

有了第一代后AlphaGO应用增强学习(reinforcement learning)继续提炼准确度。这就是自己跟自己随机下，有改善的网络进化成为第二代，将神经网络的神经重量加强，听闻训练了好几十亿代。奖励函数是赢了+1，输了-1，不够时间完成的是0。神经重量加强用随机陡度爬升(stochastic
gradient ascent)。最后强化的神经网络能够赢第一代80%的时间。这就是方针预测神经网络。单独使用方针网络预测下一步来下棋已经可以击败了当时外面最强的围棋软件。

过度拟合是源材料里较小的错误或噪声垃圾被扩大成为训练后的模型。为了避免过度拟合，AlphaGO不跟同代下棋避免扩大已有噪声，反而会随机跟自己前代下棋。

9. 快速推展神经网络 

快速推展神经网络是简单的方针网络，快1000倍，但预测准确度低。快速推展网络是用在蒙地卡罗搜索模拟阶段中人与机的随机模拟赛。

10. 估值神经网络 

估值神经网络类似方针网络，不同的是估值网络对一个棋板棋子位置评估只会给赢或输的答案，不会像方针网络预测众多下一步的概率。估值网络跟快速推展网络一样是用在蒙地卡罗搜索模拟阶段中人与机的随机模拟赛。估值网络和快速推展网络会分别独立运算人与机的随机模拟赛，然后结合两者独立获得的结果，这防止其中一个犯错了也不会错得太过离谱。 

训练估值网络时为了避免过度拟合，AlphaGO会随机制造众多(3千万)棋板棋子位置，这些都是从真正的棋局来，随机改了一些位置。


11. 下棋

真正下棋时，AlphaGO会将当前的棋板棋子位置输入方针预测网络作评估，列出比较好的候选回应步和概率，然后输入蒙地卡罗搜索，搜索的选择阶段会将预测的概率作为搜索节点的初始概率，用蒙地卡罗算法进行选择，扩展树层。模拟阶段会用估值网络和快速推展网络分别独立运算一步步在人机之间下子演译，两者独立获得的结果会50/50结合。例如估值网络说这一子胜(1)，快速推展网络也说胜(1)，那么结果是(1+1)/2=1。如一说胜(1)一说败(0)，那么结果是(1+0)/2=0.5。当扩展蒙地卡罗树层时会加全部合法的棋步，新加的棋步会用方针预测网络作评估，预测的概率作为新加棋步节点的初始概率。并会继续重复模拟直到发现获胜的步法或用完时间。

 
评分完成：已经给 别想多了 加上 50 银元！