-
Notifications
You must be signed in to change notification settings - Fork 291
/
meng-te-qia-luo-shu-sou-suo.md
144 lines (72 loc) · 10.7 KB
/
meng-te-qia-luo-shu-sou-suo.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
个人觉得，整个 AplphaGo 对于机器学习来说，最核心的算法就是深度学习（Deep Learning）和增强学习（Reinforcement Learning）。蒙特卡洛树搜索 MCTS 是一个搜索框架，将这些机器学习的技术融合在了一起。今天这篇文章的重点在深度学习，增强学习以后再说。
## **蒙特卡洛树搜索**
每个博弈类的人工智能算法的基础都是一个搜索算法。比如我们上学时学习的 A-star 算法，alpha-beta 剪枝，极大极小搜索\(min-max search\)。蒙特卡洛树搜索也是其中一个。所有搜索算法大概的步骤都如下：
1. 基于当前的状态，给出N种自己可以做出的选择
2. 对于每种选择，评估一下这种选择对自己的好处
3. 选择对自己好处最大的选择
但是这里有一个难点，就是如何评估每种选择对自己的好处，也就是如何设计出评价函数。比如说，如果我们设计出一个评价函数，结果发现在N种选择中，有M个选择得分一样，而且都是最高分，那这个时候我们怎么办？这里本质的原因是，如果基于当前的状态只看一步，其实很多时候看不出好坏。所以就要多看几步。比如
1. 基于当前的状态，给出N种自己可以做出的选择
2. 对于每种自己可以做出的选择，做出对手可能做出的N种选择
3. 这个时候，我们最多可以面临 N^2 种局面，对每种局面进行评估
4. 反推出自己应该做出什么选择
举个例子，比如给定一个评价函数Q，在当前局面下，自己有A，B两个选择，且评分一样 Q\(A\) = Q\(B\)。
但是，如果我做出A选择，对手可以做出A1选择，在这种选择下我就死了，对手就赢了。那么我肯定不能选A。这个时候，如果发现我选择B，对手的选择中，没有一种选择能让我立即就死了，那么至少B还是比A好的。这其实就是极大极小搜索的基本原理。而 Alpha-beta 剪枝是对极大极小搜索的一种优化。
当然，在上面的例子里我们只向前看了2步。但是也许看2步还是看不出局势的好坏。这个时候就要不断的扩展深度，直到能看出局势的好坏，然后再反推自己第一步怎么走。Alpha-beta 剪枝在国际象棋领域取得了很大的成功，深蓝就是基于这个算法的。但当人们把这个算法应用到围棋时就发现了一个问题：因为围棋每种状态下的选择远远大于象棋，造成在相同的算力下，围棋很难向前看太多步，但同时又很难设计出一个评价函数在搜索深度不大时，就能看清局势。
于是 MCTS 就诞生了。其实这个算法很早之前就诞生了，只是在围棋的领域里才找到了自己的出路。这个算法有如下的本质：
1. 他对局势的评估，是基于自我对局进行模拟的。模拟的次数越多，估计的越准。这种评估基本能做到不需要太深的搜索，就能看清局势。
2. 每次选择评估什么局势时，都是选择对当前胜率最大的节点进行评估
举个例子，比如棋局进行到X手时，轮到黑棋下，
1. 黑棋找到10个自己可能下的位置，每个位置有两个数，一个是W，一个是T
2. 找出10个位置中，黑棋下了胜率最大（胜率就是W/T， 当然出于探索的需要，一般会在这里使用多臂赌博机的模型，所以选择时并不完全考虑胜率，这个以后再细说\)的位置，进行模拟对局。
3. 对局结束后，T = T + 1, 如果黑棋胜了，W = W + 1，同时这个节点的祖先节点中，所有黑棋对应的节点的W都会加1。
4. 假设经过一段时间后，黑棋可能下的10个位置都已经评估过了。这个时候就找出胜率最高的位置，开始考虑如果黑棋下在这个位置后，白棋怎么下。假设白棋也找10个可能下的位置。
5. 当我们在评估白棋的位置好不好时，也要进行模拟对局。如果白棋胜了，那么这个节点的W ＝ W ＋ 1，同时这个节点的祖先节点中，所有的白色节点的W都加1。
上面这个过程其实是一种 min-max 搜索。为什么呢？我们考虑如果我们发现一个黑色节点，在之前的评估中胜率很高。但是，如果我们扩展了这个节点后，存在一个白色子节点的胜率很高（假设100%），那么我们在评估那个白色节点时，这个黑色节点的T会增加，但W不变，此时就会拉低黑色节点的胜率，直到这个节点降低到一定的程度。计算资源就不会再评估这个节点，而是去评估别的黑色节点了。
从上面的描述时，我们知道 MCTS 需要解决两个问题：
1. 在每个状态下， 如果找出下一步的候选位置
2. 如何评估每个状态的最终胜率。
3. 1. 在传统的 MCTS 里，是通过自己和自己下棋，一直下到最后确定胜负，然后下很多局可以计算出胜率。那么自己和自己下棋，也得有一个算法去给出下一步可能走在哪里。
2. AlphaGo 在这里有一个创新，就是不通过自我对局，而是直接通过神经网络基于当前局面，给出最后胜率的估计。
综合上面的讨论，下面这个问题显然是 AlphaGo 需要解决的第一个问题：
1. 如果基于当前的局面，给出下一步的可能位置
这就是 AlphaGo 的 Policy Network 做的事情。在传统的围棋程序，比如 GnuGo 中，这一步大都是通过大量的规则去确定的。这里我们不考虑这种方法，只讨论如果通过机器学习，怎么实现。
## **预测下一步的传统机器学习实现**
假设我们有一个数据集，包含了过去几十年人类高手对局的棋谱。那么我们就有了大量关于在某个盘面下，人类是怎么走下一步的例子。在19路棋盘上，总共有361个位置，如果我们对每个盘面能建立一个特征，那么就可以转化为一个361类的分类问题。这个时候最简单的就是可以用最大熵的分类器来解决这个问题。
更进一步，出于提高效率的考虑，我们也可以把这个361类的分类问题转化为一个两类分类问题。就是对于一个盘面S和一个合法的下一步p。判断y\(S, p\)是1， 还是0。是1表示人会下在p这个位置，是0表示人不会下。对于两类分类问题，我们的任务就是对于盘面S和位置p，抽取相关的特征。此时，我们的围棋知识就可以派上用场了：
1. 如果我下在p，是不是就能吃掉对方几个子？
2. 如果我下在p，是不是能救活我方的几个子？
3. 如果我下在p，是不是能让对方的几个子处于危险之中？
4. 如果我下在p，是不是能让我方几个子脱离危险？
5. 如果我下在p，是不是能断开对方的大龙？
6. 如果我下在p，是不是能让我方的大龙连回家？
7. 如果我下在p，能否破对方的眼？
8. 如果我下在p，是否能做我方的眼？
9. 如果我下在p，是否征子有利？
10. 如果我下在p，能否让一块棋活了？
11. ……
基于围棋知识，我们可以设计出很多特征。
同时，在传统的机器学习中，也可以用模版法。直接抽去p这个位置的N邻域，hash出一个数做为特征。这个特征最终的权重代表在历史的对局中，当遇到这个局部时，人类会在p落子的可能性。
很不幸的是，当我们运用大量的围棋知识去设计各种特征，并加上各种邻域的模版特征之后，下一步预测的准确率只能达到30%~40%之间。这也是目前发表的paper中具有的水平。
## **预测下一步的 DCNN 实现**
由于传统方法在这个问题上表现的很挫，因此 AlphaGo 用 DCNN（deep cnn）来解决这个问题。DCNN 之前在图片分类的问题中取得了很大的成功，给定一幅图，DCNN 可以知道这个图里是一棵树，还是一只猫，还是一艘船，还是一栋楼。由于围棋的棋盘其实可以看成一个19\*19的图片，每个像素就是对应的位置的状态（是黑棋，还是白棋，还是没放棋）。因此我们可以把每个盘面表示成一个三通道的图片，对于位置p，
1. 通道0 ＝ 1 表示p放的我方的子 （这里我方代表在这个盘面下，下一步走棋的子的颜色，对方反之）
2. 通道1 ＝ 1 表示p放的对方的子
3. 通道2 ＝ 1 表示p没放子
然后这个图片的类别就是下一步可能的位置，一共有361种可能性，因此就是一个361类的分类问题。然后用 DCNN 训练一下，结果发现预测下一步的准确率可以达到44%。这是很令人惊奇的，因为整个过程中我们没有利用到任何围棋知识，也没有提前任何特征。DCNN 就自动学习出44%的精度了。
当得到这个惊人的结果时，群众们觉得，还是加点围棋知识吧，于是有人把3通道扩展到了更多的通道，比如：
1. 通道0 ＝ 1 表示p放的是我方的棋子
2. 通道1 ＝ 1 表示p放的是对方的棋子
3. 通道2 ＝ 1 表示没有放子
4. 通道3 ＝ 1 表示p放的是我方的棋，且于p相连的棋串只有1口气
5. 通道4 ＝ 1 表示p放的是我方的棋，且于p相连的棋串有2口气
6. 通道5 ＝ 1 表示p放的是我方的棋，且于p相连的棋串有3口气
7. 通道6 ＝ 1 表示p放的是我方的棋，且于p相连的棋串大于3口气
8. 通道7 ＝ 1 表示p放的是对方的棋，且于p相连的棋串只有1口气
9. 通道8 ＝ 1 表示p放的是对方的棋，且于p相连的棋串有2口气
10. 通道9 ＝ 1 表示p放的是对方的棋，且于p相连的棋串有3口气
11. 通道10 ＝ 1 表示p放的是对方的棋，且于p相连的棋串大于3口气
12. 通道11 ＝ 1 表示p是上一步刚刚落的子
可以看到，这里只利用到了2个围棋知识，一个是棋串，一个是气。另外还利用到了上一步的信息。然后用 DCNN 训练一下，会发现下一步的预测准确率能达到53%左右了。在 AlphaGo 里，还利用到了更多的围棋知识，它们一共使用了48个通道（也就是每个点提取了48个特征），然后就可以达到57%的准确率了。
当我看到这个结果时，确实觉得 DCNN 的效果已经超出我之前的认识了，因此促使我开始全面的研究深度学习。
目前开源的围棋程序 Pachi \([GitHub - pasky/pachi: A fairly strong Go/Baduk/Weiqi playing program](http://link.zhihu.com/?target=https%3A//github.com/pasky/pachi)\) 已经支持了 DCNN 用来预测下一步，有兴趣的可以关注一下。按照我在网上的实测，配合不太多的模拟之后，棋力在业余2段到3段之间。关于这里用的网络的详细信息可以参考[\[Computer-go\] CNN with 54% prediction on KGS 6d+ data](http://link.zhihu.com/?target=http%3A//computer-go.org/pipermail/computer-go/2015-December/008324.html)