前言

从有了计算机开始,人们便从来没有停止对于机器博弈的研究。最早击败人类的 AI,是1997年的深蓝。之后随着硬件以及算法的深入发展,计算机也越来越强,而人工智能与神经网络的发展更是对于机器博弈如虎添翼。即使是被誉为“人类的最后一道壁垒”的围棋也在前几年被 AlphaGo 斩于马下。

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

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

实际上,大家最常见的博弈游戏就是象棋、围棋、五子棋等等。因此实际上这类游戏都可以用这篇文章当中的算法思想来实现。

但是实际上如果简单地去实现博弈(比如暴力破解之类的),算法的复杂度将是一个天文数字。下表是我们常见的棋类游戏的复杂度,大家可以感受一下:

名称 复杂度
黑白棋 58
五子棋 70
国际象棋 123
中国象棋 150
围棋 360

这些都是以10为底数的指数,也就是10的 n 次方。可见,简单破解是行不通的。

因此,实际上我们的算法所需要完成的工作就是,尽可能快地寻找到当前形式下的最优解,去掉没有用地解法,并作出相应的决策。

通过一些资料的学习,我也逐渐了解掌握了机器博弈的算法并实现了一个简单的五子棋 AI,并将其取名为 Last Order(即最终之作)。相信各位有看过超炮的小伙伴应该对这个名字不陌生了叭~

之后我将简单地对我的算法进行一个介绍~

项目地址:https://github.com/DavinciEvans/gobang-Cpp

PS:实际上这是我的 Linux 大作业所以实际上包含了 windows 和 Linux 两套编译版本 XD

基本概念

首先我们需要明白决策树的概念。

我们以五子棋为例,假设在当前的情形之下我落下了一颗子。

对于标准的 15*15 的五子棋棋盘来说,在下一步机器拥有 15*15 的走法,而在这所有的走法之下,又拥有 15*15 种走法的可能性。由此便形成了一个巨大的树状网络,我们便称之为决策树。一般我们普通人会往后推导四步。如果机器也想往后想四步,那在决策树的最底层叶子节点,将会有 15⁸ = 2 562 890 625个决策节点,而如果只考虑两步,那相当于只考虑眼前,棋力将会非常弱。但即使只有四层,这个计算量也已经相当大了,显然如果用暴力穷举是行不通的。

下图便是一个简单的决策树的例子。

对于我们的机器博弈算法来说,所需要实现的便是从这颗巨大的博弈树当中寻找到最优的一条路径。通常来说常用的算法是极大极小值搜索算法和 Alpha-Beta 剪枝算法。这个之后会进行详细的介绍。

算法思想

评估函数

在详细介绍极大极小值搜索算法前,我觉得很有必要先介绍评估函数。

既然要想让机器能下五子棋,首先我们需要做的就是“让机器看懂棋盘”。通常,我们会将整个棋盘抽象成一个二维数组,然后用不同的数字(比如1和2)来表示黑子和白子。

评估函数则是起到了让机器“理解棋盘”的作用,即能通过分析整个棋盘,计算出当前的局势是对自己是利是弊。如果对于机器有利,则计算出的局势为正值,反之对人类有利则为负值。如果为0则表示旗鼓相当。

我们规定了几种棋形,每种棋形拥有一定的权重,计算机能通过分析整个棋盘上的棋形,计算整个棋盘的权重。

棋形一般分为“活”和“冲”,“活”即代表两端都没有被堵上,而“冲”则代表有一端被堵上了。现在规定的棋形有以下几个:

  • 连五:即五连子,代表一方赢棋(权重100 000)

  • 活四:四连,四连的两端都没有被堵(权重50 000)

  • 冲四:四连,四连的某一端被堵上了(权重400)

  • 活三:三连,三连的两端都没有被堵(权重400)

  • 冲三:三连,三连的一端被堵上了(权重20)

一般来说,冲的权重就是下一等级的活的权重。

权重代码定义如下:

```C++
#define OTHER 0//0
#define WIN 1//100000
#define LOSE 2//-10000000
#define FLEX4 3//50000
#define flex4 4//-100000
#define BLOCK4 5//400
#define block4 6//-100000
#define FLEX3 7//400
#define flex3 8//-8000
#define BLOCK3 9//20
#define block3 10//-50
#define FLEX2 11//20
#define flex2 12//-50
#define BLOCK2 13//1
#define block2 14//-3
#define FLEX1 15//1
#define flex1 16//-3
```

大写代表机器方,小写代表人类方。请注意,人类方权重的绝对值大约是原本棋形权重的10~20倍。

其实只要我们有了这个评估函数,并在每次做出决策时,找到权重最大的位置来作为我们的决策,就已经实现一个简单的 AI 了!如果一时大意,甚至可能会被 AI 下出双杀棋。

那么该如何实现这个评估函数呢?我的想法是使用一个六维数组 chess_Status 属性来保存所有的棋形以及权重。判断时将每一个格子放入六维数组的每一位当中,从而直接获得权重。

具体评估函数的实现代码都在 LastOrder.cppevaluation 函数当中。

极大极小值算法

但是我们也应该清楚,如果每次只把棋子下在权重最高的位置,其实是非常短见的。实际上,我们的决策不应该只考虑当下,而是要往后看多步。也就是说,当前决策的权重值不应该只由评估函数来决定,而是由后面的几步来决定的。

极大极小值搜索就是起到这么一个作用(假设搜索深度为4):先通过对决策树进行 DFS 求得第四步的权重值,再自底往上来求取每一个节点的权重值。

我们先来简单看一下这个算法的具体图解(图源维基百科):

机器方就是甲方,而人类方就是乙方。我们将甲方称为最大层(Max 层),乙方称为最小层(Min 层),在 Max 层,我们需要从它的子节点中选出权重最大值作为自己节点的权重,反之在 Min 层则是从子节点选出权重最小值作为自己的权重。

例如上图的节点7,其拥有三个子节点权重:2、9、3。因为是位于 Min 层,因此选用权重最小值作为自己的权重值,即2。

我们遍历这颗博弈树的时候就很明显知道这个算法的原理了:

  • 在 MAX 层,这一层电脑要保证自己利益最大化,那么就需要选分最高的节点。
  • 在 MIN 层,这一层玩家要保证自己的利益最大化,那么就会选分最低的节点。

Alpha-Beta 剪枝

我们解决了“如何寻找最优解”,但并没有减小问题的规模。

这也因此需要用到我们的剪枝算法,即去除掉不需要的叶子节点,大幅度减少计算量。它的基本依据是:棋手不会做出对自己不利的选择,如果有一个节点是对我们不利的,那我们就可以将其剪枝。

Alpha 代表下界,Beta 代表上界。在最开始时,Alpha 为负无穷,Beta 为正无穷。然后进行搜索,max层节点每搜索它的一个子节点,就要更新自己的 Alpha(下界),而min层节点每搜索它的一个子节点,就要更新自己的 Beta(上界)。如果更新之后发现 Alpha >= Beta了,说明后面的子节点已经不需要进行搜索了。

上图即为剪枝示意图,这可以极大减小我们的计算量。

启发式评估函数与局部搜索

大家经过仔细研究上图后发现,如果第二层是3、6,由于3比较小,因此也需要把6的所有孩子全部计算一遍。而假如6先发生,那么当计算出5的时候就没有必要计算之后的孩子了。因为此时的 Beta 已经为 6。

也就是说,如果我们一个更优良的决策能尽早被计算出来,那么后面就可以剪枝地更多。

为了能尽快计算更好的决策,我们将决策进行排序,并选出前10个决策,事实证明10个决策已经完全可以得出科学的决策了。之后我们从权重最高的进行计算,以此来尽快生成剪枝。

而局部搜索则较容易理解:我们在下五子棋的时候,更多是考虑已经落子的周围,而不会去思考边边角角,因此在我们做决策时,我们也只搜索落子的周围。我设定的规则是一颗棋子沿着水平、竖直、斜向各延申三格的位置,我们只在这些位置做出决策。

将启发式评估函数与局部搜索相结合,也就是只在已经落了棋子的周围找出权重最高的十个点,并分别对他们进行极大极小值搜索和剪枝。根据这个算法,如果计算4层,那么实际上只需要考虑5000个决策,已经减少了非常多了!

还未结束

虽然目前,我们的 Ai 已经取得了非常大的进步,但实际上与真正的高手依然存在着距离。本文只是提供一个入门的基础,但是依然有着非常多需要优化的地方:比如在 Ai 快赢棋的时候,Ai 会去调戏玩家;没有算杀模块,Ai 进攻性依然不强;没有采用多线程,使得不能进行更深更快的计算······这些东西我本人也在不断地学习研究之中,欢迎各位感兴趣的同学一起来和我讨论~

参考文献

五子棋ai:极大极小搜索和α-β剪枝算法的思想和实现(qt和c++):https://blog.csdn.net/livingsu/article/details/104544562

javascript gobang AI,可能是github上最受欢迎的五子棋AI:https://github.com/lihongxun945/gobang


You Are All Stardust.