新浪博客

人工智能的里程碑：从深蓝到AlphaGo

2017-01-11 17:31阅读：

http://blog.sina.cn/dpool/blog/u/1929644930

（这篇博文是2016年3月写的，发表在《中国人工智能学会通讯》第三期上，同时在学会微信公众号上发表，重新整理在这里，以便保留）
下棋一直被认为是人类的高智商游戏，从人工智能诞生的那一天开始，研究者就开始研究计算机如何下棋。著名人工智能研究者、图灵奖获得者约翰·麦卡锡在50年代就开始从事计算机下棋方面的研究工作，并提出了著名的α-β剪枝算法。很长时间内，该算法成为了计算机下棋程序的核心算法，著名的国际象棋程序深蓝采用的就是该算法框架。
IBM公司一直具有研究计算机下棋程序的传统，该公司的一个研究小组研究的西洋跳棋程序，在1962年就曾经战胜过美国一个州的冠军。当然，让IBM公司大出风头的是其研制的深蓝系统，在1997年首次在正式比赛中战胜人类国际象棋世界冠军卡斯帕罗夫，可以说是人工智能发展史上的一个里程碑。


人工智能的里程碑：从深蓝到AlphaGo
图灵奖获得者约翰·麦卡锡


那么，深蓝究竟是如何工作的呢？
经常听到一些人有这么一种说法，现在计算机计算速度这么快，内存这么大，完全可以依靠暴力搜索找到必胜策略战胜人类。真的有这么简单吗？答案是否定的。
曾经在资料中看到有人对中国象棋进行过估算，按照一盘棋平均大约走50步计算，总状态数约为10161的规模，假设1毫微秒走一步，约需10 145年才能生成出所有状态。这是一个什么概念呢？据估计宇宙的年龄大概是1010年量级。可见即便今天的计算机再快，也不可能生成出中国象棋的所有状态，国际象棋也基本差不多。


