深挖围棋AI技术：alphaGo在下一盘什么棋？（上）

一个边的访问次数超过一定阈值后展开这个边对应的下一个局面。阈值会动态调整以是的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算一个步骤？）

（编辑：PHP编程网 - 襄阳站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!