alphago战胜李世石 AlphaGo 能战胜李世石吗?

“国际象棋电脑程序想要在人类大师级(Master)选手中赢得一场比赛的唯一可能,是等到这位大师喝得烂醉、同时在下着50盘棋、并且犯下一个他一年才可能犯一次的错误时。”

上面这段话是1976年一位高级国际象棋大师(Senior Master)对当时的国际象棋程序所作出的评价。(这种说法是不是听起来很耳熟?20年前,人们差不多也是这么评价围棋电脑程序的。)

但在接下来的20年中,随着电脑算法和硬件的不断升级,电脑程序在与人类选手的比赛中战绩越来越好,国际象棋大师们对电脑程序的评价也在一次次改变:

“电脑永远也不可能击败特级大师(Grand Master)。”

“电脑永远也不可能击败实力强劲的特级大师。”

“也许电脑可以击败实力强劲的特级大师,但它永远也无法击败国际象棋世界冠军卡斯帕罗夫。”

1996年2月,世界冠军卡斯帕罗夫作为人类棋手的最后一道防线在美国费城迎战IBM的“深蓝”电脑,双方一共进行了六局的较量。在比赛的第一天,深蓝在第一局中击败了卡斯帕罗夫,这也是电脑第一次在标准比赛规则下战胜世界冠军。

在第一局比赛结束的当晚,卡斯帕罗夫和他的助手在费城的街道上一直散步到深夜。期间,心烦意乱的卡斯帕罗夫曾经问他的助手“如果那玩意儿是不可战胜的,那怎么办?”

不过,在次日进行的第二局比赛中,卡斯帕罗夫扳回了一局。在比赛结束后的采访中,他对深蓝做出了很高的评价:“在某些局面中,它(深蓝)看得非常深,就像上帝在下棋。”

在随后的四局比赛中,卡斯帕罗夫两胜两平,最终以4:2的总比分击败了深蓝,捍卫了人类象棋大师的尊严。虽然深蓝失败了,但4:2的比分让深蓝的制造者们心里很清楚,用电脑程序战胜世界排名第一的人类棋手将只是一个时间问题了。

要想明白在这20年内人们是如何将国际象棋程序的水平提高到足以跟世界冠军较量的,我们得先来看一下电脑程序下棋的原理。

电脑下棋的基本原理其实一点都不复杂,在这里我们用简单的井字棋(Tic-Tac-Toe)来举例说明:


井字棋是一种非常简单的二人棋类游戏。棋盘上一共有九个格子,对战的双方依次在格子中画下圆圈或者叉叉。当一方的三个棋子以横、竖或对角的方式连成一条线时即为胜利。

想要让电脑下井字棋,最简单的方法就是让它对所有可能的走法逐个推演一遍。比如说对于井字棋来说,第一步一共有三种走法,分别是下在角落上、边上和棋盘中间。对于这三种走法中的每一种,对手又会各有数种应对走法,从而形成更多数量的局面。电脑所要做的就是一步步计算下去,把每一种局面都推演一遍:


上面这张图片中显示了电脑推演过程的前两步。其中叉叉选手一共有三种开局,分别显示在图片的第二行中。图片的第三行中显示的是圈圈选手的应对走法。对于叉叉画在在中间的开局,圈圈选手一共有两种应对方法。对于另外两种开局,圈圈选手各有五种对应的走法。

这种推演每多推演一步,我们得到的不同局面就会越来越多。上面图片中只推演了两步,或者说两“层”(Ply)。由于井字棋最多也只能下上9步,并且每步的变化都十分有限。从第一步下到最后一步,井字棋一共只有26830种不同的棋局。电脑可以很容易地将每一种情况都推演到底并记录下输赢结果,下面的图片是一个简化的示意图:


在上面的图片里,最后一行中蓝点代表的是选手一获胜的结局,红点代表的是选手二获胜的结果。对于可以直接“看穿”每一步棋的最终结果的电脑来说,在和人类下棋时只要尽量选择自己颜色获胜的分支去下就可以了。如果双方都按照最优方案去下,将永远是和棋的结果。

