Engineering Atlas › Low-Level Design

Code a tic-tac-toe game

14 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Requirements

Functional:

Non-functional:

Out of scope: networking, matchmaking, persistence, an AI opponent and timers. They come up in the Extensibility section, but they don't belong in the core.

Entities and relationships

Start from the nouns in the requirements and keep only the ones that have behaviour or invariants.

A Cell class is a common trap. A cell has no behaviour beyond holding a mark, so a two-dimensional array of marks is clearer and cheaper.

Class diagram

classDiagram
    class Game {
        -Board board
        -Player current
        -GameState state
        -int movesMade
        +move(row, col) GameState
        +currentPlayer() Player
        +state() GameState
    }
    class Board {
        -int n
        +isInside(row, col) bool
        +isEmpty(row, col) bool
        +place(row, col, mark)
        +cell(row, col) Mark
    }
    class Player {
        +String name
        +Mark mark
    }
    class WinDetector {
        <<interface>>
        +record(row, col, mark) bool
    }
    class CounterWinDetector {
        -int n
        -int diag
        -int anti
        +record(row, col, mark) bool
    }
    class Move {
        +int row
        +int col
        +Mark mark
    }
    Game *-- Board
    Game o-- Player
    Game --> WinDetector
    WinDetector <|.. CounterWinDetector
    Game *-- Move : history

Key flows

The only interesting flow is a single move. Every check happens before the board changes, so a rejected move has no side effects.

sequenceDiagram
    participant UI
    participant Game
    participant Board
    participant Win as WinDetector
    UI->>Game: move(row, col)
    Game->>Game: state is IN_PROGRESS?
    Game->>Board: isInside and isEmpty?
    Board-->>Game: ok
    Game->>Board: place(row, col, mark)
    Game->>Win: record(row, col, mark)
    Win-->>Game: won = true or false
    Game->>Game: set WON, DRAW, or switch turn
    Game-->>UI: new state

The order inside the last step matters. Check for a win before you check for a draw, because the move that fills the last cell can also complete a line. That game is a win, not a draw.

Design patterns used and why

Concurrency and edge cases

In a local game one thread drives everything, so there is nothing to lock. In a server, two requests for the same game can arrive at once: a double-clicked button, or both players' clients racing. That is the contention shape. The fix is to serialise moves per game. Use a mutex on the Game object in a single process, or optimistic concurrency in a database: each move carries the expected move number, and the server applies it only if the number still matches. The same version-check pattern protects a shopping cart or a wiki page from lost updates.

Edge cases worth naming before you code:

In the wild

Down the stack

Layer 1The contract

move(row, col) either applies exactly one mark and returns the new state, or raises an error with a reason and changes nothing. Once the state is terminal, it never changes again. Each call runs in constant time regardless of N, so a 1000×1000 board is as cheap per move as a 3×3 one.

Layer 2The mechanism

Give X the value +1 and O the value -1. Keep rows[N], cols[N], diag and anti. A move at (r, c) adds its value to rows[r] and cols[c]. It also adds to diag if r == c, and to anti if r + c == N - 1. A line is complete for X exactly when its counter equals N. That can only happen if all N cells hold X, because any O would pull the sum below N. Only the lines through the latest move can have changed, so you check at most four counters. A naive version rescans the row, column and both diagonals, which is O(N) per move. A full-board rescan is O(N²). LeetCode 348 is this exact counter trick.

Layer 3The machine

For N = 3 the whole state fits in a few cache lines: 9 cells, plus 8 small integers, plus a turn and a state. Every operation is a handful of integer adds that finish in nanoseconds. Even for N = 10,000, the counters take 2 × 10,000 × 4 bytes, about 80 KB, which fits in L2 cache. The grid, at 100 million cells, is what grows. A server holding a million concurrent games cares more about per-object overhead than about the algorithm. In CPython a list of lists of one-character strings costs pointers plus object headers. A flat bytearray of N² bytes would cut that by roughly 8×. Go and TypeScript typed arrays give you the flat layout directly.

Why it's built this way

  • Players expect instant feedback, so a move must cost O(1), not a board scan.
  • O(1) needs incremental state, so you keep counters that change with each move instead of recomputing.
  • Incremental state can drift from the grid if a half-applied move is ever left in place, so you validate completely before mutating anything.
  • Validation and turn order are rules, not data, so they live in Game, and Board stays a dumb container you can reuse for Connect Four or chess.

Extensibility

Variant: snake and ladder board game

A dice-and-board race keeps the same skeleton (a Game that owns the rules, a Board that stores data, an explicit status, validate-then-mutate) but changes three things.

Chance enters the rules. Tic-tac-toe is deterministic: the next state depends only on the move. Here a turn depends on a die roll, so randomness must be injected as a Dice interface that the game asks for the next roll, never a random call inside the rules. Tests and replays pass a scripted sequence. A production server draws from a server-side generator and logs every roll, because Python's general-purpose random module is documented as unsuitable for security purposes, while Go's math/rand/v2 top-level functions use a stronger default source. Reject a roll outside 1 to 6 and leave the game unchanged.

The board is a lookup table, not a counter set. Treat a snake and a ladder as one thing, a jump from a start cell to an end cell. Store dest[0..N] with dest[i] = i and one overwritten entry per jump. A move is pos = dest[pos + roll], still O(1), and snakes and ladders differ only in direction. Validate at build time: jumps inside the board, a snake ending below its start, a ladder above, at most one jump per cell, and no jump ending on another jump's start unless you define chaining and guard against cycles. Nothing like the win-detection Strategy is needed, because the win rule is "reach cell N".

A turn can contain several moves. Typical house rules make a player roll again after a six, forfeit the turn after three sixes in a row (returning to where the turn began, even after a ladder), and land exactly on N to win. Put these behind a RuleSet strategy with hooks such as onOvershoot and grantsExtraRoll, and return one TurnResult listing each roll, jump and final position, so the UI can animate it. Compute the whole turn in locals and commit once, which keeps the atomicity of tic-tac-toe's move.

Players also have positions, not marks, so turn order is a rotating index over two or more players, and there is no draw. Online play adds a turn number to each request to reject stale ones, plus an idempotency key so a retried request returns the stored TurnResult instead of rolling again. With a seeded die the board is also a Markov chain, so a million simulated games can be compared against the analytic expected game length to check a layout.

Leadership lens

Check yourself

  1. Why can't a row counter reach +N unless every cell in that row is X?

    Show answer

    Each X adds 1 and each O subtracts 1. Empty cells add 0, so the sum reaches N only when all N cells contribute +1.

  2. The last empty cell is filled and that move also completes a diagonal. What should the game report, and what ordering in the code guarantees it?

    Show answer

    A win. Check for a win before you check whether the board is full.

  3. Why do the line counters fail for "5 in a row on a 15×15 board"?

    Show answer

    A counter summarises an entire line. A row holding five Xs and some Os, or five Xs that aren't contiguous, gives sums that can't tell you whether five Xs sit next to each other. You have to count consecutive marks outward from the last move.

  4. Two HTTP requests try to make a move in the same game at the same moment. What goes wrong without coordination, and what is a cheap fix?

    Show answer

    Both can pass validation against the same old state, so one player moves twice or two marks land on one turn. Serialise per game with a lock, or require an expected move number and reject stale requests.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →