如何修改井字棋minimax算法将搜索深度限制为3

问题原因 #

• 胜负判断逻辑被错误注释：修改后的minimax函数中注释掉了胜负检查代码，搜索过程中即使出现已分胜负的局面，也不会提前终止搜索返回对应得分，算法无法识别必胜/必败局面。
• 深度参数传递错误：递归调用时使用了depth++（后置自增），实际传递给下一层递归的深度值还是当前的depth，自增仅对当前函数生效，深度完全不会叠加，搜索限制相当于没有生效。
• 深度终止条件位置与逻辑错误：深度判断放在了所有子节点遍历完成之后，且判断条件仅为depth == 3，既没有在达到深度上限时立即停止递归，也没有针对深度上限场景设计对应逻辑，深度限制完全没有起到截断搜索树的作用。
• 缺少深度上限场景的评估函数：搜索到深度3时，没有对当前未分胜负的棋盘做得分评估，直接返回遍历子节点得到的score，导致所有走法的得分没有区分度，算法会默认选择第一个遍历到的合法空位落子，就是你观察到的“只会落子到下一个空单元格”的现象。
• 初始调用缺少深度参数：修改了minimax函数的参数列表增加了depth，但computerMove函数中调用minimax的时候没有传入初始深度值，参数不匹配会导致运行异常。

修复后的核心代码示例 #

// 启发式评估函数：深度到达上限时评估当前棋盘得分，范围[-1,1]
int evaluate(int board[9]) {
    int winner = win(board);
    if (winner != 0) return winner;
    // 未分胜负时可根据己方/对方的连子数计算得分，以下为简化实现
    return 0;
}

int minimax(int board[9], int player, int depth) {
    // 先判断终止条件：出现胜负、平局、到达深度上限
    int winner = win(board);
    if (winner != 0) return winner * player;
    if (depth == 3) return evaluate(board) * player; // 到达深度限制，返回评估得分
    
    int move = -1;
    int score = -2;
    int i;
    for(i = 0; i < 9; ++i) {
        if(board[i] == 0) {
            board[i] = player;
            // 传递depth+1给下一层递归
            int thisScore = -minimax(board, player*-1, depth + 1);
            if(thisScore > score) {
                score = thisScore;
                move = i;
            }
            board[i] = 0;
        }
    }
    if(move == -1) return 0; // 平局返回0
    return score;
}

void computerMove(int board[9]) {
    int move = -1;
    int score = -2;
    int i;
    for(i = 0; i < 9; ++i) {
        if(board[i] == 0) {
            board[i] = 1;
            // 初始调用传入深度0
            int tempScore = -minimax(board, -1, 0);
            board[i] = 0;
            if(tempScore > score) {
                score = tempScore;
                move = i;
            }
        }
    }
    board[move] = 1;
}

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