Chess / Tic-Tac-Toe Engine

Problem statement (interviewer prompt)

Design the model for a chess game engine + UI: board, pieces, legal-move generation per piece type, special moves (castling, en passant, promotion), check / checkmate / stalemate detection, move history with undo, and PGN import/export. Optional: AI player.

classDiagram
  class Game
  class Board
  class Piece
  class Move
  class Player
  class Rules
  Game *-- Board
  Game *-- "many" Player
  Board *-- "many" Piece
  Game --> Move
  Game --> Rules

How the engine works

A chess engine is a deterministic state machine driven by alternating moves. Game owns an 8x8 Board, two Player instances, a MoveHistory stack, and a Rules collaborator. On every turn the active player proposes a Move; the engine validates it through polymorphic piece dispatch, mutates the board, then checks for check, checkmate, stalemate, threefold repetition, and the 50-move rule. The interview value of chess LLD is not the rules themselves: it is forcing a clean split between piece-specific move geometry (each Piece subclass knows only its own movement pattern) and global game state (turn order, special moves, draw detection, history). A god-object Game that hardcodes piece movement collapses the moment the interviewer asks for Chess960 or en passant.

The class hierarchy below is the canonical OO model. Real engines such as Stockfish use bitboards for speed, but the bitboard trick is performance, not design; the OO model is what an interview answer should deliver.

Detailed class diagram with multiplicities

classDiagram
  direction TB

  class ChessGame {
    -board: Board
    -players: List~Player~
    -turn: Color
    -history: MoveHistory
    -status: GameStatus
    +makeMove(m) MoveResult
    +undo()
    +isInCheck(c) bool
    +status() GameStatus
  }

  class Board {
    -squares: Square[8][8]
    +get(pos) Piece
    +set(pos, piece)
    +isValidMove(m) bool
    +applyMove(m) Piece
    +revertMove(m, captured)
    +findKing(c) Position
    +copy() Board
  }

  class Square {
    +position: Position
    +piece: Piece
  }

  class Piece {
    <<abstract>>
    +color: Color
    +position: Position
    +hasMoved: bool
    +canMoveTo(board, dest) bool*
    +symbol() char*
  }

  class King {
    +canMoveTo(board, dest) bool
  }
  class Queen {
    +canMoveTo(board, dest) bool
  }
  class Rook {
    +canMoveTo(board, dest) bool
  }
  class Bishop {
    +canMoveTo(board, dest) bool
  }
  class Knight {
    +canMoveTo(board, dest) bool
  }
  class Pawn {
    +canMoveTo(board, dest) bool
    +canCaptureEnPassant(board, dest) bool
  }

  class Move {
    +from: Position
    +to: Position
    +piece: Piece
    +captured: Piece
    +promoteTo: PieceType
    +special: SpecialMove
    +isValid(board) bool
  }

  class MoveHistory {
    -stack: Deque~Move~
    +push(m)
    +pop() Move
    +last() Move
    +positions() List~ZobristHash~
  }

  class SpecialMove {
    <<enumeration>>
    NONE
    EN_PASSANT
    CASTLING_KINGSIDE
    CASTLING_QUEENSIDE
    PROMOTION
  }

  class GameStatus {
    <<enumeration>>
    ACTIVE
    CHECK
    CHECKMATE
    STALEMATE
    DRAW_REPETITION
    DRAW_FIFTY_MOVE
    DRAW_INSUFFICIENT
  }

  class Player {
    +name: String
    +color: Color
    +rating: int
  }

  class HumanPlayer
  class AIPlayer {
    -depth: int
    +chooseMove(board) Move
  }

  class PieceFactory {
    +standardSetup(board)
    +fromFEN(board, fen)
  }

  class GameObserver {
    <<interface>>
    +onMove(m)
    +onCheck(c)
    +onGameEnd(status)
  }

  ChessGame "1" *-- "1" Board
  ChessGame "1" *-- "2" Player
  ChessGame "1" *-- "1" MoveHistory
  ChessGame "1" --> "1" GameStatus
  ChessGame "1" o-- "0..*" GameObserver
  Board "1" *-- "64" Square
  Square "1" o-- "0..1" Piece
  Piece <|-- King
  Piece <|-- Queen
  Piece <|-- Rook
  Piece <|-- Bishop
  Piece <|-- Knight
  Piece <|-- Pawn
  Player <|-- HumanPlayer
  Player <|-- AIPlayer
  Move --> SpecialMove
  MoveHistory "1" *-- "0..*" Move
  PieceFactory ..> Board

Move validation flow in Java

The Java sketch pins down the heart of the engine: Board.isValidMove is a thin coordinator that delegates the geometry check to the piece via polymorphism, then layers global rules (turn order, self-check, special moves). The Knight.canMoveTo body shows what a concrete subclass implements; the same pattern repeats for the other five piece types, with each one isolating a different movement rule.

public final class Board {
    private final Square[][] squares = new Square[8][8];

