从零开始五子棋

发表于 | | 本文阅读量 次

在学校的时候上王老师的人工智能课，了解博弈树、启发式搜索、剪枝这些基本概念，很遗憾在当时没有完成五子棋。最近在和x 下五子棋的时候突然念头一闪，于是有了这篇文章和基于Minimax 算法的五子棋程序。程序源码：https://github.com/VincentGau/TicTacToe 包含井字棋和五子棋代码；

五子棋游戏是一个两方博弈过程，双方都能获取局面的完备信息，交替行动，最终一人获胜或达到平局，典型的零和博弈。适合使用极大极小值搜索来求解。极大极小值搜索是实现这个五子棋程序的基础。

极大极小值搜索

极大极小值搜索过程的本质是回溯，以深度优先方式遍历多叉树。
以棋类游戏为例，对于一个局面，一方有多种可能的落子法，对于它的任何一种落子情况，对方也都有多种落子，如此轮流行动。以多叉树形式表示，树的每一个节点表示一种可能的盘面，子节点表示所有可行方案，树的每一层代表一方，双方在树中交替出现。为了获取最后的胜利，一方要在所有可选项中做出能将其优势最大化的决策，另一方则选择令对手优势最小化的方法。极大极小值搜索过程中，假设每一步对方也会按照它的最佳方案行动；我们将博弈树中的层分成Max 层和Min 层，为了保证自己的收益最大化，Max 层节点会始终选择值最大的子节点来更新自己的值，Min层则相反，始终选择值最小的子节点；因此这个算法被称为Minimax。 以一个简单的图理解Minimax 算法：

上图中，有两类节点，分别代表博弈双方，

  • 方块，Max 层节点，代表我方回合，他始终选择子节点中的最大值来更新自己的值；
  • 圆圈，Min 层节点，代表对方回合，他始终选择子节点中的最小值来更新自己的值；
    现在节点1有两种选择，它应该做出怎样的选择，就是Minimax 算法要解决的问题。
    节点1 处于Max 层，它要选择2、3 中评价值最高的那一个；节点2 处于Min 层，它取值为所有子节点中最小的值，也就是节点5，所以节点2 的值为 3；同理，节点3 的值为1； 节点1 的值为3；所以节点1 应该选择第一种下法；虽然第三层四个节点中，评价值最大的是节点7，但是如果节点1 选择第二种方案，到达节点3，到对方轮次，此时决定权已经到对方手中，为了使利益最大化，对方会选择到节点6；

搜索的目标是选择一处收益最高的位置落子，上面的例子里，我们认为叶子结点的值是已知的，而实际上对于五子棋游戏，我们还不知道节点的值，为此，我们需要设定一个评判标准给节点打分，这就是后面我们会提到的评价函数。

评价函数

评价函数是影响决策的关键。首先了解五子棋的一些特征局面，

  • 连五：出现连续五个同色棋子；
  • 活四，有两点可以连五；
  • 冲四：有一点可以连五；
  • 活三：可以形成活四的连三；
  • 眠三：只能形成冲四的连三；
  • 活二：可以形成活三的连二；
  • 眠二：只能形成眠三的连二；

评分规则

如果盘面中有我方成五，表示我方已经获胜，因此给这个局面一个很高的评分（比如10000分），如果有对方成五，则给一个很低的评分（比如-10000分）；除了成五之外，活四等也是一个有利的局面，只需一步就可获胜，我们也给他一个相对较高的评分，比如8000（对方活四的话就给 -5000分）；类似地给双冲四、冲四活三、单活三等其他情况都设定一个分数：

棋型 评分
成五 10000
活四、双冲四、冲四活三 5000
双活三 3000
活三眠三 2000
冲四 1000
活三 500
双活二 400
眠三 300
活二 200
冲二 100
活一 70
死一 50

我们对盘面上的每一个点进行评分（我方为正，对方为负）；盘面的评价函数定为所有点中最高得分和最低得分之和。

点的评价函数

给每一点估值时，向八个方向扩展若干个位置，

α-β 剪枝

理解α-β剪枝

alpha-beta 剪枝是在Minimax 算法基础上的优化，避免扩展哪些不会被选择的节点，减少无效操作从而提高搜索效率。继续使用前面的例子来理解剪枝的过程。

我们扩展节点2，得到它的值为3；继续扩展节点3，因为节点3 处于Min 层，且节点6 的值为1，所以节点3 的值不可能大于1， 因此不论节点3 后面的子节点的值是多少，节点1 一定会选择到节点2，所以在得知节点6 的值为1 之后，节点3 到节点7 这条分支可以直接忽略，这个过程称为剪枝；

这里只对剪枝做了大概的理解，更多参见α-β剪枝

