计算机如何战胜围棋大师
当机器打败围棋大师，人工智能在战胜自然的路上又有了决定性的进步
作者：Christof Koch
日期：2016年3月19日
图为韩国专业棋手李世石在谷歌旗下DeepMind公司举行的挑战赛上对战谷歌的人工智能程序AlphaGo。（图片来源：AP Photo/Ahn Young-joon）
上帝操纵他，他操纵棋子
又是什么神，在上帝之外
开启了万物之局
——Jorge Luis Borges
在我写这篇专栏的时候，名为AlphaGo的计算机程序在首尔的公开围棋比赛上战胜了职业围棋手李世石。李世石排名世界前三，已经达到职业围棋的最高段位。关于这场人机大战，目前的情况是计算机以压倒性的3:1胜过这位杰出的人类棋手。还有一局比赛等待着他们。围棋，这种既简单又具有深度的游戏，是最后一种计算机尚未胜过人类的棋类游戏。然而，随着这次胜利，人类在围棋领域的绝对统治也瓦解了。随着旧时代的终结，新时代即将到来，AlphaGo背后的技术将会对未来的机器智能产生惊人的影响。
一举成名
AlphaGo登上围棋世界顶端的过程实在令人吃惊，国际象棋程序的经历跟它完全不同。一个由IBM公司硬件和软件工程师组成的团队用超过十年的时间研发了一种有特殊用途的超级电脑，叫作深蓝（Deep Blue）。深蓝只做一件事——下国际象棋，它每秒钟可以计算2亿步。1996年，IBM团队挑战了国际象棋世界冠军Garry Kasparov，Kasparov以3胜2负1平的成绩战胜了深蓝。但在一年后的再战中，深蓝却以3.5–2.5击败Kasparov。
像井字棋、国际跳棋、黑白棋和双陆棋一样，国际象棋也是一种传统的策略游戏，玩家轮流下棋或走棋。在牌类游戏中，玩家只能看到自己的牌和大家出过的牌，但国际象棋是与运气无关的。
围棋2500年前诞生于中国，它的规则比国际象棋简单得多：棋盘是19*19大小，白方和黑方各执一色棋子，黑先白后，交替着一子于棋盘，棋子下定后，不能再移动，双方的目标是完全围住对方的棋子，被围住的棋子将会被提出棋盘。这种极简的规则使得黑白双方在棋盘上复杂的交战成为了一种绝妙的美。
像国际象棋这类逻辑严密的游戏，复杂度是可以用可能会出现的局面数来描述的。在不同的局面下，棋手需要从几种可能的下法中选择一种。这些每轮可能的下法数被称为游戏的宽度，或分支数b。若此时轮到白方，她就需要从b种可能的下法中选择一种；而黑方可以有b种方式应对她这步棋。也就是说，下完一轮之后，白方就已经有b^2种情况需要考虑。假如一局国际象棋竞赛会持续d轮，那么这局竞赛完整的搜索树就会有b^d个终止局面（也称为终端节点或搜索树的叶子）。假如一局典型的国际象棋竞赛宽度为35，持续80轮，那么这局竞赛所有可能的局面数就会非常大，约为35^80（或写作10^123），这个数又被称作“香农数”。1950年，贝尔实验室的先驱Claude Shannon不仅创立了信息论，还完成了首篇有关国际象棋程序的论文。实际上，宇宙中所有粒子的总数也只有约10^80个，但围棋的复杂度要比它大的多。若一局围棋的典型宽度为250，深度为150，那么总共可能出现的局面数约为250^150，或写作10^360。这个数大到无法想象，因此，想要计算总共可能出现的局面数是不可能的。
比起国际象棋，围棋巨大的复杂度使得识别棋子围出一定的区域后所呈现出的形势更为困难。人类棋手会意识到棋子之间的关联，并将这种模糊的概念称作“轻”、“重”和“味”（表明棋子的姿态、配合状态）。但比起围棋的正式规则，这些概念很难用算法实现。因此，围棋程序面临的挑战非国际象棋程序可比。在AlphaGo之前，还没有围棋程序能在正常比赛中胜过人类。还有人预言，至少十年后围棋程序才有机会。
之后，由于一篇今年1月28日发表在《自然》（Nature）的文章，AlphaGo进入了公众视野。它的软件是由一个20人组成的团队研发，团队的领导者是曾经的国际象棋神童、神经学家和人工智能先驱Demis Hassabis。他来自DeepMind公司，这家公司2014年被谷歌收购。有趣的是，刊登在《自然》上的这篇文章说AlphaGo于2015年10月与欧洲围棋冠军樊麾对战，在人类选手没有让子的情况下取得了5:0的胜利。简直太令人震惊了。
内部技术
值得注意的是，AlphaGo的算法并没有包含什么真正新颖的思路和突破。它的软件结合了旧式神经网络算法和机器学习技术，运行在强大的常规硬件上，以进行准确的数学计算。它的硬件包含48 个中央处理器（central processing units,CPUs）和8个用来呈现3D图形的图形处理器（graphical processing units,GPUs）。
计算的核心是神经网络，它们是仿照生物大脑内的神经回路诞生的。置于重叠层的神经元层处理输入的棋局，然后用卷积神经网络得到关于游戏各个方面的抽象表示。这个技术最近也在自动图像识别方面（比如自动标注Facebook上所有的图片）有了突破性的表现。
AlphaGo包含两个神经网络，它们一前一后地处理棋局，力求行动最优化。价值网络可以在无需遍历搜索树中的节点的情况下估计特定局势下获胜的可能性，从而减少搜索的有效深度。而通过限制网络应对的策略，策略网络减少了游戏的宽度。策略网络决策当前的下法，然后价值网络评估其获胜的可能性。然而，对于这种完全确定（每一次的下法完全取决于之前的下法）的游戏来说，最有用的技术竟然是概率。由于搜索树上大多数树枝都无法被探索，最佳方案是在最有潜力的树枝中选取一些，并一直评估它们直到一方获胜。在搜索树上选取不同的节点进行评估会增加获胜几率。不断地重复这个过程后，即使只探索了搜索树很小的一部分，这个被称为蒙特卡罗树（Monte Carlo tree）的伪随机样本也能够导向一个最佳行动。19世纪40年代末，蒙特卡罗树技术由于核武器而罪恶地诞生于美国洛斯阿拉莫斯国家实验室（Los Alamos National Laboratory）。后来，它成功地应用于世界上最早下围棋的程序Crazy Stone。
但对这些程序来说，仅搜索蒙特卡罗树并不足以达到世界水平，AlphaGo还需要获得学习能力。最初，他们给它展示职业围棋大师之前的比赛。随后，通过让程序和自己对弈几百万次，人工智能的水平逐渐提高了。
在第一阶段，这个13层的策略神经网络还没有接触过围棋大师的比赛，一切都是从零开始。研究人员用围棋库中16万个真实的比赛训练了三千万种棋局的下法。这可比任何一个职业棋手一生中经历过的比赛都要多。每种棋局都与棋手实际上的下法配对（这个技术因此被称为监督学习），一个被称为深度机器学习的技术将调整这些网络之间的连接点，使其不断完善。之后，研究人员会给神经网络一个它之前从没见过的棋局来测试，而它准确地预测出了职业棋手的下法，哪怕不是那么完美无缺。
在第二阶段，策略网络通过强化学习来训练自己。这项技术的灵感来自行为学派（一种20世纪初起源于美国的心理学和生物学流派），这种学派认为生物体的学习是一种特定刺激和它所导致的某种行为的联结。不断地重复这个过程之后，生物体就在刺激和反应之间建立了联系。而这一切都可以在无意识的机械重复后完成。
比如，训练你的狗按命令打滚或者“装死”，你会把复杂的动作分解成一些简单的动作：躺在地上，翻滚，伸爪子。之后，一旦做出这些动作，你会奖励它们一句称赞和一小块肉。足够多次之后，它就会完全按命令行事。
强化学习几年前就被用在神经网络中了，它被用于模仿动物的行为，或是训练机器人。去年，DeepMind的研究人员又进一步利用了这项技术，他们用Atari公司在1977年10月发行的一款游戏机——Atari 2600的电子游戏训练神经网络。（在围棋中，atari表示“打吃”，是一种日本的围棋术语，指一方落子后，对方的某个子或某些子仅剩一口气，如果置之不理，下一手就会被提子。）这些游戏包括豪华屏幕弹珠（Video Pinball）、星际炮手（Stargunner）、遥控坦克（Robot Tank）、公路赛跑（Road Runner）、太空侵略者（Space Invaders）、吃豆人（Ms.Pac-Man）、异形（Alien）以及蒙特祖玛的复仇（Montezuma's Revenge）。
每次竞赛的时候，DeepMind的网络会“看”比赛的屏幕，目前比分它们也能看到。神经网络通过命令操纵杆来移动屏幕上的光标。算法会通过成千上万个路径来弄清楚竞赛规则，并实现比分的最大化。神经网络学习如何移动并击毁外星飞船，同时还要躲避它们的攻击。它在某些比赛中的表现超过了人类。在监督学习之后，AlphaGo就采用了这种强大的强化学习算法。
在最后一个阶段，决策网络自主生成了3000万种棋局来进行自我训练。这是自我对战的独特之处，使算法能够不断进步。而由于自我对战需要把自己分成两个角色，人类是做不到这一点的。
AlphaGo的特点之一是，当它采取某种最大化胜率的策略时，全然不顾步数的多少。比如，它宁愿用两步换取90 %的胜率，而不用五十步换取85%的胜率。但对于人类来说，几乎没有人会放弃一个稍微有点冒险的击败对手的机会，而去竭力维持一个很惊险但却更确定的胜利。
这一切造就了这个战胜各种竞争者并最终打败围棋大师樊麾的程序。不过，樊麾的排名并不在世界前三百，而且，他和高级棋手之间的差距实在太大了，就算训练一辈子恐怕也无法赶上李世石。因此，基于之前和樊麾的五场公开赛，李世石自信地预测他会胜过AlphaGo——连胜五场，也可能倒霉地输掉一场。但令他没有想到的是，比起樊麾六个月之前对战的那个程序，他在首尔面对的这个是有了巨大进步的版本。
深蓝与AlphaGo之间一个有趣的不同点是，前者的价值网络被准确编程了，它可以评价给定局面的价值是正面的（好）还是负面的（坏）。这个不同点使得深蓝的开发者能在其策略系统中添加准确的规则，比如“如果出现这种局面，就这样做”。 而这对于AlphaGo来说是不可能的，因为AlphaGo的所有知识都是委婉地编入其网络中的。
应用前景
深蓝是机器体力胜过人类大脑的成功典范，它的成功建立在专门研发的高速中央处理器上。虽然它战胜Kasparov是一个历史性的事件，但它的成功并没有带来什么副产品。实际上，那次比赛之后IBM就让深蓝退役了。
但AlphaGo不一样，它的中央处理器是现成的，并没有经过专门设计，这使它能够获得更强大的计算能力。研究人员将AlphaGo的计算分配给一个由1200个CPU和GPU组成的网络，但这只能略微地改善它的性能。真正起作用的是AlphaGo的“分身”能力：和自己对战，进一步提高整体水平。我们不知道AlphaGo的能力是否有上限，就像我们不知道人的脑力是否有极限一样。而这种能力，很可能就是智能系统的心脏、研究人员们一直在追随的梦想——完全的人工智能。它将会以它的强大和灵活性压倒人类。
Hassabis的团队也许正在考虑设计更强大的程序。比如，可以不依靠人类竞赛资料而一切自学的围棋程序，可以同时以国际水平下跳棋、国际象棋和围棋的程序，或者一种会打德州扑克和其它类似靠运气取胜的游戏的程序。
在《自然》中，Hassabis和他的同事详尽地描述了AlphaGo的算法和参数设置，这将会进一步加快世界范围内学术和工业实验室人工智能研究的狂热脚步。为了进一步巩固这些技术，基于路径和试错学习的算法可以用于解决各种涉及大量数据的问题，比如金融市场、医疗诊断、机器人学、军事行动等等。就业结构、大规模管制和持续增长的政治经济不平等关系产生出一些中长期影响，虽然这些影响未知，但应用人工智能的潜力巨大。一个新时代会由此开始。
AlphaGo会对围棋产生哪些影响呢？尽管总有人对国际象棋怀有悲观的预言，但随处可见的国际象棋程序有助于培养新一代的国际象棋高手，让国际象棋重获新生。这一切也可能会在围棋身上发生。毕竟，汽车和摩托车比跑步的人速度快多了，这也并没有消除跑步的乐趣，反而有更多人开始跑马拉松了。确实可以说，当人们不必追求极限的时候，反而会更享受这种充满美和智慧的游戏本身带来的乐趣。其实，在中国古代，围棋正是文人和君子想要掌握的“四艺”之一。
正如要过一个有意义的生活是为了它本身一样，下围棋也应该是为了围棋自身带来的乐趣。就像哲学家Mark Rowlands说的那样，这种乐趣可以呈现出很多形式：
“专注，全身心地沉迷在某件事中，本身就具有乐趣。献身，关注事件本身而非结果，关注活动本身而非目的，也是具有乐趣的。坚持，尽你所能、不遗余力地去做这件事，哪怕经验告诉你你不能。这就是挑战和热情的乐趣：这一刻，你无法战胜我。”
当李世石代表人类对战这股强大的围棋力量时，就拥有这种乐趣。这篇文章是献给他的。
原文链接：http://www.scientificamerican.com/article/how-the-computer-beat-the-go-master/
翻译：吴苏栗 审校：赵昌昊
留言