計算機博弈案例教程

本書主要講述電腦博弈及其實現的過程。第1章介紹電腦博弈的一些基本情況。第2章介紹極大極小算法，並以井字棋為例實現。第3章介紹Alpha-Beta算法，並以亞馬遜棋為例實現。第4章介紹期望極大極小算法，並以愛恩斯坦棋為例實現。第5章介紹UCT算法，並以海克斯棋為例實現。第6章介紹強化學習在電腦博弈游戲中的應用，並以不圍棋為例實現。第7章介紹西洋跳棋的算法，重點介紹可下位置的生成算法。第8章介紹非完備信息博弈游戲的實現方法，並以軍棋為例實現。書中的案例全部採用目前使用量較大的C++語言來描述，並在表達中盡可能使讀者易於轉換為其他語言。附錄A介紹目前中國大學生電腦博弈大賽部分項目的規則，方便需要的讀者作為參考。本書提供部分源代碼，登錄華信教育資源網（www.hxedu.com.cn）註冊後免費下載。本書適合作為中國大學生電腦博弈大賽和其他電腦博弈比賽參考用書，也可以作為應用數學、電腦科學、人工智能等專業相關課程的教材。

第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