Tic-Tac-Toe

Part of the free Low-Level Design course on LogicWiz, in the chapter: Case studies, step by step. The class-diagram exercises run in the app.

Tic-Tac-Toe: your first problem from a blank page

"Your win check lists eight lines by hand. What does it do on a four by four board?"

Priya, in a mock interview

The prompt, and the five minutes of questions

Priya starts a 45-minute timer and says one sentence: "Design Tic-Tac-Toe." Arjun reaches for the keyboard. Priya raises a hand.

"The first five minutes are for questions. Every answer removes one guess from your design, and it shows the interviewer how you work."

Arjun asks five things and writes down what he will assume:

Notice that none of the questions is about code. They are about what the program must do.

From nouns and verbs to classes

Minutes 5 to 10 go to a short story. Priya says: "Write one game in plain sentences. Then underline."

Two players take turns. A player puts a mark on an empty cell of the board. When K of one player's marks sit side by side in a line, that player wins. If the board is full, the game is a draw.

The nouns are game, player, mark, board, cell and line. Not every noun becomes a class. Arjun decides one by one:

• Mark has two values, X and O, and no behaviour. It is an enum, a type with a fixed list of values.
• Board owns the cells, so it answers "is this cell free?" and "is it full?".
• Game owns the turn and the end of the game, so it answers "whose move is it?" and "is it over?".
• Player owns one question: where do I play?
• Cell and line stay out. A cell is one mark or nothing, so an array slot is enough. A class with one field adds names and no value.

Priya's test for ownership is a question: "Whose data does this rule need?" The rule "a cell holds one mark" needs the cells, so the board enforces it.

The first draft, and where it breaks

Arjun writes what most people write in ten minutes: one class, with a hard-coded check for the eight lines of a 3 by 3 board.

public class NaiveTicTacToe {
    private final char[][] b;
    private char turn = 'X';
    private final Scanner in;

    public NaiveTicTacToe(int size, Scanner in) {
        this.b = new char[size][size];
        this.in = in;
    }

    public void run() {
        while (true) {
            int row = in.nextInt();
            int col = in.nextInt();
            b[row][col] = turn;
            if (hasWon(turn)) {
                System.out.println(turn + " wins");
                return;
            }
            turn = (turn == 'X') ? 'O' : 'X';
        }
    }

    private boolean hasWon(char c) {
        return (b[0][0] == c && b[0][1] == c && b[0][2] == c)
            || (b[1][0] == c && b[1][1] == c && b[1][2] == c)
            || (b[2][0] == c && b[2][1] == c && b[2][2] == c)
            || (b[0][0] == c && b[1][0] == c && b[2][0] == c)
            || (b[0][1] == c && b[1][1] == c && b[2][1] == c)
            || (b[0][2] == c && b[1][2] == c && b[2][2] == c)
            || (b[0][0] == c && b[1][1] == c && b[2][2] == c)
            || (b[0][2] == c && b[1][1] == c && b[2][0] == c);
    }
}

It works. Priya feeds it scripted input for two games: a 3 by 3 board where X takes the left column, then a 4 by 4 board where X takes only three cells of the top row.

3 by 3, X takes the left column:
X wins
4 by 4, X takes three cells of the top row:
X wins

The second line is a bug. The check never looks beyond column 2, so changing the board size did not change the rules. The number 3 is written into eight lines.

"Now add a computer player," says Priya. The class reads the keyboard inside run, so a computer means editing run. Nothing stops O from writing over X's cell, and a full board with no winner is never noticed. One class has four reasons to change: the size, who plays, the rules, and the end of the game.

Two decisions: who picks the move, and how to find a win

Decision 1: the computer's rule sits behind an interface. How a computer picks a cell will change from "first free cell" to "block the opponent" and beyond. A rule that changes belongs behind an interface, a list of methods any class can promise to provide. This is the strategy pattern from the earlier lesson. A human player has no strategy, because a human's moves arrive from outside.

