One of the features I wanted to have in my Tic Tac Toe game was an unbeatable computer, but I wasn’t entirely sure how I was going to implement it. After some googling, I came across a very well written article on this exact problem:

Tic Tac Toe: Understanding The Minimax Algorithm

The article explains the Minimax algorithm through several examples and diagrams in a very intuitive way. I definitely would recommend the article as it helped me understand the Minimax algorithm, and made implementing my own Tic Tac Toe algorithm in Javascript a breeze.

Here is my Javascript version of the algorithm, with pieces of it taken out in order to focus on the relevant parts:

function playRound() {
  .
  .
  .
    // if it's a single player game
    if (players == 1) {
      // computer's turn
      if (gameWin(board) == -1) { // if game is not over
        computerMove(board); // play computer's move
      }
    }
  }
}

The computerMove function calls the minimax function for every possible move, and plays the one that yields the max score.

function computerMove(game) {
  moves = []; // array of moves
  scores = []; // array of scores

  // for each cell in the board
  for (var i = 1; i < game.length; i++) {
    // if the cell is available
    if (game[i] == 0) {
      // add move to array of moves
      moves.push(i);
      // add the corresponding score
      // by calling minimax with the computer's
      // potential move. Where player1 is the nextTurnPlayer
      scores.push(minimax(game.slice(0, i).concat([computer], game.slice(i + 1, game.length)), player1));
    }
  }
  // find the move corresponding to the max score
  var cellNum = moves[maxIndex(scores)];
  // play the move
  board[cellNum] = computer;
  // check for a winner
  checkForWinner();
  return cellNum;
}

// Stops the game if there's a winner
function checkForWinner() {
  .
  .
  .
}

Here is the actual minimax function that will find the ultimate score for each possible move:

function minimax(game, turnPlayer) {
  var winner = gameWin(game);
  // if there is a winner
  if (winner >= 0) {
    return score(game); // return the score
  }

  // otherwise, the game continues
  var scores = [];
  var moves = [];
  var nextTurnPlayer = (turnPlayer == 1) ? 2 : 1;

  // for each cell in the board
  for (var i = 1; i < game.length; i++) {
    // if the cell is available
    if (game[i] == 0) {
      // add move to array of moves
      moves.push(i);
      // add the corresponding score
      // by calling minimax with the turnPlayer's
      // potential move. Where nextTurnPlayer is the next turnPlayer
      scores.push(minimax(game.slice(0, i).concat([turnPlayer], game.slice(i + 1, game.length)), nextTurnPlayer));
    }
  }

  // if it's the computer's turn
  if (turnPlayer == computer) {
    return max(scores); // return the max score
  } else { // if it's player1's turn
    return min(scores); // return the min score
  }
}

Here is the function that scores the game, along with other helper functions:

function score(game) {
  // if the winner is the computer
  if (gameWin(game, computer) == computer) {
    return 10;
  // if the winner is player1
  } else if (gameWin(game, player1) == player1) {
    return -10;
  } else { // if there's no winner
    return 0;
  }
}

// returned the max value in array
function max(A) {
.
.
.
}

// returned the min value in array
function min(A) {
.
.
.
}

// returned the index of the max value in array
function maxIndex(A) {
.
.
.
}

// takes in a board, and returns the winning symbol
// returns -1 if no winner
// returns 0 if tied
function gameWin(board) {
  .
  .
  .
}

Refactor? Shhh…


If you noticed that the computerMove and minimax functions look very similar, you’re right. I probably could/should refactor the code to eliminate repeated code, but that’s for another day.

Here is the full game, have fun not winning!

See the Pen Tic Tac Toe by Aaron Young (@aaronyoung) on CodePen.