棋盘上打败人类的不止深蓝和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仍有差距

分享给您的好友:

您可能还喜欢…

1 Response

  1. 纪录片《7%》解密,AI能够击败人类围棋高手的“绝艺”是什么说道:

    日本著名棋手藤泽秀行说过一句话:“棋道一百,我只知七。”

    围棋被称为世界上最复杂的游戏。想成为一位顶级棋手,往往需要过人的天赋和多年不懈的努力。

    但是AI的出现颠覆了很多传统的下法,打开了围棋世界的一扇大门。2017年初,腾讯推出了AI围棋软件“绝艺”,在网络上以绝对优势击败各国顶尖棋手,其后又赴日本参加了UEC杯世界计算机围棋大赛并夺冠。

    10月12日,一部记录了腾讯“绝艺”诞生和夺冠全程的记录片《7%》在香港恒生管理学院首次试映。该片由曾蝉联第51届、52届金马奖最佳纪录片奖导演周浩执导,深度访谈了柯洁、古力、武宫正树、大竹英雄等多位世界顶级棋手,讨论AI与人类的关系。

    著名科幻作家、南方科技大学教授吴岩参加了首映会,并与周浩就AI之后人与机器的关系展开了深入的讨论,碰撞出无数花火。

    本文经腾云编辑整理发布。

    周浩
    第51、52届金马奖最佳纪录片奖导演

    研究人工智能,是用
    不熟知的方法抵达秘境

    以前我们拍纪录片还是拍一些跟人有关的东西,我一直觉得纪录片是研究人和人之间的关系。当科技发展到今天的时候,我发现好像仅仅研究人与人之间的关系还不够。所以说我想研究一下AI和人的关系。我认为这还是在研究人和人之间的关系,这是人和人之间的关系的一种拓展。

    我第一次去腾讯的时候认识了“绝艺”的研发团队。这个团队大概有十多个人,大多数是30岁左右的程序员,而且是典型的程序员,特别木讷。中午请我吃饭,除了他们的领导,其他人基本上不说话,连简单的寒喧都不会。我知道他们花了不到一年的时间设计软件,“绝艺”那时候已经不断地在跟柯洁下棋了,柯洁是很难赢一盘的。

    我就想不通一个问题,柯洁成为世界第一,一方面是因为他有天赋,另一方面是因为他自己不懈的努力。从几岁开始学棋,最后变成世界第一,需要运气,需要努力。

    但是另外一群人,就像扫地僧一样,花了不到一年的时间研发出一台会下围棋的机器,就超越了柯洁,这中间到底发生了什么事情?

    我发现我们常规的认知方式应该被不断地打破。就像两个星球之间有一百万光年,按照传统的思维方式,我们以最快的速度也得一百万年才能抵达。实际上这种思维方式,现在已经越来越不准确了。比如说有虫洞,有另外一种方法可以抵达。人类对未来的认知、对世界的认知是非常非常局限的。世界的发展,社会的发展也许有另外一种方式可以走下去的。所以我觉得研究人工智能,实际上就是用一种以前我们不大熟知的方法去抵达另外的秘境。

    对于所有围棋选手,AI的出现
    是喜悦大于悲哀的事情

    AI对我们的影响已经越来越大了,我发现另外一个问题,就是这帮围棋选手也许是人类第一批生活和职业受到严重影响的人,当AI出现以后,他们怎么面对AI的出现?他们是一种什么样的心态?

    藤泽秀行,这是日本的一位已逝的、非常有名的棋圣,他曾经说过:“棋道一百,我只知其7”。后来我也访问过很多围棋高手,我问柯洁:”你大概知道多少?”柯洁说:“大概5%、6%吧。”

    现在一般人认为AI围棋应该已经是围棋上帝了,但很多棋手并不认为AI已经穷尽了围棋的道理。我们自以为很了解世界,其实也许人类对世界的了解连7%都不到,世界上最聪明的人,他们认为对围棋的了解只有7%,何况我们这些平凡人?

    目前为止,当AI出现的时候,围棋选手们的喜悦甚至会大于悲哀。只有一个人对我说“AI来得太早了”,这个人是柯洁,一个20岁不到的年轻人。当他是世界第一的时候,突然间有一个机器下得比他厉害,可以想象他的失落感。他问,“为什么AI不晚出现几年?”

    但在另一个层面看,他也特别欣慰。当你成为世界第一的时候,突然冒出一个老师,这个老师可以很快碾压你,其实这种感觉对一个心智健全的人来说,是一件非常欣慰的事情。因为知道自己的短处在哪里,可以进步了,这种感觉是非常微妙的。

    围棋胜负是很重要的事情,但是棋手会冷静地看待胜负,比如古力。其实对大多数棋手而言,围棋是一种修行,是让你在围棋中感悟人生。我采访日本一个非常有名的棋手,他感叹老天爷发明了这么一种完美的游戏,你不能穷尽它的变化,这种感觉是职业棋手才能体会的。

    所以围棋给他们带来的乐趣,已经远远超过了胜负。当AlphaGo出现以后,全世界下围棋的人数增加,围棋在欧美的普及度也得到了提高。围棋之所以在欧美普及不开,是因为欧美没有很厉害的高手,高手都在东方。当围棋软件出现以后,一个欧洲人如果不断跟世界最高水平下棋的话,他的棋艺会提高得非常快。所以围棋界是非常高兴的,他们觉得AI既然来了就接受它。

    吴岩
    著名科幻作家
    南方科技大学教授

    人工智能可能导致失业,
    但解放出来的人将创造新工作

    我看到这个片子以后特别高兴,因为我是搞心理学出身,1961年的时候有一篇文章名为《7》,讲人类认知的极限就是7,只是7个左右的组块就可以处理这些问题。这可能已经到了人类认知的极限,但是计算机现在能帮助人类,那么下一步机器和人确实是站在一个起跑线上。

    当大量的人工智能出现时,失业就会普遍产生。在内地,我们讨论得最多的问题就是下一步谁会失业。比如说高校里面,翻译专业可能最早失业,因为翻译是比较容易做的。老师也快失业了,因为教师的这套东西基本上人工智能也是可以处理的。

    今天人工智能确实正在影响着我们的生活,而且是最普通人的生活。但另一方面,人工智能近期对职业的发展,特别是对创业特别有好处。比如有个识花的软件,只要对着花拍一张照片,它就能告诉你这是什么品种,产自哪里。还有一个看云的软件,通过对云的观察,自动预测24小时之后的天气。

    从人类发展的历史看,科技的进步是在不断解放人类,人工智能可能替代掉很多工作,而解放出来的人将会创造出新的工作方式和职业。

    当天的讨论实在太精彩,影片正式放映前,主持人特意留了出时间给现场的观众提问。

    Q:如果AI什么都能做,我们可以快乐消费,可以娱乐,可以happy,或者是进行文化方面的创作。人会不会被废掉?人类再继续往前走的动力在哪里?

    周浩:我并不认为是机器战胜了人类,我更愿意认为是一个人或者一群人设计了一个机器,战胜了另外一个人或一群人。

    我觉得未来人工智能对人类的影响,可能反而不是在人工智能本身,因为人工智能还是一种工具,危险一定是来自于那些使用这个工具的人。就是当人的恶和这个机器进行完美结合,也许人类的某种灾难会降临。所以我觉得最终应该控制的,应该用道德去规范的,还是人本身。因为人的恶,也许远远超过我们的想象,机器有时候反而是可控的。

    吴岩:周导提得很有道理,因为他一直在提一个作品是《黑晶》,这里面有大量的关于人的恶。但是我觉得后人类时代,这个问题也很严重。摆在所有人面前的现状是,不单要处理人文的问题,还要处理后人的问题。今天不是说没事儿了,而是要考虑的问题更多了。

    Q:现在好像有一种趋势,总是在谈人工智能将会取代人类,这对教育来说是有很大影响的,因为我们通过教育去培训学生,用机器去教育学生可行吗?从人文角度来说,我们应该如何相信人工智能呢?

    周浩:以我的观点,我觉得现有的人工智能是无法代替人脑的,比如说关于爱,关于爱情,我不知道两个机器怎么交配,怎么会有性生活。我觉得人是一个非常复杂的组合体,而围棋软件就是一种算法,说下棋的时候,哪一步棋的胜率高就下哪一步棋,在它的整个程序里面只有胜负,这是决定它认识世界的唯一方法。

    而人类有趣的东西,恰恰是那些混沌的、模糊的、说不清道不明白的感觉。比如柯洁就谈到过这样的问题,他说下一步棋的时候,一定会受上一步棋的情绪的影响,跟今天吃了一顿饭、见了什么人,都有非常大的关系。但是对机器而言,它永远只有胜负。

    所以人类的感觉超越了胜负,胜负只是一个手段。就围棋这个游戏而言,我并不认为胜负是人类要的结果。围棋在中国国语里面有一种说法叫做“手谈”,就是两个人不说话,用手在进行交流,这种感觉是很多棋手要找的感觉。

    人跟人在一起的感觉,和人跟机器在一起的感觉是不一样的,也许我不会那么悲观吧。

    吴岩:我同意现在的人工智能,基于深度学习的人工智能还是比较“傻”的人工智能,虽然已经可以解决很多问题了,但还是很简单的。下一代的人工智能,比如说模拟人脑的那些算法,一旦突破了,比较复杂的人工智能出现的时候,很难讲不会取代今天的一些事情。

    现在大家总是在说人工智能情绪做不了,个性做不了,自我意志做不了。但事实上,情绪这些东西早晚都是可以做出来的,因为情绪就是伴随着认知的一种东西,你喜欢和不喜欢,这些都可以还原成某种生理的信号。只要把这些信号转换成代码,人工智能模拟情绪是没有问题的。至于说自我意识,这些也很可能早晚有一天是可以做的。所以我觉得,并不能说人工智能不可怕。

    关于现在的教育,我非常同意现在我们就要做出很多应对的方式,来给我们的下一代人做准备,让他们努力面对这个新的一面。其实现在做可能都已经晚了,过去的科幻小说是说未来在远方,今天我们说未来昨天晚上已经到了。面对这个情况,学生没有办法面对,我们也没有办法面对,现在所有事情都比想象中出现得快。

发表评论

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

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