Worked system design solution

Design a Chess Game

A two-player chess engine with move validation, special rules (castling, en passant, promotion), check/checkmate detection, and game history. Exercises polymorphism (piece movement rules), the Command pattern (moves), and the State pattern (game phase).

LLDHard22 min readoopgamepolymorphismstate-machine

Clarify Requirements

Standard chess + the special rules

Functional requirements

Standard 8×8 chess board with the usual 32 pieces in standard starting position.
Two players (White / Black) alternate moves; White first.
Validate every move per piece movement rules.
Special moves: castling (kingside / queenside), en passant, pawn promotion.
Detect check, checkmate, stalemate.
Detect draws: stalemate, 50-move rule, threefold repetition, insufficient material.
Maintain move history (algebraic notation) for replay / undo.
A player can resign; the other wins.

Non-functional requirements

Move validation in O(legal-move-count) — fast enough to be the engine for a UI.
Reentrant: game.makeMove(...) doesn't depend on global state.
Serializable game state (FEN-like).

Out of scope (v1)

Computer AI / move suggestion.
Network multiplayer (wrap the model).
Time controls (clocks).
Chess960 variants.

Edge cases

Edge case	Expected behavior
Move that leaves your own king in check	Reject as illegal
Castling through check / from check	Reject
En passant only valid for one move after the pawn's two-square push	Tracked via lastMove
Pawn promotion — must choose Q/R/B/N	API requires the choice in the move
Resign during opponent's turn	Allowed
50-move + 75-move (forced draw) rules	Implement both: claim vs auto

Interview: Chess is enormous. State scope before sketching — pick the rules you'll implement and explicitly note (with one sentence each) what you skip. Otherwise the interview gets lost in details.

Core Entities

Board, Piece hierarchy, Move, GameState

Domain nouns

Position: (row 0-7, col 0-7). Value object.
Color: enum White / Black.
Piece: abstract base — King, Queen, Rook, Bishop, Knight, Pawn. Each has its own legal-move logic.
Square: a board cell; holds a Piece or null.
Board: 8×8 grid of Squares.
Move: from, to, piece, captured (if any), special (castle/enPassant/promotion).
Game: aggregate root; board + history + current player + state.
GameState: InProgress | Check | Checkmate | Stalemate | Draw | Resigned.

Piece polymorphism

classDiagram
  class Piece {
    <<abstract>>
    +color: Color
    +hasMoved: bool
    +pseudoLegalMoves(board, from): Position[]
    +symbol(): string
  }
  Piece <|-- King
  Piece <|-- Queen
  Piece <|-- Rook
  Piece <|-- Bishop
  Piece <|-- Knight
  Piece <|-- Pawn

Each piece subclass overrides pseudoLegalMoves(board, from) — returns squares the piece can move to ignoring whether the move would expose its own king.

"Pseudo-legal" vs "legal"

A pseudo-legal move follows piece movement rules. A legal move is pseudo-legal AND doesn't leave the mover's own king in check. The Game filters pseudo-legal moves by simulating each and checking king safety.

Classes & Relationships

Class diagram + the move-then-undo trick

Class diagram

classDiagram
  class Color { <<enum>> White Black }
  class Position { +row: int; +col: int }
  class Piece {
    <<abstract>>
    +color: Color
    +hasMoved: bool
    +pseudoLegalMoves(board, from): Position[]
  }
  class King
  class Queen
  class Rook
  class Bishop
  class Knight
  class Pawn
  class Move {
    +from: Position
    +to: Position
    +piece: Piece
    +captured: Piece?
    +special: SpecialMove?
    +promotion: PieceType?
  }
  class Board {
    +grid: Square[8][8]
    +at(pos): Piece?
    +place(piece, pos)
    +remove(pos)
    +clone(): Board
  }
  class Game {
    -board: Board
    -history: Move[]
    -turn: Color
    -state: GameState
    +makeMove(from, to, promotion?): Move
    +legalMoves(color): Move[]
    +isInCheck(color): bool
    +resign(color)
  }
  Piece <|-- King
  Piece <|-- Queen
  Piece <|-- Rook
  Piece <|-- Bishop
  Piece <|-- Knight
  Piece <|-- Pawn
  Game *-- Board
  Game *-- Move
  Move *-- Piece

