Skip to content

Design chess

TL;DR

  • You build a rules engine: a Board that applies and undoes moves, a Piece hierarchy that generates its own geometry, and a ChessGame that owns the turn, the status and the lock.
  • Three decisions carry the interview: legality is decided by simulation (apply, ask "is my king in check?", undo), castling rights live on the board, not on the piece, and undo restores a memento, not a guess.
  • Patterns that earn their place: Template Method, Flyweight, Memento, Command, Factory. An if/elif ladder on piece type is deliberately absent.

Problem statement

"Implement chess. Two players alternate moves on an 8x8 board. Every piece type moves differently; a move is illegal if it leaves your own king attacked. Support captures, castling, pawn promotion and en passant, detect check, checkmate and stalemate, let a player resign or agree a draw, and support taking back moves. I want the class model, the legal-move generation, and the flow of a single make_move call — including what happens when the move is rejected."

Requirements

Functional

  • Standard starting position, white moves first, strict turn alternation.
  • Legal move generation per piece type: king, queen, rook, bishop, knight, pawn.
  • Check detection; checkmate and stalemate detection after every move.
  • Captures, including en passant; pawn promotion with an explicit piece choice.
  • Castling on both wings, with the rights, path and "not through check" rules.
  • Move history, and undo that restores captured pieces, castling rights and the en-passant square.
  • Resignation and draw by agreement; a queryable game status at all times.

Non-functional and constraints

  • A move is validated and applied atomically: two clients pushing moves into one game must never interleave halfway.
  • Deterministic and testable: positions can be built directly, time and IDs are injected.
  • In-memory, single process. The engine is a library; the UI, the network and the clock sit outside it.

Out of scope: an opponent (search and evaluation), algebraic notation parsing, threefold repetition and the 50-move claim, time controls, opening books, PGN import.

Clarifying questions and assumptions

Question to ask Assumption taken here
Do you want a playable engine or an AI? Rules only. Search is a follow-up and would be a separate class that consumes legal_moves.
Which special moves are in? All three: castling, promotion and en passant. They are where the design is tested, so cutting them cuts the interesting part.
Who chooses the promotion piece? The caller, always. a7a8 without a piece is an error, not a silent queen; a rejected choice is far cheaper than a wrong one.
How are moves expressed? Coordinate notation (e2e4, a7a8q). Standard algebraic notation is a formatter on top and is a follow-up.
Is undo unlimited? Yes, back to the first move. Resignation and an agreed draw are final: undo would rewrite a result both players accepted.
Can the same game be driven from two connections? Yes, so the game holds a lock. The board itself is not thread-safe by design.
Do you need draws by repetition or the 50-move rule? Not for the first pass; the half-move clock is tracked so the rule is a small addition.

Core entities and relationships

  • Piece (abstract) with SlidingPiece (Queen, Rook, Bishop), SteppingPiece (Knight, King) and Pawn. A piece knows its geometry and nothing else — not its square, not whether it has moved.
  • PieceFactory — interns one instance per colour and type. Thirty-two pieces on the board are twelve objects.
  • Square — a frozen (file, rank) pair with shifted() returning None off the board, which removes every bounds check from the generators.
  • Move — a command object: origin, target, a MoveKind for the three special cases, and an optional promotion type.
  • Board — piece placement plus the four pieces of state a position needs beyond it: side to move, CastlingRights, the en-passant target square, and the half-move clock. It applies and undoes moves and answers is_attacked.
  • MoveRecord — the memento Board.apply returns and Board.undo consumes.
  • MoveValidator — turns a raw (from, to) request into a legal Move or an error that names the reason.
  • MoveHistory — the caretaker: a stack of PlayedMove (memento plus timestamp).
  • ChessGame — the aggregate root: two Players, one Board, the GameStatus, and the lock.

Multiplicities: game 1 -> 1 board, game 1 -> 2 players, board 1 -> 0..32 pieces (shared), history 1 -> * played moves, played move 1 -> 1 record.

Class diagram

Structure: the piece hierarchy and the board that shares it.

classDiagram
    class Piece {
        <<abstract>>
        +color: Color
        +piece_type: PieceType
        +candidate_moves(board, origin) List~Move~
        +attacks(board, origin, target) bool
        #target_squares(board, origin) Iterator~Square~
        #moves_to(board, origin, target) Iterator~Move~
        #extra_moves(board, origin) Iterator~Move~
    }
    class SlidingPiece {
        +directions: tuple
    }
    class SteppingPiece {
        +offsets: tuple
    }
    class Queen
    class Rook
    class Bishop
    class Knight
    class King {
        #extra_moves(board, origin) Iterator~Move~
    }
    class Pawn {
        +attacks(board, origin, target) bool
    }
    class PieceFactory {
        +create(color, piece_type) Piece
        +from_symbol(symbol) Piece
    }
    class Board {
        +side_to_move: Color
        +castling: CastlingRights
        +en_passant: Square
        +legal_moves(color) List~Move~
        +apply(move) MoveRecord
        +undo(record) None
        +is_attacked(square, by) bool
    }
    class Move
    Piece <|-- SlidingPiece
    Piece <|-- SteppingPiece
    Piece <|-- Pawn
    SlidingPiece <|-- Queen
    SlidingPiece <|-- Rook
    SlidingPiece <|-- Bishop
    SteppingPiece <|-- Knight
    SteppingPiece <|-- King
    PieceFactory ..> Piece : interns 12
    Board o-- "0..32" Piece : shares
    Board ..> Move : generates

Behaviour: the game, the validator and the memento chain that makes undo exact.

classDiagram
    class ChessGame {
        +id: str
        +status: GameStatus
        +winner: Color
        -lock: RLock
        +play(text) PlayedMove
        +make_move(origin, target, promotion) PlayedMove
        +undo() PlayedMove
        +legal_moves() List~Move~
        +resign(color) None
        +agree_draw() None
    }
    class MoveValidator {
        +validate(board, origin, target, promotion) Move
    }
    class MoveHistory {
        +push(record, played_at) PlayedMove
        +pop() PlayedMove
        +notation() str
    }
    class PlayedMove {
        +record: MoveRecord
        +played_at: float
    }
    class MoveRecord {
        +move: Move
        +moved: Piece
        +captured: Piece
        +previous_castling: CastlingRights
        +previous_en_passant: Square
    }
    class Move {
        +origin: Square
        +target: Square
        +kind: MoveKind
        +promotion: PieceType
    }
    class Square {
        +file: int
        +rank: int
        +shifted(files, ranks) Square
    }
    class CastlingRights {
        +allows(color, king_side) bool
        +revoked(color, king_side) CastlingRights
    }
    class Player {
        +name: str
        +color: Color
    }
    class Board
    ChessGame *-- Board
    ChessGame *-- MoveHistory
    ChessGame --> MoveValidator
    ChessGame o-- "2" Player
    MoveHistory "1" *-- "many" PlayedMove
    PlayedMove --> MoveRecord
    MoveRecord --> Move
    MoveRecord --> CastlingRights
    Move --> "2" Square
    MoveValidator ..> Board : simulates

