On this page

Design a Chess Game

Chess is the gold standard for testing OOP polymorphism in LLD interviews. Every piece type has different movement rules, yet they share a common interface. The challenge is modeling move validation, check detection, and game state transitions cleanly.

Chess is a good interview problem because the rules are fixed and everyone already knows them. You don't spend ten minutes guessing what the interviewer wants. All the difficulty sits in the model. Where does "this move is legal" live: in the piece, the board, or the game? How do you tell "the king is in check" apart from "this piece can move there"? How do you undo a capture when the captured piece has already left the board? And how do castling, en passant and promotion fit without turning makeMove into a 200-line if chain?

This page answers those questions in the order a 45-minute interview takes them (see The LLD Interview Framework). The first implementation below is the one this page has always shown, now with its bugs corrected in place. After it comes a complete, runnable version in Java, Python and TypeScript. That version adds three things: it filters pseudo-legal moves by king safety, it makes every move a Command that can undo itself, and it checks its own move generator against published perft counts.

Requirements & Use Cases

Functional Requirements

  1. Standard 8x8 chess board with standard starting positions
  2. Two players alternate turns (white moves first)
  3. Six piece types: King, Queen, Rook, Bishop, Knight, Pawn
  4. Each piece has unique movement rules
  5. Move validation: can't move into check, can't move through pieces (except Knight)
  6. Detect check, checkmate, and stalemate
  7. Special moves: castling, en passant, pawn promotion
  8. Game ends on checkmate, stalemate, resignation, or draw agreement

Non-Functional Requirements

  • Clear separation between game rules and UI
  • Extensible for variants (Chess960, timed games)
  • Undo/redo support via command pattern

Use Cases

ActorUse Case
PlayerMake a move (source square to destination square)
PlayerResign or offer draw
SystemValidate move legality
SystemDetect check, checkmate, stalemate
SystemHandle special moves (castling, en passant, promotion)
SystemTrack move history

Clarifying questions to ask first

You know the rules of chess, so these questions are about scope, not rules. Propose an answer with each one so the conversation keeps moving.

QuestionUsual answerWhat it changes
Two humans on one device, or online play?Start local, design so online can be addedWhether a GameSession with player identity and locking is needed
Full rules, including castling, en passant and promotion?Core moves first, specials as extensionsWhether Move has to carry side effects beyond from and to
Draw rules: threefold repetition, fifty-move rule, insufficient material?Stalemate and agreed draws only, repetition as a follow-upWhether we need position hashing and a half-move clock
Undo and redo?Yes, bothMakes Move a Command, and the board must be fully reversible
Clocks and time controls?Out of scope, mention as an extensionA Clock per player and a timeout path into the state machine
AI opponent?Out of scopeIf yes, the move generator must be fast and side-effect free
Input format?Square names such as e2, e4We need square parsing but no full algebraic-notation parser

Write the agreed scope down:

IN SCOPE
- 8x8 board, standard setup, White moves first
- Legal-move validation for all six pieces, including "may not leave own king in check"
- Check, checkmate, stalemate, resignation, agreed draw
- Undo / redo of any number of moves
- Castling, en passant, promotion (added as extensions once the core works)

OUT OF SCOPE (for now)
- Clocks, threefold repetition, fifty-move rule, insufficient material
- Networking, persistence, UI, AI

Non-functional requirements, as properties of the code

  • Correctness first. A chess engine that accepts one illegal move is broken, so the move generator gets the strongest tests on the page (perft counts, see Testing).
  • Reversibility. Every state change made by a move must be undoable exactly, including the "has this rook moved?" flags and the en passant square, which are easy to forget.
  • Open for new rules. Chess960 and other variants change the setup and castling, not how a bishop moves. Keep piece geometry, game rules and setup separate.
  • Thread safety at the boundary. The Game object is single-writer. If two network requests touch it, they're serialised one level up (see Concurrency).

Core entities and relationships

Start from the nouns in the requirements, then decide who owns what.

EntityKindResponsibilityOwned by
Pos / PositionValue object (immutable)A square: row and column, parsing "e4"Nobody; created freely
ColorEnumWHITE, BLACK, opposite()—
Piece (abstract) and its 6 subclassesEntityGeometry only: where this piece could go from a square, and which squares it attacksBoard (by square)
BoardEntityThe 8x8 grid, plus the one bit of history a position needs: the en passant target square. Answers "is this square attacked by colour X?"Game
MoveCommandOne move with all its side effects: capture, castling rook, promotion, the new en passant square. Can execute() and undo()Game's undo and redo stacks
GameAggregate rootWhose turn it is, legal-move generation, state (active, check, checkmate…), undo and redo, resign and drawThe caller, or a GameSession
PlayerEntityName and colourGame
GameState / GameStatusEnumLifecycle of a gameGame

Three decisions in that table carry the design:

  1. Pieces know geometry, the game knows legality. A bishop can say "from c1 I reach d2, e3, f4" without knowing whose turn it is or whether its king is pinned. Whether a move is legal depends on the whole position, so it belongs to Game. This is the single most important split on the page.
  2. The board is dumb storage plus one query. Board holds pieces and answers isAttacked(square, byColor). It doesn't know about turns or checkmate.
  3. A move is an object, not a pair of squares. As soon as you need undo, castling or en passant, (from, to) isn't enough information to reverse the move. Making Move a Command puts all that information in one place.

Class Diagram

classDiagram
    class Game {
        -board: Board
        -players: Player[2]
        -currentTurn: Color
        -status: GameStatus
        -moveHistory: Move[]
        +makeMove(from: Position, to: Position): boolean
        +resign(player: Player): void
        +getStatus(): GameStatus
        +isCheck(): boolean
        +isCheckmate(): boolean
        +isStalemate(): boolean
    }

    class Board {
        -grid: (Piece|null)[][]
        +getPiece(pos: Position): Piece?
        +setPiece(pos: Position, piece: Piece?): void
        +movePiece(from: Position, to: Position): void
        +isInsideBoard(pos: Position): boolean
        +findKing(color: Color): Position
        +getAllPieces(color: Color): Piece[]
    }

    class Piece {
        <<abstract>>
        #color: Color
        #hasMoved: boolean
        +getColor(): Color
        +canMove(board: Board, from: Position, to: Position): boolean*
        +getPossibleMoves(board: Board, from: Position): Position[]*
    }

    class King {
        +canMove(): boolean
        +getPossibleMoves(): Position[]
    }
    class Queen {
        +canMove(): boolean
        +getPossibleMoves(): Position[]
    }
    class Rook {
        +canMove(): boolean
        +getPossibleMoves(): Position[]
    }
    class Bishop {
        +canMove(): boolean
        +getPossibleMoves(): Position[]
    }
    class Knight {
        +canMove(): boolean
        +getPossibleMoves(): Position[]
    }
    class Pawn {
        +canMove(): boolean
        +getPossibleMoves(): Position[]
    }

    class Position {
        +row: int
        +col: int
    }

    class Move {
        +from: Position
        +to: Position
        +piece: Piece
        +capturedPiece: Piece?
        +isPromotion: boolean
        +isCastling: boolean
        +isEnPassant: boolean
    }

    class Player {
        +name: string
        +color: Color
    }

    class GameStatus {
        <<enumeration>>
        ACTIVE
        WHITE_WINS
        BLACK_WINS
        STALEMATE
        DRAW
        RESIGNED
    }

    class Color {
        <<enumeration>>
        WHITE
        BLACK
    }

    Game *-- Board
    Game *-- Player
    Game --> GameStatus
    Game *-- Move
    Board --> Piece
    Piece <|-- King
    Piece <|-- Queen
    Piece <|-- Rook
    Piece <|-- Bishop
    Piece <|-- Knight
    Piece <|-- Pawn
    Piece --> Color
    Move --> Position
    Move --> Piece

Refined class diagram (the runnable version)

The diagram above is the first-pass design. The runnable version further down changes three things. Piece exposes attacks() separately from pseudoMoves(). Move becomes a Command with execute and undo. And Game owns two stacks instead of a flat history list.

classDiagram
    class Game {
        -board: Board
        -turn: Color
        -state: GameState
        -winner: Color
        -undoStack: Move[]
        -redoStack: Move[]
        +move(from, to, promo) bool
        +undo() bool
        +redo() bool
        +resign(color) bool
        +agreeDraw() bool
        +legalMoves(color) Move[]
        -addCastling(color, out)
        -updateState()
    }
    class Board {
        -grid: Piece[8][8]
        +enPassant: Pos
        +get(pos) Piece
        +set(pos, piece)
        +pieces(color) List
        +findKing(color) Pos
        +isAttacked(square, byColor) bool
        +parse(rows)$ Board
        +standard()$ Board
    }
    class Piece {
        <<abstract>>
        +color: Color
        +hasMoved: bool
        +letter()* char
        +pseudoMoves(board, from)* Pos[]
        +attacks(board, from, target) bool
        #slide(board, from, dirs) Pos[]
        #step(board, from, offsets) Pos[]
    }
    class Pawn {
        +pseudoMoves(board, from) Pos[]
        +attacks(board, from, target) bool
    }
    class Move {
        +from: Pos
        +to: Pos
        +captureSq: Pos
        +promotion: Piece
        +rookFrom: Pos
        +rookTo: Pos
        -captured: Piece
        -prevMoved: bool
        -prevEnPassant: Pos
        +create(board, from, to, promo)$ Move
        +execute(board)
        +undo(board)
    }
    class Pos {
        <<value object>>
        +row: int
        +col: int
        +of(square)$ Pos
    }
    class GameState {
        <<enumeration>>
        ACTIVE
        CHECK
        CHECKMATE
        STALEMATE
        RESIGNED
        DRAW
    }
    Game *-- Board
    Game o-- Move : "undo and redo stacks"
    Game --> GameState
    Board o-- Piece : "64 squares"
    Piece <|-- King
    Piece <|-- Queen
    Piece <|-- Rook
    Piece <|-- Bishop
    Piece <|-- Knight
    Piece <|-- Pawn
    Move --> Piece
    Move --> Pos

Key flows

Making a move

The client sends two squares. Game builds the list of legal moves, finds the one that matches, executes it, flips the turn and recomputes the state. Matching against the generated list means there is exactly one definition of legality. move() never re-implements a rule.

sequenceDiagram
    participant C as Client
    participant G as Game
    participant P as Piece
    participant B as Board
    participant M as Move
    C->>G: move("e2", "e4")
    G->>G: reject if state is terminal
    loop each piece of the side to move
        G->>P: pseudoMoves(board, from)
        P-->>G: candidate squares
    end
    G->>G: addCastling(turn, candidates)
    loop each candidate Move
        G->>M: execute(board)
        G->>B: isAttacked(own king, opponent)
        B-->>G: true or false
        G->>M: undo(board)
    end
    G->>G: pick the legal move matching e2 to e4
    G->>M: execute(board)
    G->>G: push on undo stack, clear redo stack
    G->>G: flip turn, updateState()
    G-->>C: true

Detecting checkmate after a move

updateState() asks two questions about the side that is now to move. Is its king attacked? Does it have at least one legal move? Those two booleans decide all four non-terminal-by-agreement outcomes.

sequenceDiagram
    participant G as Game
    participant B as Board
    G->>B: findKing(turn)
    B-->>G: king square
    G->>B: isAttacked(king square, opponent)
    B-->>G: inCheck
    G->>G: legalMoves(turn) is empty?
    alt no legal moves and in check
        G->>G: state = CHECKMATE, winner = opponent
    else no legal moves and not in check
        G->>G: state = STALEMATE
    else has moves and in check
        G->>G: state = CHECK
    else has moves and not in check
        G->>G: state = ACTIVE
    end
In check?Has a legal move?Result
yesnoCheckmate, the other side wins
nonoStalemate, a draw
yesyesCheck, the game goes on
noyesActive

Undo and redo

Undo pops the last command and asks it to reverse itself. The command remembers what it destroyed (the captured piece, the old hasMoved flag, the old en passant square), so the game doesn't need a snapshot of the whole board.

sequenceDiagram
    participant C as Client
    participant G as Game
    participant M as Move
    participant B as Board
    C->>G: undo()
    G->>G: refuse if RESIGNED or DRAW or stack empty
    G->>M: pop from undo stack
    M->>B: restore en passant square
    M->>B: move castling rook back, if any
    M->>B: put moving piece back on from, restore hasMoved
    M->>B: put captured piece back on its square
    G->>G: push on redo stack, flip turn, updateState()
    G-->>C: true
    C->>G: redo()
    G->>M: pop from redo stack, execute(board)
    G-->>C: true

Game lifecycle

stateDiagram-v2
    [*] --> ACTIVE
    ACTIVE --> CHECK: move gives check
    CHECK --> ACTIVE: move escapes check
    ACTIVE --> ACTIVE: quiet move
    CHECK --> CHECKMATE: no legal reply
    ACTIVE --> STALEMATE: no legal reply, not in check
    ACTIVE --> RESIGNED: resign
    CHECK --> RESIGNED: resign
    ACTIVE --> DRAW: draw agreed
    CHECK --> DRAW: draw agreed
    CHECKMATE --> CHECK: undo
    STALEMATE --> ACTIVE: undo
    RESIGNED --> [*]
    DRAW --> [*]
    CHECKMATE --> [*]
    STALEMATE --> [*]

Two choices are visible in the diagram. First, checkmate and stalemate can be undone (useful for analysis and for a "takeback" button) but resignation and agreed draws can't, because those are decisions by a player, not facts about the position. Second, CHECK is a real state rather than a flag. The UI needs to show it, and it's derived the same way as checkmate, so it costs nothing extra.

Why the state is recomputed, not stored per transition

updateState() derives the state from the position every time. Undo, redo and new moves can't get it out of sync, because nothing ever sets CHECK or CHECKMATE by hand. Only RESIGNED and DRAW are set directly, and they're terminal.

Move validation: polymorphism or a table?

Interviewers often ask this directly: "Why a subclass per piece? Couldn't you use a table?" Both work. Know the trade-off and pick one deliberately.

Polymorphism (what this page uses). Each piece class overrides pseudoMoves(board, from). Sliding pieces share a slide() helper and stepping pieces share step(), so each subclass is one line:

class Rook extends Piece {
  readonly letter = "R";
  pseudoMoves(b: Board, from: Pos): Pos[] { return this.slide(b, from, ORTHO); }
}

A direction table. Five of the six pieces are just "a set of directions, and whether you keep going":

type Rule = { dirs: Dir[]; slides: boolean };
const RULES: Record<string, Rule> = {
  K: { dirs: ALL, slides: false },
  Q: { dirs: ALL, slides: true },
  R: { dirs: ORTHO, slides: true },
  B: { dirs: DIAG, slides: true },
  N: { dirs: JUMPS, slides: false },
  // P is missing on purpose: pawns move one way and capture another
};

function tableMoves(b: Board, from: Pos, piece: Piece): Pos[] {
  const rule = RULES[piece.letter];
  const out: Pos[] = [];
  for (const [dr, dc] of rule.dirs) {
    let p = from.plus(dr, dc);
    while (p.valid()) {
      const t = b.get(p);
      if (t !== null) { if (t.color !== piece.color) out.push(p); break; }
      out.push(p);
      if (!rule.slides) break;
      p = p.plus(dr, dc);
    }
  }
  return out;
}

