!This gives away every stage. For a clean attempt, practise it first, then come back.

How this walkthrough is built

This is the longest problem in the section, because chess has real rules to get right. The steps are the same as always.

Step 1Understand the problem

Picture the real thing first

Two players, sixty-four squares, sixteen pieces each. Each kind of piece moves its own way. You can’t make a move that leaves your own king attacked. Three moves break all the patterns: castling (king and rook move together), en passant (a pawn captures a pawn that isn’t on the square it moves to), and promotion (a pawn becomes another piece). The game ends in checkmate, or in one of several kinds of draw. Online, each player is on their own device, often with a clock running.

Ask before you design

Group the questions: the rules, the endings, how it’s played, and what’s out of scope.

Functional requirements

1. FR1. An 8×8 board with the standard starting position.
2. FR2. Players alternate turns; a move is given as from-square, to-square and optional promotion (“e7e8q”).
3. FR3. Only legal moves are accepted, by the full rules: piece movement, captures, castling, en passant, promotion, and never leaving your own king in check.
4. FR4. The game detects check, checkmate and stalemate.
5. FR5. Draws by threefold repetition and the fifty-move rule.
6. FR6. The last move can be undone, any number of times.

Non-functional requirements

1. NFR1: Correct. The rules must be exactly right, and we must be able to prove it.
2. NFR2: Easy to extend. New piece types (for chess variants), clocks and notation are added, not edited in.
3. NFR3: Correct online. Two requests at once never corrupt a game.
4. NFR4: Fast enough. Listing legal moves should take microseconds, so a server can host many games and a computer player can search.

Assumptions we’ll write down

Step 2Break it into entities

Pull out the nouns

Board, square, piece, king, queen, rook, bishop, knight, pawn, colour, player, move, capture, castling, en passant, promotion, check, checkmate, stalemate, draw, turn, history, clock.

Three questions that decide if a noun is a class

This time, inheritance is right

In the parking lot we refused a class per vehicle. In tic-tac-toe X and O were just a character. In snakes and ladders a snake and a ladder became one class. The rule each time: inheritance is for different behaviour; when only the data differs, use a field.

Chess pieces are the case where the behaviour really does differ. A knight jumps in an L. A bishop slides diagonally until it hits something. A pawn moves forward but captures diagonally, moves two from its starting rank, can capture en passant, and promotes. There’s no single table of numbers that captures all of that. So a class per piece is right, and saying why it’s right here when it was wrong before is exactly what interviewers want to hear.

Look closer and there’s more structure:

So the tree is Piece → Slider (rook, bishop, queen) and Stepper (knight, king), plus Pawn. A rook, bishop and queen are one algorithm with different data, so inside Slider, the difference is just a list of directions. The lesson applied twice at two levels.

The trap: “can this piece move there?”

The most common chess design gives every piece a method like this:

abstract class Piece {
    abstract boolean canMove(Board board, Square from, Square to);
}

class Bishop extends Piece {
    boolean canMove(Board board, Square from, Square to) {
        return isDiagonal(from, to) && pathIsClear(board, from, to);
    }
}

It looks tidy, and it can’t do the job.

• It can’t see a pin. A bishop between its own king and an enemy rook can’t move at all, because moving would expose the king. canMove only knows about the bishop.
• It can’t see check. When you’re in check, almost every move is illegal except the few that deal with it. Nothing in the bishop knows you’re in check.
• It can’t list moves. “Is it checkmate?” means “are there no legal moves?” With only canMove, you’d try all 64 × 64 pairs for every piece.
• Castling and en passant don’t fit. Castling moves two pieces and depends on history (have the king and rook moved?) and on attacks (is any square the king passes attacked?). En passant depends on what the previous move was.

Step through a pin to see the difference:

The design that works splits the question in two:

1. What does this piece’s shape allow? Each piece generates its moves on the current board, ignoring whether its king would be safe. These are called pseudo-legal moves. This is the piece’s job.
2. Which of those leave my king safe? Try each move on the board, check whether the king is attacked, and take it back. This needs the whole position, so it’s the board’s job.

Piece behaviour stays in pieces. Rules about the whole position stay in the board.

Hidden state: a position is more than pieces

Two boards can have the same pieces on the same squares and still be different positions:

All of these must be updated by every move and restored exactly by every undo. Forgetting any one of them is a classic source of bugs that only show up deep in a game, which is why step 9 ends with a test that finds them.

Pull out the verbs

Generate moves, slide, step, capture, castle, capture en passant, promote, check if a square is attacked, make a move, unmake a move, detect check, mate, stalemate, count repetitions, accept a player’s move.

Give each job to the class that knows the most

CRC cards

Find what will change

Step 3Top-down or bottom-up?

Top-down: the server calls game.play(color, "e2e4"). The game needs the list of legal moves (Board.legalMoves). That needs each piece’s moves (Piece.moves), a way to try a move and take it back (make, unmake), and a way to check if the king is attacked (isAttacked, which needs Piece.attacks).

Bottom-up: squares, then pieces (each tested on an empty board), then the board’s make and unmake (tested by making and unmaking thousands of moves and checking nothing changed), then legality, then the game. And at the end, the test that proves the whole thing: perft.

Step 4Design each class

Piece and its family: how each kind moves

Job: given the board and its own square, list the moves its shape allows, and say whether it attacks a given square.

Why two methods, moves and attacks? Because they differ. A pawn moves straight ahead but attacks diagonally. A king moves by castling but castling never attacks anything. Check detection needs attacks; move generation needs moves.

Piece, Slider and Stepper are sealed: only these classes can extend them. Every piece type in the game is known, so any code that needs “what kinds of piece exist?” has a complete answer.

Board: the position, and the rules about it

Job: hold the full position and change it only through make and unmake, which update every piece of hidden state.

make returns an Undo record holding the things a move can’t be undone without: the previous castling rights, en passant square and fifty-move count. The Move itself records the piece and anything it captured. Together they’re enough to put the board back exactly.

Move and Undo: enough to go back

Move is a record: from, to, the piece that moved, the piece captured (if any), the type (normal, double push, en passant, castle, promotion), and the promotion piece. Undo is the snapshot of hidden state from just before the move.

Game: the referee

Job: accept moves from players, keep the history, and know whether the game is over.

play never builds a move from the input. It generates every legal move and looks for one whose text matches. If none matches, the move is illegal, whatever the reason. That makes “never trust the client” automatic.

Step 5How the classes relate

Step 6The class diagram, built up

Version 1: the piece hierarchy

King also overrides moves to add castling, and Pawn overrides everything.

Version 2: board and moves

Version 3: the whole picture

The six concrete pieces sit under Slider, Stepper and Pawn as in version 1.

Check it against the requirements

Step 7The patterns, and why each one is here

Copy the board, or make and unmake?

To check if a move is safe, you could copy the whole board, apply the move to the copy, and look. That’s simpler to get right, and slower: a computer player checks millions of positions, and copying 64 squares plus state for each one adds up. Make and unmake on one board is the standard choice in chess programs, at the cost of having to get unmake exactly right. Perft (step 9) is what tells you that you did. Either answer is fine in an interview with the trade-off said out loud.

Why not a Singleton

One Game per game; a server hosts thousands. Nothing about chess is global.

Patterns we deliberately didn’t use

• State for the game status. Mate, stalemate and draws are worked out from the position after each move; there’s no behaviour that differs per status except “game over”.
• Factory for pieces. fromFen and promotion create pieces with a switch; there’s no family of factories to choose between.
• Flyweight for pieces. Pieces only hold a colour, so 32 small objects is nothing. A faster engine would share one object per kind and colour.

Step 8Walk the flows

A move

1. The input is never trusted. It only matters whether it matches a generated legal move.
2. Legality is “try it and look”. The board makes the move, asks whether the mover’s king is attacked, and unmakes it. That one check catches pins, moving into check, and failing to answer a check, without any special code for each.
3. A double pawn push sets the en passant square (e3). It’s part of the Undo of the next move, so undoing restores it.

Where the special moves live

That last row hides a subtle rule: if your rook is captured on its home square, you lose that castling right, even though you never moved it. Checking only the square a move starts from misses it. Step 9 shows the only kind of test that reliably catches that.

Check, checkmate and stalemate

After each move, the game asks two questions about the player now to move: is their king attacked? and do they have any legal move?

