现代计算机围棋基础PDF电子书下载

第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