使用 Min-Max 搜索和启发式评估函数实现五子棋 AI

问题描述

五子棋AI。

设计一个交互式的应用，用户用鼠标在棋盘上单击左键表示落子，然后五子棋AI分析棋局，并在它认为最好的地方落子，双方交替，直到分出胜负或者和棋。

在分析问题的过程中，我们假定图形用户界面已经完成，并且支持“开始游戏”、“重新开始”、“调整先后手”、“调整难度”等功能，获取鼠标的输入以及显示棋盘布局的功能也都正常，那么我们可以把精力放在五子棋AI类的具体实现上。

现在，问题被抽象成，在一个15*15的二维数组中，1表示黑棋，0表示白棋，-1表示还没有落子的空格，AI程序要做的是分析当前的局面，运用启发式评估函数进行搜索，找到对自己最有利（包括对对手限制最多）的地方落子，找到以后AI类返回这个点的坐标。

深度优先搜索似乎是可以完成这个任务的，但是很明显，就算是将大量的不可能是最佳落子点的部分去掉，形成的搜索树也是庞大到不可能在短时间内搜索完成。

人下棋的时候实际上用的是一种试探性的方法。

首先假定在这个位置走了一步棋，然后思考对方会采取哪些策略，或者对我的棋进行围追堵截，或者是继续下他的棋，然后我再根据对方可能采取的方法，看看我是不是有更好的回应……

这个过程一直持续下去，直到若干个轮回以后，找到了一个满意的走法为止。然后我在满意的地方落子。

初学者可能只能看一、两个轮次，而高手可以看几个甚至十几个轮次。

极大极小搜索策略，就是模拟人的这样一种思维过程。

算法描述

极大极小搜索策略

这个搜索策略是考虑双方对弈若干步以后，从可能的走法中找到一个相对较好的来落子，即在有限的搜索深度范围内进行求解。

代码语言：javascript复制

T:=(s,MAX)
把s加入到OPEN表
CLOSED表为空
LOOP1:
IF OPEN EQ ()
THEN GO LOOP2
n:=FIRST(OPEN)
并将n加入到CLOSED表
IF n可以判断输赢
THEN f(x):=INF OR -INF OR 0, GO LOOP1
ELSE EXPAND(n) to {n_i}, ADD({n_i},T)
IF d(n_i)<k
THEN ADD({n_i},OPEN), GO LOOP1
ELSE 计算f(n_i), GO LOOP1
LOOP2:
IF CLOSED EQ NIL
THEN GO LOOP3
ELSE n_p:=FIRST(CLOSED)
IF n_p in MAX AND f(n_ci) in MIN 有值
THEN f(n_p):=max{f(n_cj)}, 从CLOSED删除n_p
IF n_p in MIN AND f(n_ci) in MAX 有值
THEN f(n_p):=min{f(n_cj)}, 从CLOSED删除n_p
GO LOOP2
LOOP3:

前面的代码都是分别用两部分代码处理了极大节点和极小节点两种情况，其实，可以只用一部分代码，既处理极大节点也处理极小节点。

不同的是，前面的评估函数是针对指定的一方来给出分数的，这里的评估函数是根据当前搜索节点来给出分数的。

每个人都会选取最大的分数，然后，返回到上一层节点时，会给出分数的相反数。

代码语言：javascript复制

int AI::MINMAX_Search_With_AlphaBetaCutOff(int depth, int player) {
    int best = NEGATIVE_INFINITY;
    if (depth == this->depth) {
        return heuristic(player); 
    }
    list<Point> children; 
    for (int i = 0; i < GRID_NUM;   i)
        for (int j = 0; j < GRID_NUM;   j) {
            if (chessBoard[i][j] == NONE && nearby(i, j)) {
                children.emplace_back(Point(i, j));
            }
        }
    for (list<Point>::iterator it = children.begin(); it != children.end(); it  ) {
        setPos(*it, player);
        int val = -MINMAX_Search_With_AlphaBetaCutOff(depth   1, 1 - player); // 注意这里有个负号
        setPos(*it, NONE);
        if (val > best) {
            best = val;
            next = *it;
        }
    }
    return best;
}