(This snippet was run against the runnable TypeScript below. It produces exactly the same destinations as the subclasses for every non-pawn piece in the start position and in the "Kiwipete" test position.)

PolymorphismDirection table
Adding a fairy piece (for example an Archbishop = Bishop + Knight)New subclassNew table row, if it fits the "directions plus slides" shape
PawnsNatural: Pawn overrides pseudoMoves and attacksDoesn't fit, so you need a special case anyway
Readability in an interviewEach class reads like the rule bookCompact, but the rules hide in data
Per-piece behaviour beyond movement (value, symbol, promotion rules)Lives on the classNeeds more columns or parallel tables
PerformanceVirtual call per piece, fineSlightly faster, matters only for engines

Recommendation: use polymorphism in an LLD interview, because it's what the interviewer is testing, and mention the table as the alternative you considered. Real engines go further than either and use bitboards (one 64-bit integer per piece type with precomputed attack masks). Mention that only if asked, since it's an engine-performance answer, not an object-design one.

The trap: putting legality in the piece

A common first design gives Piece.canMove() the job of deciding whether a move is legal: whose turn it is, whether the king is in check, castling rights. Then the bishop needs to know about the king, the king needs to know about attacks, and attacks need to ask every piece, including kings, which ask about castling, which asks about attacks… Keep pieces at pseudo-legal geometry and let Game apply the whole-position rules.

Check, checkmate and stalemate

All three come from one primitive and one filter:

  1. Board.isAttacked(square, byColor). Does any piece of byColor attack square? Each piece answers through attacks(). The default is "is the square in my pseudo-moves", and Pawn overrides it because pawns capture diagonally but move straight. The king's attacks are only its eight neighbours. Castling is not an attack, which is exactly why castling lives in Game and not in King.pseudoMoves.
  2. Legal = pseudo-legal and doesn't leave your own king attacked. Generate every pseudo-legal move, execute it, ask isAttacked(ownKing, opponent), and undo. Whatever survives is legal. This one filter handles pins, moving into check, discovered checks, failing to answer a check, and the odd en passant case where removing two pawns from a rank exposes the king. No rule needs its own code.

Then:

  • Check = my king is attacked.
  • Checkmate = in check and no legal move.
  • Stalemate = not in check and no legal move.

The cost is "execute, test, undo" for every candidate: about 30–40 candidates per position, each with one isAttacked scan. That's trivial for a two-player game. A chess engine that searches millions of positions would precompute pins and check rays instead. The runnable code marks that ceiling with a "Simplification:" comment on isAttacked.

Say this sentence in the interview

"Pieces generate pseudo-legal moves. The game filters them by making each move, checking whether my king is attacked, and undoing it. Checkmate is 'in check with no legal moves', and stalemate is the same without check." That one sentence covers the part of the problem most candidates get wrong.

Core Classes & Interfaces

Corrections (2026-11-10) to the listings in this section

The original TypeScript and Python listings below are kept, with these bugs fixed in place (each fix is marked in the code):

  1. hasLegalMoves() permanently set hasMoved = true on every piece it tried, because movePiece() sets the flag and undoMove() didn't clear it. After the first status check, nobody could castle. It now saves and restores the flag.
  2. A rejected move reset hasMoved to false instead of to its previous value. A king or rook that had already moved could castle again after one illegal attempt.
  3. Castling out of check and through an attacked square was allowed. The comment said "full check in Game class", but Game never did that check. isCastleSafe() now checks the king's square and the square it passes over.
  4. isInCheck() used canMove(), so an unmoved enemy king "attacked" its castling squares two files away. A dedicated isSquareAttacked() now uses adjacency for kings and diagonals for pawns.

The listings were re-run after the fixes (fool's mate gives checkmate, and castling still works after six moves). The complete runnable version further down is the recommended reference.

TypeScript Implementation

// ─── Enums & Value Objects ───────────────────────────────

enum Color {
  WHITE = 'WHITE',
  BLACK = 'BLACK',
}

enum GameStatus {
  ACTIVE = 'ACTIVE',
  WHITE_WINS = 'WHITE_WINS',
  BLACK_WINS = 'BLACK_WINS',
  STALEMATE = 'STALEMATE',
  DRAW = 'DRAW',
  RESIGNED = 'RESIGNED',
}

class Position {
  constructor(
    public readonly row: number,
    public readonly col: number
  ) {}

  equals(other: Position): boolean {
    return this.row === other.row && this.col === other.col;
  }

  isValid(): boolean {
    return this.row >= 0 && this.row < 8 && this.col >= 0 && this.col < 8;
  }
}

interface Move {
  from: Position;
  to: Position;
  piece: Piece;
  capturedPiece: Piece | null;
  isPromotion: boolean;
  isCastling: boolean;
  isEnPassant: boolean;
}

// ─── Piece Hierarchy ─────────────────────────────────────

abstract class Piece {
  public hasMoved: boolean = false;

  constructor(public readonly color: Color) {}

  abstract canMove(board: Board, from: Position, to: Position): boolean;
  abstract getPossibleMoves(board: Board, from: Position): Position[];
  abstract get symbol(): string;

  isOpponent(other: Piece | null): boolean {
    return other !== null && other.color !== this.color;
  }

  isFriendly(other: Piece | null): boolean {
    return other !== null && other.color === this.color;
  }

  /** Slide along a direction until blocked (for Rook, Bishop, Queen) */
  protected slideMoves(
    board: Board,
    from: Position,
    directions: [number, number][]
  ): Position[] {
    const moves: Position[] = [];
    for (const [dr, dc] of directions) {
      let r = from.row + dr;
      let c = from.col + dc;
      while (r >= 0 && r < 8 && c >= 0 && c < 8) {
        const pos = new Position(r, c);
        const target = board.getPiece(pos);
        if (target === null) {
          moves.push(pos);
        } else if (this.isOpponent(target)) {
          moves.push(pos);
          break; // can capture but not go further
        } else {
          break; // friendly piece blocks
        }
        r += dr;
        c += dc;
      }
    }
    return moves;
  }
}

class King extends Piece {
  get symbol(): string {
    return this.color === Color.WHITE ? 'K' : 'k';
  }

  canMove(board: Board, from: Position, to: Position): boolean {
    return this.getPossibleMoves(board, from).some((p) => p.equals(to));
  }

  getPossibleMoves(board: Board, from: Position): Position[] {
    const moves: Position[] = [];
    const directions = [
      [-1, -1], [-1, 0], [-1, 1],
      [0, -1],           [0, 1],
      [1, -1],  [1, 0],  [1, 1],
    ];

    for (const [dr, dc] of directions) {
      const pos = new Position(from.row + dr, from.col + dc);
      if (pos.isValid() && !this.isFriendly(board.getPiece(pos))) {
        moves.push(pos);
      }
    }

    // Castling (simplified — full check in Game class)
    if (!this.hasMoved) {
      // Kingside
      const ksRook = board.getPiece(new Position(from.row, 7));
      if (
        ksRook instanceof Rook &&
        !ksRook.hasMoved &&
        board.getPiece(new Position(from.row, 5)) === null &&
        board.getPiece(new Position(from.row, 6)) === null
      ) {
        moves.push(new Position(from.row, 6));
      }
      // Queenside
      const qsRook = board.getPiece(new Position(from.row, 0));
      if (
        qsRook instanceof Rook &&
        !qsRook.hasMoved &&
        board.getPiece(new Position(from.row, 1)) === null &&
        board.getPiece(new Position(from.row, 2)) === null &&
        board.getPiece(new Position(from.row, 3)) === null
      ) {
        moves.push(new Position(from.row, 2));
      }
    }

    return moves;
  }
}

class Queen extends Piece {
  get symbol(): string {
    return this.color === Color.WHITE ? 'Q' : 'q';
  }

  canMove(board: Board, from: Position, to: Position): boolean {
    return this.getPossibleMoves(board, from).some((p) => p.equals(to));
  }

  getPossibleMoves(board: Board, from: Position): Position[] {
    return this.slideMoves(board, from, [
      [-1, -1], [-1, 0], [-1, 1],
      [0, -1],           [0, 1],
      [1, -1],  [1, 0],  [1, 1],
    ]);
  }
}

class Rook extends Piece {
  get symbol(): string {
    return this.color === Color.WHITE ? 'R' : 'r';
  }

  canMove(board: Board, from: Position, to: Position): boolean {
    return this.getPossibleMoves(board, from).some((p) => p.equals(to));
  }

  getPossibleMoves(board: Board, from: Position): Position[] {
    return this.slideMoves(board, from, [
      [-1, 0], [1, 0], [0, -1], [0, 1],
    ]);
  }
}

class Bishop extends Piece {
  get symbol(): string {
    return this.color === Color.WHITE ? 'B' : 'b';
  }

  canMove(board: Board, from: Position, to: Position): boolean {
    return this.getPossibleMoves(board, from).some((p) => p.equals(to));
  }

  getPossibleMoves(board: Board, from: Position): Position[] {
    return this.slideMoves(board, from, [
      [-1, -1], [-1, 1], [1, -1], [1, 1],
    ]);
  }
}

class Knight extends Piece {
  get symbol(): string {
    return this.color === Color.WHITE ? 'N' : 'n';
  }

  canMove(board: Board, from: Position, to: Position): boolean {
    return this.getPossibleMoves(board, from).some((p) => p.equals(to));
  }

  getPossibleMoves(board: Board, from: Position): Position[] {
    const moves: Position[] = [];
    const jumps = [
      [-2, -1], [-2, 1], [-1, -2], [-1, 2],
      [1, -2],  [1, 2],  [2, -1],  [2, 1],
    ];

    for (const [dr, dc] of jumps) {
      const pos = new Position(from.row + dr, from.col + dc);
      if (pos.isValid() && !this.isFriendly(board.getPiece(pos))) {
        moves.push(pos);
      }
    }
    return moves;
  }
}

class Pawn extends Piece {
  get symbol(): string {
    return this.color === Color.WHITE ? 'P' : 'p';
  }

  canMove(board: Board, from: Position, to: Position): boolean {
    return this.getPossibleMoves(board, from).some((p) => p.equals(to));
  }

  getPossibleMoves(board: Board, from: Position): Position[] {
    const moves: Position[] = [];
    const dir = this.color === Color.WHITE ? -1 : 1;
    const startRow = this.color === Color.WHITE ? 6 : 1;

    // Forward one square
    const oneStep = new Position(from.row + dir, from.col);
    if (oneStep.isValid() && board.getPiece(oneStep) === null) {
      moves.push(oneStep);

      // Forward two squares from starting position
      if (from.row === startRow) {
        const twoStep = new Position(from.row + 2 * dir, from.col);
        if (twoStep.isValid() && board.getPiece(twoStep) === null) {
          moves.push(twoStep);
        }
      }
    }

    // Diagonal captures
    for (const dc of [-1, 1]) {
      const capture = new Position(from.row + dir, from.col + dc);
      if (capture.isValid() && this.isOpponent(board.getPiece(capture))) {
        moves.push(capture);
      }
    }

    return moves;
  }
}

// ─── Board ───────────────────────────────────────────────

class Board {
  private grid: (Piece | null)[][] = [];

  constructor() {
    this.grid = Array.from({ length: 8 }, () => Array(8).fill(null));
  }

  getPiece(pos: Position): Piece | null {
    if (!pos.isValid()) return null;
    return this.grid[pos.row][pos.col];
  }

  setPiece(pos: Position, piece: Piece | null): void {
    this.grid[pos.row][pos.col] = piece;
  }

  movePiece(from: Position, to: Position): Piece | null {
    const piece = this.getPiece(from);
    const captured = this.getPiece(to);
    this.setPiece(to, piece);
    this.setPiece(from, null);
    if (piece) piece.hasMoved = true;
    return captured;
  }

  /** Undo a move (for check detection) */
  undoMove(from: Position, to: Position, captured: Piece | null): void {
    const piece = this.getPiece(to);
    this.setPiece(from, piece);
    this.setPiece(to, captured);
  }

  findKing(color: Color): Position {
    for (let r = 0; r < 8; r++) {
      for (let c = 0; c < 8; c++) {
        const piece = this.grid[r][c];
        if (piece instanceof King && piece.color === color) {
          return new Position(r, c);
        }
      }
    }
    throw new Error(`King not found for ${color}`);
  }

  getAllPieces(color: Color): Array<{ piece: Piece; position: Position }> {
    const pieces: Array<{ piece: Piece; position: Position }> = [];
    for (let r = 0; r < 8; r++) {
      for (let c = 0; c < 8; c++) {
        const piece = this.grid[r][c];
        if (piece && piece.color === color) {
          pieces.push({ piece, position: new Position(r, c) });
        }
      }
    }
    return pieces;
  }

  /** Initialize standard starting position */
  setup(): void {
    const backRank = [Rook, Knight, Bishop, Queen, King, Bishop, Knight, Rook];

    for (let c = 0; c < 8; c++) {
      this.grid[0][c] = new backRank[c](Color.BLACK);
      this.grid[1][c] = new Pawn(Color.BLACK);
      this.grid[6][c] = new Pawn(Color.WHITE);
      this.grid[7][c] = new backRank[c](Color.WHITE);
    }
  }
}

// ─── Player ──────────────────────────────────────────────

class Player {
  constructor(
    public readonly name: string,
    public readonly color: Color
  ) {}
}

// ─── Game ────────────────────────────────────────────────

class Game {
  private board: Board;
  private players: [Player, Player];
  private currentTurn: Color = Color.WHITE;
  private status: GameStatus = GameStatus.ACTIVE;
  private moveHistory: Move[] = [];

  constructor(white: Player, black: Player) {
    this.players = [white, black];
    this.board = new Board();
    this.board.setup();
  }

  getStatus(): GameStatus {
    return this.status;
  }

  getCurrentTurn(): Color {
    return this.currentTurn;
  }

  makeMove(from: Position, to: Position): boolean {
    if (this.status !== GameStatus.ACTIVE) return false;

    const piece = this.board.getPiece(from);
    if (!piece || piece.color !== this.currentTurn) return false;
    if (!piece.canMove(this.board, from, to)) return false;

    // Correction (2026-11-10): castling was never checked for "out of" or "through" check
    if (piece instanceof King && Math.abs(from.col - to.col) === 2 &&
        !this.isCastleSafe(from, to, piece.color)) return false;

    // Execute move
    const hadMoved = piece.hasMoved;
    const captured = this.board.movePiece(from, to);

    // Check if move leaves own king in check — illegal
    if (this.isInCheck(this.currentTurn)) {
      this.board.undoMove(from, to, captured);
      // Correction (2026-11-10): restore the old flag. Resetting to false let a rook that
      // had already moved castle again after one rejected move.
      piece.hasMoved = hadMoved;
      return false;
    }

    // Handle castling rook movement
    if (piece instanceof King && Math.abs(from.col - to.col) === 2) {
      this.handleCastlingRook(from, to);
    }

    // Handle pawn promotion (auto-promote to queen for simplicity)
    let isPromotion = false;
    if (piece instanceof Pawn) {
      const promotionRow = piece.color === Color.WHITE ? 0 : 7;
      if (to.row === promotionRow) {
        this.board.setPiece(to, new Queen(piece.color));
        isPromotion = true;
      }
    }

    // Record move
    this.moveHistory.push({
      from,
      to,
      piece,
      capturedPiece: captured,
      isPromotion,
      isCastling: piece instanceof King && Math.abs(from.col - to.col) === 2,
      isEnPassant: false,
    });

    // Switch turns
    this.currentTurn =
      this.currentTurn === Color.WHITE ? Color.BLACK : Color.WHITE;

    // Check game-ending conditions
    this.updateStatus();

    return true;
  }

  private handleCastlingRook(kingFrom: Position, kingTo: Position): void {
    if (kingTo.col === 6) {
      // Kingside
      this.board.movePiece(
        new Position(kingFrom.row, 7),
        new Position(kingFrom.row, 5)
      );
    } else if (kingTo.col === 2) {
      // Queenside
      this.board.movePiece(
        new Position(kingFrom.row, 0),
        new Position(kingFrom.row, 3)
      );
    }
  }

  isInCheck(color: Color): boolean {
    const kingPos = this.board.findKing(color);
    const opponentColor = color === Color.WHITE ? Color.BLACK : Color.WHITE;
    // Correction (2026-11-10): this used piece.canMove(), which counts the enemy
    // king's castling squares as "attacked" and misses pawn attacks on empty squares.
    return this.isSquareAttacked(kingPos, opponentColor);
  }

  // Correction (2026-11-10): an attack test separate from movement rules.
  private isSquareAttacked(sq: Position, by: Color): boolean {
    return this.board.getAllPieces(by).some(({ piece, position }) => {
      const dr = sq.row - position.row;
      const dc = sq.col - position.col;
      if (piece instanceof Pawn) {
        return dr === (piece.color === Color.WHITE ? -1 : 1) && Math.abs(dc) === 1;
      }
      if (piece instanceof King) return Math.max(Math.abs(dr), Math.abs(dc)) === 1;
      return piece.canMove(this.board, position, sq);
    });
  }

  // Correction (2026-11-10): the king may not castle out of check or across an attacked
  // square. The destination square is covered by the normal "left in check" test.
  private isCastleSafe(from: Position, to: Position, color: Color): boolean {
    const opponent = color === Color.WHITE ? Color.BLACK : Color.WHITE;
    const step = to.col > from.col ? 1 : -1;
    return (
      !this.isSquareAttacked(from, opponent) &&
      !this.isSquareAttacked(new Position(from.row, from.col + step), opponent)
    );
  }

  /** Check if the given color has any legal moves */
  private hasLegalMoves(color: Color): boolean {
    const pieces = this.board.getAllPieces(color);

    for (const { piece, position } of pieces) {
      const moves = piece.getPossibleMoves(this.board, position);
      for (const move of moves) {
        if (piece instanceof King && Math.abs(move.col - position.col) === 2 &&
            !this.isCastleSafe(position, move, color)) continue;
        // Try the move
        // Correction (2026-11-10): movePiece() sets hasMoved = true and undoMove() did
        // not reset it, so this search silently took away every side's castling rights.
        const hadMoved = piece.hasMoved;
        const captured = this.board.movePiece(position, move);
        const leavesInCheck = this.isInCheck(color);
        this.board.undoMove(position, move, captured);
        piece.hasMoved = hadMoved;

        if (!leavesInCheck) return true; // at least one legal move exists
      }
    }
    return false;
  }

  private updateStatus(): void {
    const hasLegal = this.hasLegalMoves(this.currentTurn);
    const inCheck = this.isInCheck(this.currentTurn);

    if (!hasLegal && inCheck) {
      // Checkmate
      this.status =
        this.currentTurn === Color.WHITE
          ? GameStatus.BLACK_WINS
          : GameStatus.WHITE_WINS;
    } else if (!hasLegal && !inCheck) {
      this.status = GameStatus.STALEMATE;
    }
  }

  resign(player: Player): void {
    this.status =
      player.color === Color.WHITE
        ? GameStatus.BLACK_WINS
        : GameStatus.WHITE_WINS;
  }

  getMoveHistory(): Move[] {
    return [...this.moveHistory];
  }
}

Python Implementation

from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from enum import Enum
from typing import Optional


# ─── Enums & Value Objects ──────────────────────────────

class Color(Enum):
    WHITE = "WHITE"
    BLACK = "BLACK"


class GameStatus(Enum):
    ACTIVE = "ACTIVE"
    WHITE_WINS = "WHITE_WINS"
    BLACK_WINS = "BLACK_WINS"
    STALEMATE = "STALEMATE"
    DRAW = "DRAW"
    RESIGNED = "RESIGNED"


@dataclass(frozen=True)
class Position:
    row: int
    col: int

    def is_valid(self) -> bool:
        return 0 <= self.row < 8 and 0 <= self.col < 8


@dataclass
class Move:
    from_pos: Position
    to_pos: Position
    piece: "Piece"
    captured_piece: Optional["Piece"] = None
    is_promotion: bool = False
    is_castling: bool = False
    is_en_passant: bool = False


# ─── Piece Hierarchy ───────────────────────────────────

class Piece(ABC):
    def __init__(self, color: Color):
        self.color = color
        self.has_moved = False

    @abstractmethod
    def can_move(self, board: "Board", from_pos: Position, to_pos: Position) -> bool:
        ...

    @abstractmethod
    def get_possible_moves(self, board: "Board", from_pos: Position) -> list[Position]:
        ...

    def is_opponent(self, other: Optional["Piece"]) -> bool:
        return other is not None and other.color != self.color

    def is_friendly(self, other: Optional["Piece"]) -> bool:
        return other is not None and other.color == self.color

    def _slide_moves(
        self,
        board: "Board",
        from_pos: Position,
        directions: list[tuple[int, int]],
    ) -> list[Position]:
        moves = []
        for dr, dc in directions:
            r, c = from_pos.row + dr, from_pos.col + dc
            while 0 <= r < 8 and 0 <= c < 8:
                pos = Position(r, c)
                target = board.get_piece(pos)
                if target is None:
                    moves.append(pos)
                elif self.is_opponent(target):
                    moves.append(pos)
                    break
                else:
                    break
                r += dr
                c += dc
        return moves


class King(Piece):
    def can_move(self, board: "Board", from_pos: Position, to_pos: Position) -> bool:
        return to_pos in self.get_possible_moves(board, from_pos)

    def get_possible_moves(self, board: "Board", from_pos: Position) -> list[Position]:
        moves = []
        for dr in [-1, 0, 1]:
            for dc in [-1, 0, 1]:
                if dr == 0 and dc == 0:
                    continue
                pos = Position(from_pos.row + dr, from_pos.col + dc)
                if pos.is_valid() and not self.is_friendly(board.get_piece(pos)):
                    moves.append(pos)

        # Castling
        if not self.has_moved:
            # Kingside
            ks_rook = board.get_piece(Position(from_pos.row, 7))
            if (
                isinstance(ks_rook, Rook)
                and not ks_rook.has_moved
                and board.get_piece(Position(from_pos.row, 5)) is None
                and board.get_piece(Position(from_pos.row, 6)) is None
            ):
                moves.append(Position(from_pos.row, 6))
            # Queenside
            qs_rook = board.get_piece(Position(from_pos.row, 0))
            if (
                isinstance(qs_rook, Rook)
                and not qs_rook.has_moved
                and board.get_piece(Position(from_pos.row, 1)) is None
                and board.get_piece(Position(from_pos.row, 2)) is None
                and board.get_piece(Position(from_pos.row, 3)) is None
            ):
                moves.append(Position(from_pos.row, 2))
        return moves


class Queen(Piece):
    def can_move(self, board: "Board", from_pos: Position, to_pos: Position) -> bool:
        return to_pos in self.get_possible_moves(board, from_pos)

    def get_possible_moves(self, board: "Board", from_pos: Position) -> list[Position]:
        return self._slide_moves(
            board, from_pos,
            [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)],
        )


