计算机象棋的历史与发展

　　早在发明计算机之前，人们就开始设想如何让机器下棋。 十八世纪的欧洲对机械原理的认识已相当深入，并拥有世界上最发达的机械制造业。 为后人留下了多例关于设计和制造机械弈棋机失败的记录。其中最有趣也有最出名的一台弈棋机是巴朗.冯.开普仑（Baron Von Kempelen）发明的，叫做 Turk（土耳其人）。这台弈棋机曾在欧洲各国巡回表演，并战胜过拿破仑。机器外观像一个大箱子， 在其顶端有棋盘和棋子。 每次对局表演前， 组织者都将箱口打开，向观众展示箱子内部的众多齿轮，杠杆和复杂的轴系。 看了机器内部的观众开始相信 Turk 是纯粹的机械装置， 并随后被它的精湛棋艺所折服。 该机器在与拿破仑对局时，不到 20 回合便将其杀得大败。恼羞成怒的拿破仑当众挥袖将盘面上所剩棋子扫落到地上，而后扬长而去。这盘传奇对局的对局记录一直流传至今。此弈棋机在退役之前，几次易主，并曾在美国的各大城市进行对局表演。当时就有人怀疑此弈棋机是假的，其中包括科学家富兰克林。 但是人们渴望技术进步的心理和组织者的商业宣传淹没了这些疑议。 直到两个小男孩在一个炎热夏天看到从弈棋机的箱子里钻出一矮人并将此事告述给一记者，人们才注意到美国的一名矮个子大师在此期间一直未露面。 后来此弈棋机毁于费城华人文化博物馆的一次大火中。

　　尽管上历史上有人发明过机械电子简单残局装置， 机器弈棋的重大突破应归属于科劳德.萨年(Claude Shannon)在二战期间工作。 他在 1950 年发表在荷兰著名的<<哲学>>杂志上的一篇文章奠定了现代计算机象棋的基础。

　　为什么研究计算机象棋呢？ 许多学者认为，对于人工智能研究而言， 象棋相当于遗传学研究中的果蝇的重要作用。人们普遍认为下棋是一项智力活动。它具有下列基本特征：

1. 规则简单明确，成功与失败的判定标准简单，不包含任何机会或偶然性。

2. 问题的状态(即局面)数量在数学意义上是有限的。

3. 问题的解决在认识意义上不需要过多的知识。

　　上述特点吸引了许多领域的学者， 将象棋(或国际象棋)作为他们的研究对象。

　　半个世纪不同学科的研究结果表明， 除了第一条依然完全成立外， 对其余两点又有新的认识。

　　国际象棋每个局面平均有 38 种合法着法， 笔者的统计分析表明中国象棋每个局面平均有 42 种合法着法。如果想将这两种古老的游戏完全彻底地解决则至少要分别生成和分析 38^40 和 42^40 (42 的 40 次方)个局面。 如此巨大数量, 目前仅仅有数学意义。 人类目前可知的宇宙都不需要这么大的尺度去衡量。 目前世界上最快的计算机也得花费许多世纪。因此历史上第一个计算机国际象棋程序就采用了与人类棋手相似的拆解变化的方法， 计算机科学上称之为搜索。 显然计算机的棋力在很大程度上取决于它的搜索深度，正如棋谚所云，多算为胜。

