国际象棋与围棋，人工智能最先攻破的堡垒

作者 刘韩   2017.3.9
      2016年，距人工智能诞生的1956年60周年，按中国人的农历，这两年都是丙申年（猴年），正好是一个甲子的轮回。这一年IT行业最轰动的事件，就是AlphaGo围棋软件横扫人类世界围棋冠军。有人还在讨论计算机是否具有智能，在我看来，未来的60年，将是人工智能全面超越人类智能的时代，围棋人机大战，仅仅是这一壮丽史诗的序曲。
       2016年3月9日到15日，AlphaGo围棋软件挑战世界围棋冠军李世石的围棋人机大战五番棋在韩国首尔举行。比赛采用中国围棋规则，奖金是由Google提供的100万美元。最终AlphaGo以4比1的总比分取得了胜利。
      2016年12月29日晚起到2017年1月4日晚，AlphaGo围棋软件在弈城围棋网和野狐围棋网以“大师”（Master）为注册名，依次对战数十位人类顶尖高手，包括柯洁、朴廷桓、陈耀烨、芈昱廷、唐韦星、常昊、周睿羊和古力等世界冠军，以及中国棋圣聂卫平，取得60胜0负的辉煌战绩。
      AlphaGo在2016年的围棋水平，世界围棋冠军常昊的评论是：“它现在的水平，可以说是大大的超出了我们人类的想象。”我个人的预测，随着硬件速度的提升和软件的升级优化，以及AlphaGo左右互搏，不断自我对弈几亿盘的积累，未来版本AlphaGo的围棋水平，可以轻松击败任何人类棋手，就像金庸小说《天龙八部》之中，超凡入圣的少林寺扫地僧，可以轻轻松松秒杀萧远山、慕容博这些天下一流高手。
       回顾人工智能的发展史，棋类就一直是一个热门领域，原因很简单，因为下棋被称为智力竞技运动，而棋类的胜负和等级分，可以很好地来对比和测量人工智能系统的智能水平。
       伟大的香农，最早提出了利用计算机编写国际象棋程序的设想，并于1950年发表了论文《为计算机编程下国际象棋》（《Programming a computer for playing chess》），其内容奠定了现代弈棋机的基础。1956年，他在洛斯阿拉莫斯的MANIAC计算机上实现了一个国际象棋的下棋程序。在一篇关于计算机象棋的早期论文中，纽维尔、西蒙和克里夫·肖（Cliff Shaw)提出：“如果一个人能够设计出一台成功的弈棋机，他似乎就渗入了人类智力活动的核心。”受这些大师的激励，无数的计算机专业人士、国际象棋棋手和来自各个行业的业余爱好者开始研究和开发一代又一代的下棋系统，有些人追求胜负和奖金，有些人把下棋系统作为实验工具，研究人类智能的工作原理。
      人类思考棋类问题的核心智慧就是找到妙招，而找到妙招的关键就是推算出若干步之内无论对方如何应对，本方都处于局面变好的态势。转换到国际象棋程序编程，核心都必须有两部分：博弈搜索和局面评估。
       博弈搜索时一个招法（下一步棋）向着后续招法分叉，形成了一颗树形结构，被称为博弈树。最简单的搜索法被称为暴力搜索法（Brute force）或者A（Alpha、阿尔法）方法，这种方法全面生成所有可能的招法，并选择最优的一个，也就是尽可能对博弈树穷尽搜索。另一种策略被称为B（beta、贝塔）方法，基本思想是剔除某些树枝。
       暴力搜索法程序遇到的主要难题是博弈树所包含的局面数量实在太多太多了。国际象棋平均每个局面大约有40步符合规则的着法。如果你对每步着法都考虑应着就会遇到40 x 40 = 1600个局面。而4步之后是250万个，6步之后是41亿个。平均一局棋大约走40回合80步，于是所有可能局面就有10的128次方个，这个数字远远多于已知宇宙世界的原子总数目(大约10的80次方)！
        纽维尔、西蒙和克里夫·肖发展的Alpha-beta算法可以从搜索树中剔除相当大的部分而不影响最后结果。它的基本思想是：如果有些招法将自己引入了很差的局面，这个招法的所有后续招法就都不用继续分析了。也就是说，如果有一个完美的局面评估方法，只要把最好的招法一个留下来就可以了，当然这种完美的评估方法不存在，不过只要有一个足够好的评估方法，那么也可以在每一层分析时只保留几个比较好的招法，这就大大减少了搜索法的负担。Alpha-beta算法和优秀人类棋手下棋时的思考过程已经非常接近。
       70年代时，曾经创造UNIX系统的计算机行业大腕肯·汤普森(Ken Thompson)开始进入电脑国际象棋领域，他和贝尔实验室的同事乔·康登（Joe Condon)一起决定建造一台专门用途的机器，使用了价值大约20,000美元的几百个芯片。他们把这台机器叫做Belle。它能够每秒搜索大约18万个局面,而当时的百万美元级超级电脑只能搜索5000个。Belle在比赛中可以搜索八至九层那么深，是第一台达到国际象棋大师级水平的计算机。从1980年到1983年它战胜了所有其它电脑，赢得了世界电脑国际象棋竞赛冠军，直到被价钱贵上千倍的克雷巨型机(Cray X-MPs)取代为止。Belle的成功，开创了开发国际象棋专用芯片来提高搜索速度的道路。
        汤普森的另一大贡献是他整理的残局库，他在80年代就开始生成和储存棋盘上剩四至五子的所有符合规则的残局。一个典型的五子残局，比如王双象对王单马，包含总数121万个局面。电脑使用这些残局数据库，可以把每个残局走得绝对完美，就象上帝一样。
       汤普森在80年代对搜索深度和棋力提高之间的关系做了非常有意义的试验。他让Belle象棋机自己跟自己下，但只有一方的搜索深度不断增加，结果是，根据胜负比率，平均每增加一个搜索深度可大约换算成200个国际象棋等级分。由此推论，可以计算出搜索深度达到十四层时，就达到了当时世界冠军卡斯帕罗夫的程度，即2800分的等级分。当时计算机行业专家的推测是：要与人类世界冠军争夺冠军，必须做一台每秒运算10亿次的电脑（对应于搜索到十四层的深度）。
       在评估局面方面，早期使用的是凭借经验制订的简单规则，后来这些规则逐渐增加，并逐渐加入人类优秀棋手评估棋局的思路。比如， 卡耐基梅隆大学的汉斯·贝利纳教授(Hans Berliner），他曾经是世界国际象棋通讯赛冠军，他领导开发了80年代很强的“Hitech”下棋机，在他的局面评估方法中，局面好坏由50多个因素决定（例如子力、位置、王的安全等等），每个因素则是一个变量，为每个变量赋予了一个加权系数，最后求和的大小就清晰的表明了当前局面的优劣。
        最终实现战胜人类国际象棋世界冠军之梦，取得人机大战胜利的是IBM的“深蓝”（DeepBlue)团队,核心是来自中国台湾的许峰雄、莫里·坎贝尔（Murray Cambell)和乔·赫内（Joe Hoane)。1985年起，许峰雄和莫里在卡耐基梅隆大学读研究生时，就是电脑下棋机“ChipTest”和“DeepThought”团队的核心成员，这两台下棋机在当时都处于电脑象棋行业的顶尖水平。许峰雄的导师孔祥重教授也是华人，是孔子的后代。许峰雄很有个性，有时会和权威发生冲突，高中开始就有个绰号叫“疯鸟”(Crazy Bird)，孔教授继承了他的祖先孔子“因才施教”的风范，宽容了“疯鸟”造成的一些麻烦，大力支持了许峰雄的追梦之旅。
       1989年起，加入IBM使得许峰雄和莫里得到了他们非常需要的高速计算机的资源和生产几百个象棋芯片的财力。IBM雄厚财力的另一大用途，是“深蓝”团队可以请到马克西姆·德卢基（Maxim Dlugy)、乔尔·本杰明（Joel Benjamin)、米格尔·伊列斯卡斯（Miguel Illescas)等多位国际象棋特级大师来负责与“深蓝”对弈和训练，这些训练的成果，多数都沉淀在“深蓝”不断优化的局面评估程序和开局库之中。
        又经过了近十年的艰苦努力，IBM “深蓝”下棋机最终在1997 年 5月3日至5 月 11 日的系列比赛中，以3.5:2.5(2胜1负3平）战胜了当时的国际象棋世界冠军卡斯帕罗夫，震惊了整个世界。当时用于比赛的IBM深蓝电脑，使用了30台IBM RS/6000工作站， 每台工作站有一个主频120M的Power2 CPU 加上16个VLSI 国际象棋专用芯片，所以深蓝的计算能力是30个CPU加480个象棋芯片，理论搜索速度每秒10亿个棋局，实际最大速度大约是每秒搜索2亿个棋局，很接近80年代时计算机专家的预测。
        许峰雄后来写了本书，叫《“深蓝”揭秘－－追寻人工智能圣杯之旅》，回忆了他12年磨一剑，坚持打造可以战胜所有人类选手的下棋机，最终取得成功的不凡经历，这本书很值得所有愿意长期追求远大梦想的人学习。
       书中透露的两个细节可以看到人类棋手在下棋能力以外的弱点。第一局卡斯帕罗夫取胜后，却一直疑惑为什么“深蓝”在第44步没有下看似更好的一招棋，他的助手们深入分析后得出结论，“深蓝”没下那招棋的原因是“它大概看到了20步之后的杀招”，如此高估“深蓝”的实力也许对卡斯帕罗夫后来的战斗增加了不少压力。整个系列比赛结束后，许峰雄才在书中透露“深蓝”是因为程序的隐错（Bug）才走出的那一招，当听到卡斯帕罗夫团队的分析时，他不禁笑出声来。另一个细节，此次比赛的总奖金是110万美元，胜方得70万美元，负方得40万美元，卡斯帕罗夫又对外另下了30万美元的赌注，因此，他承受了除了名誉以外还有来自金钱的巨大压力。最后一局，下了不到1小时，卡斯帕罗夫在19步后认输。
       有趣的是，作为“深蓝”的总设计师和芯片设计师，许峰雄更倾向于从工程角度看待“深蓝”的成功，他在书中的序言中说：“本书与科学发现无关，而是关于一项工程探索。从本质上讲，工程探索涉及生活中更丰富的层面。工程探索背后的技术思想首先要被发现出来，然后才能达到逻辑上的完善。这个发现可能来自运气或灵感，而探索的其他部分则需要付出辛勤的汗水和契而不舍的努力。……本书描述的是努力超越（尽管也许只是暂时的超越）世界上最佳人类棋手的弈棋水平的探索过程。”
       关于计算机下围棋，2002年，许峰雄写书时的判断是：“它实在太难了，以至于在未来20年中可能得不到解决。”这句话里“解决”的含义应该就是战胜围棋世界冠军，然而这个预言在2016年提前6年被强大的AlphaGo团队打破。
       AlphaGo这一款围棋人工智能程序，由谷歌（Google）旗下DeepMind公司开发。DeepMind公司创始人戴密斯·哈萨比斯（Demis Hassabis）生于1976年，父亲是希腊族塞浦路斯人，母亲是新加坡华人，在英国伦敦长大。他从小就是国际象棋和计算机双料神童，4岁开始下国际象棋，8岁自学编程，13岁获得国际象棋大师称号。2010年哈萨比斯创立专注于人工智能研发的DeepMind公司，目标是建立强大的通用学习算法，将技术应用于解决现实世界的难题。
      AlphaGo的开发团队核心包括大卫·席尔瓦（David Silver)、黄士杰（Aja Huang）、施恩·莱格（Shane Legg）和穆斯塔法·苏莱曼（Mustafa Suleyman）等人。AlphaGo围棋程序应用了近年来人工智能领域有重大突破的“深度学习”和“强化学习”等技术，加上Google公司强大的并行计算实力，可以说其“智能”水平已经远远超过当年的“深蓝”。

        根据DeepMind公司在《自然》杂志上发表的文章，AlphaGo这个系统主要由几个部分组成：
