Search code examples
javascriptarraysrecursiontic-tac-toeminimax

Tic-Tac-Toe with minimax can be beaten in middle row or middle column. How to fix it so it becomes unbeatable?


As part of a course, I tried to implement minimax in a game of Tic-Tac-Toe in which the human player plays first (marker 'X', adds 1 to array) and the computer plays second (marker 'O', adds -1 to array). The minimax sort of works, in the sense that I cannot win the game except if I play middle row or middle column.

let main = (function() {
  let currentPlayer;
  let gameOver = false;
  let boardArray = Gameboard();
  const dialogElement = document.querySelector('[data-modal]');
  const gameContainer = document.querySelector('[data-game-container]');

  // gameboard array
  function Gameboard() {
    const board = [];
    const columns = 3;
    const rows = 3;
    // create a 2d array and populate it with 0s
    for (let i = 0; i < rows; i++) {
      board[i] = [];
      for (let j = 0; j < columns; j++) {
        board[i][j] = 0;
      }
    }
    return board;
  }
  //let boardArray = Gameboard();

  const gameController = function(param) {
    // defining and initializing variables
    // the unary plus operator turns the string into an integer
    const gameChoice = +param.choice;
    const player1 = Players(param.playerX, 1);
    const player2 = Players(param.playerO, -1);
    const board = boardArray;
    let gameboardCells = document.querySelectorAll('.board-cell');
    currentPlayer = player1.marker;
    // click and game logic for 2 player game
    if (gameChoice === 0) {
      gameboardCells.forEach(cell => {
        cell.addEventListener('click', (event) => {
          const index = event.target.dataset.index;
          let arrayColumn = index % 3;
          let arrayRow = (index - arrayColumn) / 3;
          // add the marker of the current player in the array
          if (board[arrayRow][arrayColumn] === 0 && gameOver === false) {
            board[arrayRow][arrayColumn] = currentPlayer;
            currentPlayer = currentPlayer === player1.marker ? player2.marker : player1.marker;
            announceTurn(currentPlayer);
          } else {
            return
          }
          renderUI.addMarker(board);
          checkWinningCombinations(board);
        });
      });
    } else if (gameChoice === 1) {
      playEasyAI(gameChoice, player1, board, gameboardCells);
    } else if (gameChoice === 2) {
      playUnbeatableAI(gameChoice, player1, board, gameboardCells)
    }
  }

  function playEasyAI(choice, player, array, cells) {
    board = array;
    gameboardCells = cells;
    player = 1;
    // player vs. easy AI game
    // human clicks + computer pushes in random available cell
    // get available cells
    gameboardCells.forEach(cell => {
      cell.addEventListener('click', (event) => {
        const index = event.target.dataset.index;
        let arrayColumn = index % 3;
        let arrayRow = (index - arrayColumn) / 3;
        if (board[arrayRow][arrayColumn] === 0 && gameOver === false) {
          board[arrayRow][arrayColumn] = player;
        } else {
          return
        }
        // checkWinningCombinations(board) to see if human player wins
        // so that computer does not play after human won
        checkWinningCombinations(board);
        // get available cells
        const availableCells = [];
        for (let row = 0; row < board.length; row++) {
          for (let col = 0; col < board[row].length; col++) {
            if (board[row][col] === 0) {
              availableCells.push({
                row,
                col
              });
            }
          }
        }
        if (availableCells.length > 0 && gameOver === false) {
          randomIndex = Math.floor(Math.random() * availableCells.length);
          const easyAiMove = availableCells[randomIndex];
          board[easyAiMove.row][easyAiMove.col] = -1;
        }
        renderUI.addMarker(board);
        checkWinningCombinations(board);
      });
    });
  }

  function playUnbeatableAI(choice, player, array, cells) {
    board = array;
    gameboardCells = cells;
    player = 1;
    // player vs. easy AI game
    // human clicks + computer pushes in random available cell
    // get available cells
    gameboardCells.forEach(cell => {
      cell.addEventListener('click', (event) => {
        const index = event.target.dataset.index;
        let arrayColumn = index % 3;
        let arrayRow = (index - arrayColumn) / 3;
        if (board[arrayRow][arrayColumn] === 0 && gameOver === false) {
          board[arrayRow][arrayColumn] = player;
          renderUI.addMarker(board);
          checkWinningCombinations(board);
          const aiMove = getBestMove(board);
          console.log(aiMove);
          board[aiMove.row][aiMove.col] = -1; // Set the AI move on the board
        } else {
          return
        }
        renderUI.addMarker(board);
        checkWinningCombinations(board);
      });
    });
  }

  function minimax(board, depth, isMaximizing) {
    // Evaluate the board and return a score if the game is over
    const result = evaluate(board);
    const HUMAN_PLAYER = 1;
    const AI_PLAYER = -1;
    if (result !== 0) {
      return result;
    }
    // If it's the AI's turn (maximizing player)
    if (isMaximizing) {
      let bestScore = -Infinity;
      for (let row = 0; row < 3; row++) {
        for (let col = 0; col < 3; col++) {
          // If the cell is empty
          if (board[row][col] === 0) {
            board[row][col] = HUMAN_PLAYER;
            const score = minimax(board, depth + 1, false);
            board[row][col] = 0; // Undo the move
            bestScore = Math.max(score, bestScore);
          }
        }
      }
      return bestScore;
    } else {
      // If it's the human's turn (minimizing player)
      let bestScore = Infinity;
      for (let row = 0; row < 3; row++) {
        for (let col = 0; col < 3; col++) {
          // If the cell is empty
          if (board[row][col] === 0) {
            board[row][col] = AI_PLAYER;
            const score = minimax(board, depth + 1, true);
            board[row][col] = 0; // Undo the move
            bestScore = Math.min(score, bestScore);
          }
        }
      }
      return bestScore;
    }
  }

  function getBestMove(board) {
    let bestMove = {
      row: -1,
      col: -1
    };
    let bestScore = -Infinity;
    const HUMAN_PLAYER = 1;
    const AI_PLAYER = -1;
    for (let row = 0; row < 3; row++) {
      for (let col = 0; col < 3; col++) {
        if (board[row][col] === 0 && gameOver === false) {
          board[row][col] = AI_PLAYER;
          const score = minimax(board, 0, true);
          board[row][col] = 0; // Undo the move

          if (score > bestScore) {
            bestScore = score;
            bestMove = {
              row,
              col
            };
          }
        }
      }
    }
    return bestMove;
  }

  function evaluate(board) {
    for (let row = 0; row < 3; row++) {
      if (board[row][0] === board[row][1] && board[row][1] === board[row][2]) {
        if (board[row][0] === 1)
          return -10;
        else if (board[row][0] === -1)
          return +10;
      }
    }
    for (let col = 0; col < 3; col++) {
      if (board[0][col] === board[1][col] && board[1][col] === board[2][col]) {
        if (board[0][col] === 1)
          return -10;
        else if (board[0][col] === -1)
          return +10;
      }
    }
    if (board[0][0] === board[1][1] && board[1][1] === board[2][2]) {
      if (board[0][0] === 1)
        return -10;
      else if (board[0][0] === -1)
        return +10;
    }
    if (board[0][2] === board[1][1] && board[1][1] === board[2][0]) {
      if (board[0][2] === 1)
        return -10;
      else if (board[0][2] === -1)
        return +10;
    }
    return 0;
  }


  const checkWinningCombinations = function(array) {
    const board = array;
    for (let i = 0; i < 3; i++) {
      // check rows and columns for a winner
      const rowSum = board[i][0] + board[i][1] + board[i][2];
      const colSum = board[0][i] + board[1][i] + board[2][i];
      if (colSum === 3 || rowSum === 3) {
        endGame(1);
        return -10;
      } else if (colSum === -3 || rowSum === -3) {
        endGame(-1);
        return +10;
      }
    }
    // check diagonals for a winner
    const diagonalSum1 = board[0][0] + board[1][1] + board[2][2];
    const diagonalSum2 = board[0][2] + board[1][1] + board[2][0];
    if (diagonalSum1 === 3 || diagonalSum2 === 3) {
      endGame(1);
      return -10;
    } else if (diagonalSum1 === -3 || diagonalSum2 === -3) {
      endGame(-1);
      return +10;
    }
    // check for tie game
    if (board[0].indexOf(0) === -1 && board[1].indexOf(0) === -1 && board[2].indexOf(0) === -1) {
      endGame(0);
      return 0;
    }
  }

  const endGame = function(winner) {
    gameOver = true;
    announceWinner(winner);
  }

  const announceWinner = function(player) {
    const announcementBox = document.querySelector('[data-game-announcement]');
    const player1 = document.querySelector('[data-player-x]').value;
    const player2 = document.querySelector('[data-player-o]').value;
    if (player === 1) {
      announcementBox.innerText = `${player1} won!`;
    } else if (player === -1) {
      announcementBox.innerText = `${player2} won!`;
    } else if (player === 0) {
      announcementBox.innerText = 'It\'s a tie';
    }
  }

  const announceTurn = function(player) {
    const announcementBox = document.querySelector('[data-game-announcement]');
    const player1 = document.querySelector('[data-player-x]');
    const player2 = document.querySelector('[data-player-o]');
    if (player === 1) {
      player = player1.value;
    } else if (player === -1) {
      player = player2.value;
    }
    announcementBox.innerText = `It's ${player}'s turn`;
  }

  const initialPlayerAnnouncement = function() {
    const announcementBox = document.querySelector('[data-game-announcement]');
    const player1 = document.querySelector('[data-player-x]').value;
    announcementBox.innerText = `It's ${player1}'s turn`;
  }

  const clickReplay = function() {
    const board = boardArray;
    const cells = document.querySelectorAll('.board-cell');
    const announcementBox = document.querySelector('[data-game-announcement]');
    const player1 = document.querySelector('[data-player-x]').value;
    let gameboardCells = document.querySelectorAll('.board-cell');
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        board[i][j] = 0;
      }
    }
    cells.forEach(cell => {
      cell.classList.remove('x', 'circle');
    });
    gameOver = false;
    currentPlayer = 1;
    announcementBox.innerText = `It's ${player1}'s turn`;
  }

  const clickReset = function() {
    const board = boardArray;
    const cells = document.querySelectorAll('.board-cell');
    const announcementBox = document.querySelector('[data-game-announcement]');
    let gameboardCells = document.querySelectorAll('.board-cell');
    const form = document.querySelector('[data-add-names-form]');
    const boardContainer = document.querySelector('[data-board-container]');
    const player0 = document.querySelector('[data-player-o]');
    const dialogElement = document.querySelector('[data-modal]');
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        board[i][j] = 0;
      }
    }
    cells.forEach(cell => {
      cell.classList.remove('x', 'circle');
    });
    gameOver = false;
    gameContainer.classList.add('hidden');
    form.reset();
    announcementBox.innerText = '';
    boardContainer.innerHTML = '';
    player0.disabled = false;
    dialogElement.showModal();
  }

  const openModal = function() {
    dialogElement.showModal()
  }

  return {
    board: Gameboard,
    gameController: gameController,
    initialPlayerAnnouncement: initialPlayerAnnouncement,
    clickReplay: clickReplay,
    clickReset: clickReset,
    openModal: openModal
  }
})();
main.openModal();

