6
| 本文作者： Ticwear | 2016-03-11 14:39 | 专题：人工智能和李世石的世纪之战 |
【编者按】作者李理，出门问问NLP工程师。本文原标题：AlphaGo的棋局，与人工智能有关，与人生无关。
之前我们说了MCTS回避了局面估值的问题，但是人类下围棋显然不是这样的，所以真正要下好围棋，如此从模仿人类的角度来说，这个问题是绕不过去的。人类是怎么学习出不同局面的细微区别的呢？当然不能由人来提取特征或者需要人来编写估值函数，否则还是回到之前的老路上了。我们的机器能自动学习而不需要领域的专家手工编写特征或者规则来实现估值函数呢？
眼下最火热的深度学习也许可以给我们一条路径（当然可能还有其它路径，但深度学习目前看起来解决feature的自动学习是最promising的方法之一）。
在机器学习流行之前，都是基于规则的系统，因此做语音的需要了解语音学，做NLP的需要很多语言学知识，做深蓝需要很多国际象棋大师。
而到后来统计方法成为主流之后，领域知识就不再那么重要，但是我们还是需要一些领域知识或者经验来提取合适的feature，feature的好坏往往决定了机器学习算法的成败。对于NLP来说，feature还相对比较好提取，因为语言本身就是高度的抽象；而对于Speech或者Image来说，我们人类自己也很难描述我们是怎么提取feature的。比如我们识别一只猫，我们隐隐约约觉得猫有两个眼睛一个鼻子有个长尾巴，而且它们之间有一定的空间约束关系，比如两种眼睛到鼻子的距离可能差不多。但怎么用像素来定义”眼睛“呢？如果仔细想一下就会发现很难。当然我们有很多特征提取的方法，比如提取边缘轮廓等等。
但是人类学习似乎不需要这么复杂，我们只要给几张猫的照片给人看，他就能学习到什么是猫。人似乎能自动”学习“出feature来，你给他看了几张猫的照片，然后问题猫有什么特征，他可能会隐隐预约的告诉你猫有什么特征，甚至是猫特有的特征，这些特征豹子或者老虎没有。
深度学习为什么最近这么火，其中一个重要的原因就是不需要（太多）提取feature。
从机器学习的使用者来说，我们以前做的大部分事情是feature engineering，然后调一些参数，一般是为了防止过拟合。而有了深度学习之后，如果我们不需要实现一个CNN或者LSTM，那么我们似乎什么也不用干。
CNN最早是Yann Lecun提出用来解决图像识别的问题的一种深度神经网络。由Yann LeCun提出，通过卷积来发现位置无关的feature，而且这些feature的参数是相同的，从而与全连接的神经网络相比大大减少了参数的数量。
CNN深度神经网络
因此CNN非常适合围棋这种feature很难提取问题，比如图像识别。用CNN来尝试围棋的局面评估似乎也是很自然的想法。
之前也分析过了，围棋搜索如果不到游戏结束，深的局面并不比浅的容易评估，所以我们不需要展开搜索树，而可以直接评估一个局面下不同走法的好坏。这样做的好处是很容易获得训练数据。我们有大量人类围棋高手的对局（海量中等水平的对局），每一个局面下“好”的走法直接就能够从高手对局库里得到，认为他们的对局都是“好”的走法。但是要得到一个局面的“绝对”得分却很难，因为我们只知道一盘对局最终的结果。一盘游戏最终的胜负可能是因为布局就下得很好，也可能是因为最后的官子阶段下得好，中间具体某个局面的好坏是很难判断的（当然强化学习试图解决这个问题，但是还是很难的，下面在讨论AlphaGo的时候会有涉及）。对于一个局面，如果能知道这个局面下最好的走法（或者几个走法），那么我们对弈时就直接选择这个走法（当然这个最好的走法可能得分也很差，比如败局已定的情况下怎么走都是输）。
所以大部分研究都是用CNN来预测一个局面下最好的走法。【预测走法比估值一个局面容易，如果我们能够准确估值局面，那么最佳走法就是从走之后的局面中选择对自己最有利的走法。或者用我们做问答系统常用的比喻，预测走法是搜索引擎，局面评估是问答系统。搜索引擎只要把好的排前面就行了（甚至不一定要求排在第一，排在第一页也就差不多了），而问答不仅要把好的排前面，而且还要知道这个最“好”的结果是否足够“好”，因为排序的好是相对“好”，问答的好必须是绝对的“好”，是唯一正确答案】。
最早用CNN（当然还有用其它机器学习方法）来预测走法是2003年Van Der Werf等人的工作，他们用了很多手工构造的feature和预处理方法，他们取得了25%的预测准确率。没有细看论文，在2006年Deep Learning火之前，所以估计网络的层次很浅。
之后在2008年，这个时候Deep的神经网络已经逐渐流行了。Sutskever & Nair用来2层的CNN，第一层有15个7*7的filter，第二层用了5*5的filter，最后用了一个softmax层，输出19*19，表示每个可能走法的概率（当然需要后处理去掉不合法或者不合理的走法，比如违反棋规的打劫局面立即提回，或者在自己的眼里下棋）。他们得到了34%的预测准确率。不过有一点问题就是他们出来使用当前局面，还用了上一步走法（这个走子导致了当前局面，也就是对手的上一步走子），这个可能是有问题的，因为实际对局时对手的水平是不能确定的，用这个feature当然能提高“数字”上的准确率，但是对于下棋水平是否有负面影响是很难说的。
到了2015年，计算机的计算能力更强，深度神经网络的层次也越来越深，在围棋领域也能看到这种趋势。Clark & Storkey使用了8层的CNN，用的特征包括最原始的棋子（用了3个feature plane，表示361个点是黑棋/白棋/空白），ko（劫）的约束，一个group（块）的气。包括使用很多trick来保证symmetries（因为围棋的局面旋转90/180/270/360度后以及做180度的镜像之后应该是一样的）。他们在GoGoD数据上的预测准确率达到了41.1%，在KGS数据上的准确率达到44.4%。GoGoD上大部分是职业选手的对局，而KGS数据有很多业余高手的对局。
光是预测准确率，并不能说明下棋的水平。因此Maddison等人的工作把Move Prediction用到了实际的对弈当中。
他们的CNN增加到了12层，feature也有所增加，下面是他们使用的feature。
第一组feature是棋子（Stone）的颜色，和之前一样。
第二组是棋子（所在group）的气，用4个plane来表示，分别是1，2，3 >=4口气。
第三组是走了这步棋之后的气，用了6个plane，代表1，2，3，4，5，>=6口气。
第四组表示这个走法在当前局面是否合法。
第五组表示这个棋子距离当前局面的轮次，比如上一步对手走的就是1，上上一步自己走的就是2。因为围棋很多都是局部的战役，所以这个feature应该是有用的。
第六组就是表示走这这后能吃对方多少个棋子。
第七组表示走这能否征子成功。
第八组feature比较有趣，按照作者的说法就是因为KGS的对弈水平参差不齐，如果只留下高手的对局数据太少，所以用这个feature。
他们在KGS数据上的预测准确率达到55%。相对于Clark等人的工作，Maddison的工作除了增加了CNN的层次（8到12），增加的feature应该是很有帮助的，比如Turns Since，Capture Size和Ladder Move。尤其是Ladder Move，下过围棋的都知道征子能否成功对应是否要走这步棋已经局部的计算非常重要。
根据他们的使用，人类6d的预测准确率也只有52%，所以从预测走法的角度来说，CNN的水平已经达到了6d的水平。
另外他们还做了实验，证明Clark那些用来保证symmetry的tricky并没有什么卵用，直接简单粗暴的把数据做symmetric变换后训练就行了。
完全不用搜索直接用Move Prediction的结果下棋，能97%的比率战胜GnuGo（这个是完全基于alpha-beta搜索的），作者并没有说明只用Move Prediction的绝对水平，而只是和很差的GnuGo比较，所以应该水平不怎么样。
加上MCTS之后他们的水平能达到主流MCTS的开源软件如Pachi何Fuego的水平。当然CNN的预测相对于Simulation来说是很慢的，他们的GPU（4个GeForce GTX Titan Black）评估128个局面需要0.15s，而CPU（16 Intel Xeon E52643 v2 3.5GHz）每秒可以simulation 47,000个局面。所以他们使用了异步的策略，先用先验知识给出一个节点的N(v),Q(v)，先搜索着，等GPU运算完了再用CNN预测的胜率更新这些统计量。因此CPU和GPU的速度需要能大致匹配。
和Google DeepMind进行围棋竞赛的主要就是Facebook Tian yuandong他们了。在Google宣布文章在Nature发表的前一天，他们在arxiv上发表了自己的工作。
下面我们来看看他们的工作（《Better Computer Go Player with Neural Network and Long-Term Prediction》）。
使用的feature：
除了使用之前工作的标准feature之外，他们增加了一些feature，比如是否边界，距离中心的远近，是否靠近自己与对手的领土（不清楚怎么定义领土的归属的）。此外对于之前的feature也进行了压缩，之前都把特征分成黑棋或者白棋，现在直接变成己方和对手，这样把模型从两个变成了一个（之前需要给黑棋和白棋分别训练一个模型）。此外的一个不同地方就是类似于Multi-task的learning，同时预测未来3步棋的走法（而不是1步棋走法）。
为了与Maddison的工作比较，这里只用了标准的features，比较的也是未来1步棋的准确率，可以发现这个方法还是有效的（不过我个人觉得作者应该自己复现Maddison的结果而不是直接用他的结果）
只使用DCNN的围棋软件（不用MCTS搜索）
darkforest: 标准的feature，一步的预测，使用KGS数据
darkforest1：扩展的feature，三步预测，使用GoGoD数据
darkforest2：基于darkforest1，fine-tuning了一下参数。
把它们放到KGS上比赛，darkforest能到1k-1d的水平，darkforest1能到2d的水平，darkforest2能到3d的水平【注：KGS的3d应该到不了实际的业余3段】，下面是具体的情况。
因此作者认为加入3步预测的训练是有效的。
Tree Policy: 走法首先通过DCNN排序，然后按顺序选择，除非累计的概率超过0.8或者超过一定次数的top走法。Expansion使用的UCT算法。
Default Policy:参考的Pachi的tree policy，有3*3的pattern，对手打吃的点（opponent atari point），点眼的检测（detection of nakade points）等。
这个版本的软件叫darkforest3，在KGS上能到5d的水平。
DCNN预测的top3/5的走法可能不包含局部战役的一个关键点，所以它的局部作战能力还比较弱。
对于一些打劫点即使没用，DCNN还是会给高分。
当局面不好的情况下，它会越走越差（这是MCTS的弱点，因为没有好的走法，模拟出来都是输棋，一些比较顽强的抵抗的走法不能走出来）。
从上面的分析可以看出：DCNN给出的走法大局观还是不错的，这正是传统的方法很难解决的问题。局部的作战更多靠计算，MCTS会有帮助。但是我个人觉得MCTS搜索到结束，没有必要。一个局部的计算也许可以用传统的alpha-beta搜索来解决，比如征子的计算，要看6线有没有对手的棋子，另外即使有对手的棋子，也要看位置的高低，这样的计算DCNN是没法解决的，需要靠计算。
终于轮到主角上阵了，您可能不耐烦了。不过有了前面的基础，理解AlphaGo就容易多了，这里我们主要分析AlphaGo的创新点。
上图是AlphaGo所使用的两个网络以及训练过程。和之前的工作比，除了Policy Network之外，AlphaGo多了一个Value Network。
Policy Network我们通过之前的介绍以及了解到了，它的作用是Tree Policy时候的Node Selection。（rollout阶段不能使用Policy Network，因为DCNN的计算速度相对于Simulation来说太慢，所以AlphaGo又训练了一个简单的Rollout Policy，它基于一些local的pattern之类的feature训练了一个线性的softmax）。
那么Value Network又是做什么用的呢？这个Value Network就是我们之前说的很多工作都“回避”的问题——给一个局面打分，就是之前在象棋和minimax部分讨论的局面的估值函数，只不过AlphaGo是使用深度强化学习(deep reinforcment learning)学习出来，而不是像Deep Blue或者其它象棋程序那样是人工提取的feature甚至手工调整权重（当然Deep Blue是很多年前的工作了，现在也有用深度强化学习来搞国际象棋的，比如这篇论文《Giraffe: Using Deep Reinforcement Learning to Play Chess》）。
前面在讨论Tian等人的工作时我们也分析过了，光用Move Prediction的软件大局观还不错，但是局部的战术就比较差，因为局部的战术更多靠计算，人类也是这样。围棋由于估值函数比较困难，所以大都是用MCTS搜索到游戏结束。但是MCTS如果盲目搜索（使用随机的default policy去rollout/playout）肯定不好，使用各种领域知识来缩小rollout的范围就非常重要。前面我们也看到，传统的MCTS只能到2d的水平，而用DCNN的tree policy的MCTS就能到5d的水平（如果default policy如果能用DCNN指导肯定更好，可惜DCNN的速度太慢）。
这个和之前介绍的差不了太多。AlphaGo相比之前多了Rollout Policy，之前的Rollout Policy大多是使用手工编制的pattern，而AlphaGo用训练Policy Network相同的数据训练了一个简单的模型来做Rollout。
训练数据来自3千万的KGS的数据，使用了13层的CNN，预测准确率是57%，这和之前Tian等人的工作是差不多的。
之前训练的SL Policy Network优化的目标是预测走法，作者认为人类的走法会在很多promising的走法里选择，这不一定能提高AlphaGo的下棋水平。为什么？文中没有解释，我个人认为可能是一个局面（尤其是优势）的情况下有很多走法，有保守一点但是保证能赢一点点的走法，也有激进但需要算度准确的但能赢很多的走法。这取决于个人的能力（比如官子能力怎么样）和当时的情况（包括时间是否宽裕等等）。
所以AlphaGo使用强化学习通过自己跟自己对弈来调整参数学习更适合自己的Policy。
具体的做法是当前版本跟之前的某一个版本（把之前所有版本都保留和不是用最近的一个可以避免overfitting）对弈，对弈的走法是根据Policy Network来选择的，然后根据结果调整参数。这个公式用自然语言来描述就是最终得分z_t(获胜或者失败)，在t时刻局面是s_t我选择了走法a_t，P(a_t|s_t)表示局面s_t时选择走法a_t的概率，就像神经网络的反向传播算法一样，损失z_t(或者收益)是要由这个走法来负责的。我们调整参数的目的就是让这个概率变小。再通俗一点说就是，比如第一步我们的模型说必须走马(概率是1)，那么如果最终输棋，我们复盘时可能会觉得下次走马的概率应该少一点，所以我们调整参数让走马的概率小一点（就是这个梯度）。
RL Policy Network的初始参数就是SL Policy Network的参数。最后学到的RL Policy Network与SL Policy Network对弈，胜率超过80%。
另外RL Policy Network与开源的Pachi对弈（这个能到2d也就是业余两段的水平），Pachi每步做100,000次Simulation，RL Policy Network的胜率超过85%，这说明不用搜索只用Move Prediction能超过2d的水平。这和Tian等人的工作的结论是一致的，他们的darkforest2也只用Move Prediction在KGS上也能到3d的水平。
一个局面在policy p下的估值公式。用通俗的话说就是：在t时刻的局面是s，然后我们用p来下棋直到游戏结束，我们重复很多次，然后求平均的得分。当然，最理想的情况是我们能知道双方都是最优策略下的得分，可惜我们并不知道，所以只能用我们之前学到的SL Policy Network或者RL Policy Network来估计一个局面的得分，然后训练一个Value Network V(s)。前面我们也讨论过了，RL Policy Network胜率更高，而我们学出来的Value Network是用于rollout阶段作为先验概率的，所以AlphaGo使用了RL Policy Network的局面评估来训练V(s)。
V(s)的输入时一个局面，输出是一个局面的好坏得分，这是一个回归问题。AlphaGo使用了和Policy Network相同的参数，不过输出是一个值而不是361个值（用softmax归一化成概率）。
上面的公式说明：V(s)的参数theta就是简单的用梯度下降来训练
不过用一盘对局的所有(s,v(s))训练是有问题的，因为同一盘对局的相邻的局面是非常相关的，相邻的局面只差一个棋子，所有非常容易overfitting，导致模型“记住”了局面而不是学习到重要的feature。作者用这样的数据训练了一个模型，在训练数据上的MSE只有0.19，而在测试数据上是0.37，这明显overfitting了。为了解决这个问题，作者用RL Policy Network自己跟自己对局了3千万次，然后每个对局随机选择一个局面，这样得到的模型在训练数据和测试数据上的MSE是0.226和0.234，从而解决了overfitting的问题。
上面花了大力气训练了SL Policy Network,Rollout Policy和Value Network，那么怎么把它们融合到MCTS中呢？
一次MCTS的Simulation可以用上图来说明，下文加黑的地方是这三个模型被用到的地方。
首先每个节点表示一个局面，每一条边表示局面+一个合法的走法(s,a)。每条边保存Q(s,a)，表示MCTS当前累计的reward，N(s,a)表示这条边的访问次数，P(s,a)表示先验概率。
每次Simulation使用如下的公式从根节点开始一直选择边直到叶子节点（也就是这条边对于的局面还没有expand）。
Q(s_t,a)就是exploit term，而u(s_t,a)就是explore term，而且是于先验概率P(s,a)相关的，优先探索SL Policy Network认为好的走法。
对于叶子节点，AlphaGo不仅仅使用Rollout(使用Rollout Policy)计算得分，而且也使用Value Network打分，最终把两个分数融合起来：
n次Simulation之后更新统计量（从而影响Selection），为什么是n次，这涉及到多线程并行搜索以及运行与GPU的Policy Network与Value Network与CPU主搜索线程通信的问题
一个边的访问次数超过一定阈值后展开这个边对应的下一个局面。阈值会动态调整以是的CPU和GPU的速度能匹配，具体下一节我们讨论AlphaGo的实现细节再说明
a图是用分布式的AlphaGo，单机版的AlphaGo，CrazyStone等主流围棋软件进行比赛，然后使用的是Elo Rating的打分。
作者认为AlphaGo的水平超过了FanHui（2p)，因此AlphaGo的水平应该达到了2p（不过很多人认为目前Fanhui的水平可能到不了2p）。
b图说明了Policy Network Value Network和Rollout的作用，做了一些实验，去掉一些的情况下棋力的变化，结论当然是三个都很重要。
c图说明了搜索线程数以及分布式搜索对棋力的提升，这些细节我们会在下一节再讨论，包括AlphaGO的架构能不能再scalable到更多机器的集群从而提升棋力。
因为3月份AlphaGo要挑战李世石，所以大家都很关心AlphaGo到底到了什么水平。当然它的真实水平只有作者才能知道，我这里都是根据一些新闻的推测。而且从文章提交Nature审稿到3月份比赛还有一段不短的时间，AlphaGo能不能还有提高也是非常关键。这里我只是推测一下在文章提交Nature时候AlphaGo的棋力。至于AlphaGo棋力能否提高，我们下一节分析实现细节时再讨论（假设整体架构不变，系统能不能通过增加机器来提高棋力）。
网上很多文章试图通过AlphaGo与fanhui的对局来估计AlphaGo的棋力，我本人不敢发表意见。我只是搜索了一些相关的资料，主要是在弈城上一个叫DeepMind的账号的对局信息来分析的。
比如这篇《金灿佑分析deepmind棋谱认为99%与谷歌团队相关》。作者认为这个账号就是AlphaGo。如果猜测正确的话，AlphaGo当时的棋力在弈城8d-9d直接，换成我们常用的ranking system的话大概也就是6d-7d（业余6段到7段）的水平，如果发挥得好，最多也许能到1p的水平，战胜fanhui也有一定合理性（很多人认为fanhui目前实际水平可能已经没有2p了，那算1p的话也差不多）。
知乎上也有很多讨论，以及这篇《陈经：谷歌围棋算法存在缺陷》，都可以参考。
和之前类似，搜索树的每个状态是s，它包含了所有合法走法(s,a)，每条边包含如下的一些统计量：
P(s,a)是局面s下走a的先验概率。Wv(s,a)是simulation时value network的打分，Wr(s,a)是simulation时rollout的打分。Nv(s,a)和Nr(s,a)分别是simulation时value network和rollout经过边(s,a)的次数。Q(s,a)是最终融合了value network打分和rollout打分的最终得分。
rollout会模拟一个节点多次这比较好理解。为什么value network会给同一个节点打分多次呢？而且对于一个DCNN来说，给定一个固定的输入(s,a) P(a|s)不应该是相同的值吗，计算多次有什么意义吗？
我刚开始看了半天也没明白，后来看到Symmetries那部分才明白。原来AlphaGo没有像之前的工作那样除了对称的问题，对于APV-MCTS（Asynchronous Policy and Value MCTS)算法，每次经过一个需要rollout的(s,a)时，会随机的选择8个对称方向中的一个，然后计算p(a|s)，因此需要平均这些value。计算Policy Network的机器会缓存这些值，所以Nv(s,a)应该小于等于8。
还是这个图。
从根节点开始使用下面的公式选择a直到叶子节点。
Q(s,a)初始值为0，后面Backup部分会讲怎么更新Q(s,a)。
现在我们先看这个公式，第一部分Q(s,a)是exploit term，第二部分是explore term。这个公式开始会同时考虑value高的和探索次数少的走法，但随着N(s,a)的增加而更倾向于value高的走法。
叶子节点sL被加到一个队列中等到value network计算得分（异步的），然后从sL开始使用rollout policy模拟对局到游戏结束。
在Simulation开始之前，把从根一直到sL的所有的(s,a)增加virtual loss，这样可以防止（准确的说应该是尽量不要，原文用的词语是discourage，当然如果其它走法也都有线程在模拟，那也是可以的）其它搜索线程探索相同的路径。
上面的给(s,a)增加virtual 的loss，那么根据上面选择的公式，就不太会选中它了。
当模拟结束了，需要把这个virtual loss去掉，同时加上这次Simulation的得分。
此外，当GPU算完value的得分后也要更新：
最终算出Q(s,a):
当一条边(s,a)的访问次数Nr(s,a)【提个小问题，为什么是Nr(s,a)而不是Nv(s,a)？】超过一个阈值Nthr时会把这条边的局面（其实就是走一下这个走法）s’=f(s,a)加到搜索树里。
初始化统计量：Nv(s’,a)=0, Nr(s’,a)=0, Wv(s’,a)=0, Wr(s’,a)=0, P(s’,a)=P(a|s’)
由于计算P(a|s’)需要在GPU中利用SL Policy Network计算，比较慢，所以先给它一个place-holder的值，等到GPU那边算完了再更新。
这个place-holder的值使用和rollout policy类似的一个tree policy计算出来的（用的模型了rollout policy一样，不过特征稍微丰富一些，后面会在表格中看到），在GPU算出真的P(a|s’)之前的selection都是先用这个place-holder值，所以也不能估计的太差。因此AlphaGO用了一个比rollout feature多一些的模型。
Expansion的阈值Nthr会动态调整，目的是使得计算Policy Network的GPU能够跟上CPU的速度。
一台Master机器执行主搜索（搜索树的部分），一个CPU集群进行rollout的异步计算，一个GPU集群进行Policy和Value Network的异步计算。
整个搜索树都存在Master上，它只负责Selection和Place-Holder先验的计算以及各种统计量的更新。叶子节点发到CPU集群进行rollout计算，发到GPU集群进行Policy和Value Network的计算。
最终，AlphaGo选择访问次数最多的走法而不是得分最高的，因为后者对野点(outlier)比较敏感。走完一步之后，之前搜索过的这部分的子树的统计量直接用到下一轮的搜索中，不属于这步走法的子树直接扔掉。另外AlphaGo也实现了Ponder，也就是对手在思考的时候它也进行思考。它思考选择的走法是比较“可疑”的点——最大访问次数不是最高得分的走法。AlphaGo的时间控制会把思考时间尽量留在中局，此外AlphaGo也会投降——当它发现赢的概率低于10%，也就是 MAXaQ(s,a) < -0.8。
AlphaGo并没有想常见的围棋那样使用AMAF或者RAVE启发，因为这些策略并没有什么用处，此外也没有使用开局库，动态贴目(dynamic komi)等。
使用了两大类pattern，一种是response的pattern，也就是上一步走法附近的pattern（一般围棋很多走法都是为了“应付”对手的走子）；另一种就是非response的pattern，也就是将要走的那个走法附近的pattern。具体使用的特征见下表。Rollout Policy比较简单，每个CPU线程每秒可以从空的局面（开局）模拟1000个对局。
横线之上的feature用来rollout，所有的feature用来计算place-holder先验概率。
前面在讲Search Algorithm讲过了。
SL Policy Network使用了29.4 million局面来训练，这些局面来自KGS 6d-9d 的16万个对局。使用了前1million用来测试，后面的28.4million用来训练。此外进行了旋转和镜像，把一个局面变成8个局面。使用随机梯度下降算法训练，训练的mini-batch大小是16。使用了50个GPU的DistBelief（并没有使用最新的Tensorflow），花了3周的时间来训练了340million次训练步骤（每个mini-batch算一个步骤？）
每次用并行的进行n个游戏，使用当前版本(参数)的Policy Network和之前的某一个版本的Policy Network。当前版本的初始值来自SL Policy Network。然后用 Policy Gradient来更新参数，这算一次迭代，经过500次迭代之后，就认为得到一个新的版本把它加到Pool里用来和当前版本对弈。使用这种方法训练，使用50个GPU，n=128，10,000次对弈，一天可以训练完成RL Policy Network。
前面说了，训练的关键是要自己模拟对弈然后随机选择局面而不是直接使用KGS的对局库来避免overfitting。
AlphaGo生成了3千万局面，也就是3千万次模拟对弈，模拟的方法如下：
随机选择一个time-step U~unif{1,450}
根据SL Policy Network走1，2，… , U-1步棋
然后第U步棋从合法的走法中随机选择
然后用RL Policy Network模拟对弈到游戏结束
被作为一个训练数据加到训练集合里。
这个数据是
的一个无偏估计。
最后这个Value Network使用了50个GPU训练了一周，使用的mini-batch大小是32。
其实和前面Tian的差不太多，多了两个征子相关的feature，另外增加了一个常量1和常量0的plane。
最后一个feature 是value network用的，因为判断局面得分时要知道是谁走的，这个很关键。
13层从CNN，输入时19*19*48，第一个hidden层把输入用零把输入padding成23*23，然后用k个5*5的filter，stride是1。
2到12层首先用零把输入padding成21*21，然后使用k个5*5的filter，stride依然是1。
最后一层用一个1*1的filter，然后用一个softmax。
比赛用的k=192，文章也做了一些实验对比k=128,256,384的情况。
14层的CNN，前面12层和Policy Network一样，第13层是一个filter的卷积层，第14层是全连接的Relu激活，然后输出层是全连接的tanh单元。
不同分布式版本的水平比较，使用的是Elo rating标准。
从上面的细节来看，神经网络的训练其实用的时间和机器不多，真正非资源的还是在搜索阶段。
最强的AlphaGo使用了64个搜索线程，1920个CPU的集群和280个GPU的机器（其实也就二十多台机器）
之前我们讨论过分布式MCTS时说过，MCTS很难在多机上并行，所以AlphaGo还是在一台机器上实现的LockFree的多线程并行，只不过Rollout和神经网络计算是在CPU和GPU集群上进行的。Google的财力肯定不只二三十台机器，所以分布式MCTS的搜索才是最大的瓶颈。如果这个能突破，把机器堆到成百上千台应该还是能提高不少棋力的。
我个人估计在3月与李世石的对弈中这个架构可能还很难有突破，可以增强的是RL Policy的自对弈学习，不过这个提升也有限（否则不会只训练一天就停止了，估计也收敛的差不多了）
所以我个人的观点是3月份要战胜李世石还是难度比较大的。
之前我们讨论的都是完全信息的两人的零和博弈游戏。用的minimax也是假设对手都是走最优的走法，但实际比赛中可能并非如此。
比如为了争胜，我们可能走一些冒险的策略，这个策略下如果对手走到最佳的走法我们可能会输。但是由于局面复杂，稍有不慎可能就会走错，那么我们的目的就达到了。
还有就是多人的博弈，比如斗地主，我们可能还得对多个对手或者队友建模。比如地主最后一张牌是否要炸，还得看队友的接牌能力。
又比如你陪领导玩斗地主，另外一个人明显目的是来给领导送钱的，那么你的策略可能也需要调整。
这可能就是现实世界和人工智能的差别了。有些事情，机器永远也不会懂，比如人生。
对于人生，每个人都像一颗棋子，那么谁是下棋者呢，他又是和谁在下棋呢？
我们在下棋的时候更多的考虑是全局的利益，比如用一个兵卒换一个马炮我们会非常开心，但是作为要牺牲的兵卒来说呢？一将功成万骨枯。
人生如棋，落子无悔。等到游戏结束的时候我们来复盘，才能发现当年犯下的错误，不过毕竟于事无补，只能给后人一些经验教训罢了。
[1] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis, Mastering the game of Go with deep neural networks and tree search, Nature, 2016
[2] M. Lai, Giraffe: Using Deep Reinforcement Learning to Play Chess, arXiv. 2015
[3] Reinforcement Learning: An Introduction. Richard S. Sutton and Andrew G. Barto MIT Press, Cambridge, MA, 1998 A Bradford Book
[4] C. Browne , E. Powley , D. Whitehouse , S. Lucas , P. Cowling , P. Rohlfshagen , S. Tavener , D. Perez , S. Samothrakis and S. Colton, “A survey of Monte Carlo tree search methods”, IEEE Trans. Comput. Intell. AI Games, vol. 4, no. 1, pp. 1-43, 2012
[5] H. Baier and P. D. Drake, “The power of forgetting: Improving the last-good-reply policy in Monte Carlo Go”, IEEE Trans. Comput. Intell. AI Games, vol. 2, no. 4, pp. 303-309, 2010
[6] A. Bourki , G. M. J.-B. Chaslot , M. Coulm , V. Danjean , H. Doghmen , J.-B. Hoock , T. Hérault , A. Rimmel , F. Teytaud , O. Teytaud , P. Vayssière and Z. Yu, “Scalability and parallelization of Monte-Carlo tree search”, Proc. Int. Conf. Comput. Games, pp. 48-58, 2010
[7] M. Enzenberger , M. Müller , B. Arneson and R. B. Segal, “Fuego—An open-source framework for board games and Go engine based on Monte Carlo tree search”, IEEE Trans. Comput. Intell. AI Games, vol. 2, no. 4, pp. 259-270, 2010
[8] M. Enzenberger and M. Müller, “A lock-free multithreaded Monte-Carlo tree search algorithm”, Proc. Adv. Comput. Games, vol. 6048, pp. 14-20, 2010
[9] L. Kocsis and C. Szepesvári, “Bandit based Monte-Carlo planning”, Proc. Eur. Conf. Mach. Learn., pp. 282-293, 2006
[10] Baudis, P. & Gailly, J.-L. Pachi: State of the art open source Go program. In ˇ Advances in Computer Games, 24–38 (Springer, 2012).
[11] Sutskever, I. & Nair, V. Mimicking Go experts with convolutional neural networks. In International Conference on Artificial Neural Networks, 101–110 (2008).
[12] G. M. J.-B. Chaslot , C. Fiter , J.-B. Hoock , A. Rimmel and O. Teytaud, “Adding expert knowledge and exploration in Monte-Carlo tree search”, Proc. Adv. Comput. Games, vol. 6048, pp. 1-13, 2010
[13] R. Coquelin , Pierre-Arnaud and Munos, “Bandit algorithms for tree search”, Proc. Conf. Uncertainty Artif. Intell., pp. 67-74, 2007
[14] https://en.wikipedia.org/wiki/Minimax
[15] https://en.wikipedia.org/wiki/Branching_factor
[16] https://en.wikipedia.org/wiki/Go_ranks_and_ratings#Kyu_and_dan_ranks
[17] https://en.wikipedia.org/wiki/Alpha–beta_pruning
[18] https://www.zhihu.com/topic/20038840
[19] http://sports.sina.cn/others/qipai/2016-02-01/detail-ifxnzanm3922928.d.html?vt=4&wm=4007&cid=69557&node_id=77160
[20] Better Computer Go Player with Neural Network and Long-term Prediction. Yuandong Tian, Yan Zhu. arXiv. 2015
[21] Sutskever, I. & Nair, V. Mimicking Go experts with convolutional neural networks. In International Conference on Artificial Neural Networks, 101–110 (2008).
[22] Maddison, C. J., Huang, A., Sutskever, I. & Silver, D. Move evaluation in Go using deep convolutional neural networks. 3rd International Conference on Learning Representations (2015).
[23] Clark, C. & Storkey, A. J. Training deep convolutional neural networks to play go. In 32nd International Conference on Machine Learning, 1766–1774 (2015).
[24] Sutton, R., McAllester, D., Singh, S. & Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems,1057–1063 (2000).
本文首发CSDN
雷峰网原创文章，未经授权禁止转载。详情见转载须知。
专题
