On this page

Design Tic-Tac-Toe

Tic-Tac-Toe is deceptively simple as a game but surprisingly rich as an LLD problem. It tests your ability to model a clean game loop, implement efficient win detection ( per move instead of ), design for extensibility (arbitrary board sizes), and implement an AI opponent using the minimax algorithm. The problem also naturally leads to discussions about the Strategy pattern for player types and the Observer pattern for game events.

Nearly everyone can make the game work, so that isn't what's being tested. The interviewer watches how you split responsibilities, whether your win check beats a full scan, and whether the design survives the usual follow-ups: "make it N×N", "add a third player", "now it's online". This page follows the LLD interview framework. The original walkthrough code is kept in the implementation section, with corrections marked.

Clarifying questions and requirements

QuestionTypical answerWhy it matters
Is the board always 3×3?Default 3×3, size configurableHard-coding 3 is expensive to undo
Does a full line always win, or k in a row?Full line for nowThe sum trick only works when the win length equals the board size (see Extension A)
How many players?TwoThe ±1 encoding only works for two players (see Extension B)
Humans, AI, or both?Any mixMoves come from a pluggable source: Strategy
Undo?Nice to haveThe board must reverse its win-check state cheaply
Same device, or online?Same device firstOnline means concurrent requests, so validation must be atomic
UI?Console, core UI-agnosticNo printing or input in the core. Notify listeners

Functional Requirements

#RequirementDetails
FR-1Board setupCreate an board (default 3x3)
FR-2Two playersHuman vs Human, Human vs AI, AI vs AI
FR-3Turn managementAlternate turns between players
FR-4Move validationReject moves to occupied cells or out of bounds
FR-5Win detectionDetect row, column, or diagonal completion
FR-6Draw detectionDetect when all cells filled with no winner
FR-7Game resetReset board for a new game
FR-8AI playerComputer opponent using minimax

Non-functional requirements

#RequirementWhat it means for the design
NFR-1Win check in per moveKeep running line sums, never rescan the board
NFR-2Testable without a keyboardPlayers are injected, tests script them
NFR-3Safe under concurrent movesValidate-and-apply is atomic per game
NFR-4Invalid moves change nothingValidate before mutating

Out of scope: rendering, networking, accounts and persistence. Say where each would plug in, and don't build them.

Core entities and relationships

Keep the nouns that have behaviour or state (from nouns to classes).

EntityResponsibilityOwns
MarkX or O, with the ±1 value the sums use
BoardGeometry: cells and running sums. "Did this placement complete a line?" in Cells, line sums, move count
PlayerChooses a move. Human, network, script and AI are implementations
GameRules: turn, game over, result. Applies moves atomically, notifies listenersBoard, players, listeners
GameListenerObserves moves: UI, logger, broadcaster

The key split is Board versus Game. The board knows geometry and doesn't care whose turn it is, so minimax can place any mark anywhere while searching. The game knows the rules. A Game composes its Board and aggregates its players and listeners.

Class diagram

classDiagram
    class Mark {
        <<enumeration>>
        X
        O
        +int value
        +opponent() Mark
    }
    class Position {
        +int row
        +int col
    }
    class GameStatus {
        <<enumeration>>
        IN_PROGRESS
        X_WON
        O_WON
        DRAW
    }
    class Board {
        -int n
        -int moves
        -int diagSum
        -int antiDiagSum
        +place(r, c, mark) bool
        +undo(r, c) void
        +isFull() bool
        +emptyCells() List~Position~
        +copy() Board
    }
    class Player {
        <<interface>>
        +chooseMove(board, me) Position
    }
    class ScriptedPlayer
    class MinimaxPlayer
    class GameListener {
        <<interface>>
        +onMove(mark, at, status) void
    }
    class Game {
        -Mark turn
        -GameStatus status
        +move(mark, row, col) GameStatus
        +playTurn() GameStatus
        +playToEnd() GameStatus
        +addListener(listener) void
    }
    Game *-- Board
    Game o-- "2" Player
    Game o-- "*" GameListener
    Game --> GameStatus
    Player <|.. ScriptedPlayer
    Player <|.. MinimaxPlayer
    Board ..> Mark
    Board ..> Position

The board also holds the grid and one sum per row and per column, left off to keep the diagram readable.

Key flows

Game Flow

sequenceDiagram
    participant P1 as Player X
    participant G as Game
    participant B as Board
    participant P2 as Player O

    G->>P1: getMove(board)
    P1-->>G: (1, 1)
    G->>B: makeMove(1, 1, X)
    B-->>G: no winner
    G->>G: switch turn

    G->>P2: getMove(board)
    P2-->>G: (0, 0)
    G->>B: makeMove(0, 0, O)
    B-->>G: no winner
    G->>G: switch turn

    Note over G: ... more turns ...

    G->>P1: getMove(board)
    P1-->>G: (2, 0)
    G->>B: makeMove(2, 0, X)
    B-->>G: X wins! (anti-diagonal sum = 3)
    G-->>P1: Game over: X wins!

Correction (2026-11-10)

This diagram said "row sum = 3" for the winning move. X's (1,1) and (2,0) share no row. The line they complete with (0,2) is the anti-diagonal, and the label is fixed.

A move from a remote player, including a rejected one

sequenceDiagram
    participant C as Client for O
    participant G as Game
    participant B as Board
    participant L as Listener
    C->>G: move O at 1,1
    G->>G: lock, check status and turn
    G->>B: place O at 1,1
    B-->>G: throws, cell taken
    G-->>C: error, nothing changed, still O to move
    C->>G: move O at 2,2
    G->>G: lock, check status and turn
    G->>B: place O at 2,2
    B-->>G: false, no line completed
    G->>G: board not full, so turn passes to X, unlock
    G->>L: onMove with O, 2,2 and IN_PROGRESS
    G-->>C: IN_PROGRESS

An AI turn

sequenceDiagram
    participant G as Game
    participant AI as MinimaxPlayer
    participant S as Board snapshot
    G->>G: lock, read turn, copy the board, unlock
    G->>AI: chooseMove with the snapshot
    loop each empty cell
        AI->>S: place the mark
        AI->>AI: negamax on the opponent's replies
        AI->>S: undo the mark
    end
    AI-->>G: best position
    G->>G: move re-validates and applies it

Game lifecycle

stateDiagram-v2
    [*] --> InProgress
    InProgress --> InProgress: valid move, no line, board not full
    InProgress --> XWon: X completes a line
    InProgress --> OWon: O completes a line
    InProgress --> Draw: board full and no line
    XWon --> [*]
    OWon --> [*]
    Draw --> [*]

Every state behaves the same way, so an enum and one guard beat the State pattern here.

O(1) Win Detection

The naive approach to checking for a win scans all rows, columns, and diagonals after each move: per move, or if you scan the entire board. The elegant approach maintains running sums.

The Trick

Assign Player X a value of and Player O a value of . Maintain:

  • A sum for each row
  • A sum for each column
  • A sum for the main diagonal
  • A sum for the anti-diagonal

When a player places a mark, add their value to the relevant row, column, and (if applicable) diagonal sums. If any sum reaches or , that player has won.

graph TD
    subgraph "Win Detection Sums (3x3 board)"
        R["Row sums: [r0, r1, r2]"]
        C["Col sums: [c0, c1, c2]"]
        D["Diagonal sum: d"]
        AD["Anti-diagonal sum: ad"]
    end

    M["Player X plays (1,2)"] --> R
    M --> C
    M -.->|"if row == col"| D
    M -.->|"if row + col == n-1"| AD

A worked example

The sums on a 3×3 board as X (+1) and O (−1) alternate, with changed values in bold:

MoveRow sumsColumn sumsDiagonalAnti-diagonalResult
X at (1,1)0, 1, 00, 1, 011centre is on both diagonals
O at (0,0)−1, 1, 0−1, 1, 001
X at (0,2)0, 1, 0−1, 1, 102
O at (2,2)0, 1, −1−1, 1, 0−12
X at (2,0)0, 1, 00, 1, 0−13, so X wins

A sum of 0 can mean "empty" or "one of each". That's fine, because we only ask whether the magnitude equals .

Why it's correct, and why only lines through the move

Each cell contributes +1, −1 or 0, so a line of cells sums to only if every cell holds the same mark. The invariant is that every sum equals its line's contents: place adds the mark's value and undo subtracts it. A move can only change the lines through it, so those 2 to 4 sums are the only ones to check, whatever the board size.

Cost compared

