Solving TicTacToe with minimax algorithm in Javascript

Question

let _board = [[null, null, null], [null, null, null], [null, null, null]];
   let _flag = true;
   let _AIrowIndex = null;
   let _AIcellIndex = null;
   const _wrapper = document.querySelector(".wrapper");

   const _changeTurn = function () {
       if (_flag == true) {
           _flag = false;
           return playerOne.getSign();
       } else {
           _flag = true;
           return playerTwo.getSign();
       }
   };

   const _displayTurn = function () {
       let turn = document.querySelector(".playerInfo__turn")
       if (_flag == true) {
           turn.innerHTML = `${playerOne.getName()} is your turn`;
       } else {
           turn.innerHTML = `${playerTwo.getName()} is your turn`;
       }
   };

   
   const _evaluation = (winner) => {
           if(winner == "X"){
               return 1;
           }else if(winner == "O"){
               return -1;
           }
           else{
               return null;
           }
   };

   const _evaluationFunction = function (board) {
               /*CHECK 1 DIAG*/
           if (board[0][0] === board[1][1] && board[2][2] === board[0][0]) {
               return _evaluation(board[0][0]);
               /*CHECK 2 DIAG*/
           } 
           if (board[0][2] === board[1][1] && board[2][0] === board[0][2]) {
               return _evaluation(board[0][2]);
               /*CHECK PAIR*/
           } 
           for (let col = 0; col < 3; col++) {
               if (board[0][col] === board[1][col] && board[1][col] === board[2][col]) {
                   return _evaluation(board[0][col]);
               }
           }
           for (let row = 0; row < 3; row++) {
               if (board[row][0] === board[row][1] && board[row][1] === board[row][2]) {
                   return _evaluation(board[row][0]);
               }
           }
           return 0;        
   };

   const minimax = (_board, depth, isMaximizer) => {

       let result = _evaluationFunction(_board);
       console.log(result);
       if (result !== null) {
           return result;
       }

       if (isMaximizer) {
           let bestScore = -Infinity;

           for (let i = 0; i < 3; i++) {
               for (let j = 0; j < 3; j++) {
                   if (_board[i][j] == null) {
                       _board[i][j] = playerOne.getSign();
                       let score = minimax(_board, depth + 1, false);
                       _board[i][j] = null;
                       bestScore = Math.max(score, bestScore);
                   }
               }

           }
           return bestScore;

       } else {
           let bestScore = Infinity;

           for (let i = 0; i < 3; i++) {
               for (let j = 0; j < 3; j++) {
                   if (_board[i][j] == null) {
                       _board[i][j] = playerTwo.getSign();
                       let score = minimax(_board, depth + 1, true);
                       _board[i][j] = null;
                       bestScore = Math.min(score, bestScore);
                   }
               }
           }
           return bestScore;
       }
   };
   
   const _setAIPlay = () => {
       
       let bestScore = Infinity;
       let bestMove;

       for (let i = 0; i < 3; i++) {
           for (let j = 0; j < 3; j++) {
               if (_board[i][j] == null) {
                   _board[i][j] = playerTwo.getSign();
                   let score = minimax(_board, 0, true);       
                   _board[i][j] = null;
                   if(score < bestScore){
                       bestScore = score;
                       console.log(bestScore);
                       bestMove = {i, j}
                   }
               }
           }
       };

       _board[bestMove.i][bestMove.j] = playerTwo.getSign();
       _AIrowIndex = bestMove.i;
       _AIcellIndex = bestMove.j;
       _displayAIPlay(_AIrowIndex, _AIcellIndex);
       _changeTurn();
       _checkWinner();
   };

   


   const _displayAIPlay = (rowIndex, cellIndex) => {
       let AIcell = document.querySelector(`[data-row="${rowIndex}"][data-cell="${cellIndex}"]`);
       AIcell.textContent = playerTwo.getSign();
   }

I am trying to solve this tic-tac-toe problem with the minimax algorithm but I don't understand why it continues to place the "O" in the adjacent cell, I tried to console.log() result, and best score inside the minimax function and it looks like the recursion is working, but I don't understand why inside _setAIPlay()

if I console.log(bestScore) in the last if statement it returns me as final value or 0 or 1 and not -1 which in this case I think should be the bestscore as a minimizer.

If needed here you can find the full repo gitHub

Assertion

Answer 1

Here is a simple implementation of a minimax algorithm for Tic Tac Toe in JavaScript. The search tree deepens until a game-over state is detected. If a win is detected, then the current player cannot play, and so the static value is negative (-10). If a draw is detected the returned value is 0.

