中国人工智能学会：2017中国人工智能系列白皮书——智能博弈（101页）.pdf

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 万的经典棋局进行深度学习得到快速走棋网络和策略网络， 而快速走

26、棋网络就是落子棋感；胜负棋感是通过深度学习得到的策略网络不断进行自对弈来得到； 搜索验证指的是搜索引擎主要采用蒙特卡洛搜索树根据落子棋感和胜负棋感不断展开搜索树12 。围棋程序 AlphaGo 的成功充分验证了深度学习与计算机博弈技术结合的实用性。Google 公司宣布将其应用于医疗诊断等领域，以扩大深度学习应用领域。 此外， 不完备信息博弈以美国卡耐基梅隆大学研发的德州扑克博弈系统 Libratus 为代表，被学者们总结为主要包括三个关键模块： （1）赛前纳什均衡近似（Nash equilibrium approximation before competition）。这个模块把最重要的博弈

27、信息（例如针对某一手牌对应的战略）进行抽取，然后再应用强化学习等方法，继续寻求提高和改进。这里使用了一个新的算法：蒙特卡洛反事实遗憾最小化。在这个模型的帮助下，Libratus 自己学会了德州扑克，而且比以前速度更快。 （2）残局解算（Endgame solving）。这是 Libratus 最重要的部分，因为一局德扑只需要几个回合，耗费时间短。因此 Libratus 的开发者们选择从下往上构建博弈树， 这样最下面节点的状态是比较容易算出来的，用这个状态反过来指导设计上面的博弈树，并使用蒙特卡罗方法， 每次选一些节点去更新它们上面的策略。 也就是说， Libratus不仅仅是在比赛前学习，而且

28、还能在比赛中学到东西。 （3）持续自我强化（Continual self-improvement）。比赛中人类高手会寻找 Libratus 的漏洞，并展开有针对性的攻击。这个模块的作用就是发现问题所在，找到更多细节进行自我强化，然后得到一个更好的纳什均衡。 10 2.2.2 国内的研究现状国内的研究现状 国内计算机博弈研究相对起步较晚，曾经一度参与者寥寥无几，参考文献匮乏，计算机博弈氛围沉寂。本世纪初，东北大学徐心和教授带领团队对中国象棋、 六子棋、 点格棋等机器博弈展开了深入研究，在国内高校举办各类计算机博弈技术培训与讲座， 申请控制与决策国际会议（CCDC）机器博弈专题，极大地促进了国内计

29、算机博弈的研究与发展。 近几年，学者们结合棋牌各自特点，针对计算机博弈搜索、评估与优化等方面开展了深入研究。例如，对于局面估值问题，文献13提出结合时间差分算法和反向传播神经网络， 设计一种局面估值算法实现评估函数参数的自动调整；针对六子棋，东北大学徐长明对局面表示等关键技术进行研究14,15， 重庆理工大学张小川教授提出应用遗传算法优化评估函数16，安徽大学李学俊教授等提出基于局部“路”扫描方式的博弈树生成算法17； 针对中国象棋， 东北大学王骄教授对计算机博弈开局库18、 循环判定规则19、 评估函数参数组的自动调整和优化20展开了研究； 针对苏拉卡尔塔棋， 北京信息科技大学李淑琴教授等根

30、据棋子的数量、移动范围等不同参数，对局面评估函数进行了研究21； 辽宁石油化工大学张利群教授提出了一个网络博弈平台吃子算法22； 针对亚马逊棋， 沈阳航空航天大学邱虹坤等对搜索算法进行了分析23-24， 李淑琴教授根据特征权重值给出一个分阶段的评估函数25；中央民族大学李霞丽和吴立成教授提出一种围棋多模态算法，及基于小样本的藏棋博弈算法26,27； 哈尔滨工业大学王轩教授团队针对德州扑克等博弈系统， 开展了非完备信息机器博弈中风险及对手模型的研究28-30。 AlphaGo 和 Libratus 等机器博弈 AI 的成功，引发了国内外学者和企业广泛地关注与研讨。国内知名企业如百度、腾讯等设计并