/**
 * displays the board on form submit
 * adds CSS classes matching 2d array elements
 */
let renderUI = (function() {
  // displays the gameboard on form submit
  const displayGameboard = function() {
    const board = main.board();
    const boardContainer = document.querySelector('[data-board-container]');
    // create and append board cells
    board.forEach((row, rowIndex) => {
      row.forEach((cell, columnIndex) => {
        // create a 'div' for each array element, add a CSS class, and a data-index value
        const boardCell = document.createElement('div');
        boardCell.classList.add('board-cell');
        const index = rowIndex * 3 + columnIndex; // *3 comes from the number of columns
        boardCell.dataset.index = index;
        boardContainer.appendChild(boardCell);
      })
    })
  }

  // adds CSS classes matching array element
  function addMarker(array) {
    const board = array;
    const cells = document.querySelectorAll('.board-cell');
    for (let row = 0; row < 3; row++) {
      for (let col = 0; col < 3; col++) {
        if (board[row][col] === 1) {
          cells[row * 3 + col].classList.add('x');
        } else if (board[row][col] === -1) {
          cells[row * 3 + col].classList.add('circle');
        }
      }
    }
  }

  return {
    displayGameboard: displayGameboard,
    addMarker: addMarker
  }
})();

/**
 * Players factory function
 */