class Rook(Piece):
    def can_move(self, board: "Board", from_pos: Position, to_pos: Position) -> bool:
        return to_pos in self.get_possible_moves(board, from_pos)

    def get_possible_moves(self, board: "Board", from_pos: Position) -> list[Position]:
        return self._slide_moves(
            board, from_pos, [(-1, 0), (1, 0), (0, -1), (0, 1)]
        )


class Bishop(Piece):
    def can_move(self, board: "Board", from_pos: Position, to_pos: Position) -> bool:
        return to_pos in self.get_possible_moves(board, from_pos)

    def get_possible_moves(self, board: "Board", from_pos: Position) -> list[Position]:
        return self._slide_moves(
            board, from_pos, [(-1, -1), (-1, 1), (1, -1), (1, 1)]
        )


class Knight(Piece):
    def can_move(self, board: "Board", from_pos: Position, to_pos: Position) -> bool:
        return to_pos in self.get_possible_moves(board, from_pos)

    def get_possible_moves(self, board: "Board", from_pos: Position) -> list[Position]:
        moves = []
        jumps = [
            (-2, -1), (-2, 1), (-1, -2), (-1, 2),
            (1, -2), (1, 2), (2, -1), (2, 1),
        ]
        for dr, dc in jumps:
            pos = Position(from_pos.row + dr, from_pos.col + dc)
            if pos.is_valid() and not self.is_friendly(board.get_piece(pos)):
                moves.append(pos)
        return moves


class Pawn(Piece):
    def can_move(self, board: "Board", from_pos: Position, to_pos: Position) -> bool:
        return to_pos in self.get_possible_moves(board, from_pos)

    def get_possible_moves(self, board: "Board", from_pos: Position) -> list[Position]:
        moves = []
        direction = -1 if self.color == Color.WHITE else 1
        start_row = 6 if self.color == Color.WHITE else 1

        # Forward
        one_step = Position(from_pos.row + direction, from_pos.col)
        if one_step.is_valid() and board.get_piece(one_step) is None:
            moves.append(one_step)
            if from_pos.row == start_row:
                two_step = Position(from_pos.row + 2 * direction, from_pos.col)
                if two_step.is_valid() and board.get_piece(two_step) is None:
                    moves.append(two_step)

        # Diagonal captures
        for dc in [-1, 1]:
            cap = Position(from_pos.row + direction, from_pos.col + dc)
            if cap.is_valid() and self.is_opponent(board.get_piece(cap)):
                moves.append(cap)
        return moves


# ─── Board ──────────────────────────────────────────────

class Board:
    def __init__(self):
        self._grid: list[list[Optional[Piece]]] = [
            [None] * 8 for _ in range(8)
        ]

    def get_piece(self, pos: Position) -> Optional[Piece]:
        if not pos.is_valid():
            return None
        return self._grid[pos.row][pos.col]

    def set_piece(self, pos: Position, piece: Optional[Piece]) -> None:
        self._grid[pos.row][pos.col] = piece

    def move_piece(
        self, from_pos: Position, to_pos: Position
    ) -> Optional[Piece]:
        piece = self.get_piece(from_pos)
        captured = self.get_piece(to_pos)
        self.set_piece(to_pos, piece)
        self.set_piece(from_pos, None)
        if piece:
            piece.has_moved = True
        return captured

    def undo_move(
        self, from_pos: Position, to_pos: Position, captured: Optional[Piece]
    ) -> None:
        piece = self.get_piece(to_pos)
        self.set_piece(from_pos, piece)
        self.set_piece(to_pos, captured)

    def find_king(self, color: Color) -> Position:
        for r in range(8):
            for c in range(8):
                p = self._grid[r][c]
                if isinstance(p, King) and p.color == color:
                    return Position(r, c)
        raise ValueError(f"King not found for {color}")

    def get_all_pieces(
        self, color: Color
    ) -> list[tuple[Piece, Position]]:
        result = []
        for r in range(8):
            for c in range(8):
                p = self._grid[r][c]
                if p and p.color == color:
                    result.append((p, Position(r, c)))
        return result

    def setup(self) -> None:
        back_rank = [Rook, Knight, Bishop, Queen, King, Bishop, Knight, Rook]
        for c in range(8):
            self._grid[0][c] = back_rank[c](Color.BLACK)
            self._grid[1][c] = Pawn(Color.BLACK)
            self._grid[6][c] = Pawn(Color.WHITE)
            self._grid[7][c] = back_rank[c](Color.WHITE)


# ─── Game ───────────────────────────────────────────────

class Player:
    def __init__(self, name: str, color: Color):
        self.name = name
        self.color = color


class Game:
    def __init__(self, white: Player, black: Player):
        self._board = Board()
        self._board.setup()
        self._players = (white, black)
        self._current_turn = Color.WHITE
        self._status = GameStatus.ACTIVE
        self._move_history: list[Move] = []

    @property
    def status(self) -> GameStatus:
        return self._status

    def make_move(self, from_pos: Position, to_pos: Position) -> bool:
        if self._status != GameStatus.ACTIVE:
            return False

        piece = self._board.get_piece(from_pos)
        if not piece or piece.color != self._current_turn:
            return False
        if not piece.can_move(self._board, from_pos, to_pos):
            return False

        # Correction (2026-11-10): castling was never checked for "out of" or "through" check
        if (isinstance(piece, King) and abs(from_pos.col - to_pos.col) == 2
                and not self._is_castle_safe(from_pos, to_pos, piece.color)):
            return False

        had_moved = piece.has_moved
        captured = self._board.move_piece(from_pos, to_pos)

        if self._is_in_check(self._current_turn):
            self._board.undo_move(from_pos, to_pos, captured)
            # Correction (2026-11-10): restore the old flag instead of forcing False
            piece.has_moved = had_moved
            return False

        # Castling rook movement
        is_castling = isinstance(piece, King) and abs(from_pos.col - to_pos.col) == 2
        if is_castling:
            self._handle_castling_rook(from_pos, to_pos)

        # Pawn promotion
        is_promotion = False
        if isinstance(piece, Pawn):
            promo_row = 0 if piece.color == Color.WHITE else 7
            if to_pos.row == promo_row:
                self._board.set_piece(to_pos, Queen(piece.color))
                is_promotion = True

        self._move_history.append(Move(
            from_pos=from_pos, to_pos=to_pos, piece=piece,
            captured_piece=captured, is_promotion=is_promotion,
            is_castling=is_castling,
        ))

        self._current_turn = (
            Color.BLACK if self._current_turn == Color.WHITE else Color.WHITE
        )
        self._update_status()
        return True

    def _handle_castling_rook(self, king_from: Position, king_to: Position) -> None:
        if king_to.col == 6:
            self._board.move_piece(
                Position(king_from.row, 7), Position(king_from.row, 5)
            )
        elif king_to.col == 2:
            self._board.move_piece(
                Position(king_from.row, 0), Position(king_from.row, 3)
            )

    def _is_in_check(self, color: Color) -> bool:
        king_pos = self._board.find_king(color)
        opp = Color.BLACK if color == Color.WHITE else Color.WHITE
        # Correction (2026-11-10): can_move() counted castling squares as attacks
        return self._is_square_attacked(king_pos, opp)

    # Correction (2026-11-10): an attack test separate from movement rules
    def _is_square_attacked(self, sq: Position, by: Color) -> bool:
        for piece, pos in self._board.get_all_pieces(by):
            dr, dc = sq.row - pos.row, sq.col - pos.col
            if isinstance(piece, Pawn):
                hit = dr == (-1 if piece.color == Color.WHITE else 1) and abs(dc) == 1
            elif isinstance(piece, King):
                hit = max(abs(dr), abs(dc)) == 1
            else:
                hit = piece.can_move(self._board, pos, sq)
            if hit:
                return True
        return False

    # Correction (2026-11-10): no castling out of check or across an attacked square
    def _is_castle_safe(self, frm: Position, to: Position, color: Color) -> bool:
        opp = Color.BLACK if color == Color.WHITE else Color.WHITE
        step = 1 if to.col > frm.col else -1
        return (not self._is_square_attacked(frm, opp)
                and not self._is_square_attacked(Position(frm.row, frm.col + step), opp))

    def _has_legal_moves(self, color: Color) -> bool:
        for piece, pos in self._board.get_all_pieces(color):
            for move in piece.get_possible_moves(self._board, pos):
                if (isinstance(piece, King) and abs(move.col - pos.col) == 2
                        and not self._is_castle_safe(pos, move, color)):
                    continue
                # Correction (2026-11-10): restore has_moved after the trial move,
                # otherwise this search strips every side's castling rights
                had_moved = piece.has_moved
                captured = self._board.move_piece(pos, move)
                in_check = self._is_in_check(color)
                self._board.undo_move(pos, move, captured)
                piece.has_moved = had_moved
                if not in_check:
                    return True
        return False

    def _update_status(self) -> None:
        has_legal = self._has_legal_moves(self._current_turn)
        in_check = self._is_in_check(self._current_turn)

        if not has_legal and in_check:
            self._status = (
                GameStatus.BLACK_WINS
                if self._current_turn == Color.WHITE
                else GameStatus.WHITE_WINS
            )
        elif not has_legal:
            self._status = GameStatus.STALEMATE

    def resign(self, player: Player) -> None:
        self._status = (
            GameStatus.BLACK_WINS
            if player.color == Color.WHITE
            else GameStatus.WHITE_WINS
        )