ApproachTime per moveExtra spaceSupports cheap undo
Scan the whole boardnoneyes, nothing to restore
Scan only the lines through the movenoneyes
Running sums (this design)yes, subtract the value
Walk 4 directions for k in a rownoneyes
Run lengths stored at run endsno

Where the trick stops working

It needs exactly two players, so ±1 can't combine into a false , and a win length equal to the board size, so one sum per line is enough. Drop either and you need Extension A or B. Saying this unprompted shows you understand the trick.

Patterns used, and the alternatives rejected

Design Patterns Used

PatternWhere UsedWhy
StrategyPlayer interface (Human, AI, AIAlphaBeta)Swap player types without changing game logic
ObserverGame events (could notify UI on state changes)Decouple game logic from presentation
Template MethodGame loop structureSame turn flow, different move sources
StateGameStatus transitionsClear game lifecycle states

Correction (2026-11-10)

The last two rows overstated things. There's no Template Method here: playFullGame calls playTurn in a loop, and no subclass overrides a step. GameStatus is an enum checked by a guard, not the State pattern, which needs one object per state with its own behaviour. Both are fine choices, but don't name them as patterns in an interview.

The same decisions as you'd defend them in the room:

PatternWhereWhyAlternative rejected
StrategyPlayerHuman or AI on either side, scriptable in testsif (player.isAI) in the loop, edited for every new player type
ObserverGameListenerUI-agnostic core, spectators laterGame calling a UI directly
CompositionGame composes BoardThe board is reused by search and variantsGame extends Board, which mixes rules into geometry
Not used: StateFour statuses that behave alike. An enum is clearer
Not used: SingletonA server runs many games at once

Implementation

Complete runnable code

Each tab is one self-contained file with the same design. The Java main plays a scripted game, an AI-vs-AI draw and an eight-thread race for the centre. The Python demo plays the first two, and its tests cover the race. The TypeScript file is a module that the tests and Extension C import.

// file: TicTacToe.java
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

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

record Position(int row, int col) {}

enum GameStatus { IN_PROGRESS, X_WON, O_WON, DRAW }

/** Geometry only: cells plus running line sums. Knows nothing about turns. */
final class Board {
    private final int n;
    private final Mark[][] cells;                     // null = empty
    private final int[] rowSum, colSum;
    private int diagSum, antiSum, moves;

    Board(int n) {
        if (n < 1) throw new IllegalArgumentException("size must be at least 1");
        this.n = n;
        cells = new Mark[n][n];
        rowSum = new int[n];
        colSum = new int[n];
    }

    int size() { return n; }
    Mark get(int r, int c) { return cells[r][c]; }
    boolean isFull() { return moves == n * n; }

    /** Returns true if this placement completes a line. O(1). */
    boolean place(int r, int c, Mark m) {
        if (r < 0 || r >= n || c < 0 || c >= n) throw new IllegalArgumentException("off the board");
        if (cells[r][c] != null) throw new IllegalStateException("cell taken");
        cells[r][c] = m;
        moves++;
        return apply(r, c, m.value);
    }

    void undo(int r, int c) {
        Mark m = cells[r][c];
        cells[r][c] = null;
        moves--;
        apply(r, c, -m.value);
    }

    private boolean apply(int r, int c, int d) {
        boolean onDiag = r == c, onAnti = r + c == n - 1;
        rowSum[r] += d;
        colSum[c] += d;
        if (onDiag) diagSum += d;
        if (onAnti) antiSum += d;
        return Math.abs(rowSum[r]) == n || Math.abs(colSum[c]) == n
            || (onDiag && Math.abs(diagSum) == n) || (onAnti && Math.abs(antiSum) == n);
    }

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

    Board copy() {                                    // replaying rebuilds the sums too
        Board b = new Board(n);
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)
                if (cells[r][c] != null) b.place(r, c, cells[r][c]);
        return b;
    }
}

/** Strategy: where the next move comes from. */
interface Player { Position chooseMove(Board board, Mark me); }

final class ScriptedPlayer implements Player {
    private final Deque<Position> script;
    ScriptedPlayer(Position... moves) { script = new ArrayDeque<>(List.of(moves)); }
    public Position chooseMove(Board board, Mark me) { return script.remove(); }
}

/** Perfect play: negamax with alpha-beta pruning. */
final class MinimaxPlayer implements Player {
    public Position chooseMove(Board b, Mark me) {
        Position best = null;
        int alpha = -1000;
        for (Position p : b.emptyCells()) {
            int score = b.place(p.row(), p.col(), me) ? 10 : -negamax(b, me.opponent(), 1, -1000, -alpha);
            b.undo(p.row(), p.col());
            if (best == null || score > alpha) { alpha = score; best = p; }
        }
        return best;
    }

    // Score from the side to move's point of view. Faster wins score higher.
    private int negamax(Board b, Mark toMove, int depth, int alpha, int beta) {
        if (b.isFull()) return 0;
        for (Position p : b.emptyCells()) {
            int score = b.place(p.row(), p.col(), toMove)
                ? 10 - depth : -negamax(b, toMove.opponent(), depth + 1, -beta, -alpha);
            b.undo(p.row(), p.col());
            alpha = Math.max(alpha, score);
            if (alpha >= beta) break;                 // the opponent will never allow this line
        }
        return alpha;
    }
}

/** Observer: UIs, loggers and broadcasters subscribe to moves. */
interface GameListener { void onMove(Mark mark, Position at, GameStatus status); }

final class Game {
    private final Board board;
    private final Map<Mark, Player> players = new EnumMap<>(Mark.class);
    private final List<GameListener> listeners = new CopyOnWriteArrayList<>();
    private Mark turn = Mark.X;
    private GameStatus status = GameStatus.IN_PROGRESS;

    Game(int size, Player x, Player o) {
        board = new Board(size);
        players.put(Mark.X, x);
        players.put(Mark.O, o);
    }

    void addListener(GameListener l) { listeners.add(l); }
    synchronized GameStatus status() { return status; }
    synchronized Mark turn() { return turn; }

    /** The status check, turn check, cell check and write are one atomic step. */
    GameStatus move(Mark mark, int row, int col) {
        GameStatus after;
        synchronized (this) {
            if (status != GameStatus.IN_PROGRESS) throw new IllegalStateException("game over");
            if (mark != turn) throw new IllegalStateException("not " + mark + "'s turn");
            boolean won = board.place(row, col, mark);   // throws before changing anything
            if (won) status = mark == Mark.X ? GameStatus.X_WON : GameStatus.O_WON;
            else if (board.isFull()) status = GameStatus.DRAW;
            else turn = mark.opponent();
            after = status;
        }
        for (GameListener l : listeners) l.onMove(mark, new Position(row, col), after);  // outside the lock
        return after;
    }

    /** The AI searches a snapshot, never the live board, then goes through move() like anyone else. */
    GameStatus playTurn() {
        Mark me;
        Board snapshot;
        synchronized (this) { me = turn; snapshot = board.copy(); }
        Position p = players.get(me).chooseMove(snapshot, me);
        return move(me, p.row(), p.col());
    }

    GameStatus playToEnd() {
        while (status() == GameStatus.IN_PROGRESS) playTurn();
        return status();
    }
}

public class TicTacToe {
    public static void main(String[] args) throws Exception {
        Game g = new Game(3,
            new ScriptedPlayer(new Position(0, 0), new Position(0, 1), new Position(0, 2)),
            new ScriptedPlayer(new Position(1, 0), new Position(1, 1)));
        List<String> seen = new ArrayList<>();
        g.addListener((m, at, s) -> seen.add(m + " " + at));
        if (g.playToEnd() != GameStatus.X_WON || seen.size() != 5) throw new AssertionError("X wins row 0");
        if (new Game(3, new MinimaxPlayer(), new MinimaxPlayer()).playToEnd() != GameStatus.DRAW)
            throw new AssertionError("perfect play draws");

        // Eight threads race to play X in the centre. Exactly one may succeed.
        Game race = new Game(3, null, null);
        AtomicInteger wins = new AtomicInteger();
        CountDownLatch go = new CountDownLatch(1);
        ExecutorService pool = Executors.newFixedThreadPool(8);
        List<Future<?>> done = new ArrayList<>();
        for (int i = 0; i < 8; i++) done.add(pool.submit(() -> {
            go.await();
            try { race.move(Mark.X, 1, 1); wins.incrementAndGet(); } catch (IllegalStateException lost) { }
            return null;
        }));
        go.countDown();
        for (Future<?> f : done) f.get();
        pool.shutdown();
        if (wins.get() != 1 || race.turn() != Mark.O) throw new AssertionError("one winner, got " + wins);
        System.out.println("all checks passed");
    }
}
# file: tic_tac_toe.py
from __future__ import annotations

import copy
import threading
from collections import deque
from dataclasses import dataclass
from enum import Enum
from typing import Callable, Protocol


class Mark(Enum):
    X = 1
    O = -1

    def opponent(self) -> Mark:
        return Mark.O if self is Mark.X else Mark.X


@dataclass(frozen=True)
class Position:
    row: int
    col: int


class GameStatus(Enum):
    IN_PROGRESS = "IN_PROGRESS"
    X_WON = "X_WON"
    O_WON = "O_WON"
    DRAW = "DRAW"


class Board:
    """Geometry only: cells plus running line sums. Knows nothing about turns."""

    def __init__(self, n: int = 3) -> None:
        if n < 1:
            raise ValueError("size must be at least 1")
        self.n = n
        self._cells: list[list[Mark | None]] = [[None] * n for _ in range(n)]
        self._row, self._col = [0] * n, [0] * n
        self._diag = self._anti = self._moves = 0

    def get(self, r: int, c: int) -> Mark | None:
        return self._cells[r][c]

    def in_bounds(self, r: int, c: int) -> bool:
        return 0 <= r < self.n and 0 <= c < self.n

    def is_full(self) -> bool:
        return self._moves == self.n * self.n

    def place(self, r: int, c: int, m: Mark) -> bool:
        """Returns True if this placement completes a line. O(1)."""
        if not self.in_bounds(r, c):
            raise ValueError("off the board")
        if self._cells[r][c] is not None:
            raise ValueError("cell taken")
        self._cells[r][c] = m
        self._moves += 1
        return self._apply(r, c, m.value)

    def undo(self, r: int, c: int) -> None:
        m = self._cells[r][c]
        assert m is not None
        self._cells[r][c] = None
        self._moves -= 1
        self._apply(r, c, -m.value)

    def _apply(self, r: int, c: int, d: int) -> bool:
        n, on_diag, on_anti = self.n, r == c, r + c == self.n - 1
        self._row[r] += d
        self._col[c] += d
        if on_diag:
            self._diag += d
        if on_anti:
            self._anti += d
        return (abs(self._row[r]) == n or abs(self._col[c]) == n
                or (on_diag and abs(self._diag) == n) or (on_anti and abs(self._anti) == n))

    def empty_cells(self) -> list[Position]:
        return [Position(r, c) for r in range(self.n) for c in range(self.n)
                if self._cells[r][c] is None]

    def copy(self) -> Board:
        return copy.deepcopy(self)                # cells and sums, so subclasses work too


class Player(Protocol):
    """Strategy: where the next move comes from."""
    def choose_move(self, board: Board, me: Mark) -> Position: ...


class ScriptedPlayer:
    def __init__(self, *moves: tuple[int, int]) -> None:
        self._script = deque(Position(r, c) for r, c in moves)

    def choose_move(self, board: Board, me: Mark) -> Position:
        return self._script.popleft()


class MinimaxPlayer:
    """Perfect play: negamax with alpha-beta pruning."""

    def choose_move(self, b: Board, me: Mark) -> Position:
        best, alpha = None, -1000
        for p in b.empty_cells():
            won = b.place(p.row, p.col, me)
            score = 10 if won else -self._negamax(b, me.opponent(), 1, -1000, -alpha)
            b.undo(p.row, p.col)
            if best is None or score > alpha:
                best, alpha = p, score
        assert best is not None
        return best

    def _negamax(self, b: Board, to_move: Mark, depth: int, alpha: int, beta: int) -> int:
        if b.is_full():
            return 0
        for p in b.empty_cells():
            won = b.place(p.row, p.col, to_move)
            score = 10 - depth if won else -self._negamax(b, to_move.opponent(), depth + 1, -beta, -alpha)
            b.undo(p.row, p.col)
            alpha = max(alpha, score)
            if alpha >= beta:
                break
        return alpha


Listener = Callable[[Mark, Position, GameStatus], None]


class Game:
    def __init__(self, size: int, x: Player | None, o: Player | None) -> None:
        self._board = Board(size)
        self._players = {Mark.X: x, Mark.O: o}
        self._listeners: list[Listener] = []
        self._turn, self._status = Mark.X, GameStatus.IN_PROGRESS
        self._lock = threading.Lock()

    def add_listener(self, listener: Listener) -> None:
        self._listeners.append(listener)

    @property
    def status(self) -> GameStatus:
        with self._lock:
            return self._status

    @property
    def turn(self) -> Mark:
        with self._lock:
            return self._turn

    def move(self, mark: Mark, row: int, col: int) -> GameStatus:
        with self._lock:                          # check and write as one step
            if self._status is not GameStatus.IN_PROGRESS:
                raise RuntimeError("game over")
            if mark is not self._turn:
                raise RuntimeError(f"not {mark.name}'s turn")
            if self._board.place(row, col, mark):
                self._status = GameStatus.X_WON if mark is Mark.X else GameStatus.O_WON
            elif self._board.is_full():
                self._status = GameStatus.DRAW
            else:
                self._turn = mark.opponent()
            after = self._status
        for listener in self._listeners:          # outside the lock
            listener(mark, Position(row, col), after)
        return after

    def play_turn(self) -> GameStatus:
        with self._lock:
            me, snapshot = self._turn, self._board.copy()
        player = self._players[me]
        assert player is not None
        p = player.choose_move(snapshot, me)      # the AI searches a copy
        return self.move(me, p.row, p.col)

    def play_to_end(self) -> GameStatus:
        while self.status is GameStatus.IN_PROGRESS:
            self.play_turn()
        return self.status


if __name__ == "__main__":
    g = Game(3, ScriptedPlayer((0, 0), (0, 1), (0, 2)), ScriptedPlayer((1, 0), (1, 1)))
    assert g.play_to_end() is GameStatus.X_WON
    assert Game(3, MinimaxPlayer(), MinimaxPlayer()).play_to_end() is GameStatus.DRAW
    print("all checks passed")
// file: ticTacToe.ts
export type Mark = "X" | "O";
export type GameStatus = "IN_PROGRESS" | "X_WON" | "O_WON" | "DRAW";
export interface Position { row: number; col: number }
export const opponent = (m: Mark): Mark => (m === "X" ? "O" : "X");
const VALUE: Record<Mark, number> = { X: 1, O: -1 };

/** Geometry only: cells plus running line sums. Knows nothing about turns. */
export class Board {
  private readonly cells: (Mark | null)[][];
  private readonly rowSum: number[];
  private readonly colSum: number[];
  private diagSum = 0;
  private antiSum = 0;
  private moves = 0;

  constructor(readonly n = 3) {
    if (n < 1) throw new RangeError("size must be at least 1");
    this.cells = Array.from({ length: n }, () => Array<Mark | null>(n).fill(null));
    this.rowSum = Array<number>(n).fill(0);
    this.colSum = Array<number>(n).fill(0);
  }

  get(r: number, c: number): Mark | null { return this.cells[r][c]; }
  isFull(): boolean { return this.moves === this.n * this.n; }

  /** Returns true if this placement completes a line. O(1). */
  place(r: number, c: number, m: Mark): boolean {
    if (r < 0 || r >= this.n || c < 0 || c >= this.n) throw new RangeError("off the board");
    if (this.cells[r][c] !== null) throw new Error("cell taken");
    this.cells[r][c] = m;
    this.moves++;
    return this.apply(r, c, VALUE[m]);
  }

  undo(r: number, c: number): void {
    const m = this.cells[r][c];
    if (m === null) throw new Error("cell already empty");
    this.cells[r][c] = null;
    this.moves--;
    this.apply(r, c, -VALUE[m]);
  }

  private apply(r: number, c: number, d: number): boolean {
    const n = this.n, onDiag = r === c, onAnti = r + c === n - 1;
    this.rowSum[r] += d;
    this.colSum[c] += d;
    if (onDiag) this.diagSum += d;
    if (onAnti) this.antiSum += d;
    return Math.abs(this.rowSum[r]) === n || Math.abs(this.colSum[c]) === n
      || (onDiag && Math.abs(this.diagSum) === n) || (onAnti && Math.abs(this.antiSum) === n);
  }

  emptyCells(): Position[] {
    const out: Position[] = [];
    this.cells.forEach((line, row) => line.forEach((m, col) => { if (m === null) out.push({ row, col }); }));
    return out;
  }

  copy(): Board {
    const b = new Board(this.n);
    this.cells.forEach((line, r) => line.forEach((m, c) => { if (m) b.place(r, c, m); }));
    return b;
  }
}

/** Strategy: where the next move comes from. */
export interface Player { chooseMove(board: Board, me: Mark): Position }

export class ScriptedPlayer implements Player {
  private readonly script: Position[];
  constructor(...moves: [number, number][]) { this.script = moves.map(([row, col]) => ({ row, col })); }
  chooseMove(): Position {
    const next = this.script.shift();
    if (!next) throw new Error("script exhausted");
    return next;
  }
}

/** Perfect play: negamax with alpha-beta pruning. */
export class MinimaxPlayer implements Player {
  chooseMove(b: Board, me: Mark): Position {
    let best: Position | null = null;
    let alpha = -1000;
    for (const p of b.emptyCells()) {
      const score = b.place(p.row, p.col, me) ? 10 : -this.negamax(b, opponent(me), 1, -1000, -alpha);
      b.undo(p.row, p.col);
      if (best === null || score > alpha) { alpha = score; best = p; }
    }
    if (best === null) throw new Error("no legal moves");
    return best;
  }

  private negamax(b: Board, toMove: Mark, depth: number, alpha: number, beta: number): number {
    if (b.isFull()) return 0;
    for (const p of b.emptyCells()) {
      const score = b.place(p.row, p.col, toMove)
        ? 10 - depth : -this.negamax(b, opponent(toMove), depth + 1, -beta, -alpha);
      b.undo(p.row, p.col);
      alpha = Math.max(alpha, score);
      if (alpha >= beta) break;
    }
    return alpha;
  }
}

export type Listener = (mark: Mark, at: Position, status: GameStatus) => void;

export class Game {
  protected readonly board: Board;
  protected turnMark: Mark = "X";
  protected gameStatus: GameStatus = "IN_PROGRESS";
  private readonly listeners: Listener[] = [];

  constructor(size: number, private readonly players: Record<Mark, Player>) {
    this.board = new Board(size);
  }

  addListener(l: Listener): void { this.listeners.push(l); }
  get status(): GameStatus { return this.gameStatus; }
  get turn(): Mark { return this.turnMark; }

  // No lock needed: this synchronous method runs to completion before Node handles
  // another request. An `await` between the checks and the write would break that.
  move(mark: Mark, row: number, col: number): GameStatus {
    if (this.gameStatus !== "IN_PROGRESS") throw new Error("game over");
    if (mark !== this.turnMark) throw new Error(`not ${mark}'s turn`);
    if (this.board.place(row, col, mark)) this.gameStatus = mark === "X" ? "X_WON" : "O_WON";
    else if (this.board.isFull()) this.gameStatus = "DRAW";
    else this.turnMark = opponent(mark);
    for (const l of this.listeners) l(mark, { row, col }, this.gameStatus);
    return this.gameStatus;
  }

  playTurn(): GameStatus {
    const me = this.turnMark;
    const p = this.players[me].chooseMove(this.board.copy(), me);   // the AI searches a copy
    return this.move(me, p.row, p.col);
  }

  playToEnd(): GameStatus {
    while (this.gameStatus === "IN_PROGRESS") this.playTurn();
    return this.gameStatus;
  }
}

Run with javac -d out TicTacToe.java && java -ea -cp out TicTacToe and python tic_tac_toe.py. The TypeScript passes tsc --strict. Compared with the walkthrough below:

  • No EMPTY mark. Empty is null, so place(r, c, EMPTY) can't be written.
  • place validates and throws, so no caller can corrupt the sums.
  • Diagonals are checked only when the move is on them (common mistake 4).
  • Negamax scores from the side to move, which removes the duplicated max and min branches.
  • move(mark, row, col) takes the mark, because on a server the request says who is moving.

Component walkthrough

The original step-by-step TypeScript and Python code follows. We ran it: the TypeScript compiles under tsc --strict, and AI vs AI ends in a draw in both languages. It's a good way to see each piece in isolation before reading the complete files above.

Enums and Types

TypeScript:

enum CellState {
  EMPTY = 0,
  X = 1,
  O = -1,
}

enum GameStatus {
  IN_PROGRESS = "IN_PROGRESS",
  X_WINS = "X_WINS",
  O_WINS = "O_WINS",
  DRAW = "DRAW",
}

interface Position {
  row: number;
  col: number;
}

interface MoveResult {
  valid: boolean;
  status: GameStatus;
  message: string;
}

Python:

from enum import Enum, IntEnum
from dataclasses import dataclass
from abc import ABC, abstractmethod
import math

class CellState(IntEnum):
    EMPTY = 0
    X = 1
    O = -1

class GameStatus(Enum):
    IN_PROGRESS = "IN_PROGRESS"
    X_WINS = "X_WINS"
    O_WINS = "O_WINS"
    DRAW = "DRAW"

@dataclass
class Position:
    row: int
    col: int

@dataclass
class MoveResult:
    valid: bool
    status: GameStatus
    message: str

Board Class

TypeScript:

class Board {
  private grid: CellState[][];
  private rowSums: number[];
  private colSums: number[];
  private diagSum: number = 0;
  private antiDiagSum: number = 0;
  private moveCount: number = 0;
  public readonly size: number;

  constructor(size: number = 3) {
    this.size = size;
    this.grid = Array.from({ length: size }, () =>
      new Array(size).fill(CellState.EMPTY)
    );
    this.rowSums = new Array(size).fill(0);
    this.colSums = new Array(size).fill(0);
  }

  getCell(row: number, col: number): CellState {
    return this.grid[row][col];
  }

  isValidMove(row: number, col: number): boolean {
    return (
      row >= 0 && row < this.size &&
      col >= 0 && col < this.size &&
      this.grid[row][col] === CellState.EMPTY
    );
  }

  /**
   * Place a mark and check for win in O(1).
   * Returns the winner's CellState if someone won, else CellState.EMPTY.
   */
  makeMove(row: number, col: number, player: CellState): CellState {
    this.grid[row][col] = player;
    this.moveCount++;

    this.rowSums[row] += player;
    this.colSums[col] += player;

    if (row === col) {
      this.diagSum += player;
    }
    if (row + col === this.size - 1) {
      this.antiDiagSum += player;
    }

    // Check if this move wins
    if (
      Math.abs(this.rowSums[row]) === this.size ||
      Math.abs(this.colSums[col]) === this.size ||
      Math.abs(this.diagSum) === this.size ||
      Math.abs(this.antiDiagSum) === this.size
    ) {
      return player;
    }

    return CellState.EMPTY;
  }

  undoMove(row: number, col: number, player: CellState): void {
    this.grid[row][col] = CellState.EMPTY;
    this.moveCount--;

    this.rowSums[row] -= player;
    this.colSums[col] -= player;

    if (row === col) {
      this.diagSum -= player;
    }
    if (row + col === this.size - 1) {
      this.antiDiagSum -= player;
    }
  }

  isFull(): boolean {
    return this.moveCount === this.size * this.size;
  }

  getEmptyCells(): Position[] {
    const cells: Position[] = [];
    for (let r = 0; r < this.size; r++) {
      for (let c = 0; c < this.size; c++) {
        if (this.grid[r][c] === CellState.EMPTY) {
          cells.push({ row: r, col: c });
        }
      }
    }
    return cells;
  }

  reset(): void {
    for (let r = 0; r < this.size; r++) {
      for (let c = 0; c < this.size; c++) {
        this.grid[r][c] = CellState.EMPTY;
      }
    }
    this.rowSums.fill(0);
    this.colSums.fill(0);
    this.diagSum = 0;
    this.antiDiagSum = 0;
    this.moveCount = 0;
  }

  display(): string {
    const symbolMap = {
      [CellState.EMPTY]: ".",
      [CellState.X]: "X",
      [CellState.O]: "O",
    };

    let output = "";
    for (let r = 0; r < this.size; r++) {
      output += this.grid[r].map((c) => symbolMap[c]).join(" | ") + "\n";
      if (r < this.size - 1) {
        output += "-".repeat(this.size * 4 - 3) + "\n";
      }
    }
    return output;
  }
}

Python:

class Board:
    def __init__(self, size: int = 3):
        self.size = size
        self.grid = [[CellState.EMPTY] * size for _ in range(size)]
        self.row_sums = [0] * size
        self.col_sums = [0] * size
        self.diag_sum = 0
        self.anti_diag_sum = 0
        self.move_count = 0

    def get_cell(self, row: int, col: int) -> CellState:
        return self.grid[row][col]

    def is_valid_move(self, row: int, col: int) -> bool:
        return (0 <= row < self.size and
                0 <= col < self.size and
                self.grid[row][col] == CellState.EMPTY)

    def make_move(self, row: int, col: int, player: CellState) -> CellState:
        """Place mark, return winner's CellState or EMPTY."""
        self.grid[row][col] = player
        self.move_count += 1

        self.row_sums[row] += player
        self.col_sums[col] += player

        if row == col:
            self.diag_sum += player
        if row + col == self.size - 1:
            self.anti_diag_sum += player

        if (abs(self.row_sums[row]) == self.size or
            abs(self.col_sums[col]) == self.size or
            abs(self.diag_sum) == self.size or
            abs(self.anti_diag_sum) == self.size):
            return player

        return CellState.EMPTY

    def undo_move(self, row: int, col: int, player: CellState) -> None:
        self.grid[row][col] = CellState.EMPTY
        self.move_count -= 1

        self.row_sums[row] -= player
        self.col_sums[col] -= player

        if row == col:
            self.diag_sum -= player
        if row + col == self.size - 1:
            self.anti_diag_sum -= player

    def is_full(self) -> bool:
        return self.move_count == self.size * self.size

    def get_empty_cells(self) -> list[Position]:
        return [
            Position(r, c)
            for r in range(self.size)
            for c in range(self.size)
            if self.grid[r][c] == CellState.EMPTY
        ]

    def reset(self) -> None:
        self.grid = [[CellState.EMPTY] * self.size for _ in range(self.size)]
        self.row_sums = [0] * self.size
        self.col_sums = [0] * self.size
        self.diag_sum = 0
        self.anti_diag_sum = 0
        self.move_count = 0

    def display(self) -> str:
        symbols = {CellState.EMPTY: ".", CellState.X: "X", CellState.O: "O"}
        lines = []
        for r in range(self.size):
            lines.append(" | ".join(symbols[c] for c in self.grid[r]))
            if r < self.size - 1:
                lines.append("-" * (self.size * 4 - 3))
        return "\n".join(lines)

Player Interface (Strategy Pattern)

TypeScript:

interface Player {
  name: string;
  symbol: CellState;
  getMove(board: Board): Position;
}

class HumanPlayer implements Player {
  constructor(
    public readonly name: string,
    public readonly symbol: CellState,
    private inputFn: () => Position
  ) {}

  getMove(board: Board): Position {
    while (true) {
      const pos = this.inputFn();
      if (board.isValidMove(pos.row, pos.col)) {
        return pos;
      }
    }
  }
}

Python:

class Player(ABC):
    def __init__(self, name: str, symbol: CellState):
        self.name = name
        self.symbol = symbol

    @abstractmethod
    def get_move(self, board: Board) -> Position: ...

class HumanPlayer(Player):
    def get_move(self, board: Board) -> Position:
        while True:
            try:
                row = int(input(f"{self.name}, enter row (0-{board.size-1}): "))
                col = int(input(f"{self.name}, enter col (0-{board.size-1}): "))
                if board.is_valid_move(row, col):
                    return Position(row, col)
                print("Invalid move. Try again.")
            except ValueError:
                print("Enter valid numbers.")

AI Player (Minimax Algorithm)

The minimax algorithm plays optimally by exploring all possible future game states. The maximizing player (X) picks the move with the highest score. The minimizing player (O) picks the move with the lowest score.

The depth adjustment ensures the AI prefers faster wins and slower losses.

graph TD
    ROOT["X's turn<br/>max(−1, 0, +1)= +1"] --> A["O's turn<br/>min(+1, −1)= −1"]
    ROOT --> B["O's turn<br/>min(0, 0)= 0"]
    ROOT --> C["O's turn<br/>min(+1, +1)= +1"]

    A --> A1["+1 (X wins)"]
    A --> A2["−1 (O wins)"]
    B --> B1["0 (draw)"]
    B --> B2["0 (draw)"]
    C --> C1["+1 (X wins)"]
    C --> C2["+1 (X wins)"]

    style ROOT fill:#4caf50,color:#fff
    style A fill:#f44336,color:#fff
    style B fill:#f44336,color:#fff
    style C fill:#f44336,color:#fff

TypeScript:

class AIPlayer implements Player {
  constructor(
    public readonly name: string,
    public readonly symbol: CellState
  ) {}

  getMove(board: Board): Position {
    const result = this.minimax(board, this.symbol, 0);
    return result.position!;
  }

  private minimax(
    board: Board,
    currentPlayer: CellState,
    depth: number
  ): { score: number; position: Position | null } {
    const emptyCells = board.getEmptyCells();

    // Terminal states
    if (emptyCells.length === 0) {
      return { score: 0, position: null }; // draw
    }

    const isMaximizing = currentPlayer === this.symbol;
    let bestScore = isMaximizing ? -Infinity : Infinity;
    let bestPosition: Position | null = null;

    for (const cell of emptyCells) {
      // Make move
      const winner = board.makeMove(cell.row, cell.col, currentPlayer);

      let score: number;

      if (winner !== CellState.EMPTY) {
        // Someone won
        score = winner === this.symbol ? 10 - depth : -10 + depth;
      } else {
        // Recurse with opponent
        const opponent = currentPlayer === CellState.X ? CellState.O : CellState.X;
        score = this.minimax(board, opponent, depth + 1).score;
      }

      // Undo move
      board.undoMove(cell.row, cell.col, currentPlayer);

      if (isMaximizing) {
        if (score > bestScore) {
          bestScore = score;
          bestPosition = cell;
        }
      } else {
        if (score < bestScore) {
          bestScore = score;
          bestPosition = cell;
        }
      }
    }

    return { score: bestScore, position: bestPosition };
  }
}

Python:

class AIPlayer(Player):
    def get_move(self, board: Board) -> Position:
        _, position = self._minimax(board, self.symbol, 0)
        return position

    def _minimax(self, board: Board, current_player: CellState,
                 depth: int) -> tuple[int, Position | None]:
        empty_cells = board.get_empty_cells()

        if not empty_cells:
            return 0, None  # draw

        is_maximizing = current_player == self.symbol
        best_score = -math.inf if is_maximizing else math.inf
        best_position: Position | None = None

        for cell in empty_cells:
            winner = board.make_move(cell.row, cell.col, current_player)

            if winner != CellState.EMPTY:
                score = (10 - depth) if winner == self.symbol else (-10 + depth)
            else:
                opponent = CellState.O if current_player == CellState.X else CellState.X
                score, _ = self._minimax(board, opponent, depth + 1)

            board.undo_move(cell.row, cell.col, current_player)

            if is_maximizing:
                if score > best_score:
                    best_score = score
                    best_position = cell
            else:
                if score < best_score:
                    best_score = score
                    best_position = cell

        return best_score, best_position

Minimax Complexity

For a board, minimax explores up to states — fast enough. For larger boards (), add alpha-beta pruning to cut the search space dramatically. Without it, the game tree grows as , which is intractable for .

Correction (2026-11-10)

counts move orders that fill the whole board, but most games end before that, and the search also visits every intermediate position. Measured on the empty board, the minimax above tries 549,945 moves (the full game tree is 549,946 nodes, including the root), not 362,880. The conclusion stands: that's milliseconds of work. "Intractable for " is also a little strong. 4×4 is within reach of alpha-beta plus a transposition table, and it's 5×5 and beyond that need heuristics.

Alpha-Beta Pruning Enhancement

Alpha-beta pruning reduces the minimax search space by maintaining a window . If a branch cannot possibly affect the final decision, it is pruned.

TypeScript:

class AIPlayerAlphaBeta implements Player {
  constructor(
    public readonly name: string,
    public readonly symbol: CellState
  ) {}

  getMove(board: Board): Position {
    const result = this.alphabeta(board, this.symbol, 0, -Infinity, Infinity);
    return result.position!;
  }

  private alphabeta(
    board: Board,
    currentPlayer: CellState,
    depth: number,
    alpha: number,
    beta: number
  ): { score: number; position: Position | null } {
    const emptyCells = board.getEmptyCells();
    if (emptyCells.length === 0) return { score: 0, position: null };

    const isMaximizing = currentPlayer === this.symbol;
    let bestPosition: Position | null = null;

    for (const cell of emptyCells) {
      const winner = board.makeMove(cell.row, cell.col, currentPlayer);
      let score: number;

      if (winner !== CellState.EMPTY) {
        score = winner === this.symbol ? 10 - depth : -10 + depth;
      } else {
        const opponent = currentPlayer === CellState.X ? CellState.O : CellState.X;
        score = this.alphabeta(board, opponent, depth + 1, alpha, beta).score;
      }

      board.undoMove(cell.row, cell.col, currentPlayer);

      if (isMaximizing) {
        if (score > alpha) {
          alpha = score;
          bestPosition = cell;
        }
      } else {
        if (score < beta) {
          beta = score;
          bestPosition = cell;
        }
      }

      if (alpha >= beta) break; // prune
    }

    return {
      score: isMaximizing ? alpha : beta,
      position: bestPosition,
    };
  }
}

