是什么让AlphaGo如此成功?
鉴于当前形势,政策网络预测/取样下一步行动。
快速卷展,目标和1一样,但是在牺牲棋的质量的情况下,速度比1快1000倍。
价值网,鉴于目前情况,估计是白胜还是黑胜。
蒙特卡罗树搜索(MCTS)将上述三部分连接起来,形成一个完整的系统。
我们的暗黑森林和AlphaGo也是用4构建的系统。与AlphaGo相比,DarkForest强化了1,但缺少了2和3,然后用开源软件Pachi的默认策略代替了2的功能。下面介绍几个部分。
1,棋牌网
下棋网络将当前情况作为输入来预测/采样下一次下棋。它的预测不仅给出了最强的手牌,还对棋盘上所有可能的下一步棋给出了分数。棋盘上有361个点,给出的数字是361,走好的棋比走不好的棋得分高。
黑暗森林在这一部分有所创新。通过在训练时预测三步而不是一步,提高了策略输出的质量,相当于他们使用强化学习进行自匹配后得到的RL网络的效果。当然,他们在最终的系统中并没有使用强化学习后的网络,而是使用了直接通过训练学习到的网络(SL网络),理由是RL网络输出的招式缺乏变化,不利于搜索。
有意思的是,AlphaGo为了速度,只使用宽度为192的网络,而没有使用宽度为384的最佳网络(见图2(a)),所以如果GPU更快(或者更多),AlphaGo肯定会变强。
所谓0.1第二步,就是纯粹的利用这个网络来获取可信度最高的法律方法。这个方法根本没做搜索,但是大局感很强,不会陷入局部战斗。说它塑造了一个“棋感”并没有错。我们把DarkForest的下棋网直接放在KGS上,它有3d水平,让大家大吃一惊。
可以说,这波围棋AI的突破,主要是因为棋牌网的突破。这在以前是不可想象的。过去的算子生成方法是基于规则,或者基于局部形状和简单的线性分类器训练。它需要慢慢调整参数年取得进展。
当然,仅仅在网络上下棋也有很多问题。就我们在DarkForest上看到的,不分大小的抢将毫无意义,冲锋陷阵毫无意义,不顾地方生死,杀人失误等等。有点像大师下的一盘没有经过认真思考的棋。因为棋牌网没有价值判断功能,只是靠“直觉”下棋,只有加入搜索后,计算机才有价值判断的能力。
2.快走
那你有棋牌网为什么还要快速出招?原因有二。首先,棋牌网的运行速度比较慢。AlphaGo说是3毫秒,这里差不多,而跑得快的可以做到几微秒,差1000倍。所以在棋网不回的情况下让CPU先搜索,等网回更好的玩法后再更新相应的玩法信息,这一点很重要。
其次,快速转轮可用于评估盘面。由于可能出现的情况的天文数字,对围棋的搜索是无望的,搜索到一定程度就要对现有情况进行评估。在没有估值网络的时候,不像国象可以通过计算棋子的得分来对盘面做出更准确的估值,围棋的盘面估值还得通过模拟走法来进行,从当前盘面一路到终点,不考虑岔路口,计算出胜负,然后把胜负值作为当前盘面价值的估值。
这里有一个权衡:同时仿真步行机质量高,单次估计精度高,但步行机速度慢;模拟算子很快,甚至使用了随机算子。虽然单次估计精度低,但可以模拟几次计算平均值,效果不一定差。所以,如果有一个高质量的快棋策略,对提高棋力会很有帮助。
为了达到这个目的,神经网络的模型太慢,仍然需要传统的局部模式匹配加逻辑回归的方法。这个方法虽然不算新,但是非常好用,几乎所有的广告推荐、竞价排名、新闻排名都在用。
与更传统的基于规则的方案相比,它在吸收了众多专家后,具备了通过梯度下降法自动调整参数的能力,因此性能提升会更快更省心。AlphaGo通过这种方法实现了2微秒的跑者速度和24.2%的跑者准确率。24.2%意味着它的最佳预测与棋手儿子0.242的概率一致。相比之下,象棋网络在GPU上2毫秒就能达到57%的准确率。在这里,我们看到了步行机的速度和准确性之间的权衡。
与训练深度学习模型不同,跑得快的人使用局部特征匹配,自然需要一些围棋领域知识来选择局部特征。AlphaGo只提供了局部特征的数量(见扩展表4),并没有指定特征的具体细节。最近我也用他们的方法做了实验,取得了25.1%的准确率和4-5微秒的行走速度。然而,整个系统的整合并没有重现他们的水平。
感觉24.2%不能完全概括他们的快招,因为只要走错关键一步,形势判断就会完全错误;而图2(b)可以更好地反映他们对磁盘情况的快速跟踪估计的准确性。要达到图2(b)的水平,需要比简单匹配24.2%更多的工作,他们在文章中没有强调这一点。
AlphaGo有了快手之后,不需要下棋网络和评测网络,不需要任何深度学习和GPU的帮助,不需要强化学习,在单机上就达到了3d的水平(见扩展表7倒数第二行),相当强大。任何使用传统方法在单台计算机上达到这种水平的围棋程序都需要几年时间。在AlphaGo之前,Aja Huang曾经写过一个非常不错的围棋程序,相信在这方面也有很多积累。
3.估价网络
AlphaGo的估值网络可以说是锦上添花。从图2(b)和扩展表7来看,AlphaGo没有它也不会变得太弱,至少在7d-8d的水平。没有估值网,评分少480分,没有棋牌网,评分会少800到1000分。特别有意思的是,如果只使用评价网来评价情况(2177),其效果还不如只使用跑得快的(2416),只有将两者结合起来才能进一步提高。
我的猜测是,估值网和快跑者在盘面估算上是相辅相成的。游戏开始的时候大家玩的比较和气,估值网络会比较重要。但当出现复杂的生死或对抗时,通过快走来估计盘面就变得更重要了。考虑到估值网络是整个系统中最难训练的部分(需要3000万次自匹配),我估计是最晚做出来的,最有可能进一步完善。
关于估值网训练数据的生成,值得注意的是文章中附录的小字部分。与棋牌网不同的是,每个棋牌游戏只取一个样本进行训练,避免过拟合。否则,对于同一个游戏,输入略有不同,输出相同,对训练非常不利。这就是为什么你需要3000万个游戏而不是3000万个磁盘。对于每一场自配,采样都是很有讲究的。首先用SL网络保证棋步的多样性,然后随机走棋得到盘面,再用更精确的RL网络得到最精确的胜负估计。当然,我不能说比用单一网络好多少。
有一点让我很惊讶,他们根本不做任何局部的生死分析,只是通过暴力训练,训练出了一个相当不错的估值网络。这在一定程度上说明DCNN具有自动将问题分解为子问题并分别求解的能力。
另外,我猜他们在取训练样本的时候,用中国规则来判断最后的结果。所以我们在3月对阵李世石的时候,也要求使用中国规则,否则如果换成其他规则,就需要重新训练估值网(虽然我觉得结果差距不会太大)。至于当初为什么用中国规则,我的猜测是编程很方便(我写DarkForest的时候也有这种感觉)。
4.蒙特卡罗树搜索
这部分基本用的是传统方法,没有太多评论。他们用的是带先验的UCT,即先考虑DCNN认为更好的方法,然后等到每种方法都有更多的探索,选择更值得信赖的胜率值。而DarkForest则直接选择DCNN推荐的前3或前5的方法进行搜索。我的初步实验几乎有同样的效果。当然,他们的方法更灵活。在允许大量搜索的情况下,他们的方法可以找到一些DCNN认为不好但对情况至关重要的方法。
一个有趣的事情是,每搜索一个叶子节点,并不是立即展开,而是在访问次数达到一定数量(40)后才展开,这样可以避免分支过多,分散搜索的注意力,节省GPU的宝贵资源。同时在扩展的时候,叶子节点的磁盘会更精确。此外,他们还使用了一些技巧来防止多个线程在搜索开始时同时搜索更改,这一点我们在DarkForest中也注意到了,并进行了改进。
5.摘要
总的来说,这一整篇文章是一个系统性的工作,不是一两个小点的突破就能取得的胜利。成功的背后是作者,尤其是两位第一作者David Silver和Aja Huang在博士阶段和毕业后五年多的积累,不是一朝一夕可以完成的。他们值得能够做出AlphaGo,享受现在的荣誉。
从上面的分析也可以看出,与之前的围棋系统相比,AlphaGo对围棋领域知识的依赖更少,但远没有达到一般系统的水平。职业棋手看几局就能明白对手的打法,采取相应的策略。一个资深游戏玩家玩几遍新游戏也可以很快上手,但是到目前为止,人工智能系统仍然需要大量的样本训练才能达到人类的水平。可以说,没有围棋几千年来众多棋手的积累,就没有今天的围棋AI。