Unbeatable Tic Tac Toe — Minimax in Java

Over the past week, I’ve been working on simplifying my Java Tic Tac Toe game, as well as implementing the Minimax algorithm to make an unbeatable computer player. You may recall I’ve implemented this algorithm in Ruby previously.

In my Ruby post, I focused on my process and how I felt about it, in this post I am going to show my implementation and explain step by step what it is doing.

First of all — what is Minimax? It is a recursive algorithm that calculates every possibility, and chooses a move to minimise the possible loss for a worst case (maximum loss) scenario.

When it is the computer’s turn, we look at the board and simulate every possible outcome, assuming that its opponent will also try to win. If we can’t win (or tie the game) in one move, we recursively call the function and sees what our opponent could do. If the game is not over, we continue to simulate outcomes, until the game is over. As I’m sure you can imagine, this can take quite a long time to process all these situations.

Here’s my implementation of minimax— if it looks intimidating scroll down to where I break it down.

Note: There are some methods/variables that I have extracted for readability. They are not necessary. If you want to see a much smaller version of this with the exact same functionality, scroll to the bottom.

@Override
public int chooseSpace(Game game) {
  return calculateBestMove(game, 0, new HashMap<>());
}

private int calculateBestMove(Game game, int depth, Map<Integer, Integer> potentialOutcomes) {
  int TIEDGAME = 0;
  int WONGAME = -1;
  if (game.isGameTied()) {
    return TIEDGAME;
  } else if (game.isGameOver()) {
    return WONGAME;
  } else {
    checkPossibilities(game, depth, potentialOutcomes);
    if (depth == 0) {
      return chooseBestMove(potentialOutcomes);
    } else {
      return getTopScoreInThisScenario(potentialOutcomes);
    }
  }
}

private void checkPossibilities(Game game, int depth, Map<Integer, Integer> potentialOutcomes) {
  for (int space : game.board.getAvailableSpaces()) {
    emulateTurn(game, space);
    addPossibilityToOutcomes(game, depth, potentialOutcomes, space);
    resetBoard(game, space);
  }
}

private void emulateTurn(Game game, int space) {
  game.board.placeMarker(space, game.getCurrentPlayer().getMarker());
  game.changeCurrentPlayer();
}
private void addPossibilityToOutcomes(Game game, int depth, Map<Integer, Integer> potentialOutcomes, int space) {
  potentialOutcomes.put(space, (-1 * calculateBestMove(game, depth + 1, new HashMap<>())));
}
private void resetBoard(Game game, int space) {
  game.board.resetSpace(space);
  game.changeCurrentPlayer();
}

private int chooseBestMove(Map<Integer, Integer> potentialOutcomes) {
  return potentialOutcomes.entrySet().stream().max(Map.Entry.comparingByValue()).get().getKey();
}

private int getTopScoreInThisScenario(Map<Integer, Integer> potentialOutcomes) {
  return potentialOutcomes.entrySet().stream().max(Map.Entry.comparingByValue()).get().getValue();
}

1) Choose Space

@Override
public int chooseSpace(Game game) {
  return calculateBestMove(game, 0, new HashMap<>());
}

My implementation of Tic Tac Toe uses polymorphism to defer the chooseSpace(Game game) method to the player. A human player’s version of this method calls the getNumber method in the command line interface, and allows the user to choose a move based on the available spaces on the board.

@Override
public int chooseSpace(Game game) {
  return cli.getNumber(game.board.getAvailableSpaces());
}

For the computer’s implementation of the chooseSpace method, we create a new HashMap, and call the calculateBestMove method, passing in the current game, a 0 (the current depth), and our empty HashMap.

2) Calculate Best Move

private int calculateBestMove(Game game, int depth, Map<Integer, Integer> potentialOutcomes) {
  int TIEDGAME = 0;
  int WONGAME = -1;
  if (game.isGameTied()) {
    return TIEDGAME;
  } else if (game.isGameOver()) {
    return WONGAME;
  } else {
    checkPossibilities(game, depth, potentialOutcomes);
    if (depth == 0) {
      return chooseBestMove(potentialOutcomes);
    } else {
      return getTopScoreInThisScenario(potentialOutcomes);
    }
  }
}

This is the method that we have called above. It takes a Game object, an integer which relates to the depth of the recursive calls, and a Map object that holds a key value pair, both of which are integers.

The first thing I did was declare two constants:

• TIEDGAME which is 0
• WONGAME which is -1

I’ll explain why WONGAME is -1 not 1 in 2c.

The first thing we do is check if the game is tied. If so, nobody wins, so we assign the game an outcome of 0. Not a great result, but not a loss.

Then we check if the game has been won. I already have a method that checks if either player has won or if the game has been tied, so I decided to reuse this. Since code runs from the top down, if the game has been tied we would have returned 0 and broken out of the function, so would not get to this line. If the game is won in this turn we return -1.