In all other cases the search deepens. This implementation uses a minimax algorithm where the value is maximised for both players. Therefore the sign of the value coming back from a deeper evaluation is always flipped ("what is good for my opponent is bad for me, and vice versa").

If a board is found to have a winning position then the moves that lead to the shortest path to a win are prioritised. This is achieved by lowering the absolute value by 1 point every time we backtrack.

If there are several moves with an equal value, then a random one will be picked from those.

Here is the implementation, with some basic HTML:

class TicTacToe {
    constructor() {
        this.board = Array(9).fill(0); // 0 means "empty"
        this.moves = [];
        this.isWin = this.isDraw = false;
    }
    get turn() { // returns 1 or 2
        return 1 + this.moves.length % 2;
    }
    get validMoves() {
        return [...this.board.keys()].filter(i => !this.board[i])
    }
    play(move) { // move is an index in this.board
        if (this.board[move] !== 0 || this.isWin) return false; // invalid move
        this.board[move] = this.turn; // 1 or 2
        this.moves.push(move);
        // Use regular expression to detect any 3-in-a-row
        this.isWin = /^(?:...)*([12])\1\1|^.?.?([12])..\2..\2|^([12])...\3...\3|^..([12]).\4.\4/.test(this.board.join(""));
        this.isDraw = !this.isWin && this.moves.length === this.board.length;
        return true;
    }
    takeBack() {
        if (this.moves.length === 0) return false; // cannot undo
        this.board[this.moves.pop()] = 0;
        this.isWin = this.isDraw = false;
        return true;
    }
    minimax() {
        if (this.isWin) return { value: -10 };
        if (this.isDraw) return { value: 0 };
        let best = { value: -Infinity };
        for (let move of this.validMoves) {
            this.play(move);
            let {value} = this.minimax();
            this.takeBack();
            // Reduce magnitude of value (so shorter paths to wins are prioritised) and negate it
            value = value ? (Math.abs(value) - 1) * Math.sign(-value) : 0;
            if (value >= best.value) {
                if (value > best.value) best = { value, moves: [] };
                best.moves.push(move); // keep track of equally valued moves
            }
        }
        return best;
    }
    goodMove() {
        let {moves} = this.minimax();
        // Pick a random move when there are choices:
        return moves[Math.floor(Math.random() * moves.length)];
    }
}

(function main() {
    const table = document.querySelector("#game");
    const btnNewGame = document.querySelector("#newgame");
    const btnCpuMove = document.querySelector("#cpumove");
    const messageArea = document.querySelector("#message");
    let game, human;

    function display() {
        game.board.forEach((cell, i) => table.rows[Math.floor(i / 3)].cells[i % 3].className = " XO"[cell]);
        messageArea.textContent = game.isWin ? (game.turn == human ? "CPU won" : "You won")
                                : game.isDraw ? "It's a draw"
                                : game.turn == human ? "Your turn" 
                                : "CPU is preparing move...";
        table.className = game.isWin || game.isDraw || game.turn !== human ? "inactive" : "";
    }

    function computerMove() {
        if (game.isWin || game.isDraw) return; 
        human = 3 - game.turn;
        display();
        setTimeout(() => {
            game.play(game.goodMove());
            display();
        }, 500); // Artificial delay before computer move is calculated and played
    }

    function humanMove(i) {
        if (game.turn !== human || !game.play(i)) return; // ignore click when not human turn, or when invalid move
        display();
        computerMove();
    }

    function newGame() {
        game = new TicTacToe();
        human = 1;
        display();
    }

    table.addEventListener("click", e => humanMove(e.target.cellIndex + 3 * e.target.parentNode.rowIndex));
    btnNewGame.addEventListener("click", newGame);
    btnCpuMove.addEventListener("click", computerMove);
    newGame();
})();

#game { border-collapse: collapse }
#game td { border: 1px solid black; width: 30px; height: 30px; text-align: center; cursor: pointer } 
#game td.X, #game td.O { cursor: default }
#game td.X { color: green }
#game td.O { color: red }
#game td.X:after { content: "X" }
#game td.O:after { content: "O" }
#game.inactive { background: silver }

<table id="game">
    <tr><td></td><td></td><td></td></tr>
    <tr><td></td><td></td><td></td></tr>
    <tr><td></td><td></td><td></td></tr>
</table>
<h4 id="message"></h4>
<button id="newgame">New Game</button>
<button id="cpumove">Let CPU play a move</button>

Momentary

Hello, could you clarify what the purpose of takeback() is for the minmax() function? Not sure what returning true or false there is doing. – Puling

takeback does what is says: it takes back the last move that was played. Its return value is not used in this algorithm, but it returns false when there is no move to take back. This will never happen in the current algorithm, as it is always called after a move was played. – Momentary