const Players = (name, marker) => {
  return {
    name,
    marker
  }
}

(function clickSubmit() {
  const form = document.querySelector('[data-add-names-form]');
  form.addEventListener('submit', returnFormInput);
})();

function returnFormInput(event) {
  event.preventDefault();
  const formData = new FormData(this);
  const data = Object.fromEntries(formData);
  const dialogElement = document.querySelector('[data-modal]');
  const gameContainer = document.querySelector('[data-game-container]');
  dialogElement.close();
  gameContainer.classList.remove('hidden');
  // displayGameboard hass to be before gameController
  // because gameController needs to select already rendered cells
  renderUI.displayGameboard();
  main.initialPlayerAnnouncement();
  main.gameController(data);
}

(function replayGame() {
  // reset: board, CSS classes, text field, currentPlayer, gameOver
  const replayButton = document.querySelector('[data-replay-game]');
  replayButton.addEventListener('click', main.clickReplay);
})();

(function resetGame() {
  const resetButton = document.querySelector('[data-reset-game]')
  resetButton.addEventListener('click', main.clickReset);
})();

(function clickTwoPlayerGame() {
  const radioButton = document.getElementById('pvp');
  const xInput = document.querySelector('[data-player-x]');
  const oInput = document.querySelector('[data-player-o]');
  radioButton.addEventListener('click', () => {
    xInput.value = '';
    oInput.value = '';
    oInput.disabled = false;
  });
})();