The vast majority of the time, the game will not be over, so here’s where we get to our else statement. The first thing we do is checkPossibilities(game, depth, bestScore)

2a) Check Possibilities

private void checkPossibilities(Game game, int depth, Map<Integer, Integer> potentialOutcomes) {
  for (int space : game.board.getAvailableSpaces()) {
    emulateTurn(game, space);
    addPossibilityToOutcomes(game, depth, potentialOutcomes, space);
    resetBoard(game, space);
  }
}

In this method we loop through all the available spaces left on the board. From a high level perspective, we pretend to take a turn, adds that possibility to the Map where we are storing outcomes, and then reset the board (since that turn wasn’t actually made).

2b) Emulate Turn

private void emulateTurn(Game game, int space) {
  game.board.placeMarker(space, game.getCurrentPlayer().getMarker());
  game.changeCurrentPlayer();
}

This is probably the most simple method here. We pretend to take a turn by placing a marker in one of the available spaces, then change the current player.

2c) Add Possibility To Outcomes

private void addPossibilityToOutcomes(Game game, int depth, Map<Integer, Integer> potentialOutcomes, int space) {
  potentialOutcomes.put(space, (-1 * calculateBestMove(game, depth + 1, new HashMap<>())));
}

Here we add our result to our potential outcomes map. This is the recursive call I’ve referred to above.

• Key: The space we are checking (from our loop of all available spaces)
• Value: The outcome of another call of our calculateBestMove method. There’s a few things to note about this call. Fundamentally, we are going to return a -1, a 0, or a 1, since that is all that the calculateBestMoves score can return in a recursive call.
• We are multiplying it by -1. For the protagonist computer’s turn, this negates the -1 we have as our WONGAME constant. If the game is won on an odd move we will result in a positive outcome +1, and if it is won on an even number, this means the opponent has won, and we will have a negative outcome, -1.

2d) Reset Board

private void resetBoard(Game game, int space) {
  game.board.resetSpace(space);
  game.changeCurrentPlayer();
}

Here’s another logical method, where we just reset each space back to what it was, since we aren’t actually making these moves, only emulating them.

3) Outcomes

if (depth == 0) {
  return chooseBestMove(potentialOutcomes);
} else {
  return getTopScoreInThisScenario(potentialOutcomes);
}

One we get to the end of our method we’ve got two options.

3a) Choose Best Move

private int chooseBestMove(Map<Integer, Integer> potentialOutcomes) {
  return potentialOutcomes.entrySet().stream().max(Map.Entry.comparingByValue()).get().getKey();
}

If we are at a depth of 0, meaning that we aren’t inside our recursive call, and this is where we have to make an actual decision of where to play, we need to choose the best move.

I’ve used a Java 8 Stream for this, that checks for the highest value (-1, 0 or 1) and returns the key (the move from the available spaces).

3b) Get Top Score In This Scenario

private int getTopScoreInThisScenario(Map<Integer, Integer> potentialOutcomes) {
  return potentialOutcomes.entrySet().stream().max(Map.Entry.comparingByValue()).get().getValue();
}

If, on the other hand, we are inside of our recursive function, the depth will be higher than 0. In this instance, we don’t want to see what the space is doing, we want to see what the best possible outcome is, therefore we return the value (-1, 0, or 1).

Summary

All recursion, especially Minimax, used to scare me — I’ve now grown to really enjoy it. I find it much more logical and easy to read than a while loop.

Like everything else, when it comes to problem solving I find that breaking everything down makes it much less intimidating.

On my next Tic Tac Toe I want to try the Negamax algorithm which does the same thing, and also Alpha Beta Pruning which makes it faster.

BONUS

As I noted above, I’ve extracted methods and variables which I think helps with readability, but here is my implementation where I’ve inlined everything that I can. It is quite a bit smaller, and some people may find this less intimidating.

@Override
public int chooseSpace(Game game) {
  return calculateBestMove(game, 0, new HashMap<>());
}

private int calculateBestMove(Game game, int depth, Map<Integer, Integer> potentialOutcomes) {
  if (game.isGameTied()) {
    return 0;
  } else if (game.isGameOver()) {
    return -1;
  } else {
    for (int space : game.board.getAvailableSpaces()) {
      game.board.placeMarker(space, game.getCurrentPlayer().getMarker());
      game.changeCurrentPlayer();
      potentialOutcomes.put(space, (-1 * calculateBestMove(game, depth + 1, new HashMap<>())));
      game.board.resetSpace(space);
      game.changeCurrentPlayer();
    }
    if (depth == 0) {
      return potentialOutcomes.entrySet().stream().max(Map.Entry.comparingByValue()).get().getKey();
    } else {
      return potentialOutcomes.entrySet().stream().max(Map.Entry.comparingByValue()).get().getValue();
    }
  }
}