中国人工智能学会:2017中国人工智能系列白皮书——智能博弈(101页).pdf
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中国人工智能系列白皮书 中国人工智能学会 2017中国人工智能系列白皮书 中国人工智能系列白皮书2017 2017 中国人工智能系列白皮书 中国人工智能系列白皮书2017 中国人工智能学会
- 资源描述:
-
1、 中国人工智能系列白皮书中国人工智能系列白皮书 -机器博弈机器博弈 中国人工智能学会中国人工智能学会 二二一七年五月一七年五月 2 目 录 第 1 章 引言. 1 第 2 章 机器博弈的发展状况 . 5 2.1 机器博弈历史 . 5 2.2 机器博弈研究现状 . 7 2.2.1 国外的研究现状 . 8 2.2.2 国内的研究现状 . 10 2.3 机器博弈产业现状 . 11 2.4 面临的问题与展望 . 12 第 3 章 博弈的复杂度 . 15 3.1 概述. 15 3.2 博弈问题的状态复杂度及其估算方法 . 17 3.2.1 博弈问题的状态复杂度定义 . 17 3.2.2 博弈问题的博弈树
2、复杂度 . 20 3.3 博弈问题的计算复杂性 . 24 第 4 章 机器博弈的典型技术 . 28 4.1 概述. 28 4.2 穷尽搜索 . 28 4.3 裁剪搜索 . 29 4.4 启发式算法 . 30 4.5 迭代深化 . 31 4.6 最佳优先算法 . 31 4.7 随机搜索算法 . 32 4.8 并行计算 . 33 4.9 遗传算法 . 34 3 4.10 神经网络 . 35 4.11 机器学习 . 35 第 5 章 机器博弈的平台技术 . 38 5.1 计算机博弈平台概述 . 38 5.2 计算机博弈平台的分类 . 38 5.3 计算机博弈平台的设计规范 . 39 5.3.1 人机
3、交互接口规范 . 39 5.3.2 平台与引擎通信的协议规范 . 40 5.4 计算机博弈平台的相关技术 . 40 5.5 计算机博弈平台应用实例 . 41 第 6 章 完备信息机器博弈的专项技术 . 43 6.1 六子棋机器博弈 . 43 6.1.1 概述 . 43 6.1.2 六子棋机器博弈主要技术 . 43 6.2 围棋机器博弈 . 46 6.2.1 概述 . 46 6.2.2 围棋机器博弈主要方法 . 47 6.3 点格棋计算机博弈 . 50 6.3.1 概述 . 50 6.3.2 点格棋机器博弈主要技术 . 51 6.4 爱恩斯坦棋机器博弈 . 54 6.4.1 概述 . 54 6.
4、4.2 爱恩斯坦棋机器博弈主要技术 . 56 第 7 章 非完备信息机器博弈的专项技术 . 60 7.1 德州扑克机器博弈 . 60 7.1.1 概述 . 60 4 7.1.2 非完备信息动态博弈解的主要方法 . 61 7.2 军棋机器博弈 . 63 7.2.1 概述 . 63 7.2.2 军棋机器博弈主要技术 . 64 7.3 桥牌机器博弈 . 67 7.3.1 概述 . 67 7.3.2 桥牌机器博弈的主要方法 . 68 第 8 章 机器博弈的国内外赛事 . 72 8.1 国际机器博弈赛事 . 72 8.1.1 国际象棋人机博弈大赛 . 72 8.1.2 围棋人机与机机博弈大赛 . 73
5、8.1.3 桥牌计算机博弈大赛 . 75 8.1.4 德州扑克人机与机机博弈大赛 . 75 8.1.5 其它赛事与研究成果 . 76 8.2 国内机器博弈赛事 . 76 8.2.1 中国象棋人机与机机博弈大赛 . 76 8.2.2 中国计算机博弈大赛 . 77 第 9 章 结束语. 79 参考文献 . 81 1 第 1 章 引言 计算机博弈也称机器博弈(Computer Games),英文直译应该是计算机游戏,其覆盖面非常广泛。然而,从事计算机棋牌竞技研究的科学家们,很早便将 Computer Games 定义为让计算机能够像人一样会思考和决策, 能够下棋。 为此还成立了 Internatio
6、nal Computer Games Association(ICGA国际机器博弈协会),专门组织世界范围内的棋类(后又加入牌类)博弈竞赛和学术交流。为了和计算机游戏区别开来,Computer Games 中文名字便称之为机器博弈,或者计算机博弈。 负责组织全国范围内的棋牌类博弈竞赛和学术交流的群众组织便是中国人工智能学会下属的机器博弈专业委员会。 机器博弈的第一个里程碑成果是 1997年IBM深蓝战胜世界棋王卡斯帕罗夫。虽然此项成果震动了世界,但在中国只是成为广为流传的消息, 却没有在学术界引起足够的重视和兴趣。 除去中国台湾之外,在中国大陆计算机博弈还只是极个别人的个人行为。当谷歌的Alp
7、haGo 战胜了围棋世界冠军李世石, AlphaGo 的升级版 Master 横扫了包括中国在内的 60 位世界顶尖高手,中国人才认识到机器博弈太可怕了,而我们在这一领域已经落后了太多。 人生如棋,世事如棋,而围棋又是各种棋类中公认最难以驾驭的棋种。计算机博弈在围棋上的骄人战绩,无疑显示出人工智能即将达到登峰造极的时代,人工智能将改变人类的生产和生活方式。人们开始研究 AlphaGo 的技术和能力,这也把计算机博弈推向了新的高度。 如果要盘点一下中国的计算机博弈, 那最值得一提的是电脑围棋先行者中山大学化学系教授陈志行(19312008)。陈老先生 1991年退休后潜心研究电脑围棋, 在苹果机
8、上用汇编语言编写了博弈程序手谈,并且赢得了 19951997 连续 3 年的 6 项世界冠军,成为机器博弈史上的一朵奇葩。 当晚年的陈老得知国内组织了计算机博弈全国锦标赛时,兴奋不已,抱病参加了在重庆理工大学举行的 2007 2 年第二届全国锦标赛(不计名次),还亲自指导年轻人开发软件。陈老先生是我们的楷模,也是中国人的骄傲。 再值得提及的便是许峰雄博士。 他台湾大学毕业后到美国卡内基梅隆攻读博士学位,特别钟爱国际象棋计算机博弈。他在毕业后到IBM 公司组织了深蓝课题组,并在 1997 年以战胜卡斯帕罗夫的辉煌战绩赢得了世人的尊重。 计算机博弈在中国大陆虽然“迟到”、姗姗来迟,但发展非常迅速。
9、2005 年,中国人工智能学会成立了机器博弈专业委员会,一批热心这一领域的科技工作者开始学习国际的先进理论与算法, 很快便把国际象棋的算法移植到中国象棋的电脑程序当中, 并取得了令人触目的成果。东北大学的棋天大圣代表队夺得了由 ICGA 组织的 2006、2007 年国际棋类奥林匹克大赛中国象棋冠军。而且,2006 年首届中国象棋计算机博弈锦标赛在北京科技馆成功举行, 期间举办了人机大战,挑战了中国象棋的顶尖高手许银川、柳大华、徐天红、卜凤波等特级大师,并取得势均力敌的战绩,令国人刮目相看,但并未掀起预期的热潮,但却推动了全国锦标赛每年一届的举行。而且,在 2011年还得到了教育部计算机类专业
10、教学指导委员会的赞同, 开始共同主办全国大学生计算机博弈大赛,使得比赛项目数不断增加,参加的队伍规模也不断壮大。竞赛棋种不仅有完备信息动态博弈项目,如中国象棋、围棋、点格棋、亚马逊棋等,还有非完备信息博弈项目,如幻影围棋、军棋等,还有考虑随机因素的爱恩斯坦棋。自 2013 年起,还增加了多人博弈的扑克项目,如斗地主和桥牌,使得关于博弈算法的研究更加全面和深入。特别值得提及的在,2015 年得到国家体育总局棋牌运动管理中心支持,将该项比赛纳入 2015 年第三届全国智力运动会,进一步扩大了比赛的影响力和知名度。 十年来,计算机博弈在中国大地上蓬勃发展,很多院校开展了以机器博弈为内容的学生科技竞赛
11、活动, 很好地带动了校园科技活动的 3 氛围,也很好地培养了学生的科研能力和创新意识。这使得计算机博弈活动在中国从无到有,从小到大,至今可以说中国是世界上参与人数最多、比赛规模最大的国家。 这项比赛之所以能不断发展, 最关键的原因就是计算机博弈有着强大的生命力,契合了大学生对棋牌游戏天然的兴趣和喜爱。表面上看,每届参与人数有限,这是受限于比赛规则和条件,比如规定每所高校在每个项目中最多只能报名 2 支队伍, 加上高校参赛差旅费用限制。因此考虑到各个学校的选拔赛在内,保守估计实际能到场参赛的人数是实际参与这项科技活动人数的 1/5,那么,实际参加计算机博弈活动的人数将是数以千计的。 计算机博弈的
12、强大生命力主要源于以下方面:1)参赛成本低,学生只要有一台电脑就可以开展研究,参加比赛;2)没有专业限制,会下棋、或会编程,就可以参加这项活动;3)下棋本身就是游戏,活动本身具有很好的高趣味、强吸引力;4)比赛具有强挑战性和不确定性,比如这届胜了,并不能保证下届还胜,因此,研究没有止境、不是一蹴而就,是创新活动的不竭研究宝库;5)下棋规则简单、输赢结果立判,不需要专家评审、打分,真正实现公开、公平、公正;6)适合分工合作和团队作战,在研究与开发中使得学生的技能和素质得到全面锻炼;7)有一定的网络化和产业化前景,很容易进入信息化和互联网+的项目当中;8)培养学生创新能力、职业素养明显,极大促进学
13、生就业能力。 此外,中国要想成为计算机博弈强国,就要加强博弈理论和算法的深入研究。为此,我们专委会在中国控制与决策学术年会(CCDC)上开辟了计算机博弈特邀专题,开展成果交流,提高我国在该领域的学术水平和学术影响。 本 机器博弈白皮书 是机器博弈宣传和普及工作的继续和深化,为此专委会邀请了这一领域的同行专家共同撰写。首先,介绍了机器博弈的发展过程、国内外赛事、博弈典型技术和比赛平台,然后结合 4 相关棋种介绍了各种专项博弈技术,既包括完备信息的棋类比赛,还包括不完备信息的牌类游戏搜索算法,当然还包括目前最先进的AlphaGo 的深度学习算法、最新的桥牌和德州扑克博弈算法等。 机器博弈的产业化前
14、景也是很可观的。AlphaGo 的成功,标志着人工智能进入了新的阶段, 深度学习算法得以在各个领域的广泛重视和应用。 丰富多彩的博弈搜索算法无疑可以应用到面对决策优化的各种场合。随着不完全信息博弈、随机环境博弈搜索算法的不断完善,也将在兵棋推演和战略、战役和战术博弈中加以应用。博弈是人类经济、政治、军事、反恐、治霾和日常生活中无所不在的内容,机器博弈的概念和技术也必然大有用武之地。 让计算机博弈活动在更多的学校中生根、开花、结果,这是专委会一直追求的目标。让我们走出去,在国际大赛中夺取更多的奖牌,为国争光。同时,借助计算机博弈活动,促进产学研相结合,推动我国人工智能技术的发展,加速我国早日成为
15、人工智能领域的大国、强国。 5 第 2 章 机器博弈的发展状况 2.1 机器博弈历史 早在人类文明发展初期,人们就开始棋类博弈的游戏。1928 年,被称作计算机之父的冯诺依曼(John von Neumann)通过对两人零和一类博弈游戏的分析,提出了极大极小值定理,证明了博弈论的基本原理。在冯诺依曼和摩根斯特恩合著的博弈论和经济行为(1944)中,将二人博弈推广到 n 人博弈结构,并将博弈论系统应用于经济领域,从而奠定了机器博弈研究的基础和理论体系。 近代计算机博弈的研究,是从上世纪五十年代开始的。许多世界上著名的科学家, 例如数学家和计算机学家阿兰图灵 (Alan Turing) ,信息论创
16、始人科劳德香农(Claude E. Shannon),人工智能的创始人麦卡锡(John McCarthy)以及冯诺依曼等人都曾经涉足计算机博弈领域的研究工作,并为之做出过非常重要的贡献。 1950 年,著名的控制论先驱香农提出了象棋博弈的编程方案。1953 年,阿兰图灵设计了一个能够下国际象棋的纸上程序,并经过一步步的人为推演,实现了第一个国际象棋的程序化博弈。1958 年,IBM 推出取名“思考”的 IBM704,成为了第一台与人类进行国际象棋对抗的计算机。虽然在人类棋手面前被打得丢盔卸甲,但许多科学家却对此欢欣鼓舞。1959 年,人工智能的创始人之一塞缪(AL Samuel)编写了一个能够
17、战胜设计者本人的西洋跳棋计算机程序,1962 年该程序击败了美国的一个州冠军,这是计算机博弈历程中一个重要的里程碑。 随着计算机硬件和软件技术的不断发展,通过人-机或者机-机对弈,实现了计算机硬件性能和计算机软件水平的较量。科学家们开始对电脑能否战胜人脑这个话题产生了浓厚的兴趣, 提出以棋类对弈的方式,向人类智能发起挑战。 6 上世纪八十年代中期, 美国卡耐基梅隆大学开始研究世界级的国际象棋计算机程序;1988-1989 年间,IBM“深思”分别与丹麦特级大师拉尔森、世界棋王卡斯帕罗夫进行了 “人机大战”。 从上世纪九十年代起,Tcsauro 的 TD-GAMMON 西洋双陆棋程序经过上百万盘
18、的学习训练, 程序达到世界水平; “深思” 二代产生,吸引了前世界棋王卡尔波夫和世界优秀女棋手小波尔分别前来与之对抗(1990 和 1993 年)。特别是“深蓝”(1996 年)、“超级深蓝”(1997 年)与卡斯帕罗夫的两场比赛,引起全球媒体的关注。在随后的几年里, 计算机与卡斯帕罗夫和克拉姆尼克等世界顶级棋手进行了一系列的比赛,计算机逐渐负少胜多,表现得越来越聪明。 经过多年对计算机博弈进行系统的理论研究,在国际象棋、中国象棋等棋种的人机大战中,从最初人类完胜电脑,到如今电脑击败人类顶级高手,计算机博弈水平迅速上升。特别是,2016-2017 年,AlphaGo 分别与李世石、柯洁的人机围
19、棋大战并取得胜利,这可谓是人机对抗史上的最强之战,从而掀起全球人工智能热潮。 此外,除了 AlphaGo 完备信息机器博弈领域的人工智能划时代成就外,2007 年 1 月 30 日,美国卡耐基梅隆大学开发的德州扑克博弈系统 Libratus 与 4 名人类顶尖德州扑克选手之间进行了“人机大战”,宣告在“多人”博弈的非完备信息机器博弈领域,人工智能同样取得了胜利。2017 年 4 月 610 日,备受关注的亚洲首度人工智能与真人对打的扑克大赛“冷扑大师(Libratus 扑克机器人)与中国龙之队”扑克巅峰表演赛在海南收官,最终以“冷扑大师”获胜,赢得 200 万元奖金,这是人工智能在各种棋牌博弈
20、中对人类取得的又一个胜利。再次在全球范围加剧了对人工智能的敬畏或恐惧气氛。 在中国国内,也有一些学者从事计算机博弈方面的研究。比如,南开大学黄云龙教授和他的学生吴韧在上世纪八十年代开发了一系 7 列中国象棋程序; 中山大学化学系教授陈志行先生在九十年代初开发了围棋程序“手谈”,并获得世界冠军;本世纪初,东北大学的徐心和教授和他的学生王骄、徐长明等研究开发了中国象棋软件“棋天大圣”,并在 2006 年的人机大战中,展现了具有挑战国内中国象棋顶级高手的实力,表现出较高的智能;南京航空航天大学夏正友教授指导学生研究开发了具有一定智能的四国军棋博弈系统; 北京邮电大学的刘知青教授带领学生开发的“本手(
21、LINGO)”围棋程序,能够战胜具有一定水平的业余围棋选手; 哈尔滨工业大学王轩教授的团队开发的德州扑克博弈系统,2013-2016 年间多次参加 ACPC 二人非限制性、三人及多人德州扑克比赛,均进入决赛前 4 名。 这项活动最重要的事件是由东北大学徐心和教授发起成立的中国人工智能学会机器博弈专业委员会,以及从 2006 年起每年一届的中国大学生计算机博弈大赛暨中国计算机博弈锦标赛1,至今已经举办 12 届。沈阳航空航天大学王亚杰教授在国内大力推广计算机博弈活动,规范比赛规则,吸引越来越多高校师生参与计算机博弈相关研究中来,中国计算机博弈进入了快速发展阶段2。特别是教育部高等学校计算机类专业
22、教学指导委员会参与进来成为共同主办单位, 这些对我国计算机博弈技术的研究与发展起到了极大的促进作用。 近几年来,国内许多企业如腾讯、百度、联众、新睿等纷纷加入到机器博弈的研究大军中,开发出一些具有较高智能水平的产品。如腾讯人工智能实验室 (AI Lab) 研发的围棋人工智能程序 “绝艺” (Fine Art),夺得 2017 年第 10 届 UEC 杯计算机围棋大赛冠军;北京邮电大学的刘玉璋和杨放春教授带领创业团队开发的新睿桥牌机器人, 在2017 年第 21 届世界计算机桥牌锦标赛中获得亚军。 2.2 机器博弈研究现状 DeepMind 公司创始人 Demis Hassabis 曾言:“游戏
23、是测试人工智能算法的完美平台”。而计算机博弈被誉为是人工智能学科的“果 8 蝇”,通过机器博弈的过程来理解智能的实质,是研究人类思维和实现机器思维最好的实验载体。 2.2.1 国外的研究现状国外的研究现状 在计算机博弈研究的早期阶段, 研究的主要内容涉及如何建立有效、快速地评价函数和评价方法,使评价的效率更高,花费的时间和空间的代价更小, 以及如何在生成的博弈树上更准确有效地找到最优解,并由此衍生出搜索算法的研究成果。在随后的几十年里,专家和学者们在计算机博弈搜索与评估方面进行了大量深入探索和实质性的研究,产生了许多计算机博弈技术,如极大极小搜索、负极大值搜索、Alpha-Beta 剪枝、并行
24、搜索算法等3-7。 特别值得讲述的是,2006 年多伦多大学教授 Geoffery Hinton 发表文章提出了基于深度信念网络(Deep Belief Networks, DBN)可使用非监督的逐层贪心训练算法8,9, 在学术界掀起了对深度学习 (Deep Learning)的研究热潮。随着并行计算、基于人工神经网络的深度学习10,11等技术的突破性进展,成功解决了机器博弈中抽象认知的难题。使得深度学习等技术被成功应用于计算机博弈及相关领域中,从而将机器博弈水平带上了一个新的台阶。 Google、百度等国际大公司争相跟进,研发出相关的机器博弈产品。尤其是 Google 公司的围棋软件 Alp
25、haGo,作为完备信息博弈代表,它具有极强的自学能力,如图 2-1 显示了 AlphaGo 的算法组成。 图图 2-1 AlphaGo 算法组成算法组成 AlphaGo深度学习网络蒙特卡洛搜索树(MCTS)策略网络(Policy Network)价值网络(Value Network)基于线性回归模型的快速走棋策略基于CNN的策略网络 9 AlphaGo 的技术突破被学者们总结为两个关键技术: 棋感直觉和搜索验证。其中,棋感直觉通过深度学习(Deep Learning)获得,它分为落子棋感和胜负棋感,AlphaGo 通过对 3000 万的经典棋局进行深度学习得到快速走棋网络和策略网络, 而快速走
展开阅读全文
