基于Minimax算法的井字棋无法阻止玩家获胜问题排查

我在井字棋中实现了Minimax算法，目前电脑（X）能够主动寻求获胜，但无法识别玩家（O）的获胜威胁并进行阻止，仅专注于自身获胜。例如：电脑试图拿下第一行获胜，我先占据中心位置，随后堵住第一行的获胜点，此时我只差一步即可获胜，但电脑未选择阻止，反而尝试拿下第一列。

我在评估函数evaluate中为玩家的威胁赋值，期望引导电脑识别并阻止威胁，但未达到预期效果，相关代码如下：

// 'X' => +10; 'O' => -10; 
function evaluate(board) {
    // evaluating rows;
    for (let i = 0; i < 3; i++) {
        if (
            board[i][0] == board[i][1] &&
            board[i][1] == board[i][2]
        ) {
            if (board[i][0] == AI) {
                return +10;
            } else if (board[i][0] == player) {
                return -10;
            }
        };
    };

    // evaluating columns;
    for (let j = 0; j < 3; j++) {
        if (
            board[0][j] == board[1][j] &&
            board[1][j] == board[2][j]
        ) {
            if (board[0][j] == AI) {
                return +10;
            } else if (board[0][j] == player) {
                return -10;
            }
        }
    };

    // evaluating the diagonals;
    if (
        board[0][0] == board[1][1] &&
        board[1][1] == board[2][2]
    ) {
        if (board[0][0] == AI) {
            return +10;
        } else if (board[0][0] == player) {
            return -10;
        }
    }
    if (
        board[0][2] == board[1][1] &&
        board[1][1] == board[2][0]
    ) {
        if (board[0][2] == AI) {
            return +10;
        } else if (board[0][2] == player) {
            return -10;
        }
    }

    // detecting row threats;
    for (let i = 0; i < 3; i++) {
        if (
            (board[i][0] == player && board[i][1] == player && board[i][2] == '') ||
            (board[i][0] == player && board[i][2] == player && board[i][1] == '') ||
            (board[i][1] == player && board[i][2] == player && board[i][0] == '') 
        ) { return -9; }
    };

    // detection column threats;
    for (let j = 0; j < 3; j++) {
        if (
            (board[0][j] == player && board[1][j] == player && board[2][j] == '') ||
            (board[0][j] == player && board[2][j] == player && board[1][j] == '') ||
            (board[1][j] == player && board[2][j] == player && board[0][j] == '')
        ) { return -9; }
    };

    // detecting diagonal threats;
    if ((board[0][0] == player && board[1][1] == player && board[2][2] == '') ||
        (board[0][0] == player && board[2][2] == player && board[1][1] == '') ||
        (board[1][1] == player && board[2][2] == player && board[0][0] == '')
    ) { return -9; };
    if ((board[0][2] == player && board[1][1] == player && board[2][0] == '') ||
        (board[0][2] == player && board[2][0] == player && board[1][1] == '') ||
        (board[1][1] == player && board[2][0] == player && board[0][2] == '')
    ) { return -9; }

    // if none then:
    return 0;
};

问题根源 #

评估函数存在两个核心问题：

1. 威胁检测逻辑过早返回：当前代码检测到玩家的任意一个威胁后就直接返回-9，未考虑电脑自身获胜机会的优先级，也未处理多威胁/多获胜机会的场景。Minimax算法需要递归遍历所有可能走法，当前评估函数混淆了终局评估与中间局面启发式评估的逻辑。
2. 缺失电脑自身威胁的优先级设置：仅为玩家威胁赋值，但未给电脑即将获胜的局面设置更高分值（如+9），导致电脑无法在“自己赢”和“阻止玩家赢”之间做出正确选择。

修正方案 #

1. 重构评估函数逻辑 #

先判断终局胜负，再累计启发式分值（威胁），确保优先级正确：

