从AlphaGo到Libratus,百页白皮书详解机器博弈(附报告下载地址)

AI科技评论按:计算机博弈也称机器博弈(Computer Games)。如果按英语字面意义来看,这一名词应该理解为「计算机游戏」。但从事计算机棋牌竞技研究的科学家们,所定义的「Computers Games」则是计算机像人一样会思考和决策的棋类游戏。为了与计算机游戏进行区隔,Computer Games 采用的是「机器博弈」或「计算机博弈」这一具有指代性的译名。

1997 年,IBM 深蓝战胜世界棋王卡斯帕罗夫成为了机器博弈的第一个里程碑,而在近 20 年后,AlphaGo 又横扫了围棋世界冠军李世石,升级版 Master 横扫 60 余名顶级高手,让我们看到了计算机博弈的强大生命力与令人惊叹的技术。

在 2005 年,中国人工智能学会成立了机器博弈专业委员会,将国际象棋算法移植到中国象棋的电脑程序中,并取得了令人瞩目的成果。为了更好地对机器博弈进行一个细致、深入的全景式刻画,中国人工智能学会机器博弈专业委员会撰写了《机器博弈白皮书》。本白皮书介绍了机器博弈的发展过程、国内外重要赛事、博弈典型技术与比赛平台;并结合相关棋种介绍各种专项博弈技术,包括完备信息的棋类比赛,也涵盖不完备信息的牌类游戏搜索算法。

AI科技评论将102页白皮书进行简单梳理,对重点内容做概要介绍。原报告为中文版本,欢迎关注 AI科技评论(aitechtalk),在后台回复关键词「机器博弈」下载报告全文。

本文要点:

  • 机器博弈的发展状况
  • 机器博弈的复杂度及典型技术
  • 完备机器博弈及非完备机器博弈的专项技术

一、机器博弈的发展状况

在 1928 年,「计算机之父」冯•诺依曼通过对两人零和一类博弈游戏的分析,提出了极大极小值定理,并证明博弈论的基本原理。在冯•诺依曼与摩根斯特恩合著的《博弈论和经济行为》(1944)中,将二人博弈推广到 n 人博弈,并将博弈论系统应用于经济领域,奠定了机器博弈研究的基础与理论体系。

近代机器博弈的研究始于 20 世纪 50 年代,包括阿兰•图灵、科劳德•香农、约翰•麦卡锡以及冯•诺依曼等人都做出了巨大的贡献。随着研究的深入,科学家们开始研究国际象棋的博弈编程方案,并在 50 至 60 年代有了极大突破。由此,科学家们开始思考,棋类对弈是否能成为让计算机尝试战胜人类的入口。

从上世纪八十年代中期,美国卡耐基梅隆大学开始研究世界级的国际象棋计算机程序,并在 IBM「深思」、「深蓝」的不断迭代中,计算机在 90 年代以来变得越来越聪明。1996 年的「深蓝」、1997 年的「超级深蓝」与卡斯帕罗夫的两场比赛饱受世界瞩目,堪称「世纪之战」。

进入 21 世纪,计算机博弈水平也在逐步提升。2016-2017 年,AlphaGo 与李世石在围棋领域的两场人机大战,堪称是人机对抗史上是顶级比赛,从而也掀起了人工智能的全球热潮。

随着围棋被攻克,科学家们开始将目光投向了多人博弈的非完备信息机器博弈领域。2017 年初,美国卡耐基梅隆大学开发的德州扑克博弈系统 Libratus,在与 4 名人类顶尖扑克选手的人机大战中获得了胜利,再次树立了机器博弈的新一里程碑。

二、机器博弈的复杂度及典型技术

计算机的博弈水平代表了计算机的智能水平。而衡量其复杂程度的的两个重要标准则包括了计算机博弈问题的状态复杂度与博弈树复杂度。下图为一些常见博弈问题的状态复杂度及博弈树复杂度。

计算机博弈的最高境界是找到该棋种的理想解,即不败解。而计算机博弈的最大困难和无法逾越的障碍则是问题的计算复杂性。被广泛认可的博弈问题,其计算复杂性一般都属于某复杂性类的困难问题(hard)或完全问题(complete),属于此类计算复杂性类的问题,被认为是最难解或是最难解的。

计算机博弈系统中,典型的关键技术主要包括搜索、评估与优化、学习与训练等技术。典型的博弈搜索算法:

  1. 搜索方向考虑,可分为深度优先搜索与宽度优先搜索;
  2. 从控制策略考虑,可分为盲目搜索与启发搜索;
  3. 从搜索范围考虑,可分为穷尽搜索、裁剪搜索。

此外,机器博弈的典型算法还包括迭代深化、最佳优先算法、随机搜索算法、并行计算、遗传算法、神经网络、机器学习等。

计算机博弈平台系统本身并不具有下棋或出牌的逻辑决策功能,但它能加载其它一个或多个决策引擎程序,使这些引擎程序以选手的角色参与对局。根据不同标准,计算机博弈平台可分为如下几类:

  1. 完备信息博弈平台和非完备信息博弈平台
  2. 单引擎博弈平台和多引擎博弈平台
  3. 单机博弈平台和网络博弈平台
  4. 程序级博弈平台和模块级博弈平台

