Design a Chess Game

package com.androidinterview.chess.game;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.GameStatus;
import com.androidinterview.chess.model.Move;
import com.androidinterview.chess.model.Position;
import com.androidinterview.chess.piece.Piece;

// The orchestrator, and the only class that knows whose turn it is. Every rule
// about the whole position rather than about one piece is here, and there are
// three. Move your own piece, the piece must offer the square, and the move
// must not leave your own king attacked.
public final class Game {

    private final Board board;
    private final Deque<Move> history = new ArrayDeque<>();

    private Color turn = Color.WHITE;
    private GameStatus status;

    public Game() {
        this(Board.standard());
    }

    public Game(Board board) {
        this.board = board;
        this.status = statusFor(turn);
    }

    public Board board() {
        return board;
    }

    public Color turn() {
        return turn;
    }

    public GameStatus status() {
        return status;
    }

    // On checkmate the side to move is the mated side, so the winner is
    // whoever just played. No separate winner field to keep in step.
    public Color winner() {
        return status == GameStatus.CHECKMATE ? turn.opponent() : null;
    }

    public List<Move> legalMoves() {
        return legalMoves(turn);
    }

    // Generate, then filter. The filter is apply, test, revert. Play the move
    // on the real board, ask whether the king is attacked, put the board back.
    // No copy is made, because the move carries the piece that was taken.
    private List<Move> legalMoves(Color color) {
        List<Move> legal = new ArrayList<>();
        for (Position from : board.squaresHolding(color)) {
            Piece piece = board.at(from);
            for (Position to : piece.targets(board, from)) {
                Move move = new Move(from, to, piece, board.at(to));
                apply(move);
                boolean safe = !isInCheck(color);
                revert(move);
                if (safe) {
                    legal.add(move);
                }
            }
        }
        return legal;
    }

    // Validation happens here and nowhere else.
    public Move makeMove(Position from, Position to) {
        if (status.isOver()) {
            throw new IllegalStateException("The game already ended as " + status);
        }
        Piece piece = board.at(from);
        if (piece == null || piece.color() != turn) {
            throw new IllegalArgumentException(from + " does not hold a " + turn + " piece");
        }
        Move move = legalMoves().stream()
            .filter(candidate -> candidate.from().equals(from) && candidate.to().equals(to))
            .findFirst()
            .orElseThrow(() -> new IllegalArgumentException(from + " to " + to + " is not legal for " + turn));

        apply(move);
        history.push(move);
        turn = turn.opponent();
        status = statusFor(turn);
        return move;
    }

    // A pop and a revert. The move holds its own inverse, so taking one back
    // never replays the game from the start.
    public Move undo() {
        Move move = history.poll();
        if (move == null) {
            throw new IllegalStateException("There is nothing to undo");
        }
        revert(move);
        turn = turn.opponent();
        status = statusFor(turn);
        return move;
    }

    // Attack detection, not move legality. Every enemy piece is asked for its
    // squares and the king's square is looked for among them. A push needs an
    // empty square, so a pawn in front of a king does not check it.
    public boolean isInCheck(Color color) {
        Position king = board.kingSquare(color);
        if (king == null) {
            return false;
        }
        for (Position from : board.squaresHolding(color.opponent())) {
            if (board.at(from).targets(board, from).contains(king)) {
                return true;
            }
        }
        return false;
    }

    // Checkmate and stalemate are the same sentence with one word changed. No
    // legal move and attacked is mate, no legal move and safe is a draw. That
    // costs a few thousand board reads, free at human speed.
    private GameStatus statusFor(Color color) {
        boolean check = isInCheck(color);
        if (!legalMoves(color).isEmpty()) {
            return check ? GameStatus.CHECK : GameStatus.IN_PROGRESS;
        }
        return check ? GameStatus.CHECKMATE : GameStatus.STALEMATE;
    }

    private void apply(Move move) {
        board.set(move.from(), null);
        board.set(move.to(), move.piece());
    }

    private void revert(Move move) {
        board.set(move.from(), move.piece());
        board.set(move.to(), move.captured());
    }
}

package com.androidinterview.chess.game;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.GameStatus;
import com.androidinterview.chess.model.Move;
import com.androidinterview.chess.model.Position;
import com.androidinterview.chess.piece.Piece;