(function clickPlayerEasyAI() {
  const radioButton = document.getElementById('easyai');
  const xInput = document.querySelector('[data-player-x]');
  const oInput = document.querySelector('[data-player-o]');
  radioButton.addEventListener('click', () => {
    xInput.value = '';
    oInput.value = 'EasyAI';
    oInput.disabled = true;
  });
})();

(function clickPlayerToughAI() {
  const radioButton = document.getElementById('unbeatableai');
  const xInput = document.querySelector('[data-player-x]');
  const oInput = document.querySelector('[data-player-o]');
  radioButton.addEventListener('click', () => {
    xInput.value = '';
    oInput.value = 'ToughAI';
    oInput.disabled = true;
  });
})();
:root {
  --cell-size: 100px;
  --mark-size: calc(var(--cell-size)* 0.9);
  --pantone-honeysuckle: rgb(203, 101, 134);
  --pantone-classic-blue: rgb(16, 76, 129);
  --pantone-rose-quartz: #f7cac9;
  --pantone-serenity: #92a8d1;
}

html {
  font-size: calc(16px + (26 - 16) * ((100vw - 300px) / (2800 - 300)));
  font-family: Roboto, Arial, sans-serif;
}

body {
  display: flex;
  align-items: center;
  justify-content: center;
  background-color: var(--pantone-rose-quartz);
  padding-top: 25vh;
}


/* modal */

.modal {
  border: none;
  box-shadow: 0 0 #0000, 0 0 #0000, 0 25px 50px -12px rgba(0, 0, 0, 0.25);
  background-color: var(--pantone-serenity);
}

