Why my minimax algorithm dosen't block my moves?

Question

This is the Javascript code for my Tic-Tac-Toe algorithm:

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;
   }
}

---

The problem with this "algorithm", "code" is simple: it doesn't block my moves Let's image this scenario:

X-> player O-> MM algorithm

X - O
- X -
- - -

Normal, a perfect MiniMax algorithm should take this choice to block me from winning (lower case o is the new move):

X - O
- X -
- - o

The problem is that my code dose this (lower case o is the new move):

X - O
- X o
- - -

Why? I dont know, but I think it take's any chance it has to win, ignoring my moves, ignoring the fact that I'm one move away from winning. To be honest with you, I don't really understand how this algorithm work's.

Other info: The main board is an two dimensional array and the result of the minimax function is an object with two proprieties (i,j) that represent coordinates on the main board.

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

Answer 1

So, when in doubt, comment ! I did it step by step, not stopping when I was stuck but delaying and going back and forth each time I understood something more.

//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;
   }
}

With that done, we have a better understanding on how the code work, and why it doesn't work like it's supposed to. Indeed, on computer turn, it only check for what's the quickest move to win. I'm not 100% sure of my solution, but you could for example try to fix it that way :

    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
        }
        //[...]

It's far from perfect (you could get him with a 2-move win for example) and it's not tested, but I hope it's clearer for you now. When you're done with your code and it's working like you want, don't hesitate to post it on codereview.stackexchange to get optimisation advices.