智东西(公众号:zhidxcom)
 | 王

智东西4月29日消息,美国南卡罗来纳大学安·约翰逊科学与技术与社会研究所的联合主任、历史系副教授Allison Marsh,近日发表了一篇文章,向我们讲述了一个计算机如何成为国际象棋大师的故事。

国际象棋是一种复杂的策略游戏,两个对手之间没有任何隐藏的信息,双方在一开始就知道对方所有的潜在动作。

每一回合,玩家都会交流他们的意图,并试图预测可能的对策。提前预想几步行动的能力是获胜的秘诀,数学家和逻辑学家一直以来都认为这种能力很有趣。

接下来我们根据Allison Marsh的讲述一起来了解一下这段计算机国际象棋大师的历史。

一、计算机国际象棋大师的缔造者是如何结识对方的?

第一台计算机国际象棋大师的前世今生

▲Ken Thompson(坐)和Joe Condon(站)

在数字计算出现之前,虽然已经出现了一些早期的机械国际象棋游戏机,但这种机械化仍然只是一个假设。20世纪40年代初,德国计算机先驱Konrad Zuse攻读博士学位时,把计算机国际象棋作为他正在开发的名为plankalk l的高级语言的例子。

然而,由于第二次世界大战,他的作品直到1972年才出版。由于Konrad Zuse的工作不为英国和美国的工程师所知,所以数学家Norbert Wiener、Alan Turing,尤其是Claude Shannon(1950年发表论文“为计算机编程”玩国际象棋)被视为了为思考计算机国际象棋铺平道路的人。

从20世纪70年代初开始,贝尔实验室的研究人员Ken Thompson和Joe Condon开发了一种会下国际象棋的计算机Belle。

Ken Thompson是Unix操作系统的共同创造者,他也是国际象棋的忠实爱好者。他在国际象棋世界冠军Bobby Fischer的时代长大,青年时期参加过国际象棋比赛。1966年,他在加州大学伯克利分校获得电子工程和计算机科学硕士学位后,加入了贝尔实验室。

Joe Condon是贝尔实验室冶金部门的一名物理学家。他的研究有助于理解金属的电子能带结构,他的兴趣随着数字计算的兴起而发展。

Ken Thompson是在与Unix合作伙伴Dennis Ritchie开始合作开发一款名为《太空旅行》的游戏时认识Joe Condon的,当时他们使用的是Joe Condon负责的PDP-7小型计算机。Ken Thompson和Joe Condon继续合作开展了许多项目,包括推广使用C语言作为AT&T交换系统的语言。

二、Belle成为计算机国际象棋大师的艰辛历程

Belle是从一种软件方法开始的,Ken Thompson在早期的Unix手册中编写了一个象棋程序示例。但在Joe Condon加入这个团队后,这个程序变成了一台混合计算机国际象棋机器,Ken Thompson负责编程,Joe Condon负责硬件设计。

Belle由三个主要部分组成: 一个移动生成器,一个板评估器,和一个移位表。

移动生成器识别受攻击的最高价值块和最低价值块,并根据这些信息对潜在移动进行排序。评估器能注意到国王在比赛不同阶段的位置及其相对安全性。移位表包含一个潜在移动的内存缓存,这使得计算更有效率。

Belle采用了蛮力的方法,它研究了玩家在当前棋盘布局下的所有可能的棋步,然后考虑了对手可以做出的所有棋步。

在国际象棋中,双方跟完成一步叫做一个回合。最初,Belle可以计算四层深度的移动。1978年,当Belle在美国计算机协会的北美计算机国际象棋锦标赛上首次亮相时,它的搜索深度达到了8层,Belle之后赢得了四次冠军。1983年,它成为了第一台获得国际象棋“大师”称号的计算机。

当计算机象棋程序设计人员让系统与人类竞争对手对抗时,这些程序经常受到敌意对待,因为有人怀疑程序中有潜在的作弊行为。

所以,当Ken Thompson想要在当地的国际象棋俱乐部测试Belle时,他煞费苦心地建立起了人际关系,他向对手提供了一份计算机分析比赛结果的打印件,并承诺如果Belle人机混合锦标赛中获胜,他会拒绝奖金,将奖金提供给下一个参加比赛的人。因此,Belle每周都可以去新泽西州韦斯特菲尔德的韦斯特菲尔德国际象棋俱乐部下棋,持续了差不多10年。

和以人为中心的国际象棋比赛相比,计算机国际象棋比赛可能是一件嘈杂的事情,因为人们会讨论和辩论不同的算法和游戏策略。

