10 — Tic-Tac-Toe Game

This is the smallest classic object-oriented design problem. The skill is designing it without inflating it.

By the end of this chapter you will be able to:

• Name the three or four objects the problem needs.
• Justify the objects you deliberately left out.
• Write a board class that runs unchanged on a 3x3 or a 19x19 grid.
• Say exactly where the fast win check stops being correct, and show the counterexample.
• State the cost of a perfect computer opponent as nodes searched.

The design is worked as runnable Python.

What an OOD interview is, and what makes this one different

An object-oriented design (OOD) interview hands you an English description of a system and asks you to turn it into classes: which objects exist, what each one is responsible for, and how they refer to each other.

The trap in this one is over-engineering. It is the only OOD question where the failure mode is producing too much design. The board is nine cells. A candidate who reaches for an abstract Piece hierarchy, a MoveValidator chain of responsibility, a GameStateFactory, and an Observer for the scoreboard has spent 40 minutes signalling that they cannot tell a small problem from a big one.

Those four names are all real design patterns. Each one is defined below at the point where this chapter refuses it, so you can refuse them by name and with a reason.

Keep the design tight, then spend the round on the two parts that are genuinely interesting:

1. A win check that touches a constant number of values per move rather than rescanning the board.
2. A model that generalizes to an n x n grid needing k marks in a row without a rewrite.

The rules, stated once

The generalizations later need something to generalize from, so pin the rules down first.

Two players alternate, X first. Each claims one empty cell of a 3x3 grid per turn. The first player to occupy three cells in a straight line — a full row, a full column, or one of the two long diagonals — wins immediately. If all nine cells fill with no such line, the game is a draw.

Two links, offered for depth and not needed to follow this chapter. The interview method — how to spend the 45 minutes — is 02 — a framework for the OOD interview. The pattern vocabulary is 03 — object-oriented programming (OOP) fundamentals. Every pattern this chapter names is also defined where it arrives, so you can read straight through.

What goes in, and what comes out

Fix the shape of the problem before drawing a single class. The system accepts exactly one kind of request and answers three questions about it.

The block below is not code you can run yet — it names the calls the design has to support and the shape of what each one returns. The names on the right (game.play, board.at, game.over) are the methods you will find in Working python.

IN   a move        "X takes row 0, column 2"
                   -> game.play(0, 2)

OUT  a verdict     whether that very move completed a line, and for whom
                   -> Mark.X, or None if the game continues

OUT  a cell        who occupies a given square, asked at any time
                   -> board.at(0, 2) is Mark.X

OUT  a terminal    whether the game has ended at all, by a win or by a
     signal        full board with no line
                   -> game.over() is True

The verdict is an output of the move itself, not a separate query. play returns the winner; there is no check_for_win() that a caller has to remember to invoke.

That single choice is what the rest of the chapter defends. The moment a mark lands is the only moment the answer can change, so the answer is computed there, cheaply, instead of being recomputed by scanning the whole grid on every query.

1. Clarifying questions that change the design

Only two questions are worth asking before you start typing, and each one changes something concrete downstream. Ask them, then start coding. Spending five minutes on requirements for tic-tac-toe is itself a negative signal.

Why the second row is not a hypothetical

n x n with k-in-a-row is a real game. Gomoku is the standard board game of that shape, usually played as five in a row on a 15x15 or 19x19 grid.

It is the variant interviewers reach for when they want to see whether your fast win check was fast for a reason you understood, or fast because you copied it.

Everything else — undo, replay, several simultaneous games, a network protocol — is an extension. Say “the design supports that; ask me and I will show you” rather than building it up front.

2. Core objects, and why so few

The full inventory is three objects, four with a computer opponent — and on this question the omissions are the argument, so the classes the design refuses get equal time below.

An enum, short for enumeration, is a type whose values are a fixed, named, closed list — here exactly two, Mark.X and Mark.O. That closed-list property is the whole reason it beats a class hierarchy: X and O differ by one printed symbol and by nothing else, and an enum says so in three lines.

The four objects this design refuses

Each of the next four paragraphs names a class a candidate commonly adds, defines the pattern behind it, and gives the reason it does not pay here.

There is no Cell class. A cell is either empty or holds a mark, which Python spells Optional[Mark] — a value that is either a Mark or the special empty value None. Wrapping that in an object buys a field and a constructor and costs a layer of indirection on every read.

There is no MoveValidator. Validation is four comparisons inside Board.place: two that the row is on the board, two that the column is. Extracting them into a class makes the code longer and the bounds check harder to find. The pattern a candidate usually reaches for here is chain of responsibility, where a request is passed down a list of handler objects until one of them deals with it. It earns its place when the set of handlers is configured at run time. Here it is four < signs known at authoring time.

