!This gives away every stage. For a clean attempt, practise it first, then come back.

How this walkthrough is built

In a low-level design round you get about an hour to turn something familiar into classes and working code. With tic-tac-toe, the “something” is so familiar that you can’t hide behind requirements. Every minute is spent on design decisions, and the interviewer sees all of them.

We’ll build it in the same order you would in the room. Each step only uses what the steps before it produced.

The one idea to take away: a small problem is a chance to show clean design, not a reason to skip it. Candidates who write one 200-line Game class with a main loop pass the “does it work” test and fail the interview.

Step 1Understand the problem

Picture the real thing first

Two people, a 3×3 grid drawn on paper. One draws crosses, the other noughts. They take turns. Whoever gets three in a row, across, down or diagonally, wins. If the grid fills up first, it’s a draw. Someone usually says “wait, let me take that back”, and the other person usually says no.

Even this tiny story has a few hints: grid, turns, three in a row, fills up, take it back. And a few questions it doesn’t answer: Is it always 3×3? Is the other player a person or the computer? Are they at the same screen or on two phones?

Ask before you design

Even for a game everyone knows, ask. The answers here change the design more than you’d expect. Group them: the board, the players, the rules, and how it’s played.

Eight questions. Here’s what each one decided:

Functional requirements

1. FR1. The board is N×N, 3×3 by default. Cells start empty.
2. FR2. Players take turns in a fixed order. Each places their mark in an empty cell.
3. FR3. A player who completes a full row, column or diagonal wins. If the board fills first, it’s a draw.
4. FR4. An invalid move (out of turn, outside the board, taken cell, game over) is rejected with a reason. The game continues.
5. FR5. A player can be a person or a bot.
6. FR6. The last move can be undone, any number of times.
7. FR7. A scoreboard counts wins and draws across games.

Non-functional requirements

1. NFR1: Easy to extend. Bigger boards, new win rules and new kinds of bot are added, not edited in.
2. NFR2: Correct under concurrency. Two requests at once can never break turn order or put two marks in one cell.
3. NFR3: Fast win check. Checking for a win after each move shouldn’t get slower the bigger the board gets, or at least not much.
4. NFR4: Testable. Games can be scripted move by move, and bots can be tested without a person.

Assumptions we’ll write down

Step 2Break it into entities

Pull out the nouns

From the requirements: board, cell, row, column, diagonal, mark, X, O, player, person, bot, turn, move, win, draw, history, scoreboard, game.

Three questions that decide if a noun is a class

For each noun: does it have its own data, its own rules, and will it change on its own?

Two nouns are missing from the requirements and only appear while filling this table: what chooses a bot’s move? and who reacts when a game ends? They become MoveChooser and GameListener.

The trap: a class for X and a class for O

The tempting design gives every noun a class, and every class a subclass:

abstract class Piece { }
class PieceX extends Piece { }
class PieceO extends Piece { }

class Cell { Piece piece; boolean isEmpty() { ... } }
class Board { Cell[][] cells; }

abstract class Player { abstract Move nextMove(Board board); }
class HumanPlayer extends Player { ... }
class BotPlayer extends Player { ... }

Look at what PieceX and PieceO actually do differently. Nothing. The only difference is a character. Two classes for one character is the same mistake as a class per vehicle in the parking lot: inheritance is for different behaviour; when only the data differs, use a field. A mark is a char on the player.

Cell is the same story. It holds one mark and has no rules of its own (the board decides whether a cell can be taken). A char[][] says exactly the same thing, and a 15×15 board doesn’t need 225 objects.

HumanPlayer and BotPlayer are more interesting, because they do behave differently: one waits for a tap, the other computes. So something should vary. But it’s not the player that varies, it’s how the next move is chosen. Split them:

• Player is who you are in this game: a name and a mark. Plain data.
• MoveChooser is how a move gets picked: a person’s taps, a random bot, a perfect bot.

Why bother? Because the two change separately. If a person disconnects, a bot can take over the same Player mid-game and the scoreboard still credits the right name. With HumanPlayer extends Player, you’d have to swap the whole player object. And the game itself never needs to know which kind of chooser is involved: on an online server, the game just receives moves.

Pull out the verbs

Place a mark, check the cell is empty, check it’s your turn, check for a win, check for a draw, pass the turn, undo, choose a move, record a result.

Grouped into use cases:

Give each job to the class that knows the most

Notice that Game doesn’t check for wins itself, and Board doesn’t know whose turn it is. Each keeps one kind of rule.

CRC cards

Find what will change

Things that won’t change get no interface: the board, a move, a player.

Step 3Top-down or bottom-up?

Top-down asks what the outside world calls. A player’s device calls play(player, row, col), so Game.play exists. To play, the game needs to know if a cell is free, so Board.isEmpty exists. To know if the move won, it needs a WinRule. To run a game against a bot, something needs to keep asking the bot for moves, so Match exists.

Bottom-up starts from the pieces that must be right first: the board, then the win rule (tested on its own on hundreds of random boards), then the game on top.

Same answer as most LLD problems: design top-down, code bottom-up. Say it out loud in the interview. It takes five seconds and shows you have a plan.

Step 4Design each class

Game: the referee

Job: own one game’s rules: whose turn it is, whether a move is allowed, and whether the game has ended.

Two decisions. First, play returns a MoveResult (OK, game over, not your turn, outside the board, cell taken) instead of throwing exceptions. A player tapping a taken cell is not a bug; it happens all the time. Exceptions are for things that should never happen, like the board being asked to overwrite a mark after the game has already checked it was empty.

Second, Game is the only class that changes the board. Bots and the UI get a read-only view, so a buggy bot can’t place two marks.

Board and BoardView: the grid

Job: hold the marks and answer simple questions about cells.

BoardView is an interface with only the reading methods. Board implements it. Anyone outside the game (bots, the UI, the win rule) receives a BoardView, so the type system itself stops them from changing the board. That’s the interface segregation principle from chapter 2 doing real work.

Why keep a filled counter instead of scanning for empty cells? The game asks “is it full?” after every move, and the counter makes that instant.

WinRule and LineCounter: what counts as a win

Job: after a move is placed, say whether it completed a winning line.

WinRule is an interface with isWinningMove(board, move) and a default undo(move) that does nothing. Rules that keep their own state, like LineCounter, override it.

The key insight, which deserves a whole section in step 8: a move can only complete lines that pass through it. So there’s never a reason to look at the whole board. LineCounter goes one step further and keeps a running count of each player’s marks in each row, column and diagonal. A move adds one to at most four counters, and a count reaching N means a win. That’s constant time, whatever the board size.

Player, Move, GameState, MoveResult: the vocabulary

Player is a record of name and mark. Move is a record of row, column and player. GameState is an enum: in progress, won, draw. MoveResult is an enum of every outcome of play. All of them are values: once made, they never change.

MoveChooser and Match: who picks the move

MoveChooser has one method, choose(boardView, myMark), returning a cell. RandomChooser picks any empty cell. Later, PerfectChooser never loses.

Match is a small loop for offline games: ask the current player’s chooser for a cell, call game.play, repeat until the game ends. On the online server, there’s no Match. Moves arrive as requests and go straight to game.play. That’s why the loop lives outside Game: the game works the same either way.

GameListener and Scoreboard: reacting to results

GameListener has two methods with empty defaults: moved and finished. Scoreboard implements finished and counts. The game calls every listener without knowing what they are, so adding a rating system later is a new listener, not an edit to Game.

Step 5How the classes relate

The composition test: if the game disappears, does the part disappear too? The board does: it has no meaning outside its game. The players don’t: Asha plays tomorrow’s game too.

Step 6The class diagram, built up

Version 1: what a game is made of

Version 2: the parts that change

The win check and move choosing come out as interfaces, and the board gets a read-only face.

Version 3: the whole picture

The records and enums (Player, GameState, MoveResult) are left off to keep the picture readable. Say so when you draw it; interviewers don’t want every value type, but they want to know you didn’t forget them.