人工智能的里程碑：从深蓝到AlphaGo
深蓝与卡斯帕罗夫比赛
深蓝采用的是前面提到的约翰·麦卡锡提出的α-β剪枝算法。该算法的基本思想是，利用已经搜索过的状态对搜索进行剪枝，以提高搜索的效率。算法首先按照一定原则模拟双方一步步下棋，直到向前看几步为止，然后对棋局进行打分（分数越大表明对我方越有利，反之表明对对方有利），并将该分数向上传递。当搜索其他可能的走法时，会利用已有的分数，减掉对我方不利对对方有利的走法，尽可能最大化我方所得分数，按照我方所能得到的最大分数选择走步。从以上描述可以看出，对棋局如何打分是α-β剪枝算法中非常关键的内容。深蓝采用规则的方法对棋局打分，大概的思路就是对不同的棋子按照重要程度给予不同的分数，比如车分数高一点，马比车低一点等。同时还要考虑棋子的位置赋予不同的权重，比如马在中间位置比在边上的权重就大，还要考虑棋子之间的联系，比如是否有保护、被捕捉等等。当然实际系统中比这要复杂的多，但大概思想差不多，这里只是举例。这样打分看起来很粗糙，但是如果搜索的深度比较深的话，尤其是进入了残局，还是非常准确的，因为对于国际象棋来说，当进入残局后，棋子的多少可能就决定了胜负。这就如同用牛顿法数值计算一个曲线下的面积，用多个矩形近似曲线肯定有不小的误差，但是如果矩形的宽度足够小时，矩形的面积和就可以逼近曲线下的面积了，道理是一样的。
人工智能的里程碑：从深蓝到AlphaGo
α-β剪枝算法示意图
根据上面的介绍，α-β剪枝算法也只是搜索到一定的深度就停止，并不是一搜到底，那么是不是可以不用α-β剪枝算法，而是生成出小于该深度的所有状态，也可以达到同样的效果呢？换句话说，α-β剪枝算法对于提高搜索效率究竟有多大的提高呢？笔者曾经就这个问题请教过深蓝的主要参与者许峰雄博士，他回答说：在深蓝计算机上，如果不采用α-β剪枝算法，要达到和深蓝一样的下棋水平的话，每步棋需要搜索17年的时间。由此可见，α-β剪枝算法是非常有效的。在深蓝之后，中国象棋、日本将棋等，采用类似的方法先后均达到了人类顶级水平。2006年8月9日，为了纪念人工智能50周年，在浪潮杯中国象棋人机大战中，“浪潮天梭”系统击败了以柳大华等5位中国象棋大师组成的大师队，第二天再战许银川国际大师，双方战平。
人工智能的里程碑：从深蓝到AlphaGo
许银川在人机大战后接受记者采访
长时间以来，计算机在人机大战中一马平川，攻克一个又一个堡垒，唯独剩下了一个围棋，成为一个未开垦的处女地。为什么在其它棋类中屡建奇功的α-β剪枝算法对围棋不灵了呢？很多人认为是围棋的状态更多，更复杂，计算机还处理不了。从可能的状态数上来说，围棋确实更复杂一些，但笔者认为这不是根本的原因。前面分析过，在α-β剪枝算法中，非常依赖于对棋局的打分，无论是国际象棋还是中国象棋，都有一个共同的特点，一方面局面越下越简单，进入残局后，棋子的多少就可能决定胜负，另一方面，以将军为获胜标志，判断起来简单。而围棋就不同了，对局面的判断非常复杂，棋子之间相互联系，不可能单独计算，而且没有一个像将军这样的获胜标志，导致对棋局打分非常困难，从而使得计算机围棋的水平一直停止不前，即便国际上最好的围棋程序也达不到业余初段的水平。
计算机围棋的第一次突破发生在2006年，来自法国的一个计算机围棋研究团队，将信心上限决策方法引入到计算机围棋中，结合蒙特卡洛树搜索方法，使得围棋程序性能有了质的提高，在9路围棋上（9*9大小的棋盘）战胜了人类职业棋手。从此之后，围棋程序基本以蒙特卡洛树搜索结合信心上限决策方法为主要的计算框架，经过大家不断的改进提高，2013年计算机程序CrazyStone在受让四子的情况下，在19路（19*19大小的正式棋盘）围棋上战胜被称为“人脑计算机”的日本棋手石田芳夫九段，被认为达到了业余围棋五、六段的水平。
蒙特卡洛方法是二十世纪40年代中期由S.M.乌拉姆和J.冯·诺伊曼提出的一类随机模拟方法的总称，其名称来源于摩纳哥的著名赌城，可以用随机模拟的方法求解很多问题的数值解。著名的“蒲丰投针”就属于这类方法，通过向画有格子的纸上投针计算π值。
人工智能的里程碑：从深蓝到AlphaGo
蒲丰投针方法求解π值
前面提到过，传统方法之所以在围棋上失效，一个主要原因就是围棋的棋局难于估计，于是有人就想到了用蒙特卡洛随机模拟的方法对棋局进行估值。其思想很简单，对于当前棋局，随机地模拟双方走步，直到分出胜负为止。通过多次模拟，计算每个可下棋点的获胜概率，选取获胜概率最大的点走棋。在围棋程序中实际使用的是一种被称为蒙特卡洛树搜索的方法，边模拟边建立一个搜索树，父节点可以共享子节点的模拟结果，以提高搜索的效率。其基本原理如下图所示，分为一下四个过程：
l 选择：以当前棋局为根节点，自上而下地选择一个落子点。
l 扩展：向选定的节点添加一个或多个子节点。
l 模拟：对扩展出的节点用蒙特卡洛方法进行模拟。
l 回传：根据模拟结果依次向上更新祖先节点的估计值。
人工智能的里程碑：从深蓝到AlphaGo
围棋中的蒙特卡洛树搜索方法


上述过程有点类似于人类下棋时的计算过程，搜索树的深度相当于向前看多少步棋，对棋局的判断则是通过“模拟”这个过程实现的。人在计算的过程中，对可能的走棋点会分轻重缓急，重要的点多考虑，次要的点少考虑，甚至不考虑。计算机程序在第一步“选择”过程中如何体现这一想法呢？信心上限决策方法的引入就是这一思想的体现。
信心上限决策是研究多臂老虎机问题时提出的一个统计决策模型，根据该模型，可以最大化效益。在围棋问题中，每个可落子点相当于多臂老虎机的一个臂，要选择可带来最大化效益的那个节点扩展。按照信心上限决策方法，要考虑两个因素：
l 优先选择模拟过程中到目前为止胜率最大的节点，以进一步考察它是否是一个好点。
l 优先选择那些到目前为止模拟次数比较少的节点，以考察这些点是否有潜在的好点。

信心上限决策方法就是对上述两个因素的加权折中，选取Ij最大的点进行扩展，其中Ij按下式计算，是上述两个因素的加权和：
人工智能的里程碑：从深蓝到AlphaGo
其中，Xj是节点j目前的收益（比如获胜概率），n是目前为止的总的模拟次数，Tj（n）是节点j目前的模拟次数，C是加权系数，对二者的重要性进行调节。
在蒙特卡洛树搜索中引入信心上限决策方法后，计算机围棋水平得到很大的提高，最好的围棋程序已经可以达到业余5段左右的水平。由于是通过模拟的方法对棋局进行评估，如果想达到比较准确的评估，需要模拟更多的次数。因此，蒙特卡洛树搜索存在两个不足，影响了其水平的提高：（1）虽然采用了信心上限决策方法选择扩展的棋子，但是其选择范围还是全体可下子点；（2）每次模拟必须一下到底，完成整局棋的模拟，直到分出胜负为止。由于围棋可能存在的状态非常巨大，这两点均极大地影响了搜索效率，阻碍了计算机围棋水平的提高。

