Design Chess
Pieces, moves, check/checkmate, and rules — a polymorphism-heavy engine with per-piece move strategies.
Problem Statement
Design the object model for a Chess engine that supports two players moving pieces on an 8x8 board. The system must represent the board, all standard piece types, legal move validation, turn ownership, status transitions, and the history seam needed for undo or replay. The interview focus is not a UI or an online matchmaking service. It is the domain model: where rules live, how illegal moves are rejected before mutation, and how the game can grow from a clean core into castling, promotion, draw rules, timers, and persistence.
Business context
Chess is an advanced LLD interview problem because the obvious model quickly becomes a giant conditional controller if responsibilities are misplaced. Strong candidates separate Board storage from Piece movement strategy, make Game the state machine, treat Move as the command request, and validate self-check on a candidate board before committing the real board. Amazon, Google, and Microsoft commonly use this style of game-design problem to test polymorphism, invariants, state transitions, and extensibility under a dense rule set.
Functional Requirements
Represent an 8x8 board with addressable, bounds-checked squares.
Initialize a normal chess starting position for black and white pieces.
Model players by name and color, with white moving first and turns alternating after valid moves.
Support King, Queen, Rook, Bishop, Knight, and Pawn with per-type movement rules.
Validate each move for game status, source occupancy, active-player ownership, destination bounds, piece geometry, blocked paths, legal capture, and self-check.
Apply a move atomically only after every validation passes.
Detect whether the next player is in check, checkmate, or stalemate after a valid move.
Expose current player and game status so a UI, API, or test harness can observe the game without mutating it.
Represent a move as a command-style object so a move log, replay, or undo stack can be layered on the same boundary.
Non-Functional Requirements
Rule correctness
Illegal movement, own-piece capture, moving into check, and moving after the game is terminal must be rejected before the real board changes.
Extensibility
Special rules such as castling, en passant, promotion, half-move draw counters, and variants should be additive validators or move effects, not edits to every piece.
Encapsulation
Board owns placement and path queries; Piece owns movement geometry; Game owns turns, status transitions, and self-check validation.
Deterministic behavior
Given the same starting position and move list, the engine should reach the same board and status. This makes replay, debugging, and tests straightforward.
Interactive latency
A complete status update scans at most a fixed 8x8 board. Even a brute-force legal-move search is effectively constant time for standard chess.
Requirement Clarification
QWhich coordinate system should the design use?
Use zero-based Square(row, col) coordinates internally. Row 0 is black's back rank, row 7 is white's back rank, and presentation notation such as e4 can be translated at the boundary.
QDo we need castling, en passant, promotion, clocks, or draw-by-repetition in the first pass?
No. The core implementation ignores those tournament rules but keeps clear extension points: extra validators, richer move effects, and additional GameStatus values.
QShould **Board** know whose turn it is?
No. Board is a storage and query object. Turn ownership belongs to Game, which asks Board for pieces and then delegates movement geometry to those pieces.
QHow exact should checkmate and stalemate detection be?
The reference implementation performs a high-level legal-move search: locate the king, test attacks by opposing pieces, then see whether any legal candidate move removes check or avoids stalemate.
QHow should move history and undo be handled?
The base code models Move as the immutable command request. A production version would store executed moves with captured piece and prior status metadata so undo can reverse moveUnchecked safely.
UML Class Diagram
Sequence Diagram
Entity Identification
Game
Aggregate root and state machine. It validates moves, rejects terminal-game actions, prevents self-check, updates checkmate or stalemate, and alternates turns.
Board
Owns the 8x8 placement matrix and board-level queries such as bounds, path clearance, occupied squares, copying, and unchecked piece movement.
Square
Immutable coordinate value object used by Board, Move, and search loops. Equality and hash code make coordinates safe as values.
Piece
Abstract base for color and shared target checks. Each subclass implements canMove as its movement strategy.
King
Allows one-square movement in any direction and cannot stay on the same square. The broader rule that kings may not move into check is enforced by Game.
Queen
Combines rook-like straight movement and bishop-like diagonal movement, requiring a clear path and a legal target.
Rook
Moves horizontally or vertically with path clearance. This is the natural home for castling metadata in an extended design.
Bishop
Moves diagonally with path clearance and legal capture checks.
Knight
Moves in an L shape and ignores path clearance because it jumps over intervening pieces.
Pawn
Encodes direction by color, starting-row double steps, forward movement into empty squares, and diagonal captures.
Move
Immutable command request from a source square to a destination square. It is intentionally small so history, replay, and undo metadata can wrap it.
Player
Human or bot identity associated with a color. It does not own pieces; board state does.
GameStatus
Closed state vocabulary for active play, white win, black win, and stalemate.
Color
Side enum with opposite to advance turns and choose the player being evaluated for check.
Design Patterns Used
Movement varies by piece, but Game calls the same Piece.canMove interface. King, Queen, Rook, Bishop, Knight, and Pawn are interchangeable movement strategies behind the abstract base.
The reference code centralizes initial piece creation inside Board.setupStartingPosition and placeBackRank. In production, that seam becomes a PieceFactory so variants, loaded positions, and promoted pieces are created without changing Game.
GameStatus makes the game lifecycle explicit. Game.updateStatus transitions from ACTIVE to WHITE_WON, BLACK_WON, or STALEMATE after each accepted move.
Move is the command request consumed by Game.move. The base implementation executes it directly; undo and replay extend the same boundary by storing executed command metadata such as captured piece and previous status.
Step-by-Step Design
1Start with immutable coordinates and a storage-only board
Make Square a value object and keep Board focused on storage, bounds, path queries, copying, and unchecked mutation. Turn logic must not leak into Board.
public boolean isInside(Square square) { return square.getRow() >= 0 && square.getRow() < 8 && square.getCol() >= 0 && square.getCol() < 8; }2Push movement geometry into piece strategies
The abstract Piece exposes the common color and target helper, while each concrete piece implements exactly its own geometry. This avoids a large switch in Game.
public abstract class Piece { private final Color color; protected Piece(Color color) { this.color = color; } public Color getColor() { return color; } public abstract boolean canMove(Board board, Square from, Square to); }3Model sliding, leaping, and pawn movement separately
Sliding pieces ask Board.isPathClear, knights skip path checks, and pawns combine color direction with occupancy-sensitive capture rules. Each rule stays local to the class that needs it.
public boolean canMove(Board board, Square from, Square to) { int rowDelta = Math.abs(to.getRow() - from.getRow()); int colDelta = Math.abs(to.getCol() - from.getCol()); boolean diagonal = rowDelta == colDelta; boolean straight = from.getRow() == to.getRow() || from.getCol() == to.getCol(); return board.isInside(to) && (diagonal || straight) && rowDelta + colDelta > 0 && board.isPathClear(from, to) && canCaptureOrMoveTo(board, to); }4Validate in layers before mutating the real board
Game.move first checks lifecycle, source ownership, piece movement, then self-check on a copied board. Only the final success path calls board.moveUnchecked on the real board.
Board candidate = board.copy(); candidate.moveUnchecked(move.getFrom(), move.getTo()); if (isKingInCheck(candidate, turn)) { throw new IllegalArgumentException("Move leaves king in check"); } board.moveUnchecked(move.getFrom(), move.getTo());5Detect check by asking opposing pieces whether they attack the king
The engine locates the king, scans occupied squares, and asks every opposing piece if it can move to the king's square in the current position.
6Derive checkmate and stalemate from legal-move search
After a valid move, evaluate the next player. If they are in check and have no legal move, the mover wins. If they are not in check and still have no legal move, the game is a stalemate.
private void updateStatus(Color nextToMove) { boolean inCheck = isKingInCheck(board, nextToMove); boolean hasLegalMove = hasAnyLegalMove(nextToMove); if (inCheck && !hasLegalMove) { status = nextToMove == Color.WHITE ? GameStatus.BLACK_WON : GameStatus.WHITE_WON; } else if (!inCheck && !hasLegalMove) { status = GameStatus.STALEMATE; } else { status = GameStatus.ACTIVE; } }7Treat moves as commands and add history at the execution boundary
The reference Move is already an immutable command request. To add undo, store an executed-move record beside Game.move with source, destination, moved piece, captured piece, prior turn, and prior status.
public final class Move { private final Square from; private final Square to; public Move(Square from, Square to) { this.from = from; this.to = to; } }
Complete Java Implementation
Explanation of Every Class
Color
Enum for the two sides. opposite is used by Game to advance the turn and to evaluate the next player after a move.
Square
Immutable row/column coordinate. It exposes accessors and value equality, making it safe to create fresh coordinates during board scans and legal-move search.
Board
Stores a fixed 8x8 Piece matrix. It owns bounds checks, placement, path clearance, occupied-square enumeration, shallow copying for candidate validation, and starting-position setup.
Piece
Abstract movement strategy. It stores color, provides canCaptureOrMoveTo for shared target rules, and requires each concrete piece to implement canMove.
King
Concrete Piece that moves at most one row and one column, cannot remain stationary, and respects target occupancy. Check safety is handled outside by Game.
Queen
Concrete Piece combining diagonal and straight-line movement. It requires non-zero movement, clear path, board bounds, and a legal target.
Rook
Concrete Piece for horizontal or vertical movement. It rejects same-square moves, requires path clearance, and can capture only opposing pieces.
Bishop
Concrete Piece for diagonal movement. The movement is valid only when row and column deltas match, the path is clear, and the target is empty or hostile.
Knight
Concrete Piece for L-shaped movement. It intentionally does not call isPathClear because knights can jump over pieces.
Pawn
Concrete Piece with the densest basic movement rule: color-specific direction, starting-row double advance, forward movement only to empty squares, and diagonal captures only against enemies.
Move
Immutable command request holding from and to squares. It is intentionally free of validation so Game can validate the command against the current board and turn.
Player
Small identity object with name and color. It represents who is playing a side but does not own the pieces; the board owns piece placement.
GameStatus
Enum for the current lifecycle: active, white won, black won, or stalemate. The reference design encodes check as a derived condition rather than a stored status.
Game
The domain controller and state machine. It validates Move, copies the board for self-check detection, commits legal moves, searches for checkmate or stalemate, and exposes current player/status.
Dry Run
Sample input
Fool's mate on the starting board using zero-based coordinates: White f2-f3, Black e7-e5, White g2-g4, Black Qd8-h4. Coordinates use row 0 for black's back rank and column 0 for file a.
| Step | Move | Validation focus | Board or status change | Turn result |
|---|---|---|---|---|
| 0 | Initial setup | Board.setupStartingPosition places all pieces | status ACTIVE | WHITE to move |
| 1 | Move (6,5) to (5,5) | White Pawn moves one row forward into empty square | f-pawn leaves f2 | BLACK to move |
| 2 | Move (1,4) to (3,4) | Black Pawn uses starting-row double step with middle square empty | e-pawn moves to e5 | WHITE to move |
| 3 | Move (6,6) to (4,6) | White Pawn uses starting-row double step and opens king diagonal | g-pawn moves to g4 | BLACK to move |
| 4 | Move (0,3) to (4,7) | Black Queen moves diagonally through a clear path | queen lands on h4 | Evaluate WHITE |
| 5 | updateStatus(WHITE) | White king is attacked and no legal move removes it | status BLACK_WON | Turn does not advance |
The important row is step 4: the queen's geometric move is not enough. Game also copies the board, verifies black does not leave its own king in check, commits the move, then searches whether white has any legal response. With none available, BLACK_WON is set.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| Board.get/place/isInside | O(1) | O(1) | Direct matrix access on a fixed 8x8 board. |
| Piece.canMove | O(1) for King, Knight, Pawn; O(N) for Queen, Rook, Bishop | O(1) | Sliding pieces may scan up to N squares for path clearance. |
| isKingInCheck | O(P × N) | O(P) | Scans occupied squares and asks enemy pieces whether they attack the king; occupiedSquares materializes up to P coordinates. |
| hasAnyLegalMove | O(P × N² × (N² + P × N)) | O(N² + P) | For each piece and destination, the code may copy the board and re-run king safety checks. With N=8 this is still small. |
| Game.move | O(P × N² × (N² + P × N)) worst case, O(1) for standard chess size | O(N² + P) | The expensive part is terminal-state search after a legal move, not source or geometry validation. |
For interviews, say the asymptotic form using board dimension N and piece count P, then immediately note that normal chess fixes N at 8 and P at 32, making the brute-force search acceptable. Optimized engines use bitboards, attack maps, and incremental move generation, but those are unnecessary for LLD clarity.
Extensibility
Special moves
Add validators/effects for castling, en passant, and promotion around Game.move. Promotion can call a PieceFactory without changing basic movement classes.
Move history and undo
Store executed commands with Move, moved piece, captured piece, previous turn, previous status, and promotion metadata. Undo reverses board placement and restores state from that record.
Richer statuses
Extend GameStatus with CHECK, DRAW_BY_REPETITION, FIFTY_MOVE_RULE, RESIGNATION, and TIMEOUT if the product needs these states explicitly.
Variant boards and custom pieces
Extract board size and starting layout into configuration, and register new Piece subclasses behind a factory. Game still calls canMove.
AI or hints
Expose legal move generation as a service that reuses hasAnyLegalMove logic. A bot or hint engine can evaluate candidate boards without mutating the game.
Alternative Designs
Rule engine with validators
Instead of putting most orchestration in Game.move, create a chain of validators: status, source, ownership, movement, self-check, and special-rule validators.
Tradeoffs
Excellent for castling and draw rules, but heavier for an interview unless the candidate keeps the chain readable.
Immutable board snapshots
Every accepted move returns a new Board instead of mutating the current matrix. History and undo become natural because old boards remain available.
Tradeoffs
Simplifies replay and debugging at the cost of extra allocation and more careful sharing of immutable pieces.
ExecutedMove command objects
Make each accepted move an object with execute and undo, storing captured piece, prior status, and prior turn.
Tradeoffs
This is the strongest Command pattern implementation, but it introduces more classes than the reference solution needs for the base problem.
Bitboard engine
Represent each piece set as 64-bit masks and precompute attacks for very fast move generation.
Tradeoffs
Great for chess engines, poor for LLD interviews because it hides object responsibilities behind dense bit manipulation.
Common Mistakes
- ×
Putting all movement logic in Game with piece-type conditionals instead of using Piece.canMove polymorphism.
- ×
Mutating the real board before checking whether the move leaves the current player's king in check.
- ×
Letting Board manage turns or game status, which mixes storage with orchestration.
- ×
Treating check as a stored boolean that can drift from the board instead of deriving it from the current position.
- ×
Forgetting that pawns move and capture differently, and that their direction depends on color.
- ×
Checking piece geometry but forgetting own-piece capture and blocked paths for sliding pieces.
- ×
Declaring checkmate just because the king is attacked, without searching for any legal escape move.
- ×
Designing undo as a blind reverse move without remembering captured pieces and previous status.
Follow-up Interview Questions
QHow would you add castling?
Track whether the king and rook have moved, verify the path is clear, ensure the king is not in check and does not pass through attacked squares, then apply a compound move effect that moves both pieces atomically.
QHow would you implement undo?
Store an executed command record after each accepted move: Move, moved piece, captured piece, prior turn, prior status, and any promotion or castling side effects. Undo restores all of those fields in reverse order.
QWhere should legal move generation live?
The primitive geometry stays in Piece.canMove. A higher-level move generator can live beside Game and reuse board copying plus self-check validation to enumerate only legal moves.
QWhy copy the board before applying a move?
It lets the engine test self-check without risking a partially mutated real board. If the move is illegal, the committed state remains untouched.
QHow would you support custom chess variants?
Make board dimensions, starting layout, and piece factory configuration-driven. Each custom piece still implements canMove, so Game remains generic.
QShould CHECK be part of **GameStatus**?
It depends on product needs. The reference derives check during status updates and stores only terminal states. If the UI must display CHECK persistently, add it as a non-terminal state carefully so turn transitions remain clear.
Production Considerations
Persistence and replay
Persist the initial position plus a validated move log. Reconstruct board state by replaying commands, and store snapshots periodically for faster recovery.
Rule-versioning
Store which rule set created a game. Chess variants, bug fixes, or tournament modes should not reinterpret old move histories differently.
Concurrency
For online play, serialize moves per game with an optimistic version or lock. Reject stale moves whose expected turn/version no longer matches.
Observability
Emit events for move accepted, move rejected, checkmate, stalemate, resignation, timeout, and undo. These events support analytics and dispute debugging.
Input boundaries
Translate algebraic notation, UI clicks, or API payloads into Move at the boundary. The domain should only receive validated coordinate objects.
What Interviewers Look For
Did the candidate keep Board, Piece, and Game responsibilities separate?
Did they reject illegal moves before mutating the committed board?
Did they explain why checkmate requires legal-move search, not just detecting attack on the king?
Did they mention the command/history metadata needed for undo, including captured pieces and previous status?
Did they offer extension seams for castling, promotion, variants, and richer draw rules without rewriting the engine?
Did they avoid over-optimizing into bitboards before the object model is clear?
Quiz
0/5 answered
1.Why should movement rules live in **Piece** subclasses?
2.What is the main reason **Game.move** copies the board before committing a move?
3.Which condition indicates stalemate in this design?
4.What extra information is required to undo a capture correctly?
5.Why is **Board** kept free of turn logic?
Practice Variants
Add castling and promotion
AdvancedTrack whether king and rooks moved, validate attacked transit squares, and use a factory to replace a pawn on promotion.
Implement undo and redo
AdvancedAdd an executed-move history stack and a redo stack. Include captured piece, prior turn, prior status, and compound move side effects.
Add algebraic notation parsing
IntermediateTranslate user-facing notation into Move while keeping domain validation in Game.
Support chess variants
ExpertMake board size, initial layout, and registered piece strategies configurable for variants such as Chess960 or custom pieces.
Flashcards
Cheat Sheet
Core model: Game coordinates turns and status; Board stores an 8x8 piece matrix; Square identifies coordinates; Move carries from/to; Player binds name to color.
Piece strategy: Piece is abstract. King, Queen, Rook, Bishop, Knight, and Pawn each implement canMove. Sliding pieces use Board.isPathClear; knights do not; pawns depend on color and target occupancy.
Validation order: status active → source has current-player piece → piece geometry is legal → candidate board does not leave mover's king in check → commit real board → update next player's status → advance turn only if active.
State: GameStatus stores ACTIVE, WHITE_WON, BLACK_WON, STALEMATE. Check is derived from the current board; checkmate is check plus no legal move.
Patterns: Strategy for piece movement, Factory Method seam for piece creation/setup, State for game lifecycle, Command for Move and future undo/replay history.
Extensibility: Add castling, promotion, en passant, move history, notation parsing, custom pieces, and variant boards around Game.move without corrupting Board or existing piece rules.
References
- BookDesign Patterns: Elements of Reusable Object-Oriented Software — Gamma, Helm, Johnson, and Vlissides
- BookEffective Java — Enums, immutability, and method design — Joshua Bloch
- DocsRefactoring Guru — Strategy Pattern
- DocsChess Programming Wiki — Move Generation