Complete runnable implementation

This is the version to study and to reproduce in a machine-coding round. Each tab is a single file you can paste and run. Java: javac Chess.java && java -ea Chess. Python: python chess.py. TypeScript: tsx chess.ts, and it also passes tsc --strict. Each file ends with its own tests, which are covered in Testing.

What's different from the first listing:

  • pseudoMoves vs attacks. Pieces describe geometry only, and Pawn overrides attacks because it captures differently from how it moves. The king's pseudo-moves don't include castling, so attack detection can't recurse.
  • Move is a Command. Move.create works out every side effect up front (the en passant victim's square, the castling rook, the new en passant target). execute() records what it destroys, and undo() puts it all back, hasMoved flags included.
  • One definition of legality. Game.legalMoves(color) generates candidates, adds castling, then keeps only moves that don't leave the king attacked. move(), checkmate detection and the perft tests all use it.
  • Castling, en passant and promotion are already in. The extensions section shows them as the diffs you'd make live in the interview.
  • Test positions as strings. Board.parse takes eight strings, rank 8 first, so a test can set up any position in four lines.
import java.util.*;

enum Color {
    WHITE, BLACK;
    Color opposite() { return this == WHITE ? BLACK : WHITE; }
}

enum GameState { ACTIVE, CHECK, CHECKMATE, STALEMATE, RESIGNED, DRAW }

/** Immutable square. Row 0 is rank 8 (Black's back rank), row 7 is rank 1. */
record Pos(int row, int col) {
    static Pos of(String sq) { return new Pos(8 - (sq.charAt(1) - '0'), sq.charAt(0) - 'a'); }
    boolean valid() { return row >= 0 && row < 8 && col >= 0 && col < 8; }
    Pos plus(int dr, int dc) { return new Pos(row + dr, col + dc); }
    @Override public String toString() { return "" + (char) ('a' + col) + (8 - row); }
}

// ─── Pieces: each one knows only its own geometry ───────────────

abstract class Piece {
    static final int[][] ORTHO = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static final int[][] DIAG = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    static final int[][] ALL = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    static final int[][] JUMPS = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};

    final Color color;
    boolean hasMoved;

    Piece(Color color) { this.color = color; }

    abstract char letter();

    char symbol() { return color == Color.WHITE ? letter() : Character.toLowerCase(letter()); }

    /** Destinations by the piece's own rules, ignoring whether our king is left in check. */
    abstract List<Pos> pseudoMoves(Board b, Pos from);

    /** Does this piece attack target? Pawns override: they capture differently from how they move. */
    boolean attacks(Board b, Pos from, Pos target) { return pseudoMoves(b, from).contains(target); }

    protected List<Pos> slide(Board b, Pos from, int[][] dirs) {
        List<Pos> out = new ArrayList<>();
        for (int[] d : dirs) {
            for (Pos p = from.plus(d[0], d[1]); p.valid(); p = p.plus(d[0], d[1])) {
                Piece t = b.get(p);
                if (t == null) { out.add(p); continue; }
                if (t.color != color) out.add(p);
                break;
            }
        }
        return out;
    }

    protected List<Pos> step(Board b, Pos from, int[][] offsets) {
        List<Pos> out = new ArrayList<>();
        for (int[] d : offsets) {
            Pos p = from.plus(d[0], d[1]);
            if (p.valid() && (b.get(p) == null || b.get(p).color != color)) out.add(p);
        }
        return out;
    }
}

class King extends Piece {
    King(Color c) { super(c); }
    char letter() { return 'K'; }
    List<Pos> pseudoMoves(Board b, Pos from) { return step(b, from, ALL); } // castling lives in Game
}

class Queen extends Piece {
    Queen(Color c) { super(c); }
    char letter() { return 'Q'; }
    List<Pos> pseudoMoves(Board b, Pos from) { return slide(b, from, ALL); }
}

class Rook extends Piece {
    Rook(Color c) { super(c); }
    char letter() { return 'R'; }
    List<Pos> pseudoMoves(Board b, Pos from) { return slide(b, from, ORTHO); }
}

class Bishop extends Piece {
    Bishop(Color c) { super(c); }
    char letter() { return 'B'; }
    List<Pos> pseudoMoves(Board b, Pos from) { return slide(b, from, DIAG); }
}

class Knight extends Piece {
    Knight(Color c) { super(c); }
    char letter() { return 'N'; }
    List<Pos> pseudoMoves(Board b, Pos from) { return step(b, from, JUMPS); }
}

class Pawn extends Piece {
    Pawn(Color c) { super(c); }
    char letter() { return 'P'; }
    int dir() { return color == Color.WHITE ? -1 : 1; }

    List<Pos> pseudoMoves(Board b, Pos from) {
        List<Pos> out = new ArrayList<>();
        Pos one = from.plus(dir(), 0);
        if (one.valid() && b.get(one) == null) {
            out.add(one);
            Pos two = from.plus(2 * dir(), 0);
            int startRow = color == Color.WHITE ? 6 : 1;
            if (from.row() == startRow && b.get(two) == null) out.add(two);
        }
        int epRow = color == Color.WHITE ? 2 : 5; // only the side to move can use the target
        for (int dc : new int[]{-1, 1}) {
            Pos diag = from.plus(dir(), dc);
            if (!diag.valid()) continue;
            Piece t = b.get(diag);
            boolean enPassant = diag.equals(b.enPassant) && diag.row() == epRow;
            if ((t != null && t.color != color) || enPassant) out.add(diag);
        }
        return out;
    }

    @Override boolean attacks(Board b, Pos from, Pos target) {
        return target.row() == from.row() + dir() && Math.abs(target.col() - from.col()) == 1;
    }
}

// ─── Board: squares plus the one bit of history a position needs ─

class Board {
    private final Piece[][] grid = new Piece[8][8];
    Pos enPassant; // square a pawn may capture onto en passant this turn, or null

    Piece get(Pos p) { return p.valid() ? grid[p.row()][p.col()] : null; }
    void set(Pos p, Piece piece) { grid[p.row()][p.col()] = piece; }

    /** Simple factory: 'K' = white king, 'k' = black king, and so on. */
    static Piece create(char ch) {
        Color c = Character.isUpperCase(ch) ? Color.WHITE : Color.BLACK;
        return switch (Character.toUpperCase(ch)) {
            case 'K' -> new King(c);
            case 'Q' -> new Queen(c);
            case 'R' -> new Rook(c);
            case 'B' -> new Bishop(c);
            case 'N' -> new Knight(c);
            case 'P' -> new Pawn(c);
            default -> throw new IllegalArgumentException("bad piece " + ch);
        };
    }

    /** Eight strings, rank 8 first, '.' for empty. */
    static Board parse(String... rows) {
        Board b = new Board();
        for (int r = 0; r < 8; r++)
            for (int c = 0; c < 8; c++)
                if (rows[r].charAt(c) != '.') b.grid[r][c] = create(rows[r].charAt(c));
        return b;
    }

    static Board standard() {
        return parse("rnbqkbnr", "pppppppp", "........", "........",
                     "........", "........", "PPPPPPPP", "RNBQKBNR");
    }

    List<Map.Entry<Pos, Piece>> pieces(Color c) {
        List<Map.Entry<Pos, Piece>> out = new ArrayList<>();
        for (int r = 0; r < 8; r++)
            for (int col = 0; col < 8; col++)
                if (grid[r][col] != null && grid[r][col].color == c)
                    out.add(Map.entry(new Pos(r, col), grid[r][col]));
        return out;
    }

    Pos findKing(Color c) {
        for (var e : pieces(c)) if (e.getValue() instanceof King) return e.getKey();
        throw new IllegalStateException("no " + c + " king");
    }

    // Simplification: asks every enemy piece, O(pieces x moves); ray-cast from the square if a bot needs speed
    boolean isAttacked(Pos sq, Color by) {
        for (var e : pieces(by)) if (e.getValue().attacks(this, e.getKey(), sq)) return true;
        return false;
    }
}

// ─── Move: a Command that can execute and undo itself ───────────

final class Move {
    final Pos from, to, captureSq, rookFrom, rookTo, newEnPassant;
    final Piece piece, promotion;
    private Piece captured;
    private boolean prevMoved, prevRookMoved;
    private Pos prevEnPassant;

    private Move(Pos from, Pos to, Piece piece, Pos captureSq, Piece promotion,
                 Pos rookFrom, Pos rookTo, Pos newEnPassant) {
        this.from = from; this.to = to; this.piece = piece; this.captureSq = captureSq;
        this.promotion = promotion; this.rookFrom = rookFrom; this.rookTo = rookTo;
        this.newEnPassant = newEnPassant;
    }

    /** Works out the side effects (en passant victim, castling rook, new en passant square). */
    static Move create(Board b, Pos from, Pos to, Piece promotion) {
        Piece piece = b.get(from);
        Pos captureSq = to, rookFrom = null, rookTo = null, ep = null;
        if (piece instanceof Pawn) {
            if (from.col() != to.col() && b.get(to) == null) captureSq = new Pos(from.row(), to.col());
            if (Math.abs(to.row() - from.row()) == 2) ep = new Pos((from.row() + to.row()) / 2, from.col());
        }
        if (piece instanceof King && Math.abs(to.col() - from.col()) == 2) {
            boolean kingside = to.col() == 6;
            rookFrom = new Pos(from.row(), kingside ? 7 : 0);
            rookTo = new Pos(from.row(), kingside ? 5 : 3);
        }
        return new Move(from, to, piece, captureSq, promotion, rookFrom, rookTo, ep);
    }

    void execute(Board b) {
        captured = b.get(captureSq);
        prevMoved = piece.hasMoved;
        prevEnPassant = b.enPassant;
        b.set(captureSq, null);
        b.set(from, null);
        b.set(to, promotion != null ? promotion : piece);
        piece.hasMoved = true;
        if (rookFrom != null) {
            Piece rook = b.get(rookFrom);
            prevRookMoved = rook.hasMoved;
            b.set(rookFrom, null);
            b.set(rookTo, rook);
            rook.hasMoved = true;
        }
        b.enPassant = newEnPassant;
    }

    void undo(Board b) {
        b.enPassant = prevEnPassant;
        if (rookFrom != null) {
            Piece rook = b.get(rookTo);
            b.set(rookTo, null);
            b.set(rookFrom, rook);
            rook.hasMoved = prevRookMoved;
        }
        b.set(to, null);
        b.set(from, piece);
        piece.hasMoved = prevMoved;
        b.set(captureSq, captured); // for a normal capture captureSq == to
    }

    Piece captured() { return captured; }
    boolean isCastling() { return rookFrom != null; }
    boolean isEnPassant() { return !captureSq.equals(to); }
    @Override public String toString() { return "" + from + to + (promotion == null ? "" : promotion.letter()); }
}

// ─── Game: turn, rules that need the whole position, history ────

class Game {
    private final Board board;
    private Color turn;
    private GameState state;
    private Color winner;
    private final Deque<Move> undoStack = new ArrayDeque<>();
    private final Deque<Move> redoStack = new ArrayDeque<>();

    Game() { this(Board.standard(), Color.WHITE); }

    Game(Board board, Color turn) {
        this.board = board;
        this.turn = turn;
        updateState();
    }

    public synchronized boolean move(String from, String to) { return move(from, to, 'Q'); }

    public synchronized boolean move(String from, String to, char promo) {
        if (isOver()) return false;
        Pos f = Pos.of(from), t = Pos.of(to);
        for (Move m : legalMoves(turn)) {
            boolean promoOk = m.promotion == null || m.promotion.letter() == Character.toUpperCase(promo);
            if (m.from.equals(f) && m.to.equals(t) && promoOk) {
                apply(m);
                redoStack.clear(); // a new move forks history
                return true;
            }
        }
        return false;
    }

    public synchronized boolean undo() {
        if (undoStack.isEmpty() || state == GameState.RESIGNED || state == GameState.DRAW) return false;
        Move m = undoStack.pop();
        m.undo(board);
        redoStack.push(m);
        turn = turn.opposite();
        updateState();
        return true;
    }

    public synchronized boolean redo() {
        if (redoStack.isEmpty() || isOver()) return false;
        apply(redoStack.pop());
        return true;
    }

    public synchronized boolean resign(Color who) {
        if (isOver()) return false;
        state = GameState.RESIGNED;
        winner = who.opposite();
        return true;
    }

    public synchronized boolean agreeDraw() {
        if (isOver()) return false;
        state = GameState.DRAW;
        return true;
    }

    private void apply(Move m) {
        m.execute(board);
        undoStack.push(m);
        turn = turn.opposite();
        updateState();
    }

