从"深蓝"到 AlphaGo丨AI 在游戏领域的升级打怪之路

可以说,AI的发展进化史就是AI在游戏领域的升级史。

SciShow是Youtube上热门的科普向脱口秀节目。它的内容包罗万象,无论什么问题在这里都会得到风趣又详尽的解答。在本次节目中,介绍了AI 是如何在游戏领域通过不断的升级发展,一步步碾压人类的。

机器赢了。机器如今几乎能够打败人类发明的所有游戏。这都归功于一些我们通过AI实现的技术。

人工智能丨AI

AI最简单定义是: 为解决问题而设计的计算机程序。

大多数程序,包括你此刻看视频用到的,都是不能解决问题的。相反,这些程序执行程序员编写的指令。它们不会自己得出完成任务的方案。而AI会尝试自己得出解决方案。AI越聪明,越能解决更复杂的问题。

自从计算机编程出现以来,我们就开始教AI玩游戏。比如跳棋国际象棋,还有中国的棋盘游戏——围棋。原因是游戏能很好地衡量AI到底有多聪明。玩游戏并取胜,需要解决问题的能力。解决问题的能力正是衡量智能的标准。因为无论对观众还是计算机程序而言,当中对问题的定义都很明确,没有模棱两可的结果。AI要么能够玩跳棋,要么不能。

游戏是开发新型AI的绝佳实验室环境,这就是为什么AI的发展历史也是AI玩游戏的历史。

跳棋丨Checkers

AI在游戏第一次打败人类对手是一个跳棋程序。

于1950年代,由美国计算机科学家Arthur Samuel开发,在IBM 704计算机上运行。

这台机器通过录入磁盘进行编程。跳棋游戏很简单,但IBM 704是个很简单的机器。它不能通过试错法得出所有可能的棋步,从而得出最佳的移动方式,至少无法在合理的时间内完成。除非采用暴力算法,当中需要大量的数字计算。

计算机算出一个棋步后可能出现的各种棋局,然后选择取胜概率最好的棋步。这个方法尽管不够创新,但切实可行。之后我们再回到这个话题。

问题是,暴力算法需要大量的计算资源,从而对数字进行计算,然而在1950年代没有那些资源。因此,最初AI玩游戏主要靠的是启发法(heuristics)。从此之后所有的AI用到了启发法。

启发法是经验法则(rule of thumb),尽管不是一直都正确,但是大多时候是正确的。在计算机科学中,启发法是一种算法。通过选择并不是最好,但足够解决问题的方案,以此来限制蛮力搜索。

一旦跳棋算法发现能够吃掉对手棋子的棋步,然后就停止了,就按这个棋步走。这种简单的启发法足以攻克跳棋。

扑克牌丨Poker

接下来,AI面对的是扑克牌游戏。

1970年代,计算机科学家Donald Waterman编写能够玩抽牌扑克游戏的程序。该游戏给玩家5张牌,可以最多换3张牌。

当中他开发了所谓的"生产系统"(production system)。如今AI当中都包含这一技术。

生产系统使用预先编好的规则来对符号进行分类,比如扑克牌的符号。Watermen开发的系统根据手上已有的牌,对牌的价值大小进行分类。比如一张梅花4,就其本身而言无足挂齿,但如果你手上还有一张方片4和一张黑桃4,那么这张梅花4的价值就会大幅提升。系统将评估这手牌的好坏,以及选择出手还是弃牌。通过把这手牌的价值,与预先编程的所谓好牌和坏牌进行比较。

启发法与生产系统。

前者要依靠经验法则;后者则根据复杂的规则比较系统。这两者的结合,让AI玩简单的棋类游戏变得轻而易举。

但是国际象棋不是简单的棋类游戏,而是更复杂的棋类游戏,要想取胜则需要运用一些成熟技术。

沉思 丨Deep Thought

1980年代,第一批国际象棋机在卡内基梅隆大学诞生。

这些早期的机器中,最成功的是"沉思"(Deep Thought)。每秒能计算70万个棋步。

1988年,Deep Thought试图击败一名国际象棋高手。但那并不是一般的象棋高手,这位棋圣在八 九十年代甚至如今,一直是世界上最顶尖的国际象棋高手。他就是加里·卡斯帕罗夫。

