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
- Standard 8x8 chess board with standard starting positions
- Two players alternate turns (white moves first)
- Six piece types: King, Queen, Rook, Bishop, Knight, Pawn
- Each piece has unique movement rules
- Move validation: can't move into check, can't move through pieces (except Knight)
- Detect check, checkmate, and stalemate
- Special moves: castling, en passant, pawn promotion
- 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
| Actor | Use Case |
|---|---|
| Player | Make a move (source square to destination square) |
| Player | Resign or offer draw |
| System | Validate move legality |
| System | Detect check, checkmate, stalemate |
| System | Handle special moves (castling, en passant, promotion) |
| System | Track 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.
| Question | Usual answer | What it changes |
|---|---|---|
| Two humans on one device, or online play? | Start local, design so online can be added | Whether a GameSession with player identity and locking is needed |
| Full rules, including castling, en passant and promotion? | Core moves first, specials as extensions | Whether 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-up | Whether we need position hashing and a half-move clock |
| Undo and redo? | Yes, both | Makes Move a Command, and the board must be fully reversible |
| Clocks and time controls? | Out of scope, mention as an extension | A Clock per player and a timeout path into the state machine |
| AI opponent? | Out of scope | If yes, the move generator must be fast and side-effect free |
| Input format? | Square names such as e2, e4 | We 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
Gameobject 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.
| Entity | Kind | Responsibility | Owned by |
|---|---|---|---|
Pos / Position | Value object (immutable) | A square: row and column, parsing "e4" | Nobody; created freely |
Color | Enum | WHITE, BLACK, opposite() | — |
Piece (abstract) and its 6 subclasses | Entity | Geometry only: where this piece could go from a square, and which squares it attacks | Board (by square) |
Board | Entity | The 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 |
Move | Command | One 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 |
Game | Aggregate root | Whose turn it is, legal-move generation, state (active, check, checkmate…), undo and redo, resign and draw | The caller, or a GameSession |
Player | Entity | Name and colour | Game |
GameState / GameStatus | Enum | Lifecycle of a game | Game |
Three decisions in that table carry the design:
- 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. - The board is dumb storage plus one query.
Boardholds pieces and answersisAttacked(square, byColor). It doesn't know about turns or checkmate. - 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. MakingMovea 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 |
|---|---|---|
| yes | no | Checkmate, the other side wins |
| no | no | Stalemate, a draw |
| yes | yes | Check, the game goes on |
| no | yes | Active |
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.)
| Polymorphism | Direction table | |
|---|---|---|
| Adding a fairy piece (for example an Archbishop = Bishop + Knight) | New subclass | New table row, if it fits the "directions plus slides" shape |
| Pawns | Natural: Pawn overrides pseudoMoves and attacks | Doesn't fit, so you need a special case anyway |
| Readability in an interview | Each class reads like the rule book | Compact, but the rules hide in data |
| Per-piece behaviour beyond movement (value, symbol, promotion rules) | Lives on the class | Needs more columns or parallel tables |
| Performance | Virtual call per piece, fine | Slightly 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:
Board.isAttacked(square, byColor). Does any piece ofbyColorattacksquare? Each piece answers throughattacks(). The default is "is the square in my pseudo-moves", andPawnoverrides 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 inGameand not inKing.pseudoMoves.- 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):
hasLegalMoves()permanently sethasMoved = trueon every piece it tried, becausemovePiece()sets the flag andundoMove()didn't clear it. After the first status check, nobody could castle. It now saves and restores the flag.- A rejected move reset
hasMovedtofalseinstead of to its previous value. A king or rook that had already moved could castle again after one illegal attempt. - Castling out of check and through an attacked square was allowed. The comment said "full check in Game class", but
Gamenever did that check.isCastleSafe()now checks the king's square and the square it passes over. isInCheck()usedcanMove(), so an unmoved enemy king "attacked" its castling squares two files away. A dedicatedisSquareAttacked()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:
pseudoMovesvsattacks. Pieces describe geometry only, andPawnoverridesattacksbecause it captures differently from how it moves. The king's pseudo-moves don't include castling, so attack detection can't recurse.Moveis a Command.Move.createworks 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, andundo()puts it all back,hasMovedflags 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.parsetakes 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
| Pattern | Where | Why |
|---|---|---|
| Polymorphism | Piece hierarchy — each piece implements canMove() and getPossibleMoves() | Uniform interface, Board doesn't need to know piece types |
| Template Method | slideMoves() in base Piece class | Rook, Bishop, Queen share sliding logic, only differ in directions |
| Command (extension) | Move objects stored in history | Enable undo/redo by reversing recorded moves |
| Composition | Game owns Board, Board owns Piece grid | Clean 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 Type | What to Test |
|---|---|
| Unit | Each piece's getPossibleMoves() from various board positions |
| Unit | Knight can jump over pieces; Rook/Bishop/Queen cannot |
| Unit | Pawn: forward move, capture, double move from start, promotion |
| Integration | Move leaves own king in check — should be rejected |
| Integration | Checkmate detection: Scholar's Mate (4-move checkmate) |
| Integration | Stalemate detection |
| Integration | Castling: kingside and queenside, blocked by pieces, blocked by check |
| Edge case | King cannot castle through check or out of check |
| Edge case | Pawn 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:
| Test | Position or moves | Asserts |
|---|---|---|
| Fool's mate | f3, e5, g4, Qh4 | CHECKMATE, winner Black, further moves rejected |
| Undo a capture | e4, d5, exd5, then undo | d5 holds the black pawn again, e4 holds the white pawn, White to move |
| Redo, and a new move clears redo | redo, undo, a3 | redo replays the capture, then redo() returns false |
| Stalemate | White Kf7 and Qg5, Black Kh8, then Qg6 | STALEMATE, no winner |
| Pin | White Ke1, Be2, Black Re8 | Be2-d3 rejected, Ke1-d1 allowed |
| Castling through check | Black rook on f8 covers f1 | e1-g1 rejected |
| Castling and undo | Same without the rook | Rook lands on f1, undo restores e1 and h1, and castling is allowed again (rights restored) |
| En passant and undo | d7-d5, then e5xd6 | d5 empty after capture, pawn back on d5 after undo |
| Under-promotion | a7-a8=N | Knight on a8, undo gives back the pawn on a7 |
| Resignation | White resigns | RESIGNED, 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.parsemakes 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,
executefollowed byundomust give back a byte-identical board. Perft gives you this for free.
Extensions & Follow-ups
| Extension | Design Impact |
|---|---|
| En passant | Track last move's pawn double-step; Pawn checks adjacent column |
| Undo/redo | Command pattern: Move objects with execute() / undo() methods |
| Move timer | Add Clock class per player; decrement on turn, lose if zero |
| Chess960 | Randomize back-rank setup; castling rules adapt to king/rook positions |
| Algebraic notation | NotationService converts Move to/from "e2e4", "Nf3", "O-O" |
| AI opponent | AIPlayer with Minimax + alpha-beta pruning using Board.evaluate() |
| Move validation caching | Cache 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:
- It's generated by
Game, not byKing.pseudoMoves. If the king's pseudo-moves included castling,isAttacked(which asks the enemy king for its moves) would have to check castling, which asksisAttacked, which recurses forever. Geometry stays in the piece, and the castling rule goes where the whole position is visible. - The rook's move is a side effect stored in the
Move.executeandundomove the rook too, and remember its oldhasMovedflag.
// 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 inapply()and decrement it inundo(). 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
Movefor undo, and declare a draw at 100. - Chess clock. A
Clockper colour, started and stopped inapply(), with timeouts going through the game lock (see Concurrency in depth).
Common mistakes
- 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. - Using
canMoveas the attack test. Pawns attack diagonally even on empty squares, and kings don't "attack" by castling. The original listing had exactly this bug. - 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 originalhasLegalMovesleakedhasMovedand silently disabled castling. - Restoring flags to a constant instead of the previous value.
hasMoved = falseon undo is wrong whenever the piece had moved before. - 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".
- Ignoring stalemate, or computing it as "not in check" without checking that the side to move has no legal move.
- 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.
- En passant without expiry. The right exists only on the move immediately after the double push. Overwriting
enPassanton every move handles that. - 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.
- A
Singletonboard or game, and a godGameclass that also renders the board and parses notation. Keep notation and UI outside. - Two sources of truth for legality: one check in
move()and another in the checkmate detector. Use a singlelegalMoves()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
- Command pattern: the undo and redo mechanics in general form
- State pattern and Memento: the two alternatives discussed above
- The LLD Interview Framework: the 45-minute route this page follows
- Common LLD Mistakes
- Tic-Tac-Toe and Snake & Ladders: simpler board games with the same Game, Board and Player split