Design patterns applied

Pattern Where Why it earns its place
Template Method Piece.candidate_moves with the _target_squares, _moves_to and _extra_moves hooks The skeleton ("reach squares, drop friendly occupants, wrap in moves") is written once. A new piece supplies geometry only; the board never learns its name.
Polymorphism over conditionals SlidingPiece.directions, SteppingPiece.offsets The queen is four lines. Adding a fairy piece is a class, not an elif in a 200-line function — this is the single loudest signal in this problem.
Flyweight PieceFactory interning 12 instances Pieces carry no square and no has_moved flag, so they can be shared. That constraint is what forces castling rights onto the board, where they belong.
Memento MoveRecord produced by Board.apply, consumed by Board.undo Legality checking undoes thousands of moves per game. The memento makes undo exact and O(1), and the same object powers user-facing take-backs.
Command Move as a value object with a kind The board switches on kind, not on piece type, and a move can be logged, queued or sent over a socket.
Factory Method Board.standard, Board.from_placement, PieceFactory.from_symbol Setup is a named constructor, and tests build a five-piece position in one line instead of playing twenty moves to reach it.
State (lightweight) GameStatus with guarded transitions in ChessGame Six statuses with a single is_over predicate. Full State classes would add six classes and buy nothing.

What was deliberately not used: a Strategy for move generation. It is tempting to inject a MoveRule per piece type, but the rule and the piece are the same concept here — one object, not two. Also no bitboards: they are the right answer for an engine that searches millions of positions and the wrong answer for a 45-minute interview, and saying that out loud is better than either writing them or ignoring them.

Key flows

One move: validate by simulation, apply, then classify the position it produced.

sequenceDiagram
    autonumber
    actor U as Player
    participant G as ChessGame
    participant V as MoveValidator
    participant B as Board
    participant P as Piece
    participant H as MoveHistory
    U->>G: play("h5f7")
    G->>G: acquire lock, reject if the game is over
    G->>V: validate(board, h5, f7)
    V->>B: pseudo_legal_moves(white)
    B->>P: candidate_moves(board, origin)
    P-->>B: geometric moves
    B-->>V: candidates for h5 to f7
    V->>B: apply(move)
    V->>B: in_check(white)?
    alt own king exposed
        B-->>V: True
        V->>B: undo(record)
        V-->>G: IllegalMoveError
        G-->>U: rejected, board untouched
    else king safe
        B-->>V: False
        V->>B: undo(record)
        V-->>G: Move
        G->>B: apply(move)
        G->>H: push(record, now)
        G->>B: legal_moves(black)
        B-->>G: empty and black is in check
        G-->>U: PlayedMove, status CHECKMATE
    end

Status lifecycle. CHECK is not a terminal state, it is a label on an active position; CHECKMATE and STALEMATE are decided by the same question ("does the side to move have a legal move?") and separated by one more ("is the king attacked?").

stateDiagram-v2
    [*] --> ACTIVE : pieces set up
    ACTIVE --> ACTIVE : quiet move
    ACTIVE --> CHECK : move gives check
    CHECK --> ACTIVE : check answered
    ACTIVE --> STALEMATE : no legal move and not in check
    CHECK --> CHECKMATE : no legal move
    ACTIVE --> RESIGNED : resign
    CHECK --> RESIGNED : resign
    ACTIVE --> DRAW : draw agreed
    CHECKMATE --> ACTIVE : undo the mating move
    STALEMATE --> ACTIVE : undo
    CHECKMATE --> [*]
    STALEMATE --> [*]
    DRAW --> [*]
    RESIGNED --> [*]

Implementation

Write it in this order: the vocabulary, the pieces, the board, then the services. Nothing below is pseudocode — it is the module the tests run.

The enums are the vocabulary. MoveKind is the one that pays: it names exactly the three moves that are not "pick the piece up and put it down", so the board can handle them without asking what piece moved.

code/lld/chess/models.py — enums
class Color(StrEnum):
    WHITE = "white"
    BLACK = "black"

    @property
    def opponent(self) -> Color:
        return Color.BLACK if self is Color.WHITE else Color.WHITE


class PieceType(StrEnum):
    KING = "king"
    QUEEN = "queen"
    ROOK = "rook"
    BISHOP = "bishop"
    KNIGHT = "knight"
    PAWN = "pawn"


class MoveKind(StrEnum):
    """What the board has to do beyond "pick the piece up and put it down"."""

    NORMAL = "normal"
    DOUBLE_PUSH = "double_push"  # sets the en-passant target square
    EN_PASSANT = "en_passant"  # captures a pawn that is not on the target square
    CASTLE_KING_SIDE = "castle_king_side"  # moves the rook too
    CASTLE_QUEEN_SIDE = "castle_queen_side"


class GameStatus(StrEnum):
    ACTIVE = "active"
    CHECK = "check"
    CHECKMATE = "checkmate"
    STALEMATE = "stalemate"
    DRAW = "draw"
    RESIGNED = "resigned"

    @property
    def is_over(self) -> bool:
        return self in (
            GameStatus.CHECKMATE,
            GameStatus.STALEMATE,
            GameStatus.DRAW,
            GameStatus.RESIGNED,
        )


PROMOTION_LETTERS: dict[PieceType, str] = {
    PieceType.QUEEN: "q",
    PieceType.ROOK: "r",
    PieceType.BISHOP: "b",
    PieceType.KNIGHT: "n",
}
PROMOTION_CHOICES: tuple[PieceType, ...] = tuple(PROMOTION_LETTERS)
code/lld/chess/models.py — errors
class IllegalMoveError(ValidationError):
    """The move breaks a rule: wrong geometry, blocked path, or it leaves your king in check."""


