AlphaGo 的“前世今生”
1996 年 2 月，在美国费城举行了一项别开生面的国际象棋比赛，报名参加比赛者包括了“深蓝”计算机 和 当时世界棋王 卡斯帕罗夫。 比赛最后一天，世界棋王卡斯帕罗夫对垒“深蓝”计算机。在这场人机对弈的6局比赛中，棋王卡斯帕罗夫以 4：2 战胜计算机“深蓝”，获得 40 万美元高额奖金。人胜计算机，首次国际象棋人机大战落下帷幕。比赛在 2 月 17 日结束。其後研究小组把深蓝加以改良。 次年，也就是1997 年 5 月 11 日，在人与计算机之间挑战赛的历史上可以说是历史性的一天。 计算机在正常时限的比赛中首次击败了等级分排名世界第一的棋手。加里·卡斯帕罗夫以 2.5:3.5 （1胜2负3平）输给 IBM 的计算机程序 “深蓝”。机器的胜利标志着国际象棋历史的新时代。 其中，比赛的转折点出现在第二局。 卡斯帕罗夫第一局获胜，感觉很好。但在第二局中，双方却打得不可开交。在第 36 步棋时，电脑的做法让卡斯帕罗夫不寒而栗。在当时的情况下，几乎所有顶尖国际象棋程序都会攻击卡斯帕罗夫暴露在外的皇后，但深蓝却走出了一步更为狡猾的棋，最终的效果也更好。这令卡斯帕罗夫对电脑另眼相看。 对卡斯帕罗夫和所有旁观者来说，深蓝突然不再像电脑一样下棋（它顶住诱惑，没有攻击皇后），反而采取了只有最聪明的人类大师级选手才有可能使用的策略。通过在卡斯帕罗夫面前深藏不漏，IBM成功让人类低估了它的水平。 他的斗志和体力在随后3局被拖垮，在决胜局中，仅 19 步就宣布放弃。 后来，IBM拒绝了卡斯帕罗夫的再战请求，拆卸了“深蓝”。卡斯帕罗夫虽然后来多次挑战电脑战平，却无法找“深蓝”“复仇”，留下永久的遗憾。 在今天看来，“深蓝”还算不上智能，它主要依靠强大的计算能力穷举所有路数来选择最佳策略：“深蓝”靠硬算可以预判 12 步，卡斯帕罗夫可以预判 10 步，两者高下立现。 在 AlphaGo 诞生之前，计算机在除围棋之外，几乎所有棋类游戏上战胜了人类，唯独围棋没有被攻克，为什么呢？ 围棋游戏只有两个非常简单的规则，而其复杂性却是难以想象的，一共有 10 的 170 次方种可能性，这个数字之大，以至于用当今世界最强大的计算系统，算几十年也算不完，是没有办法穷举出围棋所有的可能结果的。所以，计算机需要一种更加聪明的方法。 直到 2016 年，AlphaGo 第一版发表在了 Nature 自然杂志上，这可是牛逼得不要不要的期刊。 而刚过去一年，Google DeepMind 又在 Nature 上发表了一篇 AlphaGo 的改进版——AlphaGo Zero，同样的围棋 AI，竟然在自然杂志上发了两次！可见他们的实力！ AlphaGo 战胜过欧洲冠军樊麾，韩国九段棋手李世石，而后又赢了世界冠军柯洁，种种迹象表明，人类已经失守最拿手的围棋了。这些围棋高手一个个都表示 AlphaGo 走到了他们想不到的地方，战胜了人类的生物极限。那 AlphaGo 又是怎么在策略上战胜人类的呢？很简单，它会做计划。 阿尔法狗（AlphaGo）是通过两个不同神经网络合作来改进下棋。这就像有两个导师，每个都是多层神经网络。它们从多层启发式二维过滤器开始，去处理围棋棋盘的定位，就像图片分类器网络处理图片一样。经过过滤，13 个完全连接的神经网络层产生对它们看到的局面判断。这些层能够做分类和逻辑推理。 这些网络通过反复训练来检查结果，再去校对调整参数，去让下次执行更好。这个处理器有大量的随机性元素，所以人们是不可能精确知道网络是如何“思考”的，但更多的训练后能让它进化到更好。 导师1号：策略网络（Policy network） AlphaGo 的第一个神经网络大脑是“策略网络（Policy Network）”，观察棋盘布局企图找到最佳的下一步。事实上，它预测每一个合法下一步的最佳概率，那么最前面猜测的就是那个概率最高的。这可以理解成“落子选择器”。 AlphaGo 团队首先利用几万局专业棋手对局的棋谱来训练系统，得到初步的“策略网络”。训练“策略网络”时，采用“深度学习”算法，基于全局特征和深度卷积网络 (CNN) 来训练，其主要作用是给定当前盘面状态作为输入，输出下一步棋在棋盘其它空地上的落子概率。 接下来，AlphaGo 采用左右互搏的模式，不同版本的 AlphaGo 相互之间下了 3000 万盘棋，利用人工智能中的“深度增强学习”算法，利用每盘棋的胜负来学习，不断优化和升级“策略网络”，同时建立了一个可以对当前局面估计白棋和黑棋胜率的“价值网络”。 导师2号：价值网络（Value network） AlphaGo 的第二个大脑相对于落子选择器是回答另一个问题。不是去猜测具体下一步，它预测每一个棋手赢棋的可能，在给定棋子位置情况下。这个局面评估器就是 “价值网络（Value Network）” ，通过整体局面判断来辅助落子选择器。 然后，AlphaGo 通过吸收人类 几千年 来优秀的棋谱，不断学习优化 策略网络 和 价值网络，从而战胜了欧洲冠军樊麾，韩国九段棋手李世石，而后又赢了世界冠军柯洁。 实际对局时，AlphaGo 通过“蒙特卡罗树搜索”来管理整个对弈的搜索过程。 首先，通过“策略网络”，AlphaGo 可以优先搜索本方最有可能落子的点（通常低于10个）。对每种可能再通过“估值网络”评估胜率，分析需要更进一步展开搜索和演算的局面。综合这几种工具，辅以超级强大的并行运算能力，AlphaGo 在推演棋局变化和寻找妙招方面的能力，已经远超人类棋手。 根据资料，最高配置的 AlphaGo 分布式版本，配置了 1920 个 CPU 和 280 个 GPU，同时可以跑 64 个搜索线程，这样的计算速度就好像有几十个九段高手同时在想棋，还有几十个三段棋手帮着把一些难以判断的局面直接下到最后，拿出结论，某一位人类棋手要与对抗，确实难以企及。 但是，这并不是重点。 终于说到重点了~~ Zero 英文意思是：零。除了围棋最基本规则（棋盘的几何学定义，轮流落子规则，终局输赢计算，打劫等），它就是一张白纸。放弃参考任何人类棋谱，完全自我学习。 如果你和一个有人类老师的 AlphaGo 交手，那可能还会在它背后看到人类下棋的影子。但是 AlphaGo Zero，完全是一个无师自通的家伙，和它下棋，你可能闻到很浓烈的机械味。但从另一方面想，这样的 AlphaGo 打破了数千年来人类下棋思维的限制，探索了人类想不到的下棋境界，学会了一个崭新的下棋方式。 仅仅经过 3 天的训练后，这套系统已经可以击败 AlphaGo Lee，也就是击败韩国顶尖棋手李世石的那套系统，而且比分高达100：0。经过 40 天训练后，它总计运行了大约 2900 万次自我对弈，使得 AlphaGo Zero 击败 AlphaGo Master，也就是击败世界冠军柯洁的系统，比分为 89：11。要知道职业围棋选手一生中的正式比赛也就一千多局， 而 AlphaGo Zero 却进行了 2900 万次对局。 在技术层面来说，AlphaGo Zero 使用的不再是之前提到的两套神经网络系统，而是将它们融合成一个神经网络系统，这样做能更有效利用资源，学习效果更好。其关键在于采用了新的 Reinforcement Learning（强化学习） ，并给该算法带了新的发展。 而且，它不再仅仅使用 GPU，转而添加了自家的专门为机器学习打造的 TPU，而且使用的硬件个数也在逐步降低，然而学习的效果却不断上升。在短短 40 天没有老师教的训练中，AlphaGo Zero 超越了他所有的前辈，在这个时候，我相信它真正做到了在围棋场上无人能敌了。 最后，正如 AlphaGo 之父 David Silver 所说，一个无师自通 AlphaGo 的产生，并不仅仅意味着我们的 AI 能在围棋场上战胜人类，放眼未来，它还意味着，在更多方面，我们能用这样的 AI 创造出更多人类历史上的新篇章。 围棋场上，无论谁赢，最终获胜的都是人类自己。
阿尔法狗团队宣布＂阿狗＂退役是怎么回事？
5月27日，升级后的AlphaGo所向披靡，最终以3：0赢下了这次乌镇人机大战。这也将是人机大战的最后3局比赛了。创始人说了什么？在最后一局比赛结束后的发布会上，AlphaGo之父、DeepMind创始人戴密斯·哈萨比斯说：“本周的比赛聚集了围棋起源地最优秀的棋手参与，是AlphaGo作为一个竞赛系统能够对弈的最高级别对手。因此，本次中国乌镇围棋峰会是AlphaGo参加的最后对弈比赛。”不过，哈萨比斯宣布，人类棋手与AlphaGo的故事并不会就此结束。AlphaGo的启蒙老师、欧洲围棋冠军樊麾随后表示：“我们将与柯洁共同研究这三局比赛，做成视频，与全世界围棋爱好者共同分享。我们还给全世界围棋爱好者准备了一份礼物，这些自我对战是阿尔法狗最宝贵的财富，我们近期会公布50副阿尔法狗自我对战的棋谱，以慢棋的形式进行。”程序员讲解新版AlaphaGo柯洁感慨：真太可怕了5月24日消息，在昨日AlphaGo战胜柯洁后，Deepmind首席程序员席尔瓦表示，战胜柯洁的AlphaGo Master比一年前战胜李世石的AlphaGo Lee强三个子。对此，柯洁再次在微博上感慨对手的强大，“我到底是在和一个怎样可怕的对手下棋”。
到底是什么让AlphaGo变得如此成功
AlphaGo这个系统主要由几个部分组成：走棋网络(Policy Network)，给定当前局面，预测/采样下一步的走棋。快速走子(Fast rollout)，目标和1一样，但在适当牺牲走棋质量的条件下，速度要比1快1000倍。估值网络(Value Network)，给定当前局面，估计是白胜还是黑胜。蒙特卡罗树搜索(Monte Carlo Tree Search，MCTS)，把以上这三个部分连起来，形成一个完整的系统。我们的DarkForest和AlphaGo同样是用4搭建的系统。DarkForest较AlphaGo而言，在训练时加强了1，而少了2和3，然后以开源软件Pachi的缺省策略 (default policy)部分替代了2的功能。以下介绍下各部分。1、走棋网络走棋网络把当前局面作为输入，预测/采样下一步的走棋。它的预测不只给出最强的一手，而是对棋盘上所有可能的下一着给一个分数。棋盘上有361个点，它就给出361个数，好招的分数比坏招要高。DarkForest在这部分有创新，通过在训练时预测三步而非一步，提高了策略输出的质量，和他们在使用增强学习进行自我对局后得到的走棋网络(RL network)的效果相当。当然，他们并没有在最后的系统中使用增强学习后的网络，而是用了直接通过训练学习到的网络(SL network)，理由是RL network输出的走棋缺乏变化，对搜索不利。有意思的是在AlphaGo为了速度上的考虑，只用了宽度为192的网络，而并没有使用最好的宽度为384的网络(见图2(a))，所以要是GPU更快一点(或者更多一点)，AlphaGo肯定是会变得更强的。所谓的0.1秒走一步，就是纯粹用这样的网络，下出有最高置信度的合法着法。这种做法一点也没有做搜索，但是大局观非常强，不会陷入局部战斗中，说它建模了“棋感”一点也没有错。我们把DarkForest的走棋网络直接放上KGS就有3d的水平，让所有人都惊叹了下。可以说，这一波围棋AI的突破，主要得益于走棋网络的突破。这个在以前是不可想像的，以前用的是基于规则，或者基于局部形状再加上简单线性分类器训练的走子生成法，需要慢慢调参数年，才有进步。当然，只用走棋网络问题也很多，就我们在DarkForest上看到的来说，会不顾大小无谓争劫，会无谓脱先，不顾局部死活，对杀出错，等等。有点像高手不经认真思考的随手棋。因为走棋网络没有价值判断功能，只是凭“直觉”在下棋，只有在加了搜索之后，电脑才有价值判断的能力。2、快速走子那有了走棋网络，为什么还要做快速走子呢？有两个原因，首先走棋网络的运行速度是比较慢的，AlphaGo说是3毫秒，我们这里也差不多，而快速走子能做到几微秒级别，差了1000倍。所以在走棋网络没有返回的时候让CPU不闲着先搜索起来是很重要的，等到网络返回更好的着法后，再更新对应的着法信息。其次，快速走子可以用来评估盘面。由于天文数字般的可能局面数，围棋的搜索是毫无希望走到底的，搜索到一定程度就要对现有局面做个估分。在没有估值网络的时候，不像国象可以通过算棋子的分数来对盘面做比较精确的估值，围棋盘面的估计得要通过模拟走子来进行，从当前盘面一路走到底，不考虑岔路地算出胜负，然后把胜负值作为当前盘面价值的一个估计。这里有个需要权衡的地方：在同等时间下，模拟走子的质量高，单次估值精度高但走子速度慢；模拟走子速度快乃至使用随机走子，虽然单次估值精度低，但可以多模拟几次算平均值，效果未必不好。所以说，如果有一个质量高又速度快的走子策略，那对于棋力的提高是非常有帮助的。为了达到这个目标，神经网络的模型就显得太慢，还是要用传统的局部特征匹配(local pattern matching)加线性回归(logistic regression)的方法，这办法虽然不新但非常好使，几乎所有的广告推荐，竞价排名，新闻排序，都是用的它。与更为传统的基于规则的方案相比，它在吸纳了众多高手对局之后就具备了用梯度下降法自动调参的能力，所以性能提高起来会更快更省心。AlphaGo用这个办法达到了2微秒的走子速度和24.2%的走子准确率。24.2%的意思是说它的最好预测和围棋高手的下子有0.242的概率是重合的，相比之下，走棋网络在GPU上用2毫秒能达到57%的准确率。这里，我们就看到了走子速度和精度的权衡。和训练深度学习模型不同，快速走子用到了局部特征匹配，自然需要一些围棋的领域知识来选择局部特征。对此AlphaGo只提供了局部特征的数目(见Extended Table 4)，而没有说明特征的具体细节。我最近也实验了他们的办法，达到了25.1%的准确率和4-5微秒的走子速度，然而全系统整合下来并没有复现他们的水平。我感觉上24.2%并不能完全概括他们快速走子的棋力，因为只要走错关键的一步，局面判断就完全错误了；而图2(b)更能体现他们快速走子对盘面形势估计的精确度，要能达到他们图2(b)这样的水准，比简单地匹配24.2%要做更多的工作，而他们并未在文章中强调这一点。在AlphaGo有了快速走子之后，不需要走棋网络和估值网络，不借助任何深度学习和GPU的帮助，不使用增强学习，在单机上就已经达到了3d的水平(见Extended Table 7倒数第二行)，这是相当厉害的了。任何使用传统方法在单机上达到这个水平的围棋程序，都需要花费数年的时间。在AlphaGo之前，Aja Huang曾经自己写过非常不错的围棋程序，在这方面相信是有很多的积累的。3、估值网络AlphaGo的估值网络可以说是锦上添花的部分，从Fig 2(b)和Extended Table 7来看，没有它AlphaGo也不会变得太弱，至少还是会在7d-8d的水平。少了估值网络，等级分少了480分，但是少了走棋网络，等级分就会少掉800至1000分。特别有意思的是，如果只用估值网络来评估局面(2177)，那其效果还不及只用快速走子(2416)，只有将两个合起来才有更大的提高。我的猜测是，估值网络和快速走子对盘面估计是互补的，在棋局一开始时，大家下得比较和气，估值网络会比较重要；但在有复杂的死活或是对杀时，通过快速走子来估计盘面就变得更重要了。考虑到估值网络是整个系统中最难训练的部分(需要三千万局自我对局)，我猜测它是最晚做出来并且最有可能能进一步提高的。关于估值网络训练数据的生成，值得注意的是文章中的附录小字部分。与走棋网络不同，每一盘棋只取一个样本来训练以避免过拟合，不然对同一对局而言输入稍有不同而输出都相同，对训练是非常不利的。这就是为什么需要三千万局，而非三千万个盘面的原因。对于每局自我对局，取样本是很有讲究的，先用SL network保证走棋的多样性，然后随机走子，取盘面，然后用更精确的RL network走到底以得到最正确的胜负估计。当然这样做的效果比用单一网络相比好多少，我不好说。一个让我吃惊的地方是，他们完全没有做任何局部死活/对杀分析，纯粹是用暴力训练法训练出一个相当不错的估值网络。这在一定程度上说明深度卷积网络(DCNN)有自动将问题分解成子问题，并分别解决的能力。另外，我猜测他们在取训练样本时，判定最终胜负用的是中国规则。所以说三月和李世石对局的时候也要求用中国规则，不然如果换成别的规则，就需要重新训练估值网络(虽然我估计结果差距不会太大)。至于为什么一开始就用的中国规则，我的猜测是编程非常方便(我在写DarkForest的时候也是这样觉得的)。4、蒙特卡罗树搜索这部分基本用的是传统方法，没有太多可以评论的，他们用的是带先验的UCT，即先考虑DCNN认为比较好的着法，然后等到每个着法探索次数多了，选择更相信探索得来的胜率值。而DarkForest则直接选了DCNN推荐的前3或是前5的着法进行搜索。我初步试验下来效果差不多，当然他们的办法更灵活些，在允许使用大量搜索次数的情况下，他们的办法可以找到一些DCNN认为不好但却对局面至关重要的着法。一个有趣的地方是在每次搜索到叶子节点时，没有立即展开叶子节点，而是等到访问次数到达一定数目(40)才展开，这样避免产生太多的分支，分散搜索的注意力，也能节省GPU的宝贵资源，同时在展开时，对叶节点的盘面估值会更准确些。除此之外，他们也用了一些技巧，以在搜索一开始时，避免多个线程同时搜索一路变化，这部分我们在DarkForest中也注意到了，并且做了改进。5、总结总的来说，这整篇文章是一个系统性的工作，而不是一两个小点有了突破就能达到的胜利。在成功背后，是作者们，特别是两位第一作者David Silver和Aja Huang，在博士阶段及毕业以后五年以上的积累，非一朝一夕所能完成的。他们能做出AlphaGo并享有现在的荣誉，是实至名归的。从以上分析也可以看出，与之前的围棋系统相比，AlphaGo较少依赖围棋的领域知识，但还远未达到通用系统的程度。职业棋手可以在看过了寥寥几局之后明白对手的风格并采取相应策略，一位资深游戏玩家也可以在玩一个新游戏几次后很快上手，但到目前为止，人工智能系统要达到人类水平，还是需要大量样本的训练的。可以说，没有千年来众多棋手在围棋上的积累，就没有围棋AI的今天。