31、实现了具有深度学习能力的机器博弈 AI。 11 总之，经过国内外学者们多年努力，对于状态空间和搜索树复杂度都较大的完备信息人机博弈（例如围棋、中国象棋）而言，经过学习训练，计算机可以战胜人类顶级棋手。在二人零和完备信息博弈研究方面，尤其是关于深度学习技术的研究与运用，机器博弈为人工智能提供了很多重要方法和理论。此外，在非完备信息人机博弈方面，德州扑克项目也取得了战胜人类的惊人成果，达到了新高度。 2.3 机器博弈产业现状 近几年，机器博弈不仅在学术界掀起了对其研究的热潮，还带动与之高度密切相关的游戏产业飞速发展。 人工智能不仅提高了游戏的趣味性，还使游戏变得更精致。 从 2001 年到 201

32、7 年，游戏产业从冬眠期醒来，经历了起步、成长、成熟的过程。根据产业调查显示，全球游戏市场总体增速在 10%左右，主要驱动力在手机游戏。2015 年移动游戏收入占移动应用市场总收入的 85%， 达到 348 亿美元， 2016 年移动游戏的收入达到 415亿美元，预计 2020 年将增至 746 亿美元。 相对于国外，我国游戏产业发展较快，2014 年中国游戏的营业收入已超过 1100 亿元， 是电影票房的 3 倍以上， 其游戏收入的 63.5%源自国产游戏。2016 年中国游戏整体营收超过 1400 亿人民币，超过美国和日本，成为世界最大游戏市场。另外，国家对电子竞技的发展给予了大力支持，除

33、了将电子竞技纳入第 99 个体育项目外，还将电子竞技纳入教育部增补专业。 在机器博弈领域，学术界与产业界结合日趋紧密。庞大的机器博弈产业吸引了众多公司争相跟进， 企业积极与从事机器博弈领域研究的专家学者展开多方位的合作， 将学者们的科研成果转化为具有更高人工智能水平的产品。 比如北京邮电大学刘玉璋教授创建的新睿桥牌机器人，开启了崭新的计算机游戏新商业模式，已经发展成为全球最大的桥牌游戏平台， 目前他们又引进重庆理工大学张小川教授带领团 12 队研制的斗地主全国冠军引擎， 旨在具有最广泛群众娱乐活动的斗地主游戏中，探索机器博弈发展的商业新模式，为机器博弈发展注入新动力。 除了游戏产业，机器博弈技

34、术还逐步被应用到智慧医疗、智能交通、 航空、 航天等相关产业中， 特别是与军事国防领域的产业相结合，催生出许多新型智能武器与系统。例如：军用无人机通过引入机器博弈等相关人工智能技术， 操控方式可由传统的遥控逐渐过渡到系统自主智能决策与控制31；在智能化战争模拟（兵棋推演）系统中，可以自动模拟敌方复杂的行为，更加真实地模拟战争的场景，通过虚拟仿真推演军事对抗，将其结果作为决策系统重要可信的依据32-34；在以理解、推理、决策为代表的军用信息系统中，结合深度学习与机器博弈相关技术，推动系统向智能化发展35。 因此，随着机器博弈与相关领域产学研相结合，机器博弈技术真正进入实用阶段，在我国智能化建设中

35、展示了巨大的潜在应用价值。大批机器博弈科研人才将成为民用、军工企业发展的强大技术引擎，对引领未来的机器博弈相关产业的发展，必将产生深远影响。 2.4 面临的问题与展望 在过去的几十年里， 尽管机器博弈研究成果对于推动人工智能的发展具有重要意义，但在计算机博弈领域仍存在不同程度的局限性。具体表现为： （1）在学术研究方面，尽管深度学习等技术在围棋方面取得了前所未有的成功，但在其应用拓展方面，仍有许多值得研究和探索之处。另外，对于具有模糊性和随机性的麻将、桥牌、斗地主、多国军旗等非完备信息博弈，虽然在基于案例的策略研究方面有了一定进展，但因其相关研究还不成熟，开发的程序智力有限，目前仍难以战胜人类

