计算机博弈案例教程

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

第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