机器博弈入门——以五子棋 AI 设计为例(一)

in 编程技术 with 0 comment

写在前面

  1. 本文很大程度上参考了 lihongxun945gobang,在此表示深切感谢。
  2. 感谢我的好基友 YLT 大佬帮忙解惑。
  3. 我在 GitHub 放了一个符合本文所述算法的 Python demo:pbrain-jellyfish

我能学习到什么知识?

你能掌握棋类 AI 设计的基础知识,虽然是以五子棋为例,但是目前除了围棋之外的所有棋类几乎都可以用这个算法来实现,比如常见的象棋、黑白棋、跳棋等。

这里用的算法都是非常标准的,非常国际化的算法,是经过了几十年的发展,由很多大神发明的算法。所以不用担心学到了“奇怪的,野生的”算法,你学到的都是可以让你受益终身的知识,不仅是AI,甚至不仅是博弈。

这是基于传统搜索算法实现的AI教程,并不会详细的讲解神经网络的实现。不过如果你想学习神经网络的AI设计,我强烈建议你依然要完整的弄懂传统的搜索实现。因为目前包括AlphaGO在内的AI使用的是搜索+神经网络的结合技术。

什么是博弈?在《人工智能——一种现代方法》一书中的第五章《对抗搜索》中,介绍了博弈论专家们对博弈的一种定义:

有完备信息的,确定性的,轮流行动的,两个游戏者的零和游戏。

计算机博弈的艰苦历程

早在计算机诞生的前夜,著名的数学家和计算机学家阿伦·图灵(Alan Turing)便设计了一个能够下国际象棋的计算机程序,并经过一步步的人为推演,实现了第一个国际象棋的人机博弈。那些世界上最著名的科学家,如计算机创始人冯·诺依曼(John von Neumann),信息论创始人科劳德·香浓(Claude E. Shannon),人工智能的创始人麦卡锡(John McCarthy)等人都曾涉足计算机博弈领域,并做出过非常重要的贡献。应该看到,从上世纪40年代计算机诞生,计算机博弈经过一代又一代学者的艰苦奋斗和坎坷历程。早在 1958 年,IBM推出的取名“思考”的 IBM704 就成为了第一台与人类进行国际象棋对抗的计算机,当时它一秒钟可以进行 200 步的运算,但是在人类棋手面前被打得丢盔卸甲。而许多科学家却对此欢欣鼓舞,诺贝尔经济学奖和杰出科学贡献奖的获得者赫伯特·西蒙教授,早在 1957 年就预测说:“计算机在10年内将成为世界的国际象棋冠军!”。10 年过去,不要说战胜世界冠军,就连与最“臭”的专业象棋选手对阵,电脑也都战战兢兢。60 年代中期,科学家德里夫斯断言,计算机将无法击败一位年仅 10 岁的棋手。为了给电脑棋手打气,麻省理工学院的教授弗雷德金甚至不惜重金悬赏,设立 10 万美金的“弗雷德金奖”,声明这笔巨款将奖给第一个战胜世界国际象棋冠军的电脑程序设计者。1973 年,国际象棋软件 4.0 被开发出来,这是未来程序的基础。1979 年,国际象棋软件 4.9 达到专家级水平。1981 年,CRAYBLITZ 新的超级计算机拥有特殊的集成电路,预言将可在 1995 年击败世界棋王。1983 年,BELLEAT&T 开发了国际象棋硬件,达到了大师水平。80 年代中期,皮兹堡的 CARNEGIEMELLON 大学开始研究世界级的国际象棋计算机程序。1987 年,“深思”首次以每秒钟 75 万步的思考速度露面,它的水平相当于拥有国际等级分为 2450 的棋手。1988 年,“深思”击败丹麦特级大师拉尔森。1989 年,“深思”已经有 6 台信息处理器,每秒思考速度达 200 万步,但在与世界棋王卡斯帕罗夫进行的“人机大战”中对阵以 0 比 2 败北。1990 年,“深思”第二代产生,使用 IBM 的硬件,吸引了前世界棋王卡尔波夫与之对抗。1991 年,“弗里茨”问世。1993 年,“深思”二代击败了丹麦国家队,在与世界优秀女棋手小波尔加的对抗中获胜。1995 年,“深蓝”更新程序,新的集成电路将其思考速度达到每秒 300 万步。1996 年,“深蓝”在与卡斯帕罗夫的挑战赛中,以 2 比 4 不敌卡斯帕罗夫。

从计算机问世后,博弈算法从来就没有停止过改进的步伐。最早打败人类顶级棋手的AI就是深蓝。

以下内容摘自百度百科:

深蓝是美国 IBM 公司生产的一台超级国际象棋电脑,重 1270 公斤,有 32 个大脑(微处理器),每秒钟可以计算 2 亿步。"深蓝”输入了一百多年来优秀棋手的对局两百多万局。1997 年 6 月,深蓝在世界超级电脑中排名第 259 位,计算能力为每秒 113.8 亿次浮点运算。1997 年的深蓝可搜寻及估计随后的 12 步棋,而一名人类象棋好手大约可估计随后的 10 步棋。每增加 1 步棋的搜寻能力约等于增加下棋强度约 80 ELO 分。

1997 年深蓝以一分总比分优势战胜当时的国际象棋之王——卡斯帕罗夫,这是电脑第一次在棋类中战胜顶尖人类选手,让世人见证了人工智能的威力。在这以后,计算机逐渐统治了除围棋意外的大部分棋类游戏。

可以看到,深蓝其实并不是一个很厉害的 AI,因为它只搜索了 12 层,现在有名的「象棋旋风」等软件都可以超过这个搜索深度。深蓝的基本原理和本文介绍的方法类似,不过由于深蓝的运算速度远高于我们现在的个人电脑,并且他可以进行大量的并行运算,所以能达到比较高的棋力。可以认为深蓝作为一个早期的 AI,靠的是堆硬件来提升棋力。

中国的计算机博弈

正当世界的目光开始将计算机博弈的方向聚焦在中国象棋、日本将棋和围棋博弈系统的研究与开发的时候,在中国的计算机博弈却成为了“被爱情遗忘的角落”。寥寥无几的参与者,匮乏的参考文献,沉寂的计算机博弈氛围,使得中国象棋的计算机博弈在中国大陆难有作为。其中很重要的原因则是缺少计算机博弈方面得宣传和基础知识的普及,甚至难以找到论述计算机博弈原理与方法学的书籍与资料。

计算机博弈——对于人类智能的挑战

国内曾有人提出,国际象棋计算机程序已经可以战胜世界棋王卡斯帕罗夫,还有没有必要开展中国象棋计算机博弈方面的研究工作?上面已经介绍了国际上的计算机博弈方兴未艾,况且中国象棋的计算机博弈难度决不在国际象棋之下。目前中国象棋、日本将棋和围棋已经成为计算机博弈领域新的挑战。表1给出这三种棋类与国际象棋复杂度的对比。表中的数字为复杂度的自然对数值。显然,这更是对中国学者提出的严峻挑战

可以看到,哪怕是最简单的黑白棋,其状态空间的复杂度也是一个天文数字,而围棋的复杂度远远高于前面的几种棋类。我们把这个复杂度叫做空间复杂度,由于围棋的复杂度太高,因此很难在较短的步骤内评估出合适的走法,而且也很难搜索到较深的深度。更直观点说,围棋的难点在于两部分:

  1. 围棋本身的局面评估很复杂,不像象棋一样可以简单的给每个子打一个分。围棋更注重“局势”,非常难用常规手段打分。由于连评分都不准,因此搜索的基础都不可靠
  2. 围棋很难达到较深的深度。围棋每一步的可能性非常多,平均一步需要考虑 100+ 种可能,因此很难达到较深的搜索深度。

AlphaGO 通过两个神经网络,分别解决了这两个问题。

  1. 价值网络可以比较准确的进行局势的评分
  2. 策略网络可以让产生更少的分支,预测更合理的着法

什么是卷积神经网络?

AlphaGO 开启了卷积神经网络在围棋中应用的先例,后来所有的围棋 AI 都向这个方向前进,围棋 AI 们的棋力有了质的飞越。那么什么是卷积神经网络呢?

卷积神经网络是神经网络模型中的一种,本来是用来提取图片特征,进行图像识别的。卷积是一种矩阵运算,通过不同的卷积核,可以提取图片的不同特征。通过神经网络自动学习,就可以学到图像的特征从而学会识别图片。很凑巧地,棋盘不就是一个小图片吗?比如围棋就是一个 19x19 的图片,并且每一个像素只有三种值。对这个图片进行图像识别并评分,就变得是很自然的事情。

棋类介绍与分类

由于棋类游戏为广大群众所喜爱,种类与玩法十分丰富。有些在国际上广为流行,也有些是仅限于地区的民间棋类。而且总会有新的棋类,新的玩法在推出。因此在研究普遍的博弈原理之前有必要对于棋类的属性和分类进行介绍。

按参与人数分类(Player)

按兵种多少分类(Pieces, Materials)

按着法分类(Move)

按胜负判决分类(Win-Lose-Draw)

AI 实现的基本思路——极大极小值搜索算法(Minimax Algorithm)