36、顶级高手，尚有很大的提升空间。 （2）在相关技术产业化方面，产学研结合仍有不足。表现为： 13 一方面，相关企业缺乏机器博弈领域的专业人才，特别是缺少机器博弈领域顶级专家的技术支持；另一方面，机器博弈领域专家、学者们缺少相关部门、企业给予的研发资金支持。 从学术研究和相关技术产业化来看， 我国对机器博弈技术的研发与应用相对于国外存在较大的差距。 开发具有高效自主学习能力与抽象思维能力的智能博弈系统， 特别是在非完备信息和不确定性机器博弈方面，还有很长的路要走。此外，只有将机器博弈技术作为战略核心予以关注， 不断加大投入， 在未来竞争中， 我国才能处于不败之地。 国务院近期印发的新一代人工智能发

37、展规划给我国人工智能发展指明了道路，为机器博弈发展注入新的活力并带来更多机遇，规划中明确提出：开展综合深度推理与创意人工智能理论与方法、非完全信息下智能决策基础理论与框架、 数据驱动的通用人工智能数学模型与理论等研究；支持开展人工智能竞赛。相信在国家层面政策的支持下，我国计算机博弈领域的研究与应用将进入快速发展的新阶段。未来计算机博弈将呈现多学科技术融合、人机协同、产学研相结合等趋势36。具体体现在： （1）计算机博弈研究的内容将不断拓宽，处理的问题复杂程度越来越高，信息量将越来越大。为解决某类特定问题，技术方法将集成化，计算机博弈技术将与并行计算、大数据、知识工程等相关技术紧密结合。 （2）

38、计算机博弈软件与硬件的结合越来越密切，固化博弈系统的智能硬件产品将越来越多的出现在人们的生活中，典型的应用包括：有博弈思维能力的机器人、智能决策控制系统的无人驾驶汽车和无人机等。 （3）计算机博弈将融入各个领域的应用中，在此基础上可以开展一系列人工智能领域的科学研究。 计算机博弈越来越注重实际工程应用，紧密地结合经济、医疗、航空航天等领域，解决实际问题。特 14 别在航空航天领域的多学科协同综合设计、 虚拟现实仿真及人机交互智能游戏与教育方面，拥有广阔的应用前景。 （4）计算机博弈技术将呈现高度智能化趋势，通过与遗传算法、人工神经网络、类脑思维等人工智能技术进一步融合，类似基于神经网络深度学习

39、的智能技术将大量涌现， 使得计算机博弈程序的类脑智能越来越高。 （5）合理拓展现有博弈技术，深入研究更加智能的普适算法，构建一个通用计算机博弈系统，将成为未来计算机博弈研究的重点。 （6）作为计算机博弈技术交流与验证的平台，中国计算机博弈比赛将越来越被社会所认同。 各种新技术将会被越来越多地运用到计算机博弈中。 （7）学术界与产业界的结合日趋紧密，计算机博弈研究学术成果加速向产业化转变，助力游戏开发、智能医疗、航空航天企业，促进计算机游戏、智能医疗、航空航天、国防等相关产业发展。 可以预见，在计算机博弈领域越来越多的人机博弈项目中，人类终将被战胜。机器智能的胜利，既是人类创造力与智慧的结晶，也

40、是科学发展的必然，同样也是人类最终的胜利。 15 第 3 章 博弈的复杂度 3.1 概述 计算机博弈属于人工智能领域的一个重要分支。 计算机的博弈水平代表了计算机的智能水平。 计算机博弈问题的状态复杂度和博弈树复杂度是衡量其复杂程度的两个重要标准。图 3-1 给出了求解博弈问题一般采取的四种策略。比如，博弈问题常用到的剪枝算法，它是为了避免分支过于庞大而采取的一种策略。 这种策略可以节省计算机的内存空间，提高搜索效率，但也存在一定的风险，即如果估值函数不能准确地评估局面的话，这种算法可能将存在最佳着法的分支剪掉。当然，若博弈树复杂度比较小，就可以采用蛮力搜索的方式，只要时间允许，就可以找到最佳

41、着法。 策略策略3采用知识库，可以求解。策略策略1采取任何方法，都可求解。策略策略2采用蛮力搜索，可以求解。策略策略4采用任何方法，都不能求解。状态复杂度博弈树复杂度图图 3-1 博弈问题的复杂度与求解策略之间的关系博弈问题的复杂度与求解策略之间的关系 文献37讨论了博弈问题的状态复杂度及其博弈树复杂度对寻找博弈问题理论解的意义， 认为一个较低的状态复杂度比一个较低的博弈树复杂度对求解博弈问题所起的作用更大， 因为状态复杂度为通过完全列举求解博弈问题的复杂度提供了一个边界值； 而较低的博弈树复杂度主要是对搜索效率产生较大的影响。文献37还列出了一些 16 常见博弈问题的状态复杂度及博弈树复杂度

42、（见表 3-1）。 表表 3 3- -1 1 一些博弈问题的状态复杂度和博弈树复杂度一些博弈问题的状态复杂度和博弈树复杂度 棋种棋种 状态复杂度状态复杂度 博弈树复杂度博弈树复杂度 西洋跳棋（Checkers） 1021 1031 国际象棋（Chess） 1046 10123 中国象棋 （Chinese Chess） 1048 10150 日本将棋（Shogi） 1071 10226 围棋（Go）（1919） 10172 10360 文献37中，以 tic-tac-toe（三子连珠棋）为例，估算了此博弈问题的状态复杂度和博弈树复杂度。tic-tac-toe 共有 9 个位置可以落子，能够形成的

43、局面较少，因此其复杂度的估算相对容易，具体估算过程如下： （1）对于其状态复杂度，由于棋盘上每个位置有三种状态（双方的棋子和空白），因此，状态复杂度可估算为 39，根据此博弈问题的走棋规则，在棋盘上形成连 3 则游戏结束，出现两个以上的连 3 的局面属于非法局面。而对称相同的多个局面应该只算作一个局面。将这些考虑在内，则更精确的状态复杂度为 5478； （2）对于其博弈树复杂度，平均深度约为 9，第 i（1 i 9）层时， 走棋方可能的走法有 9-i 个， 因此， 此博弈树的叶子节点数 （即博弈树复杂度）为 9！。 计算机博弈的最高境界就是找到该棋种的理想解，即不败解。而计算机博弈的最大困难和

44、无法逾越的障碍则是问题的计算复杂性。 对问题的计算复杂性进行分类，可以了解该问题被求解的难易程度，如果问题被证明是难解的（比如 NP-complete、PSPACE-complete 及EXPTIME-complete），则不必将大量的精力花费在寻找问题的理论解上，而只能去寻求某种近似解。事实上，当前多数人工智能问题都 17 是追求满意解， 大部分原因就是问题的复杂度远远超过当前计算设备能以合理性价比的求解代价， 从而推动着各类博弈算法、 策略的研究。 3.2 博弈问题的状态复杂度及其估算方法 3.2.1 博弈问题的状态复杂度定义博弈问题的状态复杂度定义 博弈过程的局面称之为状态， 博弈问题的

45、状态复杂度是指从初始局面出发， 产生的所有合法局面的总和。 然而， 精确计算博弈问题 （比如：国际象棋、围棋等）的状态复杂度几乎是不可能的38。一般以该棋类可能的局面总数的上限值为标准。 它为通过完全列举求解博弈问题的复杂度提供了一个边界值。 88 的西洋跳棋（Checkers）于 2007 年得到了理论解39，证明过程中，采用了三种方法：证据计数法，残局阶段采用了数据库，通过两个程序实现对节点的估值。不仅证明了一种不败的策略，而且计算了 88 的西洋跳棋可能会产生 500,995,484,682,338,672,639（约 51020）个合法局面。可见，只有得到了理论解的博弈问题，才能比较精