Then the draws: if this exact position (pieces, turn, castling rights, en passant square) has now occurred three times, it’s a draw by repetition; if 100 half-moves have passed without a capture or pawn move, the fifty-move rule applies.

Undo

What walking the flows taught us

Step 9Write the code, bottom-up

Complete Java. Every output on this page comes from running it.

9.1 Colours and squares

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

record Square(int file, int rank) { 1
    private static final Square[] ALL = new Square[64];
    static {
        for (int i = 0; i < 64; i++) ALL[i] = new Square(i % 8, i / 8);
    }
    static Square at(int file, int rank) {
        return file < 0 || file > 7 || rank < 0 || rank > 7 ? null : ALL[rank * 8 + file];
    }
    static Square of(String name) {
        return at(name.charAt(0) - 'a', name.charAt(1) - '1');
    }
    static Square index(int i) { return ALL[i]; }
    int index() { return rank * 8 + file; }
    Square plus(int df, int dr) { return at(file + df, rank + dr); }
    @Override public String toString() { return "" + (char) ('a' + file) + (rank + 1); }
}

1. All 64 squares are created once and reused, so stepping across the board creates no new objects. at returns null off the board, which is how sliding pieces know to stop.

9.2 Moves

enum MoveType { NORMAL, DOUBLE_PUSH, EN_PASSANT, CASTLE, PROMOTION }

record Move(Square from, Square to, Piece piece, Piece captured, MoveType type,
            Piece promotion) {
    String uci() {
        String promo = promotion == null ? ""
            : String.valueOf(Character.toLowerCase(promotion.letter()));
        return "" + from + to + promo;
    }
    @Override public String toString() { return uci(); }
}

record Undo(int castling, Square enPassant, int halfmove) { }

9.3 Piece, Slider and Stepper

abstract sealed class Piece permits Slider, Stepper, Pawn {
    final Color color;
    Piece(Color color) { this.color = color; }

    abstract char letter();                                       // (1)
    abstract void moves(Board b, Square from, List out);    // (2)
    abstract boolean attacks(Board b, Square from, Square target);

    protected char mark(char c) {
        return color == Color.WHITE ? Character.toUpperCase(c) : c;
    }

    protected void addIfFree(Board b, Square from, Square to, List out) {
        Piece there = b.at(to);
        if (there == null)
            out.add(new Move(from, to, this, null, MoveType.NORMAL, null));
        else if (there.color != color)
            out.add(new Move(from, to, this, there, MoveType.NORMAL, null));
    }
}

abstract sealed class Slider extends Piece permits Rook, Bishop, Queen {
    Slider(Color c) { super(c); }
    abstract int[][] directions();

    void moves(Board b, Square from, List out) {
        for (int[] d : directions()) {
            for (Square s = from.plus(d[0], d[1]); s != null; s = s.plus(d[0], d[1])) {
                addIfFree(b, from, s, out);
                if (b.at(s) != null) break;                      // (3)
            }
        }
    }

    boolean attacks(Board b, Square from, Square target) {
        for (int[] d : directions()) {
            for (Square s = from.plus(d[0], d[1]); s != null; s = s.plus(d[0], d[1])) {
                if (s.equals(target)) return true;
                if (b.at(s) != null) break;
            }
        }
        return false;
    }
}

abstract sealed class Stepper extends Piece permits Knight, King {
    Stepper(Color c) { super(c); }
    abstract int[][] steps();

    void moves(Board b, Square from, List out) {
        for (int[] d : steps()) {
            Square s = from.plus(d[0], d[1]);
            if (s != null) addIfFree(b, from, s, out);
        }
    }

    boolean attacks(Board b, Square from, Square target) {
        for (int[] d : steps())
            if (target.equals(from.plus(d[0], d[1]))) return true;
        return false;
    }
}

1. Upper case for white, lower case for black, as in FEN.
2. Pseudo-legal: everything the piece’s shape allows, even if it leaves its own king in check. The board filters.
3. A slider stops at the first piece it meets, after adding it as a capture if it’s an enemy.

9.4 The six pieces

final class Rook extends Slider {
    private static final int[][] D = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
    Rook(Color c) { super(c); }
    int[][] directions() { return D; }
    char letter() { return mark('r'); }
}