There is no Observer for the display. Observer is the pattern where an object publishes events and an unknown number of subscribers register to receive them, so the publisher never names its listeners. A command-line-interface game with one board and one renderer does not need a subscription mechanism, because the loop that called play already knows the board changed and can simply redraw. Observer earns its place when the number of listeners is unknown at the time the publisher is written, which here it is not.

There is no GameStateFactory. A factory is an object whose job is choosing which concrete class to instantiate, and it pays for itself when that choice is genuinely conditional. Here there are three outcomes — in progress, won, drawn — and they are one nullable winner field plus a full-board test.

3. Class diagram

The model as one picture. The arrowheads carry claims that the boxes do not, so after a note on notation, every line is read back as an English sentence.

classDiagram
    class Mark {
        <<enumeration>>
        X
        O
        +other() Mark
    }
    class Board {
        +int n
        +int k
        +place(r, c, mark) bool
        +unplace(r, c)
        +at(r, c) Mark
        +free() List
        +full() bool
    }
    class Game {
        +Mark turn
        +Mark winner
        +play(r, c) Mark
        +over() bool
        +undo()
    }
    class Move {
        +int row
        +int col
        +Mark mark
    }
    class Player {
        <<interface>>
        +choose(board, mark) Move
    }
    class HumanPlayer
    class MinimaxPlayer

    Game "1" *-- "1" Board : owns
    Game "1" *-- "0..*" Move : history, for undo
    Game "1" o-- "2" Player : plays, does not own
    Board ..> Mark : stores
    Player <|.. HumanPlayer
    Player <|.. MinimaxPlayer

Reading the notation

This is a UML class diagram. UML is the Unified Modeling Language, the standard set of shapes for drawing software structure.

• Each box is a class. The lines inside a box are its fields and methods, and a leading + means public, visible to code outside the class.
• <<enumeration>> marks the fixed-list type described above, so X and O inside the Mark box are values rather than fields.
• <<interface>> marks a class that is only a promise of methods, with no implementation of its own.
• The quoted numbers at the ends of a line are multiplicities, meaning how many objects sit at that end: 1 is exactly one, 2 is exactly two, 0..* is any number including none.

Four line styles appear here and they mean four different things.

• *--, a filled diamond, is composition: the owner controls the part’s lifetime, so destroying the owner destroys the part.
• o--, a hollow diamond, is aggregation: a “has a” relationship that does not control lifetime, so the part can outlive the whole or be shared with someone else.
• ..>, a dashed open arrow, is a dependency: the class at the tail merely uses or mentions the class at the head, without holding it as a structural part.
• <|.., a hollow triangle on a dashed line, is realization: the class at the tail implements the interface at the head without inheriting any code from it.

Reading the lines back as sentences

Each of the six relationship lines is a claim. Here is each one spelled out.

A Game composes exactly one Board and owns it, so the board is created with the game and dies with it. There is no board that outlives the game it belongs to.

A Game also composes any number of Move objects as its history, for undo — the ordered record of what was played, which exists only to be walked backwards.

A Game aggregates exactly two Player objects, and the label plays, does not own is the hollow diamond spelled out: the same human or computer player object can sit down at a second game, or at several games at once, without being copied.

Board has a dashed dependency on Mark labelled stores, meaning cells hold Mark values but a board is not made of marks the way it is made of cells. Swap the enum and the board’s structure is unchanged.

Finally, HumanPlayer and MinimaxPlayer each realize the Player interface. That is the claim that whatever drives a turn — a person typing, or the search algorithm of Now add an ai opponent — is interchangeable to the game loop, which never learns which it got.

Four boxes plus an optional player interface. A nine-box diagram for this problem is itself the answer to the over-engineering trap.

Where the diagram and the code differ, and why

A diagram is the design; Working python is the smallest code that satisfies it. Three boxes are drawn fuller than the 3x3 code needs; state this before an interviewer points it out.

What this class structure assumes

A class diagram is a frozen bet about what will change. Every interface you draw says “I expect this to vary”; every field you hard-code says “I expect this to hold forever”.

Naming those bets is the transferable skill; tic-tac-toe is only the vehicle for it. The general form of the argument is What a class structure assumes; what follows is this design’s version.

Assumed to vary — and therefore given a parameter or an interface:

Assumed fixed — and therefore baked into the structure rather than into a parameter:

The largest assumption is deliberate and worth stating before an interviewer finds it: the win condition is hard-coded as “a full row, column, or main diagonal”.

Board keeps one counter per row, one per column, and one for each of the two diagonals. It decides which of those a cell belongs to with the two tests r == c and r + c == n - 1. That is a claim that the shape of a winning line never changes even though the size of the board does — which is exactly the claim that breaks in Now make it n x n with k in a row, where five in a row on a fifteen-wide board is a win and a full row is not required.

Underneath that sit five more fixed bets, each cheap to state and expensive to discover late.

• There are exactly two players, because Mark.other() is a flip rather than a rotation through a list.
• Turns strictly alternate and every turn places exactly one mark, so the history is a flat list and undo is a single pop.
• Marks are permanent. Nothing captures, moves or removes an opponent’s mark, which is what makes counters monotonic between a place and its matching unplace.
• The board is square, so one n suffices where a general grid needs rows and cols.
• The grid is dense and small, so a dictionary keyed by (row, column) is a fine representation.

What a different assumption would have produced.

• If the set of winning lines were data rather than structure — a precomputed list of coordinate groups, with each cell knowing which groups it belongs to — then Board becomes a generic “did any group just fill with one mark” engine. Three-dimensional tic-tac-toe, a hexagonal board, and Connect Four’s gravity-fed columns all fall out with no new code, only a new group list. The cost is one setup pass to enumerate the groups, a per-cell index that is memory the current design does not spend, and the loss of the two one-line membership tests that make _bump readable. For k smaller than n the group list is large but finite — 572 groups on a 15x15 board needing 5 in a row, counted in Decision 1 the win check is o1 not on2 — which is why the directional scan is the better answer there than a group table.
• If turn order were data — a list of players cycled by index instead of Mark.other() — three-player and team variants cost nothing, but Mark stops being a two-member enum, undo can no longer restore the turn by flipping it, and every “the other player” in the search becomes “the next player”, which quietly changes the search from a two-sided minimax into something with no simple sign flip.
• If marks could be removed or moved — as in the three-marks-each variant where your fourth move slides your first — the counters survive, because unplace already exists and is exact, but the history stops being a stack of placements and becomes a stack of (from, to) transitions.
• If the board were sparse and unbounded, as in gomoku played on paper with no edges, the dictionary representation is already right and the row and column counters are already wrong, because there is no bound for a counter to reach. The directional scan is the only survivor.

What is data and what is code

Tic-tac-toe is a rules engine, so the question worth answering explicitly is which rules were written as values you can change without recompiling, and which were written as control flow.

A rule expressed as data can be edited, tested and shipped by someone who cannot read the code. A rule expressed as code can be read as a sentence and checked by a type checker. You pay for whichever one you did not pick.

The table splits every rule in this design into one bucket or the other, and names what that choice costs you later.

The bet is that board size varies and the rules do not, and for this problem that bet is correct, which is why the design stays at four boxes.

The cost of being wrong is concentrated in one place. Every rule listed as code above is a rule that a table-driven engine would have absorbed for free, and the moment two of them start varying together — different win lengths and different capture rules, say — the four-box design stops being small and starts being under-built.

Say which side of that line you think the problem is on. That judgement is what is being tested, not the pattern vocabulary.

4. Decision 1 — the win check is O(1), not O(n^2)

The win check is the one algorithmic choice in the problem. Walking it through five real moves, then counting the work both ways on concrete boards, produces the ratio that justifies the extra state.

The notation

The whole section is written in big-O, so define it first. Big-O notation describes how the work grows as the input grows, ignoring constant factors.

• O(1) means the work is bounded by a constant no matter how large the board is.
• O(k) means it grows in proportion to the win length k.
• O(n^2) means it grows with the square of the board’s side, which is to say in proportion to the number of cells.

The idea: one counter per line, per mark

Instead of storing only the grid, Board also stores a tally for every line on the board — one per row, one per column, one for each of the two diagonals — broken down by mark. When a mark lands on a cell, only the lines through that cell can have changed, and there are at most four of them.

So a move updates at most four integers and compares the largest of them to n. Nothing else is read.

flowchart TD
    A[Mark placed at r, c] --> B[Update the 2 to 4 counters through that cell]
    B --> C[Take the largest updated counter]
    C --> D{Largest equals n?}
    D -->|yes| E[This move wins]
    D -->|no| F[Game continues]

A worked instance: five moves, and every counter they touch

Follow the row-win game from Working python: X plays (0,0), O plays (1,0), X plays (0,1), O plays (1,1), X plays (0,2). The board is 3x3, so n = 3 and a counter reaching 3 is a win.

Each row is one move. “Counters touched” is what _bump increments; “longest run returned” is what it hands back to place, which compares it to n.

Three details in that table carry the argument.

