Part 4 of 6 · 4 min read
The code
Place a mark and detect a win in one step.
The simple way to detect a win is to scan the row, column and diagonals after each move. That works. A faster way keeps a count for each line and mark.
class Board {
private final int n; private final Mark[][] cells;
private final int[][] rows, cols; // rows[mark][r], cols[mark][c]
private final int[] diag, anti; // per mark
private int filled;
Board(int n) {
if (n < 3) throw new IllegalArgumentException("n >= 3");
this.n = n; cells = new Mark[n][n];
rows = new int[2][n]; cols = new int[2][n]; diag = new int[2]; anti = new int[2];
}
boolean place(int r, int c, Mark m) { // true if this move completes a line
cells[r][c] = m; filled++;
int k = m.ordinal();
rows[k][r]++; cols[k][c]++;
if (r == c) diag[k]++;
if (r + c == n - 1) anti[k]++;
return rows[k][r] == n || cols[k][c] == n || diag[k] == n || anti[k] == n;
}
// inBounds, isEmpty, isFull, size omitted
}
Each move adds one to a row count, a column count and possibly two diagonal counts. A line is complete when its count reaches n. The work per move is constant, whatever the board size. A scan would cost about n steps per line.
The game applies the rules in a fixed order and changes state only after every check has passed (the failure atomicity of Level 5, module 1).
class Game {
private final Board board;
private Mark turn = Mark.X; private Status status = Status.IN_PROGRESS; private Mark winner;
void play(int r, int c) throws InvalidMoveException {
if (status != Status.IN_PROGRESS) throw new InvalidMoveException("game is over");
if (!board.inBounds(r, c)) throw new InvalidMoveException("off the board");
if (!board.isEmpty(r, c)) throw new InvalidMoveException("cell taken");
boolean won = board.place(r, c, turn);
if (won) { status = Status.WON; winner = turn; }
else if (board.isFull()) status = Status.DRAW;
else turn = (turn == Mark.X) ? Mark.O : Mark.X;
}
}
The turn changes only when the game goes on. Out-of-turn moves cannot occur, because the game only accepts a move for whoever's turn it is.
A run on a 3 by 3 board:
| Moves in order (row, column) | Result |
|---|---|
| X(0,0) O(1,0) X(0,1) O(1,1) X(0,2) | X wins on row 0 |
| X(0,0) O(0,1) X(1,1) O(0,2) X(2,2) | X wins on the diagonal |
| X(0,2) O(0,0) X(1,1) O(0,1) X(2,0) | X wins on the other diagonal |
| Nine moves that fill the board with no line | Draw |
| X(0,0) then O(0,0) | "cell taken", the game goes on |
| X(3,0) | "off the board" |
| A sixth move after X wins | "game is over" |
| On a 4 by 4 board, X fills row 0 | X wins, with the same code |
The last line shows requirement R6 working: the same classes handle any size from 3 up.
A computer player needs only a MoveSource. The simplest one takes the first empty cell.
interface MoveSource { int[] next(Board b, Mark me); }
class FirstFree implements MoveSource {
public int[] next(Board b, Mark me) {
for (int r = 0; r < b.size(); r++)
for (int c = 0; c < b.size(); c++)
if (b.isEmpty(r, c)) return new int[]{r, c};
throw new IllegalStateException("full");
}
}
Two such bots playing each other end with X winning on the second diagonal after seven moves. A smarter bot is a new class and nothing else changes.
Constant time
An action takes constant time when its cost does not grow with the size of the input.
Example: the counter win check, which does the same few steps on a 3 by 3 or a 100 by 100 board.
Check yourself:
1. How many counters change when a mark is placed at the centre of a 3 by 3 board?
2. Why does turn change only in the last branch?
3. What does a new bot need to implement?