棋盘上打败人类的不止深蓝和AlphaGo!图灵、香农、冯·诺依曼

拿破仑怎样输给会下棋的木头人?谁编写了第一个下棋程序?
人类最先在哪种棋上被机器人打败?……
人机对弈的趣事,别错过了呀。

拿破仑下棋竟然输给了木头人?

1769年,德国发明家兼外交家沃尔夫冈·肯佩伦(Wolfgang von Kempelen)男爵准备造一台机械的下棋装置,一年后机器完工,取名“土耳其人”(The Turk),那时大家就把这玩意叫作“自动机”(automaton)。肯佩伦把这台机器展示给奥匈帝国的掌权者玛丽娅·特蕾西娅(奥国女大公、匈国女王),于是它就成为娱乐欧洲各皇室的保留节目。

称为“土耳其人”是因为这个装置的后面坐着一个土耳其装束的木头人。1804年,男爵死后,“土耳其人”被转卖给德国发明家约翰·马泽尔(Johann Nepomuk Maelzel),1809年马泽尔把它展示给拿破仑,并和这位不可一世的欧洲征服者对弈一局。

肯佩伦制造的、号称能自动下棋的“土耳其人”,其实是个骗局。(南方周末资料图)

肯佩伦制造的、号称能自动下棋的“土耳其人”,其实是个骗局。(南方周末资料图)

拿破仑执白棋先手,但最后“土耳其人”大胜,拿破仑恼羞成怒,把棋盘上的棋子全胡撸到地上。有好事者把拿破仑和“土耳其人”的对战棋谱记录在案,确实艺不如“机”。陆续和“土耳其人”接触过的名人还有本杰明·富兰克林、爱伦·坡、数学家查尔斯·巴贝奇。

“土耳其人”在欧洲巡演了几十年,最后被人发现是个彻头彻尾的假货:那个装置里总是有个活人,而且是个下棋高手。肯佩伦只是发明了个魔术而已。那时的水平,想造台会下棋的机器,门儿都没有。

1827年,“土耳其人”到美国巡演时,请了美国当时的顶级高手施伦伯杰(Schlumberger)藏匿其中。在巴尔的摩的一次表演中,两个孩子发现施伦伯杰频繁出入后台,把这个秘密透露给了报界。见过这台机器的高人如富兰克林和巴贝奇一开始就猜这是魔术而不是科技。但当时还是很多人愿意相信“土耳其人”真会下棋。更多人工智能解读:www.yangfenzi.com/tag/rengongzhineng

和牛顿、霍金一样,巴贝奇还做过一届剑桥的卢卡斯教授,他对所有机器装置都感兴趣,他在看到“土耳其人”时,正在研制第一台机械计算机“分析机”(analytical engine)。他认为他的分析机也可以下棋,但那至多是猜测。

图灵

图灵

图灵编写了第一个下棋程序

下棋一直就是人类智能的挑战,自然也成了人工智能的标志之一。二战没结束,图灵就研究计算机下棋,他1947年编了第一个下棋程序,可惜那时计算机的时间(简称“机时”)很宝贵,轮不到他上机,地主家也没余粮——图灵也不能保证机时。

但即使后来拿到机时,那机器和程序的水平也很有限。唐米歇(Donald Michie)是图灵的追随者,1950年试着在纸上模拟程序,和图灵对弈,但这实在不是办法。图灵在曼彻斯特大学的同事迪特里希·普林茨(Dietrich Prinz)接着图灵的思路,在1951年写了一个残局程序,能在离将死还有两步的情况下,找到最优解。这个问题也被称为“两步将死”(mate-in-two)问题。

跳棋:人类第一次在棋盘上被打败

1951年,图灵的朋友克里斯托弗·斯特拉切(Christopher Strachey)在曼彻斯特Mark-1上写了第一款跳棋程序。图灵在1952年曾与之对弈一局,轻松取胜。1956年IBM的亚瑟·撒米尔(Arthur Samuel)写了第二个跳棋程序,这款程序的特点是自学习,这也是最早的机器学习程序之一,后来不断改进,曾经赢过盲人跳棋大师。

1980年代末,最强的跳棋程序一直就是加拿大阿尔伯塔大学的Chinook,作者是现任阿尔伯塔大学理学院院长的计算机系教授强纳森·舍佛(Jonathan Schaeffer)。数学家丁斯利(Marion Tinsley)自1950年代起就一直是跳棋的人类冠军。丁斯利对跳棋理论研究很深,对舍佛团队也很支持,但美国、英国和加拿大的跳棋协会一直拒绝Chinook参赛。

1992年,跳棋程序Chinook(奇努克)挑战跳棋高手马里恩·廷斯利(Marion Tinsley),当时,跳棋程序还是不敌人类。

1992年,跳棋程序Chinook(奇努克)挑战跳棋高手马里恩·廷斯利(Marion Tinsley),当时,跳棋程序还是不敌人类。

为了和Chinook比赛,丁斯利放弃他的冠军称号。1992年丁斯利大战Chinook并取胜,1994年再战,但在比赛中,丁斯利不幸确诊为胰腺癌,不久病逝。丁斯利的公开纪录,除了输给Chinook几局棋外,从没有输给过任何人类棋手。此后Chinook独孤求败。

舍佛团队继续精研跳棋理论和实践,直到2007年,他们证明对于跳棋,只要对弈双方不犯错,最终都是和棋,而Chinook已经可以不犯错。他们的结果发表在2007年9月的《科学》杂志上,自此跳棋这一页就算翻过去了。舍佛的兴趣遂转向德州扑克和围棋。

来自火星的图灵,来自金星的香农

