LayoffReady

Design Tic-Tac-Toe

Easyobject-oriented design · design patterns · strategy pattern · game design · java⏱ 13 min readAsked at Amazon, Microsoft, Google, Meta, AppleUpdated

Model an N x N tic-tac-toe game with players, pluggable bot strategies and an O(1) win check driven by row, column and diagonal counters.

Requirements

Tic-tac-toe looks trivial, which is exactly why interviewers use it: the rules are known, so the whole conversation is about clean responsibilities, a fast win check and room for extension. Confirm the scope first.

Functional

  • A board of configurable size N x N (3 by default). A player wins by filling a whole row, column or diagonal.
  • Two players take turns, marked X and O. A player is either a human (moves supplied from outside) or a bot.
  • Reject invalid moves: out of bounds, occupied cell, playing out of turn, or moving after the game is over.
  • Detect win and draw immediately after each move.
  • Bots use a swappable strategy (random, rule-based, minimax for small boards).
  • Support undo of the last move and reset for a new game.

Non-functional

  • Each move, including the win check, runs in O(1) time regardless of N.
  • The core engine has no console or UI code, so it can back a CLI, a web socket server or a test.
  • Adding a new bot level or a new player type should not touch Game or Board.

Out of scope (confirm)

  • Networking, matchmaking, leaderboards, a "K in a row" variant (we mention it under Extensions).
Tip

Ask "is the board always 3 x 3?" early. If the interviewer says N x N, the naive "scan all lines after every move" check becomes O(N) or O(N^2) per move, which sets up the counter trick nicely.

Core Entities

Entity Responsibility Key fields
Symbol (enum) The mark in a cell; knows its opponent and its counter sign X(+1), O(-1)
GameStatus (enum) Lifecycle state IN_PROGRESS, X_WON, O_WON, DRAW
Move Immutable value: who played where row, col, symbol
Board Grid of cells; validates and places/removes marks; reports emptiness size, cells, filled
WinChecker O(1) line bookkeeping using signed counters rows[], cols[], diag, antiDiag
Player (abstract) Has a name and a symbol; decides a move name, symbol
HumanPlayer Plays moves queued by the UI pending queue
BotPlayer Delegates the choice to a strategy MoveStrategy
MoveStrategy Picks a cell for a bot interface
Game Facade: turn order, validation, status, history, undo, listeners board, players, history

Keep Board dumb (cells only) and put the rules in Game and WinChecker. That separation lets a strategy simulate moves on a copy of the board without triggering game events.

Class Diagram

classDiagram
  class Symbol {
    <<enumeration>>
    X
    O
    +opponent() Symbol
  }
  class GameStatus {
    <<enumeration>>
    IN_PROGRESS
    X_WON
    O_WON
    DRAW
  }
  class Move {
    -int row
    -int col
    -Symbol symbol
  }
  class Board {
    -int size
    -Symbol[][] cells
    -int filled
    +isEmpty(int, int) boolean
    +place(Move) void
    +clear(Move) void
    +isFull() boolean
  }
  class WinChecker {
    -int[] rows
    -int[] cols
    -int diag
    -int antiDiag
    +record(Move) boolean
    +undo(Move) void
  }
  class Player {
    <<abstract>>
    -String name
    -Symbol symbol
    +nextMove(Game) Move
  }
  class HumanPlayer
  class BotPlayer
  class MoveStrategy {
    <<interface>>
    +choose(Board, Symbol) int[]
  }
  class RandomStrategy
  class RuleBasedStrategy
  class GameListener {
    <<interface>>
    +onMove(Move, GameStatus) void
  }
  class Game {
    -Board board
    -WinChecker checker
    -Player[] players
    -Deque history
    -GameStatus status
    +play(Move) GameStatus
    +playTurn() GameStatus
    +undo() void
  }

  Player <|-- HumanPlayer
  Player <|-- BotPlayer
  BotPlayer --> MoveStrategy
  MoveStrategy <|.. RandomStrategy
  MoveStrategy <|.. RuleBasedStrategy
  Game "1" *-- "1" Board
  Game "1" *-- "1" WinChecker
  Game "1" o-- "2" Player
  Game "1" o-- "many" Move
  Game --> GameListener
  Board ..> Move

Design Patterns Used