　　然而, 博弈是一种实时过程, 无论人类棋手还是计算机程序都面临着相同的时间压力。 计算出的着法质量必需能够补偿为此所耗费的时间。 因此, 对于复杂局面, 机器和人一样， 不得不在搜索一定深度后在某些没有简单结论(胜，负， 和)的局面停下来, 并对此局面加以判断。 象棋大师们有很多词汇用来描述局面的优劣, 如均势，红方大优和各有千秋等等。计算机象棋往往采用经验性定量分析的方法来判定局面的优劣程度， 也有采用模糊数学方法的。 这种用来判定局面的优劣程度的方法叫做评价函数。 评价函数可以包括用来描述局面的很多特征。 例如在作者开发的“七星大师”象棋程序的评价函数中包含子力平衡，子力的机动性， 将（帅）的安全性， 子力位置和子力配置等多项常见的局面特征， 以及一些其它不常见的局面知识。从棋手的角度来看，评价函数相当于程序所掌握的象棋知识。这些知识无疑是经验性的， 无法保证其在任何情况下都正确。例如让对手打空头炮在绝大多数情况下都是不利的，但当我们学习大师们的对局记录时就会发现一些违背此经验知识并且成功的特例。另一方面， 这些特征之间的关系, 即参数， 也是难于精确定量的。战胜过卡斯帕罗夫的深蓝有近千个此类参数。 这些参数往往是程序按机器学习方法经多次与强对手对弈并自动学习后确定的。然而, 包括深蓝, 弈棋机所拥有的知识数量也远不及其人类对手。

　　简略描述了计算机如何下棋，现在有必要回顾一下心理学家们是如何研究和认识优秀棋手和普通棋手水平差异的。 研究的对象是国际象棋特级大师，大师，俱乐部棋手和普通棋手。我认为这些研究结论同样适用于中国象棋和棋手。十九世纪末荷兰和法国学者就发现， 大师们在下盲棋时并不是他们脑中有生动形象的棋盘， 而是通过诸如子力关系等抽象概念来记住局面。 心理学家还发现， 大师们作为一个群体其平均智商和记忆力都和普通人群无任何明显差异， 并且大师的信息处理方式和弱手属同一类型。 本世纪三十和四十年代苏联和美国的实验结果进一步证实，分析过程本身不是决定棋力的关键因素。在一个实验中只给棋手几秒种时间观察生疏的实战局面，然后再让他们靠记忆将局面重新摆出来。 大师几乎可以回忆出每个子的正确位置，俱乐部棋手能记住一半, 而初学者只能记住三分之一。 而在另一个实验中每个棋子都是完全随机放置的，结果上述记忆能力的差别完全消失了。这些实验结果表明大师的超人记忆力是象棋特指的，而不是一般性能力。高级棋手可以识别大量的子力组合， 而这些组合可作为知觉枝干。大师在很短时间内可以记住 4 或 5 个枝干而不是 4 或 5 个棋子。 而一个枝干一般包含三或四个棋子。这样就不难理解为什么大师对有意义局面的超群记忆能力了。 进一步来说， 棋力取决于通过学习获得的感知能力。正像儿童上学时逐步建立起他自己的英语词汇库一样。开始时，他只能一个字母一个字母地读每一个单词， 并且还经常不理解词义。 初学者以相同的方式一个棋子一个棋子地去感知局面，并且不能识别常见子力组合的含义。成年人以词或短语(枝干)作单位来阅读并拥有很大的词库。 与此相类似， 熟练棋手可以识别大量的棋子组合方式(枝干)并且理解其整体意义以及其中每个子的作用。因此， 人类棋手的水平是建立在两种通过学习获得的高度发达的能力基础之上的，即模式识别能力和高速信息抽取能力。实际上，这两种能力不仅对于博弈至关重要，对其他许多领域都同样重要。

　　那么, 计算机是不是可以模仿特级大师来下棋呢？ 这方面有很多的尝试，但都不很成功。 深蓝就不是这种方式。 模式识别和按概念高速抽取信息至今还吸引着世界各地的学者, 并在一些领域取得了成功。 模式识别在计算机象棋上也有很多应用，但是机器的模式识别能力较大师相差甚远。 部分原因在于， 现代计算机的结构更适合于复杂计算， 而不太适合于模式识别和按概念高速抽取信息。