开始Deep Thought根本不是卡斯帕罗夫的对手,打败卡斯帕罗夫需要更快更强大的机器。对Deep Thought进行升级,包括以下改进:

第一、需要更多的内存和多处理器,即计算能力。Deep Thought的后代产品"深蓝"(Deep Blue)应运而生,它是更强大的机器。

第二、更好的软件。当处理数以百万计互相对比的搜索结果时,速度慢是个大问题。为此,深蓝被设计为适合并行处理。另外,系统还要考虑衡量一些更微妙的棋位。换句话说,采用了更优的启发法。

深蓝丨 Deep Blue

第一代深蓝的搜索速度约为每秒5千万到1亿个棋位。与Garry 卡斯帕罗夫对战时,它以2:4惨败给对手。每秒计算1亿个棋位,仍不足以击败人类的国际围棋冠军。

为此,深蓝团队在系统中增加了一倍的芯片,同时改进了软件,使每个芯片效率提升了25%。1997年与卡斯帕罗夫再次对战时,其运算速度达到了每秒3亿棋位,从而大获全胜

深蓝的胜利是计算机程序中的伟大壮举。当深蓝击败卡斯帕罗夫时,它是当时世界上最复杂的AI。但总体还是靠暴力算法来实现的。对己方或对方的每个可能的棋步进行暴力搜索,然后选出获胜概率最大的棋步。如果无法战胜对方,程序员升级程序从而计算更多的数字,但这种方法对围棋就不适用了。

围棋丨Go

我们之前的节目说过,谷歌的AlphaGo在2016年3月,击败了世界围棋冠军李世石。但是让我们探究一下,为什么AI攻克围棋是艰巨的任务。

如果你生活在西方国家,你可能对围棋不熟悉。围棋是一个中国的棋类游戏,数千年来其规则从未改变。有时被描述为"东方版国际象棋”,但是围棋要比国际象棋复杂得多,尤其对计算机而言。

首先,围棋棋盘比国际象棋要大。

围棋棋盘为19×19的网格,国际象棋棋盘为8×8。但这实际低估了围棋的复杂性,因为围棋的棋子不是放在网格中,而是放在四个角上。也就是说每个网格代表四种可能的位置,即与周围网格的交叉点。总而言之,围棋中的棋步组合比宇宙中原子数量还多。

其次,围棋中每个棋子都同等重要。

这与国际象棋不同,比如国际象棋中,后就比兵要重要。这种关系是可以通过编程让AI理解的,比如输入生产系统。但是围棋棋子的价值取决于,各个棋子在棋盘位置的相互关系。

围棋的目标是用在对弈过程中,以双方棋子所围"地"的大小决定胜负,所以每次棋步都是很主观的。甚至高水平的棋手有时也很难解释,他们是如何判断每个棋步和好坏。

计算机不擅长的领域就是主观性,以及计算万亿次的位置。因此深蓝的暴力算法对于围棋是完全不可取的。

阿尔法狗丨AlphaGo

AlphaGo并不是采用暴力算法的系统,而是使用深度神经网络。面部识别也是利用的该技术。并不是对一个个棋子的位置进行计算,而是通过寻找棋盘中的模式。

如同面部识别系统会搜寻眼睛、鼻子、嘴等图像。AlphaGo寻找提供强大或薄弱战术的棋子模式。但它要如何明确什么会带来有力或不利的局面呢? 我们提过每个特定位置的价值是主观的,不是么?

那么你需要了解深度神经网络的运行原理。

深度神经网络由不同机器系统的层构成,这称为神经元。这些神经元全都堆叠在一起、并行运行。从而神经网络能够对同一个问题,从多个不同角度、同时进行分析。

每个层根据不同标准评判同一图像,其中一层将看到围棋棋盘的图像,选出当中所有合理的棋步;下一层将找到棋盘中还未被控制的区域;再下面一层会追踪,自从一位棋手在任何区域落子,已经过了多久时间。从而告诉系统,哪片区域目前处于争夺状态,哪片区域暂时安全、可以先忽视。接下来的一层,会把白字黑字的模式与内部数据库进行比较,看目前棋局是否类似之前看到过的。诸如此类。