几乎和图灵同时,冯诺依曼也在研究计算机下棋,他和经济学家摩根斯顿合作的《博弈论》1944年出版,其中首先提出两人对弈的minimax算法。香农(Claude Shannon)1950年在《哲学杂志》发表“计算机下棋程序”(Programming a Computer for Playing Chess)一文,开启了计算机下棋的理论研究。其中主要思路在“深蓝”和AlphaGo中还能看到。

有趣的是战时图灵在布莱彻里庄园破解德国密码,香农则在贝尔实验室研究密码理论,其中还用到了他后来发明的信息论。图灵的工作直到1974年才部分解密,香农则偏理论。图灵战时到访美国普林斯顿大学和贝尔实验室,曾和香农多次会晤,但他们从来没聊过密码学,尽管香农猜到了图灵在干啥。

香农

香农

1950年香农去英国参加信息论会议时到曼彻斯特大学图灵的办公室回访,他们这次只聊了下棋和大脑,仍然没聊密码。图灵没有参加这次在伦敦的会议,但贡献了两篇短文,一篇讲机器学习,另一篇讲下棋。直到图灵的工作解密,香农才知道图灵在战时已经用到了“熵”,但是不是从了解信息论的美国同事处学来的就无从考证了。

信息安全专家史密斯(S.W.Smith)曾写过一篇题为“图灵来自火星,香农来自金星”的文章,很明显这是受那本《男人来自火星,女人来自金星》的启发。

香农把棋盘定义为二维数组,每个棋子都有一个对应的子程序计算棋子所有可能的走法,最后有个评估函数(evaluation function)。传统的棋局都把下棋过程分为三个阶段,开局、中局和残局,不同阶段需要不同的技术手段。香农的论文引用了冯·诺依曼的《博弈论》和维纳的《控制论》。

冯·诺依曼

冯·诺依曼

minimax算法中,二人对弈的一方为max,另一方为min,max的一方的评估函数要越高越好,min的一方则越低越好。max和min的对弈就形成了博弈树。树的增长是指数式的,当树很深时,树的规模会变得不可控。

达特茅斯会议的组织者之一麦卡锡首先提出α-β剪枝术以控制树的增长。纽厄尔、司马贺和肖(NSS,Newell, Simon and Shaw)在他们著名的定理证明程序之后,又做了下棋程序。

他们首先实现了α-β剪枝术。他们的程序是在一台Johnniac上实现的。原始的minimax算法是在博弈树被全部画出后再静态地计算评估函数,而α-β剪枝术则采取边画树边计算评估函数的动态方法。当评估函数的值超越给定的上界和下界时,树的搜索过程就停止,这样大大减少了树的规模。平均而言,同样资源限制下,α-β剪枝术要比原始minimax算法搜索的树深度多一倍,也就是说,可以比minimax向前看的步数多一倍。

第一个可以走完全局的下棋程序,每步要想8分钟

IBM 704

IBM 704

第一个可以走完全局的下棋程序是IBM的工程师阿列克斯·伯恩斯坦1958年在一台IBM 704上做的。估计那时IBM支持下棋就像后来支持深蓝和谷歌支持AlphaGo一样,虽没什么短期实用价值,但是很好的公关。机器每步要花8分钟想,随便会走几步棋的人就能击败这个程序。更多AlphaGo解读:www.yangfenzi.com/tag/alphago

1959年,麻省理工(MIT)的几位本科生在当时刚到MIT任教的麦卡锡指导下开始学习计算机下棋,当他们1962年本科毕业时,他们用FORTRAN实现了一款实战下棋程序,跑在IBM新出的 7090大型机上,此时已经可以击败一般的象棋初学者了。这个结果变成了其中一位学生Kotok的本科学位论文。1962年麦卡锡前往斯坦福任教,他持续改进,这个程序后来被称为Kotok-McCarthy程序。

1966年这个不安宁的年份,美苏的对抗也扩展到计算机下棋。苏联科学院的理论与实验物理研究所(ITEP)也在本所研制的一台M20计算机上开发了一款下棋程序,他们要和斯坦福大学的Kotok-McCarthy程序一决高下。1966年11月22日开始,直到1967年3月10日止,他们通过电报的方式走了四局。最后苏联3∶1战胜美国。

当时MIT的程序员格林布拉特(Richard Greenblatt)也在改进Kotok的程序,格林布拉特本人还是成绩不错的棋手。他在PDP-6上实现了程序MacHack VI。1966年,一直批评人工智能的哲学家德雷福斯也和MacHack对弈过一局,并且输给MacHack,这倒没有改变德雷福斯对待人工智能的态度。

1967年MacHack参加象棋锦标赛,并累计积分1400,这相当于不错的高中生水平。这个程序用了16K内存,后来PDP的厂家DEC把它预装到所有PDP系列的机器中。MacHack也是Internet前身ARPAnet上最早的网上游戏。当时给格林布拉特帮忙的志愿者中有个人叫克柔可(Stephen Crocker),他后来成为Internet前身ARPAnet的重要人物,并创办了互联网标准化组织IETF且写了第一个标准化文本RFC。

【文/尼克 乌镇智库(微信公号:WUZHEN-INSTITUTE)】

氧分子网(www.yangfenzi.com)是关注互联网生态圈的科技新媒体

·氧分子网http://www.yangfenzi.com)延伸阅读:

➤ 人机大战结束了,AI 投资才刚刚开始

➤ 超智能时代:中国输不起的三盘棋

➤ 信海光:机器战胜人类是宿命,但有一样它们永远学不会

➤ AlphaGo赢了围棋,但玩量子计算游戏人的直觉强过机器

➤ AlphaGo之父戴密斯·哈萨比斯:除了下围棋,AI还要塑造人类未来

➤ Facebook围棋项目负责人田渊栋:DarkForest与AlphaGo仍有差距

分享给您的好友:

您可能还喜欢…

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>