• Move 4 is the maximum case: the centre cell of a 3x3 board sits on both diagonals, so it touches four counters. No move ever touches more.
• Move 5 wins because row0[X] reached 3, which equals n. Nothing scanned the grid; one integer crossed a threshold.
• Every counter that stayed at 0 was never read. That is the whole saving.

Counting the rescan when k equals n

The obvious alternative rescans the board after every move. Count the cell reads.

When k equals n — classic tic-tac-toe, and gomoku played on a full-length line — a rescan reads n rows of n cells, n columns of n cells, and two diagonals of n cells. For n = 3:

rows      3 * 3   = 9
cols      3 * 3   = 9
diagonals 2 * 3   = 6
9 + 9 + 6         = 24

The incremental version touches at most 4 counters per move, as move 4 in the table above showed. Each touch is a read-modify-write of a single integer, so 4 is the honest number to compare against 24.

24 / 4    = 6

That is 6x less work on a 3x3 board, and the ratio is (2n^2 + 2n) / 4, so it grows with the square of the board’s side.

The numerator counts the rescan: n^2 cells read once for the rows, n^2 again for the columns, and 2n for the diagonals. The denominator stays at 4 forever. For a 19x19 board:

2 * 19 * 19       = 722
2 * 19            = 38
(722 + 38) / 4    = 190

Counting the rescan when k is smaller than n

Now the rescan gets much worse, because every window of k consecutive cells anywhere on the board is a candidate line, not just the full rows and columns.

A window here means a run of k adjacent cells along one direction. On an n x n board the window count is:

horizontal windows   n * (n - k + 1)
vertical windows     n * (n - k + 1)
diagonal windows     (n - k + 1)^2  each way

Each expression reads as “how many starting positions fit”. A row of n cells holds n - k + 1 distinct windows of length k, and there are n rows. For gomoku, with n = 15 and k = 5:

horizontal   15 * 11    = 165
vertical     15 * 11    = 165
diag         11 * 11    = 121
anti-diag    11 * 11    = 121
165 + 165 + 121 + 121   = 572 windows
572 * 5                 = 2860 cell reads

The final multiplication is by k, because checking one window means reading all k of its cells. So a full rescan of a 15x15 gomoku board is 2,860 cell reads per move.

The incremental version instead walks outward from the cell just placed. It follows 4 line directions, in 2 opposite rays each, taking at most k - 1 steps per ray before it either runs out of matching marks or has already found its win.

directions             4    horizontal, vertical, diagonal, anti-diagonal
rays per direction     2    forward and backward
steps per ray, k - 1   4    the placed cell is already counted, so k - 1 = 4
4 * 2 * 4                 = 32
2860 / 32                 = 89.375

That is roughly 89x fewer reads. And the incremental cost does not depend on n at all — it is O(k) — so on a 19x19 gomoku board it is still 32 reads while the rescan grows to 5,100:

horizontal   19 * 15    = 285
vertical     19 * 15    = 285
diag         15 * 15    = 225
anti-diag    15 * 15    = 225
285 + 285 + 225 + 225   = 1020 windows
1020 * 5                = 5100 cell reads

The second payoff: counters are reversible

Running counters have one more property that matters for Now support undo: they are reversible.

Taking a move back is a decrement rather than a recomputation, so undo is O(1) too, and you get it without storing a copy of the board after every move.

What the counters cost

Board now holds an invariant — a property that must be true before and after every operation — spanning four separate data structures. Any code path that writes the cell dictionary without going through place or unplace silently corrupts the win check without raising anything.

That is a real risk, and it is the reason the cell dictionary is private and is mutated only by those two methods. A rescan has no such hazard, which is why it is the right choice for a one-off script and the wrong choice inside a search loop that places and unplaces millions of times.

5. Working Python

Now the whole design as running code, followed by the assertions that prove each claim made above. Every idiom used is explained immediately after the block.

The classes

Read this block top to bottom in three parts: Mark is the two-value enum, Board owns the grid plus the counters from Decision 1 the win check is o1 not on2, and Game owns turn order and history. The method to study is _bump, which is the worked table above expressed in eight lines.

from __future__ import annotations

from enum import Enum
from typing import Dict, List, Optional, Tuple

class Mark(Enum):
    X = "X"
    O = "O"

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