class NotYourTurnError(ConflictError):
    """The piece belongs to the other side, or the other side is to move."""


class GameOverError(InvalidStateError):
    """The game already ended; no further moves, resignations or draws are accepted."""


class NothingToUndoError(NotFoundError):
    """Undo was asked for on an empty move history."""

The value objects. Square.shifted returning None off the board is a small decision with a large payoff: every generator below is a loop with no bounds arithmetic in it. MoveRecord is the memento — note the two fields candidates forget, captured and previous_castling.

code/lld/chess/models.py — value objects
@dataclass(frozen=True, slots=True, order=True)
class Square:
    """A board coordinate. ``file`` is a-h as 0-7, ``rank`` is 1-8 as 0-7."""

    file: int
    rank: int

    def __post_init__(self) -> None:
        if not (0 <= self.file <= 7 and 0 <= self.rank <= 7):
            raise ValidationError(f"square off the board: file={self.file} rank={self.rank}")

    @classmethod
    def of(cls, name: str) -> Square:
        text = name.strip().lower()
        if len(text) != 2 or text[0] not in FILES or text[1] not in RANKS:
            raise ValidationError(f"not a square name: {name!r}")
        return cls(FILES.index(text[0]), RANKS.index(text[1]))

    @property
    def name(self) -> str:
        return f"{FILES[self.file]}{RANKS[self.rank]}"

    def shifted(self, files: int, ranks: int) -> Square | None:
        """The square this many steps away, or ``None`` when that falls off the board."""
        file, rank = self.file + files, self.rank + ranks
        return Square(file, rank) if 0 <= file <= 7 and 0 <= rank <= 7 else None

    def __str__(self) -> str:
        return self.name


@dataclass(frozen=True, slots=True)
class Move:
    """A Command object: what to do, not how. ``kind`` carries the three special cases."""

    origin: Square
    target: Square
    kind: MoveKind = MoveKind.NORMAL
    promotion: PieceType | None = None

    @property
    def is_castle(self) -> bool:
        return self.kind in (MoveKind.CASTLE_KING_SIDE, MoveKind.CASTLE_QUEEN_SIDE)

    def __str__(self) -> str:
        return f"{self.origin}{self.target}{PROMOTION_LETTERS[self.promotion] if self.promotion else ''}"


@dataclass(frozen=True, slots=True)
class CastlingRights:
    """Four booleans that only ever go from True to False within a game."""

    white_king_side: bool = True
    white_queen_side: bool = True
    black_king_side: bool = True
    black_queen_side: bool = True

    @staticmethod
    def _field(color: Color, king_side: bool) -> str:
        return f"{color.value}_{'king' if king_side else 'queen'}_side"

    def allows(self, color: Color, king_side: bool) -> bool:
        return bool(getattr(self, self._field(color, king_side)))

    def revoked(self, color: Color, king_side: bool | None = None) -> CastlingRights:
        """A new value with one side (or both, when ``king_side`` is None) switched off."""
        sides = (True, False) if king_side is None else (king_side,)
        return replace(self, **{self._field(color, side): False for side in sides})

    def __str__(self) -> str:
        flags = "".join(
            letter
            for letter, on in zip(
                "KQkq",
                (
                    self.white_king_side,
                    self.white_queen_side,
                    self.black_king_side,
                    self.black_queen_side,
                ),
                strict=True,
            )
            if on
        )
        return flags or "-"


@dataclass(frozen=True, slots=True)
class MoveRecord:
    """Memento. Everything ``Board.undo`` needs to restore the position exactly.

    The captured piece and the previous castling rights are the two fields
    candidates forget; without them undo silently corrupts the game.
    """

    move: Move
    moved: Piece
    captured: Piece | None
    captured_square: Square | None
    previous_castling: CastlingRights
    previous_en_passant: Square | None
    previous_halfmove_clock: int


@dataclass(frozen=True, slots=True)
class Player:
    name: str
    color: Color


@dataclass(frozen=True, slots=True)
class PlayedMove:
    """One entry in the move history: the memento plus when it was played."""

    record: MoveRecord
    played_at: float

    @property
    def move(self) -> Move:
        return self.record.move

    @property
    def color(self) -> Color:
        return self.record.moved.color

    def __str__(self) -> str:
        return str(self.record.move)


def parse_move_text(text: str) -> tuple[Square, Square, PieceType | None]:
    """Coordinate notation: ``"e2e4"``, or ``"a7a8q"`` for a promotion."""
    cleaned = text.strip().lower().replace("-", "")
    if len(cleaned) not in (4, 5):
        raise ValidationError(f"not a move: {text!r} (expected e2e4 or a7a8q)")
    promotion: PieceType | None = None
    if len(cleaned) == 5:
        letters = {letter: piece for piece, letter in PROMOTION_LETTERS.items()}
        if cleaned[4] not in letters:
            raise ValidationError(f"cannot promote to {cleaned[4]!r}; use one of qrbn")
        promotion = letters[cleaned[4]]
    return Square.of(cleaned[:2]), Square.of(cleaned[2:4]), promotion

Now the piece hierarchy, and the Template Method that makes it work. candidate_moves is written once; subclasses fill three hooks. Read attacks carefully: it is not "is the target in my move list", because castling asks whether a square is attacked, and asking the king for its moves would recurse forever.

code/lld/chess/pieces.py — the template
class BoardView(Protocol):
    """All a piece is allowed to know about the position while generating moves."""

    castling: CastlingRights
    en_passant: Square | None

    def piece_at(self, square: Square) -> Piece | None: ...

    def is_attacked(self, square: Square, by: Color) -> bool: ...