Pattern Where Why it is justified
Strategy MoveStrategy used by BotPlayer Difficulty levels (random, rule-based, minimax) are interchangeable algorithms; adding "hard mode" is a new class
Template / polymorphism Player.nextMove() Game asks "what is your move?" without caring whether a human or a bot answers
Observer GameListener A console printer, a web socket pusher or a stats tracker can react to moves without the engine knowing about them
Command (light) Move objects in a history stack Each move is a reversible record, which makes undo and replay trivial
Facade Game Callers use play / playTurn / undo and never touch WinChecker directly

The O(1) win check

The standard trick: give X the value +1 and O the value -1. Keep an integer per row, per column and one each for the main and anti-diagonal. When a player marks cell (r, c):

  • add the value to rows[r] and cols[c];
  • if r == c, add it to diag; if r + c == n - 1, add it to antiDiag.

A line is won exactly when its counter reaches +n or -n, because only one symbol can contribute n times to an n-cell line without the other symbol touching it. Each move updates at most four counters, so the check is O(1) time and the counters cost O(n) space. Undo simply subtracts the value again.

Insight

Signed counters work because a line containing both symbols can never reach plus or minus n: every opposing mark pulls the sum one step toward zero. You never need to look at the cells themselves to decide the winner.

A draw is detected when the board is full and nobody won. A sharper interview answer: a line is "dead" once it contains both symbols, and the game is a forced draw when every line is dead. That needs per-line counts of X and O separately, so mention it as an optimisation rather than building it upfront.

Java Implementation

The code compiles as a single Main.java (Java 17+). The demo plays a scripted human-vs-human game, shows undo, rejects bad moves, and then lets a rule-based bot play a random bot on a 4 x 4 board with a fixed seed so output is repeatable.

java
import java.util.*;

enum Symbol {
    X(1), O(-1);
    final int value;
    Symbol(int value) { this.value = value; }
    Symbol opponent() { return this == X ? O : X; }
}

enum GameStatus { IN_PROGRESS, X_WON, O_WON, DRAW }

record Move(int row, int col, Symbol symbol) {}

class Board {
    private final int size;
    private final Symbol[][] cells;
    private int filled;

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

    int size() { return size; }
    boolean inBounds(int r, int c) { return r >= 0 && c >= 0 && r < size && c < size; }
    boolean isEmpty(int r, int c) { return cells[r][c] == null; }
    boolean isFull() { return filled == size * size; }
    Symbol get(int r, int c) { return cells[r][c]; }

    void place(Move m) { cells[m.row()][m.col()] = m.symbol(); filled++; }
    void clear(Move m) { cells[m.row()][m.col()] = null; filled--; }

    List<int[]> emptyCells() {
        List<int[]> out = new ArrayList<>();
        for (int r = 0; r < size; r++)
            for (int c = 0; c < size; c++)
                if (cells[r][c] == null) out.add(new int[]{r, c});
        return out;
    }

    String render() {
        StringBuilder sb = new StringBuilder();
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) sb.append(cells[r][c] == null ? '.' : cells[r][c].name().charAt(0));
            if (r < size - 1) sb.append('\n');
        }
        return sb.toString();
    }
}

// O(1) per move: signed counters per row, column and both diagonals.
class WinChecker {
    private final int n;
    private final int[] rows, cols;
    private int diag, antiDiag;

    WinChecker(int n) { this.n = n; rows = new int[n]; cols = new int[n]; }

    boolean record(Move m) { return apply(m, m.symbol().value); }
    void undo(Move m) { apply(m, -m.symbol().value); }

    private boolean apply(Move m, int v) {
        int r = m.row(), c = m.col();
        rows[r] += v;
        cols[c] += v;
        if (r == c) diag += v;
        if (r + c == n - 1) antiDiag += v;
        return Math.abs(rows[r]) == n || Math.abs(cols[c]) == n
                || Math.abs(diag) == n || Math.abs(antiDiag) == n;
    }
}

interface MoveStrategy {
    int[] choose(Board board, Symbol me);
}

class RandomStrategy implements MoveStrategy {
    private final Random rnd;
    RandomStrategy(long seed) { rnd = new Random(seed); }
    public int[] choose(Board board, Symbol me) {
        List<int[]> empty = board.emptyCells();
        return empty.get(rnd.nextInt(empty.size()));
    }
}

// Win if possible, otherwise block, otherwise take the centre-most free cell.
class RuleBasedStrategy implements MoveStrategy {
    public int[] choose(Board board, Symbol me) {
        int[] win = findFinishingMove(board, me);
        if (win != null) return win;
        int[] block = findFinishingMove(board, me.opponent());
        if (block != null) return block;
        double mid = (board.size() - 1) / 2.0;
        return board.emptyCells().stream()
                .min(Comparator.comparingDouble(p -> Math.abs(p[0] - mid) + Math.abs(p[1] - mid)))
                .orElseThrow();
    }

