基于Alpha- Beta剪枝Max-Min博弈树的五子棋对战AI

前言

用到的技术

• 极小化极大值搜索（Max-Min）
• Alpha- Beta剪枝
• 棋局局面评估方法与优化
• Ac自动机
• IDA*（迭代加深）
• A*（启发式搜索）
• Zobrist-Hashing（Zobrist哈希方法）
• QT-UI框架

博弈树

概念解释：

• 顾名思义，对于“一来一往”式的棋牌（博弈）游戏，可以将双方的每一个选择构建为一条双方交替进行的链式结构A-B-A-B...
• 博弈树将当前选择的所有可能扩展指上述链式结构（类似于邻接表），由此便可将双方的未来可能选择用一棵树来表示，树的每一个节点代表一种决策。
• 以Gobang Game为例，则深度为奇数层的节点代表黑棋的决策，偶数的层节点为白棋决策，因此一棵五子棋的决策树便初步建立。（如下图）

极小化极大值搜索（Max-Min）

• 设想一下，对于一个棋手，在选择下一步的着子位置时，一定是尽量选择最有利与自己（等价于最不利于对方的位置）

• Max-Min搜索就是基于以上想法，在博弈树中将当前自己着子的那一层命名为Max层，对方的命名为Min层，接下来进行如下讨论：

  1. 当前处于Max层
  • 该自己着子，因此选择当前局面最有利于自己的位置（如何寻找这个位置后文会讲），随后进入Min层
  2. 当前处于Min层
  • 该对方着子，此时应该选择最不利于自己的位置（有利于对方），让对方着子

• 假设现在我们进行两轮搜索，即自己下一次，对方下一次重复两次：

  • Ps：为什么要按照轮来搜，而不是按照层？
    • 由于是双人博弈，因此应该自己下完以后让对方再防守一次，将防守后的结果进行比较，最后选择最好的解。这样的结果更有效
  • 如下图所示，建立博弈树以某一节点为例（画成二叉树只是便于讲解）：
    • 下面模拟搜索过程（前序遍历）
    • 第一次达到第4层，得到这条方案的对于对方玩家的最后局面评估为10，将记录的最优解分数（初始化为INF，假设我们定义分值越大越对结果有益，此时为Min层则对自己最有力的分数是越小越好，因为此时的打分是对方得分，自己得分+对方得分 = 0）更新为10，继续搜索得到-5，再更新，以此往复，最终找到最优解分数为-999
  • 上述类似的树在确认当前点的着法是有很多，树的规模取决于每次决策后新的对应决策的规模，对五子棋而言，可以将每次的新着法确定为棋盘已有点的8联通方向上距离为1的点，由此可见，这棵树的规模非同寻常

局面评估

• 顾名思义，我们需要对当前黑白子的局面分别打分，将分值作为局面的评估结果，对于两个持方，其评估分数互为相反数（val_black = score_black-score_white,val_white = score_white-score_black）
• 我们可以对局面上所有的棋子，分离其8联通方向的连成活棋的数量
• 
• 对不同情况给予相应的分值，一个位置的分值为其8联通（x，y，right_edge,left_edge）的评分之和
• 最后将所有同色棋的得分相加作为该持方的分数，分数相减得到对应持方在本局面的分数
• 实现：
  • 首先需要定义8联通方向的偏移数组，然后分离出对应的布局，这里可以用字符串来记录

//Key-val分值表
std::vector<Pattern> patterns = {
    { "11111",  50000 },
    { "011110", 4320 },
    { "011100", 720 },
    { "001110", 720 },
    { "011010", 720 },
    { "010110", 720 },
    { "11110",  720 },
    { "01111",  720 },
    { "11011",  720 },
    { "10111",  720 },
    { "11101",  720 },
    { "001100", 120 },
    { "001010", 120 },
    { "010100", 120 },
    { "000100", 20 },
    { "001000", 20 },
};