五子棋看起来有各种各样的走法,而实际上把每一步的走法展开,就是一颗巨大的博弈树(Game Tree)。在这个树中,从根节点为 0 开始,奇数层表示电脑可能的走法,偶数层表示玩家可能的走法。

假设电脑先手,那么第一层就是电脑的所有可能的走法,第二层就是玩家的所有可能走法,以此类推。

我们假设平均每一步有 50 种可能的走法,那么从根节点开始,往下面每一层的节点数量是上一层的 50 倍,假设我们进行 4 层思考,也就是电脑和玩家各走两步,那么这颗博弈树的最后一层的节点数为 50^4=625W 个。

先不考虑这么多个节点需要多久能算出来。有了对博弈树的基本认识,我们就可以用递归来遍历这一棵树。

那么我们如何才能知道哪一个分支的走法是最优的,我们就需要一个评估函数能对当前整个局势作出评估,返回一个分数。我们规定对电脑越有利,分数越大,对玩家越有利,分数越小,分数的起点是 0。

我们遍历这颗博弈树的时候就很明显知道该如何选择分支了:

这也就是极大极小值搜索算法的名称由来。这是维基百科上的一张图:

此图中甲是电脑,乙是玩家,那么在甲层的时候,总是选其中值最大的节点,乙层的时候,总是选其中最小的节点。

而每一个节点的分数,都是由子节点决定的,因此我们对博弈树只能进行深度优先搜索而无法进行广度优先搜索。深度优先搜索用递归非常容易实现,然后主要工作其实是完成一个评估函数,这个函数需要对当前局势给出一个比较准确的评分。

五子棋是一个 15x15 的棋盘,因为棋盘大小不会变动,所以目前来看用 15x15 的二维数组来存储,效果是最好的。极小化极大值搜索,正常需要两个函数,一个搜索极小值,一个搜索极大值。因为其实大部分逻辑是一样的,完全可以把这两个函数合并成一个。然后把对手的分数变成负的,就是我方的分数。这种实现就是「负极大值搜索」。

评估函数

因为有了搜索策略,我们还需要进行局势的评估。我们简单的用一个整数表示当前局势,分数越大,则自己优势越大,分数越小,则对方优势越大,分数为 0 是表示双方局势相当。

评估函数,它接受一个角色,因为分数是相对角色而言的,返回一个整型数。比如如果对电脑是 1000 分,那么同样的局势对人类棋手就会返回 -1000 分。

我们对五子棋的评分是简单的把棋盘上的各种连子的分值加起来得到的,对各种连子的基本评分规则如下:

如果一侧被封死但是另一侧没有,则评分降一个档次,也就是「眠四」和「活三」是相同的分:

按照这个规则把棋盘上电脑的所有棋子打分,之和即为电脑的单方面得分,然后对玩家的棋子同样打分得到当前局势的总分数。

那么如何找出所有的连子呢,目前我的方式是遍历数组,一个个的数。他就是对单个点进行评分的模块。

(请注意,这里说的评估函数是对整个棋局的评估,后面讲启发式搜索的时候还会有一个启发式评估函数是对某一个位置的评估。这两个评估是不同的。)

为什么要进行剪枝?

上面讲了极小化极大值搜索,其实单纯的极小化极大值搜索算法并没有实际意义。

可以做一个简单的计算,平均一步考虑 50 种可能性的话,思考到第四层,那么搜索的节点数就是 50^4=6250000,比如在我的 Core i7 的 CPU 上一秒钟能计算的节点不超过 5W 个,那么 625W 个节点需要的时间在 100 秒以上。电脑一步思考 100 秒肯定是不能接受的,实际上最好一步能控制在 5 秒以内。

顺便说一下层数的问题,首先思考层数必须是偶数。因为奇数节点是 AI,偶数节点是玩家,如果 AI 下一个子不考虑玩家防守一下,那么这个估分明显是有问题的。然后,至少需要进行 4 层思考,如果连 4 四层都考虑不到,那就是只看眼前利益,那么棋力会非常非常弱。如果能进行 6 层思考基本可以达到对战普通玩家有较高胜率的水平了(普通玩家是指没有专门研究过五子棋的玩家,棋力大约是 4 层的水平),如果能达到 8 层或以上的搜索,对普通玩家就有碾压的优势,可以做到 90% 以上胜率。

Alpha-Beta 剪枝算法原理

Alpha-Beta 剪枝算法是一种安全的剪枝策略,也就是不会对棋力产生任何负面影响。它的基本依据是:棋手不会做出对自己不利的选择。依据这个前提,如果一个节点明显是不利于自己的节点,那么就可以直接剪掉这个节点。

