PHASE 4Intermediate ~9 min· topic 7 of 18Level 2

Problem 4.7 — Tic-Tac-Toe

In one line

A tight game-engine problem where strategy, board state, players and win-checking must stay decoupled and extensible.

0/18 · 0%

Think of it like this

A simple grid game most of us played as kids. The interesting design problem isn't the game itself, it's building it so a 4x4 board or a computer opponent can be added without rewriting everything.

Key ideas

01
Entities: Board (3x3 grid), Player (mark), Move (row, col), Game (session), WinChecker.
02
Separate concerns: board state ∈ Board; legal-move + win detection ∈ rules; turn order ∈ Game.
03
Win check: after each move only check the affected row/col/diagonal — O(1), not O(n²) rescan.
04
Draw detection: board full and no winner.
05
Strategies: computer player difficulty (easy/medium/unbeatable minimax) behind a PlayerStrategy interface.
06
Extensibility: bigger boards (standardize to N×N), 4-in-a-row variant, custom marks.
07
Tests are natural: winCheck cases, blocked cells, invalid play, draws, and the minimax path.

Java / Spring map

→
Turn-based service (Postman-friendly) or pure domain objects; minimax as the ComputerStrategy impl.

Code & diagrams

TicTacToe.javajava

Pure domain model — board, rules, win check, strategy-backed players.

public enum Mark { X, O; Mark other() { return this == X ? O : X; } }

public class Board {
  private final Mark[][] cells;
  public Board(int n) { cells = new Mark[n][n]; }

  public boolean play(Mark m, int r, int c) {
    if (r < 0 || r >= cells.length || c < 0 || c >= cells.length || cells[r][c] != null)
      return false;                               // invalid or occupied
    cells[r][c] = m;
    return true;
  }

  public boolean win(Mark m, int lastR, int lastC) {  // O(1) check around last move
    int n = cells.length;
    boolean row=true, col=true, diag=true, anti=true;
    for (int i = 0; i < n; i++) {
      row  &= cells[lastR][i] == m;
      col  &= cells[i][lastC] == m;
      diag &= cells[i][i] == m;
      anti &= cells[i][n - 1 - i] == m;
    }
    return row || col || diag || anti;
  }
  public boolean full() { for (Mark[] r : cells) for (Mark v : r) if (v == null) return false; return true; }
  public Mark[][] cells() { return cells; }
}

public interface PlayerStrategy {             // strategy: human or AI
  int[] nextMove(Board b, Mark me);
}
public class HumanStrategy implements PlayerStrategy {
  public int[] nextMove(Board b, Mark me) { return new int[]{-1, -1}; } // input handled by UI
}
public class RandomStrategy implements PlayerStrategy {
  public int[] nextMove(Board b, Mark me) {
    Random rnd = new Random();
    while (true) {
      int r = rnd.nextInt(b.cells().length), c = rnd.nextInt(b.cells().length);
      if (b.cells()[r][c] == null) return new int[]{r, c};
    }
  }
}

public class Game {
  private final Board board = new Board(3);
  private final PlayerStrategy x, o;
  private Mark turn = Mark.X;
  public Game(PlayerStrategy x, PlayerStrategy o) { this.x = x; this.o = o; }

  // returns X, O, DRAW or null (still playing)
  public Mark playTurn() {
    PlayerStrategy cur = turn == Mark.X ? x : o;
    int[] mv = cur.nextMove(board, turn);
    if (mv[0] < 0) return null;                    // human: UI will call play(mark,r,c)
    if (!board.play(turn, mv[0], mv[1])) throw new IllegalStateException("illegal move");
    Mark won = board.win(turn, mv[0], mv[1]) ? turn : null;
    if (won != null) return won;
    if (board.full()) return Mark.X;               // DRAW sentinel via caller
    turn = turn.other();
    return null;
  }
}

Explain without notes

Why is win-checking restricted to the last move a design win? What would O(n²) rescan cost at N×N?

Practice

Implement MiniMaxComputerStrategy and verify it never loses.

Trade-offs

↔
Minimax is O(n!) in the worst case for large boards — alpha-beta pruning or depth limit for bigger variants.

Completion checklist

I can write board+rules+strategy for Tic-Tac-Toe and explain where variants slot in.

Back to phase

Command Palette