第1部分 导论 3
第1章 计算机博弈概述 3
1.1计算机博弈的概念 3
1.1.1计算机博弈的主要特征 3
1.1.2计算机博弈的相关领域 4
1.2计算机博弈的意义 5
1.3计算机博弈的发展历史 7
第2章 计算机博弈的理论与方法 9
2.1博弈树模型 9
2.2博弈的复杂度与可解性 12
2.2.1博弈的复杂度 12
2.2.2博弈的可解性 13
2.3博弈的盘面评估 14
2.3.1子力 14
2.3.2位置 15
2.3.3空间 15
2.3.4机动 15
2.3.5拍节 15
2.3.6威胁 16
2.3.7形状 16
2.3.8局面评估值 16
2.3.9局面评估的准确性与性能 16
2.4极小极大搜索算法 17
2.5负极大搜索 19
2.6a-β搜索 19
2.7负侦查搜索 22
2.8静止搜索 23
2.8.1地平线问题 23
2.8.2静止搜索算法 24
2.8.3静止节点 25
2.9置换表 26
第3章 围棋的基本知识 28
3.1围棋的基本规则 28
3.1.1棋盘和棋子 29
3.1.2下法 29
3.1.3棋串和气 30
3.1.4提子 30
3.1.5可着子点与禁着子点 31
3.1.6终局 31
3.1.7死棋与活棋 31
3.1.8胜负计算与贴子 31
3.2围棋的基本概念 32
3.2.1紧气与长气 32
3.2.2劫 33
3.2.3眼 33
3.2.4活棋与双活 36
3.2.5目与单官 37
第4章 围棋的起源及发展 38
4.1围棋的起源 38
4.2围棋博弈规则的发展 42
4.2.1自然终局法 43
4.2.2唐宋数路法 43
4.2.3明清数子法 46
4.2.4现代数目法 47
4.2.5现代数子法 48
4.2.6座子制、贴目制与贴子制 49
4.2.7计算机围棋规则 50
第5章 计算机围棋概述 52
5.1计算机围棋的意义 52
5.2围棋的复杂度 53
5.2.1围棋的状态空间复杂度 53
5.2.2围棋的博弈树复杂度 54
5.2.3复杂度比较 55
5.3计算机围棋的主要特点 55
5.3.1目标的总体效应 56
5.3.2巨大的搜索空间 56
5.3.3复杂的盘面评估 56
5.3.4紧密相连的盘面评估与博弈树搜索 57
5.4计算机围棋的主要困难 57
5.4.1搜索无法终结 57
5.4.2选点无法验证 57
5.5计算机围棋的发展历史 58
5.5.1传统计算机围棋时代 58
5.5.2现代计算机围棋时代 58
5.5.3计算机围棋赛事 59
第2部分 模型 63
第6章 专家系统局势评估 63
6.1领域知识和分块组合 63
6.1.1领域知识的作用 63
6.1.2分块组合 64
6.2评估函数的实现 65
6.2.1连接问题 65
6.2.2眼的问题 66
6.2.3边缘问题 66
6.2.4分块组合 67
6.2.5二次评估 68
6.3影响函数 68
6.3.1影响函数的算法 68
6.3.2局面评估 71
第7章 蒙特卡洛局势评估 72
7.1蒙特卡洛方法 72
7.1.1发展历史 72
7.1.2基本思想 74
7.1.3随机数 75
7.2数学期望结果模型 76
7.2.1蒙特卡洛对弈 76
7.2.2与静态评估的比较 77
7.3在线机器学习 78
第8章 多臂匪徒模型 80
8.1多臂匪徒问题 80
8.2多臂匪徒问题的数学模型 82
8.2.1数学模型 82
8.2.2后悔度 82
8.2.3求解方法 83
8.2.4一贪婪策略 84
8.3 UCB策略 85
8.3.1 UCB1算法 85
8.3.2 UCB2算法 87
第9章 围棋落子搜索的数学模型 88
9.1马尔科夫决策过程概念 88
9.1.1决策时刻与周期 89
9.1.2状态与行动集 90
9.1.3转移概率和报酬 90
9.1.4历史、决策规则与策略 91
9.2围棋落子搜索的数学模型 92
9.3蒙特卡罗规划 93
9.3.1围棋落子搜索问题 95
9.3.2 UCT算法 96
第10章 蒙特卡罗搜索树 98
10.1蒙特卡罗搜索树基本思想 98
10.2逐渐扩展的策略 99
10.3在UCT算法中进行剪枝的策略 101
10.3.1绝对剪枝条件 101
10.3.2相对剪枝条件 102
10.3.3地域剪枝条件 102
第3部分 模式 107
第11章 上下文模式 107
11.1上下文模式的介绍 107
11.1.1什么是模式 107
11.1.2围棋中的上下文模式 108
11.1.3模式的种类 109
11.1.4围棋中上下文模式的价值 110
11.1.5模式具有的相关属性 112
11.2模式的对称关系 113
11.3模式的表示 114
11.3.1模式表示的重要性 114
11.3.2模式的表示方式 115
11.4模式的编码 116
11.5 Zobrist哈希 116
第12章 模式的处理 119
12.1模式的获取 119
12.2模式频率的计算 121
12.3模式频率的属性 122
第13章 评分系统 124
13.1相关介绍 124
13.2双人对弈模型 125
13.3 Elo评分系统 126
13.4 Elo评分系统在围棋中的应用 127
第14章 模式的搭配 131
14.1什么是模式的搭配 131
14.2模式搭配关系的获取 132
14.3模式搭配关系的属性 135
第4部分 程序 139
第15章 计算机围棋博弈程序的组成结构 139
15.1程序语言的选择 139
15.2基本数据结构 140
15.2.1模板 140
15.2.2类型定义 141
15.3程序的主体框架 144
15.4棋盘模块 146
15.4.1棋盘模块的构成 146
15.4.2棋盘模块的设计 148
15.5对弈引擎 149
15.5.1对弈引擎的设计 149
15.5.2对弈引擎的实现 150
15.6评估器和生成器 152
15.6.1评估器 152
15.6.2生成器 154
第16章 程序中的盘面表示 158
16.1棋盘数据结构和主要方法 158
16.2博弈树节点的表示 162
第17章 程序中的搜索方法 164
17.1搜索节点的静态排序 164
17.1.1节点的静态排序 164
17.1.2生成器 165
17.2搜索节点的逐渐展开 168
17.3基于UCT算法的最优搜索 168
第18章 程序中的盘面评估 171
18.1蒙特卡洛盘面评估 171
18.2蒙特卡洛模拟中围棋知识的应用 173
第19章 程序中的高性能计算 176
19.1高性能计算的必要性 176
19.1.1并行处理的介绍 177
19.1.2围棋程序的并行化处理 177
19.2基于共享内存的多核并行计算 177
19.3基于独立内存的分布式计算 179
第20章 程序之间的通信 181
20.1 SGF格式 181
20.2 GTP协议 182
20.3 CGOS服务器 184
后记 185
参考文献 189