class Board:
    """n x n board with per-line running counters. Win check is O(1) per move."""

    def __init__(self, n: int = 3):
        self.n = n
        self._cells: Dict[Tuple[int, int], Mark] = {}
        self._row: List[Dict[Mark, int]] = [{} for _ in range(n)]
        self._col: List[Dict[Mark, int]] = [{} for _ in range(n)]
        self._diag: Dict[Mark, int] = {}
        self._anti: Dict[Mark, int] = {}

    def _bump(self, r: int, c: int, m: Mark, delta: int) -> int:
        """Adjust the 2-4 counters this cell belongs to; return the longest."""
        self._row[r][m] = self._row[r].get(m, 0) + delta
        self._col[c][m] = self._col[c].get(m, 0) + delta
        best = max(self._row[r][m], self._col[c][m])
        if r == c:
            self._diag[m] = self._diag.get(m, 0) + delta
            best = max(best, self._diag[m])
        if r + c == self.n - 1:
            self._anti[m] = self._anti.get(m, 0) + delta
            best = max(best, self._anti[m])
        return best

    def place(self, r: int, c: int, m: Mark) -> bool:
        """Place a mark. Returns True if it completed a line."""
        if not (0 <= r < self.n and 0 <= c < self.n):
            raise ValueError("off board: %r" % ((r, c),))
        if (r, c) in self._cells:
            raise ValueError("occupied: %r" % ((r, c),))
        self._cells[(r, c)] = m
        return self._bump(r, c, m, +1) == self.n

    def unplace(self, r: int, c: int) -> None:
        """Exact inverse of place. This is why undo and search are cheap."""
        self._bump(r, c, self._cells.pop((r, c)), -1)

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

    def full(self) -> bool:
        return len(self._cells) == self.n * self.n

    def free(self) -> List[Tuple[int, int]]:
        return [(r, c) for r in range(self.n) for c in range(self.n)
                if (r, c) not in self._cells]

class Game:
    def __init__(self, n: int = 3):
        self.board = Board(n)
        self.turn: Mark = Mark.X
        self.winner: Optional[Mark] = None
        self.history: List[Tuple[int, int]] = []

    def over(self) -> bool:
        return self.winner is not None or self.board.full()

    def play(self, r: int, c: int) -> Optional[Mark]:
        if self.over():
            raise ValueError("game is over")
        won = self.board.place(r, c, self.turn)
        self.history.append((r, c))
        if won:
            self.winner = self.turn
        else:
            self.turn = self.turn.other()
        return self.winner

    def undo(self) -> None:
        r, c = self.history.pop()
        self.board.unplace(r, c)
        if self.winner is None:          # a non-winning move had flipped the turn
            self.turn = self.turn.other()
        self.winner = None

The Python idioms in that block

Taken in the order they appear.

• from __future__ import annotations tells the interpreter to store every type annotation as text rather than evaluating it. That is what lets a method mention a type that does not exist yet, and it keeps newer annotation syntax working on older interpreters. It must be the first statement in a file.
• The bracketed names from typing are type hints, documentation the interpreter does not enforce. Dict[Tuple[int, int], Mark] says “a dictionary whose keys are pairs of integers and whose values are marks”. Optional[Mark] says “a mark or None”. List[...] says “a list of”.
• The leading underscore in _cells and _bump is a convention, not enforcement. It says “this is internal, do not touch from outside”, and that convention is the only thing protecting the invariant described at the end of Decision 1 the win check is o1 not on2.
• self is Mark.X compares identity rather than value, which is the correct test for enum members because each member is a single shared object.
• [{} for _ in range(n)] is a list comprehension building n separate empty dictionaries. _ is the conventional name for a loop variable you never read.
• self._row[r].get(m, 0) reads a dictionary key with a default, so the first time a mark appears in a row the counter reads 0 instead of raising KeyError.
• "%r" % ((r, c),) is old-style string formatting inserting the pair’s debug representation. The extra comma makes a one-element tuple, so the pair is formatted as a whole rather than being spread across two placeholders.
• raise ValueError(...) aborts the call with an error the caller can catch. That is how place refuses an illegal move without returning a special value that someone will forget to check.

Why undo flips the turn only sometimes

The one line in Game that looks wrong is if self.winner is None: inside undo. It is there because play flips the turn only when the move did not win.

So undoing a losing-or-neutral move has to flip back, and undoing the winning move must not — the turn was never advanced past the winner. Both branches then clear winner, which is a no-op in the first case.

The tests

An assert raises immediately if its condition is false, so a block of assertions that runs to completion is a passing test. Each group below is labelled with the claim it is checking.

# --- row win ---------------------------------------------------------------
g = Game()
for mv in [(0, 0), (1, 0), (0, 1), (1, 1)]:
    g.play(*mv)
assert g.winner is None
assert g.play(0, 2) is Mark.X          # X completes the top row
assert g.over()

# --- undo restores everything, including whose turn it is ------------------
g.undo()
assert g.winner is None and g.turn is Mark.X and not g.over()
assert g.board.at(0, 2) is None
assert g.play(0, 2) is Mark.X          # and the same move still wins