MINMAX搜索的过程是把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树，然后再进行端结点静态估值和倒退值的计算，这显然会导致低效率。

事实上，如果生成某个结点A以后，马上进行静态估值，得知f(A)=-∞之后，就可以断定再生成其余结点即进行静态计算是多余的，可以马上对MIN结点赋倒推值-∞，而丝毫不会影响MAX的最好优先走步的选择。

Alpha-Beta剪枝用于裁剪搜索树中没有意义的不需要搜索的树枝，以提高运算速度。

它的基本思想是根据上一层已经得到的当前最优结果，决定目前的搜索是否要继续下去。

如果某个着法的结果小于或等于Alpha，那么它就是很差的着法，因此可以抛弃。

如果某个着法的结果大于或等于Beta，那么整个节点就作废了，因为对手不希望走到这个局面，而它有别的着法可以避免到达这个局面。因此如果我们找到的评价大于或等于Beta，就证明了这个结点是不会发生的，因此剩下的合理着法没有必要再搜索。

如果某个着法的结果大于Alpha但小于Beta，那么这个着法就是走棋一方可以考虑走的，除非以后有所变化。

代码语言：javascript复制

if  depth = 0 or node is a terminal node
    return the heuristic value of node
if  Player = MaxPlayer // 极大节点
    for each child of node // 极小节点
        alpha := max(alpha, alphabeta(child, depth-1, alpha, beta, not(Player) ))   
        if beta <= alpha // 该极大节点的值>=alpha>=beta，该极大节点后面的搜索到的值肯定会大于beta，因此不会被其上层的极小节点所选用了。对于根节点，beta为正无穷
            break                            
    return alpha
else // 极小节点
    for each child of node // 极大节点
        beta := min(beta, alphabeta(child, depth-1, alpha, beta, not(Player) ))        if beta <= alpha // 该极大节点的值<=beta<=alpha，该极小节点后面的搜索到的值肯定会小于alpha，因此不会被其上层的极大节点所选用了。对于根节点，alpha为负无穷
            break    
   return beta

启发式评估函数

如果我们有一个评估函数，可以对棋局进行评估，那么每次在我下棋的时候，我就可以用这个评估函数对棋面上所有的我可能下棋的点都进行评估，然后根据这个函数的评估值，来选择对我最有利的点落子。

一般的，在极大极小搜索中，这个评估函数可以根据势态优劣特征来定义（主要用于对端结点的“价值”进行度量），有利于程序方的势态，

f(p)

为正，有利于用户方的势态，

f(p)

为负，势均力敌的情况，

f(p)

为

，并且，若

f(p)= infin

，表示程序方赢了，若

f(p)=-infin

，表示用户方赢了。

首先明确两种特殊情况的评估值。

恒为0。

则每次落子都一定是与棋盘上棋子互为邻居的那么多棋子中最左上角的那个。

随机。

则每次落子将完全随机。

当然这样两种情况在实际操作中是不会被采用的，但是在程序编写过程中却可以用来作为调试的手段，检查函数的正确性。

同时，我们定义的评估方法，也要在这两种特殊情况下有意义。

定义两个数值，ally表示自己一方的所有棋子的评估值的和，enemy表示对手一方的所有棋子的评估值的和。

遍历棋盘，如果某位置上有棋子，则不是自己的就是对手的，那分别对自己和对手的棋子的每一个位置计算f(x)，加到评估值中，空位置不管。

代码语言：javascript复制

for (int i = 0; i < GRID_NUM; i  ) {
        for (int j = 0; j < GRID_NUM; j  ) {
            if (chessBoard[i][j] == player)
                ally  = f(Point(i, j), player);
            else if (chessBoard[i][j] == 1 - player)
                enemy  = f(Point(i, j), 1 - player);
        }
    }

对于每个位置，计算f(x)。

