How to design Tic-Tac-Toe

In this lesson, we’ll model tic-tac-toe with the fewest objects it actually needs and name every pattern we deliberately leave out. By the end you’ll be able to defend a four-class design, write a win check that reads only a handful of values per move, and grow the board to n x n without a rewrite.

Tic-tac-toe is the smallest classic object-oriented design problem, and the skill it teaches is restraint: modelling it with the few objects it actually needs, and knowing exactly which patterns to leave out and why.

Two parts of the design are genuinely interesting, and we spend most of our length there:

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

Object-oriented design means turning an English description of a system into classes: which objects exist, what each one is responsible for, and how they refer to each other. For most systems the risk is under-modelling. Tic-tac-toe is the opposite case, and worth studying precisely for that. A board of nine cells does not need an abstract Piece hierarchy, a MoveValidator chain, a GameStateFactory, or an Observer for the scoreboard. Those are all real patterns; each is defined below at the point where the design declines it, so you can name the pattern and give the reason it does not pay here.

The rules

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.

What goes in and what comes out

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

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, by a win or by a full
     signal        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. 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. That single choice is what the rest of the design defends.

Two questions that shape the design

Two questions change something concrete downstream. Everything else (undo, replay, several simultaneous games, a network protocol) is an extension the same model can absorb later.

The second row is not hypothetical. n x n with k-in-a-row is a real game: Gomoku is usually played as five in a row on a 15x15 or 19x19 grid. It is the natural stress test for whether the fast win check was fast for a reason you understood.

The objects, and why so few

The full inventory is three objects, four with a computer opponent.