    private int[] findFinishingMove(Board board, Symbol s) {
        int n = board.size();
        for (int[] cell : board.emptyCells()) {
            WinChecker sim = new WinChecker(n);   // simulate on a scratch checker
            for (int r = 0; r < n; r++)
                for (int c = 0; c < n; c++)
                    if (board.get(r, c) == s) sim.record(new Move(r, c, s));
            if (sim.record(new Move(cell[0], cell[1], s))) return cell;
        }
        return null;
    }
}

abstract class Player {
    private final String name;
    private final Symbol symbol;
    Player(String name, Symbol symbol) { this.name = name; this.symbol = symbol; }
    String name() { return name; }
    Symbol symbol() { return symbol; }
    abstract Move nextMove(Game game);
    @Override public String toString() { return name + "(" + symbol + ")"; }
}

class HumanPlayer extends Player {
    private final Deque<int[]> pending = new ArrayDeque<>();
    HumanPlayer(String name, Symbol symbol) { super(name, symbol); }
    void queue(int r, int c) { pending.add(new int[]{r, c}); }
    Move nextMove(Game game) {
        int[] p = pending.poll();
        if (p == null) throw new IllegalStateException(name() + " has no move queued");
        return new Move(p[0], p[1], symbol());
    }
}

class BotPlayer extends Player {
    private final MoveStrategy strategy;
    BotPlayer(String name, Symbol symbol, MoveStrategy strategy) { super(name, symbol); this.strategy = strategy; }
    Move nextMove(Game game) {
        int[] p = strategy.choose(game.boardView(), symbol());
        return new Move(p[0], p[1], symbol());
    }
}

interface GameListener {
    void onMove(Move move, GameStatus status);
}

class Game {
    private final int size;
    private Board board;
    private WinChecker checker;
    private final Player[] players;
    private final Deque<Move> history = new ArrayDeque<>();
    private final List<GameListener> listeners = new ArrayList<>();
    private GameStatus status = GameStatus.IN_PROGRESS;
    private int turn;

    Game(int size, Player first, Player second) {
        if (first.symbol() == second.symbol()) throw new IllegalArgumentException("Players need different symbols");
        this.size = size;
        this.players = new Player[]{first, second};
        reset();
    }

    void addListener(GameListener l) { listeners.add(l); }
    Player current() { return players[turn]; }
    GameStatus status() { return status; }
    Board boardView() { return board; }   // read-only use by strategies in this demo

    synchronized GameStatus play(Move m) {
        if (status != GameStatus.IN_PROGRESS) throw new IllegalStateException("Game is over: " + status);
        if (m.symbol() != current().symbol()) throw new IllegalStateException("Not " + m.symbol() + "'s turn");
        if (!board.inBounds(m.row(), m.col())) throw new IllegalArgumentException("Out of bounds: " + m);
        if (!board.isEmpty(m.row(), m.col())) throw new IllegalArgumentException("Cell taken: " + m);

        board.place(m);
        history.push(m);
        if (checker.record(m)) status = m.symbol() == Symbol.X ? GameStatus.X_WON : GameStatus.O_WON;
        else if (board.isFull()) status = GameStatus.DRAW;
        else turn = 1 - turn;
        for (GameListener l : listeners) l.onMove(m, status);
        return status;
    }

    GameStatus playTurn() { return play(current().nextMove(this)); }

    synchronized void undo() {
        Move last = history.poll();
        if (last == null) throw new IllegalStateException("Nothing to undo");
        board.clear(last);
        checker.undo(last);
        status = GameStatus.IN_PROGRESS;
        turn = last.symbol() == players[0].symbol() ? 0 : 1;
    }

    synchronized void reset() {
        board = new Board(size);
        checker = new WinChecker(size);
        history.clear();
        status = GameStatus.IN_PROGRESS;
        turn = 0;
    }
}