三、完备机器博弈及非完备机器博弈的专项技术

以完备信息机器博弈与非完备信息博弈的专项技术,白皮书以棋类为例,分述了不同棋种的游戏规则,并介绍了它们在机器博弈所采用的主要技术。

国外机器博弈在完备信息博弈的研究代表是 Google 公司的 AlphaGo,它具有极强的自觉能力。AlphaGo 的成功充分验证了深度学习与计算机博弈技术结合的实用性。学者总结 AlphaGo 的关键技术包括:

  1. 棋感直觉:通过深度学习获得,分为落子棋感与胜负棋感。AlphaGo 通过对 3000 万的经典棋局进行深度学习获得快速走棋网络(落子棋感)与策略网络;胜负棋感则是通过策略网络不断进行自对弈得到。
  2. 搜索验证:搜索引擎采用蒙特卡洛搜索树根据落子棋感与胜负棋感不断展开搜索树。

国外机器博弈在不完备信息博弈的研究代表是美国卡耐基梅隆大学开发的德州扑克博弈系统 Libratus。主要包括三个关键模块:

  1. 赛前纳什均衡近似,让Libratus自己学会德州扑克。它将最重要的博弈信息(如针对某一手牌对应的战略)进行抽取,再应用强化学习算法进行提升。
  2. 残局解算,让 Libratus 不仅能在比赛前学习,还能在比赛中学到东西。科学家从下往上构建博弈树,得以较容易地算出最下面节点的状态,再反过来指导设计上面的博弈树,并使用蒙特卡洛方法,每次选一些节点更新上面的策略。
  3. 持续自我强化。在游戏中发现问题所在,并找到更多细节进行自我强化,得到更好的纳什均衡。

目前,机器博弈也带动了游戏产业、智慧医疗、智能交通、航空、航天等相关产业中,特别是与军事国防领域的产业,催生新型武器与系统。

尽管机器博弈取得了巨大的成果,但依然存在一定局限性。具体包括:

  1. 应用拓展方面仍有提升空间;在具有模糊性和随机性的麻将、桥牌、斗地主、多国军旗等非完备信息博弈上,虽然在基于案例的策略研究上有一定进展,但相关研究还不成熟,开发的程序智力有限,目前还难以战胜人类顶级高手,存在一定的提升空间。
  2. 在相关技术产业化方面,产学研结合还有不足之处。一方面,相关企业缺乏机器博弈的专业人才,特别是顶级人才的支持;另一方面,机器博弈领域专家、学者们缺少相关部门、企业给予的研发资金支持。

在国内外,包括国际象棋人机博弈大赛、围棋人机与机机博弈大赛、桥牌计算机博弈大赛、德州扑克人机与机机博弈大赛、中国象棋人机与机机博弈大赛、中国计算机博弈大赛等多项赛事,本白皮书也做了详细的介绍与回顾。

原文发布于微信公众号 - AI科技评论(aitechtalk)

原文发表时间:2017-10-31

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏区块链大本营

股权众筹鼻祖Naval Ravikant发表36条对于区块链乃至整个世界的思考,不得不读!

34311
来自专栏贾老师の博客

支付业务背景知识梳理之一: 复试记账

952
来自专栏数据的力量

HR必备的88个关键知识及管理工具

2047
来自专栏Crossin的编程教室

学了量化交易之后能做什么样的事情?

毕竟,P2P和空气币的惨剧谁都不想发生在自己身上。长期来看,低风险才能走的更远。 学了量化交易之后,具体可以做什么样的事情呢?在这里举几个例子:

1073
来自专栏晓枫说

趋利避害,数字货币市场迎来大资管时代

巴菲特的段子很多,比如这个“鸡汤”:一个人从现在开始,每年存1.4万元,并且获得每年平均20%的投资回报率,40年后财富会增长为1亿零281万元。不过,对于大部...

1565
来自专栏数据猿

天云数据副总经理李从武:大数据实践三部曲

<数据猿导读> 2016中国信息大数据通信大数据大会在京召开,天云数据副总经理李从武在大会上发表了以“大数据实践三部曲”为主题的演讲。他主要格局整个大数据从平台...

1943
来自专栏AI科技大本营的专栏

9名华人当选,包揽总人数1/6!2017 ACM Fellow名单公布,华人强势亮相

翻译 | AI科技大本营(ID:rgznai100) 参与 | 林椿眄 纽约时间2017年12月11日--计算机协会ACM公布了新当选的Fellow名单,共54...

2865
来自专栏人工智能快报

人工智能对冲基金创造出数字货币

据https://motherboard.vice.com报道,金融交易界已经被数据分析主导,而美国旧金山一家新成立的对冲基金Numerai则更进了一步。 说起...

3779
来自专栏量化投资与机器学习

【年度系列】经过多年交易之后你应该学到的东西(深度分享)

公众号推送了很多技术类的文章,今天为大家带来一篇软文,直指交易实战。所有策略、算法等,可能都需要经过实践的检验和不断的改进才有可能为你带来一定的财富,但也不是永...

873
来自专栏大数据文摘

【译】大数据如何改变金融?

1367

扫码关注云+社区