首先一个很明显的结论，如果我在某个位置下棋，在每一行最多影响到它左边的4个，一直到它右边的4个，加上自己，这一行就一共是9个点，更远的点不受它的影响。

同样地，对于列、对角线、反对角线，也是一样。

那么，每个点，我都可以得到4个方向上的可能被影响的点。每个方向上是9个点。

如果对这9个点做如下编码：如果这个点没有超过棋盘范围，是自己颜色就记为1，是空记为0，是对手记为-，超过棋盘的点记为#，那么就可以构建出一个长度为9的字符串。

每个点都可以构建这样4个长度为9的字符串。

例如，“111001111”表示在这9个点中，左边3个都是我的棋，中间空了2个没人下，右边4个都是我的棋。

如果下面要轮到我下棋，而我就想要下在这两个空中的某一个，显然，落子在右边这个我就赢了，而落子在左边那个，我赢不了，且下一步一定会被对手堵死。

那么很容易想到的是，对于不同的状态，应当是有不同的分数。

简单考虑，如果我在长度为9的这个字符串中找到了“111”，我就给10分，而找到了“1111”我就给20分，那么对于每个点构建的4个长度为9的字符串，我都可以通过计分的方法来给每个点一个分数。

如果把这个分数乘上这个点所在位置的重要程度，正好是可以作为这个点的评估值。

代码实现

首先给出一些术语的介绍：

成五：五颗同色棋子连在一起

image-20210331082042815

活四：有两个点可以形成五

image-20210331082104908

冲四：只有一个点能够形成五，要么是一头被对手堵住，要么是只有中间能连起来

image-20210331082113622

image-20210331082117952

image-20210331082122169

更多的状态也是类似的。

下表给出了不同状态的得分。

术语	得分
成五	5000000分
活四	100000分
冲四	10000分
单活三	8000分
跳活三	7000分
眠三	500分
活二	50分
眠二	10分

与围棋的“金角银边草肚皮”不一样，五子棋还是越往中间下，赢的机会也就越大，这也就是为什么先手落子一般落在最中间的点上。

那么，根据这个特性，我对棋盘的不同位置定义了不同的权重，即越往中间，重要程度越大。

image-20210331082224673

代码语言：javascript复制

int AI::heuristic(int player) {
    int ally = 0; // 表示自己的棋子的评估值
    int enemy = 0; // 表示对手的棋子的评估值
    // 遍历棋盘，分别对自己和对手的棋子的每一个位置计算f(x)，加到评估值中，空位置不管
    for (int i = 0; i < GRID_NUM; i  ) {
        for (int j = 0; j < GRID_NUM; j  ) {
            if (chessBoard[i][j] == player)
                ally  = f(Point(i, j), player);
            else if (chessBoard[i][j] == 1 - player)
                enemy  = f(Point(i, j), 1 - player);
        }
    }
    // 棋盘遍历完毕，至此，已经分别求出每个黑子和白子的评估值，并对应的加入到对应玩家的评估值中
    int heuristic = 10 * ally - enemy;
    return heuristic;
}