　　然而， 目前计算机为什么能战胜特级大师，甚至卡斯帕罗夫呢？ 概括地说，这归功于近半个世纪的研究积累和计算机硬件的发展。许多研究人员创造性的工作使得算法日趋完善和高效。 1997年的深蓝要比1950年第一台能下国际象棋的 IBM 704计算机快一百万倍。 尽管深蓝的知识要比其它国际象棋程序高出很多，然而，较其唯一的对手卡斯帕罗夫还相差甚远。这里所说的唯一并不意味着其它几位超一流特级大师面对深蓝毫无希望。 IBM 似乎只对卡斯帕罗夫这位棋界英雄感兴趣。先进的算法和强大的硬件祢补了知识的不足。 正如卡斯帕罗夫在赛后报告中所说的，深蓝考虑 15 分钟所看到的变化恐怕比世界上所有棋手终生分析的变化还要多。毫无疑问，深蓝在这 15 分钟内所考虑的绝大多数变化对人来说都是非常滑稽可笑的，不然的话，深蓝根本不需要每秒钟解析 2 亿个局面的能力。面对复杂局面时， 人类棋手依靠所掌握的知识， 往往可以迅速确定近期目标和远期目标。 熟练棋手或大师只对符合这些目标的着法进行变化分析。七十年代以前， 国际象棋程序都采用这种经济合理的局面分析方式， 每个局面只考虑少于 7 种可能着法。然而，程序在对弈时会经常将最佳着法排除在 7 种可能着法之外， 使得随后的分析变得毫无意义。当然，棋手，既使是特级大师， 也会犯此类错误， 但频率和严重程度要比此类程序低得多。深蓝这种蛮力搜索方式早在七十年代中期就变成了计算机象棋的主流。蛮力搜索解决了选择分析的盲点问题， 但代价是严重降低了分析深度， 往往要求非常高效的算法和强大的硬件支持。 知识工程努力的结果是机器经常发现连大师都会忽略的好棋。目前在微机上仍有棋力很强（大师以上）的选择性程序。知识和速度是计算机象棋永恒的主题。

　　实际上目前在微机上已有几个国际象棋程序达到了强大师和弱特大的水平（等级分2500 至 2600）。苏珊布尔加近年来很少参加比赛。当中央电视台体育记者问及她是如何保持水平以迎接今年谢军的挑战时， 她回答说， 经常和机器下棋。显然，她指的是个人计算机， 女子世界冠军的收入距离巨型机还很远。可以预见在不久的将来微机国际象棋程序就可以全面和强特大抗衡。 实际上， 几年前卡斯帕罗夫就曾输给过不只一个微机程序。

　　计算机中国象棋的研究历史较短， 文献和报道均很少。 台湾学者在七十年代末开始了计算机中国象棋的研究工作， 并在八十年代初开发和出版了苹果机（6502）和IBM PC 机 (8088) 象棋程序。 1983 年南开大学开发了残局程序，并在随后的几年里开发了全局程序。 八十年代中期， 香港也出版了象棋程序。这一时期的象棋程序的棋力很低。 现在还能回想起第一次在实验室里和 6502 象棋程序对弈时的兴奋心情，尽管程序的表现很难让我称其为初学者。1992 年台湾光谱公司出版的 "象棋大师 III"，即将族， 仍然是目前最强的商品程序。 尽管近两年有其它公司的产品已和爱好者见面， 但棋力与将族相比， 差距是很明显的。将族可以打败很多初学者。1990 年一位来自台湾的同事赠送我一套将族的早期版本，那时我就发现将族有时会走出令人尊重的棋来。