The make-undo trick for legality

To check if a move leaves my king in check:

applyMove(move);                     // mutate board
const inCheck = isAttacked(myKingPos, opponentColor);
undoMove(move);                      // restore board
return !inCheck;

Cheaper than cloning the whole board for every candidate move. Requires reversible mutations (every applyMove must remember enough to undo).

Check detection

A king is in check if any opponent piece's pseudo-legal moves include the king's square. To check, scan all opponent pieces and test their attack squares.

For performance at scale (chess engines), precompute attack maps. For interview-scope: scan is fine.

Code Implementation

TypeScript core (Java + C++ follow same patterns)

Core TypeScript

export enum Color { White = 'W', Black = 'B' }
export enum PieceType { King = 'K', Queen = 'Q', Rook = 'R', Bishop = 'B', Knight = 'N', Pawn = 'P' }
export interface Position { row: number; col: number; }

export abstract class Piece {
  hasMoved = false;
  constructor(public readonly color: Color) {}
  abstract type(): PieceType;
  abstract pseudoLegalMoves(board: Board, from: Position): Position[];
}

export class Pawn extends Piece {
  type() { return PieceType.Pawn; }
  pseudoLegalMoves(board: Board, from: Position): Position[] {
    const dir = this.color === Color.White ? -1 : 1;
    const moves: Position[] = [];
    const oneAhead = { row: from.row + dir, col: from.col };
    if (board.inBounds(oneAhead) && !board.at(oneAhead)) {
      moves.push(oneAhead);
      const twoAhead = { row: from.row + 2*dir, col: from.col };
      if (!this.hasMoved && !board.at(twoAhead)) moves.push(twoAhead);
    }
    for (const dc of [-1, 1]) {
      const cap = { row: from.row + dir, col: from.col + dc };
      if (board.inBounds(cap) && board.at(cap)?.color === oppositeColor(this.color)) {
        moves.push(cap);
      }
      // En passant — check Game.lastMove
    }
    return moves;
  }
}

export class Knight extends Piece {
  type() { return PieceType.Knight; }
  pseudoLegalMoves(board: Board, from: Position): Position[] {
    const deltas = [[-2,-1],[-2,1],[-1,-2],[-1,2],[1,-2],[1,2],[2,-1],[2,1]];
    return deltas
      .map(([dr, dc]) => ({ row: from.row+dr, col: from.col+dc }))
      .filter(p => board.inBounds(p) && board.at(p)?.color !== this.color);
  }
}

export class Bishop extends Piece {
  type() { return PieceType.Bishop; }
  pseudoLegalMoves(board: Board, from: Position): Position[] {
    return slidingMoves(board, from, this.color, [[-1,-1],[-1,1],[1,-1],[1,1]]);
  }
}

export class Rook extends Piece {
  type() { return PieceType.Rook; }
  pseudoLegalMoves(board: Board, from: Position): Position[] {
    return slidingMoves(board, from, this.color, [[-1,0],[1,0],[0,-1],[0,1]]);
  }
}

export class Queen extends Piece {
  type() { return PieceType.Queen; }
  pseudoLegalMoves(board: Board, from: Position): Position[] {
    return slidingMoves(board, from, this.color,
      [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]);
  }
}

export class King extends Piece {
  type() { return PieceType.King; }
  pseudoLegalMoves(board: Board, from: Position): Position[] {
    const deltas = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
    return deltas
      .map(([dr, dc]) => ({ row: from.row+dr, col: from.col+dc }))
      .filter(p => board.inBounds(p) && board.at(p)?.color !== this.color);
    // Castling handled in Game.legalMoves
  }
}

function slidingMoves(board: Board, from: Position, color: Color, dirs: number[][]): Position[] {
  const out: Position[] = [];
  for (const [dr, dc] of dirs) {
    let r = from.row + dr, c = from.col + dc;
    while (board.inBounds({row:r, col:c})) {
      const p = board.at({ row: r, col: c });
      if (!p) { out.push({ row: r, col: c }); }
      else { if (p.color !== color) out.push({ row: r, col: c }); break; }
      r += dr; c += dc;
    }
  }
  return out;
}

