从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 条评论
登录 后参与评论

相关文章

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

最懂机器学习的围棋高手,解读柯洁首战AlphaGo时的失误

解读柯洁大战AlphaGo,当然离不开围棋界最懂机器学习的高手。 本次,我们很荣幸邀请到围棋队的电脑专家——余平大师,来为我们讲解第一盘人机大战。 首先,当然...

2859
来自专栏顶级程序员

AlphaGo之父:关于围棋,人类3000年来犯了一个错

转自澎湃新闻 “我会抱必胜心态、必死信念。我一定要击败阿尔法狗!” 对于5月23日至27日与围棋人工智能程序AlphaGo(阿尔法狗)的对弈,目前世界排名第一...

3657
来自专栏镁客网

人工智能里程碑,谷歌AlphaGo击败围棋冠军!

2013
来自专栏AI科技评论

学界丨CMU风头被抢,新型DeepStack算法抢先攻克德州扑克图灵测试

在国外的学术圈里,有一份论文火了。论文里进行的研究表明,人类历史上第一次,AI在德州扑克游戏上赢得了人类职业玩家。而这份论文的突破性意义在于:AI在非完整信息的...

4039
来自专栏AI科技评论

AlphaGo 将在 2017 年重磅复出,业内人士怎么看?

今日,DeepMind CEO Demis Hassabis 在 Twitter 上发布声明:他们正在全力提高 AlphaGo 的智能程度,全新版 AlphaG...

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

【重磅】AI击败顶级德扑玩家的秘密!德扑AI创造者现身reddit,全面解答34个提问,详解Libratus的现状和未来

翻译:刘畅、reason_W 编校:reason_W 编辑:鸽子 今年上半年,继AlphaGo多次升级连克人类高手之后,德州扑克终于也迎来了它的“破壁人”——...

3004
来自专栏人工智能头条

吴韧:“异构神机”强于Google AlphaGo 专注类脑芯片、调参是错误

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

人工智能领域里程碑:AlphaGo战胜围棋9段选手

? 3月9日消息,代表人类出战的李世石九段与谷歌DeepMind人工智能程序“阿尔法围棋”之间历史性的人机大战3月9日在首尔四季酒店拉开序幕。首局谷歌...

38212
来自专栏新智元

DeepMind创始人:AlphaGo破解围棋3000年奥义,超越人类认知极限

【新智元导读】AlphaGo之父杰米斯·哈萨比斯(Demis Hassabis)近日在母校英国剑桥大学做了一场题为“超越人类认知的极限”的演讲,解答了世人对于人...

3634
来自专栏新智元

40张图看懂扑克AI对抗人类30年历史,解密冷扑大师前世今生

【新智元导读】2017年是AI在扑克上取得突破的一年,冷扑大师Libratus和DeepStack 相继完胜人类,实现对人类专业级玩家的超越,毫无疑问是里程碑式...

2998

扫码关注云+社区