public class Main {
    public static void main(String[] args) {
        HumanPlayer alice = new HumanPlayer("Alice", Symbol.X);
        HumanPlayer bob = new HumanPlayer("Bob", Symbol.O);
        Game game = new Game(3, alice, bob);
        game.addListener((m, s) -> System.out.println(m.symbol() + " -> (" + m.row() + "," + m.col() + ") status=" + s));

        int[][] script = {{1, 1}, {0, 0}, {0, 2}, {2, 0}, {1, 0}};
        for (int i = 0; i < script.length; i++) {
            (i % 2 == 0 ? alice : bob).queue(script[i][0], script[i][1]);
            game.playTurn();
        }
        System.out.println(game.boardView().render());

        game.undo();
        System.out.println("After undo, " + game.current() + " to move, status=" + game.status());
        try {
            game.play(new Move(1, 1, Symbol.X));
        } catch (IllegalArgumentException e) {
            System.out.println("Rejected: " + e.getMessage());
        }
        alice.queue(2, 2);
        game.playTurn();
        bob.queue(1, 0);
        System.out.println("Final: " + game.playTurn());
        System.out.println(game.boardView().render());
        try {
            game.play(new Move(0, 1, Symbol.X));
        } catch (IllegalStateException e) {
            System.out.println("Rejected: " + e.getMessage());
        }

        Game botGame = new Game(4,
                new BotPlayer("SmartBot", Symbol.X, new RuleBasedStrategy()),
                new BotPlayer("RandomBot", Symbol.O, new RandomStrategy(1)));
        while (botGame.status() == GameStatus.IN_PROGRESS) botGame.playTurn();
        System.out.println("4x4 bot game: " + botGame.status());
        System.out.println(botGame.boardView().render());
    }
}

Demo output

text
X -> (1,1) status=IN_PROGRESS
O -> (0,0) status=IN_PROGRESS
X -> (0,2) status=IN_PROGRESS
O -> (2,0) status=IN_PROGRESS
X -> (1,0) status=IN_PROGRESS
O.X
XX.
O..
After undo, Alice(X) to move, status=IN_PROGRESS
Rejected: Cell taken: Move[row=1, col=1, symbol=X]
X -> (2,2) status=IN_PROGRESS
O -> (1,0) status=O_WON
Final: O_WON
O.X
OX.
O.X
Rejected: Game is over: O_WON
4x4 bot game: X_WON
OOX.
.XX.
.XX.
OOXO

Walkthrough:

  • After X's move at (1,0) is undone, the turn returns to X, and checker.undo subtracts the +1 from row 1 and column 0.
  • O completes column 0, so cols[0] reaches -3 and the game ends; the next move is rejected.
  • On the 4 x 4 board the rule-based bot starts in the centre, builds column 2 and finishes it once it has three marks there and the random bot has not blocked; cols[2] reaches +4.

Concurrency Considerations

A single local game is driven by one thread, so concurrency only matters when moves arrive over the network (two browser tabs, a retried request).

  • play, undo and reset are synchronized on the Game, so validation, placement, counter updates and the turn switch happen as one atomic step. Without that, two requests could both see a cell as empty.
  • The turn check doubles as protection against duplicate submissions: a retried move from the same player fails because it is no longer their turn. For true idempotency, attach a client move ID or the expected move number and ignore repeats.
  • Listeners run inside the lock here for simplicity. In a server, hand events to a queue so a slow socket cannot block gameplay.
  • A game server hosting thousands of games keeps one lock per game, never a global one; games are independent, so they scale horizontally by game ID.
Warning

Strategies receive the live board in this compact demo. In production pass an immutable snapshot (or a copy) so a buggy bot cannot mutate state or read it mid-update.

Extensions

Requirement Change
Win with K in a row on an N x N board (Gomoku-style) Counters no longer suffice; after each move count consecutive same symbols in the 4 directions through the cell, O(K) per move
Unbeatable bot on 3 x 3 MinimaxStrategy with alpha-beta pruning; feasible because the 3 x 3 state space is tiny
More than two players Generalise Symbol to a player ID, keep per-player counters per line (or count distinct owners per line)
Replay and spectators Persist the history of Move commands; spectators subscribe as GameListeners
Timed moves A TurnTimer that auto-forfeits or plays a random move when the clock runs out
Online play Wrap Game in a GameSession keyed by ID, with move version numbers for idempotent retries

Interview Tips

  • Lead with the O(1) counter idea; it is the single detail most interviewers are waiting for on the N x N variant.
  • Keep the board free of rules. Board stores marks; Game enforces turns; WinChecker decides wins.
  • Validate in a clear order (game over, wrong turn, bounds, occupied) and use exceptions or result types consistently.
  • Show that bots are a Strategy, so the interviewer can ask for "hard mode" and you simply add a class.
  • Mention undo early: storing Move objects makes it almost free, and the counters reverse by subtraction.
  • If asked about draws, offer the "every line is dead" early detection as an optimisation.

References

My notes saved in this browser