AlphaGo 的棋局，与人工智能有关，与人生无关

比如这篇《金灿佑分析 deepmind 棋谱认为 99%与谷歌团队相关》。作者认为这个账号就是 AlphaGo。如果猜测正确的话，AlphaGo 当时的棋力在弈城 8d-9d 直接，换成我们常用的 ranking system 的话大概也就是 6d-7d（业余 6 段到 7 段）的水平，如果发挥得好，最多也许能到 1p 的水平，战胜 fanhui 也有一定合理性（很多人认为 fanhui 目前实际水平可能已经没有 2p 了，那算 1p 的话也差不多）。

知乎上也有很多讨论，以及这篇《陈经：谷歌围棋算法存在缺陷》，都可以参考。

AlphaGo 的实现细节 Search Algorithm

和之前类似，搜索树的每个状态是 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。

Selection(图 a)

从根节点开始使用下面的公式选择 a 直到叶子节点。

图片描述Q(s,a) 初始值为 0，后面 Backup 部分会讲怎么更新 Q(s,a)。

现在我们先看这个公式，第一部分 Q(s,a) 是 exploit term，第二部分是 explore term。这个公式开始会同时考虑 value 高的和探索次数少的走法，但随着 N(s,a)的增加而更倾向于 value 高的走法。

Evaluation(图c)

叶子节点 sL 被加到一个队列中等到 value network 计算得分（异步的），然后从 sL 开始使用 rollout policy 模拟对局到游戏结束。

Backup(图 d)

在 Simulation 开始之前，把从根一直到 sL 的所有的 (s,a) 增加 virtual loss，这样可以防止（准确的说应该是尽量不要，原文用的词语是 discourage，当然如果其它走法也都有线程在模拟，那也是可以的）其它搜索线程探索相同的路径。

上面的给 (s,a) 增加 virtual 的 loss，那么根据上面选择的公式，就不太会选中它了。

当模拟结束了，需要把这个 virtual loss 去掉，同时加上这次 Simulation 的得分。

此外，当 GPU 算完 value 的得分后也要更新：

最终算出Q(s,a):

Expansion(图 b)

当一条边 (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 的速度。

Distributed APV-MCTS 算法

一台 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)等。

Rollout Policy

（编辑：应用网_丽江站长网）

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