    /** Pseudo-legal candidates, then keep only those that leave our own king safe. */
    List<Move> legalMoves(Color c) {
        List<Move> candidates = new ArrayList<>();
        for (var e : board.pieces(c)) {
            Pos from = e.getKey();
            Piece p = e.getValue();
            for (Pos to : p.pseudoMoves(board, from)) {
                if (p instanceof Pawn && (to.row() == 0 || to.row() == 7)) {
                    for (char ch : "QRBN".toCharArray()) {
                        Piece promo = Board.create(c == Color.WHITE ? ch : Character.toLowerCase(ch));
                        promo.hasMoved = true;
                        candidates.add(Move.create(board, from, to, promo));
                    }
                } else {
                    candidates.add(Move.create(board, from, to, null));
                }
            }
        }
        addCastling(c, candidates);
        List<Move> legal = new ArrayList<>();
        for (Move m : candidates) {
            m.execute(board);
            if (!board.isAttacked(board.findKing(c), c.opposite())) legal.add(m);
            m.undo(board);
        }
        return legal;
    }

    private void addCastling(Color c, List<Move> out) {
        int row = c == Color.WHITE ? 7 : 0;
        Pos kingPos = new Pos(row, 4);
        Piece king = board.get(kingPos);
        if (!(king instanceof King) || king.color != c || king.hasMoved) return;
        if (board.isAttacked(kingPos, c.opposite())) return; // no castling out of check
        tryCastle(c, row, 7, new int[]{5, 6}, new int[]{5, 6}, out);
        tryCastle(c, row, 0, new int[]{1, 2, 3}, new int[]{3, 2}, out);
    }

    private void tryCastle(Color c, int row, int rookCol, int[] mustBeEmpty, int[] kingPath, List<Move> out) {
        Piece rook = board.get(new Pos(row, rookCol));
        if (!(rook instanceof Rook) || rook.color != c || rook.hasMoved) return;
        for (int col : mustBeEmpty) if (board.get(new Pos(row, col)) != null) return;
        for (int col : kingPath) if (board.isAttacked(new Pos(row, col), c.opposite())) return; // not through check
        out.add(Move.create(board, new Pos(row, 4), new Pos(row, kingPath[kingPath.length - 1]), null));
    }

    private void updateState() {
        boolean inCheck = board.isAttacked(board.findKing(turn), turn.opposite());
        boolean canMove = !legalMoves(turn).isEmpty();
        winner = null;
        if (!canMove && inCheck) { state = GameState.CHECKMATE; winner = turn.opposite(); }
        else if (!canMove) state = GameState.STALEMATE;
        else state = inCheck ? GameState.CHECK : GameState.ACTIVE;
    }

    boolean isOver() {
        return state == GameState.CHECKMATE || state == GameState.STALEMATE
            || state == GameState.RESIGNED || state == GameState.DRAW;
    }

    public synchronized GameState state() { return state; }
    public synchronized Color winner() { return winner; }
    public synchronized Color turn() { return turn; }
    public synchronized int ply() { return undoStack.size(); }
    public synchronized char at(String sq) { Piece p = board.get(Pos.of(sq)); return p == null ? '.' : p.symbol(); }
    Board board() { return board; }
}

public class Chess {
    static long perft(Game g, Color c, int depth) {
        if (depth == 0) return 1;
        long n = 0;
        for (Move m : g.legalMoves(c)) {
            m.execute(g.board());
            n += perft(g, c.opposite(), depth - 1);
            m.undo(g.board());
        }
        return n;
    }

    public static void main(String[] args) {
        boolean ea = false;
        assert ea = true;
        if (!ea) throw new AssertionError("run with java -ea");

        // Move generator vs published perft counts (start position, then "Kiwipete")
        Game start = new Game();
        assert perft(start, Color.WHITE, 1) == 20;
        assert perft(start, Color.WHITE, 2) == 400;
        assert perft(start, Color.WHITE, 3) == 8902;
        Game kiwi = new Game(Board.parse("r...k..r", "p.ppqpb.", "bn..pnp.", "...PN...",
                                         ".p..P...", "..N..Q.p", "PPPBBPPP", "R...K..R"), Color.WHITE);
        assert perft(kiwi, Color.WHITE, 1) == 48;
        assert perft(kiwi, Color.WHITE, 2) == 2039;

        // Fool's mate
        Game g = new Game();
        assert g.move("f2", "f3") && g.move("e7", "e5") && g.move("g2", "g4") && g.move("d8", "h4");
        assert g.state() == GameState.CHECKMATE && g.winner() == Color.BLACK;
        assert !g.move("a2", "a3");

        // Undo restores the captured piece, redo replays, a new move clears redo
        g = new Game();
        assert g.move("e2", "e4") && g.move("d7", "d5") && g.move("e4", "d5");
        assert g.at("d5") == 'P';
        assert g.undo() && g.at("d5") == 'p' && g.at("e4") == 'P' && g.turn() == Color.WHITE;
        assert g.redo() && g.at("d5") == 'P' && g.turn() == Color.BLACK;
        assert g.undo() && g.move("a2", "a3") && !g.redo();

        // Stalemate: Qg5-g6 leaves the black king on h8 with no legal move and not in check
        g = new Game(Board.parse(".......k", ".....K..", "........", "......Q.",
                                 "........", "........", "........", "........"), Color.WHITE);
        assert g.move("g5", "g6") && g.state() == GameState.STALEMATE && g.winner() == null;

        // A pinned bishop cannot move
        g = new Game(Board.parse("k...r...", "........", "........", "........",
                                 "........", "........", "....B...", "....K..."), Color.WHITE);
        assert !g.move("e2", "d3") && g.move("e1", "d1");

        // Castling: blocked through an attacked square, legal otherwise, undo restores rights
        g = new Game(Board.parse("k....r..", "........", "........", "........",
                                 "........", "........", "........", "....K..R"), Color.WHITE);
        assert !g.move("e1", "g1");
        g = new Game(Board.parse("k.......", "........", "........", "........",
                                 "........", "........", "........", "....K..R"), Color.WHITE);
        assert g.move("e1", "g1") && g.at("f1") == 'R' && g.at("g1") == 'K';
        assert g.undo() && g.at("e1") == 'K' && g.at("h1") == 'R';
        assert g.move("e1", "g1");

        // En passant, and undo puts the captured pawn back
        g = new Game(Board.parse("k.......", "...p....", "........", "....P...",
                                 "........", "........", "........", "....K..."), Color.BLACK);
        assert g.move("d7", "d5") && g.move("e5", "d6");
        assert g.at("d5") == '.' && g.at("d6") == 'P';
        assert g.undo() && g.at("d5") == 'p' && g.at("e5") == 'P' && g.at("d6") == '.';

        // Promotion with a chosen piece, undone back to a pawn
        g = new Game(Board.parse("........", "P.......", "........", ".......k",
                                 "........", "........", "........", "K......."), Color.WHITE);
        assert g.move("a7", "a8", 'N') && g.at("a8") == 'N';
        assert g.undo() && g.at("a7") == 'P' && g.at("a8") == '.';

        // Resignation is terminal
        g = new Game();
        assert g.resign(Color.WHITE) && g.state() == GameState.RESIGNED && g.winner() == Color.BLACK;
        assert !g.move("e2", "e4") && !g.undo();

        System.out.println("all chess tests passed");
    }
}
from __future__ import annotations

import threading
from abc import ABC, abstractmethod
from dataclasses import dataclass
from enum import Enum


class Color(Enum):
    WHITE = "WHITE"
    BLACK = "BLACK"

    def opposite(self) -> Color:
        return Color.BLACK if self is Color.WHITE else Color.WHITE


class GameState(Enum):
    ACTIVE = "ACTIVE"
    CHECK = "CHECK"
    CHECKMATE = "CHECKMATE"
    STALEMATE = "STALEMATE"
    RESIGNED = "RESIGNED"
    DRAW = "DRAW"


@dataclass(frozen=True)
class Pos:
    """Row 0 is rank 8 (Black's back rank), row 7 is rank 1."""
    row: int
    col: int

    @staticmethod
    def of(sq: str) -> Pos:
        return Pos(8 - int(sq[1]), ord(sq[0]) - ord("a"))

    def valid(self) -> bool:
        return 0 <= self.row < 8 and 0 <= self.col < 8

    def plus(self, dr: int, dc: int) -> Pos:
        return Pos(self.row + dr, self.col + dc)

    def __str__(self) -> str:
        return f"{chr(ord('a') + self.col)}{8 - self.row}"


# ─── Pieces: each one knows only its own geometry ───────────────

ORTHO = [(1, 0), (-1, 0), (0, 1), (0, -1)]
DIAG = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
ALL = ORTHO + DIAG
JUMPS = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]


class Piece(ABC):
    letter = "?"

    def __init__(self, color: Color):
        self.color = color
        self.has_moved = False

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

    @abstractmethod
    def pseudo_moves(self, b: Board, frm: Pos) -> list[Pos]:
        """Destinations by the piece's own rules, ignoring whether our king is left in check."""

    def attacks(self, b: Board, frm: Pos, target: Pos) -> bool:
        return target in self.pseudo_moves(b, frm)

    def _slide(self, b: Board, frm: Pos, dirs) -> list[Pos]:
        out = []
        for dr, dc in dirs:
            p = frm.plus(dr, dc)
            while p.valid():
                t = b.get(p)
                if t is None:
                    out.append(p)
                    p = p.plus(dr, dc)
                    continue
                if t.color is not self.color:
                    out.append(p)
                break
        return out

    def _step(self, b: Board, frm: Pos, offsets) -> list[Pos]:
        out = []
        for dr, dc in offsets:
            p = frm.plus(dr, dc)
            if p.valid() and (b.get(p) is None or b.get(p).color is not self.color):
                out.append(p)
        return out


class King(Piece):
    letter = "K"

    def pseudo_moves(self, b, frm):
        return self._step(b, frm, ALL)  # castling lives in Game


class Queen(Piece):
    letter = "Q"

    def pseudo_moves(self, b, frm):
        return self._slide(b, frm, ALL)


class Rook(Piece):
    letter = "R"

    def pseudo_moves(self, b, frm):
        return self._slide(b, frm, ORTHO)


class Bishop(Piece):
    letter = "B"

    def pseudo_moves(self, b, frm):
        return self._slide(b, frm, DIAG)


class Knight(Piece):
    letter = "N"

    def pseudo_moves(self, b, frm):
        return self._step(b, frm, JUMPS)


class Pawn(Piece):
    letter = "P"

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

    def pseudo_moves(self, b, frm):
        out = []
        one = frm.plus(self.dir, 0)
        if one.valid() and b.get(one) is None:
            out.append(one)
            two = frm.plus(2 * self.dir, 0)
            start_row = 6 if self.color is Color.WHITE else 1
            if frm.row == start_row and b.get(two) is None:
                out.append(two)
        ep_row = 2 if self.color is Color.WHITE else 5  # only the side to move can use the target
        for dc in (-1, 1):
            diag = frm.plus(self.dir, dc)
            if not diag.valid():
                continue
            t = b.get(diag)
            en_passant = diag == b.en_passant and diag.row == ep_row
            if (t is not None and t.color is not self.color) or en_passant:
                out.append(diag)
        return out

    def attacks(self, b, frm, target):
        return target.row == frm.row + self.dir and abs(target.col - frm.col) == 1


# ─── Board: squares plus the one bit of history a position needs ─

PIECE_TYPES = {cls.letter: cls for cls in (King, Queen, Rook, Bishop, Knight, Pawn)}


class Board:
    def __init__(self):
        self._grid: list[list[Piece | None]] = [[None] * 8 for _ in range(8)]
        self.en_passant: Pos | None = None

    def get(self, p: Pos) -> Piece | None:
        return self._grid[p.row][p.col] if p.valid() else None

    def set(self, p: Pos, piece: Piece | None) -> None:
        self._grid[p.row][p.col] = piece

    @staticmethod
    def create(ch: str) -> Piece:
        """Simple factory: 'K' = white king, 'k' = black king, and so on."""
        color = Color.WHITE if ch.isupper() else Color.BLACK
        return PIECE_TYPES[ch.upper()](color)

    @staticmethod
    def parse(*rows: str) -> Board:
        """Eight strings, rank 8 first, '.' for empty."""
        b = Board()
        for r, line in enumerate(rows):
            for c, ch in enumerate(line):
                if ch != ".":
                    b._grid[r][c] = Board.create(ch)
        return b

    @staticmethod
    def standard() -> Board:
        return Board.parse("rnbqkbnr", "pppppppp", "........", "........",
                           "........", "........", "PPPPPPPP", "RNBQKBNR")

    def pieces(self, color: Color) -> list[tuple[Pos, Piece]]:
        return [(Pos(r, c), p) for r in range(8) for c in range(8)
                if (p := self._grid[r][c]) is not None and p.color is color]

    def find_king(self, color: Color) -> Pos:
        for pos, p in self.pieces(color):
            if isinstance(p, King):
                return pos
        raise RuntimeError(f"no {color} king")

    # Simplification: asks every enemy piece, O(pieces x moves); ray-cast from the square if a bot needs speed
    def is_attacked(self, sq: Pos, by: Color) -> bool:
        return any(p.attacks(self, pos, sq) for pos, p in self.pieces(by))


# ─── Move: a Command that can execute and undo itself ───────────

