计算机博弈案例教程

第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