public final class Game {

    private final Board board;
    private final Deque<Move> history = new ArrayDeque<>();

    private Color turn = Color.WHITE;
    private GameStatus status;

    public Game() {
        this(Board.standard());
    }

    public Game(Board board) {
        this.board = board;
        this.status = statusFor(turn);
    }

    public Board board() {
        return board;
    }

    public Color turn() {
        return turn;
    }

    public GameStatus status() {
        return status;
    }

    public Color winner() {
        return status == GameStatus.CHECKMATE ? turn.opponent() : null;
    }

    public List<Move> legalMoves() {
        return legalMoves(turn);
    }

    private List<Move> legalMoves(Color color) {
        List<Move> legal = new ArrayList<>();
        for (Position from : board.squaresHolding(color)) {
            Piece piece = board.at(from);
            for (Position to : piece.targets(board, from)) {
                Move move = new Move(from, to, piece, board.at(to));
                apply(move);
                boolean safe = !isInCheck(color);
                revert(move);
                if (safe) {
                    legal.add(move);
                }
            }
        }
        return legal;
    }

    public Move makeMove(Position from, Position to) {
        if (status.isOver()) {
            throw new IllegalStateException("The game already ended as " + status);
        }
        Piece piece = board.at(from);
        if (piece == null || piece.color() != turn) {
            throw new IllegalArgumentException(from + " does not hold a " + turn + " piece");
        }
        Move move = legalMoves().stream()
            .filter(candidate -> candidate.from().equals(from) && candidate.to().equals(to))
            .findFirst()
            .orElseThrow(() -> new IllegalArgumentException(from + " to " + to + " is not legal for " + turn));

        apply(move);
        history.push(move);
        turn = turn.opponent();
        status = statusFor(turn);
        return move;
    }

    public Move undo() {
        Move move = history.poll();
        if (move == null) {
            throw new IllegalStateException("There is nothing to undo");
        }
        revert(move);
        turn = turn.opponent();
        status = statusFor(turn);
        return move;
    }

    public boolean isInCheck(Color color) {
        Position king = board.kingSquare(color);
        if (king == null) {
            return false;
        }
        for (Position from : board.squaresHolding(color.opponent())) {
            if (board.at(from).targets(board, from).contains(king)) {
                return true;
            }
        }
        return false;
    }

    private GameStatus statusFor(Color color) {
        boolean check = isInCheck(color);
        if (!legalMoves(color).isEmpty()) {
            return check ? GameStatus.CHECK : GameStatus.IN_PROGRESS;
        }
        return check ? GameStatus.CHECKMATE : GameStatus.STALEMATE;
    }

    private void apply(Move move) {
        board.set(move.from(), null);
        board.set(move.to(), move.piece());
    }

    private void revert(Move move) {
        board.set(move.from(), move.piece());
        board.set(move.to(), move.captured());
    }
}

package com.androidinterview.chess.model;

import java.util.ArrayList;
import java.util.List;

import com.androidinterview.chess.piece.Bishop;
import com.androidinterview.chess.piece.King;
import com.androidinterview.chess.piece.Knight;
import com.androidinterview.chess.piece.Pawn;
import com.androidinterview.chess.piece.Piece;
import com.androidinterview.chess.piece.Queen;
import com.androidinterview.chess.piece.Rook;

// Storage and geometry, nothing else. It says what is standing on a square and
// it puts something there. It cannot tell you whether a move is legal, whose
// turn it is, or whether anybody is in check. The instant one rule lands here,
// every rule wants to live here too.
public final class Board {

    public static final int SIZE = 8;

    private final Piece[][] squares = new Piece[SIZE][SIZE];

    // The opening position. Both colours use the same back rank order,
    // because the layout is a mirror and not two arrangements.
    public static Board standard() {
        Board board = new Board();
        for (Color color : Color.values()) {
            int homeRow = color == Color.WHITE ? 0 : SIZE - 1;
            Piece[] backRank = {
                new Rook(color), new Knight(color), new Bishop(color), new Queen(color),
                new King(color), new Bishop(color), new Knight(color), new Rook(color),
            };
            for (int col = 0; col < SIZE; col++) {
                board.set(new Position(homeRow, col), backRank[col]);
                board.set(new Position(color.pawnStartRow(), col), new Pawn(color));
            }
        }
        return board;
    }