function oppositeColor(c: Color): Color { return c === Color.White ? Color.Black : Color.White; }

export class Board {
  private grid: (Piece | null)[][] = Array.from({ length: 8 }, () => Array(8).fill(null));

  static initial(): Board {
    const b = new Board();
    // Place pawns, then back rank in standard order…
    for (let c = 0; c < 8; c++) {
      b.grid[1][c] = new Pawn(Color.Black);
      b.grid[6][c] = new Pawn(Color.White);
    }
    const backRank = (color: Color, row: number) => {
      b.grid[row] = [new Rook(color), new Knight(color), new Bishop(color), new Queen(color),
                     new King(color), new Bishop(color), new Knight(color), new Rook(color)];
    };
    backRank(Color.Black, 0);
    backRank(Color.White, 7);
    return b;
  }

  at(pos: Position): Piece | null {
    if (!this.inBounds(pos)) return null;
    return this.grid[pos.row][pos.col];
  }
  inBounds(pos: Position): boolean { return pos.row >= 0 && pos.row < 8 && pos.col >= 0 && pos.col < 8; }
  place(pos: Position, piece: Piece | null): void { this.grid[pos.row][pos.col] = piece; }

  findKing(color: Color): Position {
    for (let r = 0; r < 8; r++) for (let c = 0; c < 8; c++) {
      const p = this.grid[r][c];
      if (p?.color === color && p.type() === PieceType.King) return { row: r, col: c };
    }
    throw new Error('King not found');
  }
}

export type GameState = { kind: 'in_progress' } | { kind: 'check'; color: Color }
  | { kind: 'checkmate'; winner: Color } | { kind: 'stalemate' } | { kind: 'draw'; reason: string }
  | { kind: 'resigned'; winner: Color };

export class Game {
  private board = Board.initial();
  private turn: Color = Color.White;
  private state: GameState = { kind: 'in_progress' };
  private readonly history: Move[] = [];

  makeMove(from: Position, to: Position, promotion?: PieceType): Move {
    if (this.state.kind !== 'in_progress' && this.state.kind !== 'check') throw new Error('game over');
    const piece = this.board.at(from);
    if (!piece || piece.color !== this.turn) throw new Error('no piece of yours at from');
    const legal = this.legalMovesFor(piece, from);
    if (!legal.some(p => p.row === to.row && p.col === to.col)) throw new Error('illegal move');

    const captured = this.board.at(to);
    const move: Move = { from, to, piece, captured, promotion };
    this.applyMove(move);
    this.history.push(move);
    this.turn = oppositeColor(this.turn);
    this.updateState();
    return move;
  }

  private legalMovesFor(piece: Piece, from: Position): Position[] {
    const pseudo = piece.pseudoLegalMoves(this.board, from);
    return pseudo.filter(to => this.isMoveSafe(piece, from, to));
  }

  private isMoveSafe(piece: Piece, from: Position, to: Position): boolean {
    const captured = this.board.at(to);
    this.board.place(to, piece);
    this.board.place(from, null);
    const kingPos = this.board.findKing(piece.color);
    const safe = !this.isAttacked(kingPos, oppositeColor(piece.color));
    // undo
    this.board.place(from, piece);
    this.board.place(to, captured);
    return safe;
  }

  private isAttacked(pos: Position, byColor: Color): boolean {
    for (let r = 0; r < 8; r++) for (let c = 0; c < 8; c++) {
      const p = this.board.at({ row: r, col: c });
      if (p?.color === byColor) {
        const moves = p.pseudoLegalMoves(this.board, { row: r, col: c });
        if (moves.some(m => m.row === pos.row && m.col === pos.col)) return true;
      }
    }
    return false;
  }

  private applyMove(move: Move): void {
    this.board.place(move.from, null);
    let piece = move.piece;
    if (move.promotion) {
      const PromCls = { Q: Queen, R: Rook, B: Bishop, N: Knight }[move.promotion];
      if (PromCls) piece = new PromCls(move.piece.color);
    }
    this.board.place(move.to, piece);
    piece.hasMoved = true;
    // (castling rook move + en-passant capture logic also here in a complete impl)
  }

