Alpha-Beta剪枝Minimax算法在井字棋AI中无法返回正确最优移动

问题描述 #

使用Alpha-Beta剪枝的Minimax算法实现井字棋AI时，给定棋盘状态：
["X", "O", 2, "X", 4, 5, "O", 7, 8]
AI玩家（"X"）的最优移动应为索引4（中心位置），但算法返回的最优移动索引为8。

代码展示 #

let humanPlayer = "O";
let aiPlayer = "X";
let origBoard = ["X", "O", 2, "X", 4, 5, "O", 7, 8];
let MAX = {index: 99, score: 1000};
let MIN = {index: 99, score: -1000}
let fc = 0;

function checkAvailableMoves(board) {
    return board.filter(s => s !== "O" && s !== "X");
}

function winning(board, player) {
    const winningCombinations = [
      [0, 1, 2],
      [3, 4, 5],
      [6, 7, 8],
      [0, 3, 6],
      [1, 4, 7],
      [2, 5, 8],
      [0, 4, 8],
      [2, 4, 6]
    ];
    return winningCombinations.some(combination =>
      combination.every(cell => board[cell] === player)
    );
}

function max(a,b) {return a.score > b.score ? a : b;}
function min(a,b) {return a.score < b.score ? a : b;}

function minimax(newBoard, depth, player, alpha, beta) {
    const availableMoves = checkAvailableMoves(newBoard);
    let theBestMove = {};
    fc++
    if (winning(newBoard, humanPlayer)) {return { score: -10 + depth }}
    else if (winning(newBoard, aiPlayer)) {return { score: 10 - depth }}
    else if (availableMoves.length === 0) {return { score: 0 }};

    if (player === aiPlayer) {
      for (let i = 0; i < availableMoves.length; i++) {
        const index = availableMoves[i];
        newBoard[index] = player;
        let result = minimax(newBoard, depth + 1, humanPlayer, alpha, beta);
        result.index = index;
        alpha = max(alpha,result)
        newBoard[index] = index;
        if (alpha.score >= beta.score) {break}
      }
      theBestMove = alpha;
    } else if (player === humanPlayer) {
      for (let i = 0; i < availableMoves.length; i++) {
        const index = availableMoves[i];
        newBoard[index] = player;
        let result = minimax(newBoard, depth + 1, aiPlayer, alpha, beta);
        result.index = index;
        beta = min(beta, result);
        newBoard[index] = index;
        if (alpha.score >= beta.score){break}
      }
      theBestMove = beta;
    }
    return theBestMove;
}

bestAIMove = minimax(origBoard,0,aiPlayer,MIN,MAX)
console.log(bestAIMove)
console.log(fc)

问题原因分析 #

1. 分数相同时的移动选择逻辑错误 #

当前的max和min函数在两个移动的分数相等时，会返回后一个比较的对象（即当前循环中的result）：

• max函数：return a.score > b.score ? a : b;，当a.score === b.score时，返回b
• min函数：return a.score < b.score ? a : b;，当a.score === b.score时，返回b

在给定棋盘状态下，所有可用移动的最终评估分数均为0（当前无即时胜负，最终会走向平局），因此循环会遍历所有可用移动，每次分数相等时alpha都会被更新为当前的result，最终保留最后一个遍历的移动索引8。

2. 未处理分数相同时的位置优先级 #

井字棋的位置价值有明确优先级：中心（4）> 角落（0、2、6、8）> 边位（1、3、5、7）。当多个移动的评估分数相同时，算法需要优先选择价值更高的位置，而非单纯依赖遍历顺序。

解决方案 #

方案1：修正max/min函数的相等情况处理 #

定义位置优先级，在分数相同时优先选择价值更高的位置：

// 定义位置优先级，数值越大优先级越高
const positionPriority = {4: 10, 0: 8, 2: 8, 6: 8, 8: 8, 1: 5, 3:5,5:5,7:5};

function max(a,b) {
    if (a.score > b.score) return a;
    if (a.score < b.score) return b;
    // 分数相同时，选择优先级更高的位置
    return positionPriority[a.index] > positionPriority[b.index] ? a : b;
}

function min(a,b) {
    if (a.score < b.score) return a;
    if (a.score > b.score) return b;
    // 人类玩家会选择对AI最不利的位置，即优先级最低的
    return positionPriority[a.index] < positionPriority[b.index] ? a : b;
}

方案2：调整可用移动的遍历顺序 #

让高优先级位置先被遍历，这样当分数相同时，alpha会保留先遍历的高优先级位置：

const positionPriority = {4: 10, 0: 8, 2: 8, 6: 8, 8: 8, 1: 5, 3:5,5:5,7:5};

function checkAvailableMoves(board) {
    return board.filter(s => s !== "O" && s !== "X")
                .sort((a,b) => positionPriority[b] - positionPriority[a]);
}

以上两种方案均可让算法优先选择中心位置（索引4）作为最优移动。

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