> **来源：[研报客](https://pc.yanbaoke.cn)** # 中国人工智能学会系列白皮书——棋盘上的人工智能 中国人工智能学会 二〇二五年十一月 # 中国人工智能学会系列白皮书——棋盘上的人工智能 中国人工智能学会 二〇二五年十一月 # 《中国人工智能学会系列白皮书》编委会 主任：戴琼海 执行主任：马华东 副主任：赵春江 何友 王恩东 郑庆华 刘成林 周志华 孙富春 庄越挺 胡德文 杜军平 杨强 委員：陳松灿 董振江 付宜利 高新波 公茂果 古天龙 何清 胡清华 黄河燕 季向阳 蒋田仔 林浩哲 梁吉业 刘奕群 潘纲 石光明 孙茂松 孙长银 陶建华 王海峰 王熙照 王轩 王蕴红 吴飞 于剑 余有成 张化光 张学工 章毅 周鸿祎 周杰祝烈煌 # 本书编写组 张小川 徐勇 王亚杰 李学俊 邱虹坤 李霞丽 周珂 王静文 丁濛 徐心和 李淑琴 杨放春 王骄 徐长明 吴愚 梅险 高强 常晓亚 全书统稿：张小川 徐勇 常晓亚 # 前言 计算机博弈是人工智能领域的重要应用，它以高对抗性的棋牌类游戏项目为研究对象，具有怡神益智、评判客观、挑战无穷的特点。近年来，随着人工智能、大模型等技术的飞速发展，计算机博弈模型能够自主学习复杂的策略和技能、处理更加复杂的博弈任务，成为衡量AI智能水平的重要领域之一。从棋类博弈到电子游戏，机器博弈不仅是技术进步的展示窗口，更是人类智慧与机器智能交互融合的舞台。未来，计算机博弈领域将继续快速发展，技术的融合和创新将推动该领域达到新的高度。 本书编写的指导思想是：通识技术和专项技术相结合，依托具体的棋牌类项目，介绍国内外相关技术的应用方法与进展。本书主要介绍了机器博弈的发展历程、国内外研究现状、复杂度分析、机器博弈的典型技术、平台技术，完备信息博弈和非完备信息博弈的关键技术、以及国内外赛事等，提出了机器博弈未来的发展趋势。期望该书的出版能促进全社会对机器博弈、以及人工智能的整体认知和应用水平。 本书的编写者全部是机器博弈领域资深的高校教师，而且都在不同时期指导学生参加全国计算机博弈大赛获重要奖项，具有较强的理论水平和实践经验。编写分工如下：第1章由东北大学徐心和、安徽财经大学徐勇编写；第2章和第4章由沈阳航空航天大学邱虹坤编写；第3章由沈阳大学高强编写；第5章由哈尔滨理工大学梅险编写；第6.1节由东北大学秦皇岛分校徐长明编写；第6.2和7.1节由东北大学 王骄编写；第6.3节由北京信息科技大学李淑琴编写；第6.4节由安徽大学李学俊编写；第6.5至6.8节、第7.4至7.5节、第8章由安徽财经大学徐勇编写；第6.9节由中央民族大学李霞丽编写；第6.10节由北京信息科技大学丁濛编写；第6.11节由北京科技大学周珂编写；第6.12节由安徽财经大学张炜编写；第6.13节由沈阳工业大学王静文编写；第7.2节由重庆三峡学院吴愚编写；第7.3节由北京邮电大学杨放春编写；第9章和第10章由沈阳航空航天大学王亚杰和安徽财经大学徐勇编写。全书统稿由张小川和徐勇完成。 本书在编写过程中得到很多专家的支持和指导，在此表示诚挚的感谢！书中难免有错误和有妥之处，恳请读者批评指正。 作者 2024年11月 # 目录 # 中国机器博弈2024发展报告 1 # 第1章 引言 # 第2章 机器博弈的发展状况 ..... 8 2.1 机器博弈历史 ..... 8 2.2 机器博弈研究现状 ..... 13 2.2.1 国外的研究现状 13 2.2.2 国内的研究现状 ..... 20 2.3 机器博弈产业现状 ..... 26 2.4 面临的问题与展望 ..... 28 # 第3章博弈的复杂度 37 3.1 概述 37 3.2博弈问题的状态复杂度及其估算方法 39 3.2.1 博弈问题的状态复杂度定义 39 3.2.2 博弈问题的博弈树复杂度 ..... 42 3.3博弈问题的计算复杂性 47 # 第4章 机器博弈的典型技术 ..... 52 4.1 概述 ..... 52 4.2 穷尽搜索 52 4.3裁剪搜索 53 4.4启发式算法 54 4.5 迭代深化 56 4.6 最佳优先算法 ..... 56 4.7随机搜索算法 57 4.8 并行计算 ..... 60 4.9 遗传算法 61 4.10 路径寻迹算法 62 4.11 神经网络 64 4.12 机器学习 ..... 65 4.13知识库 67 4.14 微分博弈 ..... 71 4.15贝叶斯网络与概率推理 72 # 第5章 机器博弈的平台技术 ..... 76 5.1计算机博弈平台概述 76 5.2计算机博弈平台的分类 77 1. 完备信息博弈平台和非完备信息博弈平台 ..... 77 2.单引擎博弈平台和多引擎博弈平台 77 3.单机博弈平台和网络博弈平台 77 4.程序级博弈平台和模块级博弈平台。 77 5.3计算机博弈平台的设计规范 78 5.3.1 人机交互接口规范 ..... 78 1.显示输出规范 78 2.操作输入规范 78 3.其它约定规范 78 5.3.2 平台与引擎通信的协议规范 ..... 78 1.对局状态和过程的信息编码 78 2. 引擎与博弈平台的通信协议 ..... 79 3. 引警示例代码 ..... 79 5.4计算机博弈平台的相关技术 79 1.匿名管道通信技术 79 2.数据保存和加密技术 79 3.在线对局技术 80 5.5计算机博弈平台应用实例 80 1.哈尔滨理工大学军棋博弈平台系统 80 2.哈尔滨理工大学二打一（斗地主）博弈平台系统……80 3.北京理工大学苏拉卡尔塔棋博弈平台系统 81 4.沈阳航空航天大学通用计算机博弈对战平台 81 # 第6章 完备信息机器博弈的专项技术 ..... 82 6.1 六子棋机器博弈 ..... 82 6.1.1 概述 ..... 82 6.1.2 六子棋机器博弈主要技术 ..... 83 6.2 围棋机器博弈 ..... 86 6.2.1 概述 86 6.2.2 围棋机器博弈主要方法 ..... 87 6.3 点格棋机器博弈 91 6.3.1 概述 91 6.3.2 点格棋机器博弈主要技术 ..... 91 6.4 爱恩斯坦棋机器博弈 ..... 94 6.4.1 概述 94 6.4.2 爱恩斯坦棋机器博弈主要技术 ..... 96 6.5 苏拉卡尔塔棋机器博弈 ..... 100 6.5.1 概述 100 6.5.2 苏拉卡尔塔棋规则 ..... 100 6.5.3搜索算法 101 6.5.4 评估函数 ..... 103 6.6 海克斯棋机器博弈 ..... 103 6.6.1 概述 ..... 103 6.6.2 海克斯棋规则 ..... 104 6.6.3 算法改进 ..... 105 6.7 五子棋机器博弈 ..... 106 6.7.1 概述 ..... 106 6.7.2 五子棋规则 ..... 106 6.7.3 改进的五子棋博弈算法 ..... 108 6.7.4 机器人五子棋机器博弈 ..... 108 # 6.8 中国象棋机器博弈 ..... 110 6.8.1 概述 ..... 110 6.8.2 估值方法 ..... 111 6.8.3搜索算法 111 # 6.9 藏族久棋博弈 ..... 112 6.9.1 藏族久棋简介 112 6.9.2 藏族久棋博弈方法 ..... 115 6.9.3 藏族久棋线上对弈平台 ..... 118 # 6.10 国际跳棋 120 6.10.1 概述 ..... 120 6.10.2 基本规则简介 ..... 120 6.10.3 国际跳棋机器博弈关键技术 ..... 121 # 6.11 不围棋 123 6.11.1 概述 ..... 123 6.11.2 不围棋机器博弈主要技术 ..... 123 # 6.12 幻影围棋 ..... 126 6.12.1 概述 ..... 126 6.12.2 幻影围棋博弈主要技术 ..... 127 # 6.13 亚马逊棋 ..... 129 6.13.1 概述 ..... 129 6.13.2 游戏规则 ..... 132 6.13.3 亚马逊棋博弈主要技术 ..... 133 # 第7章 非完备信息机器博弈的专项技术 ..... 137 7.1 德州扑克机器博弈 ..... 138 7.1.1 概述 ..... 138 7.1.2 非完备信息动态博弈解的主要方法 ..... 139 7.2 军棋机器博弈 ..... 142 7.2.1 概述 142 7.2.2 军棋机器博弈主要技术 ..... 143 1. 对手棋子可能性矩阵更新 ..... 143 2. 欺诈走法的选择和判定 ..... 146 3.搜索技术的选择 146 7.3 桥牌机器博弈 ..... 147 7.3.1 概述 ..... 147 7.3.2 桥牌机器博弈的主要方法 ..... 149 7.4 国标（大众）麻将机器博弈 ..... 152 7.4.1 概述 ..... 152 7.4.2 国标（大众）麻将机器博弈规则 ..... 153 7.4.3 麻将博弈平台 ..... 155 7.5 二打一扑克牌机器博弈 ..... 156 7.5.1 概述 ..... 156 7.5.2 计分规则 ..... 156 7.5.3 二打一扑克牌机器博弈的特点 ..... 157 # 第8章 机器博弈的国内外赛事 ..... 158 8.1 国际机器博弈赛事 ..... 158 8.1.1 国际象棋人机博弈大赛 ..... 158 8.1.2 围棋人机与机机博弈大赛 ..... 160 8.1.3 桥牌计算机博弈大赛 ..... 162 8.1.4 德州扑克人机与机机博弈大赛 163 8.1.5 其它赛事与研究成果 ..... 164 8.2 国内机器博弈赛事 ..... 165 8.2.1 中国象棋人机与机机博弈大赛 ..... 165 8.2.2 中国计算机博弈大赛 ..... 166 第9章 结束语 ..... 169 参考文献 173 # 第1章 引言 计算机博弈也称机器博弈（Computer Games），英文直译应该是计算机游戏，其覆盖面非常广泛。然而，从事计算机棋牌竞技研究的科学家们，很早便将Computer Games定义为让计算机能够像人一样会思考和决策，能够下棋。随着计算机博弈事业的发展，国内外学术界、工业界陆续涌现出多个计算机博弈相关的学术组织、企业，开展了一系列的计算机博弈相关研究与实践活动。如国际机器博弈协会（International Computer Games Association, ICGA专门组织世界范围内的棋类（后又加入牌类）博弈竞赛和学术交流。2024年10月19日至24日，ICGA在西班牙的圣地亚哥-德孔波斯特拉举办世界计算机国际象棋锦标赛，这也是该锦标赛的50周年纪念活动，该活动由欧洲人工智能会议主办，谷歌DeepMind赞助。2024计算机和游戏大会将于2024年11月26日至28日在线举行。为了和计算机游戏区别开来，Computer Games中文名字便称之为机器博弈，或者计算机博弈。国内负责组织棋牌类博弈竞赛和学术交流的群众组织是中国人工智能学会下属的机器博弈专业委员会。由中国人工智能学会主办，浙江省机器人创新中心、重庆理工大学联合承办的2024年第三届高校计算机博弈教育论坛于2024年4月20日在浙江省宁波市余姚机器人小镇举办。2024年8月2日下午，由中国人工智能学会（CAAI）主办，CAAI机器博弈专委会组织、青海民族大学和重庆理工大学联合承办的“2024中国机器博弈学术会议”，以线下线上相结合的方式 在青海民族大学博雅校区举行。 机器博弈的发展历程大致可以分为萌芽阶段，发展阶段和深度学习阶段。萌芽阶段，1928年，冯·诺依曼提出了极大极小值定理，并在此基础上证明了博弈论的基本原理。1950年，图灵基于几个最基本的国际象棋规则，运用简单的逻辑搜索两个步骤，完成了简单的计算机智能程序。1956年，麦卡锡发明了Alpha-Beta搜索算法，两年后基于此算法的国际象棋程序问世，基本可以达到初学者的技术水平。发展阶段，随着研究的不断发展与深入，研究人员发现博弈程序的优劣很大程度上是由搜索的深度来决定的，所以人们开始致力于更加有效的搜索算法的研究。机器博弈的第一个里程碑成果是1997年IBM深蓝战胜世界棋王卡斯帕罗夫，这一胜利使得计算机博弈的发展迎来了一个新的高峰。深度学习阶段，2015年，著名的阿尔法狗（AlphaGo）诞生，并在2016年打败了世界围棋冠军李世石，这一事件也把计算机博弈的研究热潮推向了新的高度。2019年，在暴雪娱乐公司打造的实时策略游戏《星际争霸II》中，人工智能程序AlphaStar打败了职业玩家。2024年诺贝尔物理学奖在瑞典皇家科学院揭晓，今年该奖项授予2位人工智能方面的专家：普林斯顿大学的John J. Hopfield和多伦多大学的Geoffrey E. Hinton，他们“因在利用人工神经网络实现机器学习方面的基础性发现和发明而获奖”。在可以预见的未来，人工智能将改变人类的生产和生活方式。 中国机器博弈研究与应用虽然起步较晚，但发展迅速。作为中国机器博弈事业开拓者，东北大学徐心和教授自2003年便开始从事中 国象棋的计算机博弈的研究工作；并于2005年发起组织和领导了中国人工智能学会机器博弈专业委员会的成立，将国际象棋算法移植到中国象棋电脑程序中，并取得了显著成果。专委会的成立标志着中国在机器博弈领域的研究开始系统化和专业化。吸引了一批热心这一领域的科技工作者开始学习国际的先进理论与算法，很快便把国际象棋的算法移植到中国象棋的电脑程序当中，并取得了令人触目的成果。东北大学的棋天大圣代表队夺得了由ICGA组织的2006、2007年国际棋类奥林匹克大赛中国象棋冠军。而且，2006年首届中国象棋计算机博弈锦标赛在北京科技馆成功举行，期间举办了人机大战，挑战了中国象棋的顶尖高手许银川、柳大华、徐天红、卜凤波等特级大师，并取得势均力敌的战绩，令国人刮目相看，但并未掀起预期的热潮，但却推动了全国锦标赛每年一届的举行。2008年，专委会在北京举办了ICGA国际计算机博弈大赛，有14个国家的71支代表队参赛，这是中国在国际计算机博弈领域的重要展示。2010年，专委会与教育部高等学校计算机类专业教学指导委员会联合主办了首届全国大学生计算机博弈大赛暨全国锦标赛，吸引了18所高校的53支代表队参赛，这标志着计算机博弈在中国高校中的普及和推广，使得比赛项目数不断增加，参加的队伍规模也不断壮大，竞赛棋种不仅有完备信息动态博弈项目，如中国象棋、围棋、点格棋、亚马逊棋等，还有非完备信息博弈项目，如幻影围棋、军棋等，还有考虑随机因素的爱恩斯坦棋。自2013年起，还增加了多人博弈的扑克项目，如斗地主和桥牌，使得关于博弈算法的研究更加全面和深入。2015年，计算机 博弈被国家体育总局棋牌运动管理中心列入第三届全国智力运动会项目，进一步扩大了比赛的影响力和知名度。自2006年起，专委会每年都举办全国范围内的大型计算机博弈活动，取得了较大的社会影响。中国机器博弈竞赛项目从中国象棋1个项目，发展到19个项目；参与高校从不足10所，发展到70多所高校5000余师生参与。特别需要提到的是，2024年中国大学生计算机博弈大赛中增加了面向高校学生的机器人五子棋、坦克大战2个软硬件结合的博弈竞赛项目，标志着国内高校机器博弈活动向软硬件融合发展、产业化发展趋势的新探索。 盘点中国计算机博弈事业的发展历程，那最值得一提的学者还有电脑围棋先行者中山大学化学系教授陈志行（1931—2008）。陈老先生1991年退休后潜心研究电脑围棋，在苹果机上用汇编语言编写了博弈程序《手谈》，并且赢得了1995—1997连续3年的6项世界冠军，成为机器博弈史上的一朵奇葩。当晚年的陈老得知国内组织了计算机博弈全国锦标赛时，兴奋不已，抱病参加了在重庆理工大学举行的2007年第二届全国锦标赛（不计名次），还亲自指导年轻人开发软件。陈老先生是我们的楷模，也是中国人的骄傲。 再值得提及的便是许峰雄博士。他台湾大学毕业后到美国卡内基梅隆攻读博士学位，特别钟爱国际象棋计算机博弈。他在毕业后到IBM公司组织了深蓝课题组，并在1997年以战胜卡斯帕罗夫的辉煌战绩赢得了世人的尊重。 十余年来，计算机博弈在中国大地上蓬勃发展，很多院校开展了 以机器博弈为内容的学生科技竞赛活动，很好地带动了校园科技活动的氛围，也很好地培养了学生的科研能力和创新意识。这使得计算机博弈活动在中国从无到有，从小到大，至今可以说中国是世界上参与人数最多、比赛规模最大的国家。 这项比赛之所以能不断发展，最关键的原因就是计算机博弈有着强大的生命力，契合了大学生对棋牌游戏天然的兴趣和喜爱。形式上看，每届参与人数有限，这是受限于比赛规则和条件，比如规定每所高校在每个项目中最多只能报名2支队伍，加上高校参赛差旅费用限制。因此考虑到各个学校的选拔赛在内，保守估计实际能到场参赛的人数是实际参与这项科技活动人数的1/5，那么，实际参加计算机博弈活动的人数将是数以千计的。计算机博弈的强大生命力主要源于以下方面：1）参赛成本低，学生只要有一台电脑就可以开展研究，参加比赛；2）没有专业限制，会下棋、或会编程，就可以参加这项活动；3）下棋本身就是游戏，活动本身具有很好的高趣味、强吸引力；4）比赛具有强挑战性和不确定性，比如这届胜了，并不能保证下届还胜，因此，研究没有止境、不是一蹴而就，是创新活动的不竭研究宝库；5）下棋规则简单、输赢结果立判，不需要专家评审、打分，真正实现公开、公平、公正；6）适合分工合作和团队作战，在研究与开发中使得学生的技能和素质得到全面锻炼；7）有一定的网络化和产业化前景，很容易进入信息化和互联网+的项目当中；8）培养学生创新能力、职业素养明显，极大促进学生就业能力。 此外，中国要想成为计算机博弈强国，就要加强博弈理论和算法 的深入研究。为此，我们专委会主办了中国计算机博弈技术论坛、在中国控制与决策学术年会（CCDC）上开辟了“机器博弈”特邀专题论坛、在《重庆理工大学学报》（自科版）上开辟了“机器博弈”专栏，开展成果交流，提高我国在该领域的学术水平和学术影响。同时，专委会还组织了中国大学生计算机博弈大赛、中国计算机博弈锦标赛和中国大学生机器博弈创新设计赛等赛事，这些赛事不仅为大学生提供了实战平台，也推动了人工智能教育和研究的发展；与竞技世界（北京）网络技术有限公司、学大教育、浙江钱塘机器人及智能装备研究有限公司、重庆工能科技有限公司等企业开展校企合作。通过这些活动和平台，中国人工智能学会机器博弈专委会为机器博弈领域的研究人员、开发者和学生提供了丰富的资源和机会，推动了机器博弈研究的进步与应用的发展。 机器博弈的产业化是一个涉及人工智能、机器学习、博弈论等多个领域的复杂过程。AlphaGo的成功，标志着人工智能进入了新的阶段，得益于深度学习、强化学习等人工智能技术的进步，机器博弈已经不再局限于游戏领域，而是开始向更广泛的行业渗透，如在数字经济、智慧医疗、智能交通、航空、航天、兵棋推演和战略、战役和战术博弈中等领域，机器博弈技术正在推动相关产业的发展。层出不穷的博弈搜索算法无疑可以应用到面对决策优化的各种场合，博弈是人类经济、政治、军事、反恐、治霾和日常生活中无所不在的内容，机器博弈的概念和技术也必然大有用武之地。因此，机器博弈的产业化是一个多元化、跨学科的过程，它不仅推动了人工智能技术的发展， 也为多个行业带来了创新和变革。随着技术的不断进步和应用场景的拓展，机器博弈的产业化前景非常广阔。 本《中国机器博弈2024发展报告》是机器博弈宣传和普及工作的继续和深化，为此专委会邀请了这一领域的同行专家共同撰写，首先，介绍了机器博弈的发展过程，国内外赛事，博弈棋种和比赛平台，然后结合相关棋种介绍了各种博弈技术，既包括完备信息的棋类比赛，还包括不完备信息的牌类游戏搜索算法，当然还包括目前流行的深度学习算法、最新的桥牌和德州扑克博弈算法等。 让计算机博弈活动在更多的学校中生根、开花、结果是专委会一直追求的目标。让我们走出去，在国际大赛中夺取更多的奖牌，为国争光。同时，借助计算机博弈活动，促进产学研相结合，推动我国人工智能技术的发展，加速我国早日成为人工智能领域的大国、强国。 # 第2章 机器博弈的发展状况 # 2.1 机器博弈历史 早在人类文明发展初期，人们就开始棋类博弈的游戏。1928年，被称作计算机之父的冯·诺依曼（John von Neumann）通过对两人零和一类博弈游戏的分析，提出了极大极小值定理，证明了博弈论的基本原理。在冯·诺依曼和摩根斯特恩合著的《博弈论和经济行为》（1944）中，将二人博弈推广到n人博弈结构，并将博弈论系统应用于经济领域，从而奠定了机器博弈研究的基础和理论体系。 近代机器博弈的研究，是从上世纪五十年代开始的。许多世界上著名的科学家，例如数学家和计算机学家阿兰·图灵（Alan Turing），信息论创始人科劳德·香农（Claude E. Shannon），人工智能的创始人麦卡锡（John McCarthy）以及冯·诺依曼等人都曾经涉足机器博弈领域的研究工作，并为之做出过非常重要的贡献。 1950年，著名的控制论先驱香农提出了象棋博弈的编程方案。1953年，阿兰·图灵设计了一个能够下国际象棋的纸上程序，并经过一步步的人为推演，实现了第一个国际象棋的程序化博弈。1958年，IBM推出取名“思考”的IBM704，成为了第一台与人类进行国际象棋对抗的计算机。虽然在人类棋手面前被打得丢盔卸甲，但许多科学家却对此欢欣鼓舞。1959年，人工智能的创始人之一塞缪（A. L Samuel）编写了一个能够战胜设计者本人的西洋跳棋计算机程序，1962年该程序击败了美国的一个州冠军，这是机器博弈历程中一个重要的里程碑。 随着计算机硬件和软件技术的不断发展，通过人-机或者机-机对弈，实现了计算机硬件性能和计算机软件水平的较量。科学家们开始对电脑能否战胜人脑这个话题产生了浓厚的兴趣，提出以棋类对弈的方式，向人类智能发起挑战。 上世纪八十年代中期，美国卡耐基梅隆大学开始研究世界级的国际象棋计算机程序；1988-1989年间，IBM“深思”分别与丹麦特级大师拉尔森、世界棋王卡斯帕罗夫进行了“人机大战”。 从上世纪九十年代起，Tcsauro的TD-GAMMON西洋双陆棋程序经过上百万盘的学习训练，程序达到世界水平；“深思”二代产生，吸引了前世界棋王卡尔波夫和世界优秀女棋手小波尔分别前来与之对抗（1990和1993年）。特别是“深蓝”（1996年）、“超级深蓝”（1997年）与卡斯帕罗夫的两场比赛，引起全球媒体的关注。在随后的几年里，计算机与卡斯帕罗夫和克拉姆尼克等世界顶级棋手进行了一系列的比赛，计算机逐渐负少胜多，表现得越来越聪明。 经过多年对机器博弈进行系统的理论研究，在国际象棋、中国象棋等棋种的人机大战中，从最初人类完胜电脑，到如今电脑击败人类顶级高手，机器博弈水平迅速上升。特别是，2016-2017年，AlphaGo分别与李世石、柯洁的人机围棋大战并取得胜利，这可谓是人机对抗史上的最强之战，从而掀起全球人工智能热潮。 此外，除了AlphaGo完备信息机器博弈领域的人工智能划时代成就外，2007年1月30日，美国卡耐基梅隆大学开发的德州扑克博弈系统Libratus与4名人类顶尖德州扑克选手之间进行了“人机大战”， 宣告在“多人”博弈的非完备信息机器博弈领域，人工智能同样取得了胜利。2017年4月6~10日，备受关注的亚洲首度人工智能与真人对打的扑克大赛——“‘冷扑大师’（Libratus扑克机器人）与中国龙之队”扑克巅峰表演赛在海南收官，最终以“冷扑大师”获胜，赢得200万元奖金，这是人工智能在各种棋牌博弈中对人类取得的又一个胜利。再次在全球范围加剧了对人工智能的敬畏或恐惧气氛。 在2018年至2024年期间，国外机器博弈领域的研究显著推进，主要体现在理论模型创新、算法优化、应用场景拓展以及实验评估体系的完善上。2018年OpenAI Five在Dota2中击败人类队伍，OpenAI Five是OpenAI开发的Dota2 AI，在2018年TI8（国际邀请赛）的表演赛中击败了职业玩家队伍，展示了AI在复杂的多人对战游戏中的能力。DeepMind推出的AlphaZero在没有人类数据的情况下，通过自我对弈学习了国际象棋、将棋和围棋，并在短时间内超越了之前所有版本的AlphaGo，展示了AI自主学习的能力。2019年，Pluribus在德州扑克多人对战中获胜，AlphaStar在星际争霸II中表现卓越。2020年，大规模在线博弈研究展开，AI与全球棋手进行在线对战。2021年，AI辅助决策系统在商业博弈中得到应用，新一代AI在国际象棋中取得新突破。2022年，AI在电子竞技中广泛应用，对抗样本研究结合博弈论和机器学习。2023年，探索AI与人类协作的新模式，AI在国际关系模拟中作为决策辅助工具。2024年，AI伦理和博弈论的研究增多，AI在元宇宙中的博弈实验开始探索新的策略和行为模式。这些事件展示了机器博弈在多领域的广泛影响和应用潜力。 在中国国内，也有一些学者从事机器博弈方面的研究。比如，南开大学黄云龙教授和他的学生吴韧在上世纪八十年代开发了一系列中国象棋程序；中山大学化学系教授陈志行先生在九十年代初开发了围棋程序“手谈”，并获得世界冠军；本世纪初，东北大学的徐心和教授和他的学生王骄、徐长明等研究开发了中国象棋软件“棋天大圣”，并在2006年的人机大战中，展现了具有挑战国内中国象棋顶级高手的实力，表现出较高的智能；南京航空航天大学夏正友教授指导学生研究开发了具有一定智能的四国军棋博弈系统；北京邮电大学的刘知青教授带领学生开发的“本手（LINGO）”围棋程序，能够战胜具有一定水平的业余围棋选手；哈尔滨工业大学王轩教授的团队开发的德州扑克博弈系统，2013-2016年间多次参加ACPC二人非限制性、三人及多人德州扑克比赛，均进入决赛前4名。 从2006年起，由东北大学徐心和教授发起成立了中国人工智能学会机器博弈专业委员会，在国内高校师生间推广与普及机器博弈知识，每年举办一届机器博弈大赛暨中国机器博弈锦标赛(王骄，孙英龙，吕辉展，&杨辉，2012)。在沈阳航空航天大学王亚杰教授、重庆理工大学张小川教授、安徽大学李学俊教授等人的大力推动下，陆续在辽宁省和安徽省开展省级大学生机器博弈竞赛，吸引越来越多高校师生参与机器博弈相关研究中来，中国机器博弈进入了快速发展阶段(李飞，王亚杰，尹航，&孙玉霞，2016)。 直到2017年，国内许多企业如腾讯、百度、联众、新睿、竞技世界等纷纷加入到机器博弈的研究大军中，开发出一些具有较高智能 水平的产品。如腾讯人工智能实验室（AI Lab）研发的围棋人工智能程序“绝艺”（Fine Art），夺得2017年第10届UEC杯计算机围棋大赛冠军；北京邮电大学的刘玉璋和杨放春教授带领创业团队开发的新睿桥牌机器人，在2017年第21届世界计算机桥牌锦标赛中获得亚军。 在2018至2024年期间，中国机器博弈领域经历了显著的发展。以2018年“天河二号”超级计算机的全球最快评选为起点，该领域的研究逐渐深入，不断融合深度学习、强化学习等先进技术，提升了机器博弈系统的智能决策能力。随后几年，全国范围内举办的机器博弈赛事进一步推动了技术交流与创新，并激发了年轻人的兴趣。2020年后，出现了许多新的机器博弈技术，提升了机器博弈智能体的决策效率和准确性。到2022年，这些技术开始广泛应用于游戏、智能交通等实际场景。至2024年，中国机器博弈领域已展现出强大的创新活力和广阔的应用前景，预示着未来该领域的持续快速发展。此外，一些研究开始探索将机器博弈技术应用于社会治理领域，例如，通过模拟博弈过程来预测和应对社会冲突、制定更有效的政策等。至2025年，机器博弈研究呈现出从专用游戏算法向通用战略智能的范式转移。前沿探索集中于将大型语言模型的核心推理能力与机器博弈的自我对弈范式深度融合，旨在培养能适应复杂合作与竞争环境的通用决策智能体。研究表明，通过在多轮战略游戏中进行的强化学习训练，智能体所获得的战略能力可有效泛化至未知任务乃至通用推理领域。这一进展标志着机器博弈的价值超越了传统的游戏胜负，正成为锻造 具备高级决策与协作能力的通用人工智能的关键实验平台与核心驱动力量。基于此类技术构建的智能决策支持系统，已在模拟推演、策略评估等实际场景中展现出指导价值。 目前，在机器博弈领域中，非完备算法扮演着至关重要的角色，它使得机器能够在信息不完整或不确定的环境中进行有效的决策，这对于提高机器在复杂博弈场景中的性能和适应性具有决定性的影响。它们在处理不完全信息或不确定性方面具有显著优势。这些算法在多个领域展现出其有效性。 # 2.2 机器博弈研究现状 DeepMind公司创始人Demis Hassabis曾言：“游戏是测试人工智能算法的完美平台”。而机器博弈被誉为是人工智能学科的“果蝇”，通过机器博弈的过程来理解智能的实质，是研究人类思维和实现机器思维最好的实验载体。 # 2.2.1 国外的研究现状 在机器博弈研究的早期阶段，研究的主要内容涉及如何建立有效、快速地评价函数和评价方法，使评价的效率更高，花费的时间和空间的代价更小，以及如何在生成的博弈树上更准确有效地找到最优解，并由此衍生出搜索算法的研究成果。在随后的几十年里，专家和学者们在机器博弈搜索与评估方面进行了大量深入探索和实质性的研究，产生了许多机器博弈技术，如极大极小搜索、负极大值搜索、Alpha-Beta剪枝、并行搜索算法等(Bench-Capon & Dunne, 2007; Cormen, Rivest, Leiserson, & C., 2009; Lieberum, 2005; T. A Marsland & Campbell, 1982; Takeuchi, Kaneko, & Yamaguchi, 2010)。 特别值得讲述的是，2006年多伦多大学教授Geoffery Hinton发表文章提出了基于深度信念网络（Deep Belief Networks，DBN）可使用非监督的逐层贪心训练算法(G.E.Hinton, Osindero, & Teh, 2006)，在学术界掀起了对深度学习（Deep Learning）的研究热潮。随着并行计算、基于人工神经网络的深度学习(Schölkopf & Platt, 2007; David Silver et al., 2016)等技术的突破性进展，成功解决了机器博弈中抽象认知的难题。使得深度学习等技术被成功应用于机器博弈及相关领域中，从而将机器博弈水平带上了一个新的台阶。 Google、百度等国际大公司争相跟进，研发出相关的机器博弈产品。尤其是 Google 公司的围棋软件 AlphaGo，作为完备信息博弈代表，它具有极强的自学能力，如图 2-1 显示了 AlphaGo 的算法组成。 图2-1AlphaGo算法组成 AlphaGo的技术突破被学者们总结为两个关键技术：棋感直觉和搜索验证。其中，棋感直觉通过深度学习（Deep Learning）获得，它分为落子棋感和胜负棋感，AlphaGo通过对3000万的经典棋局进行深度学习得到快速走棋网络和策略网络，而快速走棋网络就是落子棋感；胜负棋感是通过深度学习得到的策略网络不断进行自对弈来得 到; 搜索验证指的是搜索引擎主要采用蒙特卡洛搜索树根据落子棋感和胜负棋感不断展开搜索树 (刘知青 & 吴修竹, 2016)。围棋程序AlphaGo的成功充分验证了深度学习与机器博弈技术结合的实用性。Google 公司宣布将其应用于医疗诊断等领域，以扩大深度学习应用领域。 在人工智能和博弈论的交叉领域，博弈的类型成为塑造策略和决策模型的关键因素。博弈可以分为两大类：完备信息博弈和非完备信息博弈。 完备信息博弈是指所有参与者在任何时间点都拥有关于博弈状态的完整知识和信息，而参与者之间的策略选择直接影响博弈的发展和结果。这类博弈在许多经典的游戏中得到体现，如印度女子工程学院Sneha Garg等学者设计了多带图灵机模型，为井字棋游戏提供了新颖的计算决策方法(Garg & Songara，2016)；孟加拉国东三角洲大学的Muhammad Sakib Khan Inan 和Rizwan Hasan等人，通过集成专家系统，使用XGBoost算法和规则推理，成功地在井字棋游戏中与极小化极大算法打成平局，展示了监督机器学习在游戏AI中的潜力(Inan, Hasan, & Prama, 2021)；印度希里·巴格温·马法塔拉尔理工学院的Mihir Rajesh Panchal等人，结合不同机器学习算法，成功预测了象棋游戏状态(Panchal, Dodia, & Rathod, 2023)；Sajjad Ghazanfari Shabankareh等在伊朗和法国的研究机构，通过结合遗传算法和神经网络改进了边缘跟踪方法，显著提升了边缘检测的准确性和质量等(Shabankareh & Shabankareh, 2019)。这些都体现了完 备信息博弈在计算决策方法创新、监督机器学习与规则推理集成、机器学习算法应用和复杂计算任务优化等方面的广泛应用和深入研究。通过这些案例，完备信息博弈展示了其在推动人工智能技术发展和应用方面的重要作用，为策略制定、决策优化和复杂任务处理提供了坚实的理论基础和实践指导。 相比之下，非完备信息博弈则引入了信息的不确定性，其中参与者可能无法完全了解对手的策略、状态或意图，如Ahmed H. Anwar等在奥兰多中央佛罗里达大学开发了MTD框架，分析云提供商与攻击者在虚拟机迁移中的博弈，提出博弈论公式描述共置时机，验证Nash均衡，为首篇虚拟机迁移时机博弈研究，提供新防御视角(Anwar, Atia, & Guirguis, 2021)；新南威尔士大学研究团队由Shuo Yang等人使用PPO算法在《Ticket to Ride》中训练RL代理，通过对抗和循环赛评估，发现RL代理优于启发式代理，RLSelfplayAI表现最佳。论文证明了RL在复杂非完备信息博弈中的潜力，并提供了可推广的建模方案(Yang et al., 2023)；捷克技术大学的沃伊捷赫·科瓦里克等人提出了不完美信息零和博弈的深度限制求解方法，并实验验证了其有效性，该方法对相关研究具有重要推动作用(Kovaík & V, 2019)；来自英国帝国理工学院的Francesco Belardinelli等人提出了一种抽象细化框架，用于验证不完全信息下的多智能体系统战略属性(Belardinelli, Ferrando, & Malvone, 2023)；日本高知工科大学的Lucien Troillet等则通过DREAM算法的智能体分析了不完全信息对Geister棋盘游戏策略的影响(Troillet & Matsuzaki, 2024)； 瑞典皇家理工学院的Dilan Gurov等研究者探讨了多智能体团队在不完全信息下如何合成基于知识的策略(Gurov，Goranko，&Lundberg，2022)；日本东京电气通信大学研究者Moyuru Kurita和Kunihito Hoki等则提出了一种构建麻将游戏中AI玩家的新方法，通过抽象为马尔可夫决策过程来构建高效搜索树(Kurita & Hoki,2021)；麻省理工学院的Dimitris Bertsimas和哥伦比亚大学的Alex Paskov共同完成针对不完美信息游戏中的可解释性问题，提出了新颖的特征表示方法和最优决策树，通过与世界级扑克AI的对局实验验证了其有效性(Bertsimas & Paskov, 2022)。利物浦大学的George Christodouloud等学者，设计了贝叶斯博弈中资源分配问题的成本分担方法，并提出了预算平衡在均衡的替代性要求，改进了价格混乱度的界限(Christodoulou，Leonardi，&Sgouritsa，2016)；巴黎经济学院的Andres Salamanca，研究了不完全信息下具有可转移效用博弈中的价值概念，并构建了货币转移作为额外附加支付的模型，证明了相关值的推广和等价性(Salamanca，2020)；瑞典皇家理工学院的图通措格鲁，费里敦研究了边缘计算中服务缓存和定价的问题，提出了贝叶斯高斯过程多臂老虎机方法，并证明了其算法的性能优于现有算法(Mehdi，HoumairiAdam，Miriman，&BellafkihMostafa,2024)；而摩洛哥国立邮电大学坎杜西，埃尔迈赫迪研究了云安全中的挑战，提出了一种基于贝叶斯博弈理论的动态防御机制，并通过数值结果证明了其方案在提高云环境安全性方面的有效性(Tutuncuoglu & Dán, 2024)；意大利特伦托大学的Samuel Rota Bulò等提出了随机预测游戏框架，有效提升了分类器的安全性和鲁棒性(Bulò, Biggio, Pillai, Pelillo, & Roli, 2017); 塞尔丘克大学的 Mustafa A. Al-Asadi 等利用 FIFA 视频游戏数据成功预测了足球运动员的市场价值，为足球转会市场提供了有价值的参考 (Al-Asadi & Tasdemür, 2022); 奥地利 MCI 因斯布鲁克大学的 Florian Merkle 等研究了对抗性机器学习的经济学问题，通过扩展游戏理论框架，分析了攻击者和防御者的经济激励和策略选择 (Merkle, Samsinger, Schöttle, & Pevny, 2024)。与此同时，在理论基础层面，研究视野正从静态模型扩展到更符合现实世界的动态交互模型。例如，北京大学李阿明团队在《PNAS》上发表的关于“时序相互作用促进集体合作”的研究，突破了传统静态网络的限制，揭示了在动态变化的交互网络中，通过优化互动时序能更有效地促进群体合作，为构建多智能体协作系统提供了新颖的理论框架 (Meng, McAvoy, & Li, 2025)。研究前沿正将大型语言模型与机器博弈范式深度结合。Yuan等人提出的 MARS 框架，通过在多轮合作与竞争性战略游戏中进行端到端强化学习自我对弈，其关键价值在于，该能力可泛化至游戏之外的通用推理任务，这强有力地验证了机器博弈作为培养高级决策模型的关键途径的深远价值 (Yuan et al., 2025)。通过这些案例，非完备信息博弈的研究不仅推动了人工智能技术的发展，也为构建具备通用战略推理能力的智能体奠定了坚实基础。通过这些案例，非完备信息博弈展示了其在推动人工智能技术发展、复杂决策制定、多智能体 协作和对抗策略优化方面的重要作用，为相关领域的研究和应用提供了坚实的理论基础和实践指导。 此外，不完备信息博弈以美国卡耐基梅隆大学研发的德州扑克博弈系统Libratus为代表，被学者们总结为主要包括三个关键模块： （1）赛前纳什均衡近似（Nash equilibrium approximation before competition）。这个模块把最重要的博弈信息（例如针对某一手牌对应的战略）进行抽取，然后再应用强化学习等方法，继续寻求提高和改进。这里使用了一个新的算法：蒙特卡洛反事实遗憾最小化。在这个模型的帮助下，Libratus 自己学会了德州扑克，而且比以前速度更快。 （2）残局解算（Endgame solving）。这是 Libratus 最重要的部分，因为一局德扑只需要几个回合，耗费时间短。因此 Libratus 的开发者们选择从下往上构建博弈树，这样最下面节点的状态是比较容易算出来的，用这个状态反过来指导设计上面的博弈树，并使用蒙特卡罗方法，每次选一些节点去更新它们上面的策略。也就是说，Libratus 不仅仅是在比赛前学习，而且还能在比赛中学到东西。 （3）持续自我强化（Continual self-improvement）。比赛中人类高手会寻找 Libratus 的漏洞，并展开有针对性的攻击。这个模块的作用就是发现问题所在，找到更多细节进行自我强化，然后得到一个更好的纳什均衡。 通过对这两个博弈类型的比较和研究，我们不仅能够更全面地理解博弈理论的复杂性，还能洞察人工智能在策略设计和决策支持中的 巨大潜力。 # 2.2.2 国内的研究现状 国内机器博弈研究相对起步较晚，曾经一度参与者寥寥无几，参考文献匮乏，机器博弈氛围沉寂。本世纪初，东北大学徐心和教授带领团队对中国象棋、六子棋、点格棋等机器博弈展开了深入研究，在国内高校举办各类机器博弈技术培训与讲座，申请控制与决策国际会议（Chinese Control and Decision Conferen，简称CCDC）机器博弈专题。近几年，重庆理工大学张小川教授在《重庆理工大学学报（自然科学版）》申请了机器博弈专题，并与国际机器博弈协会(International Computer Games Association，简称ICGA)开展交流与合作。上述举措都极大地促进了国内机器博弈的研究与发展。 2010年后，国内机器博弈领域不仅在理论研究上有所突破，还在实际应用中取得了诸多成果。机器博弈作为人工智能领域的一个重要分支，其研究涵盖了棋类博弈、牌类博弈、电子竞技等多个方面，涉及搜索算法、估值函数、强化学习等关键技术，特别是在深度学习和强化学习技术的应用上取得了显著突破。许多研究机构和企业正致力于将最新的机器学习和人工智能技术应用于机器博弈中，以实现更高效的策略搜索和更精准的局势评估。当前，博弈论与人工智能领域的交叉研究日益兴盛，其中完备信息博弈与非完备信息博弈作为核心议题，其研究现状备受瞩目，不仅在理论构建、算法创新上取得了显著进展，也在实际应用中面临着一系列独特而复杂的挑战。” 在完备信息博弈领域, 随着计算技术的飞速发展和算法的不断优 化，机器博弈的研究已经取得了令人瞩目的成果。在这类博弈中，机器可以获取到全部的博弈信息，从而进行更为精确的策略分析和决策。目前，该领域的研究重点主要集中在如何设计更高效的算法、提升机器的自主学习能力，以及探索机器博弈在实际应用中的更广泛可能性。学者们结合棋牌各自特点，针对机器博弈搜索、评估与优化等方面开展了深入研究。例如，中央民族大学的李霞丽对藏族传统棋类游戏“久”棋的机器博弈算法与软件开发的研究。他们通过数据采集和棋型提取，设计了基于棋型的攻防策略，并开发了具有多种功能的“久”棋博弈软件(李霞丽，吴立成，& 李永集，2018)。对于局面估值问题，沈阳理工大学的吕艳辉提出结合时间差分算法和反向传播神经网络，设计一种局面估值算法实现评估函数参数的自动调整(吕艳辉 & 宫瑞敏，2012)；针对六子棋，东北大学徐长明对局面表示等关键技术进行研究(徐长明，2010；徐长明，马宗民，& 徐心和，2009)，重庆理工大学张小川教授提出应用遗传算法优化评估函数(张小川，陈光年，张世强，孙可均，& 李祖枢，2010)，安徽大学李学俊教授等提出基于局部“路”扫描方式的博弈树生成算法(李学俊，王小龙，吴蕾，& 刘慧婷，2015)；针对中国象棋，东北大学王骄教授对机器博弈开局库(魏钦刚，王骄，徐心和，& 南晓斐，2007)、循环判定规则(王骄 et al., 2012)、评估函数参数组的自动调整和优化(王骄，王涛，罗艳红，& 徐心和，2005)展开了研究；针对苏拉卡尔塔棋，北京信息科技大学李淑琴教授等根据棋子的数量、移动范围等不同参数，对局面评估函数进行了研究(李淑琴，李静波，韩裕华，& 陶思拓，2012)；辽宁石油化工大学张利群教授提出了一个网络博弈平台吃子算法(张利群，2016)；针对亚马逊棋，沈阳航空航天大学邱虹坤对搜索算法、评估与调参进行了分析研究(Hongkun, Peng, Yajie, Jiehong, & Fei, 2014; Jianning, Hongkun, Yajie, Fei, & Shengran, 2016；邱虹坤，王浩宇，& 王亚杰，2022)，李淑琴教授根据特征权重值给出一个分阶段的评估函数(郭琴琴，李淑琴，& 包华，2012)；中央民族大学李霞丽和吴立成教授提出一种围棋多模态算法，及基于小样本的藏棋博弈算法(Jiao et al., 2017；Xinyang et al.)。完备信息博弈领域的研究已经取得了显著成果，为机器博弈技术的发展奠定了坚实基础。 目前，非完备信息博弈领域的研究正处于快速发展阶段，逐渐成为人工智能和计算机科学领域前沿热点。非完备信息机器博弈策略的研究，不断推动着机器智能决策和策略推理能力的提升，尤其是在扑克比赛、无人机对抗、兵器推演等复杂决策场景中，其重要性愈发凸显。 在算法理论层面，多智能体强化学习与进化计算等前沿方向的融合持续深化。例如，南京航空航天大学陈洪放等人提出了基于策略优化和表征搜索的改进多智能体进化强化学习方法（SORS），该方法为处理多智能体非平稳性和部分可观测性难题提供了新颖的解决方案（陈洪放，王秋红，顾晶晶，&张凯，2025）。在高端应用领域，机器博弈技术在国防智能决策中的价值日益凸显。南昌航空大学郑巍等人针对非均势空战中的策略趋同问题，提出了基于非对称自博弈的智能 决策方法。有效提升了在武器失衡和数量失衡场景下的决策效能（郑巍，汤佳豪，熊小平，&樊鑫，2025)。例如，哈尔滨工业大学王轩教授团队针对德州扑克等博弈系统，开展了非完备信息机器博弈中风险及对手模型的研究(Hongkun et al., 2014；马骁，王轩，&王晓龙，2010；张加佳，2016)。中央民族大学吴立成等人提出了一种基于卷积神经网络的“拱猪”博弈算法，包括亮牌和出牌两个网络，在真实牌谱数据集上训练后，达到了较高的准确率，能够产生合理的博弈策略(吴立成，吴启飞，钟宏鸣，王世尧，&李霞丽，2023)。中央民族大学李霞丽等人综述了麻将博弈AI的构建方法，分析了基于知识和基于数据的方法，探讨了当前最高水平的麻将AI Suphx的构建原理及其优缺点，指出了未来研究方向(吴立成 et al., 2023)。沈阳航空航天大学邱虹坤基于数据库和经验分析技术，优化了桥牌博弈模型并构建了混合策略打牌模型，显著提高了桥牌AI的综合能力和获胜几率(邱虹坤，郑晓东，&王亚杰，2021)。中南林业科技大学柴化云提出了基于深度神经网络的斗地主博弈智能体设计方法，结合置换表技术和迭代深化搜索算法，提高了系统博弈水平，并克服了高维度状态空间下对手决策评估的难点(柴化云&王福成，2020)。来自深圳市腾讯计算机系统有限公司的徐方婧等人设计了一种基于卷积神经网络的“斗地主”策略，通过蒙特卡洛树自我博弈训练网络，实现了较高的胜率，验证了算法的有效性与可行性(徐方婧，魏鲲鹏，王以松，彭敬文，&于小民，2020)。上海大学唐杰等人提出了一种面向智能博弈游戏的卷积神经网络估值方法，应用于德州扑克中，通 过训练模型学习人类大师经验，增强了博弈程序的牌力，取得了较高的胜率(唐杰，许华虎，& 谈广云，2020)。南昌大学雷捷维等人结合Expectimax 搜索与 Double DQN 算法，提出了一种非完备信息博弈算法，应用于麻将游戏中，显著提高了博弈性能和胜率(雷捷维，王嘉旸，任航，闫天伟，& 黄伟，2021)。 在扑克比赛这一非完备信息博弈的经典场景中，算法研究同样取得了显著进展。特别是基于反事实后悔最小化（CFR）及其变体的算法，在扑克比赛中展现出了强大的求解能力。如DeepStack、Libratus和Pluribus等智能体，通过融合CFR与深度学习技术，成功战胜了顶级人类玩家，充分证明了CFR及其变体在非完备信息博弈中的广泛应用前景(王帅 & 雷跃明，2017)。 在无人机对抗领域，鉴于战场环境的复杂多变以及信息的不确定性，传统的完备信息博弈策略已难以满足实际需求。因此，探索非完备信息下的无人机博弈策略显得尤为迫切。南京航空航天大学王琳蒙在无人机非完备信息攻防博弈策略方面的研究成果。研究团队通过建立无人机攻防博弈模型，并提出一种基于反向学习的改进麻雀算法，解决了非完备信息下的无人机攻防决策问题(王琳蒙，王玉惠，陈谋，&刘昊天，2022)。通过引入机器博弈等相关人工智能技术，军用无人机操控方式可由传统的遥控逐渐过渡到系统自主智能决策与控制(全秉达，段海滨，&魏晨，2024；朱丰 & 胡晓峰，2016)。 在智能化战争模拟（兵棋推演）系统中，可以自动模拟敌方复杂的行为，更加真实地模拟战争的场景，通过虚拟仿真推演军事对抗， 将其结果作为决策系统重要可信的依据(周超，胡晓峰，郑书奎，&夏荣祥，2017；朱丰 & 胡晓峰，2016)；在以理解、推理、决策为代表的军用信息系统中，结合深度学习与机器博弈相关技术，推动系统向智能化发展(郭圣明，贺筱媛，胡晓峰，吴琳，& 欧微，2016)。 国内在机器博弈领域的研究展现出了蓬勃的发展态势和深厚的创新能力。学者们不仅在传统棋类游戏的机器博弈搜索、评估与优化等方面取得了显著成果，如提出结合时间差分算法和神经网络的局面估值算法、应用遗传算法优化评估函数等，还成功将机器博弈技术拓展到电子竞技、自动驾驶、金融交易等多个新兴领域，展现了技术的广泛应用前景。越来越多的高校、研究机构和企业投入到机器博弈的研究中，形成了强大的研究力量。在这些研究中，多种创新算法和技术的提出，如干扰生成对抗强化学习（田大江 et al., 2024）、Expectimax 搜索与 Double DQN 算法的结合（雷捷维 et al., 2021）、基于卷积神经网络的博弈策略等（吴立成 et al., 2023），不仅提高了博弈系统的性能和胜率，还推动了相关领域的理论和技术进步。同时，针对特定棋牌游戏的深入研究，如六子棋、中国象棋、苏拉卡尔塔棋等，为机器博弈技术的精细化发展提供了有力支撑。这些机构不仅在国内进行竞争与合作，还积极参与国际上的机器博弈比赛和学术交流，不断提升自身的研究水平和影响力。此外，此外，活跃的学术生态持续推动着知识的交融与创新。在 2025 年中国机器博弈学术会议上，来自东北大学的王骄教授探讨了“复杂场景下的机器博弈方法与应用”，中央民族大学的李霞丽教授则分享了“知识驱动的分层分 阶段藏族久棋神经网络模型”，这些工作鲜明地体现了国内研究正从通用算法探索走向针对特定文化和复杂问题的专业化、精细化探索。国内高校、研究机构和企业之间的紧密合作与竞争，以及政府的积极支持，共同构建了一个充满活力的机器博弈研究生态。这种生态不仅促进了技术的快速迭代和进步，还培养了大量专业人才，为机器博弈技术的长期发展奠定了坚实基础。 总之，国内机器博弈研究在理论创新、技术应用和生态建设等方面均取得了显著成就，展现出了强大的研究实力和广阔的发展前景。未来，随着技术的不断进步和应用领域的不断拓展，机器博弈技术将在更多领域发挥重要作用，为人类社会带来更多便利和福祉。 # 2.3 机器博弈产业现状 在深度学习和人工智能技术的推动下，机器博弈相关产业在近年来取得了显著的发展。特别是以AlphaGo为代表的完备信息博弈研究，通过深度学习获得棋感直觉，并结合蒙特卡洛搜索树技术，成功击败了人类围棋冠军。在不完备信息博弈领域，如德州扑克，Libratus系统通过赛前纳什均衡近似、残局解算和持续自我强化等关键模块，展现了机器博弈技术的新高度。 机器博弈相关技术的发展，不仅在学术界掀起了对其研究的热潮，还带动与之高度密切相关的游戏产业飞速发展。庞大的机器博弈产业吸引了众多公司争相跟进，学术界与产业界结合日趋紧密。企业积极与从事机器博弈领域研究的专家学者展开多方位的合作，将学者们的科研成果转化为具有更高人工智能水平的产品。 以游戏产业为例，人工智能不仅提高了游戏的趣味性，还使游戏变得更精致。技术创新是游戏产业发展的重要驱动力，而国家对电子竞技的大力支持（将电子竞技纳入第99个体育项目，并成为教育部增补专业），是游戏产业发展的重要保障。 2001年至今，游戏行业的市场规模不断扩大。全球范围内游戏行业的竞争格局较为集中，全球游戏市场也保持着稳定的增长态势，2024年全球游戏市场规模超过2000亿美元，玩家总数达33亿。相对于国外，我国游戏产业发展较快。2023年底，中国国内游戏市场达到了3029亿元，同比增长 $14\%$ 。2024年上半年，中国游戏市场实际销售收入达到1472.67亿元，同比增长 $2.08\%$ ，市场增长趋势平稳。其中，移动端游戏作为中国游戏市场的主力军，占整体市场的 $75\%$ 左右。此外，小游戏市场快速崛起，2024年上半年收入破166亿，同比大增 $60.5\%$ 。游戏用户规模达到6.74亿人，同比增长 $0.88\%$ ，显示出国内游戏市场的广泛覆盖和深厚基础。腾讯和网易占据了中国市场较大的份额（腾讯约占 $60\%$ ，网易约占 $30\%$ 多），尽管头部厂商占据优势，但一些新的游戏公司和工作室也不断涌现，给行业带来了新的活力。未来，随着5G、VR/AR等新技术的普及，技术创新和游戏体验将进一步优化，游戏产业将吸引更多用户，保持继续增长态势。 伴随机器博弈算法等技术的日趋成熟，相关的AI算力支撑硬件也在快速发展。在市场规模方面，中国的人工智能芯片市场价值达70亿美元，华为的昇腾芯片系列在AI算法方面可以与英伟达的A100相媲美，显示出中国在机器博弈领域的竞争力。华为昇腾910B芯片 在训练大规模语言模型时，相比英伟达的A100，效率提升高达 $80\%$ ，在具体测试性能上，超越A100 AI GPU $20\%$ 。这表明中国在AI芯片领域正逐步减少对外部技术的依赖，并在全球市场中占据越来越重要的位置。 展望未来五到十年，随着机器博弈开发和应用的相关技术“从概念化到产业化”，机器博弈技术将进入实用阶段。该领域的产业发展呈现出更深刻的智能化与生态化趋势。在竞争模式上，领先企业正从单一产品竞争转向构建产业生态的“生态博弈”，通过开源关键数据集、组建产业联盟等方式确立行业标准。在核心技术层面，具身智能机器人已能理解并执行“铺床”等抽象任务指令，并在失败后自主纠错，标志着智能体对物理世界的干预能力迈上新台阶。更根本的突破在于，AI已开始参与并优化强化学习算法本身的设计，实现了核心技术的自我进化。机器博弈与相关领域产学研相结合，将极大地激发科研工作者的创新热情，加速推进科技创新和技术进步。大批机器博弈科研人才将成为民用、军工企业发展的强大技术引擎，为我国智能化建设，引领机器博弈产业发展，发挥巨大的潜在应用价值。机器博弈产业将继续作为推动人工智能发展的关键力量，进一步强化其在国家科技进步中的关键引擎作用。 # 2.4 面临的问题与展望 在过去的几十年里，机器博弈研究成果对推动人工智能发展具有重要意义，但我国在该领域迈向全球领先水平的过程中，仍面临一系列核心挑战与“卡脖子”技术瓶颈。 # （一）面临的关键问题与“卡脖子”技术瓶颈 具体而言，当前的局限性主要体现在以下四个相互关联的层面： 1. 底层算力底座受制于人，高端训练生态存在差距。我国机器博弈研究，特别是面向通用智能体的大规模模型训练，严重依赖国际巨头的高性能AI芯片（如GPU）及其封闭的软件生态。尽管国产AI芯片在特定场景已取得突破，但在支撑千亿参数级模型进行持续自我博弈所需的算力密度、互联带宽与软件栈成熟度上，与国际顶尖水平仍有差距，这直接制约了前沿探索的自主性与迭代效率。 2. 核心算法与框架创新不足，范式引领能力有待加强。当前主导性的算法范式（如Alpha系列、CFR系列）多由国外机构定义。国内研究多为跟踪、改进与应用，在开创具有全球影响力的通用非完备信息求解器、超大规模博弈树搜索新方法、以及多智能体协作与对抗的理论模型等方面，原创性贡献仍显不足。这导致我们在学术话语权和未来产业标准制定中易处于被动。 3. 开源平台与基准数据集生态薄弱，协同创新门槛高。相较于国际上有 OpenSpiel、PettingZoo 等被广泛采纳的开源平台和标准基准，国内缺乏统一的、高质量的机器博弈开发与评测基础设施。这抬高了广大研究者，尤其是中小团队和初学者的技术门槛，不利于形成协同创新的开源社区，也使得国内优秀成果在进行国际对标时面临障碍。 4. 高水平复合型人才短缺，产学研深度融合不足。机器博弈深度交叉的特性，要求人才兼具深厚的博弈论、人工智能与系统工程能力。 目前，既精通核心算法又能解决产业实际问题的尖端人才和工程师队伍供给不足。同时，产学研链条存在脱节：一方面，企业难以获得前沿算法的持续支持；另一方面，学术界的研究成果缺乏充足的资金与真实的场景进行工程化淬炼与产业化落地。 5. 伦理规范与安全治理体系尚不完善。随着机器博弈技术在军事、金融、自动驾驶等高风险领域的深度应用，其伴生的伦理与安全挑战日益凸显。首先，存在技术滥用风险，博弈决策能力可能被用于开发更高效的自主攻击系统、进行市场操纵或设计诱导成瘾的交互界面，对社会安全与公平构成潜在威胁。其次，算法面临偏见与价值对齐的严峻挑战，智能体在自我博弈中可能涌现出人类难以预测甚至违背人类价值观的策略，例如为达胜利不择手段，因此如何确保其决策与人类社会的安全、公正、可信等伦理准则对齐是一项巨大挑战。此外，责任归属的模糊性也带来了治理难题，当基于博弈AI的自主系统（如无人机、交易系统）造成损害时，其决策过程的黑箱特性使得事故责任认定变得极其困难。 # （二） 发展机遇与突破路径 尽管挑战严峻，但国家层面的战略指引为机器博弈的发展注入了强大动力。2017年国务院印发的《新一代人工智能发展规划》明确了包括智能决策理论在内的重点方向；2024年政府工作报告提出“人工智能+”行动，标志着AI与产业融合已上升为国家战略。为此，我们必须把握机遇，规划清晰的突破路径： 1. 聚力软硬件协同创新，夯实自主算力基础。设立专项鼓励国产 AI芯片厂商与顶尖研究团队合作，针对博弈负载进行芯片级优化，并共同构建成熟的国产软硬件一体化博弈算法栈，逐步在特定领域形成性能优势和应用生态。 2. 鼓励前沿探索与范式变革，力争算法引领。在国家重点研发计划中前瞻布局“通用博弈智能”等方向，鼓励高风险、高回报的原始创新。支持科研机构探索如大语言模型与博弈搜索融合等新路径，力争在核心算法和理论上实现从“0到1”的突破。 3. 构建开源开放平台，繁荣协同研发生态。由学会、头部企业联合高校，共同打造中国主导的机器博弈开源平台，集成主流项目接口、评估基准和算法库，并建设开放棋谱数据库。通过举办竞赛、设立基金等方式，快速吸引全球开发者，构建健康生态。 4. 深化产学研用融合，培养与汇聚高端人才。推动建立“企业出题、学界答题、成果共享”的联合实验室和创新联盟。以国家重大需求和应用场景为牵引，在实战中锤炼一支具备全链条能力的国家队，并依托竞赛和项目，大规模培养青年创新人才。 5. 构建负责任的创新体系，前瞻部署伦理与安全治理。在推动技术突破的同时，必须同步建立与之配套的伦理与安全框架。具体而言，应积极推动伦理准则研究，鼓励开展机器博弈的伦理学研究，明确技术开发的红线与底线，特别是在生命攸关和国计民生领域的应用规范。同时，需重点发展价值对齐与安全验证技术，在研究投入上支持安全、可靠、可控的博弈AI开发，致力于研发能够检测和纠正危险策略、确保系统行为符合设计预期的关键技术。此外，还应探索有 效的治理与监管机制，推动产学研各方共同参与，针对高风险应用场景建立审计、监督与问责机制，最终形成覆盖技术研发、部署与应用全周期的治理体系，确保技术创新始终行驶在健康发展的轨道上。 未来机器博弈将呈现多学科技术融合、产教学研相结合等趋势 (徐长明 et al., 2009)。具体体现在: # （1）复杂化 机器博弈研究的内容将不断拓宽，处理的问题复杂程度越来越高，信息量将越来越大。研究重点逐步由完备信息（完全信息、完美信息）博弈转到非完备信息（非完全信息、非完美信息）博弈。随着技术的进一步创新和应用场景的拓展，非完备信息博弈将展现出更为强大的实力和潜力，为人工智能领域的发展注入新的活力。 # (2) 固件化 机器博弈软件与硬件的结合越来越密切，固化机器博弈系统的智能硬件产品将越来越多的出现在人们的生活中，典型的应用包括：具有博弈思维能力的机器人、具有智能决策控制系统的无人驾驶汽车和具有群智博弈能力的无人机等。 # (3) 集成化 为解决某类特定问题，机器博弈技术将与并行计算、大数据、大模型、知识工程、群智算法、人工神经网络、深度学习、类脑思维等人工智能技术将进一步集成融合。 # （4）智能化 机器博弈技术将呈现高度智能化趋势，合理拓展现有博弈技术， 深入研究更加智能的普适算法，使得机器博弈程序的类脑智能越来越高。构建具有强人工智能（甚至超人工智能）能力的通用机器博弈系统，将成为未来机器博弈研究的重点。 # (5) 工程化 机器博弈越来越注重实际工程应用，紧密地结合经济、娱乐、医疗、教育、智能交通、航空航天、国防等各个领域实际问题，在此基础上开展一系列人工智能领域的科学研究。例如虚拟现实仿真智能教育、人机交互沉浸式体感游戏、航空航天多学科协同综合设计等。 # (6) 产业化 机器博弈研究学术成果加速向产业化转变，学术界与产业界的结合日趋紧密，助力游戏开发、智能教育、智慧医疗、交通运输、航空航天、国防等相关领域的产业发展。 另外，随着各种新技术被越来越多地运用到机器博弈中，作为机器博弈技术推广、交流与检验的平台，中国人工智能学会机器博弈专业委员会组织的各类计算机博弈比赛将越来越被社会各界所认同。 可以预见，随着机器博弈技术的快速发展，我们不仅要追求机器智能在博弈中能力的新高度，探索人机智能在协同中融合的新深度，更要肩负起引导技术向善、确保安全可控的新责任。机器的胜利是科学发展的必然，而构建对人类透明、可信、可协作且符合伦理规范的博弈智能，则是未来更大的挑战与机遇。推动机器博弈技术的负责任创新，确保其发展始终服务于人类的整体利益与社会的和平进步，这必将成为人类创造力与智慧在人工智能时代更为辉煌和成熟的结晶。 # 2.5 国际对比与发展启示 要清晰定位我国在全球机器博弈格局中的坐标，明确自身优势与短板，需从基础研究、驱动模式、平台生态与战略布局等多个维度进行系统性的国际对比。 1. 基础理论与核心算法：引领者与快速跟随者。全球机器博弈的创新范式长期由少数国际顶尖机构定义。美国与英国的研究机构（如DeepMind、OpenAI、卡耐基梅隆大学）扮演着“范式开创者”的角色，其成果如AlphaGo、AlphaZero、Libratus等，实现了深度学习与蒙特卡洛树搜索的结合、反事实遗憾最小化算法家族等基础性突破，旨在攻克星际争霸、Dota2等超高复杂度游戏，其目标直指通用人工智能。相比之下，中国的研究力量（以高校为主体）更多地扮演着“卓越的改进者与应用者”。我们展现出强大的工程实现与算法优化能力，能够迅速吸收国际先进算法，并将其高效应用于六子棋、藏族久棋、麻将等具有文化特色的博弈项目中，且在特定棋种的竞赛水平上已达世界前列。然而，在提出全新的、具有全球影响力的通用博弈理论模型与核心算法方面，原始创新贡献仍有提升空间。 2. 研究驱动模式：产业前沿与学术社群双轨并行。国际上前沿研究的驱动模式呈现出“产业界尖端实验室主导，顶尖高校深度协同”的鲜明特征。企业以前瞻的AGI愿景为牵引，投入巨量的计算与工程资源，其研究具备高度的系统性和连续性。中国的研发生态则以活跃的学术社群和大规模竞赛为核心驱动力，通过国家自然科学基金等项目支持，形成了独特的人才培养与技术创新土壤。尽管出现了腾讯“绝 艺”、新睿桥牌等产业界成功案例，但具备国际影响力的、以机器博弈为核心探索路径的顶级产业研究实验室仍相对匮乏，产业界在前沿探索的投入强度与战略纵深上，与国际同行存在差距。 3. 平台生态与赛事体系：开放标准与本土繁荣。国际上已形成由巨头或社区主导的、标准化的开源平台生态（如 OpenAI Gym、DeepMind 的 OpenSpiel），这些平台为全球研究者提供了统一的“起跑线”，加速了创新循环。与之配套的 ICGA 计算机奥林匹克、ACPC 年度计算机扑克大赛等赛事，因其历史积淀与项目前沿性，成为全球顶尖 AI 的试金石。中国则依托庞大的高校群体，构建了世界上规模最大、最具活力的本土竞赛体系，并在博弈平台技术上积累了丰富的工程经验。然而，国内平台多为满足特定竞赛需求的“专用平台”，在开放性、标准化与计算资源支持上存在局限，可能导致技术发展在特定领域形成“内循环”。我国赛事在本土化和参与规模上优势明显，但在项目的国际前沿性及赛事的全球影响力方面，仍有提升空间。 4. 战略布局：宏观指引与精准投入。中国拥有《新一代人工智能发展规划》等强大的国家顶层战略指引，为领域发展注入了强劲的政策动能，这是我国独特的制度优势。相较之下，美国等国更多依靠市场资本和科研基金进行“自下而上”的资源配置。然而，将宏观战略优势转化为在机器博弈这一具体领域的持久领先，需要更具针对性的部署。对比国际同行在特定方向的长期、集中投入，我国在设立类似DARPA大挑战的、以机器博弈为核心攻关内容的国家级重大专项方面，尚有可为空间，以期实现对关键“卡脖子”技术的集中突破。 中国机器博弈事业已奠定规模化和工程化的坚实基础。未来的发展，要求在持续发挥自身优势的同时，更主动地融入全球创新网络，力争在基础理论的原始创新、产业研究生态的构建、开源平台标准的制定等方面实现突破，从“应用大国”迈向“创新强国”。 # 第3章 博弈的复杂度 # 3.1 概述 计算机博弈属于人工智能领域的一个重要分支。计算机的博弈水平代表了计算机的智能水平。计算机博弈问题的状态复杂度和博弈树复杂度是衡量其复杂程度的两个重要标准。图3-1给出了求解博弈问题一般采取的四种策略。比如，博弈问题常用到的剪枝算法，它是为了避免分支过于庞大而采取的一种策略。这种策略可以节省计算机的内存空间，提高搜索效率，但也存在一定的风险，即如果估值函数不能准确地评估局面的话，这种算法可能将存在最佳着法的分支剪掉。当然，若博弈树复杂度比较小，就可以采用蛮力搜索的方式，只要时间允许，就可以找到最佳着法。 图3-1博弈问题的复杂度与求解策略之间的关系 文献(Herik, Uiterwijk, & Rijswijck, 2002)讨论了博弈问题的状态复杂度及其博弈树复杂度对寻找博弈问题理论解的意义，认为一个较低的状态复杂度比一个较低的博弈树复杂度对求解博弈问题所起的作用更大，因为状态复杂度为通过完全列举求解博弈问题的复杂度提供了一个边界值；而较低的博弈树复杂度主要是对搜索效率产生较大的影响。文献(Herik et al., 2002)还列出了一些常见博弈问题的状态复 杂度及博弈树复杂度（见表3-1）。 表 3-1 一些博弈问题的状态复杂度和博弈树复杂度 <table><tr><td>棋种</td><td>状态复杂度</td><td>博弈树复杂度</td></tr><tr><td>西洋跳棋（Checkers）</td><td>1021</td><td>1031</td></tr><tr><td>国际象棋（Chess）</td><td>1046</td><td>10123</td></tr><tr><td>中国象棋（Chinese Chess）</td><td>1048</td><td>10150</td></tr><tr><td>日本将棋（Shogi）</td><td>1071</td><td>10226</td></tr><tr><td>围棋（Go）(19×19)</td><td>10172</td><td>10360</td></tr></table> 文献(Herik et al., 2002)中，以tic-tac-toe（三子连珠棋）为例，估算了此博弈问题的状态复杂度和博弈树复杂度。tic-tac-toe共有9个位置可以落子，能够形成的局面较少，因此其复杂度的估算相对容易，具体估算过程如下： （1）对于其状态复杂度，由于棋盘上每个位置有三种状态（双方的棋子和空白），因此，状态复杂度可估算为 $3^{9}$ ，根据此博弈问题的走棋规则，在棋盘上形成连3则游戏结束，出现两个以上的连3的局面属于非法局面。而对称相同的多个局面应该只算作一个局面。将这些考虑在内，则更精确的状态复杂度为5478； （2）对于其博弈树复杂度，平均深度约为9，第i（ $1 \leqslant i \leqslant 9$ ）层时，走棋方可能的走法有9-i个，因此，此博弈树的叶子节点数（即博弈树复杂度）为9！。 计算机博弈的最高境界就是找到该棋种的理想解，即不败解。而计算机博弈的最大困难和无法逾越的障碍则是问题的计算复杂性。对问题的计算复杂性进行分类，可以了解该问题被求解的难易程度，如果问题被证明是难解的（比如 NP-complete、PSPACE-complete 及 EXPTIME-complete），则不必将大量的精力花费在寻找问题的理论解上，而只能去寻求某种近似解。事实上，当前多数人工智能问题都是追求满意解，大部分原因就是问题的复杂度远远超过当前计算设备能以合理性价比的求解代价，从而推动着各类博弈算法、策略的研究。 # 3.2 博弈问题的状态复杂度及其估算方法 # 3.2.1 博弈问题的状态复杂度定义 博弈过程的局面称之为状态，博弈问题的状态复杂度是指从初始局面出发，产生的所有合法局面的总和。然而，精确计算博弈问题（比如：国际象棋、围棋等）的状态复杂度几乎是不可能的(V. Allis, 1993)。一般以该棋类可能的局面总数的上限值为标准。它为通过完全列举求解博弈问题的复杂度提供了一个边界值。 $8 \times 8$ 的西洋跳棋（Checkers）于2007年得到了理论解(Jonathan Schaeffer et al., 2007)，证明过程中，采用了三种方法：证据计数法，残局阶段采用了数据库，通过两个程序实现对节点的估值。不仅证明了一种不败的策略，而且计算了 $8 \times 8$ 的西洋跳棋可能会产生500,995,484,682,338,672,639（约 $5 \times 10^{20}$ ）个合法局面。可见，只有得到了理论解的博弈问题，才能比较精确地计算其状态复杂度。估算博弈问题的状态复杂度，与各个博弈问题的走棋规则密切相关，下面以亚马逊和苏拉卡尔塔棋为例，估算这两个博弈问题的状态复杂度。 # 3.2.1.1 亚马逊棋的状态复杂度 1. 亚马逊棋的走棋规则 棋盘与棋子（棋盘见图3-2）： 1)棋盘规模为 $10 \times 10$ 个方格, 相邻两个方格填充的颜色不同; 2) 比赛双方各有 4 个棋子; 每个棋子都相当于国际象棋中的皇后, 它们的走棋规则与皇后相同(Lieberum, 2005)。 走棋规则： 1)每次开局由位于棋盘下方的玩家先手； 2) 当轮到一方走棋时，此方只能而且必须移动 4 个棋子中的一个，在移动完成后，该棋子必须释放一个障碍，障碍的释放方法与棋子的移动方法相同（不能穿过障碍）； 3) 当某个走棋方在完成一次移动后, 对方的 4 个棋子均不能再移动时, 对方输掉比赛。 图3-2亚马逊棋棋盘 # 2.估算亚马逊棋的状态复杂度 如图3-2所示，亚马逊棋棋盘的大小为 $10 \times 10$ ，共100个格，双方棋子的走法与国际象棋的皇后相同（就是说棋子可以移动到任意一个格子上），因此每个格子可以出现白方棋子、黑方棋子、障碍、空白四种情况，所以亚马逊棋的状态复杂度可以估算为 $4^{100}$ ，以10为底的形式表示，大小约为 $10^{60}$ 。在产生的这些局面中，有很多非法的局面，根据亚马逊棋的规则，棋盘上双方各有4个棋子，而这种估算方法，显然有很多局面中出现的棋子数超过了8个。 这里从另一个角度来估算其状态复杂度，由于棋盘上始终存在双方的各4个棋子，也就是说棋盘上有8个交叉点需要用来放置这8个棋子，而棋盘上的其他交叉点可能的状态为空白或障碍，因此亚马逊棋的状态复杂度可估算为 $10^{41}$ 。 # 3.2.1.2 苏拉卡尔塔棋的状态复杂度 # 1.苏拉卡尔塔棋棋规 棋盘与棋子（见图3-3）： (1) 横竖各 6 条边构成正方形棋盘, 36 个交叉点为棋位, 各边由 8 段圆弧连接, 通常用 2 种不同颜色表示。 (2) 红黑双方各 12 枚棋子。初始状态: 棋子各方底线排成 2 排。 图3-3苏拉卡尔塔棋棋盘 走棋规则： (1) 双方轮流走棋, 每次走动一枚棋子; (2) 除了吃子之外, 每枚棋子只能沿着垂直、水平或对角方向走动一格, 只能走向空位; (3) 吃对方棋子时必须经过至少一个完整的弧线; (4) 赢棋标准: 吃掉所有对方棋子或最后剩余棋子多的一方获胜。 # 2. 估算苏拉卡尔塔棋的状态复杂度 棋盘上总共有36个交叉点，每个交叉点有三个可能的状态（即双方的棋子或空白），所以苏拉卡尔塔棋的状态复杂度可估算为 $3^{36}$ ，以对数值（10为底）的形式表示，则大小约为17.2，这些局面中存在一些非法的局面，比如：根据规则，棋盘上最多只能出现24个棋子，而以这种估算方法，显然有一些局面中棋子的个数已经超过了24个。因此，可以换一种角度来估算，根据苏拉卡尔塔的规则，初始状态时，双方各有12个棋子，棋盘上最多会出现24个棋子，因此应该将棋盘上出现36个棋子、35个棋子、...、25个棋子的这些局面去除掉。因此，苏拉卡尔塔棋更精确的状态复杂度以对数值（10为底）的形式表示，则大小约为16.9。 # 3.2.2 博弈问题的博弈树复杂度 # 3.2.2.1 博弈树搜索算法原理 对于完备信息的博弈系统，其搜索一般都是基于博弈树搜索算法，如图3-4所示，这样可以展开双方所有可能走法产生的局面（博弈树中的节点），再通过估值函数来评价各个局面的优劣，从而可以找到最佳走法。 图3-4一个博弈树实例 博弈树是一颗根在上叶在下的树，分若干层，每一层代表某一走棋方可以走出的合法局面。对于只添子的棋类博弈系统（如五子棋、六子棋），博弈树中各个节点（局面）互不相同（这里指在一盘棋局中节点的状态，若交换先后手，则存在完全相同的节点）；对于存在移动棋子的棋类博弈系统（如国际象棋、中国象棋），博弈树中就会存在完全相同的节点（局面）。 # 3.2.2.2 博弈树复杂度的定义 博弈树复杂度是指从初始局面开始，其解决树（Solution tree，解决树是指得到理论解所需展开的最小搜索树）的所有叶子节点的总和(V. Allis, 1993)。精确计算出博弈问题（如：国际象棋）的初始局面解决树的所有叶子节点总和几乎是不可行的，若能实现，那实际上就已经找到了该博弈问题的理论解（国际象棋被证明是难解的(Fraenkel & Lichtenstein, 1981)）。因此，对于比较复杂的博弈问题（如：围棋、中国象棋、亚马逊棋、六子棋等），一般采用平均分支因子(李志敏，罗里波，& 李祥，2008)的方法来估算博弈树复杂度。文献(Matsubara, Iida, Grimbergen, & al., 1997)阐述了如何采用平均分支因子的方法来估算国际象棋、围棋、日本将棋的博弈树复杂度。对于相对简单（如：tic-tac-toe）的博弈问题，可以采用蛮力搜索来精确地计算其博弈树复杂度。下面，以六子棋和点格棋为例，估算这两个博弈问题的博弈树 复杂度。 # 3.2.2.3 六子棋的博弈树复杂度 # 1.六子棋棋规 棋盘与棋子（如图3-5所示）： (1) 国际比赛中, 六子棋棋盘规模为 $19 \times 19$ , 共 361 个交叉点,初始状态时棋盘上无任何棋子; (2) 六子棋的棋子与围棋的棋子一样, 只有黑、白两种颜色的棋子。 图3-5六子棋棋盘 走棋规则： (1) 黑方先手, 第一步只下一个子, 随后每一方须下两子; (2) 先走出同色连六（方向可为横、纵、斜 $45^{\circ}$ 、斜 $135^{\circ}$ ）的一方获胜(I Chen Wu, Huang, & Chang, 2005)。 不难看出走棋方能够下的点比较多，若完全采用博弈树展开的话，产生的节点数是巨大的。这严重影响了系统的执行效率。因此六子棋的搜索算法一般采用 VCF（Victory of Continuous Fours）迫着算法（与五子棋类似的搜索算法）。但由于 VCF 算法对于复杂的局面考虑的不够全面，所以对于特殊局面（估值很高或很低的局面）可以 适时地采用基于博弈树的搜索算法进行深层次的搜索以获得更好的走法。 # 2.估算六子棋的博弈树复杂度 根据六子棋的走棋规则，不存在吃子的情况，只向棋盘添子，因此不同的走法所产生的局面互不相同。走棋方从第二步开始，每次下两子形成一个局面。因此六子棋博弈树复杂度的计算方法如下： 根据文献(I Chen Wu et al., 2005)，六子棋的博弈树搜索平均深度为30。在游戏开始时，第一步有361个点可下，第二步有 $C_{360}^{2}$ 个点可下，以此类推，一直到它的平均深度，即第30步，有 $C_{302}^{2}$ 个点可下。其中应排除棋盘上所有的连珠数等于六的情况（六子连珠为六子棋获胜的条件），这里包括黑子或白子在横向（出现同色六子连珠的局面数为 $14 \times 19 \times 2$ ）、纵向（出现同色六子连珠的局面数同横向）及所有斜 $45^{\circ}$ 和 $135^{\circ}$ 线（出现同色六子连珠的局面数为 $(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14) \times 2 \times 2$ ，即420）上所有产生同色六子连珠的局面，即棋盘上可能出现的连六总数为 $\text{Count}(6) = 952$ 。为了排除博弈树中出现的这些非法局面，我们将博弈树各层产生的结点总数都减掉 $\text{Count}(6)$ 。 根据六子棋的走棋规则，从第六层开始，棋盘上存在出现六子连珠的情况，因此从第六层开始，每层都减去Count(6)，具体计算如下： 第六层产生的节点数为: $$ \text {C o u n t p o i n t s} (6) = 3 6 1 \times C _ {3 6 0} ^ {2} \times \dots \times C _ {3 5 2} ^ {2} - 9 5 2 $$ 第七层产生的节点数为: $$ \text {C o u n t p o i n t s} (7) = \text {C o u n t p o i n t s} (6) \times \mathrm {C} _ {3 5 0} ^ {2} - 9 5 2 $$ 以此类推，第 $\mathbf{n}$ 层产生的节点数为： $$ \operatorname {C o u n t p o i n t s} (\mathrm {n}) = \operatorname {C o u n t p o i n t s} (\mathrm {n} - 1) \times C _ {3 5 2 - (n - 6) \times 2} ^ {2} - 9 5 2 $$ 因此，经计算得出六子棋的博弈树复杂度的上限值为 $10^{145}$ 。 # 3.2.2.4 点格棋的博弈树复杂度 # 1. 点格棋的棋规 棋盘和棋子（如图3-6所示）： (1) 对于 $6 \times 6$ 点格棋, 棋盘的初始状态为 36 个点, 而没有任何连线; (2) 点格棋没有棋子的概念, 完成一盘点格棋的对局需要 60 个边 (邻近两点连成的一个边)。 走棋规则： (1) 某方走棋会占至少一个边, 所以邻近两个点之间有两种可能 (有或无边), 不可越点, 不可重复连线; (2) 当一个格子的四条边均被占满, 则最后一个连线者获取这个格子, 并且该走棋方将继续走棋 (选择某两个邻近点进行连线); (3) 走棋的结束标志是该走棋方连线后未获取格子; (4) 游戏结束的标志: 所有的邻近点均被连线, 也就是说所有的格子被俘获。占领格子更多的一方获胜(Berlekamp, 2000)。 图3-6点格棋棋盘 # 2.估算点格棋的博弈树复杂度 估算点格棋的博弈树复杂度的方法与tic-tac-toe类似。根据点格棋的规则，双方交替在 $6 \times 6$ 棋盘上的邻近两点之间连一条直线，最终将完成所有邻近两点的连线（共60个），即比赛结束。也就是在比赛开始时，某走棋方可以在60个连线中，选择一个，从而完成第一步走棋；接下来，另一走棋方能够在剩下的59个连线中，选择一个来完成走棋，以此类推，即使根据规则，某一方在完成一步走棋后，形成了一个闭合的格子，该走棋方同样要从所有未形成连线的某两个邻近点之间来继续连线。最终结束的标志是所有的邻近点都被连线。因此，点格棋的博弈树复杂度可估算为60！，如果以10为底的形式表示，约为 $10^{82}$ ，这是一个天荒地老的巨型数值，即使当今最先进的计算设备也不能在机器博弈规定的有限时间（比如15秒/步）内完成。 # 3.3 博弈问题的计算复杂性 国外有很多学者都在研究计算机博弈问题的计算复杂性，比如： (1) 国际象棋 (Fraenkel & Lichtenstein, 1981) 和西洋跳棋 (Robson, 2006) 被证明属于 EXPTIME-complete 问题, 这两个棋种的计算复杂性证明, 在构建模型的过程中, 在广义化的棋盘上模拟进行一种已被证明为 EXPTIME-complete 问题的 $\mathrm{G}_{3}$ 游戏 (Stockmeyer & Chandra, 2006), 并最终证明了 $\mathrm{G}_{3}$ 游戏可多项式时间内归约到被广义化的国际跳棋（西洋跳棋）; （2）围棋被证明属于PSPACE-hard问题(Lichtenstein & Sipser, 1980)，五子棋(Reisch, 1980)、六子棋(Ming & Tsai, 2007)、奥赛罗棋 (Kasai, 1994)被证明属于 PSPACE-complete 问题，这些棋种的计算复杂性证明，都用到了广义地理学游戏（Generalized Geography Game(Sipser, 2006));亚马逊被证明属于 PSPACE-complete 问题(Hearn, 2005)，在证明过程中，它采用了一种公式博弈（Formula Game(Sipser, 2006)）。 国际上被广大学者认可的机器博弈问题，在比赛规则上对参与比赛的任何一方都是十分公平的。因为只有是公平的，这样的博弈问题才具有长期存在的意义，但也正是这种公平性，大大增加了计算机博弈问题求解的难度。因此被广泛认可的博弈问题，其计算复杂性一般都属于某复杂性类的 hard（困难问题）或 complete（完全问题）（属于此类计算复杂性类的问题被认为是难解或是最难解的）。 对博弈问题的计算复杂性证明, 前提条件是该博弈系统对应的棋盘是广义的, 即无限大 (一般为 $n \times n$ )。如果是固定大小的棋盘 (如围棋的 $19 \times 19$ ), 其复杂性是常量 (无论在空间上还是在时间上), 对问题的计算复杂性证明没有意义。 对于连珠类的博弈系统的计算复杂性证明已有一些成果。连珠类的博弈系统属于填子游戏，其一般的棋盘采用 $n \times n$ 类似围棋的棋盘，该博弈系统的游戏规则是走棋双方交替地向棋盘填子，直到形成同色的 $k$ 子连珠，则该方获胜，如广为流行的四子棋（Connect-Four）、五子棋（Go-moku）和六子棋（Connect6）。这一类博弈系统一般用函数 Connect(m,n,k,p,q)(Ming & Tsai, 2007)表示，其中 $m$ 、 $n$ 表示横、纵交叉点的数量， $k$ 表示走棋规则中获胜的条件，即形成同色连珠所 包含的棋子数。p 指第一手落几个棋子，q 规定第一手之后走棋方每轮落子的数量。 证明该类型博弈问题的计算复杂性属于PSPACE-complete问题，要根据PSPACE-complete的定义(Kasai, 1994)逐条进行证明。根据此定义的第二个条件，我们需要证明所有属于PSPACE的问题都归约到该判定问题（即该类型博弈问题），这基本是不可能做到的，需要换一个思路，如果找到一个被证明属于PSPACE-complete问题的解决方法，那么利用该判定问题的解决方法就可以解决所有的PSPACE问题，因此只需要找到一个已经被证明属于PSPACE-complete的判定问题，并证明它可归约到该类型博弈系统。证明问题属于PSPACE-complete的一般选择的是广义地理学游戏。 证明此类博弈问题属于PSPACE-complete的思路基本相同，证明过程如下： (1) 证明该博弈问题属于 PSPACE 问题; (2) 根据 PSPACE-complete 定义的第二个条件, 需要找到一个已经被证明属于 PSPACE-complete 的判定问题; (3) 在属于该博弈问题棋盘上构建一个归约模型, 即特定局面; (4) 在该模型中, 模拟解决步骤 2 中选择的判定问题; （5）若在步骤4中，找到了一个解决方法（即必胜策略）。则说明步骤2中所选择的判定问题可归约到该博弈问题。即满足了PSPACE-complete定义的第二个条件； (6) 根据步骤 5 和步骤 1, 可知该博弈问题满足定义的两个条 件。由此得证该类型博弈问题的计算复杂性属于 PSPACE-complete。若步骤 1 不成立，而步骤 5 成立，则该博弈问题只满足定义的第二个条件，因此根据相关定义可知该博弈问题的计算复杂性属于 PSPACE-hard。文献(Ming & Tsai, 2007)和文献(Kasai, 1994)就是采用了上述的证明思路。在问题的计算复杂性证明过程中，构建一个适当的归约模型至关重要，这种模型要模拟进行广义地理学游戏，也就是该模型是一个二维有向图（需要将此二维有向图嵌入到连珠棋棋盘上(Ming & Tsai, 2007)），由于广义地理学是一种两个参与者的游戏，因此必须迫使双方每轮走棋都只有一个走法可选择，若不选择该走法，则该走棋方会立即输棋。 在文献(Ming & Tsai, 2007)中，在 $n \times n$ 的棋盘上，构建一个特殊模型（见图3-7），其中包括：1个仿真区域、1个获胜区域、p-1个辅助区域。其中仿真区域和辅助区域模拟进行广义地理学游戏，每轮双方分别向仿真区域落一个棋子、向辅助区域落p-1个棋子，直到仿真区域已满，这样该走棋方将向获胜区域下一个棋子，该走棋方的迫着数将大于1，对方必输（对方只有一个棋子可以落在获胜区域，只能解决一个迫着）。由此得到某走棋方的必胜策略。进而说明广义地理学在连珠棋盘上可以被求解。也就是说广义地理学多项式时间可归约到该博弈系统，从而说明其他的属于PSPACE的判定问题可归约到该博弈系统，因此满足PSPACE-complete定义的第二个条件，得证。 图3-7一个六子棋的特定模型 # 第4章 机器博弈的典型技术 # 4.1 概述 机器博弈系统中，典型的关键技术主要包括策略搜索、局面评估与优化、神经网络的学习与训练等技术，它们是决定博弈结果的关键因素。以国际跳棋、中国象棋、围棋等为代表的传统二人零和完备信息博弈，其博弈理论已经很成熟。 近几年来，随着计算机硬件算力提升，神经网络、机器学习、大数据、大模型等技术快速发展。特别是GPU、TPU并行计算技术的广泛应用，使得神经网络+深度学习变得更加便宜、快速、实用与有效，机器博弈系统的计算与逻辑思维能力也得到大幅提升。 尽管依靠加大搜索深度可以适当提升博弈系统的 AI，但同样也使得计算量大幅提升。在实际机器博弈项目中，通常有博弈实时博弈时间限制的要求，类似宽度优先搜索、穷尽搜索和盲目搜索一类的算法，时间和空间开销巨大，难以做到很深的搜索。因此，基本上不可能直接使用此类算法去解决相关问题，也不能单纯依靠加大搜索深度提高机器博弈能力。在机器博弈中，引入必要的相关知识会大幅提升 AI 能力，降低计算量。先验知识越丰富、越正确、对博弈局面评估得越准确，获胜的几率就越高。 # 4.2 穷尽搜索 极大极小算法是最基本典型的穷尽搜索方法，它奠定了机器博弈的理论基础(Herik et al., 2002)。极小化极大算法通过构建一棵博弈树来寻找最优解。在博弈树中，每个节点代表一个游戏状态，而边 代表可能的走法。极小化极大算法会从叶子节点（游戏的最终状态）开始，向上评估每个节点的值，直到根节点，从而确定最优的走法。然而，这种方法在面对大型博弈树时计算量巨大，因此需要剪枝算法来减少不必要的计算。 通过极大极小算法可以找到对于博弈双方都是最优的博弈值，但该算法对博弈树的搜索是一种变性搜索，算法实现相对麻烦。负极大值算法是在极大极小算法基础上进行的改进算法，把极小节点值（返回给搜索引擎的局面估值）取绝对值，这样每次递归都选取最大值。 # 4.3 裁剪搜索 裁剪算法也称剪枝算法，是机器博弈中最常用的主流算法，它包括深度优先的Alpha-Beta剪枝搜索(Baudet & M., 1978)和以此为基础改进与增强的算法，如渴望窗口搜索（Aspiration search）(Lu & Xia, 2008)、MTD(f)（Memory-enhanced Test Driver with f and n)搜索(Jing, 2008)等。在具体应用中，合理地交叉使用各种搜索方法，可以具有更高的效率。 1. Alpha-Beta 剪枝(Baudet & M., 1978; Leifker & Kanal, 1985) Alpha-Beta 剪枝是在极大极小算法基础上的改进算法，是其它剪枝算法的基础。它通过引入两个参数 Alpha 和 Beta 来减少搜索的节点数，其中 Alpha 代表当前搜索分支中己方可能获得的最大值，Beta 代表对方可能获得的最小值。在搜索过程中，如果某个节点的值已经确定比 Alpha 小（对于己方）或比 Beta 大（对于对方），那么这个节点以下的分支就不需要继续搜索，因为它们不可能是最优 解。这种剪枝可以显著减少搜索空间，提高搜索效率。 目前，多数博弈程序都采用负极大值形式的Alpha-Beta搜索算法。为保证Alpha-Beta搜索算法的效率，需要调整树的结构，即对搜索节点排序，确保尽早剪枝。 2.渴望搜索(Kaindl & Shams，1991；Lu & Xia，2008) 渴望搜索是在 Alpha-Beta 搜索算法基础上，缩小搜索范围的改进算法。渴望搜索从一开始就使用小的窗口，从而在搜索之初，就可以进行大量的剪枝。通常，渴望搜索与遍历深化技术结合使用，以提高搜索性能。 3.MTD(f)搜索(Jing，2008) MTD(f)算法实际上就是不断应用零窗口的Alpha-Beta搜索，缩小上界和下界，并移动初始值使其接近最优着法。MTD(f)算法简单高效，在国际象棋、国际跳棋等博弈程序里，MTD(f)算法平均表现出色。 此外，还有各种在Alpha-Beta搜索基础上优化的算法，例如，有学者提出在博弈树同层结点中，用广度优先搜索，接力式空窗探测，平均搜索效率高于MTD(f)搜索(张明亮 & 李凡长，2009)。通常，裁剪算法需要与置换表技术相结合，以减少博弈树的规模，提高搜索效率。 # 4.4 启发式算法 “启发”（Heuristic）是指通过排序让 Alpha-Beta 剪枝的搜索树尽可能地接近最小树，优先搜索好的着法。启发通常有置换表启发、历史启发和杀手启发等常用的算法。 1. 置换表启发(Donkers, Uiterwijk, & Herik, 2001; 焦尚彬 & 刘丁, 2010) 置换表是一个大的直接访问表，用来存储已经搜索过结点（或者子树）的结果，下次搜索遇到时直接运用。置换表的构造，一般使用Hash表和ZobristHash技术来实现。 合理使用置换表，可以提高搜索效率，当博弈树的深度很大时，置换表对内存空间要求巨大。通常的对策是对置换表分配有限大小，并采用散列方式管理存取。具体应用到各个棋种中时，还要根据实际局面的节点类型进行处理。 置换表启发是置换表与Alpha-Beta剪枝算法相结合的产物。在中国象棋等棋种中，通过引进置换表启发技术来增强搜索效率。 2. 历史启发（History Heuristic）(J. Schaeffer, 1989) 历史启发也是迎合Alpha-Beta搜索对节点排列顺序敏感的特点来提高剪枝效率的。它维护着法历史，每当遇到好的着法，就给其历史得分一个相应的增量，使其具有更高的优先被搜索的权利。 3.杀手启发（Killer Heuristic）(Sakuta, Hashimoto, Nagashima, Uiterwijk, & Iida, 2003) 杀手启发可以看作是历史启发的特例，它把同层中引发剪枝最多的节点称为杀手，当下次搜索到同一层时，如果杀手移动是合法的话，就优先搜索杀手。杀手启发可以对着法进行动态重排序，提高了置换表的使用效率。 研究表明，历史启发与置换表技术结合可以大幅减少博弈树空 间, 在残局阶段应用杀手启发算法可以明显节约时间 (Sakuta et al., 2003; J. Schaeffer, 1989)。 # 4.5 迭代深化 迭代深化（Iterative Deepening）也称为遍历深化，是一种常用的蛮力搜索机制，经常使用在深度优先搜索中(Reinefeld & Marsland, 1994)。迭代深化最初是作为控制时间的机制而提出的，通过对博弈树进行多次遍历，并逐渐提高搜索深度，一直到指定的时间停止。 迭代深化利用Alpha-Beta剪枝算法对子节点排序敏感的特点，使用上次迭代后得到的博弈值，作为当前迭代的搜索窗口估值，以此为启发式信息计算当前迭代的博弈值。另外，它利用时间控制遍历次数，只要时间一到，搜索立即停止。在关键的开局和残局，由于分支较少，可以进行较深层次的搜索。Alpha-Beta剪枝经过一系列技术如置换表、历史启发、迭代深化等增强后，其性能可大幅提高。 # 4.6 最佳优先算法 最佳优先的搜索算法，不受节点排序的影响，其搜索空间小于深度优先的最小树，理论上应该优于深度优先。实际上，最佳优先算法仍处于理论研究阶段。最佳优先算法分为两类：采用极大极小算法取值的SSS*算法(T. A. Marsland, Reinefeld, & Schaeffer, 1987; Plaat, Schaeffer, Pijls, & Bruin, 1994)和DUAL*算法，不采用极大极小方法取值的B*(Berliner, 1979)和PB*(Hans et al., 1996)算法。 # 1. SSS*和DUAL*算法 SSS*和DUAL*算法都属于状态空间搜索（State Space Search），把极大极小树看成状态图，在不同的分支上展开多条路径，并且维护一个关于状态图的全局信息表。这两种算法是两个操作相反的过程，前者在搜索深度为偶数的极大极小搜索中表现较佳，后者则在深度为奇数搜索中较佳。 SSS*和DUAL*算法都过于复杂，难于理解，且时间和空间开销较大，在机器博弈中实际应用较少。 # 2. B*和PB*算法 B*算法用一个乐观值和一个悲观值来评价节点。当根节点的一个子节点的悲观值不比所有其它节点的乐观值差的时候，B*算法就结束了。算法搜索控制的关键是尽快找到终止条件。由于它对局面估值的依赖性太强，估值的可信度将直接影响最终结果。 PB*算法就是基于概率的B*算法，这个算法对概率的准确估计比较敏感，实现困难。 # 4.7 随机搜索算法 随机搜索算法主要通过对状态空间进行抽样来寻找近似最优解。其基本形式包括 拉斯维加斯算法与蒙特卡罗算法两类：前者在理论上保证能够找到最优解，但对采样次数无上限；后者在有限采样条件下逐渐逼近最优解，更适用于资源受限的决策场景。在机器博弈中，由于每步决策的时间与空间受到严格限制，且通常只需求得局部较优解，因此蒙特卡罗类算法更为常用。 1. 蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）(Baier & Winands, 2011; Browne et al., 2012; Guez, Silver, & Dayan, 2013; Lorentz, 2016) 蒙特卡洛树搜索是一种用于某些决策过程中的启发式搜索算法，特别适用于机器博弈这类具有巨大状态空间的问题。它通过随机模拟来构建搜索树，而非依赖精确的估值函数，从而在复杂博弈中表现出色。 在人工智能的问题中，蒙特卡洛树搜索是一种最优决策方法，它结合了随机模拟的一般性和树搜索的准确性。由于海量搜索空间、评估棋局和落子行为的难度，围棋长期以来被视为人工智能领域最具挑战的经典游戏。近年来，MCTS 在类似计算机围棋等完备信息博弈、多人博弈以及其它随机类博弈难题上的成功应用而受到快速关注 (Raiko & Peltonen, 2008)。理论上，MCTS 可以被用在以{状态，行动}定义并用模拟预测输出结果的任何领域。 蒙特卡洛树搜索不仅在棋类游戏如围棋、国际象棋中表现出色，也被应用于其他需要决策的场景，如机器人路径规划、实时策略游戏等。它的一个关键优势是它不需要对游戏状态的精确评估，而是通过大量的模拟来近似最优解，这使得它在处理复杂和未知的游戏状态时特别有用。 MCTS 通过随机抽样来探索决策空间，并根据模拟结果构建搜索树，以寻找最优决策。这种算法最初是为了解决博弈问题而设计的，它通过大量的随机采样来估计未知量，特别适用于完全信息游戏、零 和游戏以及离散和确定性游戏。 MCTS 的每一次迭代都包含四个核心步骤（如图 4-1 所示）： 选择（Selection）：从根节点（当前局面）开始，递归地选择最优的子节点，直至到达一个可扩展的叶节点。选择策略通常基于Upper Confidence Bound（UCB）公式，以平衡“利用”已知高收益节点和“探索”访问次数少的节点。 扩展（Expansion）：当选择的叶节点不是终止状态时，为其创建一个或多个新的子节点。 模拟（Simulation）：从新扩展的节点开始，运行一段快速的随机对弈（即“走棋”），直至到达游戏终局，并得到一个胜负结果。 反向传播（Backpropagation）：将模拟得到的结局结果沿着之前选择的路径反向传递，更新路径上所有节点的统计信息（如访问次数、累计收益）。 图4-1构造MCTS博弈树的过程 MCTS 算法适用于非完备信息博弈，也适用于有较大分支因子的博弈程序，例如,AlphaGo 就是采用 MCTS 算法进行搜索(David Silver et al., 2016)。 2. UCT 搜索算法 (Gelly & Silver, 2007b; Zhang, Wang, Lin, & Xu, 2008) UCT 算法是将 UCB 公式应用于 MCTS 的典型代表。UCT 使得 MCTS 在超大规模博弈树的搜索过程中，表现出优异的时间和空间效率，目前已广泛应用于围棋、亚马逊棋、不围棋等完备信息博弈，以及幻影围棋、德州扑克等非完备信息博弈中，成为现代机器博弈的核心算法之一。 相对于传统的搜索算法，UCT时间可控，具有更好的鲁棒性，可以非对称动态扩展博弈树，在超大规模博弈树的搜索过程中，表现出时间和空间方面的优势。目前，UCT在搜索规模较大的完备信息博弈、复杂的多人博弈、非完备信息博弈以及随机类博弈项目中，表现出色(Hashimoto，Kishimoto，Yoshizoe，&Ikeda，2011；Kato，Takaya,&Yamamura，2015；Raiko & Peltonen，2008)。据不完全统计，国内机器博弈比赛成绩较好的队伍，绝大部分采用了UCT搜索算法。 # 4.8 并行计算 并行计算(T. A Marsland & Campbell, 1982)是为了提高计算速度，结合云计算、工作站集群、多核高性能计算机、并行机系统等技术(蔡晔, 2015; 陈国良, 孙广中, 徐云, & 龙柏, 2009; 计永昶, 丁卫群, 陈国良, & 安虹, 2001; 李之棠 & 陈华民, 1998), 充分发挥计算机强大的并行处理能力。在机器博弈中，运用并行技术把博弈树动态分开，同时执行多个指令，可以在不裁剪和缩小博弈树的规模情况下，提高搜索、训练、分析的速度，优化系统性能。 并行计算主要有两种体系，单机体系 SMP（Symmetric Multiprocessor，对称多处理器）和分布式体系 Cluster（计算机集群），对应多线程并行和多机并行。两者最大的区别是，前者可以共 享存储器（并且共享同一地址的存储单元），后者则必须通过网络来交换数据。 近年来，网络并行计算及多CPU、多核技术的研究日趋成熟，尤其是CPU/GPU异构混合并行系统，以其强劲计算能力、高性价比和低能耗等特点，成为新型高性能计算平台(曹婷婷，2009；卢风顺，宋君强，银福康，&张理论，2011；聂慧，彭娇，金晶，&李康顺，2017；王京辉 & 乔卫民，2005；杨冰，2015)。机器博弈中，由于博弈搜索通常需要用到置换表，故适合采用基于SMP方式的多线程并行计算。随着大数据、云计算等技术的成熟与完善，CPU/GPU集群等并行技术被越来越多地运用到机器博弈，特别是用于深度神经网络模型训练中，达到快速训练深层模型的目的。 # 4.9 遗传算法 遗传算法是人工智能领域的关键技术，它是一种非数值、并行、随机优化、搜索启发式的算法，通过模拟自然进化过程随机化搜索最优解。它采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向、不需要确定的规则，同时具有内在的隐并行性和更好的全局寻优能力（吉根林，2004）。 遗传算法是解决搜索问题的一种通用算法，在机器博弈中，遗传算法通常被用于搜索、自适应调整和优化局面评估参数。它的基本思想是将博弈树看作遗传操作的种群，博弈树中由根节点到叶子节点组成的所有子树为种群中的个体。根据优化目标设计评估函数，计算种群中每个个体的适应度函数值，依据适应度函数值的大小确定初始种 群，让适应性强（适应度函数值大）的个体获得较多的交叉、遗传机会，生成新的子代个体，通过反复迭代，可得到满意解。 采用遗传算法优化局面估值时，可根据博弈程序与其他程序对弈的结果，检验某一组参数获胜的几率。经过多次试验，通常可以找到较好的估值参数。传统的算法一般只能维护一组最优解，遗传算法可以同时维护多组最优解。在实践中，遗传算法被引入了中国象棋、国际象棋、亚马逊棋以及禅宗花园游戏等博弈系统的智能搜索与评估优化中，效果还是很明显的(Amos & Coldridge, 2012; Esparcia-Alcázar, Martínez-García, Mora, Merelo, & García-Sánchez, 2010; Kim & Kim, 2013; Liaw, Wang, Tsai, Ko, & Hao, 2013；吉根林, 2004；王骄 et al., 2005；王书宇, 李龙澍, & 汪群山, 2008)。 # 4.10 路径寻迹算法 路径寻迹算法是一类用于在图或网格中找到从起点到目标点的最优路径的算法。在机器博弈中，这些算法可以用来模拟或优化玩家或计算机在游戏中的移动策略。以下是几个常见路径寻迹算法在机器博弈中的应用解释： # 1. Dijkstra 算法(Dijkstra, 1959) Dijkstra 算法主要用于找到从单一起点到所有其他点的最短路径, 前提是每条边的权重非负。在机器博弈中, 如果每个游戏动作 (例如移动到相邻格子) 的代价相等, Dijkstra 算法可以用来规划玩家的移动路径。例如, 在战略游戏中, Dijkstra 算法可以帮助单位找 到最短路径去敌人或目标点。 # 2. A*算法(Hart，Nilsson，& Raphael，1972) A*算法是一种广泛应用于游戏和机器人导航的路径寻迹算法。它结合了启发式搜索和标准的Dijkstra算法，通过引入启发函数（通常是估算从当前节点到目标节点的代价）来优化搜索效率。在机器博弈中，A*算法可以帮助AI找到到达目标的最优路径，适用于需要动态评估和优化路径的复杂游戏环境。 # 3. 广度优先搜索（BFS）(Moore, 1959) BFS 是一种无权图搜索算法，确保找到从起点到目标点的最短路径。在机器博弈中，BFS 适用于状态空间较小的游戏（如简单的棋类游戏），它不考虑权重，保证了路径的最小步数。BFS 简单易实现，但可能在状态空间较大的游戏中效率低下。 # 4. 深度优先搜索（DFS）(None，1986) DFS 是一种深度优先的搜索算法，适用于状态空间很大但希望尽快找到可接受解的情况。在机器博弈中，DFS 可以用于不需要保证最短路径的复杂决策树，适用于探索策略空间深度。 # 5. 动态规划 动态规划通过存储和重用子问题的解来提高计算效率，适用于那些可以从子问题递推到整体问题的博弈。例如，象棋或围棋这类游戏中，动态规划可以帮助规划中期策略，优化多步决策。 路径寻迹算法在机器博弈中扮演着至关重要的角色，它们帮助AI在复杂的游戏环境中做出最优决策。不同的算法适用于不同类型 的游戏和优化目标, 选择合适的路径寻迹算法可以显著提高机器博弈的性能和用户体验。 # 4.11 神经网络 人工神经网络（Artificial Neural Network，即ANN），简称为神经网络或类神经网络。它是一种运算模型，由大量的节点（或称神经元）之间相互联接构成。每个节点代表一种特定的输出——激励函数（Activation function）。每两个节点间的连接都代表一个对于通过该连接信号的加权值，这相当于人工神经网络的记忆。网络的输出则依网络的连接方式，依权值和激励函数的不同而不同。而网络自身通常都是对自然界某种算法或者函数的逼近，也可能是对一种逻辑策略的表达。 人工神经网络研究以多伦多大学的Geoffrey Hinton(G. Hinton, 2000; Geoffrey Hinton, Deng, Yu, Dahl, & Kingsbury, 2012; G. E. Hinton, 2011; G. E. Hinton et al., 2006; Lecun, Bengio, & Hinton, 2015; Salakhutdinov & Ruslan, 2012)为代表，目前已有前馈神经感知网络（Feed forward neural networks, FF or FFNN）、径向神经网络（Radial basis function, RBF）、霍普菲尔网络（Hopfield networks, HN）、深度信念网络（Deep belief networks, DBN）、卷积神经网络（Convolutional neural networks, CNN）、深层玻尔兹曼机（Deep Boltzmann Machine, DBM）、堆叠自动编码器（Stacked Auto-Encoder, SAE）等数十种模型。 人工神经网络在机器博弈中扮演着至关重要的角色, 通过结合深 度强化学习（如AlphaGo和AlphaZero）、策略网络、价值网络和卷积神经网络（CNN），系统能够有效地学习游戏策略和状态评估。策略网络直接输出行动概率，而价值网络估计局面胜率，共同指导蒙特卡洛树搜索（MCTS）。自我对弈机制生成大量训练数据，使模型持续进化。多智能体系统中的协同学习进一步提升了策略优化。这些技术的综合应用使现代AI在复杂博弈中达到了超越人类的水平。 近年来，人工神经网络的研究取得了很大的进展，尤其是实现了以超算为目标的并行算法的运行与概念证明后，在机器博弈、计算机视觉、模式识别等人工智能领域与深度学习相结合(Schmidhuber, 2015)，成功地解决了许多现代计算机难以解决的实际问题（例如围棋、中国象棋博弈中的估值、学习与训练等），表现出了良好的智能特性(David Silver et al., 2016；吕艳辉 & 宫瑞敏，2012；苏攀，王熙照，& 李艳，2011)。 # 4.12 机器学习 机器学习（Machine Learning）的根本任务是数据的智能分析与建模，正成为发展新学科的基础(Meltzoff，Kuhl，Movellan，& Sejnowski，2009)。它利用经验来改善计算机系统自身性能(Mitchell, 2003)，让计算机系统具有人类的学习能力，以便实现人工智能(R.S., S., Ivan, & Miroslav, 2004)。 与传统为解决特定任务、硬编码的软件程序不同，机器学习是用大量数据进行训练，使用各种算法来解析数据并从中学习，做出决策和预测。当前主流机器学习技术包括度量学习、多核学习、多视图学 习、集成学习、主动学习、强化学习、迁移学习、统计关系学习、演化学习、并行机器学习、哈希学习等，其中强化学习（Reinforcement Learning，也称为增强学习）被列为机器学习的四大研究方向之一(Dietterich, 1997)。 强化学习研究学习器在与环境的交互过程中，如何学习到一种行为策略，以得到累积利益最大化(Sutton & Barto, 1998)。在机器博弈中，强化学习的设定可用图4-2来表示，学习器所处的环境为博弈规则，学习器根据当前博弈状态输出着法，以博弈收益作为每步着法的结果，反馈给学习器，以期望最终的利益最大化。 图4-2 机器博弈强化学习设定 在实际应用中，由于强化学习的优化目标通常涉及多步决策，相对复杂，且策略的搜索空间巨大，优化比较困难。另外，强化学习还面临着特征表示、泛化能力等诸多挑战。 深度学习是基于多层网络结构的特征学习方法，把原始数据通过多层神经网络非线性变换，逐层提取抽象特征，完成复杂的目标函数系统逼近。深度学习典型的网络模型包括卷积神经网络、深层玻尔兹曼机和堆叠自动编码器等。利用GPU或TPU来训练深度神经网络，充 分发挥其并行计算能力，大幅缩短海量数据训练所耗费的时间，因此GPU或TPU并行计算已经成为业界在深度学习模型训练方面的首选解决方案。 相对于传统的机器学习方法，深度学习能够学习多层次抽象的数据表示，能够发现大数据中的复杂结构，对于解决强化学习中策略评估和优化的问题有明显优势。深度学习被成功地用于机器博弈中（郭潇逍，李程，&梅俏竹，2016)，例如采用基于深度学习和Q-Learning的Deep Q-Network(Volodymyr，Koray，David，&al，2015)技术的博弈系统已达到人类玩家水平，而AlphaGo(Schölkopf & Platt，2007;David Silver et al., 2016)则可以战胜人类顶级高手。 尽管深度学习技术在围棋机器博弈方面取得了前所未有的成功，但在拓展应用方面仍面临一些问题，例如深度学习训练耗时、非凸函数模型在理论研究中存在困难等。如何合理利用深度学习方法增强传统学习算法的性能，提升机器博弈水平，仍是今后研究的重点。 # 4.13 深度学习 深度学习作为机器学习的重要分支，通过深层神经网络架构模拟人脑的层次化认知机制，实现对数据中复杂模式的多层次抽象与表征(周雷，尹奇跃，&黄凯奇,2022)。与依赖手工特征的传统机器学习方法相比，深度学习具备从原始数据中自动学习高阶特征的能力(张千etal.,2019)，这一特性使其在机器博弈领域展现出显著优势。通过端到端的训练范式，深度学习与强化学习、蒙特卡洛树搜索(高锦涛，胡志远,&姜璐璐,2025)等技术的深度融合，已成为推动博弈智能体突 破性能瓶颈的核心驱动力。 在机器博弈的具体实践中，深度学习模型架构持续演进并展现出强大的适应性。卷积神经网络通过其局部连接和权值共享特性，在棋盘类游戏中有效捕捉空间拓扑关系(刘知青 & 吴修竹, 2016)，为策略评估提供结构化特征表示；循环神经网络及其长短期记忆变体，则在序列决策类博弈中展现出对历史状态依赖的建模能力(王璐瑶 & 吴蕾, 2025)。深度Q网络及其改进模型通过经验回放与目标网络稳定训练机制，在部分可观测环境中实现了超越传统方法的决策性能(刘剑锋，普杰信, & 孙力帆, 2023)。值得关注的是，Transformer架构凭借其自注意力机制，正逐渐应用于需要长程依赖建模的复杂博弈场景，为多步策略推理提供了新的技术路径(罗俊仁，张万鹏，苏炯铭，王尧, & 陈璟, 2023)。 深度学习与强化学习的融合形成了深度强化学习这一重要范式，极大地推动了机器博弈技术的发展。这一范式通过价值网络与策略网络的协同优化，使智能体能够在高维状态空间中实现有效的策略搜索。其核心进展体现在多个方面：基于模型的强化学习通过构建环境动力仿真来提升样本效率；分层强化学习将复杂任务分解为多个抽象层次，实现了策略的模块化学习；元强化学习则使智能体具备跨任务的快速适应能力(Huang et al., 2025)。自博弈机制的引入进一步加速了策略进化过程，通过持续自我对抗生成高质量训练数据，驱动智能体发现超越人类经验的纳什均衡策略。 近年来，深度学习在机器博弈中的技术演进呈现出若干重要趋 势。自监督与半监督学习方法有效缓解了对大规模标注数据的依赖，使智能体能够从有限的专家对局中提取有效知识。多模态融合技术整合视觉、文本等异构信息，为理解复杂博弈规则提供了更丰富的上下文。可解释性研究则致力于揭示深度决策模型的内在逻辑，通过注意力可视化、策略分解等方法增强智能体的透明度与可信度。大语言模型与博弈决策的交叉探索开辟了新的研究方向，其在战略推理、对手建模等方面的潜力正逐步显现。 尽管深度学习已推动机器博弈达到前所未有的水平，该领域仍面临诸多挑战。模型训练对计算资源的巨大需求限制了其普及应用，训练过程的稳定性与收敛性保证仍需进一步研究，如何在非平稳环境中维持策略的鲁棒性也是亟待解决的问题。未来，深度学习与机器博弈的融合将继续向更高效的训练算法、更通用的策略表示和更可信的决策机制方向发展，为实现通用博弈智能奠定坚实基础。 # 4.14知识库 知识库技术通过结构化的方式存储领域内的专业知识、规则和案例等信息。这些信息可以来自各种来源，如书籍、论文、专家经验等，并经过整理、分类和编码后存储于知识库中。知识库技术使得计算机能够高效地访问和利用这些知识，从而支持复杂的决策和问题求解过程。 1.知识库在机器博弈领域的应用(郭晓霞，韩燮，&赵融，2018) 在机器博弈领域，知识库技术发挥着至关重要的作用，它负责存储和检索与博弈相关的丰富知识。这些知识覆盖了棋谱和开局库，其 中包含了历史上著名棋手的对弈记录以及各种常见开局的走法和应对策略，这些信息能够帮助机器在博弈的早期阶段就取得优势或避开潜在的陷阱。此外，知识库还记录了棋型和定式，即棋盘上特定形状的棋子分布及其相应的走法和策略，使得机器能够迅速识别当前棋局的优劣，并据此做出决策。最后，知识库中还包含了博弈的基本规则、高手的走法策略和战术思路等，这些构成了机器进行博弈的基础，同时也是机器学习和优化策略的重要来源。通过整合这些知识，机器博弈系统能够更深入地理解和模拟人类棋手的思维过程，从而在博弈中展现出更高的竞技水平。 # 2.知识库技术在机器博弈中的优势 知识库技术在机器博弈中提供了显著的优势，它通过快速检索存储的信息，使得机器能够在极短的时间内做出高质量的决策，显著提升了博弈的效率。此外，机器可以利用知识库中积累的历史数据和统计信息，学习并模仿高手的走法策略和战术思路，通过不断的自我对弈和实践来优化自身的棋力。更为重要的是，知识库的内容可以根据最新的博弈理论和实践进行更新和扩展，这赋予了机器强大的适应性和灵活性，使其能够灵活应对多变的博弈场景和不同的对手，始终保持竞争力。 知识库技术在机器博弈领域发挥着重要作用，为机器提供了丰富的知识支持和决策依据。随着技术的不断发展，知识库技术将在机器博弈领域发挥越来越重要的作用。 # 4.15 微分博弈 微分博弈是指在时间连续的系统内，多个参与者进行持续的博弈，力图最优化各自独立、冲突的目标，最终获得各参与者随时间演变的策略并达到纳什均衡，即任何参与者都没有单独改变策略的意愿。微分博弈理论是求解协调控制问题的崭新思路(全秉达 et al., 2024)。 微分博弈理论起源于20世纪50年代美国空军开展的军事对抗中双方追逃问题的研究，它是最优控制与博弈论的结合。随着博弈种类的拓展和解法的完善，微分博弈已被应用于经济学、管理学、环境科学等多个领域。在机器博弈领域，微分博弈的思想也逐渐被引入，为机器博弈提供了新的思路和方法。 微分博弈为机器博弈提供了坚实的理论基础，它使得机器能够在复杂的博弈环境中做出最优决策。微分博弈理论中的纳什均衡等概念，为机器博弈中的策略优化和决策制定提供了重要的理论指导。在算法应用方面，微分博弈中的动态规划、最优控制等方法被广泛应用于求解机器博弈中的最优策略。同时，微分博弈的连续时间模型和离散时间模型为机器博弈中的时间演化和策略更新提供了重要的参考。 尽管微分博弈在机器博弈中的应用还处于探索阶段，但它带来了新的挑战和机遇。微分博弈的复杂性和连续性要求机器具备更高的计算能力和智能水平，这对机器的硬件和软件都提出了更高的要求。同时，微分博弈也为机器博弈提供了新的研究方向和思路，有助于推动机器博弈领域的发展，特别是在追逃问题、兵棋推演智能化等方面展 现出巨大的潜力。因此，微分博弈不仅为机器博弈提供了理论支撑和算法应用，还带来了新的挑战和机遇，促进了人工智能技术的进步和应用的拓展。 随着人工智能技术的持续进步，机器博弈领域也迎来了显著的发展，其中微分博弈作为一种创新的思路和方法，展现出广阔的应用前景。未来，微分博弈有望在提升机器博弈的智能水平方面发挥关键作用，通过其思想和方法的引入，增强机器在面对复杂局面和对手策略时的决策能力，从而做出更优的决策。此外，微分博弈的应用范围有望进一步拓展，覆盖电子竞技、棋类博弈、策略游戏等多种类型的机器博弈，从而扩大机器博弈的应用领域。同时，微分博弈的研究和应用也将推动人工智能技术的创新和发展，为人工智能领域带来新的突破和进展，预示着微分博弈在智能决策和策略优化方面的巨大潜力。 # 4.16 贝叶斯网络与概率推理 贝叶斯网络是一种概率图模型，它能够通过图形化的方式表示变量之间的依赖关系，并利用贝叶斯定理进行概率推理。在机器博弈中，贝叶斯网络可以用于建模博弈过程中的不确定性，以及预测对手的可能动作和策略。如在扑克牌博弈中，玩家需要