javascript - 为什么我的 minimax 算法不阻止我的 Action ？

Question

这是我的Tic-Tac-Toe 算法的 Javascript 代码:

function minimax(newGrid, depth, Player){

//debugger

const gameState = checkWin(newGrid,true);

if (gameState == false){
    values = [];

    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            const boardCopy = _.cloneDeep(newGrid);
            if (boardCopy[i][j] !== '') continue;
            boardCopy[i][j] = Player;
            console.log(boardCopy);
            const value = minimax(boardCopy, depth + 1, (Player === PLYR_TOKEN) ? COMP_TOKEN : PLYR_TOKEN);
            values.push({
                cost: value,
                cell: {
                    i: i,
                    j: j
                } 
            });
        }
    }

    //debugger

    if (Player === COMP_TOKEN){
        const max = _.maxBy(values, (v) => {
            return v.cost;
        });
        if( depth === 0 ){
            return max.cell;
        } else {
            return max.cost;
        }
    }else{
            const min = _.minBy(values, (v) => {
            return v.cost;
        });
        if( depth === 0 ){
            return min.cell;
        } else {
            return min.cost;
        }

    }
} else if (gameState === null){
    return 0;
} else if (gameState === PLYR_TOKEN){
    return depth - 10;
} else if (gameState === COMP_TOKEN){
    return 10 - depth;
   }
}

---

这个“算法”、“代码”的问题很简单:它不会阻止我的 Action 让我们想象一下这个场景:

X->播放器 O->MM算法

X - O
- X -
- - -

正常情况下，一个完美的 MiniMax 算法应该采取这个选择来阻止我获胜(小写 o 是新的着法):

X - O
- X -
- - o

问题是我的代码执行了这个(小写 o 是新 Action ):

X - O
- X o
- - -

为什么？我不知道，但我认为它需要任何机会才能获胜，忽略我的 Action ，忽略我离获胜只有一步之遥的事实。 老实说，我真的不明白这个算法是如何工作的。

其他信息:主板是一个二维数组，minimax函数的结果是一个对象，有两个属性(i,j)表示主板上的坐标。

const board = [
['','',''],
['','',''],
['','','']
];

Answer 1

所以，如有疑问，请发表评论!我一步一步地做，当我被卡住时没有停下来，而是在每次我理解更多的时候拖延和来回。

//newGrid : the board
//depth : keep track of the "guessing level"
//Player : keep track of who's turn it would be
function minimax(newGrid, depth, Player){

//checking if the game ended
const gameState = checkWin(newGrid,true);

//if not
if (gameState == false){
    values = [];
    //for each cell in the grid
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            //we make a deep copy of the board
            const boardCopy = _.cloneDeep(newGrid);
            //if the cell isn't empty, we jump to the next one
            if (boardCopy[i][j] !== '') continue;
            //here we assign the Player to the cell (simulating a move from this player to this cell)
            boardCopy[i][j] = Player;
            //debugging
            console.log(boardCopy);
            //here go some recursivity, so we're putting our deepcopy with the simulated move, adding a depth level, and switching player
            const value = minimax(boardCopy, depth + 1, (Player === PLYR_TOKEN) ? COMP_TOKEN : PLYR_TOKEN);
            //since it was a recursive thing, please do imagine we get here at max depth BEFORE lesser depths, and then we'll climb back when each depth return its value to the previous one
            //so here the first "value" going in "values" will be the first cell where we did not go through "if (gameState == false){" : first cell where the game ended (with its associated cost, more on that later)
            values.push({
                cost: value,
                cell: {
                    i: i,
                    j: j
                } 
            });
        }
    }

    //when the loop ended
    //if we're simulating a computer turn
    if (Player === COMP_TOKEN){
        //getting the "value" with max cost out of "values"
        const max = _.maxBy(values, (v) => {
            return v.cost;
        });
        //if we endend our recursivity (we climbed all the way back to depth 0) == we are on the actual grid with no simulation
        if( depth === 0 ){
            return max.cell; //return the cell (computer will play this cell)
        } else {
            return max.cost; //else return the cost (to put in the "values" list)
        }
    }else{ //if we're simulating a player turn, same thing but with the min
        const min = _.minBy(values, (v) => {
            return v.cost;
        });
        if( depth === 0 ){ //may not be useful if you always call minimax at depth 0 on computer turn
            return min.cell;
        } else {
            return min.cost;
        }

    }
} else if (gameState === null){ //so, here we're simulating our endgame, a draw have a value of 0
    return 0;
} else if (gameState === PLYR_TOKEN){ //a player win have a value of "depth-10" (the quicker he win, the lesser the result)
    return depth - 10;
} else if (gameState === COMP_TOKEN){ //a computer win have a value of "10-depth" (the quicker he win, the greater the result)
    return 10 - depth;
   }
}

完成后，我们就可以更好地理解代码的工作原理，以及为什么它不能像预期的那样工作。 实际上，在计算机回合中，它只会检查最快获胜的步骤。我不是 100% 确定我的解决方案，但是您可以尝试以这种方式修复它:

    if (Player === COMP_TOKEN){
        //[...]
        //if we endend our recursivity (we climbed all the way back to depth 0) == we are on the actual grid with no simulation
        if( depth === 0 ){
            const min = _.minBy(values, (v) => {
                return v.cost;
            });
            if(min.cost>=-9)return min.cell; //if player win in the next turn, prevent it instead
            else return max.cell; //else return the best cell for computer
        }
        //[...]

它远非完美(例如，您可以让他以 2 步获胜)并且还没有经过测试，但我希望您现在更清楚了。 当你完成你的代码并且它像你想要的那样工作时，请不要犹豫，将它发布到 codereview.stackexchange 上以获得优化建议。