class Move:
    def __init__(self, frm, to, piece, capture_sq, promotion, rook_from, rook_to, new_ep):
        self.frm, self.to, self.piece = frm, to, piece
        self.capture_sq, self.promotion = capture_sq, promotion
        self.rook_from, self.rook_to, self.new_ep = rook_from, rook_to, new_ep
        self.captured: Piece | None = None
        self._prev_moved = self._prev_rook_moved = False
        self._prev_ep: Pos | None = None

    @staticmethod
    def create(b: Board, frm: Pos, to: Pos, promotion: Piece | None = None) -> Move:
        """Works out the side effects (en passant victim, castling rook, new en passant square)."""
        piece = b.get(frm)
        capture_sq, rook_from, rook_to, ep = to, None, None, None
        if isinstance(piece, Pawn):
            if frm.col != to.col and b.get(to) is None:
                capture_sq = Pos(frm.row, to.col)
            if abs(to.row - frm.row) == 2:
                ep = Pos((frm.row + to.row) // 2, frm.col)
        if isinstance(piece, King) and abs(to.col - frm.col) == 2:
            kingside = to.col == 6
            rook_from = Pos(frm.row, 7 if kingside else 0)
            rook_to = Pos(frm.row, 5 if kingside else 3)
        return Move(frm, to, piece, capture_sq, promotion, rook_from, rook_to, ep)

    def execute(self, b: Board) -> None:
        self.captured = b.get(self.capture_sq)
        self._prev_moved = self.piece.has_moved
        self._prev_ep = b.en_passant
        b.set(self.capture_sq, None)
        b.set(self.frm, None)
        b.set(self.to, self.promotion or self.piece)
        self.piece.has_moved = True
        if self.rook_from:
            rook = b.get(self.rook_from)
            self._prev_rook_moved = rook.has_moved
            b.set(self.rook_from, None)
            b.set(self.rook_to, rook)
            rook.has_moved = True
        b.en_passant = self.new_ep

    def undo(self, b: Board) -> None:
        b.en_passant = self._prev_ep
        if self.rook_from:
            rook = b.get(self.rook_to)
            b.set(self.rook_to, None)
            b.set(self.rook_from, rook)
            rook.has_moved = self._prev_rook_moved
        b.set(self.to, None)
        b.set(self.frm, self.piece)
        self.piece.has_moved = self._prev_moved
        b.set(self.capture_sq, self.captured)  # for a normal capture capture_sq == to

    def __str__(self) -> str:
        return f"{self.frm}{self.to}{self.promotion.letter if self.promotion else ''}"


# ─── Game: turn, rules that need the whole position, history ────

class Game:
    def __init__(self, board: Board | None = None, turn: Color = Color.WHITE):
        self.board = board or Board.standard()
        self.turn = turn
        self.state = GameState.ACTIVE
        self.winner: Color | None = None
        self._undo: list[Move] = []
        self._redo: list[Move] = []
        self._lock = threading.RLock()
        self._update_state()

    def move(self, frm: str, to: str, promo: str = "Q") -> bool:
        with self._lock:
            if self.is_over():
                return False
            f, t = Pos.of(frm), Pos.of(to)
            for m in self.legal_moves(self.turn):
                promo_ok = m.promotion is None or m.promotion.letter == promo.upper()
                if m.frm == f and m.to == t and promo_ok:
                    self._apply(m)
                    self._redo.clear()  # a new move forks history
                    return True
            return False

    def undo(self) -> bool:
        with self._lock:
            if not self._undo or self.state in (GameState.RESIGNED, GameState.DRAW):
                return False
            m = self._undo.pop()
            m.undo(self.board)
            self._redo.append(m)
            self.turn = self.turn.opposite()
            self._update_state()
            return True

    def redo(self) -> bool:
        with self._lock:
            if not self._redo or self.is_over():
                return False
            self._apply(self._redo.pop())
            return True

    def resign(self, who: Color) -> bool:
        with self._lock:
            if self.is_over():
                return False
            self.state, self.winner = GameState.RESIGNED, who.opposite()
            return True

    def agree_draw(self) -> bool:
        with self._lock:
            if self.is_over():
                return False
            self.state = GameState.DRAW
            return True

    def _apply(self, m: Move) -> None:
        m.execute(self.board)
        self._undo.append(m)
        self.turn = self.turn.opposite()
        self._update_state()

    def legal_moves(self, color: Color) -> list[Move]:
        """Pseudo-legal candidates, then keep only those that leave our own king safe."""
        candidates: list[Move] = []
        for frm, p in self.board.pieces(color):
            for to in p.pseudo_moves(self.board, frm):
                if isinstance(p, Pawn) and to.row in (0, 7):
                    for ch in "QRBN":
                        promo = Board.create(ch if color is Color.WHITE else ch.lower())
                        promo.has_moved = True
                        candidates.append(Move.create(self.board, frm, to, promo))
                else:
                    candidates.append(Move.create(self.board, frm, to))
        self._add_castling(color, candidates)
        legal = []
        for m in candidates:
            m.execute(self.board)
            if not self.board.is_attacked(self.board.find_king(color), color.opposite()):
                legal.append(m)
            m.undo(self.board)
        return legal

    def _add_castling(self, color: Color, out: list[Move]) -> None:
        row = 7 if color is Color.WHITE else 0
        king_pos = Pos(row, 4)
        king = self.board.get(king_pos)
        if not isinstance(king, King) or king.color is not color or king.has_moved:
            return
        if self.board.is_attacked(king_pos, color.opposite()):
            return  # no castling out of check
        self._try_castle(color, row, 7, (5, 6), (5, 6), out)
        self._try_castle(color, row, 0, (1, 2, 3), (3, 2), out)

    def _try_castle(self, color, row, rook_col, must_be_empty, king_path, out) -> None:
        rook = self.board.get(Pos(row, rook_col))
        if not isinstance(rook, Rook) or rook.color is not color or rook.has_moved:
            return
        if any(self.board.get(Pos(row, c)) is not None for c in must_be_empty):
            return
        if any(self.board.is_attacked(Pos(row, c), color.opposite()) for c in king_path):
            return  # not through check
        out.append(Move.create(self.board, Pos(row, 4), Pos(row, king_path[-1])))

    def _update_state(self) -> None:
        in_check = self.board.is_attacked(self.board.find_king(self.turn), self.turn.opposite())
        can_move = bool(self.legal_moves(self.turn))
        self.winner = None
        if not can_move and in_check:
            self.state, self.winner = GameState.CHECKMATE, self.turn.opposite()
        elif not can_move:
            self.state = GameState.STALEMATE
        else:
            self.state = GameState.CHECK if in_check else GameState.ACTIVE

    def is_over(self) -> bool:
        return self.state in (GameState.CHECKMATE, GameState.STALEMATE,
                              GameState.RESIGNED, GameState.DRAW)

    @property
    def ply(self) -> int:
        return len(self._undo)

    def at(self, sq: str) -> str:
        p = self.board.get(Pos.of(sq))
        return p.symbol if p else "."


# ─── Tests ──────────────────────────────────────────────────────

def perft(g: Game, color: Color, depth: int) -> int:
    if depth == 0:
        return 1
    n = 0
    for m in g.legal_moves(color):
        m.execute(g.board)
        n += perft(g, color.opposite(), depth - 1)
        m.undo(g.board)
    return n


if __name__ == "__main__":
    start = Game()
    assert perft(start, Color.WHITE, 1) == 20
    assert perft(start, Color.WHITE, 2) == 400
    assert perft(start, Color.WHITE, 3) == 8902
    kiwi = Game(Board.parse("r...k..r", "p.ppqpb.", "bn..pnp.", "...PN...",
                            ".p..P...", "..N..Q.p", "PPPBBPPP", "R...K..R"))
    assert perft(kiwi, Color.WHITE, 1) == 48
    assert perft(kiwi, Color.WHITE, 2) == 2039

    # Fool's mate
    g = Game()
    assert g.move("f2", "f3") and g.move("e7", "e5") and g.move("g2", "g4") and g.move("d8", "h4")
    assert g.state is GameState.CHECKMATE and g.winner is Color.BLACK
    assert not g.move("a2", "a3")

    # Undo restores the captured piece, redo replays, a new move clears redo
    g = Game()
    assert g.move("e2", "e4") and g.move("d7", "d5") and g.move("e4", "d5")
    assert g.at("d5") == "P"
    assert g.undo() and g.at("d5") == "p" and g.at("e4") == "P" and g.turn is Color.WHITE
    assert g.redo() and g.at("d5") == "P" and g.turn is Color.BLACK
    assert g.undo() and g.move("a2", "a3") and not g.redo()

    # Stalemate
    g = Game(Board.parse(".......k", ".....K..", "........", "......Q.",
                         "........", "........", "........", "........"))
    assert g.move("g5", "g6") and g.state is GameState.STALEMATE and g.winner is None

    # A pinned bishop cannot move
    g = Game(Board.parse("k...r...", "........", "........", "........",
                         "........", "........", "....B...", "....K..."))
    assert not g.move("e2", "d3") and g.move("e1", "d1")

    # Castling through an attacked square is illegal, otherwise fine, undo restores rights
    g = Game(Board.parse("k....r..", "........", "........", "........",
                         "........", "........", "........", "....K..R"))
    assert not g.move("e1", "g1")
    g = Game(Board.parse("k.......", "........", "........", "........",
                         "........", "........", "........", "....K..R"))
    assert g.move("e1", "g1") and g.at("f1") == "R" and g.at("g1") == "K"
    assert g.undo() and g.at("e1") == "K" and g.at("h1") == "R"
    assert g.move("e1", "g1")

    # En passant
    g = Game(Board.parse("k.......", "...p....", "........", "....P...",
                         "........", "........", "........", "....K..."), Color.BLACK)
    assert g.move("d7", "d5") and g.move("e5", "d6")
    assert g.at("d5") == "." and g.at("d6") == "P"
    assert g.undo() and g.at("d5") == "p" and g.at("e5") == "P" and g.at("d6") == "."

    # Promotion
    g = Game(Board.parse("........", "P.......", "........", ".......k",
                         "........", "........", "........", "K......."))
    assert g.move("a7", "a8", "N") and g.at("a8") == "N"
    assert g.undo() and g.at("a7") == "P" and g.at("a8") == "."

    # Resignation is terminal
    g = Game()
    assert g.resign(Color.WHITE) and g.state is GameState.RESIGNED and g.winner is Color.BLACK
    assert not g.move("e2", "e4") and not g.undo()

    print("all chess tests passed")
enum Color { WHITE = "WHITE", BLACK = "BLACK" }
const opposite = (c: Color): Color => (c === Color.WHITE ? Color.BLACK : Color.WHITE);

enum GameState {
  ACTIVE = "ACTIVE", CHECK = "CHECK", CHECKMATE = "CHECKMATE",
  STALEMATE = "STALEMATE", RESIGNED = "RESIGNED", DRAW = "DRAW",
}

/** Immutable square. Row 0 is rank 8 (Black's back rank), row 7 is rank 1. */
class Pos {
  constructor(readonly row: number, readonly col: number) {}
  static of(sq: string): Pos {
    return new Pos(8 - Number(sq[1]), sq.charCodeAt(0) - 97);
  }
  valid(): boolean { return this.row >= 0 && this.row < 8 && this.col >= 0 && this.col < 8; }
  plus(dr: number, dc: number): Pos { return new Pos(this.row + dr, this.col + dc); }
  equals(o: Pos | null): boolean { return o !== null && o.row === this.row && o.col === this.col; }
  toString(): string { return String.fromCharCode(97 + this.col) + (8 - this.row); }
}

type Dir = readonly [number, number];
const ORTHO: Dir[] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const DIAG: Dir[] = [[1, 1], [1, -1], [-1, 1], [-1, -1]];
const ALL: Dir[] = [...ORTHO, ...DIAG];
const JUMPS: Dir[] = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]];

// ─── Pieces: each one knows only its own geometry ───────────────

abstract class Piece {
  hasMoved = false;
  constructor(readonly color: Color) {}
  abstract readonly letter: string;

  get symbol(): string {
    return this.color === Color.WHITE ? this.letter : this.letter.toLowerCase();
  }

  /** Destinations by the piece's own rules, ignoring whether our king is left in check. */
  abstract pseudoMoves(b: Board, from: Pos): Pos[];

  attacks(b: Board, from: Pos, target: Pos): boolean {
    return this.pseudoMoves(b, from).some((p) => p.equals(target));
  }

  protected slide(b: Board, from: Pos, dirs: Dir[]): Pos[] {
    const out: Pos[] = [];
    for (const [dr, dc] of dirs) {
      for (let p = from.plus(dr, dc); p.valid(); p = p.plus(dr, dc)) {
        const t = b.get(p);
        if (t === null) { out.push(p); continue; }
        if (t.color !== this.color) out.push(p);
        break;
      }
    }
    return out;
  }

  protected step(b: Board, from: Pos, offsets: Dir[]): Pos[] {
    return offsets
      .map(([dr, dc]) => from.plus(dr, dc))
      .filter((p) => p.valid() && (b.get(p) === null || b.get(p)!.color !== this.color));
  }
}

class King extends Piece {
  readonly letter = "K";
  pseudoMoves(b: Board, from: Pos): Pos[] { return this.step(b, from, ALL); } // castling lives in Game
}
class Queen extends Piece {
  readonly letter = "Q";
  pseudoMoves(b: Board, from: Pos): Pos[] { return this.slide(b, from, ALL); }
}
class Rook extends Piece {
  readonly letter = "R";
  pseudoMoves(b: Board, from: Pos): Pos[] { return this.slide(b, from, ORTHO); }
}
class Bishop extends Piece {
  readonly letter = "B";
  pseudoMoves(b: Board, from: Pos): Pos[] { return this.slide(b, from, DIAG); }
}
class Knight extends Piece {
  readonly letter = "N";
  pseudoMoves(b: Board, from: Pos): Pos[] { return this.step(b, from, JUMPS); }
}

class Pawn extends Piece {
  readonly letter = "P";
  get dir(): number { return this.color === Color.WHITE ? -1 : 1; }

  pseudoMoves(b: Board, from: Pos): Pos[] {
    const out: Pos[] = [];
    const one = from.plus(this.dir, 0);
    if (one.valid() && b.get(one) === null) {
      out.push(one);
      const two = from.plus(2 * this.dir, 0);
      const startRow = this.color === Color.WHITE ? 6 : 1;
      if (from.row === startRow && b.get(two) === null) out.push(two);
    }
    const epRow = this.color === Color.WHITE ? 2 : 5; // only the side to move can use the target
    for (const dc of [-1, 1]) {
      const diag = from.plus(this.dir, dc);
      if (!diag.valid()) continue;
      const t = b.get(diag);
      const enPassant = diag.equals(b.enPassant) && diag.row === epRow;
      if ((t !== null && t.color !== this.color) || enPassant) out.push(diag);
    }
    return out;
  }

  override attacks(_b: Board, from: Pos, target: Pos): boolean {
    return target.row === from.row + this.dir && Math.abs(target.col - from.col) === 1;
  }
}

// ─── Board: squares plus the one bit of history a position needs ─

const PIECE_TYPES: Record<string, new (c: Color) => Piece> = {
  K: King, Q: Queen, R: Rook, B: Bishop, N: Knight, P: Pawn,
};

class Board {
  private grid: (Piece | null)[][] = Array.from({ length: 8 }, () => Array<Piece | null>(8).fill(null));
  enPassant: Pos | null = null; // square a pawn may capture onto en passant this turn

  get(p: Pos): Piece | null { return p.valid() ? this.grid[p.row][p.col] : null; }
  set(p: Pos, piece: Piece | null): void { this.grid[p.row][p.col] = piece; }

  /** Simple factory: 'K' = white king, 'k' = black king, and so on. */
  static create(ch: string): Piece {
    const color = ch === ch.toUpperCase() ? Color.WHITE : Color.BLACK;
    const ctor = PIECE_TYPES[ch.toUpperCase()];
    if (!ctor) throw new Error(`bad piece ${ch}`);
    return new ctor(color);
  }

  /** Eight strings, rank 8 first, '.' for empty. */
  static parse(...rows: string[]): Board {
    const b = new Board();
    rows.forEach((line, r) => [...line].forEach((ch, c) => {
      if (ch !== ".") b.grid[r][c] = Board.create(ch);
    }));
    return b;
  }

  static standard(): Board {
    return Board.parse("rnbqkbnr", "pppppppp", "........", "........",
                       "........", "........", "PPPPPPPP", "RNBQKBNR");
  }

  pieces(color: Color): [Pos, Piece][] {
    const out: [Pos, Piece][] = [];
    for (let r = 0; r < 8; r++)
      for (let c = 0; c < 8; c++) {
        const p = this.grid[r][c];
        if (p !== null && p.color === color) out.push([new Pos(r, c), p]);
      }
    return out;
  }

  findKing(color: Color): Pos {
    const hit = this.pieces(color).find(([, p]) => p instanceof King);
    if (!hit) throw new Error(`no ${color} king`);
    return hit[0];
  }