    public boolean contains(Position at) {
        return at.row() >= 0 && at.row() < SIZE && at.col() >= 0 && at.col() < SIZE;
    }

    public Piece at(Position at) {
        return squares[at.row()][at.col()];
    }

    // Passing null clears the square, which is how undo puts a piece back.
    public void set(Position at, Piece piece) {
        squares[at.row()][at.col()] = piece;
    }

    public List<Position> squaresHolding(Color color) {
        List<Position> found = new ArrayList<>();
        for (int row = 0; row < SIZE; row++) {
            for (int col = 0; col < SIZE; col++) {
                Piece piece = squares[row][col];
                if (piece != null && piece.color() == color) {
                    found.add(new Position(row, col));
                }
            }
        }
        return found;
    }

    // Scanned rather than cached. A cached square is a second source of truth
    // that every move and every undo has to keep in step.
    public Position kingSquare(Color color) {
        for (Position at : squaresHolding(color)) {
            if (at(at) instanceof King) {
                return at;
            }
        }
        return null;
    }

    @Override
    public String toString() {
        StringBuilder out = new StringBuilder();
        for (int row = SIZE - 1; row >= 0; row--) {
            for (int col = 0; col < SIZE; col++) {
                Piece piece = squares[row][col];
                out.append(piece == null ? "." : piece.toString()).append(' ');
            }
            out.append('\n');
        }
        return out.toString();
    }
}

package com.androidinterview.chess.model;

import java.util.ArrayList;
import java.util.List;

import com.androidinterview.chess.piece.Bishop;
import com.androidinterview.chess.piece.King;
import com.androidinterview.chess.piece.Knight;
import com.androidinterview.chess.piece.Pawn;
import com.androidinterview.chess.piece.Piece;
import com.androidinterview.chess.piece.Queen;
import com.androidinterview.chess.piece.Rook;

public final class Board {

    public static final int SIZE = 8;

    private final Piece[][] squares = new Piece[SIZE][SIZE];

    public static Board standard() {
        Board board = new Board();
        for (Color color : Color.values()) {
            int homeRow = color == Color.WHITE ? 0 : SIZE - 1;
            Piece[] backRank = {
                new Rook(color), new Knight(color), new Bishop(color), new Queen(color),
                new King(color), new Bishop(color), new Knight(color), new Rook(color),
            };
            for (int col = 0; col < SIZE; col++) {
                board.set(new Position(homeRow, col), backRank[col]);
                board.set(new Position(color.pawnStartRow(), col), new Pawn(color));
            }
        }
        return board;
    }

    public boolean contains(Position at) {
        return at.row() >= 0 && at.row() < SIZE && at.col() >= 0 && at.col() < SIZE;
    }

    public Piece at(Position at) {
        return squares[at.row()][at.col()];
    }

    public void set(Position at, Piece piece) {
        squares[at.row()][at.col()] = piece;
    }

    public List<Position> squaresHolding(Color color) {
        List<Position> found = new ArrayList<>();
        for (int row = 0; row < SIZE; row++) {
            for (int col = 0; col < SIZE; col++) {
                Piece piece = squares[row][col];
                if (piece != null && piece.color() == color) {
                    found.add(new Position(row, col));
                }
            }
        }
        return found;
    }

    public Position kingSquare(Color color) {
        for (Position at : squaresHolding(color)) {
            if (at(at) instanceof King) {
                return at;
            }
        }
        return null;
    }

    @Override
    public String toString() {
        StringBuilder out = new StringBuilder();
        for (int row = SIZE - 1; row >= 0; row--) {
            for (int col = 0; col < SIZE; col++) {
                Piece piece = squares[row][col];
                out.append(piece == null ? "." : piece.toString()).append(' ');
            }
            out.append('\n');
        }
        return out.toString();
    }
}

package com.androidinterview.chess.model;

// The only place a per colour number lives. Five of the six pieces move the
// same way whichever side owns them, so colour is just a tag. The pawn walks
// one way only, so its direction and its start row hang off the colour rather
// than off if statements inside Pawn.
public enum Color {

