Tic-tac-toe is a restraint exercise: model it with the few objects it needs, decline the patterns it doesn’t, and make the win check touch a constant number of values per move.
The objects (3, or 4 with AI)
| Object | Role |
|---|
Mark (enum: X, O) | No state; only other() flips to the opposing mark. Not a Piece class. |
Board | Owns the cells and the per-line win counters. Every grid change must go through it. |
Game | Turn order, end detection, move history. |
Player (interface) | Only with a computer opponent: choose(board, mark) -> (row, col). |
play(r, c) returns the winner (or None) as the output of the move itself. No separate check_for_win().- Board size
n is a constructor arg; Board reads self.n, never the literal 3, so 4x4 works unchanged.
Patterns declined (name + reason)
- No
Cell class: a cell is Optional[Mark]; wrapping it adds indirection.
- No
MoveValidator (chain of responsibility): validation is four < comparisons known at authoring time.
- No Observer: one board, one renderer; the caller already knows the board changed.
- No
GameStateFactory (factory): three outcomes = one nullable winner + a full-board test.
- No State hierarchy: a
winner field plus board.full() is the whole state machine.
- No Singleton:
Game holds no global state, so a server runs thousands keyed by id.
The O(1) win check
Board keeps a counter per row, per column, and one per diagonal, split by mark.- A placed mark can only change lines through its cell: at most 4 counters (centre sits on both diagonals).
- Update those counters, compare the largest to
n. A win means one counter hit n with nothing else read.
- Diagonal membership:
r == c (main), r + c == n - 1 (anti).
unplace is the exact inverse of place (a -1 where the move was +1), so undo and minimax need no board snapshot, both O(1).
place (r,c) --> bump ≤4 counters --> largest == n ? --> yes: win / no: continue
Cost vs. rescan
| Check | 3x3 | Scaling |
|---|
| Rescan every move | ~24 reads | 2n^2 + 2n cells |
| Incremental counters | ≤4 updates | constant, ~6x less at 3x3, ~190x at 19x19 |
The k-in-a-row gotcha
- Counters are correct only when
k == n. For k < n a row counter of k does not mean the marks are adjacent (it misses a gapped X X . X X).
- Fix: an O(k) directional scan outward from the placed cell, 4 directions x 2 opposite rays, stop at
k. Independent of n.
Game, undo, history, and the Player interface all stay: place only ever promised “true if this move won”, never how.
AI and undo
- Minimax: enumerate moves to game end, score +1/0/-1, negate on recursion so one function serves both players. 3x3 is a forced draw; empty-board search is 66,275 nodes with the
if best == 1: break cutoff (~80% off the full 340,858).
- 4x4 is intractable (
16! ≈ 2.1e13): switch to alpha-beta + depth limit + heuristic. The Player interface absorbs all three.
- Undo came free from the incremental counters (Command pattern: store coords, invert). A real
PlaceCommand object is only worth it for redo/replay.
Data vs. code
- Data (edit without recompiling): board size, occupancy, move history, scan directions.
- Code (read as a sentence, type-checked): win condition, line geometry, two-player alternation, move legality.
- The bet: board size varies, the rules don’t. Correct here, which is why the design stays at four boxes.