个人觉得,整个 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. 如何评估每个状态的最终胜率。

    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) 已经支持了 DCNN 用来预测下一步,有兴趣的可以关注一下。按照我在网上的实测,配合不太多的模拟之后,棋力在业余2段到3段之间。关于这里用的网络的详细信息可以参考[Computer-go] CNN with 54% prediction on KGS 6d+ data

results matching ""

    No results matching ""