CSE Roadmap

Common tier · about 5 hours · 6 parts

Part 4 of 6 · 6 min read

The code

Pieces, board, and the legal-move test.

A square, with a helper to read "e2":

record Pos(int r, int c) {
    Pos { if (r < 0 || r > 7 || c < 0 || c > 7) throw new IllegalArgumentException("off board"); }
    static Pos of(String s) { return new Pos(s.charAt(1) - '1', s.charAt(0) - 'a'); }
}

Row 0 is rank 1, where white starts, and column 0 is file a.

The piece base class and three examples. A sliding piece must also check that the path is clear.

abstract class Piece {
    final Color color;
    Piece(Color c) { color = c; }
    abstract boolean canReach(Board b, Pos from, Pos to);   // geometry and blocking only
}

class Rook extends Piece {
    boolean canReach(Board b, Pos f, Pos t) {
        return (f.r() == t.r() || f.c() == t.c()) && b.pathClear(f, t);
    }
}
class Knight extends Piece {
    boolean canReach(Board b, Pos f, Pos t) {
        int dr = Math.abs(f.r() - t.r()), dc = Math.abs(f.c() - t.c());
        return dr * dc == 2;                      // 1x2 or 2x1; jumps, so no path check
    }
}
class Pawn extends Piece {
    boolean canReach(Board b, Pos f, Pos t) {
        int dir = color == Color.WHITE ? 1 : -1, home = color == Color.WHITE ? 1 : 6;
        int dr = t.r() - f.r(), dc = Math.abs(t.c() - f.c());
        if (dc == 0 && b.at(t) == null) {                         // straight, onto an empty square
            if (dr == dir) return true;
            return dr == 2 * dir && f.r() == home && b.at(new Pos(f.r() + dir, f.c())) == null;
        }
        return dc == 1 && dr == dir && b.at(t) != null && b.at(t).color != color;   // capture
    }
}

The pawn is the odd one: it moves straight and captures diagonally, and may move two squares from its home row. Bishop and queen use the same pathClear helper as the rook. The king moves one step in any direction. The board's helper walks the squares between two points and reports whether any holds a piece.

The game's tests for a move, in order:

void move(String f, String t) throws IllegalMoveException {
    if (status == Status.CHECKMATE || status == Status.STALEMATE) throw new IllegalMoveException("game over");
    Pos from = Pos.of(f), to = Pos.of(t);
    if (board.at(from) == null)           throw new IllegalMoveException("no piece on " + from);
    if (board.at(from).color != turn)     throw new IllegalMoveException("not your piece");
    if (!pseudoLegal(from, to))           throw new IllegalMoveException("that piece cannot move like that");
    if (!leavesKingSafe(from, to))        throw new IllegalMoveException("your king would be in check");
    Piece p = board.at(from);
    board.put(to, p); board.put(from, null);
    if (p instanceof Pawn && (to.r() == 0 || to.r() == 7)) board.put(to, new Queen(p.color));
    turn = turn.other();
    boolean check = inCheck(turn), moves = hasLegalMove();
    status = !moves ? (check ? Status.CHECKMATE : Status.STALEMATE)
                    : check ? Status.CHECK : Status.PLAYING;
}

A move is pseudo-legal when the piece can reach the square and the target is not the player's own piece. It is legal when it is pseudo-legal and also leaves the king safe. The king-safety test plays the move, asks whether the mover's king is attacked, and puts the board back.

private boolean leavesKingSafe(Pos from, Pos to) {
    Piece moved = board.at(from), captured = board.at(to);
    board.put(to, moved); board.put(from, null);
    boolean safe = !inCheck(turn);
    board.put(from, moved); board.put(to, captured);      // always restored
    return safe;
}

inCheck finds the king and asks every enemy piece whether it can reach that square. hasLegalMove tries every piece of the side to move against every square, and stops at the first legal move. At most 64 by 64 squares are tried, so the cost per move is small. Checkmate and stalemate then fall out of one question, "does the player to move have any legal move".

A run (the moves written as from-to):

Sequence Result
e2-e4, e7-e5, f1-c4, b8-c6, d1-h5, g8-f6 status PLAYING, white to move
h5-f7 CHECKMATE (the scholar's mate), and the next move says "game over"
New game: e2-e5 "that piece cannot move like that" (a pawn cannot jump three)
a1-a3 "that piece cannot move like that" (a pawn blocks the rook)
e7-e5 on white's turn "not your piece"
e3-e4 with no piece on e3 "no piece on e3"
g1-f3 ok (a knight jumps over its own pawns)
e2-e4, d7-d5, f1-b5 status CHECK, since the bishop attacks the king through the empty d7
Then a7-a6 "your king would be in check" (it does not answer the check)
Then c7-c6 ok (blocks the check)
The well-known ten-move stalemate game, 19 half-moves long STALEMATE, with black to move
e2-e4, e7-e5, d1-h5, b8-c6, h5-f7 CHECK only, because the king can take the unprotected queen

Check yourself: 1. Why does the knight need no path check? 2. What does leavesKingSafe do with the board afterward? 3. Which single question decides checkmate or stalemate?