  // Simplification: asks every enemy piece, O(pieces x moves); ray-cast from the square if a bot needs speed
  isAttacked(sq: Pos, by: Color): boolean {
    return this.pieces(by).some(([pos, p]) => p.attacks(this, pos, sq));
  }
}

// ─── Move: a Command that can execute and undo itself ───────────

class Move {
  captured: Piece | null = null;
  private prevMoved = false;
  private prevRookMoved = false;
  private prevEnPassant: Pos | null = null;

  private constructor(
    readonly from: Pos, readonly to: Pos, readonly piece: Piece,
    readonly captureSq: Pos, readonly promotion: Piece | null,
    readonly rookFrom: Pos | null, readonly rookTo: Pos | null,
    readonly newEnPassant: Pos | null,
  ) {}

  /** Works out the side effects (en passant victim, castling rook, new en passant square). */
  static create(b: Board, from: Pos, to: Pos, promotion: Piece | null = null): Move {
    const piece = b.get(from);
    if (!piece) throw new Error(`no piece on ${from}`);
    let captureSq = to;
    let rookFrom: Pos | null = null, rookTo: Pos | null = null, ep: Pos | null = null;
    if (piece instanceof Pawn) {
      if (from.col !== to.col && b.get(to) === null) captureSq = new Pos(from.row, to.col);
      if (Math.abs(to.row - from.row) === 2) ep = new Pos((from.row + to.row) / 2, from.col);
    }
    if (piece instanceof King && Math.abs(to.col - from.col) === 2) {
      const kingside = to.col === 6;
      rookFrom = new Pos(from.row, kingside ? 7 : 0);
      rookTo = new Pos(from.row, kingside ? 5 : 3);
    }
    return new Move(from, to, piece, captureSq, promotion, rookFrom, rookTo, ep);
  }

  execute(b: Board): void {
    this.captured = b.get(this.captureSq);
    this.prevMoved = this.piece.hasMoved;
    this.prevEnPassant = b.enPassant;
    b.set(this.captureSq, null);
    b.set(this.from, null);
    b.set(this.to, this.promotion ?? this.piece);
    this.piece.hasMoved = true;
    if (this.rookFrom && this.rookTo) {
      const rook = b.get(this.rookFrom)!;
      this.prevRookMoved = rook.hasMoved;
      b.set(this.rookFrom, null);
      b.set(this.rookTo, rook);
      rook.hasMoved = true;
    }
    b.enPassant = this.newEnPassant;
  }

  undo(b: Board): void {
    b.enPassant = this.prevEnPassant;
    if (this.rookFrom && this.rookTo) {
      const rook = b.get(this.rookTo)!;
      b.set(this.rookTo, null);
      b.set(this.rookFrom, rook);
      rook.hasMoved = this.prevRookMoved;
    }
    b.set(this.to, null);
    b.set(this.from, this.piece);
    this.piece.hasMoved = this.prevMoved;
    b.set(this.captureSq, this.captured); // for a normal capture captureSq == to
  }

  toString(): string { return `${this.from}${this.to}${this.promotion?.letter ?? ""}`; }
}

// ─── Game: turn, rules that need the whole position, history ────

class Game {
  state: GameState = GameState.ACTIVE;
  winner: Color | null = null;
  private undoStack: Move[] = [];
  private redoStack: Move[] = [];

  constructor(readonly board: Board = Board.standard(), public turn: Color = Color.WHITE) {
    this.updateState();
  }

  move(from: string, to: string, promo = "Q"): boolean {
    if (this.isOver()) return false;
    const f = Pos.of(from), t = Pos.of(to);
    const m = this.legalMoves(this.turn).find((c) =>
      c.from.equals(f) && c.to.equals(t) && (c.promotion === null || c.promotion.letter === promo.toUpperCase()));
    if (!m) return false;
    this.apply(m);
    this.redoStack = []; // a new move forks history
    return true;
  }

  undo(): boolean {
    if (this.undoStack.length === 0 || this.state === GameState.RESIGNED || this.state === GameState.DRAW) return false;
    const m = this.undoStack.pop()!;
    m.undo(this.board);
    this.redoStack.push(m);
    this.turn = opposite(this.turn);
    this.updateState();
    return true;
  }

  redo(): boolean {
    if (this.redoStack.length === 0 || this.isOver()) return false;
    this.apply(this.redoStack.pop()!);
    return true;
  }

  resign(who: Color): boolean {
    if (this.isOver()) return false;
    this.state = GameState.RESIGNED;
    this.winner = opposite(who);
    return true;
  }

  agreeDraw(): boolean {
    if (this.isOver()) return false;
    this.state = GameState.DRAW;
    return true;
  }

  private apply(m: Move): void {
    m.execute(this.board);
    this.undoStack.push(m);
    this.turn = opposite(this.turn);
    this.updateState();
  }

  /** Pseudo-legal candidates, then keep only those that leave our own king safe. */
  legalMoves(color: Color): Move[] {
    const candidates: Move[] = [];
    for (const [from, p] of this.board.pieces(color)) {
      for (const to of p.pseudoMoves(this.board, from)) {
        if (p instanceof Pawn && (to.row === 0 || to.row === 7)) {
          for (const ch of "QRBN") {
            const promo = Board.create(color === Color.WHITE ? ch : ch.toLowerCase());
            promo.hasMoved = true;
            candidates.push(Move.create(this.board, from, to, promo));
          }
        } else {
          candidates.push(Move.create(this.board, from, to));
        }
      }
    }
    this.addCastling(color, candidates);
    return candidates.filter((m) => {
      m.execute(this.board);
      const safe = !this.board.isAttacked(this.board.findKing(color), opposite(color));
      m.undo(this.board);
      return safe;
    });
  }

  private addCastling(color: Color, out: Move[]): void {
    const row = color === Color.WHITE ? 7 : 0;
    const kingPos = new Pos(row, 4);
    const king = this.board.get(kingPos);
    if (!(king instanceof King) || king.color !== color || king.hasMoved) return;
    if (this.board.isAttacked(kingPos, opposite(color))) return; // no castling out of check
    this.tryCastle(color, row, 7, [5, 6], [5, 6], out);
    this.tryCastle(color, row, 0, [1, 2, 3], [3, 2], out);
  }

  private tryCastle(color: Color, row: number, rookCol: number,
                    mustBeEmpty: number[], kingPath: number[], out: Move[]): void {
    const rook = this.board.get(new Pos(row, rookCol));
    if (!(rook instanceof Rook) || rook.color !== color || rook.hasMoved) return;
    if (mustBeEmpty.some((c) => this.board.get(new Pos(row, c)) !== null)) return;
    if (kingPath.some((c) => this.board.isAttacked(new Pos(row, c), opposite(color)))) return; // not through check
    out.push(Move.create(this.board, new Pos(row, 4), new Pos(row, kingPath[kingPath.length - 1])));
  }

  private updateState(): void {
    const inCheck = this.board.isAttacked(this.board.findKing(this.turn), opposite(this.turn));
    const canMove = this.legalMoves(this.turn).length > 0;
    this.winner = null;
    if (!canMove && inCheck) { this.state = GameState.CHECKMATE; this.winner = opposite(this.turn); }
    else if (!canMove) this.state = GameState.STALEMATE;
    else this.state = inCheck ? GameState.CHECK : GameState.ACTIVE;
  }

  isOver(): boolean {
    return [GameState.CHECKMATE, GameState.STALEMATE, GameState.RESIGNED, GameState.DRAW].includes(this.state);
  }

  get ply(): number { return this.undoStack.length; }

  at(sq: string): string { return this.board.get(Pos.of(sq))?.symbol ?? "."; }
}

// ─── Tests ──────────────────────────────────────────────────────

function assert(cond: boolean, msg = "assertion failed"): void {
  if (!cond) throw new Error(msg);
}

function perft(g: Game, color: Color, depth: number): number {
  if (depth === 0) return 1;
  let n = 0;
  for (const m of g.legalMoves(color)) {
    m.execute(g.board);
    n += perft(g, opposite(color), depth - 1);
    m.undo(g.board);
  }
  return n;
}

const start = new Game();
assert(perft(start, Color.WHITE, 1) === 20);
assert(perft(start, Color.WHITE, 2) === 400);
assert(perft(start, Color.WHITE, 3) === 8902);
const kiwi = new Game(Board.parse("r...k..r", "p.ppqpb.", "bn..pnp.", "...PN...",
                                  ".p..P...", "..N..Q.p", "PPPBBPPP", "R...K..R"));
assert(perft(kiwi, Color.WHITE, 1) === 48);
assert(perft(kiwi, Color.WHITE, 2) === 2039);

// Fool's mate
let g = new Game();
assert(g.move("f2", "f3") && g.move("e7", "e5") && g.move("g2", "g4") && g.move("d8", "h4"));
assert(g.state === GameState.CHECKMATE && g.winner === Color.BLACK);
assert(!g.move("a2", "a3"));

// Undo restores the captured piece, redo replays, a new move clears redo
g = new Game();
assert(g.move("e2", "e4") && g.move("d7", "d5") && g.move("e4", "d5"));
assert(g.at("d5") === "P");
assert(g.undo() && g.at("d5") === "p" && g.at("e4") === "P" && g.turn === Color.WHITE);
assert(g.redo() && g.at("d5") === "P" && g.turn === Color.BLACK);
assert(g.undo() && g.move("a2", "a3") && !g.redo());

// Stalemate
g = new Game(Board.parse(".......k", ".....K..", "........", "......Q.",
                         "........", "........", "........", "........"));
assert(g.move("g5", "g6") && g.state === GameState.STALEMATE && g.winner === null);

// A pinned bishop cannot move
g = new Game(Board.parse("k...r...", "........", "........", "........",
                         "........", "........", "....B...", "....K..."));
assert(!g.move("e2", "d3") && g.move("e1", "d1"));

// Castling through an attacked square is illegal, otherwise fine, undo restores rights
g = new Game(Board.parse("k....r..", "........", "........", "........",
                         "........", "........", "........", "....K..R"));
assert(!g.move("e1", "g1"));
g = new Game(Board.parse("k.......", "........", "........", "........",
                         "........", "........", "........", "....K..R"));
assert(g.move("e1", "g1") && g.at("f1") === "R" && g.at("g1") === "K");
assert(g.undo() && g.at("e1") === "K" && g.at("h1") === "R");
assert(g.move("e1", "g1"));

// En passant
g = new Game(Board.parse("k.......", "...p....", "........", "....P...",
                         "........", "........", "........", "....K..."), Color.BLACK);
assert(g.move("d7", "d5") && g.move("e5", "d6"));
assert(g.at("d5") === "." && g.at("d6") === "P");
assert(g.undo() && g.at("d5") === "p" && g.at("e5") === "P" && g.at("d6") === ".");

// Promotion
g = new Game(Board.parse("........", "P.......", "........", ".......k",
                         "........", "........", "........", "K......."));
assert(g.move("a7", "a8", "N") && g.at("a8") === "N");
assert(g.undo() && g.at("a7") === "P" && g.at("a8") === ".");

// Resignation is terminal
g = new Game();
assert(g.resign(Color.WHITE) && g.state === GameState.RESIGNED && g.winner === Color.BLACK);
assert(!g.move("e2", "e4") && !g.undo());

console.log("all chess tests passed");

Design Patterns Used

PatternWhereWhy
PolymorphismPiece hierarchy — each piece implements canMove() and getPossibleMoves()Uniform interface, Board doesn't need to know piece types
Template MethodslideMoves() in base Piece classRook, Bishop, Queen share sliding logic, only differ in directions
Command (extension)Move objects stored in historyEnable undo/redo by reversing recorded moves
CompositionGame owns Board, Board owns Piece gridClean ownership hierarchy

Correction (2026-11-10)

slideMoves() is a shared helper in the base class, not a Template Method. In a Template Method, the base class fixes the skeleton of an algorithm and calls abstract steps that subclasses fill in. Here the subclasses call the helper with their own directions, which is plain inheritance-based code reuse. The table row is kept, but read it as "shared helper".

Patterns in the runnable version, with the alternatives rejected

Command: Move with execute() and undo(). Why: undo and redo are requirements, and a move has side effects that (from, to) can't reverse: the captured piece, the castling rook, the en passant victim on a different square, the promoted piece, and the previous hasMoved and en passant state. Putting them in the command keeps Game.undo() to four lines. The same object also drives the legal-move filter (execute, test, undo) and perft. Rejected: snapshot the whole board before every move (Memento). Simpler to get right, and a fine answer if the interviewer pushes on correctness. But it copies 64 squares per move, which hurts during move generation (thousands of trial moves per second), and it hides the domain: a Move that knows what it captured is also what you need for notation and for replaying a game. Rejected: replay from the start on undo. That's O(n) per undo and needs a deterministic, side-effect-free replay path anyway.

Polymorphism over pieces (a Strategy-like family). Why: each piece's movement is a separate rule, and the board can ask "where can you go?" without a switch on type. Pawn overrides attacks cleanly. Rejected: a big switch (piece.type) in the board, which violates open/closed and becomes the place every bug lives. Considered: the direction table above. It's fine for five pieces and doesn't fit pawns.

Simple Factory: Board.create(char) and Board.parse(rows). Why: test setup and promotion both need "make me a white knight" from a letter. One place maps letters to classes. Rejected: a full Abstract Factory per variant. Chess960 changes the starting arrangement, not the piece types, so a different parse string is enough.

State, derived rather than stored (State pattern considered). Why: game status changes behaviour only a little (terminal states reject moves, and resigned or drawn games reject undo). An enum plus isOver() is enough. Rejected: a State class per status, which is worth it when each state has a different set of allowed operations with real logic, as in a vending machine. Here it would be five classes that each hold one if.

Not used: Observer. A UI or a spectator feed would subscribe to "move made" and "state changed" events. Add it when there's a second consumer (see the follow-ups). Before then it's ceremony.

Not used: Singleton. There's nothing global about a chess game. Several games run at once on any server, and a singleton Board is a classic red flag.

Concurrency Considerations

Chess Is Turn-Based

Chess is inherently sequential — only one player acts at a time. Concurrency is mainly relevant for:

  • Online multiplayer: Lock the game state during move validation to prevent race conditions if both clients somehow submit simultaneously
  • AI computation: Run the AI's move search on a background thread while the UI remains responsive
  • Move timer: A separate timer thread counts down; if it expires, the current player loses

Concurrency in depth

What's shared? In a local game, nothing. One thread owns the Game. Online, one Game object is touched by two players' request threads, a clock or timeout thread, and possibly a spectator feed reading the board.

How it's locked. The runnable Java Game makes every public method synchronized, and the Python one wraps them in a threading.RLock. The TypeScript one needs no lock, because a Node process runs one callback at a time and move() never awaits in the middle. One lock per game is right: a game sees one move every few seconds, so there's no contention worth splitting. Different games share nothing and run fully in parallel. For more detail, see Thread-Safe Class Design.