An enum (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 why it beats a class hierarchy: X and O differ by one printed symbol and by nothing else, and an enum says exactly that in three lines.

The patterns this design declines

Each of these is a class commonly added to this problem. Each entry names the pattern behind it and the reason it does not pay for a nine-cell board.

• 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 empty value None. Wrapping that in an object buys a field and a constructor and costs a layer of indirection on every read.
• No MoveValidator. Validation is four comparisons inside Board.place: two that the row is on the board, two for the column. The pattern usually reached for here is chain of responsibility, where a request passes down a list of handler objects until one handles it. It earns its place when the set of handlers is configured at run time. Here it is four < signs known at authoring time.
• No Observer. 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. It earns its place when the number of listeners is unknown when the publisher is written. A command-line game with one board and one renderer is not that case: the loop that called play already knows the board changed and can redraw.
• No GameStateFactory. A factory chooses which concrete class to instantiate, and pays off 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.
• No State hierarchy. State is the pattern where each mode of an object becomes its own class and the object delegates to the current one. A three-valued winner field plus board.full() is the whole state machine here; a GameState hierarchy would be three classes replacing one nullable field.
• No Singleton. Singleton permits only one instance of a class. Game holds no global state, so a server can hold a dictionary of games keyed by id and run thousands at once. Making it a singleton would forbid exactly that.

Class diagram

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 (Unified Modeling Language) is the standard set of shapes for drawing software structure.

• Each box is a class; the lines inside are its fields and methods, and a leading + means public.
• <<enumeration>> marks the fixed-list type, so X and O inside Mark are values, not fields. <<interface>> marks a class that is only a promise of methods, with no implementation.
• The quoted numbers are multiplicities: 1 is exactly one, 2 is exactly two, 0..* is any number including none.

Four line styles carry four different claims:

• *--, filled diamond, is composition: the owner controls the part’s lifetime, so destroying the owner destroys the part. A Game composes exactly one Board and its list of Moves. Neither outlives the game.
• o--, hollow diamond, is aggregation: a “has a” that does not control lifetime. A Game aggregates two Player objects, so the same player can sit at several games at once without being copied.
• ..>, dashed open arrow, is a dependency: the tail merely uses the head. Board depends on Mark because cells hold marks, but a board is not made of marks.
• <|.., hollow triangle on a dashed line, is realization: the tail implements the interface without inheriting code. HumanPlayer and MinimaxPlayer each realize Player, so whatever drives a turn is interchangeable to the game loop, which never learns which it got.

Where the diagram and the code differ

The diagram is the design; the working Python below is the smallest code that satisfies it. Three boxes are drawn fuller than the 3x3 code needs, deliberately:

What the structure assumes

A class diagram is a bet about what will change. Every interface says “I expect this to vary”; every hard-coded field says “I expect this to hold forever”. Naming those bets is the transferable skill; tic-tac-toe is only the vehicle.

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

Assumed fixed, and therefore baked into the structure, the largest is deliberate: 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 diagonal, and decides which a cell belongs to with the 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, exactly the claim that breaks under k-in-a-row. Underneath it sit smaller fixed bets: exactly two players (so Mark.other() is a flip, not a rotation), strictly alternating single-mark turns (so history is a flat list and undo is one pop), permanent marks (so counters are monotonic between a place and its unplace), and a square, dense, small grid (so one n and a dictionary keyed by (row, col) suffice).

If any of those started varying, the model would change shape. If the set of winning lines were data (a precomputed list of coordinate groups, each cell knowing its groups) then Board becomes a generic “did any group just fill with one mark” engine, and 3D tic-tac-toe, hexagonal boards and Connect Four fall out with only a new group list, at the cost of a setup pass and per-cell index. If turn order were data instead (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 and undo can no longer restore the turn with a flip. If marks could be removed or moved, the counters would still survive, since unplace is already exact, but the history would stop being a stack of placements and become a stack of (from, to) transitions. If the board were sparse and unbounded (gomoku on paper with no edges), the dictionary is already right but 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.

Data versus code

A rule expressed as data can be edited without recompiling; a rule expressed as code can be read as a sentence and checked by a type checker. This design puts board size, occupancy, move history, and the scan directions on the data side, and the win condition, line geometry, two-player alternation, and move legality on the code side. 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 moment two rules start varying together (different win lengths and different capture rules, say), a table-driven engine becomes the right call instead.

The win check: O(1), not O(n^2)

The win check is the one real algorithmic choice in the problem.

Big-O notation describes how the work grows with the input, ignoring constant factors. O(1) is bounded by a constant regardless of board size; O(k) grows with the win length; O(n^2) grows with the number of cells.

One counter per line, per mark

Besides the grid, Board stores a tally for every line (one per row, one per column, one for each diagonal) broken down by mark. When a mark lands, 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 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 example

Follow a row-win game on a 3x3 board (n = 3, so a counter reaching 3 wins): X plays (0,0), O plays (1,0), X plays (0,1), O plays (1,1), X plays (0,2).

Move 4 is the maximum case: the centre cell sits on both diagonals, so it touches four counters, and no move ever touches more. Move 5 wins because row0[X] reached 3 without scanning anything. One integer crossed a threshold. Every counter that stayed at 0 was never read, and that is the whole saving.

Why it beats a rescan

The obvious alternative rescans the board after every move. On a 3x3 board that reads all rows, columns and both diagonals (about 24 cell reads) against at most 4 counter updates for the incremental version: roughly 6x less work. The ratio grows as (2n^2 + 2n) / 4, with the square of the board’s side, so on a 19x19 board it is about 190x.

The k-in-a-row case

When k is smaller than n the rescan gets much worse, because every window of k consecutive cells anywhere is a candidate line, not just the full rows and columns. On a 15x15 gomoku board with k = 5 there are 572 such windows, about 2,860 cell reads per move. The incremental scan walks outward from the placed cell in 4 directions, 2 opposite rays each, at most k - 1 steps per ray: about 32 reads, roughly 89x fewer. The scan is O(k) and does not depend on n at all, so on a 19x19 board it stays at 32 reads while the rescan grows past 5,000.

Counters are reversible, and what they cost

Running counters have a second payoff: taking a move back is a decrement, not a recomputation, so undo is also O(1) with no board snapshot. The price is an invariant (a property that must hold before and after every operation) spanning four data structures. Any code path that writes the cell dictionary without going through place or unplace silently corrupts the win check. That is why the cell dictionary is private and mutated only by those two methods, and it is why a rescan is the right choice for a one-off script and the wrong choice inside a search loop that places and unplaces millions of times.

Working Python

The whole design as running code, followed by assertions that prove each claim. Read Board for the counters; the method to study is _bump, which is the worked table above 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 idioms worth naming

• from __future__ import annotations stores type annotations as text instead of evaluating them, which lets a method mention a type that does not exist yet. It must be the first statement in the file.
• The bracketed typing names are type hints, documentation the interpreter does not enforce. Dict[Tuple[int, int], Mark] is “a dictionary from integer pairs to marks”; Optional[Mark] is “a mark or None”.
• The leading underscore in _cells and _bump is a convention meaning “internal, do not touch from outside”. It is the only thing protecting the invariant described above.
• self is Mark.X compares identity, 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 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 formats as a whole instead of being spread across two placeholders.
• raise ValueError(...) aborts the call with an error the caller can catch, so place refuses an illegal move without returning a special value someone forgets to check.

undo flips the turn only when self.winner is None, because play advances the turn only on a non-winning move. Undoing a neutral move must flip back; undoing the winning move must not, since the turn was never advanced past the winner. Both branches then clear winner.

The tests

An assert raises immediately if its condition is false, so a block of assertions that runs to completion is a passing test.

# --- 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

g.play(*mv) uses the star operator to unpack a pair into two positional arguments. Each try/except ValueError/pass block asserts that a call fails: the raise AssertionError line runs only if an illegal move was wrongly accepted.

Two of these carry the real weight. The rejected-move test proves that a refused move leaves no trace at all (no history entry, no counter increment, no turn flip) because place validates before it writes anything and play appends only after place returns; len(e.history) == 1 is what proves it. The n = 4 case proves the counter design generalizes: Board was written against self.n, never the literal 3, so “make it n x n” is a constructor argument. X takes (0,0), (1,1), (2,2), (3,3), so diag[X] climbs to 4 and hits n, with not one line of Board changed.

Extensions

Three follow-ups. For each: what changes, what does not, and what it costs.

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. 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, because place promised its caller one thing, “true if this move won”, and never promised how it knew.

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

DIRS holds one (row step, column step) pair per direction. Multiplying by sign (which takes +1 then -1) walks the two opposite rays of the same line without writing eight pairs. run starts at 1 to count the placed cell, and the guard run < k stops the walk the instant enough are counted, making it O(k) and not O(n). (The literals here are plain strings; the is comparison works because Python reuses short string literals, but production code should use ==.)

The counterexample the counters get wrong: five X’s in one row with a gap in the middle.

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"

Those five X’s share a row, so a row counter reads 5 and declares a win, but the gap at column 5 means the longest adjacent run is 3. This is the bug the naive generalization ships, and it is why the fast counter trick has a precondition (k == n) that must be checked before it is trusted.

What it costs. The win check is no longer constant time, and Board now carries a k that must be validated against n. Keeping the counters for the k == n case means keeping both paths correct, a real maintenance cost.

An AI opponent

The standard search for a small two-player game with no hidden information is minimax: enumerate every legal move, then every reply, 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 is one Player implementation. What does not change is Game and Board, because place and unplace are already an exact inverse pair: precisely what a search needs, since it tries a move, explores everything beneath it, and takes it back, millions of times.

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

nodes is a one-element list used as a counter that survives across recursive calls, since Python passes lists by reference. The minus sign in -minimax(...) is what lets one function serve both players: a position worth +1 to your opponent is worth -1 to you, so recursing with roles swapped and negating avoids separate maximizing and minimizing branches. best starts at -2 so the first move examined always improves on it.

Wrapping it as the MinimaxPlayer box is four lines, because the interface only ever promised “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 to pause 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 why no snapshotting is needed anywhere in the design.

The cost on 3x3. There are 255,168 distinct complete tic-tac-toe games (smaller than 9! = 362,880 because most games end before the board fills). A full minimax makes 340,858 recursive calls; the one-line if best == 1: break cutoff cuts that to 66,275, one line removing about 80% of the work. That is milliseconds, so 3x3 is solved exactly and a minimax player is unbeatable; the search scores the empty board at 0, which is the formal statement that best play from both sides is a draw.

Why it stops at 4x4. A 4x4 board has 16 cells, and 16! ≈ 2.1 × 10^13. At an optimistic 10 million positions per second that is roughly 24 days per move. Beyond 3x3 the answer is three things layered together, and the Player interface absorbs all of them without changing:

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

Undo, and optional redo

Undo is already built, as a side effect of a decision made for speed. Two designs were available:

Command is the pattern where a request becomes an object carrying everything needed to perform and reverse it. unplace is the exact inverse of place because the counters are additive: undoing is a -1 where the move was a +1, and nothing else in the board’s state changed. The second-order payoff worth noting: undo came free because the win check had been made incremental for a completely different reason.

Formalizing a move as a real Command object is only needed if you want 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())

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

@dataclass writes the constructor, equality and printable form from the annotated fields; frozen=True makes instances immutable, which is what you want for a command kept in a history. The two lists are stacks (append pushes, pop removes the most recent), and self.undone.clear() inside execute implements the truncation rule: once you undo a few moves and then play a different one, the undone moves are no longer reachable and can never be redone.

What it costs. Every move allocates an object, and two stacks must stay consistent with Game.history, which is duplicated state and a source of bugs. For tic-tac-toe the Command layer is over-engineering unless redo is actually required. Its value here is showing you know the full pattern and when not to reach for it.

Conclusion

• Model tic-tac-toe with three objects, four with a computer opponent: Mark, Board, Game, and Player. The discipline is declining Cell, Piece, MoveValidator, GameStateFactory, Observer, State and Singleton, each for a stated reason.
• The one real algorithmic idea is the incremental win check: running counters per row, column and diagonal make each move’s check O(1) (about 4 updates versus 24 rescan reads on 3x3, growing as (2n^2 + 2n)/4).
• Those counters are only correct when k == n. For k smaller than n they cannot see gaps; switch to an O(k) directional scan outward from the placed cell.
• Because unplace is an exact inverse of place, undo is O(1) and minimax needs no board snapshots. On 3x3 exhaustive search is 66,275 nodes with the win cutoff and the game is a forced draw; on 4x4 16! is intractable, so you move to alpha-beta with a depth limit and a heuristic.
• The general lesson: decide what is data (board size, occupancy, history, scan directions) and what is code (win condition, line geometry, turn order, legality), and match the modelling effort to the size of the problem.

Further reading

• Tic-tac-toe — game tree size and outcomes: the 255,168 distinct-games figure and the drawn-with-perfect-play result.
• Gomoku: the standard k-in-a-row game the generalization models.
• Minimax and Alpha–beta pruning: the search algorithm and the refinement needed past 3x3.
• Russell & Norvig, Artificial Intelligence: A Modern Approach, the adversarial-search chapter: minimax, alpha-beta, depth limits and heuristic evaluation in one place.

Next: Blackjack, where the rules genuinely are complicated enough to need the machinery this lesson refused.