国际象棋程序的逐步演进

回顾人工智能的发展史，棋类一直就是一个热门领域，原因很简单，因为下棋被称为智力竞技运动，所以通过棋类的胜负和等级分，可以很好地来对比和测量人工智能系统的智能水平。

伟大的香农，最早提出了利用计算机编写国际象棋程序的设想，并于1950年发表了论文《为计算机编程下国际象棋》（Programming a computer for playing chess），其内容奠定了现代弈棋机的基础。1956年，他在洛斯阿拉莫斯的MANIAC计算机上实现了一个国际象棋的下棋程序。在一篇关于计算机象棋的早期论文中，纽厄尔、西蒙和约翰·肖（John Cliff Shaw）提出：“如果一个人能够设计出一台成功的弈棋机，他似乎就渗入了人类智力活动的核心。”受这些大师们的激励，无数的计算机专业人士、国际象棋棋手和各行业的业余爱好者开始研究和开发一代又一代的下棋系统，有些人追求胜负和奖金，有些人把下棋系统作为实验工具，研究人类智能的工作原理。图2.3是电脑象棋界的一次聚会，左四为香农，左三为肯·汤普森（Ken Thompson）。

图2.3 电脑象棋界的一次聚会

人类思考棋类问题的核心智慧就是找到妙招，而找到妙招的关键就是推算出若干步之内无论对方如何应对，本方都处于局面变好的态势。转换到国际象棋程序编程，核心都必须有两部分：博弈搜索和局面评估。

博弈搜索是一个招法（下一步棋）向着后续招法分叉，形成了一棵树形结构，称为博弈树。最简单的搜索法称为暴力搜索法（Brute force）或者A（Alpha、阿尔法）方法，这种方法全面生成所有可能的招法，并选择最优的一个，也就是尽可能对博弈树穷尽搜索。另一种策略称为B（Beta、贝塔）方法，基本思想是剔除某些树枝。

暴力搜索法程序遇到的主要难题是博弈树所包含的局面数量实在太多太多了。国际象棋每个局面平均有40步符合规则的着法。如果你对每步着法都考虑应着就会遇到40×40=1600个局面。而4步之后是250万个，6步之后是41亿个。平均一局棋大约走40回合80步，于是所有可能局面就有10的128次方个，这个数字远远多于已知宇宙世界的原子总数目（大约10的80次方）！

纽厄尔、西蒙和约翰·肖发展的Alpha-Beta算法可以从搜索树中剔除相当大的部分而不影响最后结果。它的基本思想是，如果有些着法将自己引入了很差的局面，这个着法的所有后续着法就都不用继续分析了。也就是说，如果有一个完美的局面评估方法，只要把最好的一个着法留下来就可以了。当然这种完美的评估方法不存在，不过只要有一个足够好的评估方法，那么也可以在每一层分析时只保留几个比较好的着法，这就大大减少了搜索法的负担。Alpha-Beta算法和优秀人类棋手下棋时的思考过程已经非常接近了。

20世纪70年代，曾经创造UNIX系统的计算机行业大腕肯·汤普森开始进入电脑国际象棋领域，他和贝尔实验室的同事乔·康登（Joe Condon）一起决定建造一台专门用于下国际象棋的机器，他们把这台机器叫作Belle，使用了价值大约2万美元的几百个芯片。Belle能够每秒搜索大约18万个局面，而当时的百万美元级超级电脑只能搜索5000个。Belle在比赛中可以搜索八至九层那么深，是第一台达到国际象棋大师级水平的计算机。从1980年到1983年它战胜了所有其他电脑，赢得了世界电脑国际象棋竞赛冠军，直到被价钱贵上千倍的克雷巨型机（Cray X-MPs）取代。Belle的成功，开创了通过研发国际象棋专用芯片来提高搜索速度的道路。

汤普森的另一大贡献是他整理的残局库，他在20世纪80年代就开始生成和储存棋盘上剩四至五子的所有符合规则的残局。一个典型的五子残局，比如王双象对王单马，包含总数121万个局面。电脑使用这些残局数据库，可以把每个残局走得绝对完美，就像上帝一样。

汤普森在20世纪80年代对搜索深度和棋力提高之间的关系做了非常有意义的试验。他让Belle象棋机自己跟自己下，但只有一方的搜索深度不断增加，结果是，根据胜负比率，平均每增加一个搜索深度可大约换算成200个国际象棋等级分。由此推论，可以计算出搜索深度达到14层时，就达到了当时世界冠军卡斯帕罗夫的水平，即2800分的等级分。当时计算机行业专家的推测是：要与人类世界冠军争夺冠军，必须做一台每秒运算10亿次的电脑（对应于搜索到14层的深度）。

在评估局面方面，早期使用的是凭借经验制定的简单规则，后来这些规则逐渐增加，并逐渐加入人类优秀棋手评估棋局的思路。比如，卡内基梅隆大学的汉斯·伯利纳（Hans Berliner）教授，他曾经是世界国际象棋通讯赛冠军，他领导开发了20世纪80年代很强的“Hitech”下棋机，在他的局面评估方法中，局面好坏由50多个因素决定（例如子力、位置、王的安全等），每个因素则是一个变量，为每个变量赋予了一个加权系数，最后加权求和的大小就清晰地表明了当前局面的优劣。