計算機博弈案例教程

第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