final class Bishop extends Slider {
    private static final int[][] D = { {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };
    Bishop(Color c) { super(c); }
    int[][] directions() { return D; }
    char letter() { return mark('b'); }
}

final class Queen extends Slider {
    private static final int[][] D = {
        {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };
    Queen(Color c) { super(c); }
    int[][] directions() { return D; }
    char letter() { return mark('q'); }
}

final class Knight extends Stepper {
    private static final int[][] D = {
        {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2} };
    Knight(Color c) { super(c); }
    int[][] steps() { return D; }
    char letter() { return mark('n'); }
}

final class King extends Stepper {
    private static final int[][] D = {
        {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };
    King(Color c) { super(c); }
    int[][] steps() { return D; }
    char letter() { return mark('k'); }

    @Override void moves(Board b, Square from, List out) {
        super.moves(b, from, out);
        int rank = color == Color.WHITE ? 0 : 7;
        if (!from.equals(Square.at(4, rank)) || b.isAttacked(from, color.other())) return;
        if (b.canCastle(color, true) && empty(b, rank, 5, 6)
                && safe(b, rank, 5, 6))                           // (4)
            out.add(new Move(from, Square.at(6, rank), this, null,
                             MoveType.CASTLE, null));
        if (b.canCastle(color, false) && empty(b, rank, 1, 3)
                && safe(b, rank, 2, 3))
            out.add(new Move(from, Square.at(2, rank), this, null,
                             MoveType.CASTLE, null));
    }

    private boolean empty(Board b, int rank, int lo, int hi) {
        for (int f = lo; f <= hi; f++) if (b.at(Square.at(f, rank)) != null) return false;
        return true;
    }

    private boolean safe(Board b, int rank, int lo, int hi) {
        for (int f = lo; f <= hi; f++)
            if (b.isAttacked(Square.at(f, rank), color.other())) return false;
        return true;
    }
}

1. The king may not castle out of check, through an attacked square, or into one. Queen-side castling needs b1 empty but not safe: the king never crosses b1, only the rook does. That asymmetry is in the rules, and it’s easy to get wrong.

9.5 The pawn

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

    void moves(Board b, Square from, List out) {
        int last = color == Color.WHITE ? 7 : 0, start = color == Color.WHITE ? 1 : 6;
        Square one = from.plus(0, dir());
        if (one != null && b.at(one) == null) {
            add(from, one, null, out, one.rank() == last);
            Square two = from.plus(0, 2 * dir());
            if (from.rank() == start && b.at(two) == null)
                out.add(new Move(from, two, this, null, MoveType.DOUBLE_PUSH, null));
        }
        for (int df : new int[] { -1, 1 }) {
            Square s = from.plus(df, dir());
            if (s == null) continue;
            Piece there = b.at(s);
            if (there != null && there.color != color)
                add(from, s, there, out, s.rank() == last);
            else if (s.equals(b.enPassant()))                     // (5)
                out.add(new Move(from, s, this, b.at(Square.at(s.file(), from.rank())),
                                 MoveType.EN_PASSANT, null));
        }
    }

    private void add(Square from, Square to, Piece captured, List out,
                     boolean promote) {
        if (!promote) {
            out.add(new Move(from, to, this, captured, MoveType.NORMAL, null));
            return;
        }
        for (Piece p : List.of(new Queen(color), new Rook(color), new Bishop(color),
                               new Knight(color)))
            out.add(new Move(from, to, this, captured, MoveType.PROMOTION, p));
    }

    boolean attacks(Board b, Square from, Square target) {
        return target.rank() == from.rank() + dir()
            && Math.abs(target.file() - from.file()) == 1;
    }
}

1. The en passant square is the one the enemy pawn passed over. The captured pawn is beside us, on our own rank, not on the square we move to.

9.6 The board

final class Board {
    private static final int WK = 1, WQ = 2, BK = 4, BQ = 8;
    private final Piece[] squares = new Piece[64];
    private Color turn = Color.WHITE;
    private int castling;                                         // (1)
    private Square enPassant;
    private int halfmove;

    Piece at(Square s) { return squares[s.index()]; }
    Color turn() { return turn; }
    Square enPassant() { return enPassant; }
    int halfmove() { return halfmove; }