    WHITE(1, 1),
    BLACK(-1, 6);

    private final int pawnDirection;
    private final int pawnStartRow;

    Color(int pawnDirection, int pawnStartRow) {
        this.pawnDirection = pawnDirection;
        this.pawnStartRow = pawnStartRow;
    }

    // Plus one for white, minus one for black, in board rows.
    public int pawnDirection() {
        return pawnDirection;
    }

    public int pawnStartRow() {
        return pawnStartRow;
    }

    public Color opponent() {
        return this == WHITE ? BLACK : WHITE;
    }
}

package com.androidinterview.chess.model;

public enum Color {

    WHITE(1, 1),
    BLACK(-1, 6);

    private final int pawnDirection;
    private final int pawnStartRow;

    Color(int pawnDirection, int pawnStartRow) {
        this.pawnDirection = pawnDirection;
        this.pawnStartRow = pawnStartRow;
    }

    public int pawnDirection() {
        return pawnDirection;
    }

    public int pawnStartRow() {
        return pawnStartRow;
    }

    public Color opponent() {
        return this == WHITE ? BLACK : WHITE;
    }
}

package com.androidinterview.chess.model;

// One enum rather than a handful of booleans, which would let you write down a
// game that is checkmate and still in progress. All four values are derived
// after every move from one question, does the side to move have a legal move
// at all, so nothing here can drift out of step with the board.
public enum GameStatus {

    IN_PROGRESS,
    // Attacked with somewhere to go, attacked with nowhere to go, and safe
    // with nowhere to go, which is a draw.
    CHECK,
    CHECKMATE,
    STALEMATE;

    public boolean isOver() {
        return this == CHECKMATE || this == STALEMATE;
    }
}

package com.androidinterview.chess.model;

public enum GameStatus {

    IN_PROGRESS,
    CHECK,
    CHECKMATE,
    STALEMATE;

    public boolean isOver() {
        return this == CHECKMATE || this == STALEMATE;
    }
}

package com.androidinterview.chess.model;

import com.androidinterview.chess.piece.Piece;

// Everything needed to play a move forwards and everything needed to play it
// backwards, in one value. The captured piece is the field that makes undo a
// pop rather than a replay from the opening position. It is null on a quiet
// move, and that means exactly one thing, this move took nothing.
public record Move(Position from, Position to, Piece piece, Piece captured) {

    public boolean isCapture() {
        return captured != null;
    }

    @Override
    public String toString() {
        return piece + " " + from + (isCapture() ? "x" : "-") + to;
    }
}

package com.androidinterview.chess.model;

import com.androidinterview.chess.piece.Piece;

public record Move(Position from, Position to, Piece piece, Piece captured) {

    public boolean isCapture() {
        return captured != null;
    }

    @Override
    public String toString() {
        return piece + " " + from + (isCapture() ? "x" : "-") + to;
    }
}

package com.androidinterview.chess.model;

// A square. Row zero is white's back rank, so a positive pawn direction walks
// up the board. Two loose ints would be two chances to pass them the wrong way
// round, and every piece adds an offset to a square, so that lives here.
public record Position(int row, int col) {

    public Position plus(int rowStep, int colStep) {
        return new Position(row + rowStep, col + colStep);
    }

    @Override
    public String toString() {
        return String.valueOf((char) ('a' + col)) + (row + 1);
    }
}

package com.androidinterview.chess.model;

public record Position(int row, int col) {

    public Position plus(int rowStep, int colStep) {
        return new Position(row + rowStep, col + colStep);
    }

    @Override
    public String toString() {
        return String.valueOf((char) ('a' + col)) + (row + 1);
    }
}

package com.androidinterview.chess.piece;

import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

// The rook with a different table.
public final class Bishop extends Piece {

    public Bishop(Color color) {
        super(color, 'B');
    }

    @Override
    public List<Position> targets(Board board, Position from) {
        return slide(board, from, DIAGONAL);
    }
}

package com.androidinterview.chess.piece;

import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

public final class Bishop extends Piece {

    public Bishop(Color color) {
        super(color, 'B');
    }

    @Override
    public List<Position> targets(Board board, Position from) {
        return slide(board, from, DIAGONAL);
    }
}