1. 策略网络（Policy Network），给定当前局面，预测下一步的走棋。对棋盘上的每个可下的点都给出了一个估计的分数，也就是围棋高手下到这个点的概率。评估一步棋的速度可达2毫秒左右。
2. 快速走子（Fast rollout），目标和1一样，但在适当牺牲走棋质量的条件下，速度要比1快1000倍。下一步棋的速度可达2微秒左右。
3. 估值网络（Value Network），给定当前局面，估计是白胜还是黑胜，给出输赢的概率。
4. 蒙特卡罗树搜索（Monte Carlo Tree Search，MCTS)，把以上这三个部分连起来，形成一个完整的系统。
        简约地说一下AlphaGo的“训练”过程，AlphaGo团队首先利用几万局专业棋手对局的棋谱来训练系统，得到初步的“策略网络”和“快速走子”。训练“策略网络”时，采用“深度学习”算法，基于全局特征和深度卷积网络(CNN)来训练，其主要作用是给定当前盘面状态作为输入，输出下一步棋在棋盘其它空地上的落子概率。“快速走子”则基于局部特征和线性模型来训练。完成这一步后，AlphaGo已经初步模拟了人类专业棋手的“棋感”。接下来，AlphaGo采用左右互搏的模式，不同版本的AlphaGo相互之间下了3000万盘棋，利用人工智能中的“深度增强学习”算法，利用每盘棋的胜负来学习，不断优化和升级“策略网络”，同时建立了一个可以对当前局面估计白棋和黑棋胜率的“估值网络”。根据AlphaGo团队的数据，对比围棋专业选手的下法，“策略网络”用2毫秒能达到57%的准确率，“快速走子”用2微秒能达到24.2%的走子准确率，据估计，单机上采用“快速走子”的下棋程序，已经具备了围棋三段左右的水平。而“估值网络”对胜负的判断力已经远超所有人类棋手。
       实际对局时，AlphaGo通过“蒙特卡罗树搜索”来管理整个对弈的搜索过程。首先，通过“策略网络”，AlphaGo可以优先搜索本方最有可能落子的点（通常低于10个）。对每种可能，AlphaGo可以通过“估值网络”评估胜率，同时，可以利用“快速走子”走到结局，通过结局的胜负来判断局势的优劣，综合这两种判断的评分再进一步优化“策略网络”的判断，分析需要更进一步展开搜索和演算的局面。综合这几种工具，辅以超级强大的并行运算能力，AlphaGo在推演棋局变化和寻找妙招方面的能力，已经远超人类棋手。根据资料，最高配置的AlphaGo分布式版本，配置了1920个 CPU和280个 GPU，同时可以跑64个搜索线程，这样的计算速度就好像有几十个九段高手同时在想棋，还有几十个三段棋手帮着把一些难以判断的局面直接下到最后，拿出结论，某一位人类棋手要与对抗，确实难以企及。
       当然，目前版本的AlphaGo也并不完美。在人机大战的第四局，0:3失利后为荣誉而战的李世石长考25分钟后，祭出了白78“挖”的妙手，这一手棋后来被新闻界称为“神之一手”，AlphaGo在李世石的绝地反击下陷入混乱，下出了不少“昏招”，最后中盘认输。 据DeepMind创始人哈萨比斯赛后Twitter称：“李世石下出白78后，AlphaGo自我感觉良好，在程序的‘估值网络’中，误以为胜率达到70%，在第79手犯了错，直到第87手才反应过来它错了。”
        围棋世界冠军古力与AlphaGo对弈以后写下了这么一句话：“人类与人工智能共同探索围棋世界的大幕即将拉开。”我相信，AlphaGo所代表的人工智能技术将在更多的领域辅助人类解决更多的难题，而更多中国血统的天才，将像许峰雄、戴密斯·哈萨比斯、黄士杰那样，在人工智能领域取得辉煌的成就。