The race that actually happens: stale and duplicate submissions. A lock makes each move() atomic, but it doesn't stop a double-clicked move from arriving twice, or a move made on a board the client hasn't refreshed. Both look like legal requests. The fix is optimistic concurrency: the client sends the ply number it saw, and the server rejects the move if the game has moved on. That's the same compare-and-set idea used for seat booking in Movie Booking.

/** One per online game. Serialises submissions and rejects stale or out-of-turn ones. */
final class GameSession {
    private final Game game;
    private final String whiteId, blackId;

    GameSession(Game game, String whiteId, String blackId) {
        this.game = game; this.whiteId = whiteId; this.blackId = blackId;
    }

    /** seenPly is the ply count the client's board showed when the player moved. */
    synchronized boolean submit(String playerId, int seenPly, String from, String to) {
        String onMove = game.turn() == Color.WHITE ? whiteId : blackId;
        if (!onMove.equals(playerId)) return false; // not your turn
        if (seenPly != game.ply()) return false;    // stale board or a duplicate send
        return game.move(from, to);
    }
}

This was run against the Java listing above: eight threads submitted the same e2-e4 at ply 0 at once, exactly one was accepted, a second move by White at ply 1 was refused as out of turn, and Black's reply at ply 1 went through. The lock order is always session, then game, so the nested synchronized calls can't deadlock.

Other shared-state traps:

  • Never hand out the live board. A spectator thread iterating board.pieces() while a move executes can see a half-moved position: the king lifted off one square and not yet placed on the next. Publish an immutable snapshot (a FEN string, or a copied grid) after each move instead.
  • Trial moves mutate the board. legalMoves() executes and undoes moves on the real board. That's safe only inside the game's lock. An AI searching in the background must search its own copy of the board, never the live one.
  • The clock is a second writer. A timeout should go through the same lock: synchronized flagFall(Color c) { if (!isOver()) { state = TIMEOUT; winner = c.opposite(); } }. Then a move and a timeout arriving together resolve to exactly one winner, whichever takes the lock first.

Testing Strategy

Test TypeWhat to Test
UnitEach piece's getPossibleMoves() from various board positions
UnitKnight can jump over pieces; Rook/Bishop/Queen cannot
UnitPawn: forward move, capture, double move from start, promotion
IntegrationMove leaves own king in check — should be rejected
IntegrationCheckmate detection: Scholar's Mate (4-move checkmate)
IntegrationStalemate detection
IntegrationCastling: kingside and queenside, blocked by pieces, blocked by check
Edge caseKing cannot castle through check or out of check
Edge casePawn promotion auto-promotes to Queen

Correction (2026-11-10)

The original listings auto-promote to a queen. The runnable version lets the caller choose (move("a7", "a8", 'N')) and defaults to a queen, so the last row now reads "promotion defaults to Queen, and under-promotion works".

Testing the runnable version

Every listing in the runnable implementation ends with the same tests, and all three were run (Java 24 with -ea, Python 3.12, and TypeScript through tsc --strict and tsx).

1. Perft: the test that catches what hand-written tests miss. Perft ("performance test") counts every leaf of the legal-move tree to a fixed depth and compares against numbers the chess-programming community has verified for decades. From the start position the counts are 20, 400 and 8,902 for depths 1 to 3. For the position nicknamed "Kiwipete", which is built to stress castling (all four rights available), pins and captures, they are 48 and 2,039 for depths 1 and 2. If any rule is wrong, for example castling through check, a pinned piece moving, or en passant leaving its pawn on the board, the count drifts. Perft also exercises undo() thousands of times: if undo leaks any state, later counts break.

def perft(g: Game, color: Color, depth: int) -> int:
    if depth == 0:
        return 1
    n = 0
    for m in g.legal_moves(color):
        m.execute(g.board)
        n += perft(g, color.opposite(), depth - 1)
        m.undo(g.board)
    return n

2. Scenario tests, one per rule. Each sets up a position with Board.parse and asserts on the state:

TestPosition or movesAsserts
Fool's matef3, e5, g4, Qh4CHECKMATE, winner Black, further moves rejected
Undo a capturee4, d5, exd5, then undod5 holds the black pawn again, e4 holds the white pawn, White to move
Redo, and a new move clears redoredo, undo, a3redo replays the capture, then redo() returns false
StalemateWhite Kf7 and Qg5, Black Kh8, then Qg6STALEMATE, no winner
PinWhite Ke1, Be2, Black Re8Be2-d3 rejected, Ke1-d1 allowed
Castling through checkBlack rook on f8 covers f1e1-g1 rejected
Castling and undoSame without the rookRook lands on f1, undo restores e1 and h1, and castling is allowed again (rights restored)
En passant and undod7-d5, then e5xd6d5 empty after capture, pawn back on d5 after undo
Under-promotiona7-a8=NKnight on a8, undo gives back the pawn on a7
ResignationWhite resignsRESIGNED, winner Black, move and undo both rejected

3. What to say about test design in the interview.

  • Keep tests position-based, not move-sequence-based: Board.parse makes each test independent of the opening.
  • Test through Game, the public surface, plus one perft harness against the generator.
  • A round-trip property is cheap and strong: for every legal move in a position, execute followed by undo must give back a byte-identical board. Perft gives you this for free.

Extensions & Follow-ups

ExtensionDesign Impact
En passantTrack last move's pawn double-step; Pawn checks adjacent column
Undo/redoCommand pattern: Move objects with execute() / undo() methods
Move timerAdd Clock class per player; decrement on turn, lose if zero
Chess960Randomize back-rank setup; castling rules adapt to king/rook positions
Algebraic notationNotationService converts Move to/from "e2e4", "Nf3", "O-O"
AI opponentAIPlayer with Minimax + alpha-beta pruning using Board.evaluate()
Move validation cachingCache legal moves per position; invalidate on board change

The interviewer adds X

The core design (geometry in pieces, legality in Game, Move as a Command) is worth building first precisely because the special moves then become small, local diffs. Here are the three that come up most, shown as the change you'd make live. Snippets are TypeScript. The Java and Python listings above contain the same code.

"Now add castling"

Castling is the only move where two pieces move and where the rules depend on attacks on squares the king passes over. Two decisions keep it contained:

  1. It's generated by Game, not by King.pseudoMoves. If the king's pseudo-moves included castling, isAttacked (which asks the enemy king for its moves) would have to check castling, which asks isAttacked, which recurses forever. Geometry stays in the piece, and the castling rule goes where the whole position is visible.
  2. The rook's move is a side effect stored in the Move. execute and undo move the rook too, and remember its old hasMoved flag.
// Game: called from legalMoves() after the piece-by-piece candidates
private addCastling(color: Color, out: Move[]): void {
  const row = color === Color.WHITE ? 7 : 0;
  const kingPos = new Pos(row, 4);
  const king = this.board.get(kingPos);
  if (!(king instanceof King) || king.color !== color || king.hasMoved) return;
  if (this.board.isAttacked(kingPos, opposite(color))) return; // no castling out of check
  this.tryCastle(color, row, 7, [5, 6], [5, 6], out);          // king side: f, g empty and safe
  this.tryCastle(color, row, 0, [1, 2, 3], [3, 2], out);       // queen side: b, c, d empty, d and c safe
}

private tryCastle(color: Color, row: number, rookCol: number,
                  mustBeEmpty: number[], kingPath: number[], out: Move[]): void {
  const rook = this.board.get(new Pos(row, rookCol));
  if (!(rook instanceof Rook) || rook.color !== color || rook.hasMoved) return;
  if (mustBeEmpty.some((c) => this.board.get(new Pos(row, c)) !== null)) return;
  if (kingPath.some((c) => this.board.isAttacked(new Pos(row, c), opposite(color)))) return; // not through check
  out.push(Move.create(this.board, new Pos(row, 4), new Pos(row, kingPath[kingPath.length - 1])));
}

// Move.create: a king moving two files drags its rook along
if (piece instanceof King && Math.abs(to.col - from.col) === 2) {
  const kingside = to.col === 6;
  rookFrom = new Pos(from.row, kingside ? 7 : 0);
  rookTo = new Pos(from.row, kingside ? 5 : 3);
}

Note the asymmetry on the queen side: b1 must be empty but needn't be safe, because the king never crosses it. Candidates who use one list for both conditions get this wrong. The "castling rights" are just the hasMoved flags on king and rooks. That's why undo() restoring prevMoved and prevRookMoved matters, and the test "castle, undo, castle again" pins it down.

"Now add en passant"

En passant needs one piece of history: did the opponent's last move push a pawn two squares? That history belongs to the position (it's part of a FEN string), so it lives on Board as enPassant: Pos | null. Three small changes:

// 1. Move.create: a double push creates the target square, and an en passant
//    capture removes a pawn from a different square than the destination
if (piece instanceof Pawn) {
  if (from.col !== to.col && b.get(to) === null) captureSq = new Pos(from.row, to.col);
  if (Math.abs(to.row - from.row) === 2) ep = new Pos((from.row + to.row) / 2, from.col);
}

// 2. Move.execute / undo: set the new target, remember the old one
this.prevEnPassant = b.enPassant;   // in execute()
b.enPassant = this.newEnPassant;    // every move overwrites it, so it expires after one turn
b.enPassant = this.prevEnPassant;   // in undo()

// 3. Pawn.pseudoMoves: the target square counts as capturable
const epRow = this.color === Color.WHITE ? 2 : 5; // only the side to move can use the target
const enPassant = diag.equals(b.enPassant) && diag.row === epRow;
if ((t !== null && t.color !== this.color) || enPassant) out.push(diag);

Because the capture square is stored separately from the destination, execute and undo stay generic: "clear captureSq, and later put captured back on captureSq". The rare case where en passant exposes your own king along the rank (both pawns leave the rank at once) needs no extra code, because the king-safety filter catches it.

"Now let the player choose the promotion piece"

The first listing auto-queened. To allow under-promotion:

// Game.legalMoves: a pawn reaching the last rank yields four candidates, not one
if (p instanceof Pawn && (to.row === 0 || to.row === 7)) {
  for (const ch of "QRBN") {
    const promo = Board.create(color === Color.WHITE ? ch : ch.toLowerCase());
    promo.hasMoved = true;
    candidates.push(Move.create(this.board, from, to, promo));
  }
}

// Game.move: match the requested piece, default queen
const m = this.legalMoves(this.turn).find((c) =>
  c.from.equals(f) && c.to.equals(t) && (c.promotion === null || c.promotion.letter === promo.toUpperCase()));

// Move.execute / undo: the promoted piece replaces the pawn, and undo restores the pawn
b.set(this.to, this.promotion ?? this.piece);   // execute
b.set(this.from, this.piece);                   // undo puts the original Pawn object back

Keeping the original pawn object in the command (not a new pawn) matters: its identity and flags survive undo. Generating four separate moves also makes perft counts correct, since each promotion choice is a different move.

Other common add-ons

  • Threefold repetition. Keep a Map<positionKey, count>, where the key is the board, the side to move, the castling rights and the en passant square. Increment it in apply() and decrement it in undo(). Declare a draw at 3.
  • Fifty-move rule. Add a half-move clock to the board. Reset it on any pawn move or capture, increment it otherwise, store the previous value in Move for undo, and declare a draw at 100.
  • Chess clock. A Clock per colour, started and stopped in apply(), with timeouts going through the game lock (see Concurrency in depth).

Common mistakes

  1. Legality inside Piece. The bishop checking whether its king is in check, or whose turn it is. Pieces should describe geometry, and the game should decide legality.
  2. Using canMove as the attack test. Pawns attack diagonally even on empty squares, and kings don't "attack" by castling. The original listing had exactly this bug.
  3. Forgetting that trial moves have side effects. Any search that executes moves must restore everything: piece positions, hasMoved, the en passant square, and the half-move clock if you have one. The original hasLegalMoves leaked hasMoved and silently disabled castling.
  4. Restoring flags to a constant instead of the previous value. hasMoved = false on undo is wrong whenever the piece had moved before.
  5. Checkmate = "the king has no moves". Wrong. A block or a capture by another piece also escapes check. Checkmate means "in check and no legal move for any piece".
  6. Ignoring stalemate, or computing it as "not in check" without checking that the side to move has no legal move.
  7. Castling checks that only test "squares empty". You also need: not in check now, not passing through an attacked square, rook and king unmoved, and (on the queen side) b1 empty but not necessarily safe.
  8. En passant without expiry. The right exists only on the move immediately after the double push. Overwriting enPassant on every move handles that.
  9. Undo implemented by "move the piece back". That loses the captured piece, the castling rook, the en passant victim and the promotion. You need a command that remembers what it destroyed, or a snapshot.
  10. A Singleton board or game, and a god Game class that also renders the board and parses notation. Keep notation and UI outside.
  11. Two sources of truth for legality: one check in move() and another in the checkmate detector. Use a single legalMoves() and match the request against it.

Interview follow-ups

Q: How would you implement undo for a game against an AI? A: Undo two plies (the AI's reply and your move) in one call. The command stack already supports that. Also cancel any background search first, because it's working on the position you're about to change.

Q: Why not store the legal moves on each piece and update them incrementally? A: Every move can change other pieces' moves (discovered attacks, blocks, pins), so incremental updates are a bug farm. Recompute per position. If profiling shows it matters, cache by position key (the extension table lists this) and drop the cache on every move.

Q: How would you support Chess960? A: Only setup and castling change. Board.parse already takes any arrangement. Castling needs the rook's starting file instead of the fixed columns 0 and 7, and the rule becomes "king ends on g or c, rook on f or d, and every square either piece crosses is empty apart from those two pieces". Put the rook files in a small CastlingRules object passed to Game. Piece classes don't change, which is the payoff of keeping geometry separate.

Q: How do you serialise a game to save it or send it over the network? A: Two standard formats. FEN describes one position: pieces, side to move, castling rights, the en passant square and the move clocks. PGN describes a whole game as a move list. Store the move list and rebuild by replaying it. Move.toString() already gives long algebraic notation such as e2e4 or a7a8N.

Q: How would you make move generation fast enough for an engine? A: Replace the "ask every piece" attack test with ray casting from the target square, then move to bitboards with precomputed attack tables. Generate check evasions and pins directly instead of execute-test-undo. The object design stays the same at the Game level. Only Board and the generator change behind the same interface.

Q: What if two players submit moves at the same time? A: Only one of them is on move, so the other request is rejected for being out of turn. For duplicates and stale boards, include the seen ply number and compare-and-set against it, as in the GameSession above.

Q: How would you notify spectators? A: Add an Observer: Game publishes MoveMade(move, state, fen) after each apply(). Subscribers get an immutable snapshot, never the live board, and slow subscribers are decoupled through a queue. For the cross-service version, see Pub-Sub.

Q: Where would draw by insufficient material go? A: In updateState(), next to stalemate: after each move, if the remaining material is K vs K, K+B vs K, K+N vs K, or K+B vs K+B with same-coloured bishops, set DRAW. It's a pure function of the board, so it's easy to unit-test.

Q: Why does Game match the requested move against generated legal moves instead of validating it directly? A: So there's exactly one definition of legality. The same list drives checkmate and stalemate detection, the UI's highlighted squares and the perft tests. A separate validator would eventually disagree with the generator.

Further reading