  private updateState(): void {
    const inCheck = this.isAttacked(this.board.findKing(this.turn), oppositeColor(this.turn));
    const hasLegalMove = this.hasAnyLegalMove(this.turn);
    if (inCheck && !hasLegalMove) this.state = { kind: 'checkmate', winner: oppositeColor(this.turn) };
    else if (!inCheck && !hasLegalMove) this.state = { kind: 'stalemate' };
    else if (inCheck) this.state = { kind: 'check', color: this.turn };
    else this.state = { kind: 'in_progress' };
  }

  private hasAnyLegalMove(color: Color): boolean {
    for (let r = 0; r < 8; r++) for (let c = 0; c < 8; c++) {
      const p = this.board.at({ row: r, col: c });
      if (p?.color === color && this.legalMovesFor(p, { row: r, col: c }).length > 0) return true;
    }
    return false;
  }

  resign(color: Color): GameState {
    if (this.state.kind === 'checkmate' || this.state.kind === 'resigned') return this.state;
    this.state = { kind: 'resigned', winner: oppositeColor(color) };
    return this.state;
  }

  getState(): GameState { return this.state; }
}

export interface Move {
  from: Position; to: Position;
  piece: Piece; captured: Piece | null;
  promotion?: PieceType;
}

(Castling + en-passant omitted for brevity — same pattern: special-case in legalMovesFor for King's castling moves; applyMove for the rook move; en-passant tracked via Game.lastMove and special-cased in Pawn.)

Java / C++ equivalents

The patterns transfer directly — abstract Piece + concrete classes, immutable Position records, Game as the aggregate root.

Edge Cases & Tests

Common chess gotchas

Critical tests

Pinned piece cannot move if doing so exposes the king.
Castling: rejected if king or rook has moved, if any square between is attacked, or if king is in check.
En passant valid only on the move immediately after the pawn's two-square advance.
Promotion requires the player to specify Q/R/B/N — without it, the move is incomplete.
Pawn moves are color-direction asymmetric.
Checkmate ≠ "king attacked." It's "king attacked AND no legal move escapes."
Stalemate: no legal move BUT NOT in check → draw.
Insufficient material: K vs K, K+B vs K, K+N vs K, K+B vs K+B (same color bishop). Draw.

describe('Chess corner cases', () => {
  it('rejects pinned-piece move', () => {
    // Setup: white king e1, white rook e2 (pinned by black queen e8)
    // Moving the rook off the e-file exposes the king → illegal
  });

  it('detects checkmate (Fool's Mate)', () => {
    const g = new Game();
    g.makeMove({row:6,col:5},{row:5,col:5}); // 1. f3
    g.makeMove({row:1,col:4},{row:3,col:4}); // 1... e5
    g.makeMove({row:6,col:6},{row:4,col:6}); // 2. g4
    g.makeMove({row:0,col:3},{row:4,col:7}); // 2... Qh4#
    expect(g.getState().kind).toBe('checkmate');
  });

  it('stalemate is a draw', () => { /* classic K+Q vs K stalemate position */ });
});

Extensibility & Trade-offs

AI hooks, network, persistence

Extensions

Computer opponent: Player becomes an interface; AIPlayer implements pickMove(game). Game loop doesn't care.
Network play: wrap Game in a GameServer that broadcasts moves over WS.
Persistence: serialize FEN string after each move. Replay by reconstructing.
Variants: Chess960 changes only initial setup. King-of-the-Hill changes the win condition. Each is a small variant of Game.
Move suggestion / hints: enumerate legal moves, score each (material balance), return top-K.

Trade-offs

Trade-off	Got	Gave up
make-undo for legality	O(legal-moves) per turn	Mutable board — careful with concurrent reads
Polymorphic piece classes	Clean OOP, easy to add variant pieces	More classes than a flat data structure
No precomputed attack maps	Simpler code	Slower at very high move-rate (chess engines do precompute)
50/threefold rules unimplemented	Saves complexity	Spec gap

Interview: Chess is famously a "show your scoping discipline" interview. Strong candidates pick a subset (e.g., "I'll implement standard moves + check + checkmate, skipping castling + en passant for time") and ship that cleanly rather than half-implementing everything.

Practice this question