算法实现

为每一个节点增加α 和β属性，α 表示最大下界， β表示最小上界；在节点扩展过程中持续更新α 和β 的值，在Max 层更新α， Min层更新β；如果发现α 大于β， 则进行剪枝，不再计算后续子节点；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public int minimax()
{
    ...
       
    // Max layer, computer's turn 
    if (turn == 0)
    {
        int maxInChild = int.MinValue;
        foreach (var move in availableMoves)
        {
            BoardState childState = new BoardState(newBoard(move, Helper.AIMark), changeTurn(turn), depth + 1, alpha, beta);
            
            // 搜索到最大深度或者已分出胜负，直接计算盘面评分
            if (depth >= Helper.searchDepth || checkFinished(childState.board).Count == 5)
            {
                childScore = evaluateBoard(childState.board);
                nextState = childState;
            }
            // 否则，继续计算子节点的评分选取最大者
            else
            {
                childScore = childState.minimax();
            }


            if (childScore > maxInChild)
            {
                maxInChild = childScore;
                alpha = maxInChild;
                nextState = childState;
                nextMove = move;
            }

            // 剪枝
            if (alpha >= beta)
                break;
        }
        return maxInChild;
    }

    //Min layer, player's turn
    else if (turn == 1)
    {
        // 与上类似
    }

    return 0;

}

算法优化

了解了Minimax 算法之后，我们可以想象，随着搜索深度的增加，需要计算的节点呈指数增长，虽然相较围棋复杂度低很多，但是我们想要穷举搜索这颗博弈树的所有叶子结点（最终一方获胜或平局）依然是不可行的，因此我们需要对此做一个限制，有两个方向，一个是设定搜索深度，这个深度即AI思索的步数，另一个是缩小可行落子点的范围，对于一些明显不适合的落点我们不进行扩展。

缩小候选点范围

五子棋盘有 15 * 15个点，所有没有落子的地方都是可行的，我们不可能对每种可能的落子情况都进行扩展，这些点中有一些明显不符合最优解，比如边角处，远离棋子圈处，我们可以通过缩小候选落子点范围来提升效率。在实践中，我选择那些周围有棋子存在的空位作为可能的落子点，比如棋盘上对方下了第一步，我们只考虑它周围一圈的八个点，因为只有这八个点周围有棋子（棋盘上的唯一一颗棋子），这样极大第减少了需要扩展的点，这样选取候选点没有经过科学验证，虽然可能失去潜在的最佳方案，但是直觉上落子在远离其他棋子的地方不会获得太多收益；

候选点排序

剪枝算法的效率依赖于着法的寻找顺序。如果总是先去搜索最坏的着法，那么剪枝就不会发生，最终会找遍整个博弈树，这时该算法就如同极大极小算法一样，效率非常低。所以我们考虑对候选点进行排序来提升效率。这里涉及到对候选点进行打分，如果在一个候选点落子后可以形成连五（或者阻止对方成五），那么它的评分应该偏高。为此我们首先为各种棋型设定一个评分规则：
成五
活四、双冲四、冲四活三
双活三
活三眠三
冲四
活三
双活二
眠三
活二
冲二
活一
死一

五子棋盘有15 * 15 个落子点，这些点有一些明显不符合最优解，比如边角处，远离棋子圈处，缩小候选落子点范围能有效提升处理速度和效率；通常棋子圈附近是落子的好选择；刚开局时落子；
候选落子位置根据已落子点周围一圈时确定，搜索深度为四层时，时间过长，只计算到达第四层的盘面估值和已经分出胜负的盘面估值；即使一步即可获胜，也需要等到前面的节点完成深度搜索；可以尝试对第一层进行估值，使用最大堆保存估值较高的K 个节点进行深度搜索，可更快发现一步获胜局面；

棋型：
连五：出现连续五个同色棋子；
活四，有两点可以连五；
冲四：有一点可以连五；
活三：可以形成活四的连三；
眠三：只能形成冲四的连三；
活二：可以形成活三的连二；
眠二：只能形成眠三的连二；

评价函数是影响决策的关键：
是对整个盘面进行评估还是对单个落子点进行评估？ 评估是否应该与轮次挂钩？ 考虑一种情况：黑子（max）形成冲四，如果是黑子轮，黑子下在第五个延伸位置即可获得连五的分数，如果是白子轮，它下在第五个延伸位置对自己成五可能并没有收益，但是它还是应该下在这个位置防止对方获胜；评价函数用二者之差来表示，博弈树中黑子作为max层追求最大的估值，白子作为min层追求最小的估值，黑子落第五个位置可获得10000分，假设白子落此位置可获得 -10 分（白子连五获得-10000分），