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
| Question | Typical answer | Why it matters |
|---|---|---|
| Is the board always 3×3? | Default 3×3, size configurable | Hard-coding 3 is expensive to undo |
| Does a full line always win, or k in a row? | Full line for now | The sum trick only works when the win length equals the board size (see Extension A) |
| How many players? | Two | The ±1 encoding only works for two players (see Extension B) |
| Humans, AI, or both? | Any mix | Moves come from a pluggable source: Strategy |
| Undo? | Nice to have | The board must reverse its win-check state cheaply |
| Same device, or online? | Same device first | Online means concurrent requests, so validation must be atomic |
| UI? | Console, core UI-agnostic | No printing or input in the core. Notify listeners |
Functional Requirements
| # | Requirement | Details |
|---|---|---|
| FR-1 | Board setup | Create an board (default 3x3) |
| FR-2 | Two players | Human vs Human, Human vs AI, AI vs AI |
| FR-3 | Turn management | Alternate turns between players |
| FR-4 | Move validation | Reject moves to occupied cells or out of bounds |
| FR-5 | Win detection | Detect row, column, or diagonal completion |
| FR-6 | Draw detection | Detect when all cells filled with no winner |
| FR-7 | Game reset | Reset board for a new game |
| FR-8 | AI player | Computer opponent using minimax |
Non-functional requirements
| # | Requirement | What it means for the design |
|---|---|---|
| NFR-1 | Win check in per move | Keep running line sums, never rescan the board |
| NFR-2 | Testable without a keyboard | Players are injected, tests script them |
| NFR-3 | Safe under concurrent moves | Validate-and-apply is atomic per game |
| NFR-4 | Invalid moves change nothing | Validate 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).
| Entity | Responsibility | Owns |
|---|---|---|
Mark | X or O, with the ±1 value the sums use | |
Board | Geometry: cells and running sums. "Did this placement complete a line?" in | Cells, line sums, move count |
Player | Chooses a move. Human, network, script and AI are implementations | |
Game | Rules: turn, game over, result. Applies moves atomically, notifies listeners | Board, players, listeners |
GameListener | Observes 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:
| Move | Row sums | Column sums | Diagonal | Anti-diagonal | Result |
|---|---|---|---|---|---|
| X at (1,1) | 0, 1, 0 | 0, 1, 0 | 1 | 1 | centre is on both diagonals |
| O at (0,0) | −1, 1, 0 | −1, 1, 0 | 0 | 1 | |
| X at (0,2) | 0, 1, 0 | −1, 1, 1 | 0 | 2 | |
| O at (2,2) | 0, 1, −1 | −1, 1, 0 | −1 | 2 | |
| X at (2,0) | 0, 1, 0 | 0, 1, 0 | −1 | 3 | , 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
| Approach | Time per move | Extra space | Supports cheap undo |
|---|---|---|---|
| Scan the whole board | none | yes, nothing to restore | |
| Scan only the lines through the move | none | yes | |
| Running sums (this design) | yes, subtract the value | ||
| Walk 4 directions for k in a row | none | yes | |
| Run lengths stored at run ends | no |
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
| Pattern | Where Used | Why |
|---|---|---|
| Strategy | Player interface (Human, AI, AIAlphaBeta) | Swap player types without changing game logic |
| Observer | Game events (could notify UI on state changes) | Decouple game logic from presentation |
| Template Method | Game loop structure | Same turn flow, different move sources |
| State | GameStatus transitions | Clear 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:
| Pattern | Where | Why | Alternative rejected |
|---|---|---|---|
| Strategy | Player | Human or AI on either side, scriptable in tests | if (player.isAI) in the loop, edited for every new player type |
| Observer | GameListener | UI-agnostic core, spectators later | Game calling a UI directly |
| Composition | Game composes Board | The board is reused by search and variants | Game extends Board, which mixes rules into geometry |
| Not used: State | Four statuses that behave alike. An enum is clearer | ||
| Not used: Singleton | A 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
EMPTYmark. Empty isnull, soplace(r, c, EMPTY)can't be written. placevalidates 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
| Operation | Time | Space |
|---|---|---|
| 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
movewould deadlock in Python, whoseLockisn'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
placeandundothousands of times. On the live board, other threads would see half-explored positions.playTurncopies the board under the lock, searches without it, and submits throughmove, which re-validates. - TypeScript needs no lock, because a synchronous method runs to completion on Node's single thread. The danger is an
awaitbetween 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 giveGamea 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 adds | Where it goes |
|---|---|
| A move timer | A scheduler calls game.forfeit(mark) under the same lock |
| AI difficulty | New Player strategies: depth-limited, or random with probability p |
| Spectators | More listeners. Nothing else changes |
| Replay | Store 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:
- Board rules. Each kind of line wins on its last mark. Taken and off-board cells are rejected.
undorestores the sums. - 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.
- Game rules. Wrong turn, moves after the end, a ninth move that fills the board and wins, and "a rejected move changes nothing".
- 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
- Scanning the board after every move. Check only the lines through the move, or better, keep sums.
- 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.
- Switching turns before deciding the result, which reports the wrong winner.
- Checking the diagonals on every move. The walkthrough's
makeMovetests|diagSum| == neven 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. - Using ±1 sums for three players or for .
- I/O in the domain. A
HumanPlayercallinginput()can't be tested or served over the web. - Turn checks in the board, which stops minimax from placing marks freely.
- Validating after mutating. If the write happens before validation fails, board and sums disagree.
- 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
- LLD Interviews Overview — SOLID principles and design patterns
- Backtracking & Recursion — minimax is a backtracking algorithm
- Dynamic Programming — game theory connections
- Design File System — another composite-pattern LLD problem
- The LLD Interview Framework — the 45-minute structure this page follows
- Common LLD Mistakes — the general versions of the mistakes above
- Design Chess — the next step up in board-game modelling, with move validation and undo
- Strategy, Observer and Command — the three patterns this design uses