让电脑下国际象棋的基本思路其实和下井字棋是一样的。但其中一个重要的区别是国际象棋的变化要比井字棋多得多。在国际象棋的中局阶段,平均每一步都有30-40种不同的选择,这意味着电脑往下推演一个回合(双方各走一步)就要计算一千种可能的情况,并且每多推演一个回合计算量就会增加一千倍。推演两个回合就要计算一百万种情况,四个回合就是一万亿种,八个回合就是一亿亿亿种……

由于计算量随着推演回合数的增多呈指数式的增长,电脑是无法像面对井字棋那样直接计算到最后一步的。人们只好做出一定程度的妥协,让电脑在推演到一定数量的回合数就停止计算。由于无法直接推演到分出胜负,所以人们又在电脑程序中增加了评分系统,好让电脑从千千万万个推演结果中选出最优的一个。例如人们可以在评分系统中设定皇后=9分、车=5分、象=5分、兵=1分等等,然后再根据棋子的不同位置对得分进行修正。电脑程序会按照这个评分系统对推演出的每一个局面进行评分。

接下来要做的事情显然是根据推演结果来选择下一步要走的棋了。假设电脑刚刚往下推演了两个回合,一共产生了一百万个可能的局面,并对它们一一进行了评分。我们现在是不是应该直接找出评分最高的那个局面,然后向上倒推出我们下一步应该要走的棋呢?

当然不是。

别忘了,在这两个回合一共四步棋中,只有两步是由电脑程序这一方来走的,还有两步是由对手来走的。对手走出的这两步棋一定是会尽力让电脑一方的评分降低的,所以电脑计算出的最优局面很可能只是存在于理论上而已,对手才不会乖乖地配合你走出这样一个局面。

在计算出N个回合后的所有局面后,我们需要用到一个特殊的算法来确定下一步要走的棋。下面的图片中是一个非常清晰的简化示例:


在上面的例子中,电脑一共进行了两个回合共四步棋的推演,得到了9个可能的局面,也就是第4行中的9个圆圈。圆圈中的数字是电脑对于这个局面的评分,正无穷大为电脑获胜,负无穷大为对手获胜。

在得到第4行的九个推演结果并对它们进行评分后,我们需要根据这个评分对第3行的局面评分(图片中红色箭头)。在这个过程中,我们需要把第3行中每个方框的评分值取为它下面所有结局评分中的最小值。这很容易理解,因为从第三行局面变为第四行局面的这一步是由对手来走的。对手当然会选择让我们的分值最小化的走法。所以第3行最左边的方框被赋予了10的评分,因为对手不可能在这个局面下配合你走出下一步让你取胜的棋,它下面的那个正无穷大局面也是根本不可能发生。

在对第3行完成评分之后,我们接下来要根据第3行的评分对2行进行评分。请注意从第2行局面变为第3行局面的这一步是由我方来走的,所以第2行中的每个圆圈的评分值取为它下面所有评分中的最大值。按照这种方法依次类推,我们可以得到对第1行两种走法的评分,分别是-10分和-7分。这两个评分的意义是,如果我们选择左边的走法,四步之后得到的最好结果将是-10分,如果选择右边的,四步之后得到的最好结果将是-7分。根据这个推演结果,我们当然选择右边的走法(图中蓝色箭头)。

由于这个算法对于每一行的评分轮流进行最小和最大取值,所以被叫做Minimax算法(Minimax Algorithm)。

有了搜索系统和评分系统这两个最核心的模块后,电脑就可以开始下象棋了。电脑用两个步骤来决定自己的下一步棋:

首先,电脑按照设定好的搜索深度向下搜索出所有可能的走法,并得到这些走法所形成的所有局面(Position)。接下来,评分系统对按照规则对这些局面逐一进行评分,然后按照上面讲的Minimax算法将评分一层层向上返回。当评分返回到第一层时(也就是电脑要走的下一步棋时),评分最高的走法被电脑选走作为下一步棋。
虽然可以下棋了,但这时的电脑搜索效率很低,完全无望战胜人类的大师级选手。

为了让电脑在相同的时间内达到更大的搜索深度,人们又想出很多方法来改进象棋程序的搜索系统。例如用剪枝算法(alpha-beta pruning)来切除那些显然不是最优解的路径以节省计算资源,或者把一些搜索结果储存起来(transpostion table)供以后调用……等等等等。

