These are the notes for Low-Level Design (LLD) episode 86, the second half of the chess machine-coding question. Episode 85 built the board, the squares, the Piece hierarchy and move generation. Here we add move validation, check detection, checkmate and stalemate, a game status, castling, en passant, pawn promotion, a move history with undo using the Command pattern (and the Memento alternative), and a chess clock.
How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly. The chess rules are the standard rules of chess; the players are made up.
1. The problem: "I took your king, Dadaji!"
The grandson's king is on e1, with his bishop right in front of it on e2. He moves the bishop away ("bishops move diagonally, it's allowed!"), and Dadaji's rook on e8 slides down the open e-file and takes the king. The game stops making sense.
Dadaji's rule: in real chess the king is never captured. You may never make a move that leaves your own king attacked. And when a player has no safe move at all, the game ends: checkmate if his king is attacked (he loses), stalemate if it isn't (a draw).
| Real life | In the design |
|---|---|
| "That bishop move was never allowed" | Move validation: legal moves, not just pseudo-legal |
| "Your king is under attack!" | Check detection |
| "No safe move, king attacked" | Checkmate |
| "No safe move, king not attacked" | Stalemate (a draw) |
| A one-time coupon | Castling (only if king and rook never moved) |
| "Jump on now or the train leaves" | En passant (only on the very next move) |
| A trainee promoted to manager | Pawn promotion |
| "Dadaji, take it back!" | Undo with a move history |
| The two-sided clock in park tournaments | Chess clock |
2. Attempt 1: validate with the piece's own rule only
Episode 85's play checked only "is the target in this piece's moves()?".
import java.util.*; enum Color { WHITE, BLACK }
record Sq(int f, int r) { boolean on() { return f >= 0 && f < 8 && r >= 0 && r < 8; }
Sq plus(int[] d) { return new Sq(f + d[0], r + d[1]); }
static Sq of(String s) { return new Sq(s.charAt(0) - 'a', s.charAt(1) - '1'); }
public String toString() { return "" + (char) ('a' + f) + (r + 1); } }
abstract class Piece { final Color color; final int[][] dirs; final boolean slides;
Piece(Color c, int[][] d, boolean s) { color = c; dirs = d; slides = s; }
List<Sq> moves(Map<Sq, Piece> b, Sq from) { List<Sq> out = new ArrayList<>(); // pseudo-legal, ep. 85
for (int[] d : dirs) for (Sq s = from.plus(d); s.on(); s = s.plus(d)) {
Piece p = b.get(s); if (p == null || p.color != color) out.add(s);
if (p != null || !slides) break; }
return out; } }
interface D { int[][] LINE = {{1,0},{-1,0},{0,1},{0,-1}}, DIAG = {{1,1},{1,-1},{-1,1},{-1,-1}},
ALL = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; }
class Rook extends Piece { Rook(Color c) { super(c, D.LINE, true); } }
class Bishop extends Piece { Bishop(Color c) { super(c, D.DIAG, true); } }
class King extends Piece { King(Color c) { super(c, D.ALL, false); } }
class Game { final Map<Sq, Piece> board = new HashMap<>();
void put(String s, Piece p) { board.put(Sq.of(s), p); }
String play(String from, String to) { Sq f = Sq.of(from), t = Sq.of(to); Piece p = board.get(f);
if (!p.moves(board, f).contains(t)) return "illegal"; // only the piece's own rule
Piece taken = board.put(t, board.remove(f)); String s = p.color + " " + from + "-" + to;
return taken == null ? s : s + ", captured the " + taken.getClass().getSimpleName(); } }
public class Main { public static void main(String[] args) {
Game g = new Game(); g.put("e1", new King(Color.WHITE)); g.put("e2", new Bishop(Color.WHITE));
g.put("e8", new Rook(Color.BLACK)); g.put("h8", new King(Color.BLACK));
System.out.println(g.play("e2", "d3")); // the bishop steps aside...
System.out.println(g.play("e8", "e1")); // ...and the king is taken
System.out.println("pieces left: " + g.board.size() + ", game over? nobody knows"); } }
Real output:
WHITE e2-d3
BLACK e8-e1, captured the King
pieces left: 3, game over? nobody knows
Why it failed
- Episode 85's moves are pseudo-legal: they follow each piece's own rule but ignore the king.
- The bishop on e2 was pinned: it stood between its own king and an enemy rook, so moving off that line exposed the king.
- And with no idea of check, the game can't tell when it's over:
game over? nobody knows.
3. Check detection and legal moves
- Attacked square: a square is attacked by black if any black piece could move to it. We already have that: ask every black piece for its
moves(). - Check: your king's square is attacked by the other side.
- Legal move: a pseudo-legal move that, when made on a copy of the board, does not leave your own king in check. "Try it, then look." This is the simplest correct way to validate moves, and it automatically handles pins, moving into check, and answering a check.
import java.util.*; enum Color { WHITE, BLACK; Color other() { return this == WHITE ? BLACK : WHITE; } }
record Sq(int f, int r) { boolean on() { return f >= 0 && f < 8 && r >= 0 && r < 8; }
Sq plus(int[] d) { return new Sq(f + d[0], r + d[1]); }
static Sq of(String s) { return new Sq(s.charAt(0) - 'a', s.charAt(1) - '1'); }
public String toString() { return "" + (char) ('a' + f) + (r + 1); } }
abstract class Piece { final Color color; final int[][] dirs; final boolean slides; // as in episode 85
Piece(Color c, int[][] d, boolean s) { color = c; dirs = d; slides = s; }
List<Sq> moves(Map<Sq, Piece> b, Sq from) { List<Sq> out = new ArrayList<>(); // pseudo-legal moves
for (int[] d : dirs) for (Sq s = from.plus(d); s.on(); s = s.plus(d)) {
Piece p = b.get(s); if (p == null || p.color != color) out.add(s);
if (p != null || !slides) break; }
return out; } }
interface D { int[][] LINE = {{1,0},{-1,0},{0,1},{0,-1}}, ALL = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; }
class Rook extends Piece { Rook(Color c) { super(c, D.LINE, true); } }
class King extends Piece { King(Color c) { super(c, D.ALL, false); } }
class Board { final Map<Sq, Piece> m = new HashMap<>(); Board put(String s, Piece p) { m.put(Sq.of(s), p); return this; }
boolean attacked(Sq sq, Color by) { // can any `by` piece move to sq?
for (var e : m.entrySet()) { Piece p = e.getValue();
if (p.color == by && p.moves(m, e.getKey()).contains(sq)) return true; }
return false; }
boolean inCheck(Color c) { // is c's king attacked?
for (var e : m.entrySet()) if (e.getValue() instanceof King && e.getValue().color == c)
return attacked(e.getKey(), c.other());
return false; }
List<Sq> legal(Sq from) { Piece p = m.get(from); List<Sq> ok = new ArrayList<>();
for (Sq to : p.moves(m, from)) { Board copy = new Board(); copy.m.putAll(m); // try it on a copy
copy.m.put(to, copy.m.remove(from)); if (!copy.inCheck(p.color)) ok.add(to); } // my king safe? keep it
return ok; } }
public class Main { public static void main(String[] args) { Color W = Color.WHITE, B = Color.BLACK;
Board b = new Board().put("e1", new King(W)).put("e2", new Rook(W)).put("e8", new Rook(B)).put("h8", new King(B));
System.out.println("pinned rook on e2 can go to " + b.legal(Sq.of("e2"))); // pinned: only along the pin
b.m.put(Sq.of("a2"), b.m.remove(Sq.of("e2"))); // say it moved sideways anyway
System.out.println("check " + b.inCheck(W) + ", king " + b.legal(Sq.of("e1")) + ", rook " + b.legal(Sq.of("a2"))); } }
Real output:
pinned rook on e2 can go to [e3, e4, e5, e6, e7, e8]
check true, king [f1, d1, f2, d2], rook [e2]
- The pinned rook on e2 can still slide along the pin (e3-e8, including capturing the black rook on e8), but not sideways.
- After it moved to a2 anyway: white is in check. The king can go to f1, d1, f2 or d2, but not e2 (still on the open e-file). The rook's only legal move is back to e2, to block.
Color.other(): an enum can have methods.WHITE.other()isBLACK.
4. Game status: checkmate and stalemate
Game status is the state the game is in now. Count the legal moves of the side to move and ask one question, "am I in check?":
| Legal moves? | In check? | Status |
|---|---|---|
| Yes | No | ACTIVE |
| Yes | Yes | CHECK (must answer it) |
| No | Yes | CHECKMATE (that side loses) |
| No | No | STALEMATE (a draw) |
import java.util.*; enum Color { WHITE, BLACK; Color other() { return this == WHITE ? BLACK : WHITE; } }
record Sq(int f, int r) { boolean on() { return f >= 0 && f < 8 && r >= 0 && r < 8; }
Sq plus(int[] d) { return new Sq(f + d[0], r + d[1]); }
static Sq of(String s) { return new Sq(s.charAt(0) - 'a', s.charAt(1) - '1'); }
public String toString() { return "" + (char) ('a' + f) + (r + 1); } }
abstract class Piece { final Color color; final int[][] dirs; final boolean slides; // as in episode 85
Piece(Color c, int[][] d, boolean s) { color = c; dirs = d; slides = s; }
List<Sq> moves(Map<Sq, Piece> b, Sq from) { List<Sq> out = new ArrayList<>(); // pseudo-legal moves
for (int[] d : dirs) for (Sq s = from.plus(d); s.on(); s = s.plus(d)) {
Piece p = b.get(s); if (p == null || p.color != color) out.add(s);
if (p != null || !slides) break; }
return out; } }
interface D { int[][] LINE = {{1,0},{-1,0},{0,1},{0,-1}}, ALL = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; }
class Rook extends Piece { Rook(Color c) { super(c, D.LINE, true); } }
class King extends Piece { King(Color c) { super(c, D.ALL, false); } }
enum Status { ACTIVE, CHECK, CHECKMATE, STALEMATE }
class Board { final Map<Sq, Piece> m = new HashMap<>(); Board put(String s, Piece p) { m.put(Sq.of(s), p); return this; }
boolean attacked(Sq sq, Color by) { for (var e : m.entrySet()) { Piece p = e.getValue(); // as before
if (p.color == by && p.moves(m, e.getKey()).contains(sq)) return true; } return false; }
boolean inCheck(Color c) { for (var e : m.entrySet()) if (e.getValue() instanceof King && e.getValue().color == c)
return attacked(e.getKey(), c.other()); return false; }
List<Sq> legal(Sq from) { Piece p = m.get(from); List<Sq> ok = new ArrayList<>();
for (Sq to : p.moves(m, from)) { Board copy = new Board(); copy.m.putAll(m); copy.m.put(to, copy.m.remove(from));
if (!copy.inCheck(p.color)) ok.add(to); } return ok; } // as before
Status status(Color c) { boolean any = m.keySet().stream().anyMatch(s -> m.get(s).color == c && !legal(s).isEmpty());
boolean check = inCheck(c); if (any) return check ? Status.CHECK : Status.ACTIVE; // game status
return check ? Status.CHECKMATE : Status.STALEMATE; } } // no legal move: mate or stalemate
public class Main { static void show(String what, Board b) { System.out.println(what + ": " + b.status(Color.BLACK)); }
public static void main(String[] args) { Color W = Color.WHITE, B = Color.BLACK; // black king h8, black to move
show("Kf6, Rb7", new Board().put("h8", new King(B)).put("f6", new King(W)).put("b7", new Rook(W)));
show("Kf6, Ra8", new Board().put("h8", new King(B)).put("f6", new King(W)).put("a8", new Rook(W)));
show("Kg6, Ra8", new Board().put("h8", new King(B)).put("g6", new King(W)).put("a8", new Rook(W)));
show("Kf6, Rg7", new Board().put("h8", new King(B)).put("f6", new King(W)).put("g7", new Rook(W))); } }
Real output:
Kf6, Rb7: ACTIVE
Kf6, Ra8: CHECK
Kg6, Ra8: CHECKMATE
Kf6, Rg7: STALEMATE
In every position the black king is on h8 and it's black to move:
- Kf6, Rb7: the rook guards rank 7, but g8 is free:
ACTIVE. - Kf6, Ra8: check along rank 8, but the king escapes to h7 (f6 doesn't guard h7):
CHECK. - Kg6, Ra8: the white king on g6 guards g7 and h7, the rook guards g8 and gives check:
CHECKMATE. - Kf6, Rg7: the king isn't attacked, but g8 and h7 are attacked by the rook, and taking the rook on g7 is impossible because the white king on f6 defends it:
STALEMATE.
A common bug is calling every "no legal move" position checkmate; that turns a stalemate draw into a win.
5. Castling
Castling is the only move where two pieces move together. Castling short (kingside, written O-O): king e1 → g1, rook h1 → f1. Castling long (queenside, O-O-O): king e1 → c1, rook a1 → d1. The conditions (standard rules):
- Neither the king nor that rook has ever moved in this game (moving away and back still counts).
- All squares between them are empty.
- The king is not in check, and doesn't pass through or land on an attacked square.
Design: a moved flag on Piece, set on every move, and reuse attacked() from check detection.
import java.util.*; enum Color { WHITE, BLACK; Color other() { return this == WHITE ? BLACK : WHITE; } }
record Sq(int f, int r) { boolean on() { return f >= 0 && f < 8 && r >= 0 && r < 8; }
Sq plus(int[] d) { return new Sq(f + d[0], r + d[1]); }
static Sq of(String s) { return new Sq(s.charAt(0) - 'a', s.charAt(1) - '1'); }
public String toString() { return "" + (char) ('a' + f) + (r + 1); } }
abstract class Piece { final Color color; final int[][] dirs; final boolean slides; boolean moved; // + moved
Piece(Color c, int[][] d, boolean s) { color = c; dirs = d; slides = s; }
List<Sq> moves(Map<Sq, Piece> b, Sq from) { List<Sq> out = new ArrayList<>(); // pseudo-legal moves
for (int[] d : dirs) for (Sq s = from.plus(d); s.on(); s = s.plus(d)) {
Piece p = b.get(s); if (p == null || p.color != color) out.add(s);
if (p != null || !slides) break; }
return out; } }
interface D { int[][] LINE = {{1,0},{-1,0},{0,1},{0,-1}}, ALL = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; }
class Rook extends Piece { Rook(Color c) { super(c, D.LINE, true); } }
class King extends Piece { King(Color c) { super(c, D.ALL, false); } }
class Board { final Map<Sq, Piece> m = new HashMap<>(); Board put(String s, Piece p) { m.put(Sq.of(s), p); return this; }
boolean attacked(Sq sq, Color by) { for (var e : m.entrySet()) { Piece p = e.getValue(); // as before
if (p.color == by && p.moves(m, e.getKey()).contains(sq)) return true; } return false; }
Board move(String from, String to) { Piece p = m.remove(Sq.of(from)); p.moved = true; return put(to, p); }
String castleShort(Color c) { // O-O: king e -> g, rook h -> f
int r = c == Color.WHITE ? 0 : 7; Sq e = new Sq(4, r), f = new Sq(5, r), g = new Sq(6, r), h = new Sq(7, r);
Piece k = m.get(e), rook = m.get(h);
if (k == null || rook == null || k.moved || rook.moved) return "refused: king or rook has moved";
if (m.containsKey(f) || m.containsKey(g)) return "refused: " + f + " and " + g + " must be empty";
for (Sq s : List.of(e, f, g)) if (attacked(s, c.other())) return "refused: " + s + " is attacked";
m.put(g, m.remove(e)); m.put(f, m.remove(h)); k.moved = rook.moved = true; // both move in one turn
return "O-O: king to " + g + ", rook to " + f; } }
public class Main { static Color W = Color.WHITE, B = Color.BLACK;
static Board start() { return new Board().put("e1", new King(W)).put("h1", new Rook(W)).put("e8", new King(B)); }
public static void main(String[] args) {
System.out.println("1. " + start().castleShort(W));
System.out.println("2. " + start().put("f8", new Rook(B)).castleShort(W)); // black rook eyes f1
System.out.println("3. " + start().move("e1", "e2").move("e2", "e1").castleShort(W)); } } // went and came back
Real output:
1. O-O: king to g1, rook to f1
2. refused: f1 is attacked
3. refused: king or rook has moved
6. Move history and undo: the Command pattern (and Memento)
"Dadaji, take it back!" Swapping to back to from loses the captured piece. Two patterns solve undo:
- Command pattern (episode 36): wrap each action in an object with
execute()andundo(). When aMoveexecutes, it remembers what it changed (the moved piece, the captured piece);undo()puts everything back. The move history is a stack (Dequeused withpush/pop): play pushes, undo pops the newest move first (last in, first out). - Memento pattern (episode 42): before each move, save a snapshot (a full copy of the board); undo restores the last snapshot. Simpler to get right (it can't forget a detail), but it stores a whole board per move. A Command stores only what changed.
| Command | Memento | |
|---|---|---|
| What is stored per move | Only what changed (from, to, captured piece) | A copy of the whole board |
| Undo | Reverse the change | Restore the snapshot |
| Risk | Forgetting a side effect (castling rook, promotion) | Memory use |
| Good for | Long games, replays, sending moves over a network | Small states, quick prototypes |
En passant and promotion in the same Move
- En passant (French: "in passing"): if an enemy pawn jumps two squares and lands right beside your pawn, you may capture it as if it had moved one square, landing on the square it passed, only on the very next move. It's the one capture where the captured piece is not on the
tosquare, soMovehas atakenAtsquare. The history tells us what the last move was. - Pawn promotion: a pawn that reaches the last rank is replaced by a queen, rook, bishop or knight (the player chooses).
MovehaspromoteTo; execute puts the new piece down, undo puts the pawn back.
import java.util.*;
record Piece(char color, char kind) { public String toString() { return "" + color + kind; } } // "wP" = white pawn
interface Command { void execute(Map<String, Piece> b); void undo(Map<String, Piece> b); }
class Move implements Command { // one move = one command object
final String from, to, takenAt; final Piece promoteTo; Piece moved, taken; // remembered for undo
Move(String from, String to, String takenAt, Piece promoteTo) {
this.from = from; this.to = to; this.takenAt = takenAt; this.promoteTo = promoteTo; }
static Move of(String from, String to) { return new Move(from, to, to, null); } // a normal move or capture
public void execute(Map<String, Piece> b) { moved = b.remove(from); taken = b.remove(takenAt);
b.put(to, promoteTo != null ? promoteTo : moved); } // promotion swaps the piece
public void undo(Map<String, Piece> b) { b.remove(to); b.put(from, moved); // put everything back
if (taken != null) b.put(takenAt, taken); } }
class Game { final Map<String, Piece> board = new TreeMap<>(); final Deque<Move> history = new ArrayDeque<>();
void play(Move m) { m.execute(board); history.push(m); } // push: newest on top
void undo() { history.pop().undo(board); } // pop: undo the newest first
boolean enPassantOk(String pawnAt, String target) { // right after an enemy pawn jumped 2, beside us
Move last = history.peek();
return last != null && last.moved.kind() == 'P' && Math.abs(last.to.charAt(1) - last.from.charAt(1)) == 2
&& last.to.charAt(1) == pawnAt.charAt(1) && last.to.charAt(0) == target.charAt(0); } }
public class Main { public static void main(String[] args) {
Game g = new Game(); g.board.put("e5", new Piece('w', 'P')); g.board.put("b7", new Piece('w', 'P'));
g.board.put("d7", new Piece('b', 'P')); System.out.println("start: " + g.board);
g.play(Move.of("d7", "d5")); // black pawn jumps two, lands beside e5
System.out.println("d7-d5: " + g.board + ", en passant e5xd6? " + g.enPassantOk("e5", "d6"));
g.play(new Move("e5", "d6", "d5", null)); System.out.println("e5xd6 e.p.: " + g.board); // d5 is taken
g.play(new Move("b7", "b8", "b8", new Piece('w', 'Q'))); System.out.println("b8=Q: " + g.board);
g.undo(); g.undo(); System.out.println("undo x2: " + g.board + ", history: " + g.history.size() + " move");
g.undo(); System.out.println("undo: " + g.board);
g.undo(); } }
Real output:
start: {b7=wP, d7=bP, e5=wP}
d7-d5: {b7=wP, d5=bP, e5=wP}, en passant e5xd6? true
e5xd6 e.p.: {b7=wP, d6=wP}
b8=Q: {b8=wQ, d6=wP}
undo x2: {b7=wP, d5=bP, e5=wP}, history: 1 move
undo: {b7=wP, d7=bP, e5=wP}
Exception in thread "main" java.util.NoSuchElementException
at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:361)
at java.base/java.util.ArrayDeque.pop(ArrayDeque.java:592)
at Game.undo(Main.java:15)
at Main.main(Main.java:29)
e5xd6 e.p.: the white pawn landed on d6, and the black pawn on d5 disappeared.b8=Q: the pawn became a queen.- Two undos went back to the position after
d7-d5, with1 moveleft in history; one more went back to the start. - The extra undo:
java.util.NoSuchElementExceptionfromArrayDeque.pop. The fix:if (history.isEmpty()) ... "Nothing to undo"(the mini project does this).
7. The chess clock
A chess clock is two timers in one box. Only the clock of the side to move runs; after moving you press your button, your clock stops and the other starts. If your time reaches zero, your flag falls and you lose on time. Blitz means a fast game, here 3 minutes each.
import java.util.*;
class ChessClock { // two timers; only the side to move is running
final String[] names; final long[] left; int side = 0; long startedAt;
ChessClock(String white, String black, long ms, long now) {
names = new String[] {white, black}; left = new long[] {ms, ms}; startedAt = now; }
void press(long now) { // the player finished a move and hits the button
left[side] -= now - startedAt;
if (left[side] <= 0) throw new IllegalStateException(names[side] + " lost on time"); // the flag falls
side = 1 - side; startedAt = now; } // the other clock starts
static String mmss(long ms) { return String.format("%d:%02d", ms / 60000, ms / 1000 % 60); }
public String toString() { return names[0] + " " + mmss(left[0]) + " | " + names[1] + " " + mmss(left[1]); } }
public class Main { public static void main(String[] args) {
long now = 0; // a pretend clock in milliseconds, so the demo is exact
ChessClock clock = new ChessClock("Asha", "Ravi", 3 * 60_000, now); // 3 minutes each: blitz
for (int seconds : new int[] {40, 70, 100, 115}) {
now += seconds * 1000L; clock.press(now);
System.out.println("after " + seconds + " s: " + clock); } } }
Real output:
after 40 s: Asha 2:20 | Ravi 3:00
after 70 s: Asha 2:20 | Ravi 1:50
after 100 s: Asha 0:40 | Ravi 1:50
Exception in thread "main" java.lang.IllegalStateException: Ravi lost on time
at ChessClock.press(Main.java:8)
at Main.main(Main.java:16)
- We pass the time in (
press(now)) instead of reading the real clock inside the class. The demo is exact every run, and the class is easy to unit-test. This is dependency injection of time (episode 16). - Ravi used 70 s, then needed 115 s with 110 s left:
Ravi lost on time.
8. The class diagram
Board: Map<Square, Piece> · attacked(square, byColor) · inCheck(color) · legal(from)
legal(from) = pseudo-legal moves, each tried on a copy, kept only if my king is safe
Status: ACTIVE · CHECK · CHECKMATE (no legal move + in check) · STALEMATE (no legal move, not in check)
Piece.moved → castling: king + rook unmoved, squares between empty, e/f/g not attacked
Move implements Command: execute() · undo() · from, to, takenAt (en passant), promoteTo
Game: board · history = Deque<Move> (push / pop) · play(move) · undo() · enPassantOk()
ChessClock: time left per player · press(now) · "lost on time"
9. Interview follow-ups
| Follow-up | A good answer |
|---|---|
| Threefold repetition? | The same position three times is a draw: keep a Map<positionKey, count>, where the key is a hash of the board plus whose turn and castling rights. |
| Fifty-move rule? | 50 moves by each side with no capture and no pawn move is a draw: a counter reset on captures and pawn moves. |
| Clock increment? | Add a few seconds to the player's time after every press. |
| Faster legal-move checks? | Instead of trying every move on a full copy, track attacked squares and pins and update them incrementally. |
| Online play? | The server owns the Game and validates every move; the app only sends requests, because it can't be trusted. |
| Undo castling? | One Move command moves two pieces, and its undo moves both back and restores both moved flags. |
10. Common mistakes
| Mistake | What you see (real) | Fix |
|---|---|---|
| Validating with piece rules only | BLACK e8-e1, captured the King |
Legal moves: try on a copy |
| "No moves" = checkmate | a stalemate reported as a win | Also ask inCheck |
| Forgetting a pin | a pinned piece moves off the line | The copy test catches it automatically |
No moved flag |
castling allowed after the king went and came back | refused: king or rook has moved |
| Castling through an attacked square | illegal O-O |
refused: f1 is attacked |
| Undo by swapping squares | the captured piece is lost | Command with taken saved, or Memento |
| Pop on an empty history | java.util.NoSuchElementException |
if (history.isEmpty()) |
| Reading the real clock inside the class | flaky, untestable timing | pass now in |
Mini project: a rules engine you can play
All six pieces, the full starting position, legal moves (pseudo-legal + en passant + castling both sides, filtered by "is my king safe?"), status, promotion to a queen, and a Command-based undo that also undoes castling and en passant. The demo plays the well-known four-move "scholar's mate", undoes it, castles and undoes it, and plays en passant.
import java.util.*;
enum Color { WHITE, BLACK; Color other() { return this == WHITE ? BLACK : WHITE; } }
enum Status { ACTIVE, CHECK, CHECKMATE, STALEMATE }
record Sq(int f, int r) {
static Sq of(String s) { return new Sq(s.charAt(0) - 'a', s.charAt(1) - '1'); }
boolean on() { return f >= 0 && f < 8 && r >= 0 && r < 8; }
Sq plus(int df, int dr) { return new Sq(f + df, r + dr); }
public String toString() { return "" + (char) ('a' + f) + (r + 1); }
}
abstract class Piece {
static final int[][] LINE = {{1,0},{-1,0},{0,1},{0,-1}}, DIAG = {{1,1},{1,-1},{-1,1},{-1,-1}},
BOTH = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}},
L = {{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};
final Color color;
boolean moved; // for castling
Piece(Color c) { color = c; }
abstract char letter();
abstract List<Sq> moves(Map<Sq, Piece> b, Sq from); // pseudo-legal
List<Sq> walk(Map<Sq, Piece> b, Sq from, int[][] dirs, boolean slides) {
List<Sq> out = new ArrayList<>();
for (int[] d : dirs)
for (Sq s = from.plus(d[0], d[1]); s.on(); s = s.plus(d[0], d[1])) {
Piece p = b.get(s);
if (p == null || p.color != color) out.add(s);
if (p != null || !slides) break;
}
return out;
}
public String toString() { return "" + (color == Color.WHITE ? letter() : Character.toLowerCase(letter())); }
}
class King extends Piece { King(Color c) { super(c); } char letter() { return 'K'; }
List<Sq> moves(Map<Sq, Piece> b, Sq s) { return walk(b, s, BOTH, false); } }
class Queen extends Piece { Queen(Color c) { super(c); } char letter() { return 'Q'; }
List<Sq> moves(Map<Sq, Piece> b, Sq s) { return walk(b, s, BOTH, true); } }
class Rook extends Piece { Rook(Color c) { super(c); } char letter() { return 'R'; }
List<Sq> moves(Map<Sq, Piece> b, Sq s) { return walk(b, s, LINE, true); } }
class Bishop extends Piece { Bishop(Color c) { super(c); } char letter() { return 'B'; }
List<Sq> moves(Map<Sq, Piece> b, Sq s) { return walk(b, s, DIAG, true); } }
class Knight extends Piece { Knight(Color c) { super(c); } char letter() { return 'N'; }
List<Sq> moves(Map<Sq, Piece> b, Sq s) { return walk(b, s, L, false); } }
class Pawn extends Piece { Pawn(Color c) { super(c); } char letter() { return 'P'; }
int up() { return color == Color.WHITE ? 1 : -1; }
List<Sq> moves(Map<Sq, Piece> b, Sq s) { // forward and diagonal captures (en passant is in Game)
List<Sq> out = new ArrayList<>();
Sq one = s.plus(0, up()), two = s.plus(0, 2 * up());
if (one.on() && !b.containsKey(one)) {
out.add(one);
if (s.r() == (color == Color.WHITE ? 1 : 6) && !b.containsKey(two)) out.add(two);
}
for (int df : new int[] {-1, 1}) {
Sq c = s.plus(df, up());
if (c.on() && b.get(c) != null && b.get(c).color != color) out.add(c);
}
return out;
}
}
/** One move as a Command: execute() and undo(). Handles captures, en passant, promotion and castling. */
class Move {
final Sq from, to, takenAt; // takenAt != to only for en passant
final Sq rookFrom, rookTo; // non-null only for castling
final boolean promotes;
Piece moved, taken, promotedTo;
boolean movedBefore, rookMovedBefore;
Move(Sq from, Sq to, Sq takenAt, Sq rookFrom, Sq rookTo, boolean promotes) {
this.from = from; this.to = to; this.takenAt = takenAt; this.rookFrom = rookFrom; this.rookTo = rookTo; this.promotes = promotes;
}
void execute(Map<Sq, Piece> b) {
moved = b.remove(from);
taken = b.remove(takenAt);
movedBefore = moved.moved;
promotedTo = promotes ? new Queen(moved.color) : null;
Piece put = promotes ? promotedTo : moved;
put.moved = true;
b.put(to, put);
if (rookFrom != null) { Piece rook = b.remove(rookFrom); rookMovedBefore = rook.moved; rook.moved = true; b.put(rookTo, rook); }
}
void undo(Map<Sq, Piece> b) {
b.remove(to);
moved.moved = movedBefore;
b.put(from, moved);
if (taken != null) b.put(takenAt, taken);
if (rookFrom != null) { Piece rook = b.remove(rookTo); rook.moved = rookMovedBefore; b.put(rookFrom, rook); }
}
public String toString() {
if (rookFrom != null) return rookFrom.f() == 7 ? "O-O" : "O-O-O";
String who = moved instanceof Pawn ? "" : String.valueOf(moved.letter());
return who + from + (taken == null ? "-" : "x") + to + (promotes ? "=Q" : "") + (takenAt.equals(to) ? "" : " e.p.");
}
}
class Game {
final Map<Sq, Piece> board = new HashMap<>();
final Deque<Move> history = new ArrayDeque<>();
Color toMove = Color.WHITE;
Game() {
String back = "RNBQKBNR";
for (int f = 0; f < 8; f++) {
board.put(new Sq(f, 0), make(back.charAt(f), Color.WHITE)); board.put(new Sq(f, 1), new Pawn(Color.WHITE));
board.put(new Sq(f, 7), make(back.charAt(f), Color.BLACK)); board.put(new Sq(f, 6), new Pawn(Color.BLACK));
}
}
static Piece make(char c, Color col) {
return switch (c) { case 'R' -> new Rook(col); case 'N' -> new Knight(col); case 'B' -> new Bishop(col);
case 'Q' -> new Queen(col); default -> new King(col); };
}
boolean attacked(Map<Sq, Piece> b, Sq sq, Color by) {
for (var e : b.entrySet()) if (e.getValue().color == by && e.getValue().moves(b, e.getKey()).contains(sq)) return true;
return false;
}
boolean inCheck(Map<Sq, Piece> b, Color c) {
for (var e : b.entrySet()) if (e.getValue() instanceof King && e.getValue().color == c) return attacked(b, e.getKey(), c.other());
return false;
}
/** Every candidate move for the side to move: pseudo-legal + en passant + castling. */
List<Move> candidates(Color c) {
List<Move> out = new ArrayList<>();
for (var e : new ArrayList<>(board.entrySet())) {
Sq from = e.getKey(); Piece p = e.getValue();
if (p.color != c) continue;
for (Sq to : p.moves(board, from))
out.add(new Move(from, to, to, null, null, p instanceof Pawn && (to.r() == 0 || to.r() == 7)));
if (p instanceof Pawn pawn) { // en passant: right after an enemy pawn jumped two, beside us
Move last = history.peek();
if (last != null && last.moved instanceof Pawn && Math.abs(last.to.r() - last.from.r()) == 2
&& last.to.r() == from.r() && Math.abs(last.to.f() - from.f()) == 1)
out.add(new Move(from, new Sq(last.to.f(), from.r() + pawn.up()), last.to, null, null, false));
}
if (p instanceof King && !p.moved && !inCheck(board, c)) { // castling, both sides
for (int side : new int[] {1, -1}) {
Sq rookSq = new Sq(side == 1 ? 7 : 0, from.r());
Piece rook = board.get(rookSq);
if (!(rook instanceof Rook) || rook.moved) continue;
boolean clear = true;
for (int f = from.f() + side; f != rookSq.f(); f += side) if (board.containsKey(new Sq(f, from.r()))) clear = false;
Sq pass = from.plus(side, 0), land = from.plus(2 * side, 0);
if (clear && !attacked(board, pass, c.other()) && !attacked(board, land, c.other()))
out.add(new Move(from, land, land, rookSq, pass, false));
}
}
}
return out;
}
List<Move> legal(Color c) { // try each on the real board, then undo
List<Move> ok = new ArrayList<>();
for (Move m : candidates(c)) { m.execute(board); if (!inCheck(board, c)) ok.add(m); m.undo(board); }
return ok;
}
Status status() {
boolean any = !legal(toMove).isEmpty(), check = inCheck(board, toMove);
return any ? (check ? Status.CHECK : Status.ACTIVE) : (check ? Status.CHECKMATE : Status.STALEMATE);
}
void play(String from, String to) {
Move m = legal(toMove).stream().filter(x -> x.from.equals(Sq.of(from)) && x.to.equals(Sq.of(to))).findFirst()
.orElseThrow(() -> new IllegalArgumentException("Illegal move: " + from + "-" + to + " (" + toMove + " to move)"));
m.execute(board); history.push(m); toMove = toMove.other();
}
void undo() {
if (history.isEmpty()) throw new IllegalStateException("Nothing to undo");
history.pop().undo(board); toMove = toMove.other();
}
List<Move> moves() { List<Move> l = new ArrayList<>(history); Collections.reverse(l); return l; }
}
public class Main {
static void playAll(Game g, String line) { for (String m : line.split(" ")) g.play(m.substring(0, 2), m.substring(2)); }
public static void main(String[] args) {
Game g = new Game();
System.out.println("start: " + g.legal(Color.WHITE).size() + " legal moves, " + g.status());
playAll(g, "e2e4 e7e5 f1c4 b8c6 d1h5 g8f6 h5f7"); // the "scholar's mate"
System.out.println(g.moves() + " -> black is " + g.status());
g.undo();
System.out.println("after undo: " + g.toMove + " to move, " + g.status() + ", white queen back on " +
(g.board.get(Sq.of("h5")) instanceof Queen ? "h5" : "?"));
try { g.play("e1", "g1"); } catch (IllegalArgumentException e) { System.out.println(e.getMessage()); }
Game c = new Game();
playAll(c, "e2e4 e7e5 g1f3 b8c6 f1c4 f8c5");
c.play("e1", "g1");
System.out.println("castling: " + c.moves().get(c.moves().size() - 1) + ", king on g1: " + (c.board.get(Sq.of("g1")) instanceof King)
+ ", rook on f1: " + (c.board.get(Sq.of("f1")) instanceof Rook));
c.undo();
System.out.println("undo castling: king on e1: " + (c.board.get(Sq.of("e1")) instanceof King) + ", rook on h1: "
+ (c.board.get(Sq.of("h1")) instanceof Rook) + ", can castle again: "
+ c.legal(Color.WHITE).stream().anyMatch(m -> m.rookFrom != null));
Game e = new Game();
playAll(e, "e2e4 a7a6 e4e5 d7d5 e5d6");
System.out.println("en passant: " + e.moves() + ", d5 empty: " + !e.board.containsKey(Sq.of("d5")));
for (int i = 0; i < 6; i++) e.undo();
}
}
Real output:
start: 20 legal moves, ACTIVE
[e2-e4, e7-e5, Bf1-c4, Nb8-c6, Qd1-h5, Ng8-f6, Qh5xf7] -> black is CHECKMATE
after undo: WHITE to move, ACTIVE, white queen back on h5
Illegal move: e1-g1 (WHITE to move)
castling: O-O, king on g1: true, rook on f1: true
undo castling: king on e1: true, rook on h1: true, can castle again: true
en passant: [e2-e4, a7-a6, e4-e5, d7-d5, e5xd6 e.p.], d5 empty: true
Exception in thread "main" java.lang.IllegalStateException: Nothing to undo
at Game.undo(Main.java:163)
at Main.main(Main.java:194)
legal()here executes each move on the real board and undoes it right away: the Command pattern doubles as a cheap "try it" without copying the board.- The game ends with the final extra undo throwing our own clear message,
Nothing to undo, instead of the rawNoSuchElementException.
Practice
1. Black: king on h8, pawns on g7 and h7. White: rook on a8, king on g1. Black to move. Status?
Answer
CHECKMATE (the "back-rank mate"): the rook checks along rank 8, g8 is attacked by the rook, and black's own pawns block g7 and h7. Pawn moves don't answer the check.
2. Why doesn't attacked() for castling use legal() moves of the enemy?
Answer
"Attacked" means "an enemy piece could move there by its own rule", even if that move would be illegal for the enemy (e.g. its piece is pinned). A pinned enemy rook still stops you castling through its file. So pseudo-legal moves are correct here, and they also avoid endless recursion.
3. Write undo() so it can't crash on an empty history.
Answer
void undo() {
if (history.isEmpty()) throw new IllegalStateException("Nothing to undo");
history.pop().undo(board);
}
Or return false instead of throwing, if the UI should just ignore the click.
4. Add a 2-second increment to ChessClock.
Answer
In press, after the time check: left[side] += 2000; before switching sides. The increment is added to the player who just moved.
5. When is en passant not allowed even though a pawn just jumped two squares?
Answer
When it didn't land right beside your pawn (same rank, adjacent file), or if you wait one move: the right lasts only for the very next move. And, like every move, it must not leave your king in check.
6. Sketch a Memento-based undo for the mini project.
Answer
Deque<Map<Sq, Piece>> snapshots = new ArrayDeque<>();
void play(...) { snapshots.push(new HashMap<>(board)); /* then make the move */ }
void undo() { board.clear(); board.putAll(snapshots.pop()); }
Pieces with state (moved) must be copied too, or the moved flags must be part of the snapshot.
Quick quiz
Black to move. The black king is alone on a8. White: king on c7, queen on b6. The black king is not attacked, but every square it could go to is. Status? (a) CHECKMATE (b) STALEMATE (c) CHECK (d) ACTIVE
Answer
(b) STALEMATE, a draw. No legal move and not in check. Checkmate also needs the king to be attacked.
Interview questions
- Pseudo-legal vs legal moves? Pseudo-legal follow the piece's rule; legal also don't leave your own king in check.
- How do you detect check? Find your king's square and ask whether any enemy piece's pseudo-legal moves include it.
- How do you validate a move simply and correctly? Make it on a copy (or make and undo it), then check whether your king is attacked.
- Checkmate vs stalemate? Both: no legal moves. Checkmate: in check (a loss). Stalemate: not in check (a draw).
- What are castling's conditions? King and that rook never moved, squares between empty, king not in check and not passing through or landing on an attacked square.
- How do you model en passant? The last move from the history (an enemy pawn's two-square jump beside you) plus a
takenAtsquare on the move. - How do you model promotion? A
promoteTopiece on the move: execute swaps the pawn for it, undo swaps back. - How do you implement undo? Command: each move stores what it changed and reverses it; history is a stack. Or Memento: a snapshot per move.
- Command or Memento for chess? Command: small per move, also a replayable record; Memento is fine for small boards and prototypes.
- How would you test a chess clock? Inject the current time (
press(now)) so tests can use exact, fake times.
Glossary
| Term | Meaning, with an example |
|---|---|
| Move validation | Deciding if a move is allowed: right piece, right turn, legal |
| Pseudo-legal move | Follows the piece's own rule, ignores check (episode 85) |
| Legal move | A pseudo-legal move that leaves your own king safe |
| Attacked square | A square an enemy piece could move to |
| Check | Your king's square is attacked |
| Check detection | Finding out if a king is in check: inCheck(color) |
| Pin / pinned piece | A piece that can't leave a line without exposing its king: the rook on e2 |
| Checkmate | No legal move and in check: that side loses |
| Stalemate | No legal move and not in check: a draw |
| Draw | A game that ends with no winner |
| Game status | The game's state now: ACTIVE, CHECK, CHECKMATE, STALEMATE |
| Castling | King moves 2 squares toward a rook, which jumps over it: O-O, O-O-O |
| Castling short / long | Kingside (O-O, king to g1) / queenside (O-O-O, king to c1) |
moved flag |
A boolean remembering a piece has moved, for castling |
| En passant | Capturing a pawn that just jumped 2 squares beside yours, as if it moved 1 |
| takenAt | The square of the captured piece; differs from to only for en passant |
| Pawn promotion | A pawn on the last rank becomes a queen, rook, bishop or knight |
| Move history | The list of moves played; here a stack (Deque) |
| Stack | Last in, first out: push on top, pop from the top |
| Deque / ArrayDeque | Java's double-ended queue; push, pop, peek use it as a stack |
| Undo | Reversing the last move |
| Command pattern | Wrap an action in an object with execute() and undo() (episode 36) |
| Memento pattern | Save a snapshot of an object's state to restore later (episode 42) |
| Snapshot | A full copy of the state at one moment |
| Chess clock | Two linked timers; only the side to move's clock runs |
| Flag fall / lose on time | A player's time reaches zero and they lose |
| Blitz | A fast time control, e.g. 3 minutes each |
| Increment | Seconds added to a player's clock after each move |
| Threefold repetition | The same position three times: a draw |
| Fifty-move rule | 50 moves each without a capture or pawn move: a draw |
| enum with methods | Color.other(): enums can have behaviour |
instanceof |
Java's type check: e.getValue() instanceof King |
| NoSuchElementException | Thrown by pop() on an empty ArrayDeque |
| IllegalStateException | "Not allowed now": Ravi lost on time, Nothing to undo |
| Dependency injection (of time) | Passing the current time in, instead of reading the clock inside |
Summary
- Move validation with piece rules alone let a king be captured; pseudo-legal moves ignore the king.
- Check detection asks "is my king's square attacked?", and a legal move is one tried on a copy that leaves the king safe.
- Game status comes from the legal moves: check, checkmate (a loss) or stalemate (a draw).
- Castling needs a
movedflag and attacked-square checks; en passant needs the move history and atakenAtsquare; pawn promotion needspromoteTo. - Undo with Command stores what each move changed and reverses it; Memento stores snapshots instead.
- A chess clock times each side, and passing the time in keeps it testable.
- Next episode: mock machine-coding round 1: Stack Overflow.