LLD6 min read
Tic-Tac-Toe
Tiny game, but a great vehicle for clean state machines and pluggable AI strategies.
lldoopgame
Intro
Tic-Tac-Toe is small enough to fit in a screen of code yet rich enough to ask the right design questions: how do you represent the board, how do you check the win condition without scanning the whole board on every move, and how do you make AI swappable?
Functional
- Two-player game on a 3×3 board (extensible to n×n).
- Detect win, draw, and illegal moves.
- Support human vs human, human vs AI, AI vs AI.
Non-functional
- Constant-time win check after each move (no full board scan).
- AI strategy must be swappable without touching the engine.
Components
Board
n×n grid with row, column, diagonal counters.
Player
Has a symbol and a Strategy that picks moves.
Strategy
Interface: HumanInput, Random, Minimax.
GameEngine
Drives the loop; queries strategy; updates board; emits events.
Code
O(1) win-check after each movejava
class Board {
final int n;
final int[] rows, cols;
int diag, anti;
Board(int n) { this.n = n; rows = new int[n]; cols = new int[n]; }
/** symbol = +1 or -1. Returns symbol if winner, else 0. */
int play(int r, int c, int symbol) {
rows[r] += symbol; cols[c] += symbol;
if (r == c) diag += symbol;
if (r + c == n - 1) anti += symbol;
if (Math.abs(rows[r]) == n) return symbol;
if (Math.abs(cols[c]) == n) return symbol;
if (Math.abs(diag) == n || Math.abs(anti) == n) return symbol;
return 0;
}
}Pitfalls
- Storing the board as a 2D char array and rescanning on each move — works but throws away an interview point.
- Letting the engine know about minimax internals.