Conquering Minimax — part 2

As I mentioned in my previous blog post I was implementing a unbeatable computer play in Java Tic Tac Toe.

I wanted to test my minimax algorithm was working. To do this, I integrated the new UnbeatableComputer class into my game flow.

Unfortunately, though my tests were green, things were still going awry. Sometimes my unbeatable player would play as I expected and would either win against me or tie. Yet, there were some game states where the computer did not pick the best move, failing to block my winning move. Something was wrong.

I played the game many times and took notes of some moves the computer didn’t play as it should. It appeared to be the same pattern that tripped the computer player up. I then wrote a test to expose one of these patterns.

@Test
public void blocksADifferentWin() {
    UnbeatableComputer unbeatableComputer = new UnbeatableComputer(O);
    Board board = new Board(3, asList(
            EMPTY, EMPTY, O,
            EMPTY, X, X,
            EMPTY, EMPTY, EMPTY));
    assertThat(unbeatableComputer.findBestMove(board, true, -1), is(3));
}

I realised I was returning the last move played every time but not scoring a move and returning the highest scoring move. This meant the move and played by the “ unbeatable” computer wasn’t always accurate.

To try and get my game to play in the correct way, I reintroduced the scoring if statement at the start. Whether I had the if statement or not, I needed to keep track of the best scoring game state depending on the move played.

I created a hash called bestMoves and if the current move scored 1 or 0 then I pushed the move as the key and score as the value inside the map.

class UnbeatableComputer implements Player {
  private Mark mark;
  public HashMap bestMoves;
  public UnbeatableComputer(Mark mark) {
    this.mark = mark;
    this.bestMoves = new HashMap();
  }
  if (score == 1 || score == 0) {
    bestMoves.put(move, score);
  }

My plan was to find the highest score in the map and then return the move corresponding to that score.

I found a way to iterate over the values and find one that matched a given condition. The problem was that the condition was too limiting.

I created an instance variable called BestMoves and pushed the current move and score to it for the keys and values.

public int getBestMove() {
  for (Map.Entry<Integer, Integer> entry : bestMoves.entrySet()) {
    if (entry.getValue() == 1) {
      return entry.getKey();
    }
  }
}

I wanted to iterate through the values and find the value equal to 1 or 0. Then I wanted to return the move that corresponded to that score. If the game state produces scores only equal to 0, it wouldn’t meet the condition (entry.getValue() == 1) or return the right move.

I tried playing with this and adding another condition to return the score if it was equal to 0 but that didn’t help. For example, what if the first score was 0 but the next score was 1? We’d return early at 0 and not get to the second score which means the highest score and corresponding key (move) is not returned.

public int getBestMove() {
  for (Map.Entry<Integer, Integer> entry : bestMoves.entrySet()) {
    if (entry.getValue() == 1) {
        return entry.getKey();
    } else {
        return entry.getKey();
    }
  }
}

To solve this issue, I needed a way of sorting all the scores from highest to lowest. Once sorted, it would be a simple as returning the first key and that would be the highest scoring move. Unfortunately, Java didn’t want to be kind and I couldn’t find a simple way of both sorting the whole hash by its values.

There are Ruby enumerable methods that would have made this very simple but Java doesn’t have simplest solutions for this kind of manipulation and it would have involved numerous loops. I decided to work with Java Streams to see if that could help. I expand on this process in part 3 of my blog post.

The main lesson I learnt was that manipulating hashmaps in Java is a confusing and long process. A simpler data structure would have been easier to work with.