    boolean canCastle(Color c, boolean kingSide) {
        int bit = c == Color.WHITE ? (kingSide ? WK : WQ) : (kingSide ? BK : BQ);
        return (castling & bit) != 0;
    }

    boolean isAttacked(Square target, Color by) {
        for (int i = 0; i < 64; i++) {
            Piece p = squares[i];
            if (p != null && p.color == by && p.attacks(this, Square.index(i), target))
                return true;
        }
        return false;
    }

    Square kingOf(Color c) {
        for (int i = 0; i < 64; i++)
            if (squares[i] instanceof King k && k.color == c) return Square.index(i);
        throw new IllegalStateException("no " + c + " king");
    }

    boolean inCheck(Color c) { return isAttacked(kingOf(c), c.other()); }

    List legalMoves() {
        List pseudo = new ArrayList<>(), legal = new ArrayList<>();
        for (int i = 0; i < 64; i++) {
            Piece p = squares[i];
            if (p != null && p.color == turn) p.moves(this, Square.index(i), pseudo);
        }
        Color me = turn;
        for (Move m : pseudo) {                                   // (2)
            Undo u = make(m);
            if (!inCheck(me)) legal.add(m);
            unmake(m, u);
        }
        return legal;
    }

1. Castling rights as four bits: white king side, white queen side, black king side, black queen side.
2. Try each pseudo-legal move, keep it if our king isn’t attacked afterwards, and always take it back.

9.7 Make and unmake

    Undo make(Move m) {
        Undo u = new Undo(castling, enPassant, halfmove);
        squares[m.from().index()] = null;
        if (m.type() == MoveType.EN_PASSANT)
            squares[Square.at(m.to().file(), m.from().rank()).index()] = null;
        squares[m.to().index()] = m.promotion() != null ? m.promotion() : m.piece();
        if (m.type() == MoveType.CASTLE) {                        // (3)
            int r = m.from().rank();
            boolean kingSide = m.to().file() == 6;
            Square rf = Square.at(kingSide ? 7 : 0, r);
            Square rt = Square.at(kingSide ? 5 : 3, r);
            squares[rt.index()] = squares[rf.index()];
            squares[rf.index()] = null;
        }
        enPassant = m.type() == MoveType.DOUBLE_PUSH
            ? Square.at(m.from().file(), (m.from().rank() + m.to().rank()) / 2) : null;
        castling &= ~lostRights(m.from()) & ~lostRights(m.to());  // (4)
        halfmove = m.piece() instanceof Pawn || m.captured() != null ? 0 : halfmove + 1;
        turn = turn.other();
        return u;
    }

    void unmake(Move m, Undo u) {
        turn = turn.other();
        squares[m.from().index()] = m.piece();
        squares[m.to().index()] = null;
        if (m.type() == MoveType.EN_PASSANT)
            squares[Square.at(m.to().file(), m.from().rank()).index()] = m.captured();
        else squares[m.to().index()] = m.captured();
        if (m.type() == MoveType.CASTLE) {
            int r = m.from().rank();
            boolean kingSide = m.to().file() == 6;
            Square rf = Square.at(kingSide ? 7 : 0, r);
            Square rt = Square.at(kingSide ? 5 : 3, r);
            squares[rf.index()] = squares[rt.index()];
            squares[rt.index()] = null;
        }
        castling = u.castling();
        enPassant = u.enPassant();
        halfmove = u.halfmove();
    }

    private static int lostRights(Square s) {
        return switch (s.toString()) {
            case "e1" -> WK | WQ;
            case "h1" -> WK;
            case "a1" -> WQ;
            case "e8" -> BK | BQ;
            case "h8" -> BK;
            case "a8" -> BQ;
            default -> 0;
        };
    }

1. Castling is recorded as the king’s move; the rook’s move is implied and done here.
2. A move from a home square (the king or rook moved) or to one (the rook was captured there) loses that right forever.

9.8 Loading positions

    String key() {                                                // (5)
        StringBuilder sb = new StringBuilder(72);
        for (Piece p : squares) sb.append(p == null ? '.' : p.letter());
        return sb.append(turn.ordinal()).append(castling).append(enPassant).toString();
    }