AlphaGo的神经元共用48层,每一层都用不同的方式分析棋局,并且这些层相互传递信息。因此如果某层发现很有利的棋步,那么其他层就会关注棋局的这个部分。一旦所有层都认同,某个棋步符合它们判断好棋的标准,AlphaGo就会落子。通过这种方式使用深度神经网络,系统就能模仿人类的直觉和创造力。

最终,AlphaGo以4:1击败李世石,李世石相当于围棋领域的卡斯帕罗夫。但AlphaGo只会变得越来越聪明。

AI的下一个挑战丨 What’s next

在游戏领域 AI几乎没有尚未攻克的挑战了,围棋是人类设计的最复杂的棋类游戏。但我还想看AI挑战魔镇惊魂(Arkham Horror:一款难度颇高的桌游)。

总之,我们设计了AlphaGo和深蓝。这些程序都是人类智力和好奇心的表现。

如果我们开发的AI能够在最复杂的游戏中击败该领域的人类顶尖高手,那么谁知道我们还能做出什么呢?

原文发布于微信公众号 - CDA数据分析师(cdacdacda)

原文发表时间:2017-11-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专注研发

第一次写博客,想了很久要给自己留一个什么样的开始

       我想说下我的理解。        很多ACMer入门的时候,都被告知:要多做题,做个500多道就变牛了。其实,这既不是充分条件、也不会是必要条件。

15330
来自专栏腾讯高校合作

悦读推荐 :《链接》 复杂网络的基石 大数据时代的开端

《链接》是《爆发》的作者,艾伯特-拉斯洛•巴拉巴西的成名之作,同时也是复杂网络的奠基之作,社交网络的入门之作。巴拉巴西之前,随机网络理论一直主导者我们的网络思维...

36570
来自专栏take time, save time

你所能用到的数据结构(一)

     无损编码的霍夫曼编码以及其余的各种编码由于要使用比较复杂的数据结构,所以按照我昨天说的,我决定从数据结构开始写起。数据结构和算法很难完全的分开,好的数...

36050
来自专栏华章科技

数学有什么用处?看完后恍然大悟!

高等数学有什么用?很多人问过我这个问题。其实大多数人在问这个问题的时候,心里已经预设了否定的答案。确实,对于大多数人来说,已经发展到了连数字都基本很少用了的一些...

8920
来自专栏新智元

机器自学72小时堪比国际大师,深度学习到底有多厉害?

本文是雷锋网2015年9月份发出的文章,由知社学术圈王鹏编译,原标题《深度学习机器自学国际象棋72小时,媲美国际大师》,文章来源:MIT Technolog...

29070
来自专栏CDA数据分析师

浅谈KL散度(相对熵)在用户画像中的应用

本文由CDA作者库成员Charlotte原创,并授权发布。 原文:http://www.cnblogs.com/charlotte77/p/5392052.ht...

34380
来自专栏PPV课数据科学社区

当禅师遇到一位理科生,后来禅师疯了!!知识无极限!!

老禅师忙着给各种年轻人指导人生,总是用一些模凌两可的语句,想着想着你自己似乎就想透了。但当满口心灵鸡汤的老禅师遇上理科生……于是有了下面的对话↓↓↓ 1、青...

43130
来自专栏机器人网

AlphaGo再下一城,是否代表已经诞生了真正的智能?

在刚刚结束的围棋人机第二场比赛中,AlphaGo执黑再下一城,原来对李世石抱有很大期望的围棋界人士信心受到重创,同样作为职业九段的选手,柯洁甚至在第二场比赛未结...

29650
来自专栏专知

【观点】Facebook人工智能组研究员田渊栋:关于AI的一些杂谈

来源:https://zhuanlan.zhihu.com/p/30750293 关于AlphaGo AlphaGo厉害的地方在于结合了工程和科研两方面的工作,...

42650
来自专栏新智元

AI 网红 Andrej Karpathy:为什么 AlphaGo很难应用到围棋以外的世界?

【新智元导读】 Karpathy在文章中谈到了AlphaGo技术中一些很酷的部分,以及,从围棋的7大属性出发,谈到了AlphaGo常常被人忽视的一些局限性。 我...

36580

扫码关注云+社区

领取腾讯云代金券