• 最后从已有的key-val打分对中进行字符串的匹配（这里用的是Ac自动机匹配见后文），同时累加最后的得分

//Ac自动机匹配
std::vector<int> tmp = acs->ACSearch(s);
for (int j = 0; j <(int)tmp.size(); j++) {
  ans += patterns[tmp[j]].score;
}

小结：

• Max-Min的搜索方式可以模拟人类下棋方式，将多轮后的最优解更新保存，得到一个经过多层考虑的节点，对于五子棋而言，考虑4层基本上就可以打败大多数人类玩家了。

• 但是Max-Min的搜索方式存在严重的缺陷：

  • 对于搜索层数的增加，所需的时间与空间是指数级倍增的，例如在仅搜索1层的情况下，需要50ms，当层树上升为4层时，所需的时间就变成了$(50ms)^4 = 104mins$，显然一局饭后娱乐的五子棋不可能允许这么久的思考时间，接下来就引入了一个至关重要的剪枝方式：Alpha-Beta剪枝

Alpha-Beta剪枝

• 在刚才的搜索中可以发现：

  • 开始时我们得到的解为10，然后遍历到-5，此时由于我们是按照每个玩家都以最优解来行棋，因此聪明的对手一定不会选择-5的方式（因为前面有10可以让自己更优势），因此第三层Max的第一个节点，分值就是-10（针对自己）。同理在后面当18和21做出抉择时，会选择21，分值是-21，在第2层的Min层聪明的对手一定会想到我们会选择让对手是-10的方式（自己是10）让自己更优，，因此，我们可以得到根节点的左子树的最后分值为10。

  • 因此，我们可以将当前得到的结果作为返回值传递给上层，同时使用Alpha,Beta两个参数（初始化为-INF和+INF）分别记录Max层和Min层的最优解（Max层更新Alpha取二者Max，Min层更新Beta取二者MIn），一旦发现某一层更新完Alpha/Beta后发生了Alpha>=beta，进行讨论：

    • 如果上一层是Max，这层是Min，我们更新Beta后发现，现在的Beta比上层传来的Alpha小，说明上一层（Max）在遍历当前节点之前已经有一个解得到的了一个更分值更小的Min层子节点解，则当前点及其分支就可以剪掉，然后返回当前的Beta
    • 如果上一层是Min，这层是Max，我们更新Alpha后发现，上一层传来的Beta比现在的Alpha小，说明上一层（Min）之前已经有一个解得到的了一个更分值更大的Max层（子节点）解，则当前点及其分支就可以剪掉（或者也可以说是之前有一个Max层的子节点【Min层】得到了一个更小的解），返回当前的Alpha

  • 纸上谈兵终觉浅，绝知此事要躬行，还是用上面这个图，标出Alpha和Beta模拟一下过程：

  • 1. 首先初始化alpha = -INF，beta = INF，依次传递至最左下节点（10）并返回该节点的val = 10,其父节点为Max层更新Alpha为10，

    2. 再进入其右儿子，返回val = -5,比Alpha小不更新，随后返回Alpha = 10到其前的Min层，更新Beta为10，

    3. 进入该点的右儿子，继续遍历，返回val = 18，更新Alpha为18，出现Alpha>=beta ，剪枝直接返回此时的Alpha = 18。

       这里解释一下为什么剪枝是合理的：

       首先，在最底层的Min层，聪明的机器【当前持方为你的对手】一定会选择一个更大的值让自己处于最优，作为我们自己，肯定不希望你的对手的分越来越大，由于之前已经有一个分是10自己的下法可以让对方的分最后是10了，因此在这之后比他大的都不是最优解。

       但这里可能会有一个疑问，假如说18的兄弟21的值改为-999，那这样岂不是更好吗，让他的分更小更有利于我们？

       请注意，对于最后的Min层，这里是对手做选择，也就是说，现在我们下完之后，对手有两个选择，一个是让自己达到18，一个是到-999，那么，聪明的对手一定会选择18，选了-999一定是在演你（犯傻），因此在新的节点的Min层有一个比之前的最优解更好（这里表现为分更高），那整个这条分支就不能选——如果下到这条分支，聪明的对手就会把这个高分选上，所以直接砍掉这整个分支就可以了。

    4. 随后9和-999都比10小，Alpha都不更新，直到后面到达999，Alpha发生更新，最后当遍历结束，Alpha = 10，beta = 999（下面简单画了个图，按着尖头方向就是遍历更新的顺序）

  • 

小结

• Alpha-Beta剪枝极大的减少了遍历的点，缩短了耗时
  • 根据本人实践，在不使用剪枝的的情况下，搜索极限大概是3层（本人是M1的Mac），四层基本跑不出来，加上剪枝后4层耗时在几秒左右，提升是肉眼可见的。
• 缺点：
  • 这种Alpha-Beta剪枝，极其依赖搜索顺序，在最坏情况下，如果最优解在整个前序遍历的最末尾，那么相当于没有剪枝，因为为了找到最优解我们遍历了整棵博弈树。
  • 以之前的例子来说，如果将值为9的那棵树第一次搜索，则能剪掉的子树将增加一棵（10和-5的）。
  • 不难发现，对于每一次可以选择点进行搜索时，将越对己方有利的点先搜索，在更新alpha和beta后可以更早的发生剪枝，因此确定每一层的子树的搜索顺序变得极为关键，下面将对其进行优化——A*（启发式搜索）。

A*

• 对于每一层的搜索次序，我们刚刚发现如果能先搜对当前持方更有利的会更早的开启剪枝，因此现在需要一种对当前点所有儿子的评估方法，使得先搜最好的，以尽早开始剪枝
• 从所有的儿子里找最好的点也是一个对点评分的过程，这里提供两种方法：
  1. 对接下来要选的点，进行“点评估”，即统计其8联通方向的分数，按从大到小排序以得到搜索次序
  2. 使用之前的全局评估函数，对所有点进行评估，按从大到小排序以得到搜索次序
• 似乎第一种算起来更快（其实差距不大），但是第一种可能会有一些极端情况，导致双方互冲活3而犯傻（概率很小），毕竟是点评估，很难照顾到全局，目前来看选择两种都可以，但后续优化过程中，用全局评估会更好（后文会给予解释）
• 实现起来还是很容易的，只需要维护一下当前局面所有点周围的空点的评估分数，最后排个序即可（这边用到了stl的Set-红黑树，用堆或者数组都可以的，复杂度都是nlogn）

小结

• 到目前为止，搜个4层已经是轻轻松松了，在较好性能的机器上还可以搜到6层（但是比较慢了），这也是传统博弈算法的局限性，棋力非常依赖搜索层数，直接体现就是4层以后可以下出很多双活3/眠4+活3
• 但是我们的优化还没有停止，依然存在一些小点可以优化：
  • 每次回溯后在进入子树会存在一些重复局面，此时需要重复计同一局面的评估值，无疑增加了不必要的计算——Zobrist-Hashing
  • 在评估函数的匹配过程中，使用的是BF算法，如果对匹配进行优化，可以继续缩短运行时间——Ac自动机
  • 对于当前已经来到必胜局面时，没有必要继续深层搜索，对于已经出现了杀棋，并且是必胜局面可以提前终止搜索——IDA*（迭代加深）
  • 为了进一步增加棋力，我们可以在完成常规搜索时，再加一次深层算杀。实现起来并不复杂，原理就是再开一棵AB博弈树然后仅考虑活3和活4这种杀棋，这种搜索一般可以达到8-12层，但这个算杀也有一定的局限性，当棋局逐渐复杂时，算杀需要的时间会更久，有超时的风险，本作没有加入算杀模块。

Zobrist-Hashing