谷歌的AlphaGo将深度学习方法引入到蒙特卡洛树搜索中，主要设计了两个深度学习网络，一个为策略网络，用于评估可能的下子点，从众多的可下子点中选择若干个认为最好的可下子点，这样就极大地缩小了蒙特卡洛树搜索中扩展节点的范围。另一个为估值网络，可以对给定的棋局进行估值，在模拟过程中，不需要模拟到棋局结束就可以利用估值网络判断棋局是否有利。这样就可以在规定的时间内，实现更多的搜索和模拟，从而达到提高围棋程序下棋水平的目的。除此之外，AlphaGo还把增强学习引入到计算机围棋中，通过不断的自我学习，提高其下棋水平。AlphaGo就是采用的这样一种方法，具有了战胜人类最高水平棋手的能力。
人工智能的里程碑：从深蓝到AlphaGo
AlphaGo采用的两个深度学习网络
有人说AlphaGo并没有什么创新，采用的技术都是已有的技术。笔者认为这种说法是不对的，将已有的技术，针对围棋这样一个具体问题进行改进，达到战胜人类顶级棋手的水平，这就是创新性。任何技术的发展不可能出现阶跃式的发展，一定是在继承前人成果的基础上，实现创新，深蓝、沃森均是如此。这也说明，利用已有的人工智能技术，针对某些具体问题进行设计，是可以达到很高的水平的。这也为人工智能技术的具体应用提供了一个很好的思路。就在笔者正在撰写本文的时候，前方传来消息，在AlphaGo对李世石的第三盘比赛中，李世石再次投子认输，AlphaGo取得了三连胜。这是围棋程序首次在正式比赛中战胜人类围棋高手，不仅是计算机围棋的一个里程碑，也同样是人工智能的一个里程碑式的成果。
人工智能的里程碑：从深蓝到AlphaGo
AlphaGo对韩国棋手李世石比赛中
AlphaGo学习了大量的已有围棋对局，并通过自己对自己下棋，产生了很多数据对深度学习网络进行训练。那么AlphaGo在围棋走法方面是否有创新呢？在赛前，有些人，尤其是一些围棋界的人士认为，它只能走以前出现过的下法，对于一些没有见到过的下法可能就会出现应对错误。可事实不是这样的，在前两局中AlphaGo均走出了一些具有创新性的走法，甚至让在赛前充满自信的高喊“人类100%必胜”的聂卫平棋圣不由自主地说出“向AlphaGo脱帽致礼”。为什么AlphaGo会走出一些新的走法呢？一方面深度学习网络具有一定的归纳能力，另一方面，通过搜索，可以得到一些新的下法。在现场解说过程中，也有专业人士认为AlphaGo的一些走法并不好，可是事后再看呢？这些“不好”的走法可以划分为两种，一种是人认为的不好，实际上从AlphaGo的角度来说，或者从最终的结果看，下的是好的。这些就属于走法的创新。还有一种，确实走的不好，确实“损目”（即有损失），走法不够漂亮。但是AlphaGo是以赢棋为其唯一目标，在它的优化函数中并不包含“走法漂亮”这个因素。如果盘面有明显优势的情况下，若干个走法可能都会导致赢棋，只是有的赢的少点，有的赢的多点，那么在这种情况下，AlphaGo可能就只是从若干种能赢棋的走法中选择一个，而不考虑是否走法漂亮了。因此，有专业棋手从这几个不太好的走法就怀疑AlphaGo的水平，也是不客观的。
由于AlphaGo的胜利，也让一些人担心，这样发展下去人工智能会不会全面超过人类，并最终毁灭人类。这样的担心是不必要的，虽然比起深蓝来，AlphaGo更具有通用性，但它还只是限于解决某些特定的问题，不可能全面超越人类。一些人之所以针对这样的结果产生恐慌，可能是不了解AlphaGo的工作原理，被AlphaGo的能力所吓倒。在阅读了本文，了解了AlphaGo的基本原理之后，你还会为人工智能是否会毁灭人类这样的问题所困扰吗？最后，我想引用Facebook CEO扎克伯格的话来结束我的这篇文章：“人类制造机器就是为了让机器在某些方面强于人类，但是机器在某些方面超越人类并不意味着机器具有能力学习其他方面的能力，或者将不同的信息联系起来而做超越人类的事情，而这一点非常重要”。

我的更多文章

下载客户端阅读体验更佳

APP专享