Design tic-tac-toe (an extensible board game)¶
TL;DR¶
- You build an N x N board game whose skeleton — set up, take turns, judge, rotate — lives in a
BoardGamebase class that snake and ladder and the bowling scorer reuse verbatim. - Three decisions carry the interview: win detection is O(1) (four counters per move, not a rescan), undo is an inverse command plus a three-field Memento, and the bot is a Strategy so a human, a seeded random bot and minimax are interchangeable.
- Patterns that earn their place: Template Method, Strategy, Factory Method, Command with Memento, Observer. Inheritance for player kinds is deliberately not used.
Problem statement¶
"Design tic-tac-toe so that it generalises. Two players alternate on an N x N board — 3 x 3 by default — placing their symbol on an empty cell. The first to fill a whole row, column or diagonal wins; a full board with no line is a draw. Players may be human or bots, and the game must support undoing the last move and replaying the game from its history. Show me the classes, the main flow, and how you would add Connect-4 later."
Requirements¶
Functional
- An N x N board, default 3 x 3, with two players who alternate turns.
- Each player is human or a bot; a bot is random, or minimax (perfect play) on 3 x 3.
- Move validation: the cell must be on the board, empty, and offered by the player whose turn it is.
- Win detection in O(1) per move using row, column and both diagonal counters.
- Draw detection when the board fills with no line.
- Undo the last move, including a move that ended the game.
- A move history and a replay that rebuilds every position from it.
- A renderer that is told about events rather than polling the board.
Non-functional and constraints
- Correct when several threads submit moves: at most one move per turn, and no cell written twice.
- Deterministic and testable: every random generator is injected and seeded; no wall-clock reads.
- In-memory, single process, standard library only.
Out of scope: networking and matchmaking, persistence, per-move clocks, rendering to an actual screen.
Clarifying questions and assumptions¶
| Question to ask | Assumption taken here |
|---|---|
| Is the board always 3 x 3? | No — size is a constructor argument. Win means a full line of length N, which keeps the counters correct for any N. |
| More than two players? | Two here, and the base class enforces it with MIN_PLAYERS. Snake and ladder raises the same limit to eight. |
| Where do human moves come from? | From outside: submit_move takes one move from a UI, socket or test. The library never reads stdin. |
| How strong must the bot be? | Perfect on 3 x 3 (minimax over 5,478 reachable positions); above 3 x 3 it delegates to a fallback strategy rather than pretending to search. |
| Can you undo after the game is over? | Yes. That is the interesting case: the status has to go back to in progress, not just the board. |
| Can two clients play the same game concurrently? | Yes — one lock per game object, and turn enforcement rejects whoever is out of turn. |
| Do we need Connect-4 or Gomoku now? | No, but the win checker is a separate class so that a k-in-a-row variant swaps one object. |
Core entities and relationships¶
- BoardGame (abstract, generic over the move type) — the shared skeleton: the turn cursor, the turn limit, observers, and the
play/play_turntemplate methods. It lives incode/lld/tic_tac_toe/base.pybecause it is game vocabulary, not infrastructure, and two other problems import it. - TicTacToeGame — the rules: what a move is, how it is applied, when the game is over, who won. Plus the three features the template does not know about:
submit_move,undoandreplay. - Board — the N x N grid. It owns placement rules (on the board, currently empty) and nothing else.
- WinChecker — the counters.
recordreturns whether the placement completed a line;eraseis its exact inverse. One checker per board. - Cell — a frozen
(row, col)coordinate. It is a key, not a container; the board holds the symbols. - Move — the frozen command record: turn number, player, symbol, cell. The move log is a list of these, and replay is a fold over it.
- TurnCursor — the Memento: status, turn index and turn count, captured before each move.
- Player — id, symbol, kind and a
MoveStrategy.Player.next_move(board)delegates; the game never asks what kind of player it is holding. - MoveStrategy —
ScriptedMove(a queue),RandomMove(injectedrandom.Random),MinimaxMove(negamax with a transposition table). - PlayerFactory — turns a
PlayerKindplus arguments into aPlayerwith the right strategy. - GameObserver —
BoardRendererandGameLogreceiveGameEvents; the game never imports a display.
Multiplicities: game 1 -> 1 board, board 1 -> 1 win checker, game 1 -> 2 players, game 1 -> * moves, player 1 -> 1 strategy, game 1 -> * observers.
Class diagram¶
Structure: the template, the rules that fill it in, and the two pieces of state a move changes.
classDiagram
class BoardGame {
<<abstract>>
+players tuple
+play() GameResult
+play_turn()
+start()
+setup()
+after_move(player, move)
+advance_turn()
+choose_move(player) M
+apply_move(player, move)
+is_over() bool
+winner() str
+cursor() TurnCursor
+restore(cursor)
}
class TicTacToeGame {
+board Board
+submit_move(player, cell) Move
+undo() Move
+history() tuple
+replay() List~str~
}
class Board {
+size int
+place(cell, symbol) bool
+clear(cell) Symbol
+free_cells() List~Cell~
+is_full() bool
+snapshot() tuple
+render() str
}
class WinChecker {
+size int
+record(cell, symbol) bool
+erase(cell, symbol)
+reset()
}
class Cell {
+row int
+col int
}
class Move {
+number int
+player_id str
+symbol Symbol
+cell Cell
}
class TurnCursor {
+status GameStatus
+turn_index int
+turns int
}
class Player {
+id str
+symbol Symbol
+kind PlayerKind
+next_move(board) Cell
}
BoardGame <|-- TicTacToeGame
TicTacToeGame "1" *-- "1" Board
Board "1" *-- "1" WinChecker
TicTacToeGame "1" o-- "2" Player
TicTacToeGame "1" o-- "many" Move
TicTacToeGame ..> TurnCursor : snapshots
Move --> CellBehaviour: the two seams an interviewer will push on — who decides a move, and who watches.
classDiagram
class MoveStrategy {
<<interface>>
+choose(board, symbol) Cell
}
class ScriptedMove {
+offer(cell)
}
class RandomMove
class MinimaxMove {
+choose(board, symbol) Cell
}
class PlayerFactory {
+create(kind, player_id, symbol) Player
}
class Player
class GameObserver {
<<interface>>
+on_event(event)
}
class BoardRenderer {
+transcript() List~str~
+render() str
}
class GameLog {
+events() tuple
+lines() List~str~
}
class GameEvent {
+turn int
+actor str
+text str
}
class TicTacToeGame
MoveStrategy <|.. ScriptedMove
MoveStrategy <|.. RandomMove
MoveStrategy <|.. MinimaxMove
Player --> MoveStrategy
PlayerFactory ..> Player : creates
GameObserver <|.. BoardRenderer
GameObserver <|.. GameLog
TicTacToeGame --> "many" GameObserver : notifies
GameObserver ..> GameEventDesign patterns applied¶
| Pattern | Where | Why it earns its place |
|---|---|---|
| Template Method | BoardGame.play and BoardGame.play_turn |
The order of a turn — choose, apply, count, judge, rotate — is identical in every board game and is exactly the thing a subclass must not be free to reorder. Two other problems in this handbook subclass it without changing a line. |
| Strategy | MoveStrategy with ScriptedMove, RandomMove, MinimaxMove |
"Now add a bot" is a one-class change, and swapping a human for a bot mid-game is an assignment. Bot strength is a runtime choice, which inheritance cannot give you. |
| Factory Method | PlayerFactory.create with a PlayerKind registry |
The caller names a kind, not a class. Adding a cautious bot is a builder function plus one registry entry. |
| Command | Move as an immutable record; Board.place and Board.clear are inverses |
The move log is the whole feature set: undo pops it, replay folds it, and a future network protocol serialises it. |
| Memento | TurnCursor captured before each move |
The board can be restored by the inverse command, but status and turn index cannot be recomputed once turn order stops being round-robin. Three integers is the cheapest honest snapshot. |
| Observer | GameObserver, BoardRenderer, GameLog |
The game emits GameEvents and never imports a display. The same log class serves all three board games in this handbook. |
| Polymorphism over conditionals | Player.next_move |
There is no if kind == "bot" anywhere in the game. The interviewer is checking for that ladder. |
What was deliberately not used: a HumanPlayer / BotPlayer class hierarchy. Player kind and move policy vary independently — you would end up with TimedHumanPlayer, TimedBotPlayer and a combinatorial explosion. Composition (one Player class holding a strategy) collapses it. Also skipped: a full State class per status. Five enum values with guarded transitions in one _settle method is smaller and easier to read than five classes; bowling, where a frame's state genuinely changes its behaviour, is where classes start to pay.
Key flows¶
One turn, driven from outside: turn check, strategy, placement, counters, verdict, notification.
sequenceDiagram
autonumber
actor U as UI
participant G as TicTacToeGame
participant P as Player
participant S as MinimaxMove
participant B as Board
participant W as WinChecker
participant R as BoardRenderer
U->>G: submit_move("X", Cell(2,2))
G->>G: require_turn("X")
G->>G: play_turn (the template method)
G->>P: next_move(board)
P->>S: choose(board, X)
S-->>P: cell
P-->>G: cell
G->>B: place(cell, X)
B->>W: record(cell, X)
W-->>B: line complete
B-->>G: True
G->>G: settle, status becomes WON
G-)R: on_event, delivered outside the lockUndo: pop the command, invert the board, restore the Memento.
sequenceDiagram
autonumber
actor U as UI
participant G as TicTacToeGame
participant B as Board
participant W as WinChecker
U->>G: undo()
G->>G: pop the last Move and its TurnCursor
G->>B: clear(cell)
B->>W: erase(cell, symbol)
G->>G: winner = None, restore(cursor)
G-->>U: the Move that was taken backGame status. The two edges that matter are the ones going backwards: undo is the only transition that leaves a terminal state, which is why TurnCursor records the status and not just the turn number.
stateDiagram-v2
[*] --> NOT_STARTED
NOT_STARTED --> IN_PROGRESS : start
IN_PROGRESS --> IN_PROGRESS : move applied, no line
IN_PROGRESS --> WON : move completes a line
IN_PROGRESS --> DRAWN : board full, no line
IN_PROGRESS --> ABANDONED : resign or turn limit
WON --> IN_PROGRESS : undo
DRAWN --> IN_PROGRESS : undo
WON --> [*]
DRAWN --> [*]
ABANDONED --> [*]Implementation¶
Write it in the order you would on a whiteboard: the skeleton every game shares, then the vocabulary, then the counters, then the rules, then the policies.
The status enum, the result and the Memento are the shared kernel. TERMINAL_STATUSES is a frozenset, so the module holds no mutable state:
code/lld/tic_tac_toe/base.py — status and memento
class GameStatus(StrEnum):
NOT_STARTED = "not_started"
IN_PROGRESS = "in_progress"
WON = "won"
DRAWN = "drawn"
ABANDONED = "abandoned"
TERMINAL_STATUSES = frozenset({GameStatus.WON, GameStatus.DRAWN, GameStatus.ABANDONED})
class NotYourTurnError(ConflictError):
"""A player acted out of turn."""
class TurnLimitError(InvalidStateError):
"""The game ran past its turn limit; a rule or a bot is looping."""
@dataclass(frozen=True, slots=True)
class GameResult:
status: GameStatus
winner: str | None # None for a draw or an abandoned game
turns: int
@dataclass(frozen=True, slots=True)
class TurnCursor:
"""Memento of the base class's own state: everything a turn changes off the board."""
status: GameStatus
turn_index: int
turns: int
The observer side is three small pieces: an immutable event, a one-method protocol, and a log that every game in this handbook reuses.
code/lld/tic_tac_toe/base.py — observer
@dataclass(frozen=True, slots=True)
class GameEvent:
"""One immutable line of the game's story, pushed to observers."""
turn: int
actor: str | None
text: str
def __str__(self) -> str:
return f"[{self.turn:>2}] {self.text}"
class GameObserver(Protocol):
"""Observer interface: renderers, logs and scoreboards implement exactly this."""
def on_event(self, event: GameEvent) -> None: ...
class GameLog:
"""The plainest observer: it remembers every event. Reused by all three games."""
def __init__(self) -> None:
self._lock = threading.Lock()
self._events: list[GameEvent] = []
def on_event(self, event: GameEvent) -> None:
with self._lock:
self._events.append(event)
def events(self) -> tuple[GameEvent, ...]:
with self._lock:
return tuple(self._events)
def lines(self) -> list[str]:
return [str(event) for event in self.events()]
Now the template itself. play_turn fixes the order of a turn; the abstract steps are the rules and the hooks have defaults. Note the try/finally: events are buffered under the lock and delivered after it is released.
code/lld/tic_tac_toe/base.py — the template method
class BoardGame[M](ABC):
"""The template. ``play`` and ``play_turn`` own the order of the steps; subclasses own the rules.
Abstract steps (``choose_move``, ``apply_move``, ``is_over``, ``winner``) must be
supplied by every game. Hooks (``setup``, ``after_move``, ``advance_turn``) have a
default that most games keep. ``M`` is the game's move type: a ``Cell`` in
tic-tac-toe, a dice roll in snake and ladder, a pin count in bowling.
``_lock`` guards the turn cursor and, by extension, whatever the subclass mutates
inside ``apply_move``. It is an ``RLock`` because the hooks call back into public
methods that lock again.
"""
MIN_PLAYERS: int = 2
MAX_PLAYERS: int = 8
def __init__(self, players: Sequence[str], *, turn_limit: int = DEFAULT_TURN_LIMIT) -> None:
if not self.MIN_PLAYERS <= len(players) <= self.MAX_PLAYERS:
raise ValidationError(
f"{type(self).__name__} takes {self.MIN_PLAYERS}-{self.MAX_PLAYERS} players, got {len(players)}"
)
if len(set(players)) != len(players):
raise ValidationError("player names must be unique")
if turn_limit < 1:
raise ValidationError("turn_limit must be positive")
self.players = tuple(players)
self.turn_limit = turn_limit
self._lock = threading.RLock()
self._status = GameStatus.NOT_STARTED
self._turn_index = 0
self._turns = 0
self._observers: list[GameObserver] = []
self._event_buffer: list[GameEvent] = []
# -- the template methods: never overridden -------------------------------------------
def play(self) -> GameResult:
"""Play the whole game and report. The order of these steps is fixed here, for every game."""
while self.status in (GameStatus.NOT_STARTED, GameStatus.IN_PROGRESS):
self.play_turn()
return self.result()
def play_turn(self) -> None:
"""One turn: pick a move, apply it, let the game re-judge itself, rotate."""
try:
with self._lock:
if self._status is GameStatus.NOT_STARTED:
self.start()
if self._status is not GameStatus.IN_PROGRESS:
raise InvalidStateError(f"game is {self._status}; no turn can be played")
if self._turns >= self.turn_limit:
self._status = GameStatus.ABANDONED
raise TurnLimitError(f"no result after {self._turns} turns")
player = self.players[self._turn_index]
move = self.choose_move(player)
self.apply_move(player, move)
self._turns += 1
self.after_move(player, move)
self._settle()
finally:
self.flush_events()
def start(self) -> None:
with self._lock:
if self._status is not GameStatus.NOT_STARTED:
raise InvalidStateError(f"game is already {self._status}")
self.setup()
self._status = GameStatus.IN_PROGRESS
self.emit("game started")
def abandon(self, reason: str) -> None:
try:
with self._lock:
if self._status in TERMINAL_STATUSES:
raise InvalidStateError(f"game is already {self._status}")
self._status = GameStatus.ABANDONED
self.emit(f"abandoned: {reason}")
finally:
self.flush_events()
def _settle(self) -> None:
"""Ask the rules whether the game ended; rotate the turn if it did not."""
if self.is_over():
champion = self.winner()
self._status = GameStatus.WON if champion is not None else GameStatus.DRAWN
self.emit(f"{champion} wins" if champion else "draw", actor=champion)
else:
self.advance_turn()
# -- hooks: a default every game can live with -----------------------------------------
def setup(self) -> None:
"""Called once, before the first turn. Games with nothing to reset keep this no-op."""
return None
def after_move(self, player: str, move: M) -> None:
"""Called after every applied move, before the game re-judges itself."""
self.emit(f"{player} -> {move}", actor=player)
def advance_turn(self) -> None:
"""Round-robin by default; bowling rotates only when a frame closes."""
self._turn_index = (self._turn_index + 1) % len(self.players)
# -- abstract steps: every game supplies them -----------------------------------------
@abstractmethod
def choose_move(self, player: str) -> M: ...
@abstractmethod
def apply_move(self, player: str, move: M) -> None: ...
@abstractmethod
def is_over(self) -> bool: ...
@abstractmethod
def winner(self) -> str | None: ...
# -- shared state, read-only to callers -------------------------------------------------
@property
def status(self) -> GameStatus:
with self._lock:
return self._status
@property
def turns(self) -> int:
with self._lock:
return self._turns
@property
def current_player(self) -> str:
with self._lock:
return self.players[self._turn_index]
def result(self) -> GameResult:
with self._lock:
champion = self.winner() if self._status is GameStatus.WON else None
return GameResult(self._status, champion, self._turns)
def require_turn(self, player: str) -> None:
"""Turn enforcement in one place: every externally driven move calls this first."""
with self._lock:
if player not in self.players:
raise ValidationError(f"{player} is not in this game")
if player != self.players[self._turn_index]:
raise NotYourTurnError(f"it is {self.players[self._turn_index]}'s turn, not {player}'s")
# -- the Memento the undo feature restores ---------------------------------------------
def cursor(self) -> TurnCursor:
with self._lock:
return TurnCursor(self._status, self._turn_index, self._turns)
def restore(self, cursor: TurnCursor) -> None:
with self._lock:
self._status = cursor.status
self._turn_index = cursor.turn_index
self._turns = cursor.turns
# -- observers --------------------------------------------------------------------------
def subscribe(self, observer: GameObserver) -> None:
with self._lock:
self._observers.append(observer)
def emit(self, text: str, actor: str | None = None) -> None:
"""Buffer an event; ``flush_events`` delivers it once the lock is released."""
with self._lock:
self._event_buffer.append(GameEvent(self._turns, actor, text))
def flush_events(self) -> None:
"""Deliver with no lock held, so a slow renderer can never stall the turn loop."""
with self._lock:
events, self._event_buffer = self._event_buffer, []
observers = tuple(self._observers)
for event in events:
for observer in observers:
observer.on_event(event)
The vocabulary comes next. Errors subclass the shared hierarchy so a caller can catch ConflictError without importing anything from tic-tac-toe:
code/lld/tic_tac_toe/models.py — enums and errors
class Symbol(StrEnum):
CROSS = "X"
NOUGHT = "O"
class PlayerKind(StrEnum):
HUMAN = "human" # moves arrive from outside: a UI, a socket, a test
RANDOM_BOT = "random_bot"
PERFECT_BOT = "perfect_bot" # minimax, 3x3 only
class OffBoardError(ValidationError):
"""The cell is outside the N x N grid."""
class CellOccupiedError(ConflictError):
"""The cell already holds a symbol."""
class NothingToUndoError(InvalidStateError):
"""Undo was called on a game with no moves left to take back."""
Cell, Move and Player are frozen. Player holds a strategy instead of being subclassed, and next_move is the single line that keeps type checks out of the game:
code/lld/tic_tac_toe/models.py — values
@dataclass(frozen=True, slots=True, order=True)
class Cell:
"""A coordinate, not a container: the board stores what is in it."""
row: int
col: int
def __str__(self) -> str:
return f"({self.row},{self.col})"
@dataclass(frozen=True, slots=True)
class Move:
"""The Command record: enough to replay the game and to invert one step."""
number: int # 1-based turn number
player_id: str
symbol: Symbol
cell: Cell
@dataclass(frozen=True, slots=True)
class Player:
"""Who plays, with which symbol, and how the move is chosen (Strategy)."""
id: str
symbol: Symbol
kind: PlayerKind
strategy: MoveStrategy
def next_move(self, board: Board) -> Cell:
return self.strategy.choose(board, self.symbol)
This is the class the interviewer is waiting for. A naive checker rescans 2N + 2 lines of N cells after every move, so a full 3 x 3 game costs about 9 x 8 = 72 line scans and an N x N game is O(N^2) per move, O(N^4) over the whole board. Counting instead touches at most four integers per move and compares each with N:
code/lld/tic_tac_toe/models.py — the O(1) win checker
class WinChecker:
"""Incremental row, column and diagonal counters: O(1) per move, no rescan.
A naive checker rescans 2N + 2 lines of N cells after every move - O(N^2) a
move, O(N^4) over a full board. Here each placement bumps at most four
counters and compares them with N. The centre of an odd board sits on *both* diagonals, so the two
diagonal tests are separate ``if``s, never an ``elif`` - that is the bug
interviewers look for.
"""
def __init__(self, size: int) -> None:
self.size = size
self._rows: dict[Symbol, list[int]] = {s: [0] * size for s in Symbol}
self._cols: dict[Symbol, list[int]] = {s: [0] * size for s in Symbol}
self._diagonal: dict[Symbol, int] = dict.fromkeys(Symbol, 0)
self._anti_diagonal: dict[Symbol, int] = dict.fromkeys(Symbol, 0)
def record(self, cell: Cell, symbol: Symbol) -> bool:
"""Count the placement and report whether it completed a line."""
self._rows[symbol][cell.row] += 1
self._cols[symbol][cell.col] += 1
if cell.row == cell.col:
self._diagonal[symbol] += 1
if cell.row + cell.col == self.size - 1:
self._anti_diagonal[symbol] += 1
return (
self._rows[symbol][cell.row] == self.size
or self._cols[symbol][cell.col] == self.size
or self._diagonal[symbol] == self.size
or self._anti_diagonal[symbol] == self.size
)
def erase(self, cell: Cell, symbol: Symbol) -> None:
"""The exact inverse of ``record``; this is what makes undo cheap."""
self._rows[symbol][cell.row] -= 1
self._cols[symbol][cell.col] -= 1
if cell.row == cell.col:
self._diagonal[symbol] -= 1
if cell.row + cell.col == self.size - 1:
self._anti_diagonal[symbol] -= 1
def reset(self) -> None:
for symbol in Symbol:
self._rows[symbol] = [0] * self.size
self._cols[symbol] = [0] * self.size
self._diagonal[symbol] = 0
self._anti_diagonal[symbol] = 0
Board is deliberately thin: it validates placement and delegates the verdict. snapshot exists for one reason — it is the hashable key the minimax transposition table needs.
code/lld/tic_tac_toe/models.py — board
class Board:
"""The N x N grid plus its win checker. Knows placement rules, not game rules."""
def __init__(self, size: int = DEFAULT_SIZE) -> None:
if size < 3:
raise ValidationError(f"board size must be at least 3, got {size}")
self.size = size
self._grid: list[list[Symbol | None]] = [[None] * size for _ in range(size)]
self._checker = WinChecker(size)
self._filled = 0
def at(self, cell: Cell) -> Symbol | None:
self._require_inside(cell)
return self._grid[cell.row][cell.col]
def place(self, cell: Cell, symbol: Symbol) -> bool:
"""Place a symbol; return True when the move completes a line."""
self._require_inside(cell)
if self._grid[cell.row][cell.col] is not None:
raise CellOccupiedError(f"cell {cell} already holds {self._grid[cell.row][cell.col]}")
self._grid[cell.row][cell.col] = symbol
self._filled += 1
return self._checker.record(cell, symbol)
def clear(self, cell: Cell) -> Symbol:
"""Take a symbol back off the board (undo). Returns the symbol removed."""
self._require_inside(cell)
symbol = self._grid[cell.row][cell.col]
if symbol is None:
raise InvalidStateError(f"cell {cell} is empty")
self._grid[cell.row][cell.col] = None
self._filled -= 1
self._checker.erase(cell, symbol)
return symbol
def free_cells(self) -> list[Cell]:
return [
Cell(r, c) for r in range(self.size) for c in range(self.size) if self._grid[r][c] is None
]
def is_full(self) -> bool:
return self._filled == self.size * self.size
def reset(self) -> None:
self._grid = [[None] * self.size for _ in range(self.size)]
self._checker.reset()
self._filled = 0
def snapshot(self) -> tuple[Symbol | None, ...]:
"""Flat, hashable copy - the key a minimax transposition table needs."""
return tuple(cell for row in self._grid for cell in row)
def render(self) -> str:
"""A dot for an empty cell, so a rendered board never ends in trailing spaces."""
return "\n".join("|".join(c.value if c else "." for c in row) for row in self._grid)
def _require_inside(self, cell: Cell) -> None:
if not (0 <= cell.row < self.size and 0 <= cell.col < self.size):
raise OffBoardError(f"cell {cell} is outside a {self.size}x{self.size} board")
The strategies. ScriptedMove doubles as the input buffer a UI needs and the exact move source a test needs.
code/lld/tic_tac_toe/strategies.py — the strategy seam
class MoveStrategy(Protocol):
"""One method, one decision. The game never asks *what kind* of player this is."""
def choose(self, board: Board, symbol: Symbol) -> Cell: ...
class ScriptedMove:
"""A queue of moves: a replayed game in tests, a UI's input buffer in production."""
def __init__(self, cells: Iterable[Cell] = ()) -> None:
self._queue: deque[Cell] = deque(cells)
def offer(self, cell: Cell) -> None:
self._queue.append(cell)
def choose(self, board: Board, symbol: Symbol) -> Cell:
if not self._queue:
raise InvalidStateError(f"no scripted move left for {symbol}")
return self._queue.popleft()
class RandomMove:
"""A legal move, uniformly at random. The generator is injected, so tests are exact."""
def __init__(self, rng: random.Random) -> None:
self._rng = rng
def choose(self, board: Board, symbol: Symbol) -> Cell:
free = board.free_cells()
if not free:
raise InvalidStateError("board is full")
return self._rng.choice(free)
Minimax is written as negamax with make/unmake on the live board — no copy per node — plus a transposition table. Scores decay by one per ply on the way up, which both prefers a faster win and keeps a cached entry valid regardless of the depth it was first computed at:
code/lld/tic_tac_toe/strategies.py — minimax
class MinimaxMove:
"""Perfect play on a 3x3 board: negamax with a transposition table.
Search is make/unmake on the live board rather than a copy per node - the game
lock is held while the bot thinks, so no other thread can observe the transient
position. Scores decay by one per ply on the way up, so the bot prefers a win in
three moves over the same win in five, and a memo entry stays valid whatever
depth it was first computed at. Anything larger than 3x3 delegates to
``fallback``, because the game tree stops being enumerable.
"""
def __init__(self, max_size: int = 3, fallback: MoveStrategy | None = None) -> None:
self._max_size = max_size
self._fallback = fallback or RandomMove(random.Random(0))
self._memo: dict[tuple[tuple[Symbol | None, ...], Symbol], int] = {}
def choose(self, board: Board, symbol: Symbol) -> Cell:
if board.size > self._max_size:
return self._fallback.choose(board, symbol)
free = board.free_cells()
if not free:
raise InvalidStateError("board is full")
best_cell, best_score = free[0], -WIN_SCORE - 1
for cell in free:
if board.place(cell, symbol): # winning now beats every alternative
board.clear(cell)
return cell
score = -self._negamax(board, opponent(symbol))
board.clear(cell)
if score > best_score: # strict > keeps the choice deterministic
best_cell, best_score = cell, score
return best_cell
def _negamax(self, board: Board, to_move: Symbol) -> int:
"""Score the position for ``to_move``: positive means to_move wins, sooner is larger."""
key = (board.snapshot(), to_move)
cached = self._memo.get(key)
if cached is not None:
return cached
free = board.free_cells()
if not free:
self._memo[key] = 0
return 0
best = -WIN_SCORE
for cell in free:
if board.place(cell, to_move):
board.clear(cell)
best = WIN_SCORE
break
score = -self._negamax(board, opponent(to_move))
board.clear(cell)
best = max(best, score)
decayed = best - 1 if best > 0 else best + 1 if best < 0 else 0
self._memo[key] = decayed
return decayed
The factory is a registry of builder functions, so a new player kind never touches the game:
code/lld/tic_tac_toe/services.py — player factory
def _human(moves: Sequence[Cell] | None, rng: random.Random | None) -> MoveStrategy:
return ScriptedMove(moves or ())
def _random_bot(moves: Sequence[Cell] | None, rng: random.Random | None) -> MoveStrategy:
return RandomMove(require_rng(rng))
def _perfect_bot(moves: Sequence[Cell] | None, rng: random.Random | None) -> MoveStrategy:
return MinimaxMove()
class PlayerFactory:
"""Factory Method: callers name a *kind*, never a strategy class.
Adding "cautious bot" is a builder plus a registry entry; the game, the board
and the renderer are untouched.
"""
_BUILDERS: dict[PlayerKind, StrategyBuilder] = {
PlayerKind.HUMAN: _human,
PlayerKind.RANDOM_BOT: _random_bot,
PlayerKind.PERFECT_BOT: _perfect_bot,
}
@classmethod
def create(
cls,
kind: PlayerKind | str,
player_id: str,
symbol: Symbol,
*,
moves: Sequence[Cell] | None = None,
rng: random.Random | None = None,
) -> Player:
try:
resolved = PlayerKind(kind)
except ValueError as exc:
raise ValidationError(f"unknown player kind: {kind!r}") from exc
return Player(player_id, symbol, resolved, cls._BUILDERS[resolved](moves, rng))
And the game. Everything above the divider is the template's five steps; everything below is the extra features. Read apply_move closely: the Memento is captured before the board changes and appended only after the placement succeeds, so a rejected move leaves no debris.
code/lld/tic_tac_toe/services.py — the game
class TicTacToeGame(BoardGame[Cell]):
"""Tic-tac-toe as a set of rules bolted onto the shared ``BoardGame`` skeleton.
The five methods below are everything this game adds to the template: how a move
is chosen, how it is applied, when the game is over, who won, and how to set up.
Undo, replay and the input buffer are the features an interviewer asks for after
the happy path works.
"""
MIN_PLAYERS = 2
MAX_PLAYERS = 2
def __init__(
self,
players: Sequence[Player],
size: int = DEFAULT_SIZE,
*,
turn_limit: int = DEFAULT_TURN_LIMIT,
) -> None:
super().__init__([p.id for p in players], turn_limit=turn_limit)
if len({p.symbol for p in players}) != len(players):
raise ValidationError("the two players must use different symbols")
self._by_id: dict[str, Player] = {p.id: p for p in players}
self.board = Board(size)
self._history: list[Move] = []
self._cursors: list[TurnCursor] = []
self._winner: str | None = None
self._buffered: Cell | None = None
# -- the template's steps ---------------------------------------------------------
def setup(self) -> None:
self.board.reset()
self._history.clear()
self._cursors.clear()
self._winner = None
def choose_move(self, player: str) -> Cell:
"""An externally submitted move wins over the player's own strategy."""
if self._buffered is not None:
cell, self._buffered = self._buffered, None
return cell
return self._by_id[player].next_move(self.board)
def apply_move(self, player: str, move: Cell) -> None:
symbol = self._by_id[player].symbol
cursor = self.cursor() # Memento taken *before* the board changes
won = self.board.place(move, symbol) # raises on an occupied or off-board cell
self._cursors.append(cursor)
self._history.append(Move(len(self._history) + 1, player, symbol, move))
if won:
self._winner = player
def after_move(self, player: str, move: Cell) -> None:
self.emit(f"{player} plays {self._by_id[player].symbol.value} at {move}", actor=player)
def is_over(self) -> bool:
return self._winner is not None or self.board.is_full()
def winner(self) -> str | None:
return self._winner
# -- what the template does not give you -------------------------------------------
def submit_move(self, player: str, cell: Cell) -> Move:
"""The UI path: one externally supplied move, turn-checked before anything moves."""
with self._lock:
self.require_turn(player)
self._buffered = cell
try:
self.play_turn()
finally:
self._buffered = None
return self._history[-1]
def undo(self) -> Move:
"""Take back the last move: invert the board change, restore the cursor Memento."""
try:
with self._lock:
if not self._history:
raise NothingToUndoError("no move to undo")
move = self._history.pop()
self.board.clear(move.cell)
self._winner = None # only the last move can have completed a line
self.restore(self._cursors.pop())
self.emit(f"undo: {move.player_id} takes back {move.cell}", actor=move.player_id)
return move
finally:
self.flush_events()
def history(self) -> tuple[Move, ...]:
with self._lock:
return tuple(self._history)
def replay(self) -> list[str]:
"""Rebuild every position from the move log; frame 0 is the empty board."""
board = Board(self.board.size)
frames = [board.render()]
for move in self.history():
board.place(move.cell, move.symbol)
frames.append(board.render())
return frames
The renderer stores text only, so it never reads a board that another thread is halfway through mutating:
code/lld/tic_tac_toe/services.py — renderer
class BoardRenderer:
"""Observer: the game emits events, the renderer decides what a screen looks like.
It stores only text, so it never reaches back into the board while another thread
is mid-turn; call ``render`` when you want the current position.
"""
def __init__(self, game: TicTacToeGame) -> None:
self._game = game
self._lock = threading.Lock()
self._lines: list[str] = []
game.subscribe(self)
def on_event(self, event: GameEvent) -> None:
with self._lock:
self._lines.append(str(event))
def transcript(self) -> list[str]:
with self._lock:
return list(self._lines)
def render(self) -> str:
status = self._game.status
header = f"{self._game.current_player} to play" if status is GameStatus.IN_PROGRESS else str(status)
return f"{header}\n{self._game.board.render()}"
Running python -m lld.tic_tac_toe.demo plays a scripted win on the main diagonal, takes it back, shows both rejections, then lets two perfect bots draw:
--- game 1: X takes the main diagonal ---
[ 0] game started
[ 1] X plays X at (0,0)
[ 2] O plays O at (0,1)
[ 3] X plays X at (1,1)
[ 4] O plays O at (0,2)
[ 5] X plays X at (2,2)
[ 5] X wins
result: won, winner X, 5 turns
X|O|O
.|X|.
.|.|X
--- undo: in_progress, X to play, 4 turns on the clock ---
NotYourTurnError: it is X's turn, not O's
CellOccupiedError: cell (0,0) already holds X
--- game 2: minimax against minimax ---
result: drawn after 9 turns; replay rebuilds 10 frames
X|X|O
O|O|X
X|O|X
Concurrency and edge cases¶
Which lock protects what. There is one lock, BoardGame._lock, and the granularity argument is the opposite of the parking lot's. A parking lot is a large aggregate with independent parts, so it locks per floor. A game is a small aggregate whose parts are not independent — the board, the turn cursor and the winner change together — so the game object is the unit of locking. The critical section is a placement and four integer increments, roughly the cost of an uncontended mutex acquire (about 17 ns), and contention is limited to the two players of one game. A lock per cell would buy nothing and would make "is the game over" a nine-lock dance.
It is an RLock because the hooks re-enter: play_turn holds the lock and calls after_move, which calls emit, which locks again.
The race it prevents. Two clients submitting into the same game interleave at three points: the turn check, the cell check, and the status update. Holding the lock across all of submit_move makes "check it is your turn, place, judge" atomic, so the losing thread gets NotYourTurnError or CellOccupiedError and the board never records two moves for one turn. The concurrency test fires 36 submissions from eight workers at one game and asserts that the accepted count equals the number of turns, that no cell appears twice, and that symbols still alternate.
Notifying outside the lock. Events are buffered under the lock and delivered by flush_events once play_turn releases it, the same rule the parking lot's floors follow. Be precise about the exception, because an interviewer reading the code will find it: submit_move holds the reentrant lock across play_turn, so on that path delivery still runs inside its critical section. Name it, then offer the fix — drain the buffer from a queue on another thread.
Edge cases handled: a cell that is occupied or off the board (a rejected move costs no turn); a player moving out of turn or not in the game; undo on an empty history; undo of a winning move, which must reopen the game; the centre cell of an odd board incrementing both diagonals; a draw when the last cell fills; a board smaller than 3 x 3; two players sharing a symbol; a random bot constructed without a seed; and a turn limit that abandons a game rather than spinning forever.
Common mistake
Writing the diagonal counters as if row == col: ... elif row + col == n - 1: .... On a 3 x 3 board the centre sits on both diagonals, so the elif silently under-counts the anti-diagonal and a win through the middle is never detected. It is two independent if statements. The parametrized test over all eight lines exists precisely to catch this, and it is the first thing to say when you write the checker.
Extensibility and follow-ups¶
- Connect-4 and Gomoku (k-in-a-row): keep
Board, replaceWinChecker. Row and column totals stop working when a line is shorter than the board, so aKInARowCheckercounts the run through the placed cell in four directions — O(k) per move, still not a rescan. Connect-4 also changes how a cell is chosen (drop into a column), which is an override ofchoose_move, not a new class hierarchy. - Battleship (hidden boards): two boards per game and a
visible_to(player)projection. The template does not change;apply_movereturns a hit or miss andafter_moveemits an event that says less to the opponent than to the owner. - Online play:
Moveis already a serialisable command. Putsubmit_movebehind a request handler, keep one game object per match, and the existing lock is what makes two sockets safe. Reconnect isreplay(). - Move timers: inject a
Clock, stamp eachMove, and add aTIMED_OUTtransition intoABANDONED. Nothing else moves, because time already enters through an interface elsewhere in the handbook. - A stronger or faster bot: alpha-beta pruning on top of the existing negamax, or an opening book keyed by
Board.snapshot. Both are internal toMinimaxMove. - Redo: keep the popped
MoveandTurnCursoron a second stack. Undo and redo become symmetric, which is the argument for having stored the cursor rather than recomputing it.
Interview tip
Say "the skeleton is shared, the rules are not" before you draw anything, then write BoardGame.play first and leave the abstract methods empty. You have now shown the interviewer the extension seam, and every follow-up — snake and ladder, Connect-4, bowling — is answered with "that is a new subclass, and here is which method it overrides." Candidates who write the 3 x 3 grid first end up rewriting it when the follow-up arrives.
Tests¶
tests/test_tic_tac_toe.py has 21 cases. The two worth walking through in an interview are the parametrized line test — it is the anti-diagonal regression guard — and undo after game over, which is the only transition that leaves a terminal status.
code/lld/tic_tac_toe/tests/test_tic_tac_toe.py — every line, both diagonals
@pytest.mark.parametrize("line", LINES_3X3)
def test_every_row_column_and_both_diagonals_win(line: list[Cell]) -> None:
"""The anti-diagonal cases fail the moment the checker uses elif for the second diagonal."""
elsewhere = [Cell(r, c) for r in range(3) for c in range(3) if Cell(r, c) not in line]
game = game_with(line, elsewhere[:2])
result = game.play()
assert (result.winner, result.turns) == ("X", 5)
def test_centre_cell_counts_towards_both_diagonals() -> None:
checker = WinChecker(3)
assert checker.record(Cell(1, 1), Symbol.CROSS) is False
assert checker.record(Cell(0, 0), Symbol.CROSS) is False
assert checker.record(Cell(2, 2), Symbol.CROSS) is True # main diagonal complete
checker.erase(Cell(2, 2), Symbol.CROSS)
assert checker.record(Cell(0, 2), Symbol.CROSS) is False
assert checker.record(Cell(2, 0), Symbol.CROSS) is True # anti-diagonal, same centre cell
code/lld/tic_tac_toe/tests/test_tic_tac_toe.py — undo after game over
def test_undo_after_game_over_reopens_the_game() -> None:
game = game_with([Cell(0, 0), Cell(1, 1), Cell(2, 2)], [Cell(0, 1), Cell(0, 2)])
game.play()
assert game.status is GameStatus.WON
taken_back = game.undo()
assert taken_back.cell == Cell(2, 2)
assert game.status is GameStatus.IN_PROGRESS # the Memento restored the cursor
assert game.current_player == "X" and game.turns == 4
assert game.board.at(Cell(2, 2)) is None # the counters were decremented too
game.submit_move("X", Cell(2, 2)) # and the same winning move still wins
assert game.result().winner == "X"
The concurrency case asserts the invariant rather than a timing outcome, which is what makes it stable in CI:
code/lld/tic_tac_toe/tests/test_tic_tac_toe.py — concurrency
def test_concurrent_submissions_never_corrupt_the_board() -> None:
game = empty_game()
cells = [Cell(r, c) for r in range(3) for c in range(3)]
def attempt(i: int) -> bool:
try:
game.submit_move("X" if i % 2 == 0 else "O", cells[i % 9])
return True
except HandbookError: # lost the turn, or the cell was already taken
return False
with ThreadPoolExecutor(max_workers=8) as pool:
accepted = sum(pool.map(attempt, range(36)))
history = game.history()
assert accepted == len(history) == game.turns
assert len({move.cell for move in history}) == len(history) # no cell written twice
symbols = [move.symbol for move in history]
assert all(a is not b for a, b in zip(symbols, symbols[1:], strict=False))
The rest cover: the happy path with the renderer transcript and replay frame count; occupied and off-board cells; out-of-turn and unknown players; a draw on a full board; unwinding every move and then refusing; minimax blocking an immediate threat; two perfect bots always drawing in nine turns; a 4 x 4 win on the diagonal; seeded bots being reproducible and unseeded bots being refused; and playing on after the game ended. Run them with uv run pytest code/lld/tic_tac_toe -q.
45-minute pacing¶
| Minutes | What to do | What to say or write |
|---|---|---|
| 0–5 | Clarify | N x N or 3 x 3? Bots? Undo? Who supplies a human move? State out of scope: networking, persistence, timers. |
| 5–10 | Entities | Nouns on the board: Game, Board, Cell, Player, Symbol, Move, WinChecker, MoveStrategy. Verbs become methods: play, place, record, choose, undo. |
| 10–16 | Skeleton | Write BoardGame.play_turn first — five lines, four abstract methods. Say that snake and ladder and bowling will subclass it. |
| 16–26 | Win detection | WinChecker.record with the four counters. Say "two ifs, not an elif" out loud and give the centre-cell reason. Then Board.place and clear as inverses. |
| 26–34 | Rules and undo | TicTacToeGame's five steps, then submit_move with the turn check and undo with the cursor Memento. Mention that undo after game over is the interesting case. |
| 34–40 | Bot and concurrency | MoveStrategy with three implementations; sketch negamax in five lines. Name the single game lock and the race it prevents. |
| 40–45 | Extensions | Connect-4 as a new WinChecker, online play as submit_move behind a socket, redo as a second stack. |
Related¶
- Template Method — the
BoardGameskeleton, and when a function taking callables beats a base class - Strategy — the interchangeable move policies
- Memento — what
TurnCursoris and where snapshots get expensive - Design snake and ladder — the same base class, dice instead of placement
- Design a bowling alley — the same base class with a turn rotation that is not round-robin
- Design chess — where the move log, undo and legality checking get genuinely hard