您当前的位置:主页 > R生活馆 >Facebook 研究员解析演算法技术:AlphaGo 为什幺这幺厉害? >

Facebook 研究员解析演算法技术:AlphaGo 为什幺这幺厉害?

发布时间:2020-06-06  浏览量:149  点赞:608

    Facebook 研究员解析演算法技术:AlphaGo 为什幺这幺厉害?

    最近 AlphaGo 的世纪大战引发关注,3 场比赛都打败李世乭,它究竟厉害在哪里?本篇内容来自 Facebook 人工智慧研究员田渊栋,他曾就职于 Google X 部门。

    最近我仔细看了一下 AlphaGo 在《Nature》杂誌上发表的文章,写一些分析给大家分享。

    AlphaGo 这个系统主要由几个部分组成:

    我们的 DarkForest 和 AlphaGo 同样是用 4 搭建的系统。DarkForest 较 AlphaGo 而言,在训练时加强了 1,而少了 2 和 3,然后以开源软体 Pachi 的缺省策略(default policy)部分替代了 2 的功能。以下介绍下各部分。

    1. 走棋网路

    走棋网路把当前局面做为输入,预测 / 採样下一步的走棋。它的预测不只给出最强的一手,而是对棋盘上所有可能的下一着给一个分数。棋盘上有 361 个点,它就给出 361 个数,好招的分数比坏招要高。DarkForest 在这部分有创新,透过在训练时预测三步而非一步,提高了策略输出的品质,和他们在使用增强学习进行自我对局后得到的走棋网路(RL network)的效果相当。当然,他们并没有在最后的系统中使用增强学习后的网路,而是用了直接通过训练学习到的网路(SL network),理由是 RL network 输出的走棋缺乏变化,对搜寻不利。

    Facebook 研究员解析演算法技术:AlphaGo 为什幺这幺厉害?

    有意思的是 AlphaGo 为了速度上的考虑,只用了宽度为 192 的网路,而并没有使用最好的宽度为 384 的网路(见图 a),所以要是 GPU 更快一点(或者更多一点),AlphaGo 肯定会变得更强的。

    所谓的 0.1 秒走一步,就是纯粹用这样的网路,下出有最高置信度的合法着法。这种做法一点也没有做搜索,但是大局观非常强,不会陷入局部战斗中,说它建模了「棋感」一点也没有错。我们把 DarkForest 的走棋网路直接放上 KGS 就有 3d 的水準,让所有人都惊叹了一下。可以说,这一波围棋 AI 的突破,主要得益于走棋网路的突破。这个在以前是不可想像的,以前用的是基于规则,或者基于局部形状再加上简单线性分类器训练的走子生成法,需要慢慢调参数年,才有进步。

    当然,只用走棋网路问题也很多,就我们在 DarkForest 上看到的来说,会不顾大小无谓争劫,会无谓脱先,不顾局部死活,对杀出错等。有点像高手不经认真思考的随手棋。因为走棋网路没有价值判断功能,只是凭「直觉」在下棋,只有在加了搜寻之后,电脑才有价值判断的能力。

    2. 快速走子

    那有了走棋网路,为什幺还要做快速走子呢?有两个原因,首先走棋网路的运行速度是比较慢的,AlphaGo 说是 3 毫秒,我们这里也差不多,而快速走子能做到几微秒级别,差了 1,000 倍。所以在走棋网路没有返回的时候让 CPU 不閑着先搜寻起来是很重要的,等到网路返回更好的着法后,再更新对应的着法资讯。

    其次,快速走子可以用来评估盘面。由于天文数字般的可能局面数,围棋的搜寻是毫无希望走到底的,搜寻到一定程度就要对现有局面做个估分。在没有估值网路的时候,不像国象可以透过算棋子的分数来对盘面做比较精确的估值,围棋盘面的估计得要透过模拟走子来进行,从当前盘面一路走到底,不考虑岔路地算出胜负,然后把胜负值做为当前盘面价值的一个估计。这里有个需要权衡的地方:在同等时间下,模拟走子的品质高,单次估值精度高但走子速度慢;类比走子速度快乃至使用随机走子,虽然单次估值精度低,但可以多模拟几次算平均值,效果未必不好。所以说,如果有一个品质高又速度快的走子策略,那对于棋力的提高是非常有帮助的。

    为了达到这个目标,神经网路的模型就显得太慢,还是要用传统的局部特徵匹配(local pattern matching)加线性回归(logistic regression)的方法,这办法虽然不新但非常好使,几乎所有的广告推荐、竞价排名、新闻排序,用的都是它。与更为传统的基于规则的方案相比,它在吸纳了众多高手对局之后就具备了用梯度下降法自动调参的能力,所以性能提高起来会更快更省心。AlphaGo 用这个办法达到 2 微秒的走子速度和 24.2% 的走子準确率。24.2% 的意思是说,它的最好预测和围棋高手的下子有 0.242 的概率是重合的,相比之下,走棋网路在 GPU 上用 2 毫秒能达到 57% 的準确率。这里,我们就看到了走子速度和精度的权衡。

    Facebook 研究员解析演算法技术:AlphaGo 为什幺这幺厉害?

    和训练深度学习模型不同,快速走子用到了局部特徵匹配,自然需要一些围棋的领域知识来选择局部特徵。对此 AlphaGo 只提供了局部特徵的数目(见上图),而没有说明特徵的具体细节。我最近也实验了他们的办法,达到了 25.1% 的準确率和 4-5 微秒的走子速度,然而全系统整合下来并没有複现他们的水準。感觉上 24.2% 并不能完全概括他们快速走子的棋力,因为只要走错关键的一步,局面判断就完全错误了;而下图更能体现他们快速走子对盘面形势估计的精确度,要能达到他们像下图这样的水準,比简单地匹配 24.2% 要做更多的工作,而他们并未在文章中强调这一点。

    Facebook 研究员解析演算法技术:AlphaGo 为什幺这幺厉害?

    在 AlphaGo 有了快速走子之后,不需要走棋网路和估值网路,不借助任何深度学习和 GPU 的帮助,不使用增强学习,在单机上就已经达到了 3d 的水準(见下图倒数第二行),这是相当厉害的了。任何使用传统方法在单机上达到这个水準的围棋程式,都需要花费数年的时间。在 AlphaGo 之前,Aja Huang 曾经自己写过非常不错的围棋程式,在这方面相信是有很多积累的。

    3. 估值网路Facebook 研究员解析演算法技术:AlphaGo 为什幺这幺厉害?

    AlphaGo 的估值网路可以说是锦上添花的部分,从图 b 和 Extended Table 7 来看,没有它 AlphaGo 也不会变得太弱,至少还是会在 7d-8d 的水準。少了估值网路,等级分少了 480 分,但是少了走棋网路,等级分就会少掉 800 至 1,000 分。特别有意思的是,如果只用估值网路来评估局面(2177),那其效果还不及只用快速走子(2416),只有将两个合起来才有更大的提高。我的猜测是,估值网路和快速走子对盘面估计是互补的,在棋局一开始时,大家下得比较和气,估值网路会比较重要;但在有複杂的死活或是对杀时,透过快速走子来估计盘面就变得更重要了。考虑到估值网路是整个系统中最难训练的部分(需要 3 千万局自我对局),我猜测它是最晚做出来并且最有可能能进一步提高的。

    关于估值网路训练资料的生成,值得注意的是文章中的附录小字部分。与走棋网路不同,每一盘棋只取一个样本来训练以避免过拟合,不然对同一对局而言输入稍有不同而输出都相同,对训练是非常不利的。这就是为什幺需要 3 千万局,而非 3 千万个盘面的原因。对于每局自我对局,取样本是很有讲究的,先用 SL network 保证走棋的多样性,然后随机走子,取盘面,然后用更精确的 RL network 走到底以得到最正确的胜负估计。当然这样做的效果比用单一网路相比好多少,我不好说。

    一个让我吃惊的地方是,他们完全没有做任何局部死活 / 对杀分析,纯粹是用暴力训练法训练出一个相当不错的估值网路。这在一定程度上说明深度卷积网路(DCNN)有自动将问题分解成子问题,并分别解决的能力。

    另外,我猜测他们在取训练样本时,判定最终胜负用的是中国规则。所以说 3 月和李世乭对局的时候也要求用中国规则,不然如果换成别的规则,就需要重新训练估值网路(虽然我估计结果差距不会太大)。至于为什幺一开始就用的中国规则,我的猜测是程式设计非常方便(我在写 DarkForest 的时候也是这样觉得的)。

    4. 蒙地卡罗树状搜寻

    这部分基本用的是传统方法,没有太多可以评论的,他们用的是带先验的 UCT,即先考虑 DCNN 认为比较好的着法,然后等到每个着法探索次数多了,选择更相信探索得来的胜率值。而 DarkForest 则直接选了 DCNN 推荐的前 3 或是前 5 的着法进行搜索。我初步试验下来效果差不多,当然他们的办法更灵活些,在允许使用大量搜寻次数的情况下,他们的办法可以找到一些 DCNN 认为不好但却对局面至关重要的着法。

    一个有趣的地方是在每次搜索到叶子节点时,没有立即展开叶子节点,而是等到访问次数到达一定数目(40)才展开,这样避免产生太多的分支,分散搜寻的注意力,也能节省 GPU 的宝贵资源,同时在展开时,对叶节点的盘面估值会更準确些。除此之外,他们也用了一些技巧,以在搜寻一开始时,避免多个执行绪同时搜寻一路变化,这部分我们在 DarkForest 中也注意到了,并且做了改进。

    5. 总结

    总的来说,这整篇文章是一个系统性的工作,而不是一两个小点有了突破就能达到的胜利。在成功背后,是作者们,特别是两位第一作者 David Silver 和 Aja Huang,在博士阶段及毕业以后 5 年以上的积累,非一朝一夕所能完成的。他们能做出 AlphaGo 并享有现在的荣誉,是实至名归的。

    从以上分析也可以看出,与之前的围棋系统相比,AlphaGo 较少依赖围棋的领域知识,但还远未达到通用系统的程度。职业棋手可以在看过了寥寥几局之后明白对手的风格并採取相应策略,一位资深游戏玩家也可以在玩一个新游戏几次后很快上手,但到目前为止,人工智慧系统要达到人类水準,还是需要大量样本的训练的。可以说,没有千年来众多棋手在围棋上的积累,就没有围棋 AI 的今天。

    在 AlphaGo 中,增强学习(Reinforcement Learning)所扮演的角色并没有想像中那幺大。在理想情况下,我们希望人工智慧系统能在对局中动态地适应环境和对手的招式并且找到办法反制之,但是在 AlphaGo 中增强学习更多地是用于提供更多品质更好的样本,给有监督学习(Supervised Learning)以训练出更好的模型。在这方面增强学习还有很长的路要走。

    另外,据他们的文章所言,AlphaGo 整个系统在单机上已具有了职业水準,若是 Google 愿意开几万台机器和李世乭对决(这对它来说再容易不过了,改个参数就行),相信比赛会非常精彩。

    下面是根据读者提问做的一些更新。

    问题 1:「Alphago 的 MCTS 做 rollout 的时候,除了使用快速走子,还用了搜寻树的已有部分,看起来像是 AMAF / RAVE 反过来:AMAF 是把快速走子的资讯传导到树的其他无关部分,Alphago 是把树的其他无关部分拿来增强快速走子。我怀疑这是不是它棋力比其他 DCNN+MCTS 强的原因之一。」

    这个办法在解死活题的文章中出现过,会在一定程度上提高搜索效率,但是提高多少还不知道。

    问题 2:「rollout 的走法品质变好可能会导致棋力下降。」

    这里要分两种情况,tree policy 和 default policy。在 AlphaGo 的文章里面已经说过了,tree policy 的分布不能太尖,不然在搜寻时太过重视一些看起来的好着,可能使得棋力下降。但是除了这种原因,一般来说 tree policy 变好棋力还是会变强的。

    default policy 这边,即(半)随机走子到最后然后判分,就很複杂了,品质变好未必对局面能估得更准。default policy 需要保证的是每块棋的死活大体正确,不要把死的棋下成活的或者反之,而对大局观的要求反而没有那幺高。双方完全可以配合着把每块棋下完,然后转战另一块,而不是说抢在对方前去别处佔先手。