Modelling a tic tac toe board state

My first foray into TDD coding katas led me to the Roman Numerals Kata. My second sees me designing a noughts and crosses engine (or tic tac toe if you prefer). This led down some interesting paths of designing the board and storing moves, combined with the best way to work out if someone had won. Maybe this shows me to be more of an algorithm designer than a TDD specialist but I think the time spent was worth it.

My initial test was that starting a game caused an empty board state to be produced. As I moved through the exercise I realised that this wasn't really a useful test. I certainly didn't care what the internal board state was, and as I'll get to, I didn't end up with a board being modelled at all! So that test got deleted. A similar test may return if I want the output of the game to be part of the API.

Equivalent initial designs

My initial board design was an array of playable positions, all initialised to the enum value Player.NEITHER. This is entirely equivalent to the other considered approach of a real-world-like model using a 3x3 array of the Player enum.

private List<Player> board = Arrays.asList(
   NEITHER,NEITHER,NEITHER,
   NEITHER,NEITHER,NEITHER,
   NEITHER,NEITHER,NEITHER);

or

private Player[][] board = {
   {NEITHER,NEITHER,NEITHER},
   {NEITHER,NEITHER,NEITHER},
   {NEITHER,NEITHER,NEITHER}};

The problem with these designs came when I needed to test the winning moves. What does an algorithm look like for checking a winning move in those data structures? Even when you factor in that that current move must be a part of the win, if there is one, you still have a lot of code checking various combinations of elements in your array. You could perhaps keep a set of 8 numbers, one for each win line (3 rows, 3 columns, 2 diagonals) and add one when player 1 plays there, and subtract 1 when player 2 does so. Then you know someone has won when a number reaches +/-3

But then I noticed a forum post which mentioned that a magic square might be a useful tool for a noughts and crosses game. And I immediately set about refactoring to use this new information. Luckily I had tests, and I could make pretty sweeping changes without breaking them as I had already deleted those pesky tests that were peering into the internals of my data structures.

The final design

I ended up with the "board" being a map of coordinates (Points) to magic square values. A turn involves taking one of those values from the map and adding it to the current players list of moves. If at any point a player has any 3 values that add up to 15, they have won. This also has the added bonus that if you were adding an AI player, it could easily scan the remaining moves to see if it, or you, has a winning move available.

import java.awt.Point;
import java.util.*;

public class Tictactoe {

 private Gamestate gameState = Gamestate.ONGOING;
 private Player currentPlayer = Player.PLAYER1;
 private Map<Point, Integer> availableSquares;
 private Map<Player, List<Integer>> playerBoards;

 public Tictactoe() {
  availableSquares = new HashMap<>();
  availableSquares.put(new Point(1,1), 4);
  availableSquares.put(new Point(1,2), 3);
  availableSquares.put(new Point(1,3), 8);
  availableSquares.put(new Point(2,1), 9);
  availableSquares.put(new Point(2,2), 5);
  availableSquares.put(new Point(2,3), 1);
  availableSquares.put(new Point(3,1), 2);
  availableSquares.put(new Point(3,2), 7);
  availableSquares.put(new Point(3,3), 6);

  List<Integer> player1sMoves = new ArrayList<>();
  List<Integer> player2sMoves = new ArrayList<>();
  playerBoards = new HashMap<Player, List<<Integer>>();
  playerBoards.put(Player.PLAYER1, player1sMoves);
  playerBoards.put(Player.PLAYER2, player2sMoves);
 }

 public Gamestate playAt(int column, int row) {
  Integer moveMade = availableSquares.remove(new Point(column, row));
  if (moveMade == null) {
   throw new IllegalStateException("already taken");
  }
  if (isWinningMove(moveMade, currentPlayer)) {
   gameState = currentPlayer.hasWon;
  }
  playerBoards.get(currentPlayer).add(moveMade);
  if (gameState == Gamestate.ONGOING && availableSquares.isEmpty()) {
   gameState = Gamestate.A_DRAW;
  }
  currentPlayer = currentPlayer.getNext();
  return gameState;
 }

 private boolean isWinningMove(int numberToTake, Player player) {
  LinkedList<Integer> second = new LinkedList<>(playerBoards.get(player));
  for (Integer integer : playerBoards.get(player)) {
   second.pollFirst();
   for (Integer integer2 : second) {
    if(numberToTake + integer + integer2 == 15) {
     return true;
    }
   }
  }
  return false;
 }

 public enum Gamestate {
  ONGOING, PLAYER1WON, PLAYER2WON, A_DRAW;
 }

 private enum Player {
  PLAYER1(Gamestate.PLAYER1WON), PLAYER2(Gamestate.PLAYER2WON);
  Gamestate hasWon;

  Player(Gamestate stateOnWinning) {
   this.hasWon = stateOnWinning;
  }

  public Player getNext() {
   Player next;
   switch (this) {
   case PLAYER1:
    next = PLAYER2;
    break;
   case PLAYER2:
   default:
    next = PLAYER1;
    break;
   }
   return next;
  }
 }

}