class Piece(ABC):
    """Immutable and shared. ``candidate_moves`` is the Template Method."""

    __slots__ = ("color",)

    piece_type: ClassVar[PieceType]
    letter: ClassVar[str]

    def __init__(self, color: Color) -> None:
        self.color = color

    def candidate_moves(self, board: BoardView, origin: Square) -> list[Move]:
        """Pseudo-legal moves: correct geometry, but they may leave the king in check."""
        moves: list[Move] = []
        for target in self._target_squares(board, origin):
            occupant = board.piece_at(target)
            if occupant is not None and occupant.color is self.color:
                continue
            moves.extend(self._moves_to(board, origin, target))
        moves.extend(self._extra_moves(board, origin))
        return moves

    def attacks(self, board: BoardView, origin: Square, target: Square) -> bool:
        """Does this piece hit ``target`` from ``origin``? Used by the check test.

        Deliberately not ``target in candidate_moves``: castling calls ``is_attacked``,
        so asking the king for its moves here would recurse forever.
        """
        return any(square == target for square in self._target_squares(board, origin))

    @abstractmethod
    def _target_squares(self, board: BoardView, origin: Square) -> Iterator[Square]:
        """Squares this piece reaches, ignoring whose piece stands there."""

    def _moves_to(self, board: BoardView, origin: Square, target: Square) -> Iterator[Move]:
        yield Move(origin, target)

    def _extra_moves(self, board: BoardView, origin: Square) -> Iterator[Move]:
        return iter(())

    @property
    def symbol(self) -> str:
        return self.letter.upper() if self.color is Color.WHITE else self.letter.lower()

    def __repr__(self) -> str:
        return f"{type(self).__name__}({self.color.value})"


class SlidingPiece(Piece):
    """Queen, rook, bishop: walk each ray until something blocks it."""

    __slots__ = ()

    directions: ClassVar[tuple[tuple[int, int], ...]]

    def _target_squares(self, board: BoardView, origin: Square) -> Iterator[Square]:
        for files, ranks in self.directions:
            square = origin.shifted(files, ranks)
            while square is not None:
                yield square
                if board.piece_at(square) is not None:
                    break  # the blocker itself is a target; anything behind it is not
                square = square.shifted(files, ranks)


class SteppingPiece(Piece):
    """Knight and king: a fixed set of one-shot offsets."""

    __slots__ = ()

    offsets: ClassVar[tuple[tuple[int, int], ...]]

    def _target_squares(self, board: BoardView, origin: Square) -> Iterator[Square]:
        for files, ranks in self.offsets:
            square = origin.shifted(files, ranks)
            if square is not None:
                yield square

The six pieces are now tiny. The king owns castling in _extra_moves (the only place is_attacked is consulted during generation), and the pawn owns promotion, the double push and en passant in _moves_to.

code/lld/chess/pieces.py — the six pieces
class Queen(SlidingPiece):
    __slots__ = ()
    piece_type = PieceType.QUEEN
    letter = "Q"
    directions = ORTHOGONALS + DIAGONALS


class Rook(SlidingPiece):
    __slots__ = ()
    piece_type = PieceType.ROOK
    letter = "R"
    directions = ORTHOGONALS


class Bishop(SlidingPiece):
    __slots__ = ()
    piece_type = PieceType.BISHOP
    letter = "B"
    directions = DIAGONALS


class Knight(SteppingPiece):
    __slots__ = ()
    piece_type = PieceType.KNIGHT
    letter = "N"
    offsets = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2))


class King(SteppingPiece):
    """The only piece with a move that is not "go to a reachable square"."""

    __slots__ = ()
    piece_type = PieceType.KING
    letter = "K"
    offsets = ORTHOGONALS + DIAGONALS

    # (king side, kind, files that must be empty, files the king crosses, landing file)
    _CASTLE_PLANS: ClassVar[tuple[tuple[bool, MoveKind, tuple[int, ...], tuple[int, ...], int], ...]] = (
        (True, MoveKind.CASTLE_KING_SIDE, (5, 6), (5, 6), 6),
        (False, MoveKind.CASTLE_QUEEN_SIDE, (1, 2, 3), (3, 2), 2),
    )

    def _extra_moves(self, board: BoardView, origin: Square) -> Iterator[Move]:
        rank = 0 if self.color is Color.WHITE else 7
        if origin != Square(4, rank) or board.is_attacked(origin, self.color.opponent):
            return  # you may not castle out of check
        for king_side, kind, empty_files, crossed_files, landing in self._CASTLE_PLANS:
            if not board.castling.allows(self.color, king_side):
                continue
            rook = board.piece_at(Square(7 if king_side else 0, rank))
            if rook is None or rook.piece_type is not PieceType.ROOK or rook.color is not self.color:
                continue
            if any(board.piece_at(Square(file, rank)) is not None for file in empty_files):
                continue
            if any(
                board.is_attacked(Square(file, rank), self.color.opponent)
                for file in crossed_files
            ):
                continue  # you may not castle through or into check
            yield Move(origin, Square(landing, rank), kind)


class Pawn(Piece):
    """Pushes forward, captures sideways, and is the only piece that becomes another."""

    __slots__ = ()
    piece_type = PieceType.PAWN
    letter = "P"

    @property
    def _forward(self) -> int:
        return 1 if self.color is Color.WHITE else -1

    @property
    def _start_rank(self) -> int:
        return 1 if self.color is Color.WHITE else 6

    @property
    def _last_rank(self) -> int:
        return 7 if self.color is Color.WHITE else 0

    def _target_squares(self, board: BoardView, origin: Square) -> Iterator[Square]:
        step = origin.shifted(0, self._forward)
        if step is not None and board.piece_at(step) is None:
            yield step
            double = origin.shifted(0, 2 * self._forward)
            if origin.rank == self._start_rank and double is not None and board.piece_at(double) is None:
                yield double
        for square in self._capture_squares(origin):
            if board.piece_at(square) is not None or square == board.en_passant:
                yield square

    def _capture_squares(self, origin: Square) -> Iterator[Square]:
        for files in (-1, 1):
            square = origin.shifted(files, self._forward)
            if square is not None:
                yield square

    def attacks(self, board: BoardView, origin: Square, target: Square) -> bool:
        # A pawn does not attack the square in front of it, so the generic
        # "reachable == attacked" rule would wrongly forbid a king from stepping there.
        return any(square == target for square in self._capture_squares(origin))

    def _moves_to(self, board: BoardView, origin: Square, target: Square) -> Iterator[Move]:
        if target.rank == self._last_rank:
            for promotion in PROMOTION_CHOICES:
                yield Move(origin, target, MoveKind.NORMAL, promotion)
        elif abs(target.rank - origin.rank) == 2:
            yield Move(origin, target, MoveKind.DOUBLE_PUSH)
        elif target.file != origin.file and board.piece_at(target) is None:
            yield Move(origin, target, MoveKind.EN_PASSANT)
        else:
            yield Move(origin, target)

The factory interns the twelve instances at import time. Because a piece has no has_moved flag, sharing is safe — and that is precisely why castling rights are board state.

