本书主要讲述计算机博弈及其实现的过程。第1章介绍计算机博弈的一些基本情况。第2章介绍极大极小算法，并以井字棋为例实现。第3章介绍Alpha-Beta算法，并以亚马逊棋为例实现。第4章介绍期望极大极小算法，并以爱恩斯坦棋为例实现。第5章介绍UCT算法，并以海克斯棋为例实现。第6章介绍强化学习在计算机博弈游戏中的应用，并以不围棋为例实现。第7章介绍西洋跳棋的算法，重点介绍可下位置的生成算法。第8章介绍非完备信息博弈游戏的实现方法，并以军棋为例实现。书中的案例全部采用目前使用量较大的C++语言来描述，并在表达中尽可能使读者易于转换为其他语言。附录A介绍目前中国大学生计算机博弈大赛部分项目的规则，方便需要的读者作为参考。本书提供部分源代码，登录华信教育资源网（www.hxedu.com.cn）注册后免费下载。本书适合作为中国大学生计算机博弈大赛和其他计算机博弈比赛参考用书，也可以作为应用数学、计算机科学、人工智能等专业相关课程的教材。

前 言 编写本书的目的 本书讨论计算机博弈程序(软件)的分析、设计和实现方法与过程。编写本书的目的是对计算机博弈竞赛的一些项目进行分析、实现，并引导学生独立完成相关程序的设计，为有兴趣参与计算机博弈程序设计的读者提供参考。 预备知识要求 本书主要讲述计算机博弈程序的实现过程，读者需有基本的计算机语言知识，并能够编写简单的应用程序。对所学的语言并无特定的要求，例如，C、C++或Java等均可作为具体实现的语言。本书中关于搜索和估值方面的内容均有相关的代码，并且在表达上力求使读者易于将相关代码转换为自己所熟悉的语言，同时从简单的示例开始讲解，逐步加深，便于学习。 学习方法 对于学生来说，重要的是如何学会自己动手完成相关代码的编写，而不是从书上或网上照抄代码。本书在撰写过程中以分析、设计为主，以代码实现为辅，通过对代码的分析，从算法的原理出发，将结构、流程、伪码相结合，引导学生独立完成相关代码的编写。同时，本书注重算法的效率，对效率从理论到实践进行讲解。 本书使用软件工程的方法分析、设计相关程序，使读者能从全局观念出发来设计程序，在实践中体会从全局出发、以工程方法设计程序的重要性。 各章内容 第1章介绍计算机博弈的一些基本情况。第2章介绍极大极小算法，并以井字棋为例实现。第3章介绍Alpha-Beta算法，并以亚马逊棋为例实现。第4章介绍期望极大极小算法，并以爱恩斯坦棋为例实现。第5章介绍UCT算法，并以海克斯棋为例实现。第6章介绍强化学习在计算机博弈游戏中的应用，并以不围棋为例实现。第7章介绍西洋跳棋的算法，重点介绍可下位置的生成算法。第8章介绍非完备信息博弈游戏的实现方法，并以军棋为例实现。书中的案例全部采用目前使用量较大的C++语言来描述，并在表达中尽可能使读者易于转换为其他语言。附录A介绍目前中国大学生计算机博弈大赛部分项目的规则，方便需要的读者作为参考。本书提供部分源代码，登录华信教育资源网（www.hxedu.com.cn）注册后免费下载。 本书适合作为中国大学生计算机博弈大赛和其他计算机博弈比赛参考用书，也可以作为应用数学、计算机科学、人工智能等专业相关课程的教材。 致谢 本书在撰写过程中得到了很多人的支持和帮助，沈阳工业大学曲绍波编写了本书第8章军棋部分的相关内容，李媛、王博和刘颖承担了算法设计、校对等工作，为本书所涉及的内容提供了具体的实现，使得本书更加完善。感谢张家铭为书中西洋跳棋程序的实现提供了基础软件，同时感谢参与试读的学生，他们在学习期间抽出宝贵的时间来阅读本书，给出了很多宝贵的意见，对提升本书的易读性、易用性有很大帮助。 无论作者有多少发现错误的技巧，总会有一些错误漏网，而读者往往最能发现错误。如果读者发现任何错误，敬请提出纠正建议，不胜感激。作者邮箱：wangjingwen007@126.com。 王静文