package com.androidinterview.chess.piece;

import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

// The queen's directions walked exactly once. Not stepping into an attacked
// square, and castling, are rules about the whole position, so the game owns
// them and the king does not.
public final class King extends Piece {

    public King(Color color) {
        super(color, 'K');
    }

    @Override
    public List<Position> targets(Board board, Position from) {
        return step(board, from, ALL_EIGHT);
    }
}

package com.androidinterview.chess.piece;

import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

public final class King extends Piece {

    public King(Color color) {
        super(color, 'K');
    }

    @Override
    public List<Position> targets(Board board, Position from) {
        return step(board, from, ALL_EIGHT);
    }
}

package com.androidinterview.chess.piece;

import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

// The only piece that jumps, and here that costs nothing. Jumping is the walk
// with no loop, so a knight never asks what it passes over.
public final class Knight extends Piece {

    private static final int[][] LEAPS = {
        { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 },
        { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 },
    };

    public Knight(Color color) {
        super(color, 'N');
    }

    @Override
    public List<Position> targets(Board board, Position from) {
        return step(board, from, LEAPS);
    }
}

package com.androidinterview.chess.piece;

import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

public final class Knight extends Piece {

    private static final int[][] LEAPS = {
        { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 },
        { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 },
    };

    public Knight(Color color) {
        super(color, 'N');
    }

    @Override
    public List<Position> targets(Board board, Position from) {
        return step(board, from, LEAPS);
    }
}

package com.androidinterview.chess.piece;

import java.util.ArrayList;
import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

// The awkward one, and the only piece that needed its own method body. It
// moves one way and captures another, so neither helper fits. Every per colour
// number comes off the colour, so there is no branch on white or black here.
public final class Pawn extends Piece {

    public Pawn(Color color) {
        super(color, 'P');
    }

    @Override
    public List<Position> targets(Board board, Position from) {
        List<Position> found = new ArrayList<>();
        int forward = color().pawnDirection();

        // A push is only a move onto an empty square and is never a capture,
        // which is why a pawn in front of a king does not check it.
        Position ahead = from.plus(forward, 0);
        if (board.contains(ahead) && board.at(ahead) == null) {
            found.add(ahead);
            Position twoAhead = ahead.plus(forward, 0);
            if (from.row() == color().pawnStartRow() && board.at(twoAhead) == null) {
                found.add(twoAhead);
            }
        }

        // A diagonal is only a move when an enemy is standing there. En
        // passant is the exception, and it is a follow up.
        for (int side : new int[] { -1, 1 }) {
            Position diagonal = from.plus(forward, side);
            if (board.contains(diagonal)) {
                Piece occupant = board.at(diagonal);
                if (occupant != null && occupant.color() != color()) {
                    found.add(diagonal);
                }
            }
        }
        return found;
    }
}

package com.androidinterview.chess.piece;

import java.util.ArrayList;
import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

public final class Pawn extends Piece {

    public Pawn(Color color) {
        super(color, 'P');
    }

    @Override
    public List<Position> targets(Board board, Position from) {
        List<Position> found = new ArrayList<>();
        int forward = color().pawnDirection();

        Position ahead = from.plus(forward, 0);
        if (board.contains(ahead) && board.at(ahead) == null) {
            found.add(ahead);
            Position twoAhead = ahead.plus(forward, 0);
            if (from.row() == color().pawnStartRow() && board.at(twoAhead) == null) {
                found.add(twoAhead);
            }
        }

        for (int side : new int[] { -1, 1 }) {
            Position diagonal = from.plus(forward, side);
            if (board.contains(diagonal)) {
                Piece occupant = board.at(diagonal);
                if (occupant != null && occupant.color() != color()) {
                    found.add(diagonal);
                }
            }
        }
        return found;
    }
}

package com.androidinterview.chess.piece;

import java.util.ArrayList;
import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

// A piece answers one question, which squares can I reach from here on this
// board. It does not know whose turn it is and it does not know whether the
// move would expose its own king. The rule lives on the piece rather than in a
// strategy because a piece type IS its movement rule, so there is nothing to
// swap at runtime.
public abstract class Piece {