Ken Thompson在2005年的口述历史中,提到了这些往事。每当比赛结束后,他都会精力充沛地回到实验室,准备解决一个新问题。

对于一台电脑来说,Belle过着丰富多彩的生活,甚至一度成为公司恶作剧的对象。1978年的一天,贝尔实验室的计算机科学家、Unix团队的另一名成员Mike Lesk,从AT&T(美国电话电报公司)董事长John d. deButts那里偷了一些信笺,并写了一份假备忘录,要求暂停使用“T”Belle计算机项目。

虚假备忘录的核心是一个哲学问题: 人和电脑之间的游戏是一种交流形式,还是一种数据处理形式?该备忘录称Belle是后者,因此它违反了1956年禁止该公司从事计算机业务的反垄断决定。尽管如此,AT&T的高管们从来没有强迫Belle的创造者停止在工作中玩游戏或发明游戏,这可能是因为这些娱乐活动带来了经济上富有成效的研究。2001年,Dennis Ritchie在《国际计算机游戏协会杂志》特刊上发表了一篇文章,专门报道Ken Thompson对计算机国际象棋的贡献。

三、Belle未成行的“苏联之旅”

20世纪80年代初,苏联电气工程师、计算机科学家、国际象棋大师Mikhail Botvinnik邀请Ken Thompson将Belle带到莫斯科进行一系列演示活动。他离开纽约肯尼迪国际机场后,却发现Belle没有被带上飞机上。

Ken Thompson在莫斯科待了好几天之后才知道Belle的命运。贝尔实验室的保安人员正在肯尼迪国际机场的机场进行兼职,碰巧看到一个标有“计算机”的贝尔实验室的盒子,被绳子绑在海关区域。警卫通知了他在贝尔实验室的朋友,最终Joe Condon得到了消息,他立即给Ken Thompson打了电话。

Joe Condon警告Ken Thompson:“如果不扔掉给Belle带来的备用零件,你回来的时候可能会因为走私电脑到俄罗斯而被逮捕。”

过分热心的美国海关人员发现了Ken Thompson装Belle的盒子并没收了它,但从未通知他或贝尔实验室。

苏联的邀请方认为这是美国政府的问题,当Ken Thompson与他们会面,向他们解释Belle已经被扣留时,苏联国际象棋俱乐部的负责人指出,Ayatollah Khomeini(前伊朗国家领导人)在伊朗宣布国际象棋非法是因为它违背了上帝。并向Ken Thompson问到:“你认为里根这样做是为了在美国取缔国际象棋吗?”

回到美国后,Ken Thompson采纳了Joe Condon的建议,将Belle的零部丢在了德国。回到家后,他没有因为走私或其他任何罪名被逮捕。

但当他试图在肯尼迪机场找回Belle时,却被告知违反了《出口法案》,因为Belle那台老旧过时的惠普显示器被列入了禁售物品清单。贝尔实验室支付了罚款,最终才领回了Belle。

四、计算机技术进步,Belle退出历史舞台

在Belle统治计算机国际象棋世界几年后,它的明星光环开始褪色,因为有更多功能强大的计算机出现了。

第一台计算机国际象棋大师的前世今生

▲深蓝在与世界冠军Garry Kasparov的初赛中获胜

其中最主要的是IBM的深蓝,1996年,深蓝在与世界冠军Garry Kasparov的初赛中获胜,引起了国际社会的关注。虽然最终的比赛获胜者仍然是Garry Kasparov,但深蓝为参与复赛奠定了基础。

第二年,经过大规模升级后,深蓝击败了Garry Kasparov,成为第一台在规定时间控制的比赛中击败人类世界冠军的计算机。

结语:Belle最终成为了计算机史上的文物

Allison Marsh表示,是摄影师Peter Adams为Ken Thompson和他的许多贝尔实验室同事拍摄的肖像系列片“开源的面孔”,引起了他对贝尔实验室的注意。

在这个系列片中,贝尔实验室的企业档案管理员Ed Eckert允许他拍摄了一些与Unix研究实验室相关的文物。

虽然Peter Adams把Belle放在了他拍摄的愿望清单上,但他认为Belle肯定已经被放进了博物馆里,应该无缘见到了。但令他吃惊的是,他得知Belle仍然在新泽西州默里山的诺基亚贝尔实验室。

Peter Adams在给Allison Marsh的邮件中写道:“它仍然在它所演奏的史诗般的国际象棋游戏中磨损了。”

原文来自:IEEE Spectrum