# --- a full board with no line is a draw, not a win ------------------------
d = Game()
for mv in [(0, 0), (0, 1), (0, 2), (1, 1), (1, 0), (1, 2), (2, 1), (2, 0), (2, 2)]:
    d.play(*mv)
assert d.winner is None and d.board.full() and d.over()

# --- illegal moves are rejected, and reject cleanly ------------------------
try:
    d.play(0, 0)
    raise AssertionError("should have refused: game over")
except ValueError:
    pass

e = Game()
e.play(1, 1)
for bad in [(1, 1), (3, 0), (-1, 0)]:
    try:
        e.play(*bad)
        raise AssertionError("should have refused %r" % (bad,))
    except ValueError:
        pass
assert len(e.history) == 1             # a rejected move left no trace

# --- the same class plays 4x4 with no changes ------------------------------
big = Game(4)
for i in range(3):
    big.play(i, i)                     # X on the diagonal
    big.play(i, (i + 1) % 4)           # O elsewhere
assert big.play(3, 3) is Mark.X        # X completes a 4-long diagonal

Two idioms there are worth naming.

• g.play(*mv) uses the star operator to unpack a pair into two positional arguments, so g.play(*(0, 0)) is exactly g.play(0, 0).
• The try / except ValueError / pass blocks assert that a call fails. The raise AssertionError line is reached only if the illegal move was wrongly accepted, and pass is the do-nothing statement that makes catching the expected error the success path.

What those tests actually prove

The rejected-move test is the one carrying real weight. A move that is refused must leave no trace at all — no history entry, no counter increment, no turn flip. place achieves that by validating before it writes anything, and play appends to the history only after place returns. The len(e.history) == 1 assertion is what proves it.

The n = 4 case at the bottom is the whole argument for the counter design. Board was written against self.n and never against the literal 3, so “make it n x n” is a constructor argument rather than an edit. Trace it: X takes (0,0), (1,1), (2,2) and then (3,3), so diag[X] climbs 1, 2, 3, 4 and hits n = 4 on the last move. Not one line of Board changed.

6. Extension scenarios

Three follow-ups, each stated the way an interviewer states it. For each one the useful answer has the same parts: what changes, what does not, why the design absorbed it, and what it still costs.

“Now make it n x n with k-in-a-row”

What changes. The counters stop working, because a row counter reaching k no longer means the k marks are adjacent. Five X’s scattered across a fifteen-wide row is not a win, and the counter cannot tell the difference because it only ever knew a total.

The fix is to replace the return value of _bump with a directional scan outward from the cell just placed.

What does not change. Game, undo, the history, the player interface and the class diagram are all untouched. The win check was already a single method returning a boolean, so replacing its body replaces the rule.

Why the design absorbed it. place promised its caller one thing — “true if this move won” — and never promised how it knew.

The function below is that replacement, written standalone so you can read it without the rest of Board. It takes the cell dictionary, the board size n, the win length k, and the coordinates just played. The two assertions at the bottom are a real five-in-a-row on a 15x15 board.

from typing import Dict, Optional, Tuple

DIRS = ((0, 1), (1, 0), (1, 1), (1, -1))   # horiz, vert, diag, anti-diag

def wins_at(cells: Dict[Tuple[int, int], object], n: int, k: int,
            r: int, c: int) -> bool:
    """O(k) win check for k-in-a-row: walk both rays of each of 4 directions."""
    m = cells[(r, c)]
    for dr, dc in DIRS:
        run = 1
        for sign in (1, -1):
            rr, cc = r + dr * sign, c + dc * sign
            while (0 <= rr < n and 0 <= cc < n
                   and cells.get((rr, cc)) is m and run < k):
                run += 1
                rr, cc = rr + dr * sign, cc + dc * sign
        if run >= k:
            return True
    return False

cells = {(7, c): "X" for c in range(3, 8)}          # five in a row, cols 3-7
assert wins_at(cells, 15, 5, 7, 5)
assert not wins_at(cells, 15, 6, 7, 5)              # six-in-a-row not met

Four things in that function are worth naming.

• DIRS holds one (row step, column step) pair per line direction. (0, 1) steps sideways, (1, 0) steps downwards, (1, 1) steps down-right along a diagonal, and (1, -1) steps down-left along the opposite diagonal.
• Multiplying a direction by sign, which takes the values +1 and -1 in turn, walks the two opposite rays of the same line — right and left, up and down — without writing eight direction pairs.
• run starts at 1 to count the cell just placed, and the guard run < k stops the walk the instant enough have been counted. That is what makes the cost O(k) rather than O(n).
• The dictionary values here are plain strings rather than Mark values, and the is comparison still works because Python reuses one object for a short literal string. In production code that comparison should be ==.