46、确地计算其状态复杂度。估算博弈问题的状态复杂度，与各个博弈问题的走棋规则密切相关，下面以亚马逊和苏拉卡尔塔棋为例，估算这两个博弈问题的状态复杂度。 3.2.1.1 亚马逊棋的状态复杂度 1. 亚马逊棋的走棋规则 棋盘与棋子（棋盘见图 3-2）： 1) 棋盘规模为 1010 个方格，相邻两个方格填充的颜色不同； 2) 比赛双方各有 4 个棋子；每个棋子都相当于国际象棋中的皇后，它们的走棋规则与皇后相同40。 走棋规则： 1) 每次开局由位于棋盘下方的玩家先手； 2) 当轮到一方走棋时，此方只能而且必须移动 4 个棋子中的一个，在移动完成后，该棋子必须释放一个障碍，障碍的释放方法与棋 18 子的移

47、动方法相同（不能穿过障碍）； 3) 当某个走棋方在完成一次移动后， 对方的 4 个棋子均不能再移动时，对方输掉比赛。 图图 3 3- -2 2 亚马逊棋棋盘亚马逊棋棋盘 2. 估算亚马逊棋的状态复杂度 如图 3-2 所示，亚马逊棋棋盘的大小为 1010，共 100 个格，双方棋子的走法与国际象棋的皇后相同 （就是说棋子可以移动到任意一个格子上），因此每个格子可以出现白方棋子、黑方棋子、障碍、空白四种情况，所以亚马逊棋的状态复杂度可以估算为 4100，以 10 为底的形式表示，大小约为 1060。在产生的这些局面中，有很多非法的局面，根据亚马逊棋的规则，棋盘上双方各有 4 个棋子，而这种估算方法

48、，显然有很多局面中出现的棋子数超过了 8 个。 这里从另一个角度来估算其状态复杂度， 由于棋盘上始终存在双方的各 4 个棋子， 也就是说棋盘上有 8 个交叉点需要用来放置这 8 个棋子，而棋盘上的其他交叉点可能的状态为空白或障碍，因此亚马逊棋的状态复杂度可估算为 1041。 3.2.1.2 苏拉卡尔塔棋的状态复杂度 1. 苏拉卡尔塔棋棋规 棋盘与棋子（见图 3-3）： （1）横竖各 6 条边构成正方形棋盘，36 个交叉点为棋位，各边 19 由 8 段圆弧连接，通常用 2 种不同颜色表示。 （2） 红黑双方各 12 枚棋子。 初始状态： 棋子各方底线排成 2 排。 图图 3 3- -3 3 苏拉

49、卡尔塔棋棋盘苏拉卡尔塔棋棋盘 走棋规则： （1）双方轮流走棋，每次走动一枚棋子； （2）除了吃子之外，每枚棋子只能沿着垂直、水平或对角方向走动一格，只能走向空位； （3）吃对方棋子时必须经过至少一个完整的弧线41； （4）赢棋标准：吃掉所有对方棋子或最后剩余棋子多的一方获胜。 2. 估算苏拉卡尔塔棋的状态复杂度 棋盘上总共有 36 个交叉点，每个交叉点有三个可能的状态（即双方的棋子或空白），所以苏拉卡尔塔棋的状态复杂度可估算为 336，以对数值（10 为底）的形式表示，则大小约为 17.2，这些局面中存在一些非法的局面，比如：根据规则，棋盘上最多只能出现 24 个棋子，而以这种估算方法，显然有

50、一些局面中棋子的个数已经超过了24 个。因此，可以换一种角度来估算，根据苏拉卡尔塔的规则，初始状态时，双方各有 12 个棋子，棋盘上最多会出现 24 个棋子，因此应该将棋盘上出现 36 个棋子、35 个棋子、. 、25 个棋子的这些局 20 面去除掉。因此，苏拉卡尔塔棋更精确的状态复杂度以对数值（10为底）的形式表示，则大小约为 16.9。 3.2.2 博弈问题的博弈树复杂度博弈问题的博弈树复杂度 3.2.2.1 博弈树搜索算法原理 对于完备信息的博弈系统，其搜索一般都是基于博弈树搜索算法，如图 3-4 所示，这样可以展开双方所有可能走法产生的局面（博弈树中的节点），再通过估值函数来评价各个局