Python:

class AIPlayerAlphaBeta(Player):
    def get_move(self, board: Board) -> Position:
        _, position = self._alphabeta(
            board, self.symbol, 0, -math.inf, math.inf
        )
        return position

    def _alphabeta(self, board: Board, current_player: CellState,
                   depth: int, alpha: float, beta: float
                   ) -> tuple[float, Position | None]:
        empty_cells = board.get_empty_cells()
        if not empty_cells:
            return 0, None

        is_maximizing = current_player == self.symbol
        best_position: Position | None = None

        for cell in empty_cells:
            winner = board.make_move(cell.row, cell.col, current_player)

            if winner != CellState.EMPTY:
                score = (10 - depth) if winner == self.symbol else (-10 + depth)
            else:
                opponent = CellState.O if current_player == CellState.X else CellState.X
                score, _ = self._alphabeta(board, opponent, depth + 1, alpha, beta)

            board.undo_move(cell.row, cell.col, current_player)

            if is_maximizing:
                if score > alpha:
                    alpha = score
                    best_position = cell
            else:
                if score < beta:
                    beta = score
                    best_position = cell

            if alpha >= beta:
                break  # prune

        return (alpha if is_maximizing else beta), best_position

Game Controller

TypeScript:

class TicTacToeGame {
  private board: Board;
  private players: [Player, Player];
  private currentPlayerIndex: number = 0;
  private status: GameStatus = GameStatus.IN_PROGRESS;

  constructor(player1: Player, player2: Player, boardSize = 3) {
    this.board = new Board(boardSize);
    this.players = [player1, player2];
  }

  get currentPlayer(): Player {
    return this.players[this.currentPlayerIndex];
  }

  get gameStatus(): GameStatus {
    return this.status;
  }

  playTurn(): MoveResult {
    if (this.status !== GameStatus.IN_PROGRESS) {
      return {
        valid: false,
        status: this.status,
        message: "Game is already over.",
      };
    }

    const player = this.currentPlayer;
    const move = player.getMove(this.board);

    if (!this.board.isValidMove(move.row, move.col)) {
      return {
        valid: false,
        status: GameStatus.IN_PROGRESS,
        message: `Invalid move at (${move.row}, ${move.col})`,
      };
    }

    const winner = this.board.makeMove(move.row, move.col, player.symbol);

    if (winner !== CellState.EMPTY) {
      this.status =
        winner === CellState.X ? GameStatus.X_WINS : GameStatus.O_WINS;
      return {
        valid: true,
        status: this.status,
        message: `${player.name} wins!`,
      };
    }

    if (this.board.isFull()) {
      this.status = GameStatus.DRAW;
      return {
        valid: true,
        status: GameStatus.DRAW,
        message: "It's a draw!",
      };
    }

    // Switch turns
    this.currentPlayerIndex = 1 - this.currentPlayerIndex;
    return {
      valid: true,
      status: GameStatus.IN_PROGRESS,
      message: `${this.currentPlayer.name}'s turn.`,
    };
  }

  playFullGame(): GameStatus {
    while (this.status === GameStatus.IN_PROGRESS) {
      this.playTurn();
    }
    return this.status;
  }

  displayBoard(): string {
    return this.board.display();
  }

  reset(): void {
    this.board.reset();
    this.currentPlayerIndex = 0;
    this.status = GameStatus.IN_PROGRESS;
  }
}

Python:

class TicTacToeGame:
    def __init__(self, player1: Player, player2: Player, board_size: int = 3):
        self.board = Board(board_size)
        self.players = (player1, player2)
        self._current_idx = 0
        self.status = GameStatus.IN_PROGRESS

    @property
    def current_player(self) -> Player:
        return self.players[self._current_idx]

    def play_turn(self) -> MoveResult:
        if self.status != GameStatus.IN_PROGRESS:
            return MoveResult(False, self.status, "Game is already over.")

        player = self.current_player
        move = player.get_move(self.board)

        if not self.board.is_valid_move(move.row, move.col):
            return MoveResult(False, GameStatus.IN_PROGRESS,
                              f"Invalid move at ({move.row}, {move.col})")

        winner = self.board.make_move(move.row, move.col, player.symbol)

        if winner != CellState.EMPTY:
            self.status = (GameStatus.X_WINS if winner == CellState.X
                           else GameStatus.O_WINS)
            return MoveResult(True, self.status, f"{player.name} wins!")

        if self.board.is_full():
            self.status = GameStatus.DRAW
            return MoveResult(True, GameStatus.DRAW, "It's a draw!")

        self._current_idx = 1 - self._current_idx
        return MoveResult(True, GameStatus.IN_PROGRESS,
                          f"{self.current_player.name}'s turn.")

    def play_full_game(self) -> GameStatus:
        while self.status == GameStatus.IN_PROGRESS:
            self.play_turn()
        return self.status

    def reset(self) -> None:
        self.board.reset()
        self._current_idx = 0
        self.status = GameStatus.IN_PROGRESS

Usage Example

TypeScript:

// AI vs AI game
const aiX = new AIPlayer("Bot-X", CellState.X);
const aiO = new AIPlayer("Bot-O", CellState.O);
const game = new TicTacToeGame(aiX, aiO);

const result = game.playFullGame();
console.log(game.displayBoard());
console.log(`Result: ${result}`);
// With perfect play on both sides: always a draw

Complexity Analysis

OperationTimeSpace
Make move (with win check)
Win detection (sum check) for sums
Board display
Minimax (3x3) worst recursion
Minimax with alpha-beta (3x3) recursion
Minimax (NxN) recursion

Correction (2026-11-10)

The alpha-beta row was wrong. There's no "divide by α" cost. With the worst move ordering, alpha-beta visits as many nodes as plain minimax. With perfect ordering it visits about instead of , where is the branching factor and the depth. We measured both versions on the empty 3×3 board. To choose its first move, the plain minimax above tries 549,945 moves, and the alpha-beta version tries 20,865, about 26 times fewer. The row is also only a loose upper bound. Games end early, so the full game tree has 549,946 nodes and 255,168 complete games, and only 5,478 distinct positions can occur. That last number is why a memo table keyed on the board makes 3×3 search almost free.

Concurrency

On one device there's one thread and no concurrency, and you should say so. The follow-up is nearly always "now two people play online". Moves then arrive as requests on different threads, and the Game is shared mutable state.

What's shared. One Game per match: the turn, the status, and the board's cells and sums. Different games share nothing, so 10,000 matches on a server never contend with each other.

The invariants at risk. A cell holds at most one mark. Marks alternate. Nothing is accepted after the game ends. And the sums always match the cells.

The race. The common one is a double tap: X's client sends the same move twice, from a second tap or a retry after a timeout. Both requests read "X's turn, centre empty" before either writes.

sequenceDiagram
    participant A as First tap by X
    participant G as Game without a lock
    participant B as Second tap by X
    A->>G: is it X's turn, is the centre empty
    B->>G: is it X's turn, is the centre empty
    G-->>A: yes
    G-->>B: yes
    A->>G: place X at the centre, pass turn to O
    B->>G: place X at the centre, pass turn to O
    Note over A,B: Both checks passed. The second write corrupts the sums or flips the turn back to X.

The locking. One lock per game guards move. The status check, turn check, cell check, write and status update all happen inside it (synchronized (this) in Java, threading.Lock in Python). A lock per cell would be wrong, because the turn rule spans the whole game. The getters take the same lock. In Java that isn't optional, because without a happens-before edge another thread may see a stale turn. Three finer points earn credit:

  • Notify outside the lock. A slow listener, such as a WebSocket broadcast, would otherwise block every move in that game, and a listener that calls back into move would deadlock in Python, whose Lock isn't re-entrant. The cost is that notifications can arrive out of order. If order matters, enqueue events inside the lock and deliver them outside.
  • The AI searches a copy. Minimax calls place and undo thousands of times. On the live board, other threads would see half-explored positions. playTurn copies the board under the lock, searches without it, and submits through move, which re-validates.
  • TypeScript needs no lock, because a synchronous method runs to completion on Node's single thread. The danger is an await between the check and the write:
// Broken: other requests run during the await and pass the same check.
async function moveAndSave(game: Game, mark: Mark, row: number, col: number, db: { save(): Promise<void> }) {
  if (game.turn !== mark) throw new Error("not your turn");
  await db.save();
  game.move(mark, row, col);
}
// Fixed: check and apply in one synchronous step, then persist.
async function moveThenSave(game: Game, mark: Mark, row: number, col: number, db: { save(): Promise<void> }) {
  game.move(mark, row, col);
  await db.save();
}

Across several servers an in-process lock protects nothing. Give each move the number it expects to be, and apply it with a conditional write such as UPDATE game SET ..., move_no = 6 WHERE id = ? AND move_no = 5. One of two racing requests wins. The other gets a conflict and re-reads. The move number doubles as an idempotency key for retries. See race conditions and thread-safe class design.

Extensibility: the interviewer adds X

Answer each in three moves: where the change goes, what doesn't change, and the code. We ran each extension below.

Extension: N x N Board

The entire design scales to arbitrary boards with -in-a-row win condition. The win detection still works if . For (e.g., 5-in-a-row on a 15x15 Gomoku board), you need a different approach:

Gomoku Extension

For -in-a-row on an board where , maintain cumulative sums along all possible winning lines. This requires total sums but still allows win detection per move by checking only the 4 directions (horizontal, vertical, two diagonals) from the placed position.

Correction (2026-11-10)

Checking the 4 directions from the placed position costs per move, not , because you walk up to cells each way. That walk reads cells directly and needs no table of sums. A true check keeps the length of each run of equal marks at both ends of the run, as Extension A shows.

Extension A: N×N with k in a row

"Only the win rule changes, and it lives in Board.place. I'll subclass the board and give Game a constructor that takes a board. Players, minimax and locking don't change."

KInARowBoard walks outward from the new mark, which is and keeps undo. RunEndpointBoard is . A new mark can only join the run ending just before it and the run starting just after it, in each direction. Those neighbours are run ends, because the new cell was empty, so their stored lengths are exact. The joined length is , and only its two outer ends need updating. The catch is undo: removing a mark splits a run whose old lengths were overwritten. Minimax needs undo, so it uses the walk.

# file: k_in_a_row.py
import random

from tic_tac_toe import Board, Mark

DIRECTIONS = ((0, 1), (1, 0), (1, 1), (1, -1))


class KInARowBoard(Board):
    """Walk outward from the new mark in 4 directions. O(k) per move, undo still works."""

    def __init__(self, n: int, k: int) -> None:
        if not 1 <= k <= n:
            raise ValueError("need 1 <= k <= n")
        super().__init__(n)
        self.k = k

    def place(self, r: int, c: int, m: Mark) -> bool:
        super().place(r, c, m)                     # validation and the cell write
        return any(self._run(r, c, dr, dc, m) >= self.k for dr, dc in DIRECTIONS)

    def _run(self, r: int, c: int, dr: int, dc: int, m: Mark) -> int:
        length = 1
        for s in (1, -1):
            rr, cc = r + s * dr, c + s * dc
            while length < self.k and self.in_bounds(rr, cc) and self.get(rr, cc) is m:
                length, rr, cc = length + 1, rr + s * dr, cc + s * dc
        return length


class RunEndpointBoard(KInARowBoard):
    """O(1) per move: every run of equal marks stores its length at both ends."""

    def __init__(self, n: int, k: int) -> None:
        super().__init__(n, k)
        self._len = [[[0] * n for _ in range(n)] for _ in DIRECTIONS]

    def place(self, r: int, c: int, m: Mark) -> bool:
        Board.place(self, r, c, m)
        won = False
        for d, (dr, dc) in enumerate(DIRECTIONS):
            left = self._end(d, r - dr, c - dc, m)     # neighbours are run ends,
            right = self._end(d, r + dr, c + dc, m)    # because (r, c) was empty
            total = left + 1 + right
            for rr, cc in ((r, c), (r - left * dr, c - left * dc), (r + right * dr, c + right * dc)):
                self._len[d][rr][cc] = total
            won = won or total >= self.k
        return won

    def _end(self, d: int, r: int, c: int, m: Mark) -> int:
        return self._len[d][r][c] if self.in_bounds(r, c) and self.get(r, c) is m else 0

    def undo(self, r: int, c: int) -> None:
        raise NotImplementedError("a split run's old lengths are gone")


if __name__ == "__main__":
    rng = random.Random(1)
    for _ in range(3_000):                         # the two boards must agree on every move
        n = rng.randint(1, 9)
        k = rng.randint(1, n)
        walk, ends, mark = KInARowBoard(n, k), RunEndpointBoard(n, k), Mark.X
        cells = walk.empty_cells()
        rng.shuffle(cells)
        for p in cells:
            won = walk.place(p.row, p.col, mark)
            assert won == ends.place(p.row, p.col, mark), (n, k, p)
            if won:
                break
            mark = mark.opponent()
    print("walk and run-endpoint boards agree")

The __main__ block plays 3,000 random games on random sizes and win lengths and checks that both boards agree on every move. Comparing a clever implementation with a simple one is the best test for any faster win check.

Extension B: a third player

"The ±1 trick needs exactly two players. I'll keep one counter per player per line: still a move, with space."

Giving the third player another value fails. With X = +1, O = −1 and Z = +3, the mixed row X, O, Z sums to 3, a false win for X. Values , and would work, because the sum then encodes each player's count in base , but that's counters packed into one integer, so write the counters.

// file: MultiPlayerBoard.java
// One counter per player per line. Lines: n rows, n columns, diagonal, anti-diagonal.
public class MultiPlayerBoard {
    private final int n;
    private final int[][] owner;     // -1 = empty
    private final int[][] count;     // count[player][line]

    MultiPlayerBoard(int n, int players) {
        this.n = n;
        owner = new int[n][n];
        for (int[] row : owner) java.util.Arrays.fill(row, -1);
        count = new int[players][2 * n + 2];
    }

    /** Returns true if `player` now owns a whole line through (r, c). O(1). */
    boolean place(int r, int c, int player) {
        if (owner[r][c] != -1) throw new IllegalStateException("cell taken");
        owner[r][c] = player;
        int[] mine = count[player];
        boolean won = ++mine[r] == n | ++mine[n + c] == n;   // non-short-circuit: count both
        if (r == c) won |= ++mine[2 * n] == n;
        if (r + c == n - 1) won |= ++mine[2 * n + 1] == n;
        return won;
    }

    public static void main(String[] args) {
        MultiPlayerBoard b = new MultiPlayerBoard(3, 3);
        boolean mixedRow = b.place(0, 0, 0) | b.place(0, 1, 1) | b.place(0, 2, 2);
        boolean partial = b.place(1, 1, 2);
        boolean antiDiagonal = b.place(2, 0, 2);       // player 2 owns (0,2), (1,1), (2,0)
        if (mixedRow || partial || !antiDiagonal) throw new AssertionError();
        System.out.println("three-player checks passed");
    }
}

Game changes too: Mark gains a value and the turn becomes (turn + 1) % players. Three players on 3×3 is an odd game, so this usually comes with Extension A, such as 6×6 with .

Extension C: undo and redo

"Each move becomes a command that can reverse itself. The sums make reversal . Two stacks."

// file: undoableGame.ts
import { Game, type GameStatus, type Mark } from "./ticTacToe.ts";

interface MoveCommand { mark: Mark; row: number; col: number }

export class UndoableGame extends Game {
  private readonly done: MoveCommand[] = [];
  private undone: MoveCommand[] = [];

  override move(mark: Mark, row: number, col: number): GameStatus {
    const status = super.move(mark, row, col);   // throws before anything is recorded
    this.done.push({ mark, row, col });
    this.undone = [];                            // a fresh move invalidates redo
    return status;
  }

  undo(): void {
    const last = this.done.pop();
    if (!last) throw new Error("nothing to undo");
    this.board.undo(last.row, last.col);         // O(1): subtract from the sums
    this.turnMark = last.mark;
    this.gameStatus = "IN_PROGRESS";             // undoing a winning move reopens the game
    this.undone.push(last);
  }

  redo(): GameStatus {
    const next = this.undone.pop();
    if (!next) throw new Error("nothing to redo");
    const rest = this.undone;
    const status = this.move(next.mark, next.row, next.col);   // re-validated like any move
    this.undone = rest;
    return status;
  }
}