    public boolean isValidMove(Move m) {
        Piece piece = get(m.from());
        if (piece == null) return false;
        if (piece.color() != m.piece().color()) return false;

        Piece target = get(m.to());
        if (target != null && target.color() == piece.color()) {
            return false; // cannot capture own piece
        }

        // Polymorphic dispatch: each subclass enforces its own geometry.
        if (!piece.canMoveTo(this, m.to())) return false;

        // Special moves bypass standard geometry rules.
        if (m.special() == SpecialMove.CASTLING_KINGSIDE
            || m.special() == SpecialMove.CASTLING_QUEENSIDE) {
            return canCastle(piece, m);
        }
        if (m.special() == SpecialMove.EN_PASSANT) {
            return ((Pawn) piece).canCaptureEnPassant(this, m.to());
        }

        // Global rule: a move that leaves your own king in check is illegal.
        Piece captured = applyMove(m);
        boolean leavesKingInCheck = isAttacked(findKing(piece.color()),
                                               piece.color().opponent());
        revertMove(m, captured);
        return !leavesKingInCheck;
    }
}

public final class Knight extends Piece {
    @Override
    public boolean canMoveTo(Board board, Position dest) {
        int dr = Math.abs(dest.row() - position.row());
        int dc = Math.abs(dest.col() - position.col());
        // L-shape: 2-by-1 or 1-by-2. Knight jumps, so no blocked-path check.
        return (dr == 2 && dc == 1) || (dr == 1 && dc == 2);
    }
}

The applyMove / revertMove pair is what makes self-check detection cheap: rather than cloning the entire board, the engine mutates in place, asks isAttacked whether the king is now under threat, and rolls back. This is the same trick used by AI search; alpha-beta minimax pushes and pops hundreds of millions of trial moves per second, so a deep board copy would tank performance.

Design patterns used

Each pattern below maps directly to a real follow-up an interviewer is likely to ask, so naming them in the answer pays off.

• Strategy / Polymorphism for Piece: each subclass (King, Queen, Rook, Bishop, Knight, Pawn) implements canMoveTo with its own geometry. Board.isValidMove never branches on piece type; it calls the abstract method and the JVM dispatches to the right implementation. Adding a fairy piece (e.g. an Archbishop for chess variants) is one new subclass with no change to Board or Game.
• Command for Move: each move object carries from, to, captured piece, promotion type, and the special-move flag. Pushing the move onto MoveHistory makes the move stack a sequence of executable commands; undo pops the last one and runs revertMove. The same command shape is what PGN export serialises, and what a networked client transmits over the wire.
• Memento for save/load: a GameSnapshot captures the board state, side-to-move, castling rights, en-passant target, half-move clock, and full-move number. This is the in-memory equivalent of a FEN string, and the engine restores a snapshot by replacing the board reference and resetting MoveHistory. Snapshots are what enable branching analysis lines without mutating the live game.
• Observer for game-state notifications: GameObserver listeners receive onMove, onCheck, and onGameEnd events. The UI renderer, sound effects, network broadcaster, opening-book logger, and engine evaluator each register independently; ChessGame never imports any of them.
• Factory for piece setup: PieceFactory.standardSetup(board) places the 32 pieces in starting position; PieceFactory.fromFEN(board, fen) parses a FEN string into a board state for puzzle solvers, opening books, and Chess960 variants where the back rank is shuffled. The factory keeps construction logic out of Board and ChessGame.
• State (implicit on GameStatus): the game flows through ACTIVE, CHECK, CHECKMATE, STALEMATE, and various draw states. Each transition is triggered by the rules engine after makeMove; an interviewer asking "how would you formalise the game lifecycle" expects a state-diagram answer.

Common variants & follow-ups

These are the questions that follow the base design and reward a layered model.

• Game clocks and time controls: each Player owns a Clock that ticks down only while it is their turn. Standard formats are Bullet (1+0, 1 minute total), Blitz (3+2, three minutes with two-second increment), Rapid (15+10), and Classical (90+30 with adjournment rules). A clock observer flips when makeMove returns, deducts the elapsed time, and adds the increment; running out of time triggers a TIMEOUT end state unless the opponent has insufficient mating material.
• Networked multiplayer: replace direct Game.makeMove calls with a turn-event bus. Each client submits a MoveIntent containing source square, destination square, and promotion type; the authoritative server validates against its own Board, applies the move, and broadcasts the resulting Move to both clients. The observer pattern carries the result into the UIs unchanged.
• AI opponent: implement AIPlayer.chooseMove with minimax + alpha-beta pruning. The search explores legal-move trees to a fixed depth, evaluates leaves with a material + positional heuristic, and prunes branches that cannot improve on the current best line. Iterative deepening picks a deeper search when time allows; a transposition table keyed on Zobrist hashes caches positions seen across branches, cutting the effective branching factor.
• Chess variants: Chess960 (Fischer Random) shuffles the back rank to one of 960 valid starting positions, which the PieceFactory.fromFEN path already supports. Crazyhouse lets captured pieces be dropped back on the board for the capturing side, adding a DropMove subclass and a Pocket collection per player. King of the Hill changes only the win condition, so it lives in the Rules checker.
• PGN serialisation: Portable Game Notation writes each Move as Standard Algebraic Notation (Nf3, O-O, e8=Q+) with seven required tags (Event, Site, Date, Round, White, Black, Result). The exporter walks MoveHistory and emits SAN; the importer parses SAN, resolves the source square via legal-move generation, and replays moves onto a fresh board.
• Draw conditions: 50-move rule triggers when no pawn move and no capture happen for 50 full moves; a counter on MoveHistory resets on each pawn move or capture. Threefold repetition triggers when the same position (board + side-to-move + castling rights + en-passant target) occurs three times in the game; the engine hashes positions with Zobrist hashing and counts occurrences. Insufficient material detects K-vs-K, K+B-vs-K, K+N-vs-K, and K+B-vs-K+B with same-colour bishops.