    static Board fromFen(String fen) {
        String[] f = fen.split(" ");
        Board b = new Board();
        String[] rows = f[0].split("/");
        for (int r = 0; r < 8; r++) {
            int file = 0;
            for (char ch : rows[7 - r].toCharArray()) {
                if (Character.isDigit(ch)) { file += ch - '0'; continue; }
                Color c = Character.isUpperCase(ch) ? Color.WHITE : Color.BLACK;
                Square sq = Square.at(file++, r);
                b.squares[sq.index()] = switch (Character.toLowerCase(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);
                    default -> new Pawn(c);
                };
            }
        }
        b.turn = f[1].equals("w") ? Color.WHITE : Color.BLACK;
        for (char ch : f[2].toCharArray())
            b.castling |= switch (ch) {
                case 'K' -> WK;
                case 'Q' -> WQ;
                case 'k' -> BK;
                case 'q' -> BQ;
                default -> 0;
            };
        b.enPassant = f[3].equals("-") ? null : Square.of(f[3]);
        b.halfmove = f.length > 4 ? Integer.parseInt(f[4]) : 0;
        return b;
    }

    static Board start() {
        return fromFen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
    }

    @Override public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int r = 7; r >= 0; r--) {
            for (int f = 0; f < 8; f++) {
                Piece p = at(Square.at(f, r));
                sb.append(p == null ? '.' : p.letter());
            }
            if (r > 0) sb.append('\n');
        }
        return sb.toString();
    }
}

1. The repetition rule counts positions as the same only if the pieces, the player to move, the castling rights and the en passant square all match. The key includes exactly those.

FEN (Forsyth–Edwards Notation) is the standard one-line description of a chess position. Being able to load one means any test can start from any position in one line.

9.9 The game

enum Status { ACTIVE, CHECK, CHECKMATE, STALEMATE, DRAW_FIFTY_MOVES, DRAW_REPETITION }

enum MoveResult { OK, GAME_OVER, NOT_YOUR_TURN, ILLEGAL }

final class Game {
    private record Played(Move move, Undo undo) { }

    private final Board board;
    private final Deque history = new ArrayDeque<>();
    private final Map seen = new HashMap<>();
    private Status status = Status.ACTIVE;

    Game(Board board) {
        this.board = board;
        seen.merge(board.key(), 1, Integer::sum);
        status = evaluate();
    }

    synchronized MoveResult play(Color who, String uci) {
        if (isOver()) return MoveResult.GAME_OVER;
        if (who != board.turn()) return MoveResult.NOT_YOUR_TURN;
        Move chosen = null;
        for (Move m : board.legalMoves())                         // (1)
            if (m.uci().equals(uci)) chosen = m;
        if (chosen == null) return MoveResult.ILLEGAL;
        history.push(new Played(chosen, board.make(chosen)));
        int times = seen.merge(board.key(), 1, Integer::sum);
        status = times >= 3 ? Status.DRAW_REPETITION : evaluate();
        return MoveResult.OK;
    }

    synchronized boolean undo() {
        if (history.isEmpty()) return false;
        seen.merge(board.key(), -1, Integer::sum);
        Played p = history.pop();
        board.unmake(p.move(), p.undo());
        status = evaluate();
        return true;
    }

    private Status evaluate() {
        boolean check = board.inCheck(board.turn());
        if (board.legalMoves().isEmpty())
            return check ? Status.CHECKMATE : Status.STALEMATE;
        if (board.halfmove() >= 100) return Status.DRAW_FIFTY_MOVES;   // (2)
        return check ? Status.CHECK : Status.ACTIVE;
    }

    synchronized boolean isOver() {
        return status != Status.ACTIVE && status != Status.CHECK;
    }
    synchronized Status status() { return status; }
    synchronized Color turn() { return board.turn(); }
    synchronized String board() { return board.toString(); }
    synchronized List legal() {
        return board.legalMoves().stream().map(Move::uci).sorted().toList();
    }
}

1. The only way a move gets played is by matching one the board generated.
2. Fifty moves each is 100 half-moves. Mate takes priority: a mating move on the hundredth half-move still wins.

9.10 Putting it together

The fastest checkmate in chess, Fool’s Mate, plus the special cases:

public class Demo {
    public static void main(String[] args) {
        Game g = new Game(Board.start());
        System.out.println("e2e5: " + g.play(Color.WHITE, "e2e5"));
        System.out.println("black first: " + g.play(Color.BLACK, "e7e5"));
        g.play(Color.WHITE, "f2f3");
        g.play(Color.BLACK, "e7e5");
        g.play(Color.WHITE, "g2g4");
        System.out.println("d8h4: " + g.play(Color.BLACK, "d8h4") + " -> " + g.status());
        System.out.println(g.board());
        System.out.println("after mate: " + g.play(Color.WHITE, "a2a3"));
        g.undo();
        System.out.println("undo: " + g.status() + ", "
            + g.legal().size() + " legal moves");

        Game st = new Game(Board.fromFen("7k/5Q2/6K1/8/8/8/8/8 b - - 0 1"));
        System.out.println("stalemate position: " + st.status());
        Game ep = new Game(Board.fromFen("4k3/8/8/8/3p4/8/4P3/4K3 w - - 0 1"));
        ep.play(Color.WHITE, "e2e4");
        System.out.println("en passant d4e3 allowed: " + ep.legal().contains("d4e3"));
        Game rep = new Game(Board.start());
        String[] shuffle = { "g1f3", "g8f6", "f3g1", "f6g8",
                             "g1f3", "g8f6", "f3g1", "f6g8" };
        for (int i = 0; i < shuffle.length; i++)
            rep.play(i % 2 == 0 ? Color.WHITE : Color.BLACK, shuffle[i]);
        System.out.println("knights out and back twice: " + rep.status());
    }
}

e2e5: ILLEGAL
black first: NOT_YOUR_TURN
d8h4: OK -> CHECKMATE
rnb.kbnr
pppp.ppp
........
....p...
......Pq
.....P..
PPPPP..P
RNBQKBNR
after mate: GAME_OVER
undo: ACTIVE, 30 legal moves
stalemate position: STALEMATE
en passant d4e3 allowed: true
knights out and back twice: DRAW_REPETITION

The black queen on h4 attacks the white king along the diagonal; f2 and g2 have both moved, and nothing can block or capture. After undo, it’s black to move again with 30 choices. In the repetition test, the starting position appears for the third time after both players move their knights out and back twice.

9.11 Prove it: perft

The demo shows the rules working in a few positions. That’s not proof. A chess move generator has thousands of edge cases: a pinned pawn that could capture en passant, castling when a rook has been captured, promotion with capture into check. Hand-written tests cover a handful.

Chess programmers solved this long ago with perft (performance test): count every sequence of legal moves to a given depth, and compare with numbers that are published and agreed by many independent engines. If your counts match at depth 5, your rules are right in millions of positions.

final class Perft {
    static long count(Board b, int depth) {
        if (depth == 0) return 1;
        long n = 0;
        for (Move m : b.legalMoves()) {
            Undo u = b.make(m);
            n += count(b, depth - 1);
            b.unmake(m, u);
        }
        return n;
    }
}

Our results, against four standard test positions: the start, “Kiwipete” (built to stress castling, en passant and promotion), and two more from the chess programming community’s well-known test set:

start: d1=20 d2=400 d3=8902 d4=197281 d5=4865609  (1980 ms)
kiwipete: d1=48 d2=2039 d3=97862 d4=4085603  (2096 ms)
position 3: d1=14 d2=191 d3=2812 d4=43238 d5=674624  (240 ms)
position 4: d1=6 d2=264 d3=9467 d4=422333  (204 ms)

Every number matches the published values. That’s about 10 million positions in total, each reached by making moves and checked by unmaking them, and every count agrees.

To show what perft catches, we planted two realistic bugs, one at a time, and ran Kiwipete again:

The second bug is invisible until depth 4: 56 extra positions out of four million. No hand-written test we’d have thought of would find it. This is the strongest answer to “how would you test this?” in the whole interview.

Step 10Make it safe

Online play needs the same thing as tic-tac-toe: one lock per game, so two requests can’t both pass the turn check. Every public method of Game is synchronized. But chess has a twist worth a whole section.

The read that writes

legalMoves() looks like a read: it returns a list and changes nothing. But look inside: it makes every candidate move on the board, checks the king, and unmakes it. For a few microseconds at a time, the board is in a half-played state.