The counterexample the counters get wrong

The board below has five X’s in row 7, but with a hole at column 5. A row counter would read exactly 5 and declare a win.

col     3  4  5  6  7  8
row 7   X  X  .  X  X  X

gapped = {(7, 3): "X", (7, 4): "X", (7, 6): "X", (7, 7): "X", (7, 8): "X"}
assert not wins_at(gapped, 15, 5, 7, 7)             # counters would say "win"

That last assertion is the bug the naive generalization ships. Those five X’s sit in one row, so a row counter reads 5, but the gap at column 5 means the longest adjacent run is 3 — columns 6, 7 and 8 — and there is no win at all.

Volunteer that failure. Noticing that the fast trick has a precondition is worth more in an interview than the trick.

What it costs. The win check is no longer constant time, and Board now carries a k that must be validated against n. The counters can stay for the case where k equals n, but keeping both paths means keeping both correct, which is a maintenance bill you should price out loud rather than pay silently.

“Now add an AI opponent”

AI here means artificial intelligence in its narrowest useful sense: a function that is handed a position and returns a move.

The standard one for a small two-player game with no hidden information is minimax. Enumerate every legal move, then every reply, and so on to the end of the game, scoring each final position from one player’s point of view and assuming both sides play their best.

What changes. One Player implementation, and nothing else.

What does not change. Game and Board do not move, because place and unplace were already an exact inverse pair — which is precisely what a search needs, since it will try a move, explore everything beneath it, and take it back millions of times.

The search

minimax returns a (score, move) pair. The score is +1 if the player to move wins, 0 for a draw, -1 if they lose. nodes is a counter the caller passes in so the cost can be measured rather than asserted.

from typing import Optional, Tuple

def minimax(board, turn, nodes) -> Tuple[int, Optional[Tuple[int, int]]]:
    """Score from `turn`'s point of view: +1 win, 0 draw, -1 loss."""
    nodes[0] += 1
    if board.full():
        return 0, None
    best, best_move = -2, None
    for (r, c) in board.free():
        if board.place(r, c, turn):
            score = 1                                   # this move wins outright
        else:
            score = -minimax(board, turn.other(), nodes)[0]
        board.unplace(r, c)
        if score > best:
            best, best_move = score, (r, c)
        if best == 1:
            break                                       # cannot beat a win
    return best, best_move

Three things in that function deserve naming.

• nodes is a one-element list used as a counter that survives across recursive calls. Python passes lists by reference, so nodes[0] += 1 in a deep call is visible to the original caller, whereas a plain integer argument would be a fresh copy in every frame.
• The minus sign in -minimax(board, turn.other(), nodes)[0] is the trick that makes one function serve both players. A position worth +1 to your opponent is worth -1 to you, so recursing with the roles swapped and negating the result avoids writing separate maximizing and minimizing branches.
• best starts at -2, one below the worst real score of -1, so the first move examined always improves on it.

Wrapping it as a Player

This is the MinimaxPlayer box from the class diagram, made real. It is four lines, because all the interface ever promised was “hand me a board and a mark, get back a move”.

class MinimaxPlayer:
    """Player: choose(board, mark) -> (row, col). Perfect on 3x3."""

    def __init__(self):
        self.last_nodes = 0

    def choose(self, board, mark) -> Optional[Tuple[int, int]]:
        counter = [0]
        _, move = minimax(board, mark, counter)
        self.last_nodes = counter[0]
        return move

p = MinimaxPlayer()
b = Board()
assert p.choose(b, Mark.X) == (0, 0)   # from an empty board, the corner
assert p.last_nodes == 66275           # exact node count, measured not guessed
assert b.free() == [(r, c) for r in range(3) for c in range(3)]

The third assertion is the one worth pausing on. After a search that placed and unplaced tens of thousands of times, the board is byte-for-byte where it started. That is unplace being an exact inverse, and it is the reason no snapshotting is needed anywhere in this design.

p.choose(b, Mark.X) takes roughly 0.4 seconds on a laptop. That is the real cost of exact play on 3x3.

The cost, stated out loud

Three numbers, all produced by running the code above rather than estimated.

distinct complete games (search leaves)      255,168
recursive calls, `if best == 1: break` gone   340,858
recursive calls, cutoff in place               66,275
340,858 / 66,275                             = 5.14

Read them in order. 255,168 is the number of distinct complete tic-tac-toe games — every legal sequence of moves, counting a game as finished the moment somebody wins. (It is smaller than 9! = 362,880, the number of orderings of all nine cells, precisely because most games end before the board fills.)

