Design a Chess Game, Low Level Design (LLD) Interview
A chess game in which each piece knows how it moves, the game throws away any move that leaves your own king in check, castling, en passant and promotion follow the FIDE rules, every move can be undone, and the move generator is proved right by counting moves against published numbers.
Where it shows up
A well known object-oriented design question for LLD rounds. Interviewers use it to test class hierarchies and rule checking.
Two courses by the author of this page:
770 lessons · 18 free to read
₹499 in India · $49 elsewhere, once
Get System DesignYou own this course
204 lessons · 10 free to read
₹999 in India · $49 elsewhere, once
Get AI EngineeringYou own this course
Spec sheetChess
- 01Core classes
- Game, Board, Piece, Pawn, King, Move, MoveCommand
- 02Design patterns
- Inheritance with one method to fill in, Command, Factory, Generate, then filter
- 03Enums
- Color, PieceType, MoveKind, GameStatus
- 04Key methods
- 4 signatures, with the code skeleton
worked through below, with the maths
Why this is asked
Chess has a natural class tree: six kinds of piece that share a lot and differ in how they move. That tests if a candidate uses inheritance well. The rules then push past the easy part. A move that looks fine can be illegal because it leaves your own king open to attack. Castling, en passant and promotion each break the normal pattern. And undo is a natural fit for the Command pattern. Most candidates stop at moving pieces. Strong ones explain how they would know the rules are right, and that is where perft comes in.
Requirements
Functional
- Two players, white and black, take turns on an 8 by 8 board.
- Each kind of piece (pawn, knight, bishop, rook, queen, king) moves by its own rules.
- A move is refused if it would leave the mover's own king in check. Check means the king is under attack.
- Castling, en passant and promotion work as in the FIDE Laws of Chess. FIDE is the world chess federation, and its Laws are the official rules.
- The game reports checkmate and stalemate.
- Any number of moves can be undone, back to the start.
Constraints & non-functional
- The move generator must be proved right, not just tried by hand. The program counts moves to a fixed depth and compares with published counts.
- Adding a new piece kind should mean adding one class.
- Undo must restore everything, including castling rights and the en passant square.
- Draws that a player must claim (threefold repetition, the 50-move rule) and the automatic draws (fivefold repetition, 75 moves) are out of scope here. The program keeps the half-move counter they need, so they can be added. Clocks and draw by too little material are also out of scope.
Core classes & entities
Game
Owns the board and the move history. It builds the list of legal moves, plays a move, undoes a move and reports the status.
attrs: board: Board, history: Deque<MoveCommand>
methods: legalMoves(), play(move), undo(), status()
Board
The 64 squares and the extra facts a position needs: whose turn it is, which castling rights are left, the en passant square and the half-move counter. It answers one key question: is this square attacked?
attrs: squares: Piece[64], sideToMove: Color, castling, epSquare
methods: at(square), put(square, piece), isAttacked(square, byColor), fromFen(text)
Piece
The base class for all six pieces. It holds the colour and a shared helper for stepping and sliding. Each subclass lists its own moves.
attrs: color: Color
methods: type(), addMoves(board, from, out), symbol()
Pawn
The hardest piece. It moves forward one square, or two from its first square, captures one square forward on a diagonal, captures en passant, and promotes on the last rank.
methods: addMoves(board, from, out)
King
Moves one square in any direction. It also adds castling, but only when every castling condition holds.
methods: addMoves(board, from, out)
Move
A small value: from square, to square, the kind of move and the promotion piece if any.
attrs: from, to, kind: MoveKind, promotion: PieceType
methods: toString()
MoveCommand
Does one move on the board and remembers what it needs to undo it: the captured piece, the old castling rights, the old en passant square and the old half-move counter.
attrs: move: Move, captured: Piece, oldCastling, oldEp
methods: execute(board), undo(board)
Relationships
- Game → composition → Board. A game owns one board.
- Game → composition → MoveCommand. The history is a stack of commands. Undo pops one.
- Board → aggregation → Piece. The board holds up to 32 pieces. Captured pieces leave the board but are kept by the command for undo.
- Piece → inheritance → Pawn. Knight, Bishop, Rook and Queen extend Piece like this too.
- Piece → inheritance → King. The king adds castling on top of its one-square steps.
- MoveCommand → association → Move. A command carries out one move.
Design patterns used
Inheritance with one method to fill in in Piece and its six subclasses
Each piece only answers one question: where can I go from here? The game never asks what kind of piece it holds.
Command in MoveCommand.execute and undo
Each move is an object that can be done and undone. That gives undo for players, and it lets the legal-move check try a move and take it back.
Factory in Piece.of(type, color)
Promotion and reading a position from text both need to make a piece from its type. One method does it.
Generate, then filter in Game.legalMoves
Pieces list every move that follows their own pattern. The game then plays each one, checks if its own king is attacked, and undoes it. One simple rule handles pins, checks and moving into check.
Enums
Key API / methods
List<Move> Game.legalMoves()Every move the side to move may play. It gathers each piece's moves, then removes any that leave its own king attacked.
boolean Board.isAttacked(int square, Color by)Looks outward from the square, once for each kind of piece, to see if an enemy piece could capture there. Used for check, for castling and for the legal-move filter.
void MoveCommand.execute(Board b) / undo(Board b)Plays a move, including the rook jump in castling, the removed pawn in en passant and the new piece in promotion. Undo puts every piece and every rule fact back.
long Game.perft(int depth)Counts every legal sequence of moves to the given depth. The count is compared with published numbers to prove the rules are right.
Code skeleton
import java.util.*;
// ---------- Enums ----------
enum Color { WHITE, BLACK; Color other() { return this == WHITE ? BLACK : WHITE; } }
enum PieceType { PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING }
enum GameStatus { IN_PROGRESS, CHECKMATE, STALEMATE }
enum MoveKind { NORMAL, DOUBLE_PUSH, EN_PASSANT, CASTLE_KING_SIDE, CASTLE_QUEEN_SIDE, PROMOTION }
// ---------- Pieces: each type knows how it moves (pseudo-legal: ignores its own king's safety) ----------
abstract class Piece {
final Color color;
Piece(Color c) { color = c; }
abstract PieceType type();
abstract void addMoves(Board b, int from, List<Move> out);
char symbol() { char ch = "pnbrqk".charAt(type().ordinal()); return color == Color.WHITE ? Character.toUpperCase(ch) : ch; }
static Piece of(PieceType t, Color c) {
return switch (t) { case PAWN -> new Pawn(c); case KNIGHT -> new Knight(c); case BISHOP -> new Bishop(c);
case ROOK -> new Rook(c); case QUEEN -> new Queen(c); case KING -> new King(c); };
}
// squares are 0..63, a1 = 0, h1 = 7, a8 = 56
static boolean onBoard(int f, int r) { return f >= 0 && f < 8 && r >= 0 && r < 8; }
void step(Board b, int from, int[][] dirs, boolean slide, List<Move> out) {
int f0 = from % 8, r0 = from / 8;
for (int[] d : dirs) {
int f = f0 + d[0], r = r0 + d[1];
while (onBoard(f, r)) {
Piece t = b.at(r * 8 + f);
if (t == null) out.add(new Move(from, r * 8 + f, MoveKind.NORMAL, null));
else { if (t.color != color) out.add(new Move(from, r * 8 + f, MoveKind.NORMAL, null)); break; }
if (!slide) break;
f += d[0]; r += d[1];
}
}
}
static final int[][] ORTHO = {{1,0},{-1,0},{0,1},{0,-1}}, DIAG = {{1,1},{1,-1},{-1,1},{-1,-1}};
static final int[][] ALL8 = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
static final int[][] JUMPS = {{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};
}
final class Knight extends Piece { Knight(Color c) { super(c); } PieceType type() { return PieceType.KNIGHT; }
void addMoves(Board b, int from, List<Move> out) { step(b, from, JUMPS, false, out); } }
final class Bishop extends Piece { Bishop(Color c) { super(c); } PieceType type() { return PieceType.BISHOP; }
void addMoves(Board b, int from, List<Move> out) { step(b, from, DIAG, true, out); } }
final class Rook extends Piece { Rook(Color c) { super(c); } PieceType type() { return PieceType.ROOK; }
void addMoves(Board b, int from, List<Move> out) { step(b, from, ORTHO, true, out); } }
final class Queen extends Piece { Queen(Color c) { super(c); } PieceType type() { return PieceType.QUEEN; }
void addMoves(Board b, int from, List<Move> out) { step(b, from, ALL8, true, out); } }
final class Pawn extends Piece {
Pawn(Color c) { super(c); } PieceType type() { return PieceType.PAWN; }
void addMoves(Board b, int from, List<Move> out) {
int dir = color == Color.WHITE ? 1 : -1, f = from % 8, r = from / 8;
int startRank = color == Color.WHITE ? 1 : 6, lastRank = color == Color.WHITE ? 7 : 0;
int one = from + 8 * dir;
if (b.at(one) == null) {
add(from, one, r + dir == lastRank, MoveKind.NORMAL, out);
int two = from + 16 * dir;
if (r == startRank && b.at(two) == null) out.add(new Move(from, two, MoveKind.DOUBLE_PUSH, null));
}
for (int df : new int[]{-1, 1}) {
if (!onBoard(f + df, r + dir)) continue;
int to = (r + dir) * 8 + f + df;
Piece t = b.at(to);
if (t != null && t.color != color) add(from, to, r + dir == lastRank, MoveKind.NORMAL, out);
else if (to == b.epSquare) out.add(new Move(from, to, MoveKind.EN_PASSANT, null));
}
}
// FIDE 3.7.3.3: a pawn reaching the last rank becomes a queen, rook, bishop or knight of its colour
private void add(int from, int to, boolean promotes, MoveKind k, List<Move> out) {
if (!promotes) { out.add(new Move(from, to, k, null)); return; }
for (PieceType p : new PieceType[]{PieceType.QUEEN, PieceType.ROOK, PieceType.BISHOP, PieceType.KNIGHT})
out.add(new Move(from, to, MoveKind.PROMOTION, p));
}
}
final class King extends Piece {
King(Color c) { super(c); } PieceType type() { return PieceType.KING; }
void addMoves(Board b, int from, List<Move> out) {
step(b, from, ALL8, false, out);
// FIDE 3.8.2: king and rook unmoved (the castling rights), nothing between them,
// and the king's square, the square it crosses and the square it lands on not attacked.
Color them = color.other();
int home = color == Color.WHITE ? 4 : 60;
if (from != home || b.isAttacked(home, them)) return;
if (b.canCastle(color, true) && b.at(home + 1) == null && b.at(home + 2) == null
&& !b.isAttacked(home + 1, them) && !b.isAttacked(home + 2, them))
out.add(new Move(from, home + 2, MoveKind.CASTLE_KING_SIDE, null));
if (b.canCastle(color, false) && b.at(home - 1) == null && b.at(home - 2) == null && b.at(home - 3) == null
&& !b.isAttacked(home - 1, them) && !b.isAttacked(home - 2, them))
out.add(new Move(from, home - 2, MoveKind.CASTLE_QUEEN_SIDE, null));
}
}
// ---------- Move: what to do. MoveCommand: does it and can undo it (Command pattern) ----------
record Move(int from, int to, MoveKind kind, PieceType promotion) {
static String sq(int s) { return "" + (char) ('a' + s % 8) + (char) ('1' + s / 8); }
public String toString() { return sq(from) + sq(to) + (promotion == null ? "" : String.valueOf("pnbrqk".charAt(promotion.ordinal()))); }
}
final class MoveCommand {
final Move move; private Piece moved, captured; private int capturedAt;
private int oldCastling, oldEp, oldHalfmove;
MoveCommand(Move m) { move = m; }
void execute(Board b) {
oldCastling = b.castling; oldEp = b.epSquare; oldHalfmove = b.halfmoveClock;
moved = b.at(move.from());
capturedAt = move.kind() == MoveKind.EN_PASSANT ? move.to() + (moved.color == Color.WHITE ? -8 : 8) : move.to();
captured = b.at(capturedAt);
b.put(capturedAt, null);
b.put(move.from(), null);
b.put(move.to(), move.kind() == MoveKind.PROMOTION ? Piece.of(move.promotion(), moved.color) : moved);
if (move.kind() == MoveKind.CASTLE_KING_SIDE) { b.put(move.to() - 1, b.at(move.to() + 1)); b.put(move.to() + 1, null); }
if (move.kind() == MoveKind.CASTLE_QUEEN_SIDE) { b.put(move.to() + 1, b.at(move.to() - 2)); b.put(move.to() - 2, null); }
b.epSquare = move.kind() == MoveKind.DOUBLE_PUSH ? (move.from() + move.to()) / 2 : -1; // en passant lasts one move only
b.castling &= Board.rightsKeptAfterTouching(move.from()) & Board.rightsKeptAfterTouching(move.to());
b.halfmoveClock = (moved.type() == PieceType.PAWN || captured != null) ? 0 : b.halfmoveClock + 1;
b.sideToMove = b.sideToMove.other();
}
void undo(Board b) {
b.sideToMove = b.sideToMove.other();
if (move.kind() == MoveKind.CASTLE_KING_SIDE) { b.put(move.to() + 1, b.at(move.to() - 1)); b.put(move.to() - 1, null); }
if (move.kind() == MoveKind.CASTLE_QUEEN_SIDE) { b.put(move.to() - 2, b.at(move.to() + 1)); b.put(move.to() + 1, null); }
b.put(move.to(), null);
b.put(move.from(), moved);
b.put(capturedAt, captured);
b.castling = oldCastling; b.epSquare = oldEp; b.halfmoveClock = oldHalfmove;
}
}
// ---------- Board: 64 squares plus the state a position needs (FEN fields) ----------
final class Board {
private final Piece[] sq = new Piece[64];
Color sideToMove = Color.WHITE;
int castling; // bit 1 = white king side, 2 = white queen side, 4 = black king side, 8 = black queen side
int epSquare = -1; // the square a pawn skipped over on the last move, or -1
int halfmoveClock;
private final int[] kingSq = new int[2];
Piece at(int s) { return sq[s]; }
void put(int s, Piece p) { sq[s] = p; if (p != null && p.type() == PieceType.KING) kingSq[p.color.ordinal()] = s; }
int king(Color c) { return kingSq[c.ordinal()]; }
boolean canCastle(Color c, boolean kingSide) { return (castling & (c == Color.WHITE ? (kingSide ? 1 : 2) : (kingSide ? 4 : 8))) != 0; }
/** A move from or to a king or rook home square removes the matching castling rights. */
static int rightsKeptAfterTouching(int s) {
return switch (s) { case 4 -> ~3; case 0 -> ~2; case 7 -> ~1; case 60 -> ~12; case 56 -> ~8; case 63 -> ~4; default -> ~0; };
}
/** Is square s attacked by any piece of colour `by`? Looks outward from s, once per piece kind. */
boolean isAttacked(int s, Color by) {
int f0 = s % 8, r0 = s / 8;
int pr = r0 + (by == Color.WHITE ? -1 : 1);
for (int df : new int[]{-1, 1}) if (Piece.onBoard(f0 + df, pr) && is(pr * 8 + f0 + df, by, PieceType.PAWN)) return true;
for (int[] d : Piece.JUMPS) if (Piece.onBoard(f0 + d[0], r0 + d[1]) && is((r0 + d[1]) * 8 + f0 + d[0], by, PieceType.KNIGHT)) return true;
for (int[] d : Piece.ALL8) if (Piece.onBoard(f0 + d[0], r0 + d[1]) && is((r0 + d[1]) * 8 + f0 + d[0], by, PieceType.KING)) return true;
return ray(f0, r0, Piece.ORTHO, by, PieceType.ROOK) || ray(f0, r0, Piece.DIAG, by, PieceType.BISHOP);
}
private boolean is(int s, Color c, PieceType t) { Piece p = sq[s]; return p != null && p.color == c && p.type() == t; }
private boolean ray(int f0, int r0, int[][] dirs, Color by, PieceType slider) {
for (int[] d : dirs) {
int f = f0 + d[0], r = r0 + d[1];
while (Piece.onBoard(f, r)) {
Piece p = sq[r * 8 + f];
if (p != null) { if (p.color == by && (p.type() == slider || p.type() == PieceType.QUEEN)) return true; break; }
f += d[0]; r += d[1];
}
}
return false;
}
static Board fromFen(String fen) {
Board b = new Board(); String[] p = fen.trim().split("\\s+");
int r = 7, f = 0;
for (char ch : p[0].toCharArray()) {
if (ch == '/') { r--; f = 0; }
else if (Character.isDigit(ch)) f += ch - '0';
else { b.put(r * 8 + f, Piece.of(PieceType.values()["pnbrqk".indexOf(Character.toLowerCase(ch))],
Character.isUpperCase(ch) ? Color.WHITE : Color.BLACK)); f++; }
}
b.sideToMove = p[1].equals("w") ? Color.WHITE : Color.BLACK;
for (char ch : p[2].toCharArray()) b.castling |= switch (ch) { case 'K' -> 1; case 'Q' -> 2; case 'k' -> 4; case 'q' -> 8; default -> 0; };
b.epSquare = p[3].equals("-") ? -1 : (p[3].charAt(1) - '1') * 8 + (p[3].charAt(0) - 'a');
b.halfmoveClock = p.length > 4 ? Integer.parseInt(p[4]) : 0;
return b;
}
String placement() {
StringBuilder s = new StringBuilder();
for (int r = 7; r >= 0; r--) {
int empty = 0;
for (int f = 0; f < 8; f++) { Piece p = sq[r * 8 + f]; if (p == null) empty++; else { if (empty > 0) s.append(empty); empty = 0; s.append(p.symbol()); } }
if (empty > 0) s.append(empty);
if (r > 0) s.append('/');
}
return s + " " + (sideToMove == Color.WHITE ? "w" : "b") + " " + castling + " " + epSquare;
}
}
// ---------- Game: legal moves, status, history for undo ----------
final class Game {
final Board board; private final Deque<MoveCommand> history = new ArrayDeque<>();
Game(Board b) { board = b; }
/** FIDE 3.9.2: a move may not leave or put your own king in check. Try each move, look, take it back. */
List<Move> legalMoves() {
List<Move> pseudo = new ArrayList<>(), legal = new ArrayList<>();
Color me = board.sideToMove;
for (int s = 0; s < 64; s++) { Piece p = board.at(s); if (p != null && p.color == me) p.addMoves(board, s, pseudo); }
for (Move m : pseudo) {
MoveCommand c = new MoveCommand(m); c.execute(board);
if (!board.isAttacked(board.king(me), me.other())) legal.add(m);
c.undo(board);
}
return legal;
}
boolean inCheck() { return board.isAttacked(board.king(board.sideToMove), board.sideToMove.other()); }
GameStatus status() {
if (!legalMoves().isEmpty()) return GameStatus.IN_PROGRESS;
return inCheck() ? GameStatus.CHECKMATE : GameStatus.STALEMATE; // FIDE 5.1.1 and 5.2.1
}
void play(String uci) {
Move m = legalMoves().stream().filter(x -> x.toString().equals(uci)).findFirst()
.orElseThrow(() -> new IllegalArgumentException("illegal move " + uci));
MoveCommand c = new MoveCommand(m); c.execute(board); history.push(c);
}
boolean undo() { if (history.isEmpty()) return false; history.pop().undo(board); return true; }
long perft(int depth) {
if (depth == 0) return 1;
long n = 0;
for (Move m : legalMoves()) { MoveCommand c = new MoveCommand(m); c.execute(board); n += perft(depth - 1); c.undo(board); }
return n;
}
}
// ---------- Demo: perft counts from chessprogramming.org, plus mate, stalemate and rule checks ----------
public class Chess {
public static void main(String[] args) {
System.out.println("Perft: count every legal move sequence to a depth, compare with published counts");
String start = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1";
perft("start position", start, new long[]{20, 400, 8_902, 197_281});
perft("position 2, Kiwipete", "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1", new long[]{48, 2_039, 97_862});
perft("position 3", "8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1", new long[]{14, 191, 2_812, 43_238});
perft("position 4", "r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1", new long[]{6, 264, 9_467});
perft("position 5", "rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8", new long[]{44, 1_486, 62_379});
System.out.println("Game rules");
Game g = new Game(Board.fromFen(start));
String before = g.board.placement();
for (String m : List.of("f2f3", "e7e5", "g2g4", "d8h4")) g.play(m);
check(g.status() == GameStatus.CHECKMATE, "fool's mate: f3 e5 g4 Qh4 is checkmate, white has 0 legal moves");
int undone = 0; while (g.undo()) undone++;
check(undone == 4 && g.board.placement().equals(before), "undo 4 times restores the start position exactly");
Game st = new Game(Board.fromFen("7k/5Q2/6K1/8/8/8/8/8 b - - 0 1"));
check(st.status() == GameStatus.STALEMATE && !st.inCheck(), "black king on h8, not in check, no legal move: stalemate (a draw)");
Game c1 = new Game(Board.fromFen("4k3/8/8/8/8/8/5r2/4K2R w K - 0 1"));
check(c1.legalMoves().stream().noneMatch(m -> m.kind() == MoveKind.CASTLE_KING_SIDE), "no castling through f1 while a rook attacks it");
Game c2 = new Game(Board.fromFen("4k3/8/8/8/8/8/8/4K2R w K - 0 1"));
c2.play("e1g1");
check(c2.board.at(5) != null && c2.board.at(5).type() == PieceType.ROOK && c2.board.at(6).type() == PieceType.KING, "castling moves the king to g1 and the rook to f1");
Game ep = new Game(Board.fromFen(start));
for (String m : List.of("e2e4", "a7a6", "e4e5", "d7d5")) ep.play(m);
check(ep.legalMoves().stream().anyMatch(m -> m.kind() == MoveKind.EN_PASSANT), "e5 can take d5 en passant right after d7-d5");
ep.play("h2h3"); ep.play("h7h6");
check(ep.legalMoves().stream().noneMatch(m -> m.kind() == MoveKind.EN_PASSANT), "one move later the en passant right is gone");
Game pr = new Game(Board.fromFen("8/P6k/8/8/8/8/8/K7 w - - 0 1"));
long promos = pr.legalMoves().stream().filter(m -> m.kind() == MoveKind.PROMOTION).count();
check(promos == 4, "a pawn on a7 has 4 promotion choices: queen, rook, bishop, knight");
pr.play("a7a8n");
check(pr.board.at(56).type() == PieceType.KNIGHT, "promotion to a knight puts a knight on a8");
Game pin = new Game(Board.fromFen("4k3/4r3/8/8/8/8/4B3/4K3 w - - 0 1"));
check(pin.legalMoves().stream().noneMatch(m -> m.from() == 12), "a bishop pinned to its king by a rook has 0 legal moves");
}
static void perft(String name, String fen, long[] expected) {
for (int d = 1; d <= expected.length; d++) {
Game g = new Game(Board.fromFen(fen));
String before = g.board.placement();
long n = g.perft(d);
check(n == expected[d - 1] && g.board.placement().equals(before),
String.format("%s, depth %d: %,d (published %,d)", name, d, n, expected[d - 1]));
}
}
static void check(boolean ok, String what) { System.out.println((ok ? " ok " : " FAIL ") + what); if (!ok) System.exit(1); }
}
/* Output of this exact program (javac + java 21, 2026-10-07):
* Perft: count every legal move sequence to a depth, compare with published counts
* ok start position, depth 1: 20 (published 20)
* ok start position, depth 2: 400 (published 400)
* ok start position, depth 3: 8,902 (published 8,902)
* ok start position, depth 4: 197,281 (published 197,281)
* ok position 2, Kiwipete, depth 1: 48 (published 48)
* ok position 2, Kiwipete, depth 2: 2,039 (published 2,039)
* ok position 2, Kiwipete, depth 3: 97,862 (published 97,862)
* ok position 3, depth 1: 14 (published 14)
* ok position 3, depth 2: 191 (published 191)
* ok position 3, depth 3: 2,812 (published 2,812)
* ok position 3, depth 4: 43,238 (published 43,238)
* ok position 4, depth 1: 6 (published 6)
* ok position 4, depth 2: 264 (published 264)
* ok position 4, depth 3: 9,467 (published 9,467)
* ok position 5, depth 1: 44 (published 44)
* ok position 5, depth 2: 1,486 (published 1,486)
* ok position 5, depth 3: 62,379 (published 62,379)
* Game rules
* ok fool's mate: f3 e5 g4 Qh4 is checkmate, white has 0 legal moves
* ok undo 4 times restores the start position exactly
* ok black king on h8, not in check, no legal move: stalemate (a draw)
* ok no castling through f1 while a rook attacks it
* ok castling moves the king to g1 and the rook to f1
* ok e5 can take d5 en passant right after d7-d5
* ok one move later the en passant right is gone
* ok a pawn on a7 has 4 promotion choices: queen, rook, bishop, knight
* ok promotion to a knight puts a knight on a8
* ok a bishop pinned to its king by a rook has 0 legal moves
*/How it works
Begin with the pieces. A Piece base class holds the colour. Each of the six kinds overrides one method that lists the squares it can move to. Bishops, rooks and queens slide until they hit something. Knights and kings take single steps. They all share one helper for that. The pawn and the king carry the special rules.
These lists are pseudo-legal. That means each move follows the piece's pattern, but it may leave your own king attacked. The FIDE Laws of Chess say no piece may be moved so that it exposes or leaves its own king in check. The simplest correct way to follow that rule: play each move on the board, ask if your own king is now attacked, then undo it. Keep only the moves where the answer is no. One check handles pins, moving the king into check, and escaping a check.
The try-and-undo step is why the Command pattern fits so well here. A MoveCommand plays a move and stores what it needs to reverse it: the captured piece, the castling rights, the en passant square and the half-move counter, which counts moves since the last pawn move or capture for the draw rules. Undo is then exact, and that command also gives players an undo button.
The three special moves follow the FIDE text. Castling is the one move where two pieces move: the king steps two squares toward a rook, and the rook jumps to the square the king crossed. It needs a king and rook that have never moved, empty squares between them, and a king that is not in check and does not pass through or land on an attacked square. En passant lets a pawn capture an enemy pawn that just moved two squares past it, but only on the very next move. So the board stores the skipped square for one move only. Promotion turns a pawn on the last rank into a queen, rook, bishop or knight, so the generator adds four moves.
Checkmate and stalemate fall out of the move list. No legal moves and in check is checkmate. No legal moves and not in check is stalemate, a draw.
How do you know all of this is right? Count. Perft walks every legal move sequence to a fixed depth and counts the end points. The Chess Programming Wiki publishes the correct counts. From the start position, there are 20 moves, then 400 two-move sequences, then 8,902 for three moves and 197,281 for four. The program matches those, plus four more test positions from that page. Between them they include castling, en passant captures and pawns about to promote. One wrong rule changes these numbers, so a match is strong proof.
Good follow-ups: a faster board using 64-bit numbers, one bit per square, called bitboards. Draw rules such as threefold repetition, which need a history of positions. And a chess engine, which is a search built on this move generator.
Edge cases & gotchas
- A pinned piece. It looks free to move, but moving it would open a line to its own king. The legal-move filter removes those moves.
- Castling while in check, through an attacked square, or onto an attacked square is not allowed. Castling is also lost for good once the king or that rook has moved. If that rook is captured, it is gone too.
- En passant is allowed only on the very next move after the enemy pawn moved two squares.
- An en passant capture can expose your own king along a rank, because two pawns leave that rank at once. The play-then-check filter catches it with no special code.
- Promotion offers four choices: queen, rook, bishop or knight.
- No legal moves while in check is checkmate. No legal moves while not in check is stalemate, which is a draw.
FAQ
Master LLD and system design interviews
770 interactive lessons and 90 real systems taken apart. One payment, lifetime access, no subscription.
course 1
System Design Masterclass
From absolute beginner to principal engineer, drawn step by step.
- 770 interactive lessons
- Step-by-step system design diagrams
- Live code editors
- Quizzes with instant feedback
- Progress tracking and streaks
- Lifetime access and all future lessons