Design a Tic Tac Toe Game
0%
Editorial Solution
Requirements
Define Core Objects
Analyze Relationships
Establish Hierarchy
Mark Enum
GameStatus Enum
Player Class
Extensibility: MoveStrategy Interface
Design Patterns
Strategy Pattern: Pluggable Move Selection
Template Method: Win Detection
Factory Method: Board Creation
Define Class Members / Write Code
Cell
Board
Game with Thread Safety
Run and Test
Adhere to SOLID Guidelines
Consider Scalability and Flexibility
Thread Safety with ReentrantLock
Scaling to a Game Server
Flexible Board Sizes
Create/Explain Your Diagrams
Future Improvements
Table of Contents
Tic-tac-toe looks like a trivial game: two players, nine cells, three-in-a-row wins. But modeling it as an object-oriented system surfaces real design challenges. You need to enforce turn alternation, detect wins across rows, columns, and diagonals after every move, handle invalid moves gracefully, and ensure that two network players cannot corrupt the board with simultaneous submissions. The design challenge is modeling these rules so that illegal states are structurally impossible.
Interview Dialogue
Functional Requirements
- Place Mark on Board - Players place their mark (X or O) on an empty cell of a 3x3 grid. The system rejects placements on occupied cells or out-of-bounds positions with a clear error message.
- Alternate Turns - X always moves first. The system strictly alternates turns between the two players. A player cannot move out of turn.
- Win, Draw, and Invalid Move Detection - After each move, the system checks all rows, columns, and both diagonals for three matching marks. If the board is full with no winner, the game is declared a draw. Moves on occupied cells or out-of-turn attempts are rejected.
- Reset and Replay - Players can start a new game at any time. The board clears, the turn resets to X, and the game status returns to active.
Non-Functional Requirements
- Thread Safety - In a networked game, two players connect from separate threads. Move placement must be synchronized so only one move executes at a time and the board state remains consistent.
- Extensibility - The design should accommodate NxN boards or more than two players without major rewrites. Board size and win condition length are configurable constructor parameters.
Walk through a game session and see where the objects emerge. Rather than listing classes upfront, trace a scenario and let the objects reveal themselves.
Scenario: Alice and Bob open the game. Alice places X at (0,0). Bob places O at (1,1). Alice places X at (0,1). Now ask: what data did the system need at each step, and who held it?
When Alice placed her mark, the system needed to know whose turn it was (a turn tracker), whether the cell was empty (a cell with state), and which mark to place (a mark type). When the move completed, the system checked whether three marks lined up (a grid analyzer). These needs point directly to objects: a Game that tracks turns, a Cell that knows its own state, a Mark enum for type safety, and a Board that scans for wins.
Start by scanning the requirements for nouns. "Two players" gives us Player. "3x3 grid" and "empty cell" become Board and Cell. "Mark (X or O)" maps to a Mark enum. "Game status" like win or draw points to Game and GameStatus. Not every noun becomes a class. "turn" is a concept tracked by a field on Game, not its own entity, but nouns give you the starting lineup.
Two players sit down. Each has a name and a mark (X or O). The mark is assigned at game creation and never changes. That gives us a Player class with immutable fields and a Mark enum (X, O, EMPTY).
Why a Mark enum instead of a char or String? With a char, nothing prevents someone from placing 'Z' on the board. With a String, the board could contain "hello". The Mark enum constrains valid values to exactly X, O, and EMPTY at compile time. Invalid marks are impossible.
The board is a 3x3 grid. Each position holds a mark. We need a Cell class (row, column, current mark) and a Board class that manages the grid. The Board handles placement, emptiness checks, win detection, and draw detection.
Why separate Cell from Board? A Cell is responsible for its own state: is it empty, what mark does it hold, can it be cleared? The Board is responsible for the grid as a whole: scanning rows, columns, and diagonals. Without Cell, the Board would manage both grid structure and individual-position logic in one class.
Why a Mark enum instead of a char or boolean? A char would allow placing 'Z' on the board, and a boolean only supports two states (no way to represent empty). The Mark enum constrains values to exactly X, O, and EMPTY at compile time, making invalid marks impossible without any runtime validation.
The game itself tracks whose turn it is, whether the game is still active, and who won. That gives us a Game class that owns the Board and two Players. Game exposes makeMove() as the single entry point for all game actions.
A GameStatus enum (ACTIVE, X_WON, O_WON, DRAW) represents the game outcome. The Game updates this after each move.
Composition: Game owns Board
The Board exists only as part of a Game. If the Game is reset or destroyed, the Board goes with it. You would never take the Board out of one Game and plug it into another. This is composition: the child's lifecycle is bound to the parent.
Composition: Board owns Cells
Each Cell is a physical position on the Board. Cell(0,0) of Game #42 is meaningless outside that Board. When the Board is cleared via reset(), all Cells are cleared together. The Cell lifecycle is bound to the Board.
Composition: Game owns Players
The two Players are created for this specific Game. Their marks are assigned at Game construction and tied to this game instance. Destroying the Game makes these Player references meaningless.
Enum Association: Cell references Mark
A Cell holds a Mark enum value. Mark is a type-level construct, not an instance with its own lifecycle. The relationship is a simple field reference, not ownership.
Delegation: Game delegates to Board
Game does not scan rows and columns itself. It delegates win detection to Board.checkWin() and draw detection to Board.isFull(). Game only interprets the boolean result to update GameStatus. This keeps Game focused on orchestration and Board focused on grid logic.
Why does Game own Players via composition instead of accepting them as external references? If Players were shared across games, a player's mark could be changed between games. Composition ensures each game's players are frozen at construction, preventing a mid-game mark swap that would corrupt the board state.
Mark Enum
Three values, no more. The type system prevents invalid marks. EMPTY represents an unoccupied cell, avoiding null checks throughout the codebase.
GameStatus Enum
Four possible game outcomes. ACTIVE means the game is still in progress. The other three are terminal states. Once the status leaves ACTIVE, no more moves are accepted.
Why enums for both Mark and GameStatus? Both represent a fixed, closed set of values. There will never be a fifth game status or a third mark type in standard tic-tac-toe. Enums make the set explicit and exhaustive at compile time. Switch statements on enums generate compiler warnings if a case is missing.
Player Class
Player is immutable after construction. It holds a name and a Mark. The constructor rejects Mark.EMPTY because a player must have a real mark. Immutability prevents accidental changes during gameplay (for example, swapping a player's mark mid-game).
Why a MoveStrategy interface instead of embedding AI logic directly in the Player class? Embedding the algorithm couples identity (who the player is) to decision-making (how they choose moves). Adding a Monte Carlo AI would require modifying Player. The Strategy pattern keeps Player unchanged and lets you compose any player with any algorithm.
Extensibility: MoveStrategy Interface
For an AI opponent, a MoveStrategy interface defines chooseMove(Board board) returning a row-column pair. HumanStrategy reads from user input. MinimaxStrategy computes the optimal move. RandomStrategy picks an empty cell at random. Game does not care which strategy a Player uses, enabling human-vs-AI and AI-vs-AI games without modifying Game.
Strategy Pattern: Pluggable Move Selection
The Strategy pattern decouples how a move is chosen from how the game processes it. Without it, Game would need if-else branches for human input, random AI, and minimax AI inside every move call. Adding a new AI type would mean editing Game.
With Strategy, each Player holds a MoveStrategy reference. A game runner asks the current player's strategy for a move, then passes the coordinates to game.makeMove(). Game never sees the strategy. This means you can add Monte Carlo tree search, neural network evaluation, or remote network input by implementing one interface.
Template Method: Win Detection
Board.checkWin() follows a template: check all rows, then all columns, then both diagonals. Each check follows the same pattern (iterate positions, compare marks). For an NxN board with connect-K rules, the template stays the same but the loop bounds change. Subclassing Board for different win conditions lets you override the check methods without changing the iteration structure.
Factory Method: Board Creation
A BoardFactory can create boards of different sizes and configurations. createStandard() returns a 3x3 board. createLarge() returns a 10x10 board with connect-5 rules. The factory centralizes creation logic so Game does not need to know how boards are configured.
The Strategy pattern is the key extensibility mechanism in tic-tac-toe. It transforms the game from a two-human-player toy into a framework that supports any combination of human, AI, and network players without touching the core Game class.
Implement Board win detection before Game.makeMove(). Once rows, columns, diagonals, and draw detection are trustworthy, Game becomes a thin rule coordinator instead of a class that mixes turn logic with spatial analysis.
Cell
We start at the leaf of the composition hierarchy. Cell is the smallest unit of board state.
Cell throws an exception if you try to place a mark on an occupied cell. This makes double-placement impossible at the Cell level, not just at the Game level. Defense in depth. Notice that Cell validates independently of the Board - even if a bug in Board skipped the emptiness check, Cell would catch it.
Board
Board sits one level up, owning a grid of Cells. Its primary job is spatial analysis: scanning rows, columns, and diagonals for wins.
The allMatch helper method uses direction vectors (dRow, dCol) to check rows, columns, and diagonals with a single method. This eliminates code duplication and makes the win-check logic work for any board size. The direction vector approach means adding diagonal-only win rules or connect-K rules changes a parameter, not the algorithm.
Game with Thread Safety
Game sits at the top of the hierarchy, orchestrating turns, invoking Board methods, and synchronizing concurrent access. Everything below it, namely Board, Cell, and Mark, is passive. Game is the single active coordinator.
Do not lock only the cell write. The dangerous part is the whole move transaction: verify the game is active, verify turn order, verify emptiness, place the mark, detect win or draw, then switch turns. If only the write is protected, two threads can still both believe it is their turn.
The entire makeMove() method is wrapped in a lock. The empty-cell check, mark placement, win detection, and turn switch all execute atomically. No other thread can observe or modify game state during this sequence.
Run and Test
Browse the complete solution code and run it. Try modifying the board size, adding a new win condition, or breaking the thread safety to see what happens.
Single Responsibility Principle
- Game orchestrates turns, status transitions, and thread safety. It does not scan the grid.
- Board manages the grid, placement, and win/draw detection. It does not know about players or turns.
- Cell manages its own mark state. It does not know about the grid or the game.
- Player holds identity and mark. It does not know about the board or game rules.
Open/Closed Principle
- Adding a 5x5 board requires passing 5 to the Board constructor. Zero code changes.
- Adding a MinimaxStrategy requires one new class implementing MoveStrategy. Zero changes to Game, Board, or Player.
- Adding a spectator notification requires one new Observer implementation. Zero changes to Game.
Liskov Substitution Principle
- Any MoveStrategy can replace any other. Game calls makeMove() with coordinates and does not know which strategy produced them.
- A Board subclass for connect-K can replace the standard Board in Game because it implements the same checkWin() and placeMark() interface.
Interface Segregation Principle
- MoveStrategy has exactly one method:
chooseMove(Board). No implementation is forced to implement unrelated methods. - If GameObserver were added, it would have focused methods like
onMove()andonGameEnd(), not a bloated interface with unrelated callbacks.
Dependency Inversion Principle
- Game depends on abstract Board behavior (checkWin, placeMark), not on specific board implementations.
- The game runner depends on MoveStrategy, not on HumanStrategy or MinimaxStrategy directly.
In an interview, demonstrate OCP with a concrete example: adding MinimaxStrategy requires one new file and zero changes to Game.java, Board.java, Cell.java, or Player.java. Count the unchanged files out loud.
Thread Safety with ReentrantLock
The Game class uses a ReentrantLock to serialize all move operations. The lock is acquired before the empty-cell check and held through placement, win detection, and turn switch. This guarantees that exactly one thread executes the entire move sequence at a time.
The race condition, made concrete: Board has one empty cell at (2,2). It is X's turn. Both threads submit simultaneously.
- Thread-A reads currentPlayerIndex = 0 (X's turn). Passes the turn check.
- Thread-B reads currentPlayerIndex = 0 (still 0, Thread-A has not updated it yet). Also passes.
- Thread-A calls board.isCellEmpty(2,2) - returns true. Places X at (2,2).
- Thread-B calls board.isCellEmpty(2,2) - returns false (Thread-A already placed). Returns false.
That scenario looks safe, but consider a subtler one where both target different cells:
- Thread-A (X) reads currentPlayerIndex = 0. Checks cell (0,0) is empty.
- Thread-B (O) reads currentPlayerIndex = 0 (not yet updated). Checks cell (1,1) is empty.
- Thread-A places X at (0,0). Sets currentPlayerIndex = 1.
- Thread-B places O at (1,1). Sets currentPlayerIndex = 1.
- Result: two moves happened on the same turn. O moved when it was X's turn. The turn counter advanced only once. Game state is corrupted.
The ReentrantLock prevents this by ensuring only one thread executes the entire check-place-detect-switch sequence at a time.
Why ReentrantLock instead of synchronized? ReentrantLock provides tryLock() with a timeout, which is useful in a network game where you want to reject a move attempt if the lock is held too long rather than blocking indefinitely. It also provides fairness guarantees when configured, preventing thread starvation.
Scaling to a Game Server
For a server hosting thousands of concurrent games, each Game instance has its own lock. Games are independent, so only the two players in a game contend for its lock. This means 5,000 simultaneous games produce zero cross-game contention.
The server architecture uses a Game registry (a ConcurrentHashMap of game ID to Game) so that incoming move requests are routed to the correct Game instance. Each game processes moves independently.
Flexible Board Sizes
Because Board takes a size parameter and the win-check logic uses direction vectors parameterized by size, supporting 4x4, 5x5, or any NxN board requires no code changes. A connect-K variant adds a winLength parameter to Board and adjusts the allMatch loop bound.
Junior: identify the race condition between cell-empty check and mark placement.
Mid-level: explain why a per-game lock eliminates cross-game contention on a multi-game server.
Senior: discuss how to add spectator broadcasting and move replay without modifying the core Game class.
Why ConcurrentHashMap instead of synchronizing a regular HashMap? A synchronized HashMap locks the entire map for every operation, serializing all threads. ConcurrentHashMap uses striped locks (one per segment), so threads operating on different segments proceed in parallel.
Below is the class diagram for the tic-tac-toe system.
Key points to highlight in an interview:
- Composition arrows (Game owns Board, Board owns Cell) show lifecycle binding. Destroying Game cascades through Board to Cells.
- Game owns exactly two Player instances. Players are created for this game and do not outlive it.
- Cell references Mark via a simple field, not ownership. Mark is an enum, not an object with its own lifecycle.
- The diagram is deliberately flat. There is no deep inheritance hierarchy. Tic-tac-toe is a simple domain, and the design reflects that simplicity rather than over-engineering with patterns it does not need.
AI Opponent with Minimax
Implement a computer player using the minimax algorithm with alpha-beta pruning. For a 3x3 board, minimax is fast enough to search the entire game tree (at most 9! positions). For larger boards, alpha-beta pruning cuts the search space dramatically. A MoveStrategy interface allows swapping between human input and AI without modifying Game.
NxN Board and Connect-K
Generalize to NxN boards where K consecutive marks in a row win. Board and win-check logic are already parameterized by size. Adding a winLength parameter to allMatch() completes the generalization. This enables 5x5 connect-4, 10x10 connect-5, or any combination.
Move History and Replay
Record each move in a history stack with the row, column, mark, and timestamp. Provide undo() to reverse the last move. Provide replay() to replay the entire game move by move with configurable delay. History enables post-game analysis and AI training data collection.
Online Multiplayer with WebSocket
Replace the local game loop with a WebSocket server. Each player connects from a browser. Moves are sent as JSON messages and broadcast to both players. The Game class remains unchanged because it only receives coordinates and returns results. The transport layer is a separate concern.
Tournament System
A Tournament class manages brackets of multiple Games. Players are seeded, matched, and advanced through elimination rounds. The Tournament uses Game as a black box, only reading the GameStatus to determine winners.
Try this problem yourself
Reading a solution is not the same as producing one under interview pressure. Design it on the whiteboard and get scored feedback.
0%
Editorial Solution
Requirements
Define Core Objects
Analyze Relationships
Establish Hierarchy
Mark Enum
GameStatus Enum
Player Class
Extensibility: MoveStrategy Interface
Design Patterns
Strategy Pattern: Pluggable Move Selection
Template Method: Win Detection
Factory Method: Board Creation
Define Class Members / Write Code
Cell
Board
Game with Thread Safety
Run and Test
Adhere to SOLID Guidelines
Consider Scalability and Flexibility
Thread Safety with ReentrantLock
Scaling to a Game Server
Flexible Board Sizes
Create/Explain Your Diagrams
Future Improvements