Edge cases

A solid LLD answer enumerates the awkward rules before the interviewer has to dig for them.

• En passant capture: a pawn that advances two squares from its starting rank can be captured on the very next move by an enemy pawn that sits on the same rank as if it had only moved one square. The engine tracks the en-passant target square on each move (a single Position field on MoveHistory.last); only the immediately following move can use it. After one half-move passes, the right expires.
• Castling: kingside (O-O) and queenside (O-O-O) each require five conditions: neither the king nor the chosen rook has moved, all squares between them are empty, the king is not currently in check, the king does not pass through a square attacked by the opponent, and the king does not land on an attacked square. The hasMoved flag on King and Rook short-circuits the first check; the path scan handles the rest.
• Pawn promotion: a pawn that reaches the opposite back rank is replaced by a Queen, Rook, Bishop, or Knight of the same colour. The UI prompts the human player to pick; an AI promotes to Queen by default unless a tactical underpromotion is preferred. The Move.promoteTo field carries the choice, and Board.applyMove swaps the pawn for the chosen piece type via PieceFactory.create.
• Check vs checkmate vs stalemate: check means the king is under attack but at least one legal move escapes it. Checkmate means the king is under attack and no legal move escapes it (move generation returns an empty list). Stalemate means the king is not under attack but the side to move has no legal move; this is a draw. The same legal-move generator answers all three.
• Threefold repetition detection: hash each position with Zobrist hashing, a 64-bit XOR over precomputed random bitstrings keyed on (piece type, square, side-to-move, castling rights, en-passant target). Maintain a counter map Map<Long, Integer>; when any key hits three, the engine emits a DRAW_REPETITION status. Without Zobrist, naive board string comparison balloons to megabytes for long games.
• 50-move rule: increment a halfmoveClock on every move; reset it to zero on a pawn move or capture. When the clock hits 100 half-moves (50 by each side), the engine flags DRAW_FIFTY_MOVE. FIDE introduced a 75-move auto-draw rule that fires without a player claim; both are easy to implement on the same counter.
• Discovered check and double check: a piece moving off a rank, file, or diagonal can expose the opponent's king to attack from a previously blocked sliding piece. Double check (the moving piece attacks the king and the unblocked piece also attacks it) forces a king move; capturing or blocking is impossible. The standard isInCheck after applyMove catches both cases without special handling.

Glossary & fundamentals

Concept	What it is	Fundamentals
State machine	game status	mvcc-isolation-levels
Idempotency	networked move replay	idempotency-retries
Pub/Sub	move event broadcast	pub-sub-pattern

Quick reference

Functional

• Represent board + pieces.
• Validate moves (legal, in-check rules).
• Detect end states: checkmate/stalemate/draw.
• Optional AI player.
• Networked play.

Patterns

• Strategy (Player AI/Human).
• State (GameStatus).
• Command (Move + undo stack).
• Visitor (per-piece legal moves).

Trade-offs

• Bitboard representation (64-bit) for chess scales to engine performance.
• Per-piece subclass is OO-clean but slower than bitboards.
• Rule engine centralizes special moves (castling, en passant, promotion).

FAQ

How do you model chess pieces in object-oriented design?

Use an abstract Piece class with subclasses for King, Queen, Rook, Bishop, Knight, and Pawn that each implement legalMoves(board, pos).

How is checkmate detected?

Generate every legal move for the side to move; if no move removes the king from check, it is checkmate. Stalemate is the same test when the king is not currently in check.

How do you support undo in a chess engine?

Treat each Move as a Command object with from, to, captured piece, and special-move flags so you can apply and revert moves against a history stack.

What design patterns fit a chess engine?

Strategy for Human vs AI players, State for game status, Command for moves and undo, and Visitor or polymorphism for per-piece legal-move generation.

Why do real engines use bitboards instead of piece classes?

Bitboards encode each piece type as a 64-bit integer so move generation and attacks become bitwise operations, which is far faster than OO traversal at engine speed.

Related Topics

• Snake & Ladders: turn-based board-game LLD
• Tic-Tac-Toe: simpler grid-game design
• State Machines: game-state transition pattern

Refs

• "Programming a Chess Engine" classic tutorials; Stockfish source.