code/lld/chess/pieces.py — flyweight factory
_PIECE_CLASSES: dict[PieceType, type[Piece]] = {
    PieceType.KING: King,
    PieceType.QUEEN: Queen,
    PieceType.ROOK: Rook,
    PieceType.BISHOP: Bishop,
    PieceType.KNIGHT: Knight,
    PieceType.PAWN: Pawn,
}
_LETTERS: dict[str, PieceType] = {klass.letter: kind for kind, klass in _PIECE_CLASSES.items()}
# Flyweight pool, interned once at import: 2 colours x 6 types = 12 objects, forever.
_INTERNED: dict[tuple[Color, PieceType], Piece] = {
    (color, kind): klass(color) for kind, klass in _PIECE_CLASSES.items() for color in Color
}


class PieceFactory:
    """Factory + Flyweight: every ``e2`` pawn on every board is the same object."""

    @staticmethod
    def create(color: Color, piece_type: PieceType) -> Piece:
        return _INTERNED[(color, piece_type)]

    @staticmethod
    def from_symbol(symbol: str) -> Piece:
        """``"K"`` is a white king, ``"k"`` a black one - the usual FEN letters."""
        try:
            piece_type = _LETTERS[symbol.upper()]
        except KeyError:
            raise ValidationError(f"unknown piece symbol {symbol!r}") from None
        return PieceFactory.create(Color.WHITE if symbol.isupper() else Color.BLACK, piece_type)

The board is the memento originator. apply returns everything undo needs; legal_moves is the pin rule, and it is the method the interviewer is waiting for.

