井字棋Minimax算法首步不选中心反选左上角问题咨询

问题描述 #

• 实现了支持AI执x、o双方落子的井字棋Minimax算法，多数场景下可保证AI不败
• 井字棋先手开局的理论最优落子点为棋盘中心，但AI执x先手时始终优先选择左上角落子
• 待确认：该现象是算法判定左上角与中心位收益等价，还是代码存在隐藏bug

附问题代码 #

minimax函数定义：

int minimax(char board[9], bool is_maximizing, char computer)
{
    char winner = check_winner(board);
    int free_spaces = check_free_spaces(board);
    char player = computer == 'x' ? 'o' : 'x';

    if (free_spaces <= 1)
        return 0;
    else if (winner == computer)
        return 1;
    else if (winner == player)
        return -1;

    if (is_maximizing)
    {
        int best_score = INT_MIN;

        for (int i = 0; i < 9; i++)
        {
            if (board[i] == ' ')
            {
                board[i] = computer;

                int score = minimax(board, false, computer);

                board[i] = ' ';

                if (score > best_score)
                {
                    best_score = score;
                }
            }
        }

        return best_score;
    }
    else
    {
        int best_score = INT_MAX;

        for (int i = 0; i < 9; i++)
        {
            if (board[i] == ' ')
            {
                board[i] = player;

                int score = minimax(board, true, computer);

                board[i] = ' ';

                if (score < best_score)
                {
                    best_score = score;
                }
            }
        }

        return best_score;
    }
}

computer_turn函数定义：

void computer_turn(char board[9], char computer)
{
    printf("%c's turn.\n", computer);

    int best_score = INT_MIN;
    int best_pos = -1;
    int free_spaces = check_free_spaces(board);

    for (int i = 0; i < 9; i++)
    {
        if (board[i] == ' ')
        {
            if (free_spaces == 1)
            {
                best_pos = i;
            }
            else
            {
                board[i] = computer;

                int score = minimax(board, 0, 10, false, computer);

                board[i] = ' ';

                if (score > best_score)
                {
                    best_score = score;
                    best_pos = i;
                }
            }
        }
    }

    board[best_pos] = computer;
}

现象成因 #

这个现象是算法收益判定规则缺陷+代码逻辑bug共同导致的，具体如下：

1. 收益无差异化判定：当前得分规则只有三档：AI获胜返回1、AI落败返回-1、平局返回0，没有考虑获胜/落败的路径长度。井字棋在双方都走最优解的前提下，所有合法首步（中心、角、边）的最终结果都是平局，因此Minimax计算所有首步的得分都是0，算法层面认为这些位置的收益完全等价。
2. 遍历顺序导致同收益下选最先遍历到的位置：代码遍历棋盘空位是从索引0（对应左上角）到索引8顺序遍历的，且最优位置更新条件是score > best_score（只有得分严格更高才更新），因此第一个拿到最高得分（0）的左上角位置会被保留，后面同得分的中心、其他角、边位置都不会替换这个选择。
3. 隐藏的代码逻辑bug：
   • 终止判断顺序错误：先判断剩余空位≤1就直接返回0（平局），再判断胜负，会漏判最后一步落子刚好分出胜负的场景，导致终局得分计算错误。
   • 函数调用参数不匹配：定义的minimax只接收3个参数，但computer_turn里调用时传了5个参数，属于代码修改时的笔误，会直接导致编译失败。

修复方案 #

• 调整终止判断顺序：优先判断是否有获胜方，再判断是否为平局，修正终局得分计算错误。
• 给得分增加深度权重：给Minimax新增递归深度参数，每深入一层深度值+1，获胜时返回10 - depth（步数越少获胜得分越高），落败时返回depth - 10（步数越晚落败得分越高），平局返回0。这样算法会优先选择最快获胜、最慢落败的路径，首步会自然选中战略价值最高的中心位——中心位开局的容错率最高，对手一旦失误可以最快获胜，加权后得分会高于角、边位置。
• 修正computer_turn中的Minimax调用参数，和函数定义对齐；如果需要加alpha-beta剪枝优化，再对应修改函数签名即可。
• 可选优化：如果需要在同得分场景下固定优先选高价值位置，可以给中心、角、边位置加0.1量级的微小偏好权重，不影响胜负判定的前提下统一落子选择逻辑。

C语言代码精简优化建议 #

• 预存8组获胜连线的索引数组（比如int win_lines[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}}），简化胜负判断逻辑，避免重复写条件判断。
• 可以把棋盘状态、AI执子、玩家执子封装为结构体，减少递归过程中重复计算对手棋子的开销。
• 加入alpha-beta剪枝逻辑，剪掉不可能出最优解的搜索分支，进一步减少递归计算量（虽然井字棋搜索空间极小，但这是博弈类算法的标准优化手段）。
• 可以提前预存空位列表，不用每次递归都循环9个格子判断是否为空，小幅提升运行效率。

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