Check it against the requirements

Step 7The patterns, and why each one is here

The move history is a light form of the Command pattern: each Move is a record of something that was done, kept so it can be undone. We don’t need full command objects with execute() and undo() methods, because there’s only one kind of action. If the game gained several kinds (place, swap, remove a piece), each would become a command class.

Why Game is not a Singleton

“There’s only one game”, so some answers write Game.getInstance(). It’s wrong the moment there are two games, which on an online server is immediately: thousands at once. It also makes tests leak into each other. Create a Game per game and pass it to whoever needs it.

Patterns we deliberately didn’t use

• State, for in progress / won / draw. Three states, and only one of them allows moves. One if at the top of play says that more clearly than three state classes would. If the game gained phases with very different rules (a setup phase, a swap phase), State would earn its place.
• Factory. Game.classic(x, o) is a static method that sets up the usual 3×3 game. That’s enough; there’s no family of games to choose between.
• Builder. Three constructor arguments don’t need one.

Step 8Walk the flows

A move

1. The client sends who is playing and where. On the server, “who” comes from the logged-in session, never from the request body, so nobody can play as someone else.
2. The checks run in a deliberate order: game over first, then turn, then the cell. A finished game should say “game over”, not “not your turn”, and a player moving out of turn should hear that before they hear the cell is taken.
3. Only after every check passes does anything change.
4. The win rule runs after the mark is placed. That’s in its contract, and the order matters: a rule that looks at the board would miss the new mark otherwise.
5. The turn only passes if the game goes on. After a win, current() still points at the winner, which is what an undo needs.

A winning move

Here’s the story game from step 9, at the moment Asha wins. She played X at (1,1) and (0,2), Ravi played O at (0,0) and (1,0). Ravi is now threatening the left column, so Asha blocks at (2,0):

O . X
O X .
X . .

The block completes the other diagonal, (0,2), (1,1), (2,0). The win rule sees Asha’s anti-diagonal count reach 3. The game sets its state to WON, records Asha as the winner, doesn’t pass the turn, tells listeners about the move and then about the finish. The scoreboard adds a win for Asha.

How the win check works

This is the part of tic-tac-toe interviewers like to dig into, so it’s worth understanding properly. There are three ways to check for a win, and they get faster in this order:

The idea behind the second and third: a move can only complete a line that passes through it. If Asha’s move at (2,0) wins, the winning line must be row 2, column 0, or the anti-diagonal. Nothing else on the board changed.

The counting version keeps, for each player, a count of their marks in each row, each column and the two diagonals. Placing at (r, c) adds one to row r and column c, plus a diagonal if the cell is on one (r = c for the main diagonal, r + c = N − 1 for the other). A count reaching N is a win. Undo subtracts the same counts.

We measured all three, filling a whole board with random moves and checking after every one (the best of three runs):

n=30   counters=0.1 ms  scan-from-move=0.1 ms  whole-board=0.8 ms
n=100  counters=1.2 ms  scan-from-move=1.5 ms  whole-board=73.5 ms
n=300  counters=3.4 ms  scan-from-move=5.7 ms  whole-board=skipped

On a 100×100 board, scanning the whole board after every move is about 60 times slower than counting. For 3×3 none of this matters (all three are instant), so be honest about that in the interview. But the question “how would you make the win check fast?” is asked almost every time, and “only the lines through the last move” is the answer they want. We also ran all three rules on 20,000 random games of sizes 3 to 6 and they agreed on every single move.

Undo

Two details here came from walking the flow. First, the win rule must also undo. LineCounter keeps counts; if undo clears the board but not the counts, the next mark in that row wins a game nobody won. That’s why WinRule has an undo method at all. Second, the turn goes back to whoever made the undone move, not to “the previous player”. With two players those are the same, but with three they aren’t, and with a finished game the turn never moved on in the first place.

What walking the flows taught us

The life of a game

When things go wrong

Every rejection leaves the game exactly as it was. That’s a property worth saying out loud: nothing changes until every check has passed.

