Minimax函数异常：Caro游戏Bot始终按顺序落子问题排查

问题描述 #

使用Minimax算法结合Alpha-Beta剪枝实现Caro游戏，Bot的bestMove函数始终返回0、1、2这类顺序索引，导致Bot只会逐行逐列连续落子（O代表Bot）。

相关代码 #

minimax函数 #

int game::minimax(int depth, bool maximizingPlayer, int scores[], int h, int board[][12], int alpha, int beta )
{
    
    int count = size * size;
    if (depth == h)
        return 0;

    if (maximizingPlayer)
    {
        int best = INT_MIN;

        for (int i = 0; i < 144; i++)
        {
            int row = i / 12;
            int col = i % 12;
            if (board[row][col] == 0)
            {
                board[row][col] = 1;
                count--;
                if (win()&&(count%2==1)) {
                    board[row][col] = 0;
                    return 10;
                }
                if (draw()) {
                    board[row][col] =0;
                    return 0;
                }
                best = max(best, minimax(depth + 1, !maximizingPlayer, scores, h, board, alpha, beta));
                alpha = max(alpha, best);
                board[row][col] = 0;
                if (beta <= alpha) {
                    break;
                }
            }
        }
        return best;
    }
    else
    {
        int best = INT_MAX;

        for (int i = 0; i < 144; i++)
        {
            int row = i / 12;
            int col = i % 12;
            if (board[row][col] == 0)
            {
                board[row][col] = 2;
                count--;
                if (win()&&(count % 2 == 0)) {
                    board[row][col] = 0;
                    return -10;
                }
                if (draw()) {
                    board[row][col] = 0;
                    return 0;
                }
                best = min(best, minimax(depth + 1, !maximizingPlayer, scores, h, board, alpha, beta));
                beta = min(beta, best);
                board[row][col] = 0;
                if (beta <= alpha) {
                    break;
                }
            }
        }
        return best;
    }
}

bestMove函数 #

int game::bestMove(int board[][size]) {
    int scores[1] = { 0 };
    int bestMove = -1;
    int bestValue = -1000;
    int count = size * size;
    for (int i = 0; i < size*size; i++)
    {
        int row = i / 12;
        int col = i % 12;
        if (board[row][col] == 0)
        {
            board[row][col] = 2;
            count--;
            if (win()&&(count % 2 == 0)) {
                board[row][col] = 0;
                return i;
            }
            if (draw()) {
                board[row][col] = 0;
                return i;
            }
            int moveValue = minimax(0, false, scores, 2, board, INT_MIN, INT_MAX);
            board[row][col] = 0;
            if (moveValue > bestValue)
            {
                bestValue = moveValue;
                bestMove = i;
            }
        }
    }
    return bestMove;
}

问题排查关键点 #

• count变量完全无效且逻辑错误
  无论是minimax还是bestMove里，count都被初始化为size*size（固定值），之后的count--只作用于局部变量，不会反映真实的棋盘空位数量。导致胜负判断时的count%2==1/count%2==0条件完全错误，无法正确识别当前落子玩家是否获胜。应删除这个局部变量，改为直接判断当前落子的玩家是否获胜（比如修改win()函数，传入当前落子的玩家编号，或者在落子后判断该玩家是否达成胜利条件）。

• 非终端节点估值缺失
  当depth == h时直接返回0，意味着所有未到终止状态的棋盘估值都相同。Minimax无法区分不同落子的优劣，当多个落子的估值一致时，会默认选择第一个遍历到的位置（即0、1、2...顺序）。需要实现启发式估值函数，根据棋盘上双方的潜在获胜机会（比如连子数量、空位情况）为每个非终端节点打分。

• 角色逻辑混淆
  bestMove中Bot落子为2，却调用minimax(0, false, ...)（即minimizingPlayer视角），但Bot需要寻找自身的最优解，应该以maximizingPlayer视角运行Minimax（或者调整Minimax中玩家的对应关系，确保Bot的落子对应正确的最大化/最小化角色）。角色混淆会导致估值逻辑完全错误，所有落子的moveValue相同，最终只能返回第一个遍历的位置。

• 胜负判断逻辑错误
  当前胜负判断依赖count的奇偶性，而非实际落子的玩家。正确的逻辑应该是：落子后，直接判断当前落子的玩家是否获胜（比如下了1之后判断玩家1是否赢，下了2之后判断玩家2是否赢），不需要通过count的奇偶性推导。

• Alpha-Beta剪枝的提前终止问题
  循环中当beta <= alpha时直接break，会跳过后续所有位置的评估，可能错过更优的落子位置。应改为continue而非break，只跳过当前分支的后续递归，而非整个循环。

内容的提问来源于stack exchange，提问作者HCMUSer