田渊栋博士解析AlphaGo原理及谷歌人工智能发展现状

hwyzw

    田元东，博士。卡内基梅隆大学机器人学博士，人工智能组研究员。

    2016年4月，我在朋友圈转发了一篇关于《原理》的文章，有同学留言说作者是他的大学舍友。我今天读了这篇文章。

    翻译过来就是Alpha Go。 Go的英文翻译是Go，是日文发音的音译。日语Go的音译很可能是从唐寅传下来的。很困惑。

    人工智能迄今为止发展得如何？我认为谷歌代表了世界顶尖水平。它已经收购了 9 家机器人公司，这使得谷歌可以轻松收购 20 亿美元以下的公司。其实的母公司就叫，大家都习惯统称为。谷歌帝国的布局如下：

    谷歌的内部基础设施包括搜索、广告、地图、应用程序和相关技术。不过，Nest、Fiber、  和 X 都是子公司。

    是  Life  的新名称。他们正在进行的基础研究包括智能隐形眼镜和腕式计算机，这些计算机可以分析注射到血液中的纳米颗粒。

    实验室中，团队希望将月球探测器应用到城市生活中。

    ，一个人工智能团队。

    X 的自动驾驶汽车部门。

    Fiber是光纤通信的实验项目，旨在构建高速互联网基础设施。

    ATAP也可以被视为子公司。 A的全称是“and”，指的是的先进技术和产品。

    视频编辑器；播放播客。

    回到Alpha Go机器人。

    2016年3月，阿尔法围棋与围棋世界冠军、围棋职业九段棋手李世石对决，以4-1获胜；

    2016年底、2017年初，Alpha Go程序在中国象棋网站上与中日韩数十位围棋高手进行了一场快棋对决，连续60盘失败；

    2017年5月，在中国乌镇围棋峰会上，与世界排名第一的围棋世界冠军柯洁交手，以3-0获胜。

    围棋界公认，阿尔法围棋的棋力已经超过了人类职业围棋的顶尖水平。 2017年5月，团队宣布不再参加围棋比赛。

    2017年10月18日，团队公布最强版本，代号零。

    我打算写一下谷歌和这些公司的黑科技。经过一番研究后，我将从这篇文章开始。

    以下是田博士的文章。这仍然不是零。

    （GO）是第一个击败人类职业围棋选手的人工智能程序，也是第一个击败世界围棋冠军的人工智能程序。它是由  (GOOG) 旗下公司 Demis  领导的团队开发的。其主要工作原理是“深度学习”。

   

    最近，我仔细阅读了《》杂志发表的文章，写了一些分析与大家分享。

    该系统主要由几部分组成：

    1. 移动网络 ( )，给定当前情况，预测/采样下一步移动。

    2.快速移动（Fast），目标与1相同，但在适当牺牲移动质量的情况下，速度比1快1000倍。

    3. 估价网络（Value），根据目前的情况，估计是白方胜还是黑方胜。

    4、蒙特卡罗树搜索（MCTS）将以上三部分连接起来，形成一个完整的系统。

    我们的 和 也是使用 4 构建的系统。相比之下，在训练时加强了 1，而省略了 2 和 3，然后将 2 的功能部分替换为开源软件 Pachi 的默认策略（ ）。下面对各部分进行介绍。

    1、棋牌网：

    国际象棋走棋网络将当前情况作为输入并预测/采样下一个国际象棋走棋。它的预测不仅给出最强的走法，而且还为棋盘上所有可能的下一步走法给出分数。棋盘上有 361 个点，给出了 361 个数字。好的动作比坏的动作得分更高。这部分是有创新的。通过在训练过程中预测三步而不是一步，提高了策略输出的质量，这相当于他们使用强化学习进行自我对弈后获得的国际象棋网络（RL）的效果。当然，他们在最终的系统中并没有使用强化学习之后的网络，而是使用了直接通过训练学习到的网络（SL）。原因是RL输出的着法缺乏变化，这不利于搜索。

    有趣的是，为了速度，只使用了宽度为192的网络，而没有使用宽度为384的最佳网络（见图2(a)），所以如果GPU更快（或者更多一点），它肯定会变得更强。

    所谓0.1秒步，简单来说就是利用这样的网络，以最高的置信度产生合法的走法。这种做法根本不搜索，但大局观很强，不会陷入局部战斗。说它模拟了“国际象棋手感”并没有错。我们把下棋网络直接放在KGS上，达到了3D的水平，让大家惊叹不已。可以说，围棋AI的这一波突破主要得益于国际象棋网络的突破。这在过去是不可想象的。过去，移动生成方法是基于规则，或者基于局部形状和简单的线性分类器训练。花了数年时间慢慢调整参数才取得进展。

    当然，仅仅下棋也存在很多网络问题。正如我们上面所看到的，会出现不必要的不​​分大小的灾难争斗、不必要的优先权丧失、不顾局部生死、战斗失误等等，这有点像高手不经过深思熟虑的随意走棋。因为下棋网络没有价值判断功能，只是根据“直觉”下棋，所以只有加入搜索后，计算机才具备进行价值判断的能力。

    2. 快速行动

    那么有了国际象棋走棋网络，为什么我们还需要快速走棋呢？有两个原因。首先，国际象棋网络的运行速度比较慢。据说是3毫秒，这里也差不多，而快速移动则可以达到几微秒的程度，相差了1000倍。因此，当棋网没有返回时，保持CPU不空闲，先进行搜索是非常重要的。当网络返回更好的走法后，相应的走法信息将会更新。

    其次，快速移动可以用来评估棋盘。由于可能的位置数量巨大，Go 中的搜索是无望的。当搜索达到一定程度时，就需要对现有的位置进行评估。在没有计价网络的情况下，不像国际象棋可以通过计算棋子的分数来对棋盘进行更准确的计价，围棋棋盘的估价必须通过模拟走棋来进行，从当前棋盘开始一路进行到最后，无论并列计算输赢，然后用赢输值作为当前棋盘值的估计。这里有一个权衡：同时，模拟走棋的质量高，单次估值的准确性高，但走棋的速度慢；模拟走法速度快，甚至采用随机走法，但单次估价准确度较低。 ，但是你可以模拟几次，计算平均值，效果可能还不错。因此，如果你有一个高质量、快速移动的策略，对于提高你的棋艺能力会有很大的帮助。

    为了达到这个目标，神经网络模型太慢了，我们仍然需要使用传统的局部特征匹配（local）加线性回归（）的方法。虽然这个方法并不新鲜，但是非常容易使用。几乎所有的广告推荐和竞价都会用到它。排名、新闻排序都用它。与更传统的基于规则的解决方案相比，它具有在吸收许多专家博弈后使用梯度下降方法自动调整参数的能力，因此性能提升会更快、更省心。使用该方法，实现了2微秒的移动速度和24.2%的移动精度。 24.2%意味着它的最佳预测与围棋大师的棋步一致，概率为0.242。相比之下，Go 网络在 GPU 上可以在 2 毫秒内达到 57% 的准确率。在这里，我们看到了移动速度和准确性之间的权衡。

    与训练深度学习模型不同，快速走棋使用局部特征匹配，这自然需要一些围棋领域知识来选择局部特征。仅提供了局部特征的数量（见表4），没有指定特征的具体细节。我最近试验了他们的方法，取得了25.1%的准确率和4-5微秒的移动速度。然而整个系统的整合并没有再现他们的水平。我觉得24.2%的人没有完全总结出自己快速出手的强度，因为只要迈出了错误的关键一步，对局势的判断就会完全错误；图2(b)更好地反映了他们对棋局形势的准确估计以及他们快速移动的动作。为了达到他们图2(b)的水平，需要做的工作不仅仅是简单地匹配24.2%，而且他们在文章中没有强调这一点。

    有了快速走法之后，就不需要移动国际象棋网络和估价网络，不需要任何深度学习和GPU的帮助，也不需要使用强化学习，在单机上已经达到了3D的水平（参见表 7 中倒数第二个 OK），这非常强大。使用传统方法，任何 Go 程序在单台机器上达到这个水平都需要数年时间。 Aja Huang之前写过非常好的Go程序，相信他在这方面也积累了不少。

    3. 估值网络

   

    估值网络可以说是锦上添花。从图2(b)和表7来看，没有它也不会变得太弱，至少还是7d-8d的水平。没有估价网络，等级分数会减少480点，但如果没有走棋网络，等级分数会减少800到1000点。特别有趣的是，如果仅使用估值网络来评估情况（2177），效果不如仅使用快速移动（2416）。只有两者结合起来，才能取得更大的提升。我的猜测是，估值网络和快速波动与董事会的估计是互补的。棋局刚开始的时候，大家下棋比较和谐的时候，估值网络就会更加重要；但当出现复杂的生死或对决时，估值网络就会更加重要。通过快速移动来估计棋盘变得更加重要。考虑到估值网络是整个系统中最难训练的部分（需要3000万次自我博弈），我猜它是最后做的，也是最有可能进一步完善的。

    关于估值网络训练数据的生成，值得注意的是文章附录中的小字。与下棋网络不同的是，每一盘棋只取一个样本进行训练，避免过拟合。否则，对于同一个游戏，输入略有不同，但输出相同，这对训练非常不利。这就是为什么需要 3000 万场比赛，而不是 3000 万个棋盘。对于每个自玩游戏来说，采样都是非常有讲究的。首先使用SL来保证走法的多样性，然后随机走棋，走棋盘，然后使用更精确的RL来得到对结果最准确的估计。当然，我不能说这比使用单个网络好多少。

    让我惊讶的一点是，他们根本没有做任何局部的生死/战斗分析，纯粹是用暴力的训练方式来训练出一个相当不错的估值网络。这在一定程度上说明深度卷积网络（DCNN）具有自动将问题分解为子问题并单独解决的能力。

    另外，我猜他们在抽取训练样本时，是用中国的规则来决定最终结果的。因此，三月份对阵李世石时，也需要中国规则。否则，如果换成其他规则，就需要重新训练估值网络（虽然我估计结果差别不会太大）。至于为什么一开始就用中文规则，我猜测是编程很方便（我写的时候也有这种感觉）。

    4. 蒙特卡罗树搜索

    这部分基本上都是采用传统的方法。没有太多可评论的。他们使用先验的UCT，即首先考虑DCNN认为更好的着法，然后等到每个着法被探索了更多次，然后选择更好的着法。相信探索中衍生的胜率价值。相反，我直接选择DCNN推荐的前3名或前5名的着法进行搜索。我的初步实验也显示了类似的结果。当然，他们的方法更加灵活。当允许大量搜索时，他们的方法可以找到一些 DCNN 认为不好但对情况至关重要的动作。

    一个有趣的点是，每次搜索到一个叶子节点时，该叶子节点并不是立即展开，而是一直展开直到访问次数达到一定数量（40）。这样可以避免生成过多的分支而分散搜索注意力，也可以节省GPU宝贵的资源，同时扩展时叶子节点的磁盘评估会更加准确。另外，他们还使用了一些技术来避免多个线程在搜索开始时同时搜索变化。我们也注意到了这一点并进行了改进。

    5. 总结

    总的来说，整篇文章是一个系统性的工作，而不是突破一两个小点就能取得胜利。成功的背后是作者特别是两位第一作者David和Aja Huang在博士阶段和毕业后五年多的积累。这不可能一朝一夕就能完成。他们所做的一切和现在所享有的荣誉都是当之无愧的。

    从上面的分析也可以看出，与之前的Go系统相比，它对Go领域知识的依赖较少，但还远远没有达到通用系统的水平。职业棋手看了几盘就可以了解对手的风格并采取相应的策略，而资深棋手玩几盘就可以很快掌握新棋法。然而，到目前为止，人工智能系统要达到人类水平仍然需要大量样本的训练。可以说，没有众多棋手几千年围棋的积累，就没有今天的围棋人工智能。

    在 中，强化学习的作用（ ）并没有想象中的那么大。理想情况下，我们希望人工智能系统能够在比赛过程中动态地适应环境和对手的动作，并找到应对的方法，但在比赛中，强化学习更多地用于提供更多、更好质量的样本。给予监督学习（ ）来训练更好的模型。强化学习在这方面还有很长的路要走。

    另外，根据他们的文章，整个系统在单机上已经达到了专业水平。如果谷歌愿意开上几万台机器来和李世石竞争（这对它来说再简单不过了，改一下参数就可以了），我相信竞争会非常精彩。

    ===========================

    一些更新。

    问题1：“在制作MCTS时，除了使用快速移动之外，我还使用了搜索树的现有部分。看起来与AMAF/RAVE相反：AMAF将快速移动的信息转移到树的其他不相关部分一部分是利用树的其他不相关部分来增强快速移动，我想这是否是它比其他DCNN+MCTS更强的原因之一。”

    这种方法出现在有关解决生死问题的文章中。会在一定程度上提高搜索效率，但提升多少还不知道。

    问题二：“提高棋步质量可能会导致棋艺下降。”

    这里有两种情况，树和。正如文中提到的，树的分布不能太尖锐，否则搜索时会过于注重一些看似不错的着法，从而可能导致棋力下降。但除了这个原因之外，一般来说，树越优秀，他的棋艺就会越强。

    这里，也就是（半）随机移动到最后然后得分是非常复杂的。更好的质量不一定会导致对情况的更准确的评估。需要保证的是每颗棋的生死大体都是正确的。不要为了让它活着而下死棋，反之亦然。不过对于整体情况的要求并没有那么高。双方可以合作完成每一子棋，然后继续下另一子，而不是试图领先对方并在其他地方取得领先。