Step 9Write the code, bottom-up

Each class below only uses classes written before it. Put together, this is complete Java that compiles and runs, and every output on this page comes from running it.

9.1 The vocabulary

record Player(String name, char mark) { }

record Move(int row, int col, Player player) { }

enum GameState { IN_PROGRESS, WON, DRAW }

enum MoveResult { OK, GAME_OVER, NOT_YOUR_TURN, OUTSIDE_BOARD, CELL_TAKEN }

9.2 The board

interface BoardView {
    int size();
    boolean inside(int row, int col);
    boolean isEmpty(int row, int col);
    char at(int row, int col); 1
}

final class Board implements BoardView {
    private final int size;
    private final char[][] cells;
    private int filled;

    Board(int size) {
        if (size < 3) throw new IllegalArgumentException("size must be at least 3");
        this.size = size;
        this.cells = new char[size][size];
    }

    public int size() { return size; }
    public boolean inside(int r, int c) {
        return r >= 0 && r < size && c >= 0 && c < size;
    }
    public boolean isEmpty(int r, int c) { return cells[r][c] == 0; }
    public char at(int r, int c) { return cells[r][c]; }

    void place(int r, int c, char mark) {
        if (!isEmpty(r, c)) throw new IllegalStateException("cell taken");   // (2)
        cells[r][c] = mark;
        filled++;
    }

    void clear(int r, int c) {
        if (isEmpty(r, c)) return;
        cells[r][c] = 0;
        filled--;
    }

    boolean isFull() { return filled == size * size; }

    @Override public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) sb.append(isEmpty(r, c) ? '.' : cells[r][c]);
            if (r < size - 1) sb.append('\n');
        }
        return sb.toString();
    }
}

1. A Java char starts as 0, so a fresh grid is already empty. No loop needed.
2. place and clear have no public: only code in the same package (the game) can call them. The game always checks the cell first, so if this exception ever fires, it’s a bug in our code, not a player’s mistake.

9.3 The win rule

interface WinRule {
    boolean isWinningMove(BoardView board, Move move); 1
    default void undo(Move move) { } 2
}

final class LineCounter implements WinRule {
    private final int n;
    private final Mapint[]> rows = new HashMap<>();
    private final Mapint[]> cols = new HashMap<>();
    private final Mapint[]> diags = new HashMap<>(); 3

    LineCounter(int n) { this.n = n; }

    public boolean isWinningMove(BoardView board, Move m) {
        return add(m, +1);
    }

    public void undo(Move m) { add(m, -1); }

    private boolean add(Move m, int delta) {
        char k = m.player().mark();
        int[] row = rows.computeIfAbsent(k, x -> new int[n]);
        int[] col = cols.computeIfAbsent(k, x -> new int[n]);
        int[] diag = diags.computeIfAbsent(k, x -> new int[2]);
        row[m.row()] += delta;
        col[m.col()] += delta;
        if (m.row() == m.col()) diag[0] += delta;
        if (m.row() + m.col() == n - 1) diag[1] += delta; 4
        return row[m.row()] == n || col[m.col()] == n || diag[0] == n || diag[1] == n;
    }
}

1. The contract is written on the interface, because the game and every rule must agree on it.
2. A default method means stateless rules (like the scan-from-move rule in step 11) don’t have to write an empty undo.
3. Counts are kept per mark, in maps. A common trick is one shared count, +1 for X and −1 for O, with a win at ±N. It’s neat, but it only works for exactly two players. Per-mark counts cost a little more memory and make three players free.
4. The centre of an odd board is on both diagonals, so these are two separate ifs, not if/else.

9.4 The game

interface GameListener {
    default void moved(Game game, Move move) { }
    default void finished(Game game, GameState state, Player winner) { }
}

final class Game {
    private final Board board;
    private final List players;
    private final WinRule rule;
    private final Deque history = new ArrayDeque<>();
    private final List listeners = new CopyOnWriteArrayList<>();
    private int turn;
    private GameState state = GameState.IN_PROGRESS;
    private Player winner;

