Search code examples
javascripttic-tac-toeminimax

Why does my tic tac toe minimax algorithm not block certain diagonal moves?


I've almost completed the logic for my tic tac toe minimax and its working quite well. But i'm still finding a few diagonal moves where the AI is seemingly getting it wrong. For example if you play square 3,6,5 and 7 you will win. It doesn't block the bottom corner for some reason.

Here's the minimax call recursively getting the best score that our computer can make:

          let compMove;
          let bestScore = -Infinity;
          for (let i = 0; i < 9; i++) {
            if (gameBoard.array[i] == '') {
              gameBoard.array[i] = 'X';
              let score = minimax(gameBoard.array, 0, true);
              gameBoard.array[i] = '';
              if (score > bestScore) {
                bestScore = score;
                compMove = i;
              }
            }
          }

Here is the actual minimax function itself:

          let scores = {
            X: 10,
            O: -10,
            tie: 0
          }
          
          const minimax = (board, depth, maximizingPlayer) => {
            let result = checkWinner(gameBoard.currentPlayer);
            
            if (result !== null) {
              return scores[result];
            }
            
            if (maximizingPlayer) {
              let bestScore = -Infinity;
              for (let i = 0; i < 9; i++) {
              
                if (board[i] == '') {
                  board[i] = 'O';
                  let score = minimax(board, depth + 1, true);
                  board[i] = '';
                  if (score > bestScore) {
                    bestScore = score;
                  }
                }
              }
              return bestScore;

            } else {
                let bestScore = Infinity;
                for (let i = 0; i < 9; i++) {
                  if (board[i] == '') {
                    board[i] = 'X';
                    let score = minimax(board, depth + 1, false);
                    board[i] = '';
                    if (score < bestScore) {
                      bestScore = score;
                    }
                  }
                }
    
                return bestScore;
            }
          }

If anything sticks out to anyone I'd greatly appreciate it. I'm stumped!

If you'd like to test the current state of the game here's the codepen:

https://codepen.io/itswakana/pen/gOeMrym?editors=1111


Solution

  • There are these issues:

    • As the "computer" plays with "O" the code where you set compMove should not move with "X", but move with "O". So the first code block you have in your post should be:

            let compMove;
            let bestScore = Infinity; // <-- to minimize (positive)
            for (let i = 0; i < 9; i++) {
              if (gameBoard.array[i] == '') {
                gameBoard.array[i] = 'O'; // <-- not X
                let score = minimax(gameBoard.array, 0, true);
                gameBoard.array[i] = '';
                if (score < bestScore) { // <-- minimize
                  bestScore = score;
                  compMove = i;
                }
              }
            }
      
      
    • checkWinner(gameBoard.currentPlayer) is always checking a win for the same player, as gameBoard.currentPlayer is not altered during the minimax search. So this will miss wins for the opponent. I would in fact leave gameBoard.currentPlayer alone, and pass an argument that is based on the maximizingPlayer argument:

      let result = checkWinner("XO"[+maximizingPlayer]); // dynamically determine player
      
    • You always pass the current value of maximizingPlayer to the recursive call. When it is false, you pass false, and when it is true, you pass true. This means it never toggles (see next point).

    • When maximizing the score, your code lets "O" make moves, but that is the minimizing player. So that needs to be switched.

           const minimax = (board, depth, maximizingPlayer) => {
              let result = checkWinner("XO"[+maximizingPlayer]); // <--
      
              if (result !== null) {
                return scores[result];
              }
      
              let bestMove;
              if (maximizingPlayer) {
                let bestScore = -Infinity;
                for (let i = 0; i < 9; i++) {
      
                  if (board[i] == '') {
                    board[i] = 'X'; // <--
                    let score = minimax(board, depth + 1, false); // <--
                    board[i] = '';
                    if (score > bestScore) {
                      bestMove = i;
                      bestScore = score;
                    }
                  }
                }
                return bestScore;
      
              } else {
                  let bestScore = Infinity;
                  for (let i = 0; i < 9; i++) {
                    if (board[i] == '') {
                      board[i] = 'O'; // <--
                      let score = minimax(board, depth + 1, true); // <--
                      board[i] = '';
                      if (score < bestScore) {
                        bestMove = i;
                        bestScore = score;
                      }
                    }
                  }
      
                  return bestScore;
              }
            }
      

    With those changes it will work.

    Final remark: it is a pity that in your code you have at least three concepts that correspond to the notion of "player": maximizingPlayer is a boolean, Player is an object with a team member, currentPlayer is a character property, and the player argument is the character too. This should be harmonised. Certainly the currentPlayer property serves hardly any purpose. It is just set here and there to a hard-coded "X" or "O" and then immediately passed as argument.