除了改进算法以外,另一个更加粗暴的方法就是直接提高计算机的运算速度。同样的一个象棋程序在普通电脑上运行时可能只相当于人类Class C的水平,但放到超级计算机上运行时立刻会上升到人类Class A的水平(Class A选手对Class C选手有90%以上的胜率)。这是因为超级计算机可以使得象棋程序在同样的时间内完成更大的搜索深度,即“看到”更多回合后的情况。

电脑象棋程序以上面的两种方式发展了20年后,实力已经越来越接近人类顶尖棋手的水平。等到开发深蓝的时候,IBM团队中技术人员的象棋水平已经根本无法跟上深蓝的水平了。于是IBM又特意雇了一位国际象棋特级大师Joel Benjamin,让他来与深蓝进行对战练习,并对深蓝的参数进行修正。

在IBM团队研制深蓝之前,其实电脑已经在一些方面显示出了超越人类的势头。一个叫做Ken Tompson的人在80年代利用计算机对国际象棋的残局进行了研究。对于双方棋子总数少于5个的残局,由于变化相对较少,Ken干脆用计算机对这些残局进行了暴力破解(即把双方所有可能的走法穷尽一遍)。

在得到结果后,他惊讶地发现,对于一些人类长期以来认为是和棋的残局,计算机竟然找到了需要走50步以上的获胜方法。在这些残局中取胜的步骤中包括一些看起来完全没有任何意义的走法,这已经彻底超越了人类在国际象棋上的思考能力,更不要提后来计算机又找到了一些需要走500步以上才能取胜的残局。

2005年,人们用计算机暴力破解了双方棋子总数不超过6个的所有残局,生成的数据大小有1200G。2012年,人们又暴力破解了双方棋子总数不超过7个的所有残局,生成的数据大小为140000G。

用Ken的话来说,这意味着现在当人类和计算机对弈到双方棋子总数不超过7个的时候,人类等于是和上帝在下棋。

在科技人员和象棋特级大师的共同努力下,1996年的深蓝虽然输给了卡斯帕罗夫,但已经具有人类顶尖棋手的实力。仅仅一年后,经过升级后的深蓝就又向卡斯帕罗夫发出了第二次挑战。升级后的深蓝可以评估出6个回合内的所有走法,对于部分重要的路径则可以计算到20个回合以后。

在双方1997年的第二次交锋中,深蓝以3.5:2.5的比分战胜了人类的世界冠军卡斯帕罗夫,创造了历史。


上面这张图片是卡斯帕罗夫在1997年对阵深蓝的最后一场比赛时的情景。

电脑象棋程序第一次战胜人类世界冠军在1997年的中国也是一个大新闻,各大中文媒体都进行了报道,印象中答主就是那个时候才第一次听说IBM这家公司。但奇怪的是,在当时很多中文媒体的报道中,讲完这条新闻后都会话锋一转强调说虽然电脑在国际象棋上战胜了人类,但下围棋是绝对下不赢人类的。文章的最后通常会附上一些论述得意洋洋地证明中国人发明围棋比国际象棋要复杂得多。答主当时正在读中学,思想有一点中二,对当时的报道非常失望,觉得为什么没有一篇报道鼓励中国人抢在西方人之前先攻克这个难题,为什么这些人只盯着几千年前的历史而不想着去创造新的历史。

当然,让计算机下围棋确实要比下国际象棋困难得多。前面讲过的国际象棋中两个最核心的模块“搜索系统”和“评分系统”在面对围棋时都会遇到很大的挑战。

搜索系统:国际象棋只有8X8=64个格子,而围棋有19X19=361个点;国际象棋每回合大约有30-40种走法,而围棋有200-300种;国际象棋一局的长度大约是40个回合,而围棋可以长达150个回合。这些都会导致需要进行的计算量指数级的增长。一个常见的比喻是“围棋中可能的棋局数比可见宇宙中的原子数还多。”如果单纯采用暴力计算的方法,别说1997年的电脑,即使用今天的超级计算机也是毫无希望的。评分系统:国际象棋的评分系统很简单,每个棋子都有一个分值,越重要的棋子分值越高,重要的棋子越多分值越高。电脑可以很容易地按照简单的规则对某个局面进行评分。而在围棋中,每个棋子的价值都是相等的,但棋盘上的棋子数目多少又与局势没有必然的联系。人类可以靠经验、靠感觉,但电脑就很难对局势的优劣进行判断。如果无法对局面进行可靠的评分,上面讲过的算法都将不再成立。
这些困难当然每个人都知道,只不过一些人看到这些困难就直接放弃了,而另外一些人会努力找到各种方法来克服这些困难。