340,858 is how many times minimax calls itself to search all of that. 66,275 is the same search with the one-line if best == 1: break cutoff, which stops examining sibling moves once a winning one is found. One line of code removes 80% of the work.

That is milliseconds of work, so 3x3 is solvable exactly and a minimax player is unbeatable. The search above scores the empty board at 0, which is the formal statement that the best either side can force is a draw.

Why this stops working at 4x4

An n x n board is not solvable this way. A 4x4 board has 16 cells:

16! = 20,922,789,888,000

At an optimistic 10 million positions examined per second:

20,922,789,888,000 / 10,000,000   = 2,092,278.99
2,092,278.99 / 86,400             = 24.22

The first division converts positions into seconds. The second divides by the 86,400 seconds in a day. That is 24 days to choose one move.

So beyond 3x3 the answer is three things layered together:

• Alpha-beta pruning, a refinement of minimax that stops exploring a branch as soon as the score already found elsewhere proves the opponent would never allow it.
• A depth limit, so the search stops after a fixed number of plies instead of reaching the end of the game.
• A heuristic evaluation, meaning an approximate score for a position the search stopped at before the game ended.

The Player interface absorbs all of that without changing, because it only ever promised to return a move. Game never learns which kind of player it got.

“Now support undo”

What changes. Nothing, and that is the interesting part. Undo was already built, as a side effect of a decision made for speed.

Two designs were available, and the table compares them on the three axes that decide it.

Command is the pattern in which a request is turned into an object carrying everything needed to perform it and, ideally, to reverse it.

unplace is the exact inverse of place because the counters are additive: undoing a move is a -1 where the move was a +1, and nothing else in the board’s state ever changed.

The reason undo was free is that the win check had been made incremental for a completely different reason. That kind of second-order payoff is exactly what is worth naming out loud in an interview.

The version that buys redo

You do not need this for tic-tac-toe. It is here so you can show you know what the full pattern looks like and then decline it.

Formalizing a move as a real Command object buys redo and replay:

from dataclasses import dataclass
from typing import List

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

    def do(self, game):
        return game.play(self.row, self.col)

    def undo(self, game):
        game.undo()

class History:
    """Undo/redo stack. Any new move truncates the redo branch."""

    def __init__(self):
        self.done: List[PlaceCommand] = []
        self.undone: List[PlaceCommand] = []

    def execute(self, game, cmd: PlaceCommand):
        cmd.do(game)
        self.done.append(cmd)
        self.undone.clear()

    def undo(self, game):
        if self.done:
            cmd = self.done.pop()
            cmd.undo(game)
            self.undone.append(cmd)

    def redo(self, game):
        if self.undone:
            self.execute(game, self.undone.pop())

A short run of it, so the truncation rule is concrete rather than asserted:

h, hg = History(), Game()
h.execute(hg, PlaceCommand(0, 0))       # X top-left corner
h.execute(hg, PlaceCommand(1, 1))       # O centre
h.undo(hg)                              # take O's move back
assert hg.board.at(1, 1) is None and len(h.undone) == 1
h.redo(hg)                              # and put it back
assert hg.board.at(1, 1) is Mark.O and h.undone == []

h.undo(hg)                              # undo O again...
h.execute(hg, PlaceCommand(2, 2))       # ...then play somewhere else
assert h.undone == []                   # the redo branch is gone for good
assert hg.board.at(1, 1) is None and hg.board.at(2, 2) is Mark.O

Three idioms in those blocks.

• @dataclass is a decorator that writes a class’s constructor, its equality test and its printable representation from the annotated fields alone, so the three lines above are a complete value type.
• frozen=True makes instances immutable, which is what you want for a command you intend to keep in a history and possibly replay.
• The two lists are stacks — append pushes, pop removes the most recent — and self.undone.clear() inside execute implements the rule in the docstring. Once you undo a few moves and then play a different one, the moves you undid can never be redone, because they are no longer reachable from the position you are in. The last three assertions are that rule firing.

What it costs. Every move now allocates an object, and the game has two stacks that must stay consistent with Game.history, which is duplicated state and therefore a source of bugs.

For tic-tac-toe that is over-engineering unless redo was actually asked for. Say that out loud. The reason to show the Command version at all is to demonstrate that you know when not to reach for it.

7. What interviewers probe

The same material, compressed into the form it arrives in: a question, and the answer that ends the follow-up.

8. Cheat sheet

Everything above, reduced to one card for the morning of the interview.

Next: 11 — Blackjack Game, where the rules genuinely are complicated enough to need the machinery this chapter refused.