带Alpha-Beta剪枝的井字棋Minimax算法AI走劣招问题排查

我为井字棋（tic-tac-toe）实现了带Alpha-Beta剪枝的Minimax算法，以下是实现代码：

判断剩余可走步骤 #

bool isMovesLeft()
{
    for (int x = 0; x < ROWS; x++)
        for (int y = 0; y < COLS; y++)
            if (game.Board[x][y] == EMPTY)
                return true;

    return false;
}

棋盘状态评估函数 #

int evaluateBoard()
{
    for (int x = 0; x < ROWS; x++)
    {
        if (game.Board[x][0] == game.Board[x][1] &&
            game.Board[x][1] == game.Board[x][2])
        {
            if (game.Board[x][0] == PLAYER_X)
                return 10;
            else if (game.Board[x][0] == PLAYER_O)
                return -10;
        }
    }

    for (int y = 0; y < COLS; y++)
    {
        if (game.Board[0][y] == game.Board[1][y] &&
            game.Board[1][y] == game.Board[2][y])
        {
            if (game.Board[0][y] == PLAYER_X)
                return 10;
            else if (game.Board[0][y] == PLAYER_O)
                return -10;
        }
    }

    if (game.Board[0][0] == game.Board[1][1] &&
        game.Board[1][1] == game.Board[2][2])
    {
        if (game.Board[0][0] == PLAYER_X)
            return 10;
        else if (game.Board[0][0] == PLAYER_O)
            return -10;
    }

    if (game.Board[0][2] == game.Board[1][1] &&
        game.Board[1][1] == game.Board[2][0])
    {
        if (game.Board[0][2] == PLAYER_X)
            return 10;
        else if (game.Board[0][2] == PLAYER_O)
            return -10;
    }

    return 0;
}

带Alpha-Beta剪枝的Minimax核心算法 #

int minimax(int depth, int alpha, int beta, bool isMax)
{
    int score = evaluateBoard();

    if (score == 10)
        return 10 - depth;

    if (score == -10)
        return -10 + depth;

    if (!isMovesLeft())
        return 0;

    if (isMax)
    {
        int best = -1000;

        for (int x = 0; x < ROWS; x++)
        {
            for (int y = 0; y < COLS; y++)
            {
                if (game.Board[x][y] == EMPTY)
                {
                    game.Board[x][y] = PLAYER_X;

                    int max = minimax(depth + 1, alpha, beta, !isMax);
                    if (max > best)
                        best = max;

                    if (best > alpha)
                        alpha = best;

                    game.Board[x][y] = EMPTY;

                    if (beta <= alpha)
                        break;
                }
            }
        }

        return best;
    }
    else if (!isMax)
    {
        int best = 1000;

        for (int x = 0; x < ROWS; x++)
        {
            for (int y = 0; y < COLS; y++)
            {
                if (game.Board[x][y] == EMPTY)
                {
                    game.Board[x][y] = PLAYER_O;

                    int min = minimax(depth + 1,alpha, beta, isMax);
                    if (min < best)
                        best = min;

                    if (best < beta)
                        beta = best;

                    game.Board[x][y] = EMPTY;

                    if (beta <= alpha)
                        break;
                }
            }
        }

        return best;
    }
}

最优走法查找函数 #

BestMove findBestMove()
{
    int bestScore = -1000;

    BestMove bestMove;
    bestMove.Row = -1;
    bestMove.Col = -1;

    if (game.Board[1][1] == EMPTY)
    {
        bestMove.Row = 1;
        bestMove.Col = 1;
        return bestMove;
    }

    for (int x = 0; x < ROWS; x++)
    {
        for (int y = 0; y < COLS; y++)
        {
            if (game.Board[x][y] == EMPTY)
            {
                game.Board[x][y] = PLAYER_X;

                int score = minimax(0, -10000000000, 10000000000, false);

                game.Board[x][y] = EMPTY;

                if (score > bestScore)
                {
                    bestScore = score;
                    bestMove.Row = x;
                    bestMove.Col = y;
                }
            }
        }
    }

    return bestMove;
}

我还在minimax函数的评分计算中加入了深度参数，以提升AI的智能程度。但该AI仍会走出拙劣的招式，极易被击败，且获胜方式重复出现。请问上述代码是否存在问题，或是我遗漏了什么关键内容？

问题分析与修正方案 #

你的代码存在几个关键逻辑错误，导致AI无法正确执行Minimax算法：

1. Min玩家递归参数错误
   在minimax函数的!isMax分支中，调用递归时传入的参数是isMax，而非!isMax。这会导致递归链无法正确切换Max/Min玩家角色，AI无法模拟对手的最优走法。
   修正代码：

// 原错误代码
int min = minimax(depth + 1,alpha, beta, isMax);
// 修正后
int min = minimax(depth + 1, alpha, beta, !isMax);

2. 对手获胜的评分逻辑错误
   当对手（PLAYER_O）获胜时，你返回-10 + depth，这意味着对手赢的越晚，AI得到的分数越高。但正确逻辑应该是：对手赢的越早，对AI（PLAYER_X）来说结果越差，因此应返回-10 - depth，让AI优先避免更早失败的局面。
   修正代码：

// 原错误代码
if (score == -10)
    return -10 + depth;
// 修正后
if (score == -10)
    return -10 - depth;

3. 硬编码中心走法的逻辑缺陷
   findBestMove中直接判断中心为空就返回，忽略了当前局面的紧急情况（比如AI即将获胜或需要阻止对手获胜）。硬编码走法会覆盖Minimax的最优决策，导致AI在关键局面犯错。应移除这段硬编码逻辑，让Minimax自行评估所有可能走法。
   修正代码：

// 移除以下硬编码逻辑
if (game.Board[1][1] == EMPTY)
{
    bestMove.Row = 1;
    bestMove.Col = 1;
    return bestMove;
}

4. Alpha-Beta剪枝的循环终止不彻底
   当触发剪枝条件beta <= alpha时，仅break了内层的y循环，外层x循环仍会继续执行，导致剪枝效率低下（虽不影响正确性，但会浪费计算资源）。可以通过标志位优化，比如：

if (isMax)
{
    int best = -1000;
    bool prune = false;
    for (int x = 0; x < ROWS && !prune; x++)
    {
        for (int y = 0; y < COLS; y++)
        {
            // ... 原有逻辑 ...
            if (beta <= alpha)
            {
                prune = true;
                break;
            }
        }
    }
    return best;
}

额外优化建议 #

• 确保PLAYER_X和PLAYER_O的定义正确，避免角色混淆；
• 在findBestMove中，若多个走法分数相同，可以随机选择一个，避免AI获胜方式重复；
• 检查ROWS和COLS是否都定义为3，确保棋盘是标准3x3井字棋。

修正上述问题后，AI应该能正确执行Minimax算法，实现最优走法，不会轻易被击败。

内容的提问来源于stack exchange，提问作者Ivan-Mark Debono