int AI::f(Point p, int color) {
    int x = p.x;
    int y = p.y;
    int score = 0; // 分数
    int weight = PosValue[p.x][p.y]; // 权重，距离中间越近，权重越高，表示越是好的地段
    // 分别构造4个方向的局面的字符串表示
    for (int dir = 0; dir < 4; dir  ) {
        string s = "";
        // 计算该方向上的起始点坐标
        int rBegin = x   DIRECTION[dir][0] * 4;
        int cBegin = y   DIRECTION[dir][1] * 4;
        // 坐标递增的方向
        int rDir = DIRECTION[dir][2];
        int cDir = DIRECTION[dir][3];
        // 计算该方向上的终止点坐标
        int rEnd = x   rDir * 4;
        int cEnd = y   cDir * 4;
        // 当行列没到终点的时候（表示没有收集齐9个点），循环
        int r = rBegin;
        int c = cBegin;
        while (r != rEnd || c != cEnd) {
            // 如果这个点没有超过棋盘范围，是自己颜色就记为1，是空记为0，是对手记为-，超过棋盘的点记为#
            if (isValid(r, c))
                if (chessBoard[r][c] == color) s  = "1";
                else if (chessBoard[r][c] == NONE) s  = "0";
                else s  = "-";
            else
                s  = "#";
            r  = rDir;
            c  = cDir;
        }
        // 如果构建出来的字符串中包含“成五”的子串，加上其分数
        if (s.find(CHENG_5_STRING) != string::npos) {
            score  = CHENG_5_SCORE;
        }
        // 如果包含“活四”的子串，加上其分数
        if (s.find(HUO_4_STRING) != string::npos) {
            score  = HUO_4_SCORE;
        }
        // “冲四”不止一种情况，如果包含任意一个子串，加上其分数，下面的情况同理
        if (s.find(CHONG_4_STRING_1_1) != string::npos
            || s.find(CHONG_4_STRING_1_2) != string::npos
            || s.find(CHONG_4_STRING_2_1) != string::npos
            || s.find(CHONG_4_STRING_2_2) != string::npos
            || s.find(CHONG_4_STRING_3) != string::npos) {
            score  = CHONG_4_SCORE;
        }
        if (s.find(DAN_HUO_3_STRING) != string::npos) {
            score  = DAN_HUO_3_SCORE;
        }
        if (s.find(TIAO_HUO_3_STRING_1_1) != string::npos
            || s.find(TIAO_HUO_3_STRING_1_2) != string::npos) {
            score  = TIAO_HUO_3_SCORE;
        }
        if (s.find(MIAN_3_1_1) != string::npos
            || s.find(MIAN_3_1_2) != string::npos
            || s.find(MIAN_3_2_1) != string::npos
            || s.find(MIAN_3_2_2) != string::npos
            || s.find(MIAN_3_3_1) != string::npos
            || s.find(MIAN_3_3_2) != string::npos
            || s.find(MIAN_3_4_1) != string::npos
            || s.find(MIAN_3_4_2) != string::npos
            || s.find(MIAN_3_5) != string::npos
            || s.find(MIAN_3_6) != string::npos) {
            score  = MIAN_3_SCORE;
        }
        if (s.find(HUO_2_STRING_1) != string::npos
            || s.find(HUO_2_STRING_2) != string::npos
            || s.find(HUO_2_STRING_3) != string::npos) {
            score  = HUO_2_SCORE;
        }
        if (s.find(MIAN_2_1_1) != string::npos
            || s.find(MIAN_2_1_2) != string::npos
            || s.find(MIAN_2_2_1) != string::npos
            || s.find(MIAN_2_2_2) != string::npos
            || s.find(MIAN_2_3_1) != string::npos
            || s.find(MIAN_2_3_2) != string::npos
            || s.find(MIAN_2_4) != string::npos) {
            score  = MIAN_2_SCORE;
        }
    }
    // 四个方向的分数都加起来，乘上权重
    return score * weight;
}

还有一些必要的说明。

第一，在互为邻居的判断标准中，我还是采用了一步以内作为邻居。

代码语言：javascript复制

bool AI::nearby(int x, int y) {
    // 检索周围的8个点，是不是有棋子
    for (int i = -1; i <= 1;   i) {
        for (int j = -1; j <= 1;   j) {
            if (i == 0 && j == 0) continue;
            if (isValid(x   i, y   j) && chessBoard[x   i][y   j] != NONE)
                return true;
        }
    }
    // 注：必要的时候，邻居的定义可以放宽到2步以内
    return false;
}

事实上，在高智能的AI中，往往会把邻居的定义放宽到两步以内，即，某个点周围的8个点和它是邻居，而那8个点的邻居也被认为是自己的邻居。

我的代码中采取了一步以内的点作为邻居，即自己周围的8个点，必要时，可以修改成两步以内。

这个地方不影响程序的正确性。

第二，启发式函数的评估值为自己的评估值减去对手的评估值。

代码语言：javascript复制