    Game(int size, List players, WinRule rule) {
        if (players.size() < 2) throw new IllegalArgumentException("need two players");
        long marks = players.stream().map(Player::mark).distinct().count();
        if (marks != players.size())
            throw new IllegalArgumentException("marks must differ");
        this.board = new Board(size);
        this.players = List.copyOf(players);
        this.rule = rule;
    }

    static Game classic(Player x, Player o) {
        return new Game(3, List.of(x, o), new LineCounter(3));
    }

    void subscribe(GameListener l) { listeners.add(l); }

    synchronized MoveResult play(Player p, int row, int col) {
        if (state != GameState.IN_PROGRESS) return MoveResult.GAME_OVER;   // (1)
        if (!p.equals(players.get(turn))) return MoveResult.NOT_YOUR_TURN;
        if (!board.inside(row, col)) return MoveResult.OUTSIDE_BOARD;
        if (!board.isEmpty(row, col)) return MoveResult.CELL_TAKEN;

        Move move = new Move(row, col, p);
        board.place(row, col, p.mark());
        history.push(move);
        if (rule.isWinningMove(board, move)) {
            state = GameState.WON;
            winner = p;
        } else if (board.isFull()) {
            state = GameState.DRAW;
        } else {
            turn = (turn + 1) % players.size();                           // (2)
        }
        for (GameListener l : listeners) l.moved(this, move);
        if (state != GameState.IN_PROGRESS)
            for (GameListener l : listeners) l.finished(this, state, winner);
        return MoveResult.OK;
    }

    synchronized boolean undo() {
        if (history.isEmpty()) return false;
        Move last = history.pop();
        board.clear(last.row(), last.col());
        rule.undo(last);                                                  // (3)
        state = GameState.IN_PROGRESS;
        winner = null;
        turn = players.indexOf(last.player());                            // (4)
        return true;
    }

    synchronized GameState state() { return state; }
    synchronized Player winner() { return winner; }
    synchronized Player current() { return players.get(turn); }
    synchronized List moves() {
        List out = new ArrayList<>(history);
        Collections.reverse(out);
        return out;
    }
    BoardView board() { return board; }
    List players() { return players; }
    @Override public synchronized String toString() { return board.toString(); }
}

1. Game over first, then turn, then the cell, as in step 8. Every check returns before anything changes.
2. The turn only moves if the game goes on.
3. Without this line, undo would leave the counters one too high, and a later move could “win” with only two marks in a row.
4. The player whose move was undone plays again.

synchronized is explained in step 10. Notice that even the small getters are synchronized: reading state while another thread is halfway through play could see a half-finished move.

The constructor checks that every player has a different mark. Two players both using X would make the win rule credit wins to the wrong person. Failing loudly when the game is created is much better than a confusing scoreboard later.

9.5 Choosing moves

interface MoveChooser {
    int[] choose(BoardView board, char me); 1
}

final class RandomChooser implements MoveChooser {
    private final Random random;
    RandomChooser(Random random) { this.random = random; }

    public int[] choose(BoardView b, char me) {
        List<int[]> free = new ArrayList<>();
        for (int r = 0; r < b.size(); r++)
            for (int c = 0; c < b.size(); c++)
                if (b.isEmpty(r, c)) free.add(new int[] { r, c });
        return free.get(random.nextInt(free.size()));
    }
}

final class Match {
    private final Game game;
    private final Map choosers;

    Match(Game game, Map choosers) {
        this.game = game;
        this.choosers = Map.copyOf(choosers);
    }

    Player playOut() {
        while (game.state() == GameState.IN_PROGRESS) {
            Player p = game.current();
            int[] cell = choosers.get(p).choose(game.board(), p.mark());
            MoveResult r = game.play(p, cell[0], cell[1]);
            if (r != MoveResult.OK) throw new IllegalStateException(p.name() + ": " + r);
        }
        return game.winner();                                             // (2)
    }
}