让李世石和Alphago之间的围棋人机大战成为现实的,正是这群“另外一些人”。

鉴于应用在象棋程序上的算法无法被直接使用在围棋程序上,开发围棋程序的人又想出了一些新的办法,例如蒙特卡洛树搜索(Monte Carlo Tree Search)。大家不要被这个逼格满满的名词吓到,蒙特卡洛是世界三大赌城之一,所以“蒙特卡洛”这个词在这里就是随机的意思。

在蒙特卡洛方法中,围棋程序在下棋时会首先判断出下一步可能的走法,假设有A和B两种。接下来,对于A和B两种走法,程序会分别按照随机的走法继续把这盘棋一直下到底,然后记录输赢结果。

假设程序在A之后按照随机的走法模拟下完了100局棋,赢了50盘。然后程序又在B之后按照随机的走法模拟下完了100局棋,赢了60盘。根据这个结果程序会得出结论:虽然都是随机乱走,在走了B之后乱走的胜率比走了A之后乱走的胜率要高那么一点点,那么想必B这步棋是比A要好那么一点点的。

这种算法乍一看有点诡异,但它很好地避开了前面提到的电脑程序下围棋中最大的两个困难。第一,这种方法不需要对某一层的可能下法进行穷尽计算,而只是随机选取一些路径进行模拟,因此大大减少了计算量。第二,这种算法在模拟中会直接将整盘棋下到最后分出胜负,然后再根据胜率来判断一步棋的优劣,因此也不需要设计任何评分系统对未结束的局面进行评分。

虽然这种算法可以绕开围棋程序中一些难以克服的困难,但一开始人们用这种算法编制的围棋程序水平也很烂,只能可怜兮兮地在9X9的棋盘上下棋。但随着技术人员的耐心改进,围棋程序的水平也一直在缓慢地提高。

2010年,围棋程序MogoTW与职业五段选手Catalin Taranu在全尺寸棋盘上对阵,在受让7子的情况下依然落败。

2012年和2013年,围棋程序Zen和Crazy Stone分别在受让4子的情况下战胜了职业九段选手。

2015年10月,谷歌的Alphago又把围棋程序提高到了一个新的高度,在没有让子的情况下以5:0的比分战胜了职业二段选手。

从网上几篇非常有限的报道来看(Nature的那篇文章我看不到,看到估计也看不懂),谷歌的Alphago的大概工作原理是这样的(下面的内容来自于这篇报道):

在Alphago中有两个模块,第一个是“落子选择器”。谷歌的在落子选择器中输入了上百万人类对弈的棋谱供它学习。在完成学习后,当你往这个落子选择器中输入一个新的局面时,它可以预测人类棋手在这种情况下会在哪个位置落子。

下面这张图片显示的就是这个模块对于下一步落子位置的预测,以概率表示:


在这里请大家注意这个落子选择器除了“猜测”下一步棋的位置之外,并不会做其他的事情。但是如果有两个版本的落子选择器来交替猜测黑白方的下一步棋时,它们之间就可以进行对战了,然后再根据的胜负结果修正自己的预测。这也就是很多报道里讲到的Alphago可以通过与自己对弈不断提高水平。

Alphago中的另一个模块是“棋局评估器”。根据Alphago自己和自己对弈的无数棋局的结果,谷歌的工程师可以训练“棋局评估器”对一个局面的黑白胜面进行评估。换句话说,通过学习海量的棋局,谷歌开发出了一个相对靠谱的围棋的评分系统。

有了上面的两个模块,Alphago在对战中通过一下步骤来决定下一步棋的位置:

首先通过落子选择器来产生下一步棋的备选走法(不一定只有一个位置);在得到下一步棋的可能走法后,程序会利用前面介绍过的蒙特卡洛算法确定其中的最优走法;利用棋局评估器对于这些可能的走法产生另外一个完全独立的评估,并得到相应的最优走法;在得到上面这两个相互独立的结果后,利用一定的权重将它们相组合,产生最终的最优走法。
在谷歌发布的视频中,谷歌的工程师在接收采访时表示对三月份的比赛很有信心。他表示李世石是一名很强大的对手,但是人类与电脑相比也有其自身的弱点(还记得前面讲过的电脑发现的需要走500步以上才能取胜的国际象棋残局吗?)。在视频的最后,这位研发人员说:“李世石每年可以下多少盘棋作为练习?也许一千盘?Alphago可以下一百万盘……每天。”

==========赛后更新==========

3月9日,第一场比赛结束,Alphago 1:0 领先。

各方反应:

Deepmind的CEO Demis Hassabis发表了推文:“Alphago赢了!!!我们登月成功了。为我们的团队感到自豪!当然李世石也棒棒哒~~”

李世石在赛后接受采访时说:“我很吃惊。我从来没有想过我会输……即使在落后的时候。我没想到它能下出这么精彩的棋……我听说Demis Hassabis将我视作值得尊敬的棋手。我同样也非常尊重制作出这个程序的人们。”

最后,李世石表示他十分期待接下来的比赛。

3月10日,第二场比赛结束,Alphago 2:0 领先。

比赛的悬念由赛前的“Alphago是否能至少赢下一局”迅速变成了“李世石是否能至少赢下一局”。

3月12日,第三场比赛结束,Alphago 3:0 领先。


在2016年前,人们说:“围棋是一种极其复杂的游戏,它的变化比宇宙中的原子数还多,所以电脑是不可能赢过人类的。”


在2016年之后,人们可能说:“围棋是一种极其复杂的游戏,它的变化比宇宙中的原子数还多,所以人类是不可能赢过电脑的。”


3月13日,第四场比赛结束,李世石奋力扳回一局,Alphago 3:1 领先。

今天李世石九段成功逆袭,战胜了Alphago!今天的比赛可谓是这场人机大战之中的莫斯科保卫战,打破了Alphago不可战胜的神话。

==========分割线==========

今天(3月9日)在微博上看到不少人说Alphago赢了李世石之后就会继续挑战击败了李世石的中国棋手柯洁。我认为这几乎肯定不会发生。如果Alphago真的在后面的比赛中击败了李世石,谷歌很有可能会对继续开发任何围棋程序彻底失去兴趣,因为他们已经在全世界的镁光灯下证明了自己的程序可以击败人类顶尖高手,也证明了自己的技术是全世界最牛逼的。

卡斯帕罗夫1997年输给深蓝之后,曾经提出过要复赛,但IBM根本就没有兴趣。

柯洁可能永远都没有机会了。   3/4   首页 上一页 1 2 3 4 下一页 尾页

爱华网本文地址 » http://www.413yy.cn/a/81320103/9135.html

更多阅读

怎么才能让鼻梁变挺鼻夹能让鼻子变高吗 捏鼻梁鼻子会变挺吗

怎么才能让鼻梁变挺鼻夹能让鼻子变高吗——简介塌鼻梁似乎成为了亚洲女性的头号公敌,亚洲人的体型不像欧洲人那么健硕,面部轮廓也不如欧洲人那么的棱角分明,亚洲人的脸部特征是扁平的,唯一凸出有立体感的五官就是鼻子,因此鼻子的美丑直接

看字读音,你能说出福州话吗 福州话字典

看字读音,你能说出福州话吗为了了解福州话的音韵,目前我有四、五本福州话字典,最古的有《戚林八音合订》、《戚林八音校注》,还有最近新编的字典。有几个学

泡椒凤爪的制作方法在坂田能学到正宗的吗 泡椒凤爪做法

泡椒凤爪的制作方法在坂田能学到正宗的吗?《食为先小吃技术培训》,学怎么做正宗泡椒凤爪制作技术,泡椒凤爪技术做法,酸萝卜做法,食为先专业的泡椒凤爪。食为先不止教你技术,还会教你用精选肉鸡爪泡制而成。泡椒凤爪的制作方法在坂田能学

声明:《alphago战胜李世石 AlphaGo 能战胜李世石吗?》为网友銗镎命嫒分享!如侵犯到您的合法权益请联系我们删除