快捷搜索:

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

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

智东西(公众号: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年的口述历史中,提到了这些往事。每当比赛结束后,他都会精力充沛地回到实验室,准备解决一个新问题。

您可能还会对下面的文章感兴趣: