spring63的个人博客分享 http://blog.sciencenet.cn/u/spring63

博文

人工智能发展史:计算机弈棋 精选

已有 4527 次阅读 2020-5-15 09:04 |个人分类:科学史|系统分类:海外观察

在人工智能发展历程中,计算机弈棋是个亮点。艾伦·图灵在20世纪40年代就已经研究过这个问题,1956年达特茅斯研讨会(通常被认为是人工智能的开端)的多位与会者,也热衷于研究计算机弈棋今天,像DeepMindAlphaGoAlphaZero这样的程序,使用人工神经网络掌握了更难的游戏,更被认为是人工智能技术进步的里程碑。这里回顾计算机弈棋发展历程。

机械土耳其人

1770年,出现世界上第一台自封的国际象棋机器,即著名的机械土耳其人。据说,它是由一名外交官和发明家沃尔夫冈·冯·肯普伦创造的。他也是一位早期的企业家,其动机还不清楚。这台国际象棋机器——一个大盒子,上面放着一个国际象棋棋盘,国际象棋棋子通过某种未知的力量来回应人类对手,似乎是通过藏在棋盘下面盒子里的神秘机器。肯普伦向奥匈帝国的玛丽亚·特里萨女皇展示了他的土耳其人。被机械盒子看似聪明的表演所迷惑,很快在欧洲引起轰动,拿破仑·波拿巴、本杰明·富兰克林和伟大的数学家(也是现代计算的鼻祖之一)查尔斯·巴贝奇都受骗了。后来肯普伦的骗局被揭穿,原来机器外壳里面藏了一位西洋象棋大师。

image.png

托雷斯·奎韦多

1912年,西班牙人莱昂纳多·托雷斯·奎韦多的国际象棋自动机,被认为是世界上第一台真的象棋机器。两年后,托雷斯·奎韦多在巴黎索邦大学机器实验室展示了他的机电式象棋机。最终游戏机器能够用车和国王,将死人类对手的国王。1951年,在巴黎计算机会议上诺伯特·维纳曾经与奎韦多的第二种型号象棋机器对弈。在1958年布鲁塞尔世界博览会上奥地利计算机科学家海因茨·泽曼尼克也曾与这种国际象棋机器比赛,他把它描述为一台远远领先于时代的历史自动机。据泽曼尼克称,托雷斯·奎韦多为游戏设计了一个非常聪明的六部分算法,该算法使用杠杆、齿轮和继电器来实现。

托雷斯·奎韦多(Torres Quevedo1852.12.28-1936.12.18)是十九世纪末二十世纪初的西班牙土木工程师、数学家和发明家。除了布鲁德勒的博文介绍的象棋自动机以外,奎韦多在1904年制造了遥控三轮车,是世界上第一辆无人驾驶地面车辆。他还在1914年提出了浮点运算作为计算机处理引擎的概念,直到1938年,第一个使用二进制浮点数的康拉德·楚泽的Z1计算机才正式诞生。的确,奎韦多的这些伟大的探索,领先于其所处的时代几十年。

image.png

托雷斯·奎韦多(左)和他的第二种型号的象棋自动机(右)

艾伦·图灵、克劳德·香农和约翰·麦卡锡

在土耳其人闹剧上演180年后,机器大脑——电子计算机诞生了。正是在这种背景下,艾伦·图灵、约翰··诺依曼、克劳德·香农和其他计算机先驱们,终于成功地建造了一个真正的机械土耳其人。这一次,机器外壳里面根本没有人,而是电子计算机的大脑。

艾伦·图灵首先用简单机器的草图解释了他的机器大脑计算理论,称为“图灵机”,根据这个蓝图,图灵和英国、美国的其他人,建造了最初的电子计算机。此外,德国人康拉德·楚泽在1941年建造了世界上第一台全功能可编程计算机Z3计算机,在1945年设计了编程语言Plankalkuel并设计了世界上第一个象棋程序

图灵设计计算机的最初动力是在战争中取胜(很像下棋的动力): 纳粹的战争机器使用一种看似牢不可破的代码,被称为英格玛谜),来交流他们的潜艇的目标位置,而英国输得很惨。图灵的工作是破解英格玛密码;他的方法是首先建造一台计算机器,然后让它破解代码。被许多历史学家称为“计算机科学之父”的图灵,在他完善了BUMB(“炸弹”)——一种被英国情报部门用来破译二战期间使用德国英格玛机器发送的加密信息的机械装置——后,一举成名。图灵的成就被认为是有助于这场战争的转折点。

image.png

用于破译英格玛密码的BUMB(“炸弹”)计算机

冯·诺伊曼是著名的普林斯顿高等研究院的成员,他帮助开发了一种电子计算机(首先是ENIAC),用于战争的另一个中心目的:分析核爆炸。正是在这种背景下,图灵、冯·诺依曼和克劳德·香农以现代的姿态提出了一个古老的问题(后来被约翰·麦卡锡称为人工智能”):机器能像人一样思考吗?这个问题的答案——机器智能的问题——从一开始就与机器是否能被用来下棋的问题联系在一起。

图灵继续他在计算机科学领域的工作。他在人工智能方面的工作包括让计算机学会下棋,他认为这是测试人工大脑真正勇气的一种方式。图灵在1948年开始研究他的算法,那时计算机甚至还不能执行复杂的计算。后来,香农在1949年的一篇论文中扩展了图灵的工作,解释了他对国际象棋的兴趣:“尽管这个问题没有实际意义,但它具有理论意义,人们希望这个问题会成为攻击其他问题的一个楔子——具有更大的意义。图灵坚持不懈,并在1950年完成了他的代码。算法很粗糙。它的逻辑仅仅基于几个最基本的国际象棋规则,而且它只能提前思考两个步骤(比较而言,被认为是世界上最好的棋手之一的加里·卡斯帕罗夫表示,他通常会提前计算三到五步,但根据具体情况,他可以提前预测1214步)。

1951年,艾伦·图灵就发布了开发的在纸上的程序,能够玩一盘完整的国际象棋。由于1952年与另一个男人的关系,图灵被起诉,并被化学阉割。图灵在战时的胜利和早期人工智能的成就都变得默默无闻。图灵从未见过他的程序被真正的计算机执行。1954年,他死于氰化物中毒——离他42岁生日还有两周。

1951年,图灵的同事迪特里希·普林茨编写了第一个真正的自动下棋程序。普林茨的程序运行在位于曼彻斯特大学的新费拉蒂马克一号电脑上,尽管由于内存和计算能力的原因,它不能玩完整的国际象棋游戏,但它成功地解决了二选一的问题: 如果你离将死只差两步,就能找到最好的棋。七年后,一位名叫亚历克斯·伯恩斯坦的IBM研究员编写了第一个完整的全自动象棋程序,运行在新的IBM 704主机上。

人工智能作为一个研究项目本身于1956年在著名的达特茅斯研讨会上正式启动。这个研讨会参加者共有10人,其中多位热衷于机器象棋:塞缪尔研究跳棋,伯恩斯坦研究象棋,麦卡锡为下象棋设计的一种名为阿尔法-贝塔的搜索算法,而赫伯特·西蒙更是热衷国际象棋程序开发。1950年克劳德·香农在《科学美国人》发表过一篇谈计算机下棋的文章《为下棋编写计算机程序》,这是关于计算机象棋问题的第一批论文之一。香农还和图灵一起讨论过计算机下棋。

算法与国际象棋计算机

除了算法,硬件是一个主要的限制因素。下棋的算法在20世纪50年代就已经为人所知,尽管在后来的几十年里会有更新和改进。

普林斯顿高等研究院(爱因斯坦也在那里进行研究)的天才约翰··诺依曼认识到新的电子计算机在分析核弹、天气和自动执行军事行动(如高射炮)方面的巨大价值,冯·诺依曼提出了用于博弈的极大极小算法。极小极大,之所以如此命名,是因为它寻求最大化一个玩家的分数,同时最小化对手的分数,成为人工智能科学家的工具箱中用于构建下棋计算机的基本工具。到20世纪50年代末,核心的极小极大算法被启发法(下棋的经验法则)所扩充,启发法是从对人类玩家的战术和策略的研究中收集的。在这里,人工智能先驱艾伦·纽威尔和卡耐基梅隆大学的赫伯特·西蒙领路。他们的NSS(纽威尔、西蒙和肖)程序将极小极大优化例程与一种被称为阿尔法-贝塔剪枝的技术相结合,通过忽略已知的坏动作来加速搜索。NSS加入了一组不断增长的启发式算法,增强了它的基本搜索策略,进一步提高了极小极大算法的性能。

1956年,在洛斯阿拉莫斯MANIAC电脑上,由保罗·斯坦和马克·韦尔斯开发了第一个玩类似国际象棋游戏的程序。1957年,亚历克斯·伯恩斯坦开发了第一个可以玩完整国际象棋游戏的程序。亚历克斯·伯恩斯坦(Alex Bernstein)是美国数学家、棋手和IBM程序员。亚历克斯·伯恩斯坦与他的同事迈克尔··罗伯茨、蒂莫西·阿布克尔和马丁·贝尔斯基一起,是IBM 704伯恩斯坦国际象棋项目的主要作者。伯恩斯坦是在704主机的控制台上玩他的象棋程序。伯恩斯坦通过拨动前面板上的开关告诉计算机可以采取什么行动。这个程序花了大约八分钟来计算每一步。

image.png

亚历克斯·伯恩斯坦与IBM 704控制台

1958年,第一个使用alpha-beta搜索算法(该算法是约翰·麦卡锡在1956年发明的)的国际象棋程序NSS被开发出来。到了20世纪60年代,人工智能已经开发出了可以和人类对手玩真实、真实、自动化的国际象棋的程序。1962年,麻省理工学院学生设计的一个程序可以打败业余棋手。1963年,大师大卫·布朗斯坦击败了运行早期国际象棋程序的M-20

1966-67年,计算机程序之间的第一场国际象棋比赛开始了。莫斯科理论和实验物理研究所(ITEP)在九个月内通过电报击败了斯坦福大学的科托克-麦卡锡。到了1967年,麻省理工学院的程序员理查德·格林布拉特(Richard Greenblatt)在早期的系统中加入了许多强大的启发式算法,并在一次国际象棋比赛中获得了前所未有的1400分。1400分是一个非常优秀的高中运动员的水平,也是国际象棋程序的一个重要里程碑。电脑象棋越来越好了。

针对人类玩家,新系统开始威胁甚至是大师级玩家。1968年,国际象棋大师大卫·利维与人工智能研究员约翰·麦卡锡打赌,在接下来的十年里,没有一台国际象棋计算机能打败他。到了1978年,国际象棋程序如此之好,以至于要决定利维的赌注结果,就要安排一场真正的比赛——谁知道会发生什么?那年在多伦多的加拿大国家展览会上,利维赢了,打败了顶尖的象棋4.7。这是人性的胜利,就像利维当时开玩笑说的那样。这也被证明是短暂的,因为国际象棋在20世纪80年代继续向大师级水平发展。

20世纪70年代,随着越来越强大的硬件和更好的软件的结合,国际象棋程序继续改进。添加了有效的启发式,并且搜索的创新性改进,如迭代深化也被用来扩充现有的程序。迭代深化逐渐增加了极小极大搜索的深度,而不是设置一个固定的深度。这种技术允许象棋程序在每一轮优化他们的搜索策略,在游戏进行的时候,时间是有限的。

硬件也受益于两项发展。第一,摩尔定律普遍提高了硬件速度,因为每两年左右,计算机系统的功能就增加一倍,速度也增加一倍:这是一个惊人的结果,似乎证明了对人工智能的兴奋和未来主义的大肆宣传是有道理的。其次,研究人员开始设计特殊用途的硬件,这些硬件被优化用于搜索象棋游戏的内部计算机表示(被称为树)。后一种发展被证明非常有用,最终使特殊用途的国际象棋机器有可能竞争,然后超越更昂贵和更强大的大型机和超级计算机。20世纪70年代,研究人员开始缩小他们的关注点,用定制的软件和硬件设计特定的、特殊用途的下棋系统。电脑象棋变得更好了。

1970ACM(世界上第一个科学性及教育性计算机学会)北美电脑象棋锦标赛的第一年。1977年,国际计算机象棋协会成立。同年,第一台微型计算机国际象棋比赛机器CHESS CHALLENGERBORIS问世。1978年,大卫·利维赢得了10年前的赌注,在6场比赛中以41的比分击败了Chess 4.7。电脑在第四场比赛中的胜利,是人类大师在锦标赛中的第一次失败。

这个人工智能时代后来被称为认知模拟,因为它特别注重开发能够模拟人类认知的某些狭窄方面(如下棋)的算法,是人工窄智能,而不是人工通用智能。然而,西蒙早在1965年就说过,20年内,机器将能够做任何一个人能做的工作。对于人工智能来说,这样的预测被证明是过于乐观的,至今还无法实现。

跳棋与亚瑟·塞缪尔

亚瑟·李·塞缪尔(1901年12月5日-1990年7月29日),是计算机游戏和人工智能领域的先驱。从1949年到60年代末,他在让计算机从经验中学习方面做得最好。“机器学习”这个术语就是亚瑟·塞缪尔于1959年创造的。他的工具是跳棋。玩游戏的程序在人工智能研究中扮演的角色,如同果蝇在遗传学研究中扮演的角色。果蝇对遗传学来说很方便,是因为它们繁殖速度快,饲养成本低;而游戏对人工智能来说很方便,是因为很容易比较计算机和人的表现。

塞缪尔利用跳棋的另一个优点进行学习研究,即,棋手有很多带注释的游戏,有好的和坏的区别。塞缪尔的学习程序使用跳棋指南,来调整其选择动作的标准,以便该程序尽可能多地选择那些被跳棋专家认为好的动作。

1961年,当埃德·费尔德曼在创作第一部人工智能选集《计算机与思维》时,他们请塞缪尔把该程序所玩过的最好的游戏,作为他关于跳棋的精彩论文的附录。塞缪尔利用这一请求作为挑战康涅狄格州跳棋冠军的机会,康涅狄格州跳棋冠军是美国排名第四的选手。塞缪尔的程序赢了。冠军提供了游戏的注释和评论。

塞缪尔的跳棋程序可以击败它的设计者,击败康涅狄格州的跳棋冠军。那么,计算机是否具有了创造性呢?塞缪尔在1960年的一篇反驳维纳的文章说:“机器并不像一些人认为的那样对人类构成威胁。机器没有意志,它所谓的“结论”只是其输入的逻辑结果,正如无生命的机械和电子部件组合的机械功能所揭示的那样。“(参考资料[1])

因为他的跳棋工作是非数值计算的最早例子之一,塞缪尔极大地影响了早期IBM计算机的指令集。这些计算机的逻辑指令是在他的鼓动下输入的,并很快被所有计算机设计者采用,因为它们对大多数非数值计算都是有用的

image.png

亚瑟·塞缪尔

塞缪尔是一个谦虚的人,直到1966年从IBM退休后,他的工作的重要性才被广泛认可。这部分是因为他不喜欢让他的研究更有力地继续下去所需要的政治。他也很现实地认识到在理解智力机制方面所取得的成就,和达到人类智力水平所需的成就之间的存在巨大差异。

塞缪尔关于机器学习的论文仍然值得研究。凭借巨大的创造力,他基本上独自工作,自己编写程序,在死记硬背和概括学习中发明了几项开创性的技术,使用了可变评估函数、爬山和签名表等基本技术。人们仍然会听到在这个领域进行研究的提议,但没有他在20世纪50年代的工作复杂。

在机器学习工作之前,塞缪尔有着杰出的电气工程师生涯,同时,他在IBM也有着杰出的工程师和工程与科学研究经理生涯。

1946年,塞缪尔成为伊利诺伊大学电气工程教授,并积极参与他们设计第一台电子计算机的项目。正是在那里,他构思了一个可以打败世界冠军并展示电子计算机威力的跳棋程序。显然,当他在伊利诺伊大学的时候,程序还没有完成,也许是因为计算机没有及时完成。

1949年,塞缪尔加入了IBM的波基普西实验室,并在IBM的第一台存储程序计算机701上工作。那台计算机的存储器是基于威廉姆斯管,威廉姆斯管在阴极射线管的屏幕上以带电点的形式存储比特。塞缪尔设法将存储的位数增加4倍,并将平均故障时间提高到半小时。

最终,701被制造出来了,它包含了塞缪尔建议的指令集的一些变化,这是他在跳棋方面工作的结果。作为第一个真正的大型非数字程序,它影响了后来所有IBM机器的指令集。由于塞缪尔害怕机器可能永远也不会完成,或者可能会彻底改变,他把跳棋程序写成一组由中央模块加载的独立小模块——一种原始的操作系统。他让这一切在701的第一个实验模型上运行。

他在701上完成了第一个跳棋程序,当它即将被演示时,IBM的创始人兼总裁老托马斯·J·沃森评论说,演示将把IBM股票的价格提高15个点。确实如此。

后来的程序根据职业玩家的输入重新评估奖励功能。塞缪尔还让它自己玩了成千上万个游戏作为另一种学习方式。通过所有这些工作,他的程序达到了令人尊敬的业余水平,并且是第一个在如此高的水平上玩任何棋盘游戏的人。1966年从IBM退休后,塞缪尔继续研究跳棋,直到20世纪70年代中期,那时他的程序获得了足够的技能来挑战一个受人尊敬的业余选手。

塞缪尔在年龄迫使他放弃积极的研究很久以后,仍然是一个活跃的计算机程序员。他的最后一项工作一直持续到85岁,包括修改程序,以便在斯坦福大学计算机科学系的一些计算机上打印多种字体。也许他是世界上最老的计算机程序员之一:他使用的电脑告诉我们,他最后一次登录是在1990年2月2日,这是在帕金森病停止了他的积极工作之后,时年91岁。

微机象棋和深度思考(Deep Thought)

20世纪80年代迎来了个人电脑时代。业余程序员开始在自己的时间里,在自己的客厅里尝试和玩象棋程序。国际象棋系统也单独出售给公众,成为当时流行的消费产品。没有人确切知道计算机最终能做什么,但是,很明显他们能下棋——而且相当好。

世界微机象棋锦标赛(WMCCC)1980年发起,并主办了第一次正式的计算机象棋比赛。也许未来最好的预兆是弗雷德金奖,它为任何打败世界象棋冠军的计算机程序提供10万美元的奖励。击败最优秀人类的竞赛正在进行。卡内基·梅隆大学的研究人员以两种系统引领潮流——高科技和芯片测试,以及后来的深度思考(Deep Thought)——20世纪80年代许峰雄等人在卡耐基-梅隆大学制造的一种计算机国际象棋机器,它是在后来在比赛中击败加里·卡斯帕罗夫的国际象棋机器深蓝的前身。深度思考的名字取自以道格拉斯·亚当斯小说《银河系漫游指南》中的超级计算机的名字。

许峰雄是中国台湾出生的电机工程师,计算机科学家、国际象棋实体芯片测试(ChipTest)、深度思考(Deep Thought)和深蓝(Deep Blue)的VLSI架构(超大规模集成电路架构)创造者。许峰雄从台湾大学电气工程学士学位毕业后来到美国。1985年,他以卡内基梅隆大学博士生的身份开始了芯片设计,为1989年在孔祥重 (Hsiang-Tsung Kung) 的指导下完成关于阿尔法-贝塔搜索算法大规模并行化的博士论文(阿尔法-贝塔的程序算法是约翰麦卡锡在20世纪50年代末发明的,最早用于开发象棋程序),然后,加入IBM,参与深蓝计划。2003年,许加入北京微软亚洲研究院。他提出了这样的观点,即在国际象棋中,蛮力计算已经使人类黯然失色,在古代的亚洲围棋游戏中,可能很快也会如此。

image.png

许峰雄在1989年世界微机象棋锦标赛上

20世纪80年代末,诞生了打败人类大师的系统。看起来,这是一个历史性的时刻——一台机器在一个被许多人认为象征人类聪明才智的游戏中,击败了一个专家人类的时刻。1988年,汉斯·伯林和卡尔·艾伯林开发的高科技,在与大师阿诺德·登科的比赛中胜出。1988年,卡内基梅隆大学设计的系统深度思考(Deep Thought)在大赛中领先于前世界冠军米哈伊尔·塔尔和几位大师,包括塞缪尔·雷舍夫斯基、沃尔特·布朗和米哈伊尔·古列维奇。它还击败了特级大师本特·拉尔森,成为第一台在锦标赛中击败通用汽车的电脑。

除了象棋,杰拉尔德·特索罗在1992年开发了TD-Gammon,一种使用人工神经网络学习如何玩双陆棋的计算机程序。

国际象棋与深蓝(DeepBlue

象棋是一种古老的游戏。它很可能是在公元6世纪从印度通过波斯(伊朗)传入西方世界的。它也是一种源于皇家的游戏:在战场上测试某人的智力和敏锐度,但今天它是每个人的游戏。首先,下棋不需要昂贵的设备。这个游戏还有另一个优点,任何玩家都可以解释:象棋很有趣。

在当今的西方世界,国际象棋是最受欢迎的棋盘游戏之一,似乎任何人都可以在任何地方下棋:在城市公园、起居室、学校,以及广为人知的正式比赛中。孩子们可以在很小的时候就学会下棋,到了高中,年轻的棋手可能会达到接近大师水平的水平。最近,一些学校已经开始将下棋纳入他们的课程。国际象棋可能有皇家和军事的起源,但在现代世界,它是一种流行的智慧游戏,许多人都喜欢。

从技术上讲,国际象棋是一种两人棋盘游戏,由一个正式系统组成:一个由离散的代币和操控代币的规则组成的系统。(在国际象棋中,有六种代币类型:国王、王后、车、骑士、主教和卒。每个玩家从这些类型中选择16个代币开始游戏。用博弈论的话来说,国际象棋是一种零和的、完美的信息游戏。零和意味着玩家A的成功移动对玩家B不利(A来说好的移动对B来说是坏的结果),而完美的信息意味着每个玩家的所有位置都是同等可见的:每个玩家在游戏的每一步都能完全看到整个游戏。

象棋也有所谓的“马尔可夫”属性,这意味着先前的棋步对于理解如何下一步棋来说是不必要的。原则上,棋盘上的每一个离散排列都可以被视为独特的,下一步可以通过检查当前的棋子排列来决定。用计算机科学的术语来说,象棋也是组合的:每一个连续的动作都会产生一个(通常很大的)可能性组合。此外,就搜索而言,国际象棋是一个有界限的分支问题:计算机科学家将国际象棋视为一大组分支可能性,由底部的差棋和顶部的好棋所限定。象棋的有界性有助于捷径或修剪,一旦确定某一分支上的特定路径相对于另一分支已经很差,就可以忽略其他可能性。

然而,对于所有的博弈论分析,人类玩家从战术和战略的角度来看待国际象棋:思想。人类棋手赢得国际象棋的能力需要一定程度的智力技能。人们必须看到正在发生的事情——对手的动作在特定战术上意味着什么,通常是长期胜利战略的一部分。尽管如此,游戏的根本仍然完全由游戏棋子的位置决定,规则告诉每个玩家下一步如何移动。因此,尽管人们下棋是一种人类思维的游戏,但它也可以被计算机程序作为一个正式系统来分析——一个有规则的系统,但不需要任何意义或额外的解释。象棋的这种形式特征引发了关于自动化的讨论,以及机器是否能根据规则智能地操纵棋盘上的棋子的问题。至少在西方世界,这个问题——机器是否真的会下棋——在象棋的漫长历史中很早就出现了。

自20世纪40年代末人工智能和第一台计算机出现以来,计算机科学家将计算机的“巨型大脑”的性能与人类的大脑进行了比较,并把象棋作为测试计算机计算能力的一种方法。第一台为国际象棋编程的计算机是名为TurboChamp的算法,它是由著名的英国计算机科学家、数学家和密码分析学家艾伦·图灵在20世纪40年代后期写的。这种象棋游戏是一个对大脑和机器来说具有挑战性的问题的集合,但是有简单的规则,因此非常适合这样的实验。其中,最著名的人机对弈是卡斯帕罗夫和IBM深蓝的对决。

自20世纪50年代初以来,IBM计算机科学家就对国际象棋计算感兴趣。1985年,卡耐基梅隆大学的研究生许峰雄的论文项目,就是一台他称之为芯片测试的国际象棋机器。后来他和他的一名同学受雇于IBM Research。他们在其他计算机科学家的帮助下继续工作,该团队将其项目命名为“深蓝”。这是早期版本的“IBM的深蓝(DeepBlue)。后来,研发团队意识到一个纯粹的蛮力算法并不能击败世界冠军,把算法、搜索和评估模型,与超级计算机结合起来,做出了世界级冠军水平的国际象棋计算机。

加里•卡斯帕罗夫是国际象棋特级大师,在1985年,年仅22岁的卡斯帕罗夫,战胜阿纳托利·卡尔波夫之后,成为世界国际象棋冠军。当年早些时候,卡斯帕罗夫在德国汉堡与世界上最先进的32台象棋电脑展开了一场车轮战。比赛结果是我全盘获胜,但那时我能够战胜数台计算机并不如何出人意料。是卡斯帕罗夫的黄金时代。在1985年至2006年间曾23次获得世界排名第一。曾11次取得国际象棋奥斯卡奖。1996年卡斯帕罗夫曾与IBM深蓝进行国际象棋比赛并胜出,成绩是三胜二和一负。

1997年5月11日, IBM 深蓝电脑在六局比赛后击败了卡斯帕罗夫,获得历史性的胜利:IBM深蓝赢了两局,卡斯帕罗夫赢了一局,三局平局。卡斯帕罗夫于最后关键一局第19手弃子投降

image.png

卡斯帕罗夫与深蓝对决

这场比赛持续了几天,得到了大量的媒体报道,成为了全世界的头条新闻。深蓝击败世界国际象棋冠军卡斯帕罗夫的结果,证明了人工智能在某些情况下有不弱于人脑的表现,并帮助广大观众更好地理解高性能计算。这项研究让开发人员洞察到他们可以设计一台计算机来解决其他领域的复杂问题,利用深厚的知识来分析更多可能的解决方案。此后,“深蓝”所采用的技术被用于分子动力学(帮助发现和开发新药的有价值的工具药物研发),金融建模(包括市场趋势和风险分析),数据挖掘(发现大型数据库中隐藏的关系和模式)等领域,深蓝对许多不同行业的计算产生了影响。

深蓝项目激发了IBM最近的一项重大挑战:制造一台能在更复杂的游戏《危险边缘》中击败冠军的电脑。。

在2011年2月的三个晚上,这台名为沃森的机器在数百万电视观众面前打败了两位史上最成功的人类玩家。沃森的技术比深蓝和早期的机器有了实质性的进步,因为它拥有能够处理和推理自然语言的软件,然后依赖于在竞争前几个月注入其中的大量信息。沃森证明了新一代人机交互将是可能的。

围棋与AlphaGo

围棋游戏是一种抽象的战略游戏,2500多年前在中国发明。尽管围棋规则简单,但它被认为比国际象棋复杂得多,是有史以来研究最多的策略游戏之一。

谷歌旗下的DeepMindAlphaGo是第一个打败职业围棋手的计算机程序,第一个打败围棋世界冠军,并且可以说是历史上最强的围棋手。随后,AlphaGo与传奇围棋手李世石展开了角逐,后者获得了18项世界冠军,被广泛认为是过去十年中最伟大的棋手。20163月,AlphaGo在韩国首尔以4-1获胜,全世界超过2亿人观看了这场比赛。这是里程碑式的成就。

DeepMind创建了AlphaGo,这是一个结合了高级搜索树和深层神经网络的计算机程序。这些神经网络将Go板的描述作为输入,并通过包含数百万个神经元样连接的多个不同网络层对其进行处理。一个神经网络,即“政策网络”,选择下一步行动。另一个神经网络,即“价值网络”,预测游戏的赢家。DeepMindAlphaGo引入众多业余游戏中,帮助它理解合理的人类游戏。然后,我们让它与不同版本的自身对抗成千上万次,每次都从错误中吸取教训。

随着时间的推移,AlphaGo不断进步,变得越来越强大,越来越擅长学习和决策。这个过程被称为强化学习。AlphaGo继续在不同的全球舞台上击败Go世界冠军,并有理由成为有史以来最伟大的围棋玩家。

image.png

AlphaGo与李世石对弈

AlphaGo使用Monte Carlo树搜索算法,使用作为其知识核心的经过训练的深神经网络来查找移动。AlphaGo最初是在一套由超过3000万人围棋比赛数据组成的训练集上进行训练的。然后,通过使用强化学习让它与自身的副本竞争,对它进行进一步的训练。

20171月,一款名为AlphaGo Master的改进版AlphaGo在一系列在线围棋游戏中与一些顶级国际围棋玩家展开竞争,但并未透露其身份,最终以600获胜。

20175月的未来围棋峰会上,AlphaGo(改进版AlphaGo大师版)与当时世界排名第一的选手柯洁展开了角逐。在这场三场比赛中,AlphaGo30获胜。这次胜利后,中国围棋协会授予AlphaGo职业9段称号。

柯洁后来称赞了AlphaGo独特的游戏风格,并表示人类花了数千年时间改进我们的战术,计算机告诉我们,人类是完全错误的”。与柯洁获胜后,AlphaGo退出围棋竞技场。

从AlphaGo到AlphaZero

201710月,DeepMind推出了AlphaGo Zero。作为AlphaGo的最新版本,AlphaGo Zero是从零开始构建的。AlphaGo Zero不是根据人类比赛中数百万次移动的数据进行训练,从空白状态学起,在无任何人类输入的条件下,通过与自身的副本竞争来进行下棋训练,能够迅速自学围棋。使用这种技术,AlphaGo Zero只需21天就超过了AlphaGo大师的水平,40天就变成了超人水平。

201712月,DeepMind扩展了AlphaGo Zero的算法,推出了AlphaZeroAlphaZero通过自我对弈强化学习,训练时只提供国际象棋规则(没有战略)。AlphaZero只花了4小时就学会了规则,能够与最高等级的国际象棋手比赛。在对斯托克菲什的100场系列赛中,AlphaZero以执白(先发优势)赢得了25场比赛,执黑赢得了3场比赛,其余的比赛都是平局。斯托克菲什没有获胜记录,AlphaZero没有失败记录。只经过24小时的训练,AlphaZero在国际象棋、围棋和日本将棋(Shogi)中,也都达到了超人的游戏水平。

image.png

AlphaZero 登上《科学》杂志封面

2018年12月7日,AlphaZero登上了《Science(科学)》杂志封面(第362卷,第6419期)。该杂志介绍说:电脑可以在越来越复杂的游戏中击败人类,包括国际象棋和围棋。然而,这些程序通常是为一个特定的游戏而构建的,利用了它的特性,比如它所玩的棋盘的对称性。Silver等人开发了一个名为AlphaZero的程序,它自学了围棋、国际象棋和日本将棋。AlphaZero在这三款游戏中,击败了最先进的专业程序。AlphaZero适应各种游戏规则的能力,是朝着实现通用游戏系统迈出的显著一步。

多年来,DeepMind一直在改进这个人工智能,在这个过程中击败了一系列人类冠军,他们在不屈不挠的“上帝般”神经网络之前就像多米诺骨牌一样倒下。麻省理工学院的计算机科学家尼克·海恩斯(Nick Hynes)说:“这就像一个外星文明发明了自己的数学”。“我们在这里看到的是一个没有人类偏见和预设的模型。它可以学习任何它认为是最佳的东西,这可能确实比我们自己对同一概念的理解更加微妙。”

扑克与Pluribus人工智能系统

人工智能在另一个我们最喜欢的游戏中击败了人类。2019年7月11日,卡内基-梅隆大学宣布,该校和Facebook(脸书)公司合作开发的人工智能Pluribus人工智能系统,在六人桌德州扑克比赛中击败多名世界顶尖选手,成为机器在多人游戏中战胜人类的一个里程碑。在12天和10,000手牌的时间里,这个名为Pluribus的人工智能系统在两种不同的环境下与12名职业玩家对决。在一个游戏中,人工智能和五个人类玩家一起玩;在另一个版本中,五个版本的人工智能与一个人类玩家一起玩(在这个场景中,计算机程序无法协作)。

image.png

Pluribus登上《科学》杂志封面

2019年8月31日在发表在《Science(科学)》杂志(第365卷,6456期)上的一篇论文中,Pluribus背后的科学家们表示,这场胜利是人工智能研究中的一个重要里程碑。尽管机器学习在象棋和围棋等棋盘游戏以及星际争霸2等电脑游戏中已经达到了超人的水平,但从某些方面来看,六人无限德州扑克代表了更高的难度:获胜所需的信息不仅对玩家来说是隐藏的(这就是所谓的“不完美信息游戏”),它还涉及多个玩家和复杂的胜利结果。围棋是在可观察的宇宙中,虽然棋盘的组合极大,这使得人工智能在规划下一步行动时面临巨大挑战,但是所有的信息都可以看到,游戏对玩家来说只有两种可能的结果: 赢或输。从某种意义上来说,这使得人工智能的训练变得更加容易。

早在2015年,一个机器学习系统在双人德州扑克中击败了人类专业人士,但是将对手的数量增加到五个,就大大增加了复杂性。为了创建一个能够应对这一挑战的项目,研发团队部署了几个关键策略。首先,他们教Pluribus玩扑克,让它和自己的副本对战——一个被称为自我游戏的过程。这是人工智能训练的常用技术,系统能够通过反复试验来学习游戏;玩几十万手牌来对抗自己。然后,为了应对6名玩家的额外复杂性,团队想出了一种有效的方法,让人工智能在游戏中向前看,并决定采取什么行动,这种机制被称为搜索功能。Pluribus没有试图预测对手将如何一直玩到游戏结束(这种计算在几个步骤后会变得异常复杂),而是设计成只看两到三步。这种截短的方法是“真正的突破”。

参考资料

[1] Arthur Samuel. Some Moral and Technical Consequences of Automation—A Refutation.Science.Vol. 132, Issue 3429, pp. 741-742  16 Sep 1960.

[2] Monty Hewborn . Kasparou uersus DEEP BLUE:COMPUTER CHESS COMES OF RGE .Springer-Verlag New York, Inc.  1997

[3] Matthew Sadler and Natasha Regan. Game Changer: AlphaZero’s Groundbreaking Chess Strategies and the Promise of AI. New In Chess. 2019

 




http://blog.sciencenet.cn/blog-3005681-1233246.html

上一篇:人工智能发展史:大事记(三)
下一篇:PAC:大概近似正确

10 杨正瓴 黄永义 鲍海飞 胡洪涛 文克玲 马耀基 郭嘉琳 张鹰 刘钢 强涛

该博文允许注册用户评论 请点击登录 评论 (7 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-8-12 00:10

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部