    protected static final int[][] STRAIGHT = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    protected static final int[][] DIAGONAL = { { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };
    // The queen slides along these and the king takes one step along them.
    protected static final int[][] ALL_EIGHT = {
        { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 },
        { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 },
    };

    private final Color color;
    private final char letter;

    protected Piece(Color color, char letter) {
        this.color = color;
        this.letter = letter;
    }

    public Color color() {
        return color;
    }

    // Pseudo legal, every square this piece could land on if the king did not
    // exist. The game narrows that down to the legal set.
    public abstract List<Position> targets(Board board, Position from);

    // The ray walker, and the reason rook, bishop and queen are five lines
    // each. An empty square is a move, an enemy is a move and then a stop, a
    // friend is a stop with no move.
    protected final List<Position> slide(Board board, Position from, int[][] directions) {
        List<Position> found = new ArrayList<>();
        for (int[] step : directions) {
            Position at = from.plus(step[0], step[1]);
            while (board.contains(at)) {
                Piece occupant = board.at(at);
                if (occupant != null) {
                    if (occupant.color != color) {
                        found.add(at);
                    }
                    break;
                }
                found.add(at);
                at = at.plus(step[0], step[1]);
            }
        }
        return found;
    }

    // The same walk with the loop taken out, all a king or a knight needs.
    protected final List<Position> step(Board board, Position from, int[][] offsets) {
        List<Position> found = new ArrayList<>();
        for (int[] offset : offsets) {
            Position at = from.plus(offset[0], offset[1]);
            if (board.contains(at)) {
                Piece occupant = board.at(at);
                if (occupant == null || occupant.color != color) {
                    found.add(at);
                }
            }
        }
        return found;
    }

    // Upper case for white, lower case for black.
    @Override
    public String toString() {
        return String.valueOf(color == Color.WHITE ? Character.toUpperCase(letter) : Character.toLowerCase(letter));
    }
}

package com.androidinterview.chess.piece;

import java.util.ArrayList;
import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

public abstract class Piece {

    protected static final int[][] STRAIGHT = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    protected static final int[][] DIAGONAL = { { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };
    protected static final int[][] ALL_EIGHT = {
        { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 },
        { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 },
    };

    private final Color color;
    private final char letter;

    protected Piece(Color color, char letter) {
        this.color = color;
        this.letter = letter;
    }

    public Color color() {
        return color;
    }

    public abstract List<Position> targets(Board board, Position from);

    protected final List<Position> slide(Board board, Position from, int[][] directions) {
        List<Position> found = new ArrayList<>();
        for (int[] step : directions) {
            Position at = from.plus(step[0], step[1]);
            while (board.contains(at)) {
                Piece occupant = board.at(at);
                if (occupant != null) {
                    if (occupant.color != color) {
                        found.add(at);
                    }
                    break;
                }
                found.add(at);
                at = at.plus(step[0], step[1]);
            }
        }
        return found;
    }

    protected final List<Position> step(Board board, Position from, int[][] offsets) {
        List<Position> found = new ArrayList<>();
        for (int[] offset : offsets) {
            Position at = from.plus(offset[0], offset[1]);
            if (board.contains(at)) {
                Piece occupant = board.at(at);
                if (occupant == null || occupant.color != color) {
                    found.add(at);
                }
            }
        }
        return found;
    }

    @Override
    public String toString() {
        return String.valueOf(color == Color.WHITE ? Character.toUpperCase(letter) : Character.toLowerCase(letter));
    }
}

package com.androidinterview.chess.piece;

import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

// A rook and a bishop at once, which here is one table rather than multiple
// inheritance.
public final class Queen extends Piece {

    public Queen(Color color) {
        super(color, 'Q');
    }

    @Override
    public List<Position> targets(Board board, Position from) {
        return slide(board, from, ALL_EIGHT);
    }
}

package com.androidinterview.chess.piece;

import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

public final class Queen extends Piece {

    public Queen(Color color) {
        super(color, 'Q');
    }

    @Override
    public List<Position> targets(Board board, Position from) {
        return slide(board, from, ALL_EIGHT);
    }
}

package com.androidinterview.chess.piece;

import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

// Slides along ranks and files. The walking is in the base class, so this
// piece contributes a direction table.
public final class Rook extends Piece {

    public Rook(Color color) {
        super(color, 'R');
    }

    @Override
    public List<Position> targets(Board board, Position from) {
        return slide(board, from, STRAIGHT);
    }
}

package com.androidinterview.chess.piece;

import java.util.List;

import com.androidinterview.chess.model.Board;
import com.androidinterview.chess.model.Color;
import com.androidinterview.chess.model.Position;

public final class Rook extends Piece {

    public Rook(Color color) {
        super(color, 'R');
    }

    @Override
    public List<Position> targets(Board board, Position from) {
        return slide(board, from, STRAIGHT);
    }
}

package com.androidinterview.chess.game

import com.androidinterview.chess.model.Board
import com.androidinterview.chess.model.Color
import com.androidinterview.chess.model.Move
import com.androidinterview.chess.model.Position

// A sealed hierarchy instead of an enum plus a nullable winner. Checkmate
// carries the side that won and Check carries the side that is attacked, so a
// finished game with no winner cannot be written down and a when over the
// status is exhaustive.
sealed interface GameStatus {
    data object InProgress : GameStatus
    data class Check(val color: Color) : GameStatus
    data class Checkmate(val winner: Color) : GameStatus
    data object Stalemate : GameStatus

    val isOver: Boolean get() = this is Checkmate || this is Stalemate
}

// The orchestrator, and the only class that knows whose turn it is. Every rule
// about the whole position rather than about one piece is here, and there are
// three. Move your own piece, the piece must offer the square, and the move
// must not leave your own king attacked.
class Game(val board: Board = Board.standard()) {

    private val history = ArrayDeque<Move>()

    var turn: Color = Color.WHITE
        private set

    var status: GameStatus = statusFor(turn)
        private set

    // Generate, then filter. The filter is apply, test, revert. Play the move
    // on the real board, ask whether the king is attacked, put the board back.
    // No copy is made, because the move carries the piece that was taken.
    fun legalMoves(color: Color = turn): List<Move> =
        board.squaresHolding(color)
            .flatMap { from ->
                val piece = board[from]!!
                piece.targets(board, from).map { to -> Move(from, to, piece, board[to]) }
            }
            .filter { move ->
                apply(move)
                val safe = !isInCheck(color)
                revert(move)
                safe
            }

    // Validation happens here and nowhere else.
    fun move(from: Position, to: Position): Move {
        check(!status.isOver) { "The game already ended as $status" }
        val piece = board[from]
        require(piece != null && piece.color == turn) { "$from does not hold a $turn piece" }
        val move = requireNotNull(legalMoves().find { it.from == from && it.to == to }) {
            "$from to $to is not legal for $turn"
        }
        apply(move)
        history.addLast(move)
        advance()
        return move
    }

    // A pop and a revert. The move holds its own inverse, so taking one back
    // never replays the game from the start.
    fun undo(): Move {
        val move = checkNotNull(history.removeLastOrNull()) { "There is nothing to undo" }
        revert(move)
        advance()
        return move
    }

    // Attack detection, not move legality. Every enemy piece is asked for its
    // squares and the king's square is looked for among them. A push needs an
    // empty square, so a pawn in front of a king does not check it.
    fun isInCheck(color: Color): Boolean {
        val king = board.kingSquare(color) ?: return false
        return board.squaresHolding(color.opponent).any { king in board[it]!!.targets(board, it) }
    }

    private fun advance() {
        turn = turn.opponent
        status = statusFor(turn)
    }

    // Checkmate and stalemate are the same sentence with one word changed. No
    // legal move and attacked is mate, no legal move and safe is a draw. That
    // costs a few thousand board reads, free at human speed.
    private fun statusFor(color: Color): GameStatus = when {
        legalMoves(color).isNotEmpty() ->
            if (isInCheck(color)) GameStatus.Check(color) else GameStatus.InProgress
        isInCheck(color) -> GameStatus.Checkmate(color.opponent)
        else -> GameStatus.Stalemate
    }

    private fun apply(move: Move) {
        board[move.from] = null
        board[move.to] = move.piece
    }

    private fun revert(move: Move) {
        board[move.from] = move.piece
        board[move.to] = move.captured
    }
}