final class Player {
    private final Mark mark;
    private final MoveStrategy strategy;
    Player(Mark mark, MoveStrategy strategy) { this.mark = mark; this.strategy = strategy; }
    Mark mark() { return mark; }
    boolean isComputer() { return strategy != null; }
    Move choose(Board board) { return strategy.choose(board, mark); }
}

interface MoveStrategy {
    Move choose(Board board, Mark me);
}

final class FirstFreeStrategy implements MoveStrategy {
    @Override
    public Move choose(Board board, Mark me) {
        for (int r = 0; r < board.size(); r++)
            for (int c = 0; c < board.size(); c++)
                if (board.isEmpty(r, c)) return new Move(r, c);
        throw new IllegalStateException("board is full");
    }
}

Game.playComputerTurn asks the player's strategy for a Move and sends it down the same play(row, col) path as a human move. A computer's move is checked exactly like a person's, so a strategy that picks a taken cell is refused, not obeyed:

MoveResult play(int row, int col) {
    if (!board.inBounds(row, col)) return MoveResult.OUT_OF_BOUNDS;
    if (!board.isEmpty(row, col)) return MoveResult.OCCUPIED;
    Mark mark = current().mark();
    board.place(mark, row, col);
    history.push(new Move(row, col));
    if (checker.placed(board, mark, row, col)) {
        status = GameStatus.WON;
        winner = mark;
        return MoveResult.WIN;
    }
    if (board.isFull()) {
        status = GameStatus.DRAW;
        return MoveResult.DRAW;
    }
    turn = 1 - turn;
    return MoveResult.OK;
}

The two refusals come before anything changes, so the turn stays with the same player. The checker line is the second decision. Here is a 3 by 3 game with a human X and a computer O. The computer takes the first empty cell, and the board is printed row by row with slashes:

play(1,1) -> OK   .../.X./...
playComputerTurn() -> OK   O../.X./...
play(0,0) -> OCCUPIED   O../.X./...
play(3,0) -> OUT_OF_BOUNDS   O../.X./...
play(0,2) -> OK   O.X/.X./...
playComputerTurn() -> OK   OOX/.X./...
play(2,0) -> WIN   OOX/.X./X..

Decision 2: the win rule gets its own type, with two implementations. There are three ways to find a win, and each is cheaper than the last:

1. Scan the whole board after every move. For N by N that is N × N cell reads.
2. Look only at the four lines through the cell just played: its row, its column and its two diagonals. Walk outward while the marks match. That reads at most 4 × (K - 1) cells, so the cost depends on K and not on the board size.
3. Keep counters. Each player has one counter per row, per column and for the two diagonals. A move adds 1 to at most four counters, and a counter that reaches N means that player holds a whole line. That is constant time, written O(1).

Arjun walks a 3 by 3 game on paper: X plays (0,0), O plays (0,1), X plays (1,1), O plays (0,2), X plays (2,2). X's diagonal counter goes 1, 2, 3 and X wins. Row 0 never helps X, because X's row counter for it stays at 1.

final class CounterWinChecker implements WinChecker {
    private final int n;
    private final int[][] rows, cols;
    private final int[] diagonal = new int[2], anti = new int[2];

    @Override
    public boolean placed(Board board, Mark mark, int r, int c) {
        int p = mark.ordinal();
        boolean won = ++rows[p][r] == n;
        won |= ++cols[p][c] == n;
        if (r == c) won |= ++diagonal[p] == n;
        if (r + c == n - 1) won |= ++anti[p] == n;
        return won;
    }
}

Now the limit, which Priya wants to hear aloud. Counters are valid only when K equals N. On a 5 by 5 board where 4 in a row win, take the row XX.XX. Its counter reads 4, but X has no four side by side. A counter counts marks, not neighbours. When K is less than N, use the line scan:

@Override
public boolean placed(Board board, Mark mark, int r, int c) {
    for (int[] d : DIRECTIONS) {
        int run = 1 + count(board, mark, r, c, d[0], d[1]) + count(board, mark, r, c, -d[0], -d[1]);
        if (run >= k) return true;
    }
    return false;
}

Both classes implement WinChecker, and Game chooses once, in its constructor: this.checker = k == n ? new CounterWinChecker(n) : new LineScanWinChecker(k);. Every move then asks the same question.