So imagine the server’s UI handler calls board.legalMoves() to highlight squares, without the lock, while another thread does the same. We tested exactly that: four threads calling legalMoves() on one board in the Kiwipete position, 2,000 times each, with no lock:

Nearly every call threw an exception, some returned the wrong number of moves, and every time the board was left corrupted. Nothing was “writing” in the usual sense: every caller was only asking a question.

The lessons:

• A method that changes state temporarily is a write, for thread-safety purposes, even if it puts everything back.
• That’s why Game.legal() is synchronized like play, and why Board is never handed out: the game exposes board() as text, not the object.
• If many readers need legal moves at once (spectators, analysis), give each one its own copy of the board. Copies are cheap; corrupted games aren’t.

Clocks

A chess clock adds one more race: a move arriving at the instant the mover’s time runs out. Keep the clock outside the rules: a ChessClock with a Clock passed in. Inside the game’s lock, first charge the elapsed time to the player to move; if they’re out of time, the move is refused and they lose on time. The server’s receive time decides, applied under the lock, so the answer is the same however the threads are scheduled.

Step 11Follow-ups, extended without editing

Faster repetition checks

Building a 70-character string after every move is fine for a server, too slow for a computer player that visits millions of positions. Real engines use Zobrist hashing: give every (piece, square) pair, each castling right, each en passant file and the side to move a random 64-bit number. A position’s key is all of its numbers combined with XOR, and because XOR undoes itself, make and unmake can update the key with two or three XORs instead of rebuilding it. It slots into Board as one more field in make, unmake and the Undo snapshot.

Standard notation

Players expect “Nf3”, not “g1f3”. That’s a translator, not a rule: a NotationParser that takes the legal moves and some text and finds the one move it describes (adding the file or rank when two knights could both reach f3). Because it works from the legal move list, it can’t accept an illegal move. Game doesn’t change.

A computer player

The tic-tac-toe walkthrough built a MoveChooser that searched every possible game. Chess is far too big for that, so a chess MoveChooser searches a few moves ahead with minimax and alpha-beta pruning (skipping lines that can’t change the decision), and scores positions with a rule of thumb: material, piece activity, king safety. Make and unmake on one board is exactly what that search needs, and perft has already shown it’s correct.

Chess variants

Chess960 shuffles the back rank, so castling must work from any king and rook squares: King.moves and make need the rook’s file instead of assuming h or a. A new piece (some variants add one that moves like a knight and a bishop combined) is a new subclass of Piece, plus adding it to the permits list. That’s the cost and the safety of a sealed hierarchy: every new piece is a deliberate change, and the compiler points to everything that must handle it.

Spectators

People watching a game want moves as they happen. A GameListener on Game, told after each move outside the lock (as in every other problem here), with the move’s UCI and the new FEN. Spectators never touch the board.

Mistakes people make on this one

• *A canMove(from, to) on each piece,* which can’t see pins, check, or list moves for checkmate.
• *A giant switch on piece type* inside the board, instead of pieces that generate their own moves.
• Forgetting hidden state: castling rights, en passant, the fifty-move counter, repetitions.
• Castling through check, or losing the right only when the rook moves, not when it’s captured.
• En passant capturing on the wrong square.
• Undo that restores pieces but not hidden state.
• Testing with a few hand-picked positions and calling the rules correct.
• Treating legal-move generation as a read and calling it without a lock.
• Trusting the client’s move.

How this answer gets scored

The whole design on one page

1. Pieces: sealed Piece → Slider (rook, bishop, queen: directions), Stepper (knight, king: offsets), Pawn. Each generates pseudo-legal moves and answers attacks. Inheritance because behaviour differs.
2. Board: 64 squares plus hidden state (turn, castling bits, en passant, fifty-move count). make returns an Undo; unmake restores everything.
3. Legality: generate pseudo-legal moves, make each, keep it if the king is safe, unmake.
4. Special moves: castling in King (rights, empty, never through check); en passant and promotion in Pawn; their side effects in make/unmake.
5. Game: match input against legal moves; history of (move, undo); check, mate, stalemate, repetition, fifty moves.
6. Proof and safety: perft matches published counts; one lock per game, including legality checks, because they temporarily change the board.