前面讲到过,AI 会在 MAX 层选择最大节点,而玩家会在 MIN 层选择最小节点。那么如下两种情况就是分别对双方不利的选择:

  1. 在 MAX 层,假设当前层已经搜索到一个最大值 X,如果发现下一个节点的下一层(也就是 MIN 层)会产生一个比 X 还小的值,那么就直接剪掉此节点。
  2. 在 MIN 层,假设当前层已经搜索到一个最小值 Y,如果发现下一个节点的下一层(也就是MAX 层)会产生一个比 Y 还大的值,那么就直接剪掉此节点。

解释一下,对于 「选择 1」来说,也就是在 MAX 层的时候会把当前层已经搜索到的最大值 X 存起来,如果下一个节点的下一层会产生一个比 X 还小的值 Y,那么之前说过玩家总是会选择最小值的。也就是说这个节点玩家的分数不会超过 Y,那么这个节点显然没有必要进行计算了。

通俗点来讲就是,AI 发现这一步是对玩家更有利的,那么当然不会走这一步。

「选择 2」是一样的道理,如果玩家走了一步棋发现其实对 AI 更有利,玩家必定不会走这一步。

下面图解说明,直接用维基百科上的图:

如上图所示,在第二层,也就是 MIN 层,当计算到第二层第三个节点的时候,已知前面有一个 3 和一个 6,最大值至少是 6。在计算第三个节点的时候,发现它的第一个孩子的结果是 5,因为当前是 MIN 节点,会选择孩子中的最小值,所以此节点值不会大于 5。而第二层已经有一个 6 了,第二层第三个节点肯定不会被选择。因此此节点的后序孩子就没有必要计算了。

其实这个图里面第三层分数为7的节点也是不需要计算的。

这是 MAX 节点的剪枝,MIN 节点的剪枝也是同样的道理,就不再讲了。Alpha-Beta 剪枝的 Alpha 和 Beta 分别指的是 MAX 和 MIN 节点。

虽然原理说了很多,但是其实代码的实现特别简单。

maxmin 函数都增加一个 alphabeta 参数。在 max 函数中如果发现一个子节点的值大于 alpha,则不再计算后序节点,此为 Alpha 剪枝。在 min 函数中如果发现一个子节点的值小于 beta,则不再计算后序节点,此为 Beta 剪枝。

优化着法生成的效果

着法生成(Generator),顾名思义,就是在每一步生成所有可以落子的点。并不是所有的空位我们又要搜索,很多位置明显不合适的我们可以直接排除。这个函数非常重要,我们要尽可能删除无用点,尽可能做更好的排序,这样才能最大限度发挥 Alpha-Beta 剪枝的效果。

按照 维基百科上的说法,最大优化效果应该达到 1/2 次方。也就是如果你本来需要计算 10000 个节点,那么最好的效果是,你只需要计算 100 个点就够了。这是建立在所有的节点排序都是完美的假设上的。因为我们不可能完美排序,所以我们的优化效果达不到那么好。但是依然可以达到约 3/4 次方的优化效果。

对生成的着法进行排序的算法,就叫 启发式评估函数,下面我们将介绍如何实现启发式评估函数。

什么是启发式搜索评估

前面讲到了,Alpha-Beta 剪枝搜索的效果很大程度上取决于子节点的排序。

还是前一章的那张图,上面可以看到在第二层中,第一个节点的值是 3,第二个是 6。因为 3 比较小,而这一层的最大值会被选中,所以第二个节点也需要完整计算所有孩子。如果 3 和 6 调换一下顺序,6 在前,3 在后。那么当第二个节点计算出第一个孩子 5 的时候就没有必要计算之后的孩子了。也就是,Alpha-Beta 剪枝的效率和节点排序有很大关系,如果最优的节点能排在前面,则能大幅提升剪枝效率。

对于 Beta 剪枝也是同样的道理。所以说 Alpha-Beta 剪枝的效率是取决于每一层节点的顺序的。我们肯定是无法精确排序的,因为每一个节点的值并不能直接计算出来,需要递归计算子节点。但是我们依然能对节点进行大致的一个排序。前面说过了,只要有一个大致的排序其实就能很好的提升剪枝效率。

那么如何排序呢?就是给所有待搜索的位置进行打分,按照分数的高低来排序。注意这个打分算法是对某一个空位进行打分,和对整个棋盘进行打分的 evaluate 函数是不一样的。不过打分的基本原理是相同的。具体就是根据这个位置是否能成五,活四,活三等来进行打分。

有了打分之后,我们就可以按照分数高低进行排序了。具体实现的时候,是根据按照成五、活四、双三、活三、其他的顺序来排序的。

To be continued...

Responses