classDiagram
  class Game {
    +play(row, col) MoveResult
    +playComputerTurn() MoveResult
  }
  class Player
  class MoveStrategy {
    <<interface>>
  }
  class WinChecker {
    <<interface>>
  }
  Game *-- Board
  Game *-- Player
  Game --> WinChecker
  Player --> MoveStrategy
  MoveStrategy <|.. FirstFreeStrategy
  WinChecker <|.. CounterWinChecker
  WinChecker <|.. LineScanWinChecker

A clever method needs proof. Arjun plays 105,000 random games on boards from 3 by 3 to 6 by 6, with every K from 2 up to N. After every move he asks the checker, and he also runs a slow full scan that cannot be wrong.

boolean truth = hasKInARow(board, mark, k);
boolean scanSays = scan.placed(board, mark, cell[0], cell[1]);
boolean counterSays = counter.placed(board, mark, cell[0], cell[1]);
if (scanSays != truth) scanBad++;
if (k == n) { counterMoves++; if (counterSays != truth) counterBad++; }

games 105000, moves 1566056
LineScanWinChecker disagreements with a full scan: 0
CounterWinChecker (K = N only), moves 606321, disagreements: 0
counters compared with K when K < N, moves 959735, disagreements: 97384

The last line is the tempting mistake, counters compared with K: it is wrong in 97,384 moves. To check that the checker can fail, Arjun breaks one test in CounterWinChecker to r + c == n. The same run then reports 1,979 disagreements for the counters.

Extend it, then break it

Priya asks for the 5 by 5 board with K = 4. Two humans play. X builds the row XX.XX while O plays elsewhere:

play(0,4) -> OK   XX.XX/OO.O./...../...../.....
play(2,4) -> OK   XX.XX/OO.O./....O/...../.....
play(0,2) -> WIN   XXXXX/OO.O./....O/...../.....

XX.XX is not a win, and filling the gap makes five in a row, which wins because a longer line also counts. Only the checker knew about K, so Game did not change.

"Now add undo." Game keeps a stack of moves. undo() pops one, clears the cell, calls checker.removed so the counters go back, and sets the status to IN_PROGRESS. After the win above, undo() -> true, status IN_PROGRESS, to move X. The line scan stores nothing, so its removed is empty.

The edge cases have answers in the code:

• A taken cell or a cell off the board. In the 3 by 3 run, play(0,0) gives OCCUPIED and play(3,0) gives OUT_OF_BOUNDS. The board is unchanged and X still moves.
• Two requests at the same instant, for example from two phones. Checking the cell, placing the mark and passing the turn must happen as one step. Marking play as synchronized does this, and it costs nothing because only two players share the game. The model Game assumes one caller at a time.

⚠️ Warning: Never write the board size or K as a number inside a rule, as in the eight lines above. Every hard-coded number is a hidden limit that fails without an error message.

Your turn: draw it, then build it

In the class designer, start from Arjun's first draft: one class doing everything. Pull the computer's rule and the win rule behind interfaces, give the win rule two implementations, and keep the board apart from the game.

📌 Summary: Ask questions first. Give each rule to the class whose data it needs. Put the computer's rule and the win rule behind interfaces. Counters give O(1) wins only when K equals N.

Now open the problem Tic-Tac-Toe in the problem library and design it again on a blank page, from memory. Compare it with the model answer. Then use its "Build it on your machine" kit to write and run it yourself.

What Arjun learns next

Tic-Tac-Toe has no money, no clock and no rules that change. The next problem adds all three. Priya describes a mall car park with two entry gates, and asks Arjun how the first draft can be the right size.

Check your understanding

1. Priya asks for a computer opponent. Which change is smallest, and why?
2. On a 5 by 5 board where 4 in a row win, the row XX.XX has a counter of 4. Why can the counter method not be used here?
3. Game must support N = 3 with K = 3, and also N = 5 with K = 4. Where should the choice between the two win checks be made?
4. A computer strategy returns a cell that is already taken. What should happen?