input[type="radio"],
input[type="radio"]:checked {
  accent-color: var(--pantone-rose-quartz);
}

.submit-form-button {
  background-color: var(--pantone-rose-quartz);
  padding: 10px;
}


/* game container */

.game-container {
  display: flex;
  flex-direction: column;
  gap: 20px;
}


/* announcement area */

.game-announcement {
  font-size: 2rem;
}


/* board container */

.board-container {
  display: grid;
  gap: 10px;
  grid-template-columns: repeat(3, 1fr);
}

.board-cell {
  background-color: var(--pantone-serenity);
  height: var(--cell-size);
  width: var(--cell-size);
  display: flex;
  justify-content: center;
  align-items: center;
  position: relative;
}


/* creating the X element */

.board-cell.x::before,
.board-cell.x::after {
  content: '';
  width: calc(var(--mark-size) * 0.15);
  height: var(--mark-size);
  background-color: black;
  position: absolute;
}

.board-cell.x::before {
  transform: rotate(45deg);
}

.board-cell.x::after {
  transform: rotate(-45deg);
}


/* creating the 0 element */

.board-cell.circle::before,
.board-cell.circle::after {
  content: '';
  background-color: black;
  position: absolute;
  border-radius: 50%;
}

.board-cell.circle::before {
  width: var(--mark-size);
  height: var(--mark-size);
  background-color: black;
}

.board-cell.circle::after {
  width: calc(var(--mark-size) * 0.7);
  height: calc(var(--mark-size) * 0.7);
  background-color: var(--pantone-serenity);
}


/* game buttons */

.replay-game,
.reset-game {
  font-size: 1.5rem;
  padding: 10px;
  display: inline-block;
}

.hidden {
  display: none;
}
<dialog data-modal class="modal" autofocus data-keyboard="false">
  <div class="modal-header">
    <h2 data-enter-names-header class="players-names">Play Tic Tac Toe!</h2>
  </div>
  <form action="" method="get" data-add-names-form>
    <div class="player-vs-player">
      <label><input type="radio" id="pvp" name="choice" value="0" checked> Player 1 Vs. Player 2</label>
    </div>

    <div class="player-vs-easyai">
      <label><input type="radio" id="easyai" name="choice" value="1"> Player 1 Vs. Easy AI</label>
    </div>

    <div class="player-vs-unbeatableai">
      <label><input type="radio" id="unbeatableai" name="choice" value="2" > Player 1 Vs. Tough AI</label>
    </div>

    <p class="add-player-x">
      <label>X <input type="text" name="playerX" data-player-x placeholder='Name of player X' required /></label>
    </p>

    <p class="add-player-o">
      <label>O <input type="text" name="playerO" data-player-o placeholder='Name of player 0' required /></label>
    </p>
    <button class="submit-form-button" type="submit" data-submit-form-button>Let's Go!</button>
  </form>
</dialog>

<div class='game-container hidden' data-game-container>
  <div class='game-announcement' data-game-announcement></div>
  <div class="board-container" data-board-container></div>
  <div class='game-buttons'>
    <button class="replay-game" data-replay-game>Replay!</button>
    <button class="reset-game" data-reset-game>Reset Game</button>
  </div>
</div>

I created a codepen https://codepen.io/aadriaan/pen/ExrvjxM and the relevant code for the Human Player vs Minimax starts at line 103. These are the functions where I think the problem is:

playUnbeatableAI
minimax
getBestMove
evaluate

To reproduce the issue, run the snippet, select "Player 1 Vs. Tough AI", type a name, and click "Let's go". Then play moves in the right column:

enter image description here

The AI answers in the first column, and doesn't prevent the win in the right column.

Where is the mistake in my minimax implementation?