1. The chooser gets a BoardView. Even if a bot wanted to place two marks, it has no method to do it with.
2. null means a draw. A bot that returns a bad cell is a bug, so Match throws rather than looping forever.

The Random is passed in, not created inside. Tests can pass new Random(42) and get the same games every run (NFR4).

9.6 The scoreboard

final class Scoreboard implements GameListener {
    private final Map wins = new TreeMap<>();
    private int draws;

    public synchronized void finished(Game g, GameState s, Player winner) {
        if (s == GameState.DRAW) draws++;
        else wins.merge(winner.name(), 1, Integer::sum);
    }

    @Override public synchronized String toString() {
        return "wins=" + wins + ", draws=" + draws;
    }
}

One scoreboard listens to many games, and on a server those games finish on different threads. So it has its own lock.

9.7 Putting it together

The story game from step 8, with every kind of rejected move, then an undo:

public class Demo {
    public static void main(String[] args) {
        Player asha = new Player("Asha", 'X'), ravi = new Player("Ravi", 'O');
        Game g = Game.classic(asha, ravi);
        System.out.println("X (1,1): " + g.play(asha, 1, 1));
        System.out.println("X again: " + g.play(asha, 0, 0));
        System.out.println("O (1,1): " + g.play(ravi, 1, 1));
        System.out.println("O (3,0): " + g.play(ravi, 3, 0));
        g.play(ravi, 0, 0);
        g.play(asha, 0, 2);
        g.play(ravi, 1, 0);
        System.out.println("X (2,0): " + g.play(asha, 2, 0));
        System.out.println(g.state() + ", winner " + g.winner().name());
        System.out.println(g);
        System.out.println("O (2,2): " + g.play(ravi, 2, 2));
        g.undo();
        System.out.println("after undo: " + g.state() + ", "
            + g.current().name() + " to play");

        Scoreboard score = new Scoreboard();
        Random random = new Random(42);
        for (int i = 0; i < 10_000; i++) {
            Game m = Game.classic(asha, ravi);
            m.subscribe(score);
            new Match(m, Map.of(asha, new RandomChooser(random),
                                ravi, new RandomChooser(random))).playOut();
        }
        System.out.println("10,000 random games: " + score);
    }
}

The output:

X (1,1): OK
X again: NOT_YOUR_TURN
O (1,1): CELL_TAKEN
O (3,0): OUTSIDE_BOARD
X (2,0): OK
WON, winner Asha
O.X
OX.
X..
O (2,2): GAME_OVER
after undo: IN_PROGRESS, Asha to play
10,000 random games: wins={Asha=5801, Ravi=2923}, draws=1276

That last line is a nice sanity check. When both players move at random, the first player wins about 58% of games, the second about 29%, and about 13% are draws. Those are the known figures for random tic-tac-toe, which tells us the rules and the win check are right.

Step 10Make it safe when moves arrive at once

The race: a double click

The bug that really happens: Asha’s connection is slow, so she taps twice, or taps two different cells. Two requests arrive at the same instant:

Asha has played twice, and depending on timing, the turn may have advanced twice, back to her. Try it:

We tested it: 100,000 trials of two simultaneous requests from the same player. Without a lock, Asha got two moves in between 1 and 3 of every 100,000 trials, depending on the run. With synchronized, it never happened.

That rarity is the dangerous part. A bug that shows up a few times in 100,000 passes every test you write by hand, and then a busy server with thousands of games hits it every day.

Why one lock per game

Everything in the table above belongs to one game. The turn check and the board update must happen as one step, so they need the same lock. Making play synchronized does exactly that: the game object is the lock.

The lesson that carries to other problems: find what the conflicting operations actually share, and lock exactly that. In the parking lot it was one spot. Here it’s one game.

Prove it

This test plays 2,000 games, each with two threads hammering random cells as fast as they can, and then checks that every game’s moves strictly alternate:

2000 games, two threads each: finished=2000, out-of-turn moves=0

Step 11Follow-ups, extended without editing

A bigger board, and five in a row