　　从棋手的角度看， 可将目前的计算机象棋程序分成三个部分， 即开局库，引擎和残局库。程序的棋力是这三部分性能的综合反映， 其中最为重要的是引擎。 开局库负责管理开局变化的选择。 程序会随机地选择不同的变化， 这会使人感到机器始终是一位有趣的对手。 开局库的另一个重要作用是可以很大程度地使机器避免战略性错误。开局中许多选择无疑是战略性的， 其结果往往需要很多回合之后才能表现出来。 和人类棋手一样，一旦脱谱之后(或程序不认可谱着)， 就要分析和思考了，也就是说，程序需要启动引擎了。引擎是计算机象棋程序的核心， 所有未知的局面都由它来处理。引擎中包括我们以前所提及的分析(搜索)和评价过程。 随着中局的子力交换的逐步增多，残局库的作用就变得越来越重要了。 现代的残局库是完备知识数据库， 如果库中有某类残局， 例如马对单象， 则库中存有任何一种可能棋形的结果。 这不同于棋手所掌握的残棋要诀。 如果某个棋形（局面）可胜则程序可查到将死对方所需要的最少着数。 这种残局库是用专用引擎经过长时间计算（几小时甚至数周）预先生成的。目前残局库所含盖的残局种类是有限的。 假如有 32 子残局库，那么象棋就被完全解决了。遗憾的是， 在我们可见的未来，这都是不可能的。对于国际象棋， 高级程序一般带有 5 子残局库。 也有人在研究 6 子残局库， 但此类残局需要大于 10G 的硬盘空间。 完备知识残局库增加了人对残局的认识， 某些胜和定式被证明是不正确的。一些国际象棋特级大师在面对计算机时甚至无法兑现一些必胜残局，机器奇怪的防御方案有时会弄得大师超出 50 步自然限着。至于中国象棋完备知识残局库， 作者未见过此方面的研究文献或报道， 也未见任何一程序中含有此类残局库。 上述三部分对于程序来说，只有引擎是必需的。这是正因为还没有任何一种引擎和硬件组合可以穷尽象棋这种古老的战略游戏。很多程序不支持残局库， 甚至一些程序不含开局库。 除了上述三部分外，实际的象棋程序还有用户界面部分。 用户界面一般用图形显示当前局面和计时钟，负责处理用户的走子信息和其它命令。用户可定对局时限，棋力水平，和其他一些参数(例如蔑视对手系数)。用户界面还负责管理对局谱保存和打印等项杂务。

　　笔者自 1987 年以来一直跟踪着计算机象棋研究的进展，并开始着手于自己的计算机中国象棋研究。1989 年和 1992 年曾两度尝试象棋软件的编写, 但是，均因时间和难度的关系而放弃。1996年底， 重新制订了"七星大师"个人项目计划，并开始实施。象棋引擎已基本完成， 目前的工作集中在开局库和测试， 以及用户界面完善上。七星大师在引擎测试过程中曾战胜过大师和特级大师。七星大师目前具有较高的战术水平， 实战过程中它几乎兑现了所有对手留给它的战术组合机会。 程序通过复杂实战中局和排局测试时也有很好的表现。 以<<棋艺>> 98 年 12 期 "龙门救险"和 "双燕单飞"为例, 程序仅分别用 3 秒 和 30 秒就给出了正确答案。然而, 七星大师目前在战略上还有弱点。完成开局库后， 七星大师犯战略性错误的可能性会很大程度地得到降低。 尽管还有其他改善方法， 避免战略失误仍然是目前微机上高级象棋(包括国际象棋)程序需要逐步克服的研究课题。

　　讨论计算机象棋， 不能不谈网络象棋。无疑网络象棋促进了计算机象棋的发展。象棋网上有各种水平和不同风格的对手，并且不受时间和地域的限制。七星大师和许多高手的对局，特别是与大师们的对局， 都使笔者获益非浅。我的一个网名叫“深蓝”的棋友甚至帮助我发现了一个隐藏在程序中达半年之久的虫子(bug)。有条件的棋迷不可能抗拒网络对弈的诱惑。 有很多网站提供免费网络象棋服务。由于网络象棋仍处于发展阶段， 各个免费网站可谓是各有所长。 作者经常去"中国象棋网"下棋, 也时常在其 BBS 上与其他棋友讨论象棋。我在这里介绍中国象棋网是因为，那里经常有大师和业余高手光顾。金松和薛文强等青年大师是棋网的长客。刘星大师参加了两次网络象棋比赛。吕钦和许银川特级大师和广大棋友以车轮战方式共度新年。互连网上还有许多免费象棋资源, 感兴趣的棋友可使用常见的中文搜索引擎查找到。