code/lld/chess/board.py
class Board:
    """Squares plus the four pieces of state a position needs beyond piece placement."""

    __slots__ = ("_squares", "side_to_move", "castling", "en_passant", "halfmove_clock")

    # A rook standing here means the matching castling right may still be alive.
    _ROOK_HOMES: ClassVar[dict[Square, tuple[Color, bool]]] = {
        Square(0, 0): (Color.WHITE, False),
        Square(7, 0): (Color.WHITE, True),
        Square(0, 7): (Color.BLACK, False),
        Square(7, 7): (Color.BLACK, True),
    }

    def __init__(
        self,
        squares: Mapping[Square, Piece],
        side_to_move: Color = Color.WHITE,
        castling: CastlingRights | None = None,
        en_passant: Square | None = None,
        halfmove_clock: int = 0,
    ) -> None:
        self._squares: dict[Square, Piece] = dict(squares)
        self.side_to_move = side_to_move
        self.castling = castling if castling is not None else CastlingRights()
        self.en_passant = en_passant
        self.halfmove_clock = halfmove_clock

    @classmethod
    def standard(cls) -> Board:
        """Factory: the opening position, built from the flyweight pool."""
        squares: dict[Square, Piece] = {}
        for file, piece_type in enumerate(BACK_RANK):
            squares[Square(file, 0)] = PieceFactory.create(Color.WHITE, piece_type)
            squares[Square(file, 7)] = PieceFactory.create(Color.BLACK, piece_type)
            squares[Square(file, 1)] = PieceFactory.create(Color.WHITE, PieceType.PAWN)
            squares[Square(file, 6)] = PieceFactory.create(Color.BLACK, PieceType.PAWN)
        return cls(squares)

    @classmethod
    def from_placement(
        cls,
        placement: Mapping[str, str],
        side_to_move: Color = Color.WHITE,
        castling: CastlingRights | None = None,
        en_passant: str | None = None,
    ) -> Board:
        """``Board.from_placement({"e1": "K", "e8": "k", "a7": "P"})`` - for tests and puzzles."""
        squares = {Square.of(name): PieceFactory.from_symbol(sym) for name, sym in placement.items()}
        return cls(
            squares,
            side_to_move,
            castling if castling is not None else CastlingRights(False, False, False, False),
            Square.of(en_passant) if en_passant else None,
        )

    # -- reading the position ---------------------------------------------------------
    def piece_at(self, square: Square) -> Piece | None:
        return self._squares.get(square)

    def occupied(self) -> list[tuple[Square, Piece]]:
        return sorted(self._squares.items())

    def pieces_of(self, color: Color) -> list[tuple[Square, Piece]]:
        return [(square, piece) for square, piece in self._squares.items() if piece.color is color]

    def king_square(self, color: Color) -> Square:
        for square, piece in self._squares.items():
            if piece.piece_type is PieceType.KING and piece.color is color:
                return square
        raise NotFoundError(f"no {color} king on the board")

    def is_attacked(self, square: Square, by: Color) -> bool:
        """Ask every enemy piece whether it hits this square. O(pieces), no recursion."""
        return any(piece.attacks(self, origin, square) for origin, piece in self.pieces_of(by))

    def in_check(self, color: Color) -> bool:
        return self.is_attacked(self.king_square(color), color.opponent)

    # -- generating moves -------------------------------------------------------------
    def pseudo_legal_moves(self, color: Color) -> list[Move]:
        moves: list[Move] = []
        for origin, piece in self.pieces_of(color):
            moves.extend(piece.candidate_moves(self, origin))
        return moves

    def legal_moves(self, color: Color | None = None) -> list[Move]:
        """Pseudo-legal moves minus the ones that leave your own king in check.

        This is the pin rule, and it is why the board must be *simulated*: there is no
        cheap static test that catches a knight pinned against its king.
        """
        color = color if color is not None else self.side_to_move
        legal: list[Move] = []
        for move in self.pseudo_legal_moves(color):
            record = self.apply(move)
            if not self.in_check(color):
                legal.append(move)
            self.undo(record)
        return legal

    # -- mutating the position --------------------------------------------------------
    def apply(self, move: Move) -> MoveRecord:
        """Play the move and return the memento that undoes it."""
        piece = self._squares.get(move.origin)
        if piece is None:
            raise IllegalMoveError(f"no piece on {move.origin}")
        captured_square = move.target
        if move.kind is MoveKind.EN_PASSANT:
            captured_square = Square(move.target.file, move.origin.rank)
        captured = self._squares.pop(captured_square, None)
        record = MoveRecord(
            move=move,
            moved=piece,
            captured=captured,
            captured_square=captured_square if captured is not None else None,
            previous_castling=self.castling,
            previous_en_passant=self.en_passant,
            previous_halfmove_clock=self.halfmove_clock,
        )
        del self._squares[move.origin]
        landing = piece if move.promotion is None else PieceFactory.create(piece.color, move.promotion)
        self._squares[move.target] = landing
        if move.is_castle:
            rook_from, rook_to = self._rook_squares(move)
            self._squares[rook_to] = self._squares.pop(rook_from)
        self.castling = self._castling_after(move, piece, captured, captured_square)
        self.en_passant = (
            Square(move.origin.file, (move.origin.rank + move.target.rank) // 2)
            if move.kind is MoveKind.DOUBLE_PUSH
            else None
        )
        reset = captured is not None or piece.piece_type is PieceType.PAWN
        self.halfmove_clock = 0 if reset else self.halfmove_clock + 1
        self.side_to_move = piece.color.opponent
        return record

    def undo(self, record: MoveRecord) -> None:
        """Restore the position the memento came from - captures and rights included."""
        move = record.move
        self._squares.pop(move.target, None)
        self._squares[move.origin] = record.moved
        if record.captured is not None and record.captured_square is not None:
            self._squares[record.captured_square] = record.captured
        if move.is_castle:
            rook_from, rook_to = self._rook_squares(move)
            self._squares[rook_from] = self._squares.pop(rook_to)
        self.castling = record.previous_castling
        self.en_passant = record.previous_en_passant
        self.halfmove_clock = record.previous_halfmove_clock
        self.side_to_move = record.moved.color

    def _castling_after(
        self, move: Move, piece: Piece, captured: Piece | None, captured_square: Square
    ) -> CastlingRights:
        rights = self.castling
        if piece.piece_type is PieceType.KING:
            rights = rights.revoked(piece.color)
        elif piece.piece_type is PieceType.ROOK and move.origin in self._ROOK_HOMES:
            color, king_side = self._ROOK_HOMES[move.origin]
            if color is piece.color:
                rights = rights.revoked(color, king_side)
        if captured is not None and captured.piece_type is PieceType.ROOK:
            home = self._ROOK_HOMES.get(captured_square)
            if home is not None and home[0] is captured.color:
                rights = rights.revoked(home[0], home[1])
        return rights

    @staticmethod
    def _rook_squares(move: Move) -> tuple[Square, Square]:
        rank = move.origin.rank
        if move.kind is MoveKind.CASTLE_KING_SIDE:
            return Square(7, rank), Square(5, rank)
        return Square(0, rank), Square(3, rank)

    def row(self, rank: int) -> str:
        """One rank as eight characters, ``"."`` for an empty square."""
        cells = (self._squares.get(Square(file, rank)) for file in range(8))
        return "".join(cell.symbol if cell else "." for cell in cells)

    def render(self) -> str:
        return "\n".join([f"{rank + 1} {self.row(rank)}" for rank in range(7, -1, -1)] + ["  abcdefgh"])

The validator exists so that "illegal" comes with a reason. Its last block is the crux of the whole problem: apply, ask, take back.

code/lld/chess/services.py — validator
class MoveValidator:
    """Turns a raw (from, to) request into a legal ``Move`` or an error that names the reason.

    The last block is the one interviews are really about: a move can be geometrically
    perfect and still illegal because your own king ends up in check. There is no way to
    know without playing it, so the validator applies the move, asks, and takes it back.
    """

    def validate(
        self, board: Board, origin: Square, target: Square, promotion: PieceType | None = None
    ) -> Move:
        piece = board.piece_at(origin)
        if piece is None:
            raise IllegalMoveError(f"no piece on {origin}")
        if piece.color is not board.side_to_move:
            raise NotYourTurnError(
                f"{origin} holds a {piece.color} {piece.piece_type}; it is {board.side_to_move} to move"
            )
        candidates = [
            move
            for move in board.pseudo_legal_moves(piece.color)
            if move.origin == origin and move.target == target
        ]
        if not candidates:
            raise IllegalMoveError(f"a {piece.color} {piece.piece_type} cannot move {origin} to {target}")
        if candidates[0].promotion is not None:
            if promotion is None:
                raise IllegalMoveError(f"promotion on {target} needs a choice, e.g. {origin}{target}q")
            candidates = [move for move in candidates if move.promotion is promotion]
            if not candidates:
                raise IllegalMoveError(f"a pawn cannot promote to a {promotion}")
        move = candidates[0]

        record = board.apply(move)
        exposed = board.in_check(piece.color)
        board.undo(record)
        if exposed:
            raise IllegalMoveError(f"{move} leaves the {piece.color} king in check")
        return move

The history is a plain caretaker; it stores mementos and never looks inside one.

code/lld/chess/services.py — history
class MoveHistory:
    """Caretaker: it stores mementos and never looks inside them."""

    def __init__(self) -> None:
        self._entries: list[PlayedMove] = []

    def push(self, record: MoveRecord, played_at: float) -> PlayedMove:
        entry = PlayedMove(record=record, played_at=played_at)
        self._entries.append(entry)
        return entry

    def pop(self) -> PlayedMove:
        if not self._entries:
            raise NothingToUndoError("no move to undo")
        return self._entries.pop()

    def entries(self) -> list[PlayedMove]:
        return list(self._entries)

    def notation(self) -> str:
        """``"1. e2e4 e7e5 2. f1c4"`` - coordinate notation, one number per full move."""
        parts: list[str] = []
        for index, entry in enumerate(self._entries):
            if index % 2 == 0:
                parts.append(f"{index // 2 + 1}.")
            parts.append(str(entry))
        return " ".join(parts)

    def __len__(self) -> int:
        return len(self._entries)

The game ties it together: one lock, one status machine, and a _refresh_status that runs after both make_move and undo so there is exactly one place where the result is decided.

code/lld/chess/services.py — game
class ChessGame:
    """Aggregate root. One lock guards the board, the status and the history together.

    Move generation *mutates* the board (apply, ask, undo), so even ``legal_moves`` is a
    write as far as locking is concerned. That is the single most important sentence in
    this class: two threads reading moves at the same time would corrupt the position.
    """

    def __init__(
        self,
        white: Player,
        black: Player,
        board: Board | None = None,
        validator: MoveValidator | None = None,
        clock: Clock | None = None,
        ids: IdGenerator | None = None,
    ) -> None:
        if white.color is not Color.WHITE or black.color is not Color.BLACK:
            raise ValidationError("white must play white and black must play black")
        self.id = (ids or SequentialIdGenerator("G")).next_id()
        self.players: dict[Color, Player] = {Color.WHITE: white, Color.BLACK: black}
        self._board = board if board is not None else Board.standard()
        self._validator = validator or MoveValidator()
        self._clock = clock or SystemClock()
        self._history = MoveHistory()
        self._lock = threading.RLock()
        self.status = GameStatus.ACTIVE
        self.winner: Color | None = None
        self.started_at = self._clock.now()
        self._refresh_status(self._board.side_to_move.opponent)

    @property
    def board(self) -> Board:
        return self._board

    @property
    def history(self) -> MoveHistory:
        return self._history

    @property
    def side_to_move(self) -> Color:
        with self._lock:
            return self._board.side_to_move

    def legal_moves(self) -> list[Move]:
        with self._lock:
            return self._board.legal_moves(self._board.side_to_move)

    def play(self, text: str) -> PlayedMove:
        """``game.play("e2e4")`` / ``game.play("a7a8q")``."""
        origin, target, promotion = parse_move_text(text)
        return self.make_move(origin, target, promotion)

    def make_move(
        self, origin: Square, target: Square, promotion: PieceType | None = None
    ) -> PlayedMove:
        with self._lock:
            if self.status.is_over:
                raise GameOverError(f"game {self.id} is over: {self.status}")
            mover = self._board.side_to_move
            move = self._validator.validate(self._board, origin, target, promotion)
            record = self._board.apply(move)
            played = self._history.push(record, self._clock.now())
            self._refresh_status(mover)
            return played

    def undo(self) -> PlayedMove:
        """Take back the last move, captured piece and castling rights included."""
        with self._lock:
            if self.status in (GameStatus.RESIGNED, GameStatus.DRAW):
                raise GameOverError(f"game {self.id} ended by agreement; undo would rewrite the result")
            played = self._history.pop()
            self._board.undo(played.record)
            self._refresh_status(self._board.side_to_move.opponent)
            return played

    def resign(self, color: Color) -> None:
        with self._lock:
            self._require_running()
            self.status = GameStatus.RESIGNED
            self.winner = color.opponent

    def agree_draw(self) -> None:
        with self._lock:
            self._require_running()
            self.status = GameStatus.DRAW
            self.winner = None

    def result(self) -> str:
        with self._lock:
            if self.status is GameStatus.CHECKMATE and self.winner is not None:
                return f"{self.players[self.winner].name} wins by checkmate"
            if self.status is GameStatus.RESIGNED and self.winner is not None:
                return f"{self.players[self.winner].name} wins by resignation"
            if self.status is GameStatus.STALEMATE:
                return "draw by stalemate"
            if self.status is GameStatus.DRAW:
                return "draw by agreement"
            return f"in progress ({self.status})"

    def _require_running(self) -> None:
        if self.status.is_over:
            raise GameOverError(f"game {self.id} is over: {self.status}")

    def _refresh_status(self, mover: Color) -> None:
        """Recompute the status of the position ``mover`` just created (or just undid)."""
        opponent = mover.opponent
        in_check = self._board.in_check(opponent)
        if not self._board.legal_moves(opponent):
            self.status = GameStatus.CHECKMATE if in_check else GameStatus.STALEMATE
            self.winner = mover if in_check else None
        else:
            self.status = GameStatus.CHECK if in_check else GameStatus.ACTIVE
            self.winner = None

python -m lld.chess.demo plays Scholar's mate, takes it back, and then shows a pin, a castle and a promotion on hand-built positions:

G-1: white has 20 legal moves in the opening position
1. white e2e4 -> active
1. black e7e5 -> active
2. white f1c4 -> active
2. black b8c6 -> active
3. white d1h5 -> active
3. black g8f6 -> active
4. white h5f7 -> checkmate
Ada wins by checkmate; black has 0 legal moves
undo h5f7 -> active, f7 holds a black pawn again
G-2: e4d6 leaves the white king in check
G-3: e1g1 castles -> rank 1 is now .....RK.
G-4: a7a8q -> white queen on a8, check
G-4: draw by agreement
32 pieces on the board share 12 Piece objects

Concurrency and edge cases

Which lock protects what. ChessGame._lock is a single RLock guarding the board, the status and the history as one unit. The sentence that impresses is why it also guards reads: legal_moves applies and undoes every candidate, so move generation mutates the board. Two threads calling game.legal_moves() at the same time on an unlocked board would interleave an apply from one with an undo from the other and leave pieces on the wrong squares. In this design there is no such thing as a read-only query of the position. The alternatives are to copy the board per query (allocation-heavy, and copying is what the memento exists to avoid) or to make generation non-mutating with an incremental attack map — real engines do the latter; say so and move on. It is an RLock rather than a Lock because make_move calls _refresh_status, which calls back into locked helpers.

The race it prevents. Two connections submitting moves for the same game: both read side_to_move == WHITE, both validate successfully, both apply. Without the lock you get two white moves in a row and a corrupted history. With it, the second call re-reads side_to_move inside the critical section, finds black, and raises NotYourTurnError. The concurrency test fires eight legal white openings at one game from eight threads and asserts exactly one lands.

Pinned pieces. There is no static test for a pin. A knight on e4 between a white king on e1 and a black rook on e8 has eight geometrically perfect moves and zero legal ones. The only correct answer is to play the move, ask in_check, and take it back — which is why apply/undo had to be cheap.

Undo correctness. Three things must come back: the captured piece (on d5, not d6, after an en-passant capture), the castling rights the move destroyed (capturing a rook on h1 kills white's king-side castle forever — undo must resurrect it), and the en-passant target square, which expires after exactly one move.

Move-generation cost. One legal_moves call in a middlegame position is roughly 30 candidates, each of which applies the move, scans up to 16 enemy pieces for an attack on the king, and undoes it: about 30 x 16 x 8 = 3.8k square reads. At the 100 ns main-memory reference from the estimation cheatsheet that is ~0.4 ms of memory traffic per sweep, and the interpreter multiplies it. Two consequences: cache legal_moves per position rather than micro-optimising the loop, and never call it inside another loop. By contrast the lock is free — an uncontended mutex is 17 ns, so one sweep costs about 0.4 ms / 17 ns ~ 20,000 lock acquisitions and guarding the whole game object costs nothing you can measure.

Other edge cases handled: promotion without a choice is rejected rather than defaulted; castling out of, through or into check is refused, as is castling when the rook was captured on its home square; a stalemated player is not "in check", so the result is a draw and winner stays None; undo after checkmate resumes the game, but undo after an agreed draw raises; moving an opponent's piece raises NotYourTurnError, which is a different error from IllegalMoveError because a UI treats the two differently.

Common mistake

Storing has_moved on the king and rook to decide castling. It looks natural and it breaks undo: after taking back a move you must know whether the flag was already set before it, so you end up storing the old value in the history anyway. Keep the four rights on the board as an immutable value, revoke them in apply, and restore them from the memento. The same mistake shows up as a Piece.position field — the moment a piece knows its square you can no longer share pieces, and both apply and undo have two sources of truth to keep in step.

Extensibility and follow-ups

  • Play against the machine: a Search class that calls game.legal_moves(), applies each move, recurses, and undoes. Minimax with alpha-beta pruning needs nothing new from this design — that is the payoff of a cheap apply/undo pair. The evaluation function is a Strategy.
  • Clocks: every PlayedMove already carries played_at from the injected Clock, so per-move durations are a subtraction; a TimeControl object holding two budgets decides flag-fall.
  • Standard algebraic notation: a formatter over MoveRecord — it needs the piece, the capture flag and disambiguation against the other legal moves, all of which the memento already holds. Parsing is the inverse and goes in front of MoveValidator.
  • Threefold repetition and the 50-move rule: hash the position (pieces, side to move, castling rights, en-passant square) after every move into a counter; the half-move clock is already tracked and reset on captures and pawn moves.
  • Online play: ChessGame is already the aggregate root behind one lock, so a socket handler calls play and broadcasts PlayedMove. Persistence is the move list — replay it to rebuild any position.
  • Variants: Chess960 changes only Board.standard and the castling target squares; a fairy piece is one subclass of SlidingPiece or SteppingPiece.

Interview tip

When you reach legality, say the sentence out loud before you write it: "I cannot decide this statically, so I will simulate the move and ask whether my king is attacked." Then write apply, undo and the four-line loop that uses them. Candidates who try to special-case pins with a "is this piece pinned?" helper spend ten minutes and get it wrong; candidates who simulate finish in three and get checkmate detection for free, because "no legal move" is the same loop.

Tests

tests/test_chess.py has 11 cases (18 with parametrisation). They are chosen so that each one fails for exactly one reason: the opening position has 20 legal moves per side (16 pawn moves plus 4 knight moves) and sets the en-passant square; Scholar's mate reaches CHECKMATE and then refuses further moves; a stalemate position is a draw with no winner; castling is checked five ways (both wings, missing rights, through check, blocked); promotion is parametrised over all four pieces and rejects a missing choice; en passant removes a pawn that is not on the target square, and undo puts it back.

The two worth walking through in the room are the pin and the undo:

code/lld/chess/tests/test_chess.py — the pin
def test_a_pinned_knight_cannot_move(clock: FakeClock) -> None:
    # Black rook on e8, white king on e1: the knight on e4 is the only thing between them.
    board = Board.from_placement({"e1": "K", "e4": "N", "e8": "r", "h8": "k"})
    game = make_game(clock, board)
    assert game.status is GameStatus.ACTIVE  # geometry says the knight has 8 moves
    with pytest.raises(IllegalMoveError, match="leaves the white king in check"):
        game.play("e4d6")
    assert all(move.origin != Square.of("e4") for move in game.legal_moves())
code/lld/chess/tests/test_chess.py — undo restores the capture and the right
def test_undo_restores_the_captured_rook_and_the_castling_right(clock: FakeClock) -> None:
    board = Board.from_placement(
        {"e1": "K", "h1": "R", "e8": "k", "h8": "r", "a1": "R"},
        side_to_move=Color.BLACK,
        castling=CastlingRights(True, True, True, True),
    )
    game = make_game(clock, board)
    game.play("h8h1")  # the black rook takes on h1 and kills white's king-side castle
    assert game.board.castling.allows(Color.WHITE, king_side=True) is False
    assert game.board.piece_at(Square.of("h1")).color is Color.BLACK

    game.undo()
    restored = game.board.piece_at(Square.of("h1"))
    assert restored is not None and restored.color is Color.WHITE
    assert game.board.castling.allows(Color.WHITE, king_side=True) is True
    assert game.side_to_move is Color.BLACK and len(game.history) == 0

The concurrency test asserts the turn invariant directly — eight threads, eight legal white openings, one winner:

code/lld/chess/tests/test_chess.py — concurrency
def test_only_one_of_many_racing_moves_is_played(clock: FakeClock) -> None:
    game = make_game(clock)
    openings = ["e2e4", "d2d4", "g1f3", "b1c3", "c2c4", "f2f4", "a2a3", "h2h3"]

    def try_move(text: str) -> str | None:
        try:
            return str(game.play(text))
        except (NotYourTurnError, IllegalMoveError, GameOverError):
            return None

    with ThreadPoolExecutor(max_workers=8) as pool:
        results = list(pool.map(try_move, openings))

    played = [text for text in results if text is not None]
    assert len(played) == 1 and played[0] in openings  # the lock serialises the turn
    assert len(game.history) == 1 and game.side_to_move is Color.BLACK

Run them with uv run pytest code/lld/chess -q. Note how Board.from_placement keeps every test to five pieces or fewer: a rules test that starts from the opening position and plays twenty moves to reach the interesting square is a test nobody can debug.

45-minute pacing

Minutes What to do What to say or write
0-5 Clarify Rules engine or AI? Castling, promotion, en passant in or out? Undo required? Notation? Out of scope: search, clocks, repetition draws.
5-10 Entities Board, Square, Piece (+6), Move, MoveRecord, ChessGame, MoveValidator, MoveHistory. State the key claim: pieces are stateless and shared, the board owns castling rights.
10-16 Class diagram Draw Piece with the three hooks and hang the six subclasses off SlidingPiece/SteppingPiece. Add Board with apply/undo/is_attacked.
16-24 Move generation Write candidate_moves, then SlidingPiece._target_squares and Pawn. Say why attacks is separate from candidate_moves.
24-34 Legality and status Write apply, undo and legal_moves. Then _refresh_status: no legal move plus check is mate, no legal move without check is stalemate.
34-40 Undo and concurrency Walk the memento fields; explain the lock and why legal_moves is a write. Mention the eight-thread test.
40-45 Extensions Minimax over legal_moves, notation as a formatter, repetition via position hashing, Chess960 as one changed factory.