That’s gomoku, and it breaks LineCounter: counting marks in a row of 15 can’t tell five together from five scattered.

Bad solutionCopy Game and change the loops

A GomokuGame with its own hard-coded checks. Two copies of the turn logic, the undo logic and the concurrency, and every bug fixed twice.

Good solutionScan the whole board for five in a row

Correct, and it fits behind WinRule. But it looks at every cell after every move: on a 15×15 board, 225 cells to find out whether the one cell that changed made a line.

Great solutionA new rule that scans from the last move

Same idea as before: a move can only complete a line through it. Walk outwards from the move in both directions along each of the four lines, and count matching marks. It’s a new class; Game doesn’t change at all.

final class KInARow implements WinRule {
    private static final int[][] DIRECTIONS = { {0, 1}, {1, 0}, {1, 1}, {1, -1} };
    private final int k;

    KInARow(int k) { this.k = k; }

    public boolean isWinningMove(BoardView b, Move m) {
        char mark = m.player().mark();
        for (int[] d : DIRECTIONS) {
            int line = 1 + count(b, m, d[0], d[1], mark)
                         + count(b, m, -d[0], -d[1], mark);
            if (line >= k) return true;                                    // (1)
        }
        return false;
    }

    private int count(BoardView b, Move m, int dr, int dc, char mark) {
        int n = 0, r = m.row() + dr, c = m.col() + dc;
        while (n < k - 1 && b.inside(r, c) && b.at(r, c) == mark) {
            n++;
            r += dr;
            c += dc;
        }
        return n;
    }
}

1. Counting both ways at once matters. If the move lands in the middle of a line (two marks on each side), checking only one direction would miss it.

It keeps no state, so it doesn’t need undo: the default does nothing, and that’s correct. Used as new Game(15, players, new KInARow(5)). In our run, X played (7,7), (8,8), (6,6), (9,9) and then (5,5), filling the gap at the end of the diagonal, and the game reported WON on exactly that move.

This rule also works for ordinary N×N with k = N, and it’s the “scan from the last move” line in the benchmark above: a little slower than counters, but simpler and more general.

A bot that never loses

Tic-tac-toe is small enough to search completely. Minimax tries every possible move, then every reply, and so on to the end of the game, and scores each final position: +1 if the player to move eventually wins, −1 if they lose, 0 for a draw. Each player picks the move that’s best for them, assuming the other does the same.

final class PerfectChooser implements MoveChooser {
    private final Map memo = new HashMap<>();

    public int[] choose(BoardView b, char me) {
        char[][] g = copy(b);
        char them = other(g, me);
        int best = Integer.MIN_VALUE;
        int[] pick = null;
        for (int r = 0; r < 3; r++)
            for (int c = 0; c < 3; c++) {
                if (g[r][c] != 0) continue;
                g[r][c] = me;
                int score = -value(g, them, me);                           // (1)
                g[r][c] = 0;
                if (score > best) { best = score; pick = new int[] { r, c }; }
            }
        return pick;
    }

    // Score for the player about to move: +1 win, 0 draw, -1 loss.
    private int value(char[][] g, char toMove, char other) {
        if (wins(g, other)) return -1;                                     // (2)
        String key = toMove + key(g);
        Integer known = memo.get(key);
        if (known != null) return known;
        int best = Integer.MIN_VALUE;
        boolean moved = false;
        for (int r = 0; r < 3; r++)
            for (int c = 0; c < 3; c++) {
                if (g[r][c] != 0) continue;
                moved = true;
                g[r][c] = toMove;
                best = Math.max(best, -value(g, other, toMove));
                g[r][c] = 0;
            }
        int v = moved ? best : 0;                                          // (3)
        memo.put(key, v);
        return v;
    }

    private static boolean wins(char[][] g, char p) {
        for (int i = 0; i < 3; i++) {
            if (g[i][0] == p && g[i][1] == p && g[i][2] == p) return true;
            if (g[0][i] == p && g[1][i] == p && g[2][i] == p) return true;
        }
        return (g[0][0] == p && g[1][1] == p && g[2][2] == p)
            || (g[0][2] == p && g[1][1] == p && g[2][0] == p);
    }