第1章 概述 1 1.1 人工智能简介 1 1.2 计算机博弈 1 1.3 计算机博弈竞赛 2 第2章 井字棋 3 2.1 井字棋简介 3 2.2 博弈树和极大极小算法 3 2.2.1 博弈树 3 2.2.2 极大极小算法 4 2.3 负极大极小算法 6 2.4 井字棋的估值函数 6 2.5 井字棋的实现 7 2.5.1 基本结构 8 2.5.2 人人对战 8 2.5.3 机机对战 14 2.5.4 人机对战 18 2.5.5 负极大极小算法的实现 20 2.6 程序测试 21 第3章 亚马逊棋 23 3.1 亚马逊棋简介 23 3.2 Alpha-Beta算法 24 3.3 亚马逊棋的走法生成 27 3.4 亚马逊棋的局面评估 28 3.5 亚马逊棋的实现 29 3.5.1 基本结构 29 3.5.2 人人对战 30 3.5.3 人机对战与机人对战 36 3.5.4 其他算法 50 第4章 爱恩斯坦棋 53 4.1 爱恩斯坦棋简介 53 4.2 期望极大极小算法 53 4.3 爱恩斯坦棋的估值 54 4.4 爱恩斯坦棋的实现 56 4.4.1 基本结构 56 4.4.2 人人对战 57 4.4.3 人机对战与机人对战 63 4.4.4 其他算法 77 第5章 海克斯棋 78 5.1 海克斯棋简介 78 5.2 算法 79 5.2.1 蒙特卡洛方法 79 5.2.2 蒙特卡洛树搜索 80 5.2.3 UCT算法 82 5.3 海克斯棋的实现 82 5.3.1 基本结构 82 5.3.2 基本功能的实现 86 5.3.3 PMC算法的实现 94 5.3.4 UCT算法的实现 98 5.4 算法改进 105 第6章 不围棋 107 6.1 不围棋简介 107 6.2 强化学习 107 6.2.1 强化学习简介 107 6.2.2 Q学习算法 108 6.3 使用置换表表示棋盘状态 110 6.4 不围棋的实现 112 6.4.1 基本结构 112 6.4.2 MC算法的实现 114 6.4.3 Q学习算法的实现 128 第7章 西洋跳棋 136 7.1 西洋跳棋简介 136 7.2 西洋跳棋的实现 138 7.2.1 基本结构 138 7.2.2 基本功能的实现 140 7.2.3 走法生成 143 7.2.4 估值函数 162 7.2.5 搜索算法的实现 165 第8章 军棋 176 8.1 军棋简介 176 8.1.1 游戏规则 176 8.1.2 游戏特点 177 8.2 搜索算法 178 8.3 非完备信息局面的抽样 178 8.3.1 概率表 178 8.3.2 概率更新 180 8.3.3 局面抽样 183 8.4 走法生成 186 8.4.1 公路走法生成 186 8.4.2 铁路走法生成 188 8.4.3 工兵走法生成 190 8.5 MCTS算法的实现 193 8.5.1 节点设计 193 8.5.2 选择与扩展 197 8.5.3 模拟 199 8.5.4 反向传播 201 8.5.5 删除树 201 8.5.6 MCTS算法主函数 202 8.6 军棋博弈平台接口 204 8.7 程序优化分析 209 附录A 中国大学生计算机博弈大赛部分项目的规则 210 A.1 苏拉卡尔塔棋规则 210 A.2 六子棋规则 210 A.3 五子棋规则 211 A.4 幻影围棋规则 213 A.5 点格棋规则 214 参考资料 216