Tic Tac Toe and The Minimax Algorithm: Advice and Tips for Struggling Campers

Tic Tac Toe and The Minimax Algorithm: Advice and Tips for Struggling Campers
0

#1

Tic Tac Toe may be a lesson in futility, however! Completing the FreeCodeCamp project with the minimax algorithm is not, quite the opposite!

I worked on the Tic Tac Toe project earlier this week, when researching strategies to code a formidable computer opponent I found the Minimax algorithm, which contained the logic to make this opponent unbeatable.

Alas, whenever I looked at tutorials, and many of them, I found myself bewildered. I was on the cusp of settling for a erroneous computer opponent that would randomly select free squares.

I think this is due to the overwhelming complexity of the algorithm when taking it in as a whole. It’s job is to simulate millions of possible games states, testing possible moves and predicting possible opponent moves to select the best move. It’s very easy to lose your place when stepping through it in your head.

So we need to break it down into several components we can comprehend individually. And then, we can put them together to see the big picture.

This is what I intend to do in this post.


1. Step One: Read Jason Fox’s article on the minimax algorithm @ neverstopbuilding.

This was the most helpful resource I encountered when trying to understand what was going on under the hood of Minimax. It’s worth a proper sit down and read. If you can write you own notes along the way. Better yet write some Pseudocode! (informal code, in your own speak!).

2. Step Two: Lets break it down!

Here’s Jason’s break down of the code:

  • If the game is over, return the score from X’s perspective.
  • Otherwise get a list of new game states for every possible move
  • Create a scores list
  • For each of these states add the minimax result of that state to the scores list
  • If it’s X’s turn, return the maximum score from the scores list
  • If it’s O’s turn, return the minimum score from the scores list

Lets think about what sort of functions (helper functions) we could build to do each of these tasks.

  • If the game is over, return the score from X’s perspective.

We need a function that can check if the game is over, scanning our game board for win, lose, or draw cases. We’ll probably execute this immediate after a play is made. Let’s call this checkWin().

We’ll also need a function that can evaluate how the game ended, different end game states (win, loses and draws), and then return a corresponding score for our Minimax calculations. Let’s call this score().

Moving on to the next logical step…

  • Otherwise get a list of new game states for every possible move

We need to look at the game board in a particular state, and then return a list or array of all the possible moves that might be made in this turn. This doesn’t sound to hard, we’ll just iterate through the rows and columns of the game board and return the coordinates of each of the spaces that don’t have an ‘X’ or and ‘O’ in them. Let’s call this function generateAllPossibleMoves().

  • Create a scores list
  • For each of these states add the minimax result of that state to the scores list

So for each of those moves we just generated, we’re going create a new state of the game to simulate what would happen as a result. We’ll call this generatePossibleGameState(). It will take the move, play it on the gameboard, alternate the turns and determine whether we’ve entered a game end state (win, lose, draw).

If it did enter an end game state, we should probably return the corresponding score using our score() function. If the game isn’t over after a possible turn, it would be cool to almost look into the future and see if it could eventually result in a win, or impending doom.

We can handle both cases by recursively calling our minimax() function, the function we’re building at the moment. It will play out until it reaches and end state, and eventually give us a score.

  • If it’s X’s turn, return the maximum score from the scores list
  • If it’s O’s turn, return the minimum score from the scores list

Can we make a function to scan through a collection / array and return the index of the maximum or minimum value? Hell yeah! We must have done that way back in the basic JavaScript challenges. We make findMaxIndex() and findMinIndex() which takes an array and returns the index of the value we’re looking for. Each time we save that optimal move so that it can be executed once the minimax algorithm has finished it’s evaluation.


And that is pretty much your minimax algorithm.

Even after reading this article, I’d wager it still feels a little confusing and overwhelming. But, you’re well on your way. Even if you do not immediately understand it, I think it is worth while writing each of these functions and experimenting. Try put them together, use plenty of console.log() statements, and try to make sense of this madness!

The only other important hint I think I have missed is that it is worthwhile creating some kind of structure or object that captures the game state. It’ll be handy to be able to pass this between functions these functions you’ve written. You’re generatePossibleGameState() might create replicated copies of this object, that can recursively pass through minimax() without it reflecting on the game. A game state might contain:

  • The state of the game board (the selected and unselected spaces).
  • Who’s turn it currently is.
  • If the game is over.
  • The result of the game.
  • The number of turns played.

Good luck and god speed!!


Code Snippets

checkWin()

// Used to check if the last played move has resulted in a win.
function checkWin(gameState) {
  const numRows = 3;
  const numCols = 3;

  // Check for diagonal win right to left
  if (gameState.board[0][0] === gameState.board[1][1] &&
    gameState.board[1][1] === gameState.board[2][2] &&
    gameState.board[0][0] !== null) {
    // Right to left, top to bottom diagonal win
    return true;
  }

  // Check for diagonal win left to right
  if (gameState.board[0][2] === gameState.board[1][1] &&
    gameState.board[1][1] === gameState.board[2][0] &&
    gameState.board[0][2] !== null) {
    // Left to right, top to bottom diagonal win
    return true;
  }

  // Checking each row for a horizontal win
  for (var row = 0; row < numRows; row++) {
    if (gameState.board[row][0] === gameState.board[row][1] &&
      gameState.board[row][1] === gameState.board[row][2] &&
      gameState.board[row][0] !== null) {
      // Horizontal win
      return true;
    }
  }

  // Checking each column for a vertical win
  for (var col = 0; col < numCols; col++) {
    if (gameState.board[0][col] === gameState.board[1][col] &&
      gameState.board[1][col] === gameState.board[2][col] &&
      gameState.board[0][col] !== null) {
      // Vertical win
      return true;
    }
  }
  return false;
}

score().

// Equates game states to scores
// Wins equating to 10, loses equating to -10, draws or continued gameplay equating to 0.
function getScore(gameState, depth) {
  if (gameState.gameOver && gameState.winner === gameState.playerMark) {
    return 10 - depth;
  } else if (gameState.gameOver && gameState.winner === gameState.aiMark) {
    return depth - 10;
  } else {
    return 0;
  }
}

generateAllPossibleMoves().

function generateAllAvailableMoves(gameState){
  const rowLength = 3;
  const colLength = 3;
  var availableMoves = [];
  
  for (var row = 0; row < rowLength; row++){
    for (var col = 0; col < colLength; col++){
      if (spaceFree(gameState.board, row, col)){
        // Scanning the game board for free spaces
        availableMoves.push([row, col]);
      }
    }
  }
  return availableMoves;
}

generatePossibleGameState().

// Creates a simulated game state when a specified move is executed.
function generatePossibleGame(state, move){
  var gameState = JSON.parse(JSON.stringify(state));
  
  // Execute the move
  if (gameState.playerTurn){
    gameState.board[move[0]][move[1]] = gameState.playerMark;
  } else {
    gameState.board[move[0]][move[1]] = gameState.aiMark;
  }
  gameState.turnsPlayed++;
  
  // Check if the move has resulted in an end game state.
  if (checkWin(gameState)) {
    gameState.gameOver = true;
    if (gameState.playerTurn){
      gameState.winner = gameState.playerMark;
    } else {
      gameState.winner = gameState.aiMark;
    }
  } else if (gameState.turnsPlayed >= 9) {
    gameState.gameOver = true;
    gameState.winner = "draw";
  } else {
    gameState.playerTurn = !gameState.playerTurn;
  }
  
  return gameState;
}

Example: http://codepen.io/allanpooley/full/qrrmoR/