const g = new UndoableGame(3, { X: { chooseMove: () => ({ row: 0, col: 0 }) }, O: { chooseMove: () => ({ row: 0, col: 0 }) } });
g.move("X", 0, 0); g.move("O", 1, 0); g.move("X", 0, 1); g.move("O", 1, 1);
if (g.move("X", 0, 2) !== "X_WON") throw new Error("X wins row 0");
g.undo();
if (g.status !== "IN_PROGRESS" || g.turn !== "X") throw new Error("undo reopens the game");
g.undo();
if (g.redo() !== "IN_PROGRESS" || g.turn !== "X") throw new Error("redo replays O's move");
console.log("undo/redo checks passed");

Undoing a winning move must reopen the game and hand back the turn, not just clear the cell. A fresh move clears the redo stack. redo goes through move, so replays are validated. The only base-class edit was making three fields protected. Composition, an UndoableGame wrapping a Game, avoids even that.

Other likely extensions

The interviewer addsWhere it goes
A move timerA scheduler calls game.forfeit(mark) under the same lock
AI difficultyNew Player strategies: depth-limited, or random with probability p
SpectatorsMore listeners. Nothing else changes
ReplayStore the move list and derive the board by replaying

Testing approach

Players are injected, so tests script them. The board has no I/O. Random tests use a seeded generator, so failures reproduce. That's designing for testability. Test in four layers:

  1. Board rules. Each kind of line wins on its last mark. Taken and off-board cells are rejected. undo restores the sums.
  2. The O(1) trick against an oracle. This matters most. Write the obviously correct scan of every line, play thousands of random games, and assert that sums and scan agree after every move. Bugs like a missing anti-diagonal undo show up within a few hundred games.
  3. Game rules. Wrong turn, moves after the end, a ninth move that fills the board and wins, and "a rejected move changes nothing".
  4. AI and concurrency. The AI blocks and never loses to a random player. Don't assert which of several equally good moves it picks. Eight threads race for one cell, and exactly one wins.
# file: test_tic_tac_toe.py
import random
import threading
import unittest

from tic_tac_toe import Board, Game, GameStatus, Mark, MinimaxPlayer, Position, ScriptedPlayer


def scan_wins(b: Board, m: Mark) -> bool:
    """The slow, obviously correct oracle: check every line."""
    n, idx = b.n, range(b.n)
    lines = [[(i, j) for j in idx] for i in idx] + [[(j, i) for j in idx] for i in idx]
    lines += [[(i, i) for i in idx], [(i, n - 1 - i) for i in idx]]
    return any(all(b.get(r, c) is m for r, c in line) for line in lines)


class BoardTest(unittest.TestCase):
    def test_each_kind_of_line_wins_on_its_last_mark(self):
        for cells in ([(1, 0), (1, 1), (1, 2)], [(0, 2), (1, 2), (2, 2)],
                      [(0, 0), (1, 1), (2, 2)], [(0, 2), (1, 1), (2, 0)]):
            b = Board(3)
            self.assertEqual([b.place(r, c, Mark.O) for r, c in cells], [False, False, True])

    def test_undo_restores_the_sums(self):
        b = Board(3)
        b.place(0, 0, Mark.X)
        b.place(0, 1, Mark.X)
        b.undo(0, 1)
        b.place(0, 1, Mark.O)
        self.assertFalse(b.place(0, 2, Mark.X))

    def test_sums_agree_with_the_oracle_on_random_games(self):
        rng = random.Random(42)                   # seeded, so a failure reproduces
        for _ in range(2_000):
            b, mark = Board(rng.randint(1, 6)), Mark.X
            cells = b.empty_cells()
            rng.shuffle(cells)
            for p in cells:
                won = b.place(p.row, p.col, mark)
                self.assertEqual(won, scan_wins(b, mark))
                if won:
                    break
                mark = mark.opponent()


class GameTest(unittest.TestCase):
    def test_rejects_wrong_turn_taken_cell_and_moves_after_the_end(self):
        g = Game(3, None, None)
        self.assertRaises(RuntimeError, g.move, Mark.O, 0, 0)
        g.move(Mark.X, 1, 1)
        self.assertRaises(ValueError, g.move, Mark.O, 1, 1)
        self.assertIs(g.turn, Mark.O)             # a rejected move changes nothing
        for m, r, c in [(Mark.O, 0, 0), (Mark.X, 0, 2), (Mark.O, 0, 1), (Mark.X, 2, 0)]:
            g.move(m, r, c)
        self.assertIs(g.status, GameStatus.X_WON)
        self.assertRaises(RuntimeError, g.move, Mark.O, 2, 2)

    def test_last_move_that_fills_the_board_and_wins_is_a_win(self):
        x = ScriptedPlayer((0, 0), (0, 2), (1, 1), (2, 1), (2, 2))
        o = ScriptedPlayer((0, 1), (1, 0), (1, 2), (2, 0))
        self.assertIs(Game(3, x, o).play_to_end(), GameStatus.X_WON)

    def test_concurrent_moves_for_the_same_cell(self):
        g, wins, start = Game(3, None, None), [], threading.Barrier(8)

        def attempt():
            start.wait()
            try:
                g.move(Mark.X, 1, 1)
                wins.append(1)
            except (RuntimeError, ValueError):
                pass

        threads = [threading.Thread(target=attempt) for _ in range(8)]
        for t in threads:
            t.start()
        for t in threads:
            t.join()
        self.assertEqual(len(wins), 1)
        self.assertIs(g.turn, Mark.O)


class MinimaxTest(unittest.TestCase):
    def test_blocks_an_open_row(self):
        b = Board(3)
        for r, c, m in [(0, 0, Mark.X), (1, 1, Mark.O), (0, 1, Mark.X)]:
            b.place(r, c, m)
        self.assertEqual(MinimaxPlayer().choose_move(b, Mark.O), Position(0, 2))

    def test_never_loses_to_a_random_player(self):
        rng = random.Random(7)

        class RandomPlayer:
            def choose_move(self, board, me):
                return rng.choice(board.empty_cells())

        for i in range(20):
            bot_is_x = i % 2 == 0
            g = Game(3, *((MinimaxPlayer(), RandomPlayer()) if bot_is_x else (RandomPlayer(), MinimaxPlayer())))
            self.assertIsNot(g.play_to_end(), GameStatus.O_WON if bot_is_x else GameStatus.X_WON)


if __name__ == "__main__":
    unittest.main()

Run with python -m unittest test_tic_tac_toe. We ported the same tests to Java (plain assertions on a bare JDK, which become JUnit 5 @Test methods in a real project) and to TypeScript (node:test), and all three pass.

Common mistakes

  1. Scanning the board after every move. Check only the lines through the move, or better, keep sums.
  2. Checking for a draw before a win. The ninth move can fill the board and complete a line. Check win, then draw, then switch turns.
  3. Switching turns before deciding the result, which reports the wrong winner.
  4. Checking the diagonals on every move. The walkthrough's makeMove tests |diagSum| == n even off the diagonal. That's harmless only because play stops at the first win. A variant that keeps playing would report the old diagonal on every later move.
  5. Using ±1 sums for three players or for .
  6. I/O in the domain. A HumanPlayer calling input() can't be tested or served over the web.
  7. Turn checks in the board, which stops minimax from placing marks freely.
  8. Validating after mutating. If the write happens before validation fails, board and sums disagree.
  9. Over-patterning, such as a State hierarchy for four statuses. Use the State pattern where states behave differently, as in the vending machine.

Interview follow-ups

"Prove the sum check is correct." Each cell adds +1, −1 or 0, so magnitude requires all cells to hold the same mark. Every place and undo keeps the sums equal to the lines, and only lines through the last move can change.

"Can you detect a draw early?" Yes. A line is dead once it holds both marks. Count X and O per line and keep a dead-line counter. When all lines are dead, it's a draw. Still per move.

"How large a board can minimax handle?" 3×3 is trivial: about 21,000 moves tried with alpha-beta, or 5,478 positions with memoisation. 4×4 needs alpha-beta plus a transposition table keyed by a Zobrist hash. Beyond that, use a depth limit with a heuristic, or Monte Carlo tree search.

"How do you use symmetry?" A 3×3 board has 8 symmetries, which shrink the 5,478 positions to 765. Memoise on the canonical form, the smallest of the 8 transformed boards.

"Why does place throw while move returns a status?" A taken cell or wrong turn is misuse. The status is the normal result. A result object for both is fine too, if it's consistent.

"Are the sums premature optimisation?" For 3×3, honestly yes. Say so. They matter for large , and they make undo cheap, which minimax calls hundreds of thousands of times.

Further Reading