Solution

  • There are the following problems in your getBestMove, minimax and evaluate functions -- which are the contributing functions to your AI player:

    1. As getBestMove is maximizing the score (cf score > bestScore), the call to minimax should get false for isMaximizing -- but you have true, which means the minimax call will take the maximum score after the opponent's move. That's wrong.

    2. In minimax the comments correctly say that AI is the maximizing player, but in the if (isMaximizing) block, you have the HUMAN player playing and maximize their scores. This is wrong. In this block, it should be the AI_PLAYER that plays the moves, and in the else block it should be the HUMAN player playing.

    3. In minimax the base case is reached when result !== 0, but when the game ends in a draw, result is 0, so also then the base case should kick in. As this doesn't happen in your code, you get a bestScore that is (-)Infinity, which is a wrong evaluation of a draw. To fix this, I would suggest adding logic to evaluate, so that it only returns 0 when a draw is detected, but in all other non-winning cases, it should return something else, like null.

    Here are the corrected versions of the three involved functions. Comments indicate where changes were made:

      function minimax(board, depth, isMaximizing) {
        const result = evaluate(board);
        const HUMAN_PLAYER = 1;
        const AI_PLAYER = -1;
        if (result !== null) { // *** Use distinct value for a non-determined value
          return result;
        }
        if (isMaximizing) {
          let bestScore = -Infinity;
          for (let row = 0; row < 3; row++) {
            for (let col = 0; col < 3; col++) {
              if (board[row][col] === 0) {
                board[row][col] = AI_PLAYER; // *** changed player. This is the maximizing player
                const score = minimax(board, depth + 1, false);
                board[row][col] = 0;
                bestScore = Math.max(score, bestScore);
              }
            }
          }
          return bestScore;
        } else {
          let bestScore = Infinity;
          for (let row = 0; row < 3; row++) {
            for (let col = 0; col < 3; col++) {
              if (board[row][col] === 0) {
                board[row][col] = HUMAN_PLAYER; // *** changed player. This is the minimizing player
                const score = minimax(board, depth + 1, true);
                board[row][col] = 0;
                bestScore = Math.min(score, bestScore);
              }
            }
          }
          return bestScore;
        }
      }
    
      function getBestMove(board) {
        let bestMove = {
          row: -1,
          col: -1
        };
        let bestScore = -Infinity;
        const HUMAN_PLAYER = 1;
        const AI_PLAYER = -1;
        for (let row = 0; row < 3; row++) {
          for (let col = 0; col < 3; col++) {
            if (board[row][col] === 0 && gameOver === false) {
              board[row][col] = AI_PLAYER;
              const score = minimax(board, 0, false); // *** Must provide false as argument
              board[row][col] = 0;
              if (score > bestScore) {
                bestScore = score;
                bestMove = {
                  row,
                  col
                };
              }
            }
          }
        }
        return bestMove;
      }
    
      function evaluate(board) {
        for (let row = 0; row < 3; row++) {
          if (board[row][0] === board[row][1] && board[row][1] === board[row][2]) {
            if (board[row][0] === 1)
              return -10;
            else if (board[row][0] === -1)
              return +10;
          }
        }
        for (let col = 0; col < 3; col++) {
          if (board[0][col] === board[1][col] && board[1][col] === board[2][col]) {
            if (board[0][col] === 1)
              return -10;
            else if (board[0][col] === -1)
              return +10;
          }
        }
        if (board[0][0] === board[1][1] && board[1][1] === board[2][2]) {
          if (board[0][0] === 1)
            return -10;
          else if (board[0][0] === -1)
            return +10;
        }
        if (board[0][2] === board[1][1] && board[1][1] === board[2][0]) {
          if (board[0][2] === 1)
            return -10;
          else if (board[0][2] === -1)
            return +10;
        }
        // *** Return null when the game is not over:
        if (board[0].includes(0) || board[1].includes(0) || board[2].includes(0)) {
            return null;
        }
        return 0; // *** Draw (game over)
      }
    

    Note that these types of problems can be found easily through debugging. This should better be done before spending time on the UI.