• 由于博弈树的搜索本质是树的DFS，因此在回溯和拓展新层时，会发生局面的重复，对同一局面重复计算无疑是增加了运行成本，如何避免对同一局面的重复计算，我们想到的比较好的办法是使用记录+哈希访问的方式快速查找已计算过的局面评估结果

• 对于Hashing的方法，显然需要一个计算迅速并且冲突率低的方式将一个局面映射为一个（伪）唯一的HashCode

• Zobrish提供了一个对于棋局的快速Hash方法：

  1. 对于场上的每一个持方（五子棋是黑白），建立一个对应的棋盘，每一个可落子的点，在该位置上生成一个64位随机数。
  2. 对于一个局面，对于所有的落子位置，取出对于持方的随机数棋盘上的64位随机数进行XOR操作
  3. 最后得到的值就是这个局面的HashCode
  4. 然后再使用拉链法或开放寻址法建立Hash_list即可

• 对于五子棋，则是初始化两个15*15的ULL数组，填上64位随机数。不难发现，这种Hashing方式的最终冲突率与64位随机数的的质量有直接关系，由于五子棋的棋盘总共只有225个可落点，复杂度较小，因此可以使用C++的rand函数即可

  ULL getRandom64() {
      return (ULL)rand() | ((ULL)rand() << 15) | ((ULL)rand() << 30) | ((ULL)rand() << 45) | ((ULL)rand() << 60);
  }

小结

• Zobrist-Hashing的应用，减去了博弈树搜索时因为回溯而重复局面所需要的运算，最直观的体现是实用6/8层搜索时，悔棋后再次落子AI的运算速度大幅降低，但本质是对搜索过程的优化，对搜索深度的影响基本可以忽略（极限在6层）。
• 对于五子棋的局面Hashing方法有很多，核心点是要解决冲突率，这也是所有Hashing方法在设计时要遵守的原则。

Ac自动机

• 字符串匹配的经典算法之一，主要针对的是多模式串下的多匹配问题
• 基于Tire树和KMP，对于本项目中五子棋的棋局，存在很多前后缀相同的状态，因此使用Ac自动机可以加快局面评估中模式串的匹配
• 构建过程：
  1. 根据模式串构建Tire树
  2. 利用KMP构造失败指针（类似于单匹配中的Next数组）
  3. 对于给定的新串进行匹配（利用失败指针进行回溯）
• 本项目对Ac自动模块进行了oop封装，对于AcString.h & AcString.cpp

小结

• Ac自动机的加入，优化了局面评估中分数匹配的过程，但可惜的是对于五子棋来说，Ac自动机和BF之间的没有体现太大的差距，只有到后期双方下到百手以上才略有体现。
• 但是对于围棋、象棋等复杂度更高的棋类博弈AI，更快的模式匹配（使用Ac自动机）的优化效果是比较明显的，即初始的模式串越多，优化效果越显著

IDA*

• 迭代加深顾名思义是将搜索的层数从小到大依次提高，如果在浅层可以找到我们想要的最优解则没必要进入深层继续搜索
• 以五子棋为例，如果当前局面我们已经可以达到双活3，或者活4、成5等必胜局面，此时已经可以判赢，换而言之，继续搜索深层是没有意义的。
• 我们假定搜索的最大深度是6层：
  1. 首先先从定义最大搜索深度为2层，
  2. 如果得到2层下的最优解已经可以判赢（局面评估分值足够大）
  3. 此时不必进行深层搜索，直接返回当前的走法即可
  4. 如果没有可以达到判赢的标准，继续进入最大深度为4层的搜索
• 实现：只需要在Alpha-beta搜索方法中加入一个最大层（Maxdepth）的限制即可，到达限制直接返回，外层使用一个for循环设置Maxdepth参数为偶数即可（为什么是偶数之前说过：一攻一防的结果更可靠）

小结

• IDA* 的加入最直观的感受是，AI在走出必胜局面后，行棋速度大幅增加（活3冲活4，活4冲活5的速度在6层下结果几乎秒出）。
• 同时，IDA*可以提高些许棋力，对于对方的成双活3，眠4加活三的杀气能更好的进行防守，不会因为搜索到更深层而替换行棋方式输掉棋局。

贪心优化

• 这是一个可以突破8层搜索瓶颈的优化方式，实测可以在前文优化基础上，可以将搜索层树提高到14层，然而这种优化具有明显的两面性
• 原理：对于复杂度较低的五子棋来说，我们选择的下一步行棋的位置，具有明显的指向性（目的性），即下一步行棋后，棋局上的优劣势方会发生变化：体现在评估结果上，在对方行棋后，我方分数会变为负数，而在我方行棋后，对方分数又会为负。
• 其次，我们发现，每一次的行棋其实总有几步是最鲜明的最优解，例如：
  • 对方活3，我们的最优解就是堵活三或自己冲4
  • 对方冲4，我们的最优解是堵眠4或自己成5
  • 可以发现，总有几步的分很高，其他的分很平庸
• 因此，由于A*算法的加入，其实就是让我们可以先搜索这些分数很高的棋（很有可能是必走的棋，即不走就输），然后再搜索平庸的棋，而这些平庸的棋，很多情况都是对我们最优解没有影响的棋，甚至可以不搜。
• 综上，我们只需要搜索每次A*得到的搜索序列中，前10个行棋方式，然后对其进行拓展，这样就可以在保证不会发生走臭棋的前提下，增大搜索层数得到更有利于我方的走法。

小结：

• 这种贪心方法并不能用于所有的博弈算法中，换而言之是五子棋的特性（每一次选择都几个很凸显、分数很高的走法）带来的一种优化。
• 但是这种优化也有局限性，假设最优的走法是在A*得到的序列中排第11位，那么就有可能因为只搜前10个的策略而丧失赢棋机会，实测当AI先手时确实会发生过这种情况。
• 由于五子棋没有太多棋子攻杀，隔山打牛等在象棋、围棋中的绝妙走法，因此加入此贪心优化不会对棋力产生太大影响，但由于加入后可以大幅增加搜索深度，因此对棋力的提升相较于优化本身的带来的负面影响更加显著，用一个形象比喻就是，加入优化而带来的搜索层数的提高是10分，优化带来的负面影响是-3，最终还是进行了7分的正优化。
• 本质上由于五子棋也不需要这么深的思考深度，4层已经可以有不错的棋力了，因此这种贪心优化的作用更多在于对付一些“套路”。

Qt制作UI界面、同时对AI进行oop封装

• 使用QPainter绘制五子棋棋盘、棋子
• 使用QMouseEvent获取鼠标事件，处理鼠标移动以及落子操作
• 将棋盘操作进行oop封装为BoardWidget，继承QWidget
• 最后将模式设置、难度选择、先后手选择、悔棋、重置、认输按钮等棋盘外UI进行封装为GameWidget，同样继承QWidget
• 最终在Main中实例化GameWidget对象并调用父类的show方法即可
• 将AI的操作封装为aiJudge类，接口传入已有局面和持方即可进行AI行棋。

成果预览

UI

• 选择难度
  • PVE
  • PVP
  • Dedution——棋谱模式，输入棋谱后可使用AI走棋

• 选择先手

  • AI
  • Human

• 选择难度

  • 对应四个难度，括号内为搜索层数

• 棋盘与功能按钮

  • 窗口标题为相关游戏模式参数
  • Restart，清空棋盘，AI与Human交换先手
  • Repentance，悔棋
  • Admit Defeat，认输
  • ResetGame，重设游戏模式
  • 下方棋盘鼠标位置为红色方块，单击鼠标完成落子，棋子上附有行棋编号，对方上一步行棋为红色字体

棋力测评

1. 与第三方AI对战
   • 我方AI白棋（后手），获胜
   • 第三方AI
2. 利用在线对战平台与人类对战