    private static char[][] copy(BoardView b) {
        if (b.size() != 3) throw new IllegalArgumentException("3x3 only");
        char[][] g = new char[3][3];
        for (int r = 0; r < 3; r++)
            for (int c = 0; c < 3; c++) g[r][c] = b.at(r, c);
        return g;
    }

    private static char other(char[][] g, char me) {
        for (char[] row : g) for (char ch : row) if (ch != 0 && ch != me) return ch;
        return me == 'X' ? 'O' : 'X';
    }

    private static String key(char[][] g) {
        StringBuilder sb = new StringBuilder(9);
        for (char[] row : g) for (char ch : row) sb.append(ch == 0 ? '.' : ch);
        return sb.toString();
    }
}

1. A position that’s good for the opponent is bad for us by the same amount, so one function with a minus sign handles both players. This form of minimax is called negamax.
2. If the player who just moved has won, the player to move has lost.
3. A full board with no winner is a draw.

The bot works on its own copy of the board, so searching never touches the real game. The memo map remembers positions it has already scored: tic-tac-toe has only a few thousand reachable positions, so after the first game every answer is instant.

The results, from real runs:

perfect vs perfect, 100 games: wins={}, draws=100
perfect (Asha) vs random, 2,000 games: wins={Asha=1807}, draws=193

Two perfect players always draw, which is the famous result for tic-tac-toe. Against a random player, playing first or second, the bot won 1,807 and drew 193 of 2,000 games, and never lost.

And nothing else changed: it’s one more MoveChooser. Match and Game don’t know it exists. Worth saying: full search only works because the game is tiny. On 15×15 there are far too many positions, so a gomoku bot would search a few moves ahead and score positions with a rule of thumb. That’s another MoveChooser, too.

Three players

Already done. Players are a list, the turn wraps with % players.size(), and LineCounter keeps counts per mark. new Game(4, List.of(a, b, c), new LineCounter(4)) just works. This is where the ±1 counting trick from 9.3 would have broken, and why we avoided it.

Saving and replaying games

The move history is already a complete record: replaying those moves into a new game rebuilds it exactly. So saving a game means saving the list of moves, and loading it means replaying them. This is the same idea as an event log: store what happened, and the current state can always be rebuilt from it. It also gives you a replay feature for free.

A time limit per move

Don’t put a timer inside Game. Pass in a Clock and have the server check, when a move arrives, whether the player’s time ran out; a scheduled job can also end games where nobody moved. The game only needs one new outcome: a player who timed out loses. That’s a new GameState reason and a small method, not a rework.

Mistakes people make on this one

• *Writing one big Game class with a main loop,* reading input and printing the board, with the rules mixed into the loop.
• *PieceX and PieceO classes,* or a Cell object per square, when a char says the same thing.
• *HumanPlayer extends Player,* tying who a player is to how their moves are chosen.
• Scanning the whole board after every move, and not being able to explain why only the lines through the move matter.
• The ±1 counting trick without noticing it limits the game to two players.
• Throwing exceptions for normal bad moves, or worse, changing state before all the checks pass.
• Forgetting that undo must also undo the win rule’s counts.
• No locking in an online game, or a single lock for every game on the server.
• *Making Game a Singleton.*

How this answer gets scored

The whole design on one page

1. Structure: Game owns a Board (behind a read-only BoardView), a list of Players and a history of Moves.
2. A move: check game over, then turn, then cell; place; ask the WinRule; then won, draw, or pass the turn.
3. Win check: only lines through the last move. LineCounter keeps per-mark counts for constant time; KInARow scans outwards for gomoku.
4. What varies: WinRule and MoveChooser are strategies; GameListener lets a Scoreboard react to results.
5. Undo: pop the move, clear the cell, undo the rule, reopen the game, give the turn back.
6. Concurrency: one lock per game, because the turn is what conflicting moves share. Games run in parallel.