AlphaGo 与深度学习
AlphaGo对工业界和学术界的影响是深远的,至少对于我来说,他让我直接就把研究方向从其他方面转向了深度学习。...
AlphaGo 对工业界和学术界的影响是深远的,至少对于我来说,他让我直接就把研究方向从其他方面转向了深度学习。从今年2月开始,就一直在研究 AlphaGo 的算法,并尝试自己写围棋程序,一直忙到4月份。最近已经把精力从围棋转向更实际的领域了,所以写一篇文章总结一下。
个人觉得,整个 AplphaGo 对于机器学习来说,最核心的算法就是深度学习(Deep Learning)和增强学习(Reinforcement Learning)。蒙特卡洛树搜索 MCTS 是一个搜索框架,将这些机器学习的技术融合在了一起。今天这篇文章的重点在深度学习,增强学习以后再说。
蒙特卡洛树搜索
每个博弈类的人工智能算法的基础都是一个搜索算法。比如我们上学时学习的 A-star 算法,alpha-beta 剪枝,极大极小搜索(min-max search)。蒙特卡洛树搜索也是其中一个。所有搜索算法大概的步骤都如下:
- 基于当前的状态,给出N种自己可以做出的选择
- 对于每种选择,评估一下这种选择对自己的好处
- 选择对自己好处最大的选择
- 基于当前的状态,给出N种自己可以做出的选择
- 对于每种自己可以做出的选择,做出对手可能做出的N种选择
- 这个时候,我们最多可以面临 N^2 种局面,对每种局面进行评估
- 反推出自己应该做出什么选择
但是,如果我做出A选择,对手可以做出A1选择,在这种选择下我就死了,对手就赢了。那么我肯定不能选A。这个时候,如果发现我选择B,对手的选择中,没有一种选择能让我立即就死了,那么至少B还是比A好的。这其实就是极大极小搜索的基本原理。而 Alpha-beta 剪枝是对极大极小搜索的一种优化。
当然,在上面的例子里我们只向前看了2步。但是也许看2步还是看不出局势的好坏。这个时候就要不断的扩展深度,直到能看出局势的好坏,然后再反推自己第一步怎么走。Alpha-beta 剪枝在国际象棋领域取得了很大的成功,深蓝就是基于这个算法的。但当人们把这个算法应用到围棋时就发现了一个问题:因为围棋每种状态下的选择远远大于象棋,造成在相同的算力下,围棋很难向前看太多步,但同时又很难设计出一个评价函数在搜索深度不大时,就能看清局势。
于是 MCTS 就诞生了。其实这个算法很早之前就诞生了,只是在围棋的领域里才找到了自己的出路。这个算法有如下的本质:
- 他对局势的评估,是基于自我对局进行模拟的。模拟的次数越多,估计的越准。这种评估基本能做到不需要太深的搜索,就能看清局势。
- 每次选择评估什么局势时,都是选择对当前胜率最大的节点进行评估
- 黑棋找到10个自己可能下的位置,每个位置有两个数,一个是W,一个是T
- 找出10个位置中,黑棋下了胜率最大(胜率就是W/T, 当然出于探索的需要,一般会在这里使用多臂赌博机的模型,所以选择时并不完全考虑胜率,这个以后再细说)的位置,进行模拟对局。
- 对局结束后,T = T + 1, 如果黑棋胜了,W = W + 1,同时这个节点的祖先节点中,所有黑棋对应的节点的W都会加1。
- 假设经过一段时间后,黑棋可能下的10个位置都已经评估过了。这个时候就找出胜率最高的位置,开始考虑如果黑棋下在这个位置后,白棋怎么下。假设白棋也找10个可能下的位置。
- 当我们在评估白棋的位置好不好时,也要进行模拟对局。如果白棋胜了,那么这个节点的W = W + 1,同时这个节点的祖先节点中,所有的白色节点的W都加1。
从上面的描述时,我们知道 MCTS 需要解决两个问题:
- 在每个状态下, 如果找出下一步的候选位置
- 如何评估每个状态的最终胜率。 [list=1]
- 在传统的 MCTS 里,是通过自己和自己下棋,一直下到最后确定胜负,然后下很多局可以计算出胜率。那么自己和自己下棋,也得有一个算法去给出下一步可能走在哪里。
- AlphaGo 在这里有一个创新,就是不通过自我对局,而是直接通过神经网络基于当前局面,给出最后胜率的估计。
- 如果基于当前的局面,给出下一步的可能位置
预测下一步的传统机器学习实现
假设我们有一个数据集,包含了过去几十年人类高手对局的棋谱。那么我们就有了大量关于在某个盘面下,人类是怎么走下一步的例子。在19路棋盘上,总共有361个位置,如果我们对每个盘面能建立一个特征,那么就可以转化为一个361类的分类问题。这个时候最简单的就是可以用最大熵的分类器来解决这个问题。
更进一步,出于提高效率的考虑,我们也可以把这个361类的分类问题转化为一个两类分类问题。就是对于一个盘面S和一个合法的下一步p。判断y(S, p)是1, 还是0。是1表示人会下在p这个位置,是0表示人不会下。对于两类分类问题,我们的任务就是对于盘面S和位置p,抽取相关的特征。此时,我们的围棋知识就可以派上用场了:
- 如果我下在p,是不是就能吃掉对方几个子?
- 如果我下在p,是不是能救活我方的几个子?
- 如果我下在p,是不是能让对方的几个子处于危险之中?
- 如果我下在p,是不是能让我方几个子脱离危险?
- 如果我下在p,是不是能断开对方的大龙?
- 如果我下在p,是不是能让我方的大龙连回家?
- 如果我下在p,能否破对方的眼?
- 如果我下在p,是否能做我方的眼?
- 如果我下在p,是否征子有利?
- 如果我下在p,能否让一块棋活了?
- ……
同时,在传统的机器学习中,也可以用模版法。直接抽去p这个位置的N邻域,hash出一个数做为特征。这个特征最终的权重代表在历史的对局中,当遇到这个局部时,人类会在p落子的可能性。
很不幸的是,当我们运用大量的围棋知识去设计各种特征,并加上各种邻域的模版特征之后,下一步预测的准确率只能达到30%~40%之间。这也是目前发表的paper中具有的水平。
预测下一步的 DCNN 实现
由于传统方法在这个问题上表现的很挫,因此 AlphaGo 用 DCNN(deep cnn)来解决这个问题。DCNN 之前在图片分类的问题中取得了很大的成功,给定一幅图,DCNN 可以知道这个图里是一棵树,还是一只猫,还是一艘船,还是一栋楼。由于围棋的棋盘其实可以看成一个19*19的图片,每个像素就是对应的位置的状态(是黑棋,还是白棋,还是没放棋)。因此我们可以把每个盘面表示成一个三通道的图片,对于位置p,
- 通道0 = 1 表示p放的我方的子 (这里我方代表在这个盘面下,下一步走棋的子的颜色,对方反之)
- 通道1 = 1 表示p放的对方的子
- 通道2 = 1 表示p没放子
当得到这个惊人的结果时,群众们觉得,还是加点围棋知识吧,于是有人把3通道扩展到了更多的通道,比如:
- 通道0 = 1 表示p放的是我方的棋子
- 通道1 = 1 表示p放的是对方的棋子
- 通道2 = 1 表示没有放子
- 通道3 = 1 表示p放的是我方的棋,且于p相连的棋串只有1口气
- 通道4 = 1 表示p放的是我方的棋,且于p相连的棋串有2口气
- 通道5 = 1 表示p放的是我方的棋,且于p相连的棋串有3口气
- 通道6 = 1 表示p放的是我方的棋,且于p相连的棋串大于3口气
- 通道7 = 1 表示p放的是对方的棋,且于p相连的棋串只有1口气
- 通道8 = 1 表示p放的是对方的棋,且于p相连的棋串有2口气
- 通道9 = 1 表示p放的是对方的棋,且于p相连的棋串有3口气
- 通道10 = 1 表示p放的是对方的棋,且于p相连的棋串大于3口气
- 通道11 = 1 表示p是上一步刚刚落的子
当我看到这个结果时,确实觉得 DCNN 的效果已经超出我之前的认识了,因此促使我开始全面的研究深度学习。
目前开源的围棋程序 Pachi (https://github.com/pasky/pachi) 已经支持了 DCNN 用来预测下一步,有兴趣的可以关注一下。按照我在网上的实测,配合不太多的模拟之后,棋力在业余2段到3段之间。关于这里用的网络的详细信息可以参考 http://computer-go.org/pipermail/computer-go/2015-December/008324.html
微信公众号【ResysChina】,中国最专业的个性化推荐技术社区。
关注 ResysChina
微信扫一扫关注公众号