function evaluate(board) {
    let score = 0;

    // 终局胜负判断
    // 行判断
    for (let i = 0; i < 3; i++) {
        if (board[i][0] === board[i][1] && board[i][1] === board[i][2]) {
            if (board[i][0] === AI) return +10;
            else if (board[i][0] === player) return -10;
        }
    }
    // 列判断
    for (let j = 0; j < 3; j++) {
        if (board[0][j] === board[1][j] && board[1][j] === board[2][j]) {
            if (board[0][j] === AI) return +10;
            else if (board[0][j] === player) return -10;
        }
    }
    // 对角线判断
    if (board[0][0] === board[1][1] && board[1][1] === board[2][2]) {
        if (board[0][0] === AI) return +10;
        else if (board[0][0] === player) return -10;
    }
    if (board[0][2] === board[1][1] && board[1][1] === board[2][0]) {
        if (board[0][2] === AI) return +10;
        else if (board[0][2] === player) return -10;
    }

    // 检测电脑即将获胜的威胁
    // 行威胁
    for (let i = 0; i < 3; i++) {
        const countAI = [board[i][0], board[i][1], board[i][2]].filter(c => c === AI).length;
        const countEmpty = [board[i][0], board[i][1], board[i][2]].filter(c => c === '').length;
        if (countAI === 2 && countEmpty === 1) score += 9;
    }
    // 列威胁
    for (let j = 0; j < 3; j++) {
        const countAI = [board[0][j], board[1][j], board[2][j]].filter(c => c === AI).length;
        const countEmpty = [board[0][j], board[1][j], board[2][j]].filter(c => c === '').length;
        if (countAI === 2 && countEmpty === 1) score += 9;
    }
    // 对角线威胁
    const diag1 = [board[0][0], board[1][1], board[2][2]];
    if (diag1.filter(c => c === AI).length === 2 && diag1.filter(c => c === '').length === 1) score += 9;
    const diag2 = [board[0][2], board[1][1], board[2][0]];
    if (diag2.filter(c => c === AI).length === 2 && diag2.filter(c => c === '').length === 1) score += 9;

    // 检测玩家即将获胜的威胁（需阻止）
    // 行威胁
    for (let i = 0; i < 3; i++) {
        const countPlayer = [board[i][0], board[i][1], board[i][2]].filter(c => c === player).length;
        const countEmpty = [board[i][0], board[i][1], board[i][2]].filter(c => c === '').length;
        if (countPlayer === 2 && countEmpty === 1) score -= 9;
    }
    // 列威胁
    for (let j = 0; j < 3; j++) {
        const countPlayer = [board[0][j], board[1][j], board[2][j]].filter(c => c === player).length;
        const countEmpty = [board[0][j], board[1][j], board[2][j]].filter(c => c === '').length;
        if (countPlayer === 2 && countEmpty === 1) score -= 9;
    }
    // 对角线威胁
    if (diag1.filter(c => c === player).length === 2 && diag1.filter(c => c === '').length === 1) score -= 9;
    if (diag2.filter(c => c === player).length === 2 && diag2.filter(c => c === '').length === 1) score -= 9;

    return score;
}

2. 确认Minimax递归逻辑正确性 #

需保证Minimax函数实现正确的极大极小值选择：

• 电脑回合（MAX玩家）选择分值最高的走法
• 玩家回合（MIN玩家）选择分值最低的走法
• 递归终止条件为：终局（胜负）或棋盘已满（平局）

优先级说明 #

分值优先级从高到低为：
电脑直接获胜（+10）> 电脑即将获胜（+9）> 普通走法（0）> 阻止玩家获胜（-9）> 玩家直接获胜（-10）

修改后，电脑会优先选择自身获胜的走法，其次优先阻止玩家的获胜威胁，最后选择普通走法，解决当前无法识别玩家威胁的问题。

内容的提问来源于stack exchange，提问作者NoT_-Rxs4