Design a Chess Game | androidinterview.com

Every piece answers one question and nothing else, which squares can I reach from here on this board. Everything that is about the whole position, whose turn it is, whether a move exposes your own king, whether the game is over, lives in the game. Make that cut first and chess turns into a small design. Miss it and you end up with a King class that needs the board's entire attack map to answer a question about one square.

The other half is that a move is a value carrying the piece that moved and the piece that was taken. That second field is what makes undo a pop, and undo is what makes legality cheap, because testing a move is nothing more than playing it and taking it back.

What this really tests

Whether you can stop a large rule set from collecting in one class. Chess has more rules than any other board game people ask about, so the interviewer is watching where each rule lands. The trap is a Board with a validateMove method that grows a branch per piece type, and then grows a second branch per special rule on top of that.

What to clarify first

Chess is the one problem where scope is most of the conversation, so ask before you draw anything.

Are castling, en passant and promotion in scope. Ask this first. They are three of the four hardest things in the problem, and they are usually a follow up rather than the main task.
Two humans at one board, or is a bot in scope. A bot needs a generator that hands back every legal move, which is a stronger requirement than validating one move at a time. Build the generator either way, because check detection needs it too.
Is undo in scope. Almost always yes here, and it changes what a Move has to hold.
Do draws count. Repetition, the fifty move rule and insufficient material all need history rather than the current position, so say whether you are doing them.
Is there a clock. Usually out, and saying so removes a class.
How does a move arrive, two squares or algebraic notation. Two squares. Parsing notation is a separate exercise and it is not the design.

Say the out of scope list out loud as well. Notation, persistence, network play and the clock.

Where the movement rule lives, and why it is not a strategy

This is the decision the interviewer is actually probing, and the honest answer is the opposite of the one tic tac toe wants.

In tic tac toe the win rule belongs in a strategy object, because the rule varies independently of the board. Three in a row today, four in a row on a bigger grid tomorrow, and the class holding the squares does not change when it does.

Chess is the other case. A rook is not a piece that happens to be configured with straight line movement, a rook is straight line movement. There is no rook anywhere that moves like a knight, so there is nothing to swap at runtime. A MovementStrategy interface would end up with exactly one implementation per piece type, plus a piece class whose only job is to hold it, which is a second hierarchy running parallel to the first.

Say the test out loud, because it is what separates the two answers. Strategy earns its place when the behaviour varies independently of the thing holding it. Polymorphism on the type earns its place when the behaviour is the type. Chess is the second case, so the movement rule goes on the piece.

One ray walker, and six tiny classes

Once movement is on the piece, the subclasses are small, and one helper on the base class is why.

Walking outward along a direction until you hit the edge or a piece is the same loop for a rook, a bishop and a queen. An empty square is a move, an enemy piece is a move and then a stop, a friendly piece is a stop with no move. Write that once and the three sliding classes contribute a table of directions and one line each. The queen's table is the rook's table plus the bishop's, which is the whole of what a queen is.

The king takes that same walk with the loop removed, and so does the knight. That is worth pointing at. The knight, the piece everybody treats as the special case, is the plainest one in the code, because jumping is exactly what you get when you stop asking about the squares in between.

The pawn is the only piece with a real method body, and that is honest rather than a failure. It moves one way and captures another, so neither helper fits it. Everything about it that differs by side, the direction it walks and the row it starts on, comes off the Color enum, so there is not a single branch on white or black inside Pawn.

Legality is apply, test, revert

Ask a piece for its squares and you get pseudo legal moves, every square it could land on if the king did not exist. A rook pinned against its own king will cheerfully offer a move that loses the game on the spot.

Turning that into a legal list is one rule and one trick. The rule is that a move is illegal if your own king is attacked after it. The trick is that you do not need a copy of the board to find out. Play the move on the real board, ask whether your king is attacked, then put the board back. Apply, test, revert.

That works because the Move already carries the captured piece. Reverting is two assignments, put the mover back where it came from and put the captured piece back where it was standing. No board copy, no snapshot, no clone method on anything. Those same two assignments are also the undo you were asked for, which is the tell that the Move was modelled right.

Attack detection comes off the same generator. You are in check when any enemy piece lists your king's square among its targets. There is a piece of free correctness here worth naming. A pawn's push is only a move onto an empty square, so a pawn standing directly in front of a king does not check it, and nothing in the code had to say so.

Check, checkmate and stalemate are one question

Do not write three algorithms. Write one and read all three answers off it.

Generate every legal move for the side to move. If the list is not empty the game is running, and it is check when that side's king is attacked. If the list is empty it is checkmate when the king is attacked and stalemate when it is not. Checkmate and stalemate are the same sentence with one word changed, and that is the sentence to say out loud, because most people describe them as two unrelated things.

Say the cost too, because it sounds expensive. Around twenty pieces, each offering a handful of squares, each tested by scanning at most sixty four squares for attackers. That is a few thousand array reads for a move that a human spent thirty seconds choosing. If they push, the honest answer is that a real engine keeps incremental attack tables and bitboards, and you would write neither in an interview, because the readable version is already fast by four orders of magnitude.

The classes

Eight types, and six of them are the piece hierarchy.

Color is white and black plus the only two numbers that differ between them, the direction a pawn walks and the row its pawns start on. Every per colour number in the game lives here, which is why nothing else has to branch on the side.
Position is a row and a column together. Two loose ints are two chances to pass them the wrong way round, and every piece in the game adds an offset to a square, so that addition is one method here rather than six copies of it.
Board is storage and geometry. It says what stands on a square, it puts something there, and it can find a king. It has no move validation at all, which is the same call as the tic tac toe board having no win check. The instant one rule lands on the board, every rule wants to live there.
Piece holds a colour and one abstract method that returns reachable squares. It also owns the ray walker and the single step walker that its subclasses share, which is why they are short.
King, Queen, Rook, Bishop, Knight and Pawn are the six. Five of them are a direction table and a one line override. Only the pawn has a body.
Move holds from, to, the piece that moved and the piece that was taken. Everything needed to play it forwards and everything needed to play it backwards.
GameStatus is in progress, check, checkmate or stalemate. One value rather than a pile of booleans, because booleans let you write down a game that is checkmate and still running.
Game owns the board, the turn, the history and the status. It is the only class that knows whose move it is, and it holds all three of the whole position rules.

The dependencies run one way. The game asks pieces for squares, pieces read the board, and the board knows about nothing above it.

Movement is the only thing that varies by piece type, so it is the only thing the hierarchy carries, and the accented edge is the one that turns undo into two assignments.

One move, walked through

Black's king is on e8 with a black knight beside it on d8. White has a rook on d1 and the rest of the d file is empty. White plays the rook to d8 and takes the knight.

The game checks that the status is not already over, then checks that d1 holds a white piece, because it is white's turn. Both checks are here and nowhere else in the codebase.
The game generates white's legal moves. It asks each white piece for its squares, and the rook walks up the d file through the empty squares. On d8 it meets the black knight, an enemy, so d8 is a move and the walk stops there.
Each square becomes a Move carrying the rook, the two squares and the black knight as the captured piece. The knight is recorded now, while it is still standing there, not later when it has already gone.
The game tests that Move. It clears d1, puts the rook on d8, and asks whether the white king is attacked. It is not, so the move is kept, and the board is put back exactly as it was.
The requested move is found in that list, so it is applied for real and pushed onto the history stack.
The turn flips to black and the status is recomputed for black. Black's legal moves are generated, the list is not empty, and black's king on e8 is attacked by the rook along the eighth rank. The status is check.
Look at what the generator threw away for black. The king stepping sideways to f8 is the move a careless implementation allows, and it is filtered out here for a reason worth saying slowly. The test runs after the king has already left e8, so the rook's walk now runs through the empty e8 and reaches f8. Compute attacked squares before lifting the king and you allow that move. Apply, test, revert gets it right without knowing the case exists.

Undo is step five run backwards. Pop the move, put the rook back on d1, put the black knight back on d8, flip the turn and recompute the status. The game is never replayed from the opening, because the move carried its own inverse.

Castling, en passant and promotion

Scope these out at the start, then say in two sentences each how the design absorbs them. That is a much stronger answer than implementing one of them badly with five minutes left.

Promotion. A pawn reaching the last rank is still a Move, it just puts a different piece on the destination square instead of the one that set off. Give Move a promotedTo field, have apply swap the new piece in and revert swap the pawn back, and nothing else in the design moves.
En passant. It is the only move in chess that depends on the previous move, so a pawn cannot generate it from the board alone, and the game passes the last move down to the generator. The captured pawn goes on the Move exactly as any other capture does, even though it is not standing on the destination square, and that field is why undo still works unchanged.
Castling. It moves two pieces and it depends on whether the king and the rook have ever moved, so add a moved flag or read it off the history, and let the Move carry the rook's two squares as well. Apply and revert then touch four squares instead of two, and the rule that the king may not pass through an attacked square is three calls to the apply, test, revert filter you already have.

Notice what the three have in common. They are all still Moves, they just touch more than two squares or look at more than the current position. The piece hierarchy, the generator and the status rule are untouched by all three, and being able to say that is the reason to scope them out rather than to skip past them.

Patterns actually used

Two, and both are carrying weight.

Polymorphism on the piece. Call it template method if a name is wanted, because the base class owns the walk and each subclass supplies the direction table. The payoff is that a new piece is one class and no edits anywhere else.
Command, for the move. The Move is a command that holds its own inverse, which is why undo is a pop and why legality testing needs no board copy. It is the rare pattern that pays for itself twice in one design, and saying that is worth more than listing five patterns.

Four to leave out, and say why you are leaving them out.

A factory for pieces. Six constructors taking a colour is not a creational problem. It earns its place the moment you load a saved position from a string, and it is a minute's work then.
State, one class per game state. Four statuses with no per state behaviour is an enum. An ATM needs the state pattern because each state accepts different operations. Here every status accepts the same single operation, make a move, or refuses it.
A MovementStrategy interface. One implementation per piece type is a hierarchy wearing a strategy costume, for the reasons above.
Observer for the display. Worth one sentence about a networked game and nothing at all in a console one.

The implementation

Both trees carry the same design. The piece knows movement, the board knows squares, and the game knows everything that is about the position.

The Kotlin is written as Kotlin rather than translated. Piece is a sealed class, so a when over the six types is exhaustive and a seventh piece breaks the compile everywhere that has to care. The direction tables are lists of pairs with a plus operator on Position, the board uses get and set operators so reading a square looks like indexing an array, and the status is a sealed interface where Checkmate carries the winner, so a finished game with nobody winning cannot be written down. The opening position is one loop over a list of constructor references.

Java

com.androidinterview.chess.game.Game.java

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());
    }
}

com.androidinterview.chess.model.Board.java

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();
    }
}

com.androidinterview.chess.model.Color.java

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;
    }
}

com.androidinterview.chess.model.GameStatus.java

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;
    }
}

com.androidinterview.chess.model.Move.java

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;
    }
}

com.androidinterview.chess.model.Position.java

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);
    }
}

com.androidinterview.chess.piece.Bishop.java

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);
    }
}

com.androidinterview.chess.piece.King.java

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);
    }
}

com.androidinterview.chess.piece.Knight.java

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);
    }
}

com.androidinterview.chess.piece.Pawn.java

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;
    }
}

com.androidinterview.chess.piece.Piece.java

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));
    }
}

com.androidinterview.chess.piece.Queen.java

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);
    }
}

com.androidinterview.chess.piece.Rook.java

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);
    }
}

Kotlin

com.androidinterview.chess.game.Game.kt

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
    }
}

com.androidinterview.chess.model.Board.kt

package com.androidinterview.chess.model

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

// 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.
enum class Color(val pawnDirection: Int, val pawnStartRow: Int) {
    WHITE(1, 1),
    BLACK(-1, 6);

    val opponent: Color get() = if (this == WHITE) BLACK else WHITE
}

// A step, in rows and columns. Every direction table in the game is a list of
// these, so the offset arithmetic is one operator and not six copies.
typealias Step = Pair<Int, Int>

// Row zero is white's back rank, so a positive pawn direction walks up the
// board and the algebraic name falls out of the two numbers.
data class Position(val row: Int, val col: Int) {
    operator fun plus(step: Step) = Position(row + step.first, col + step.second)
    override fun toString() = "${'a' + col}${row + 1}"
}

// Everything needed to play a move forwards and everything needed to play it
// backwards. The captured piece is the field that turns undo into a pop, and
// it is null on a quiet move.
data class Move(val from: Position, val to: Position, val piece: Piece, val captured: Piece? = null) {
    override fun toString() = "$piece $from${if (captured == null) "-" else "x"}$to"
}

// Storage and geometry, nothing else. It says what stands on a square and 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.
class Board {

    private val squares = Array(SIZE) { arrayOfNulls<Piece>(SIZE) }

    operator fun contains(at: Position) = at.row in 0 until SIZE && at.col in 0 until SIZE

    operator fun get(at: Position): Piece? = squares[at.row][at.col]

    // Setting null clears the square, which is how undo puts a piece back.
    operator fun set(at: Position, piece: Piece?) {
        squares[at.row][at.col] = piece
    }

    fun squaresHolding(color: Color) = ALL_SQUARES.filter { this[it]?.color == color }

    // Scanned rather than cached. A cached square is a second source of truth
    // that every move and every undo has to keep in step.
    fun kingSquare(color: Color) = squaresHolding(color).firstOrNull { this[it] is King }

    override fun toString() = (SIZE - 1 downTo 0).joinToString("\n") { row ->
        (0 until SIZE).joinToString(" ") { col -> squares[row][col]?.toString() ?: "." }
    }

    companion object {
        const val SIZE = 8

        val ALL_SQUARES = (0 until SIZE).flatMap { row -> (0 until SIZE).map { Position(row, it) } }

        // The opening position. Both colours use the same back rank order,
        // because the layout is a mirror and not two arrangements. Holding
        // constructors as function values is why this is one loop.
        private val BACK_RANK: List<(Color) -> Piece> =
            listOf(::Rook, ::Knight, ::Bishop, ::Queen, ::King, ::Bishop, ::Knight, ::Rook)

        fun standard() = Board().apply {
            for (color in Color.entries) {
                val homeRow = if (color == Color.WHITE) 0 else SIZE - 1
                BACK_RANK.forEachIndexed { col, make ->
                    this[Position(homeRow, col)] = make(color)
                    this[Position(color.pawnStartRow, col)] = Pawn(color)
                }
            }
        }
    }
}

com.androidinterview.chess.piece.Piece.kt

package com.androidinterview.chess.piece

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

private val STRAIGHT: List<Step> = listOf(1 to 0, -1 to 0, 0 to 1, 0 to -1)
private val DIAGONAL: List<Step> = listOf(1 to 1, 1 to -1, -1 to 1, -1 to -1)

// The queen slides along these and the king takes one step along them.
private val ALL_EIGHT: List<Step> = STRAIGHT + DIAGONAL

private val LEAPS: List<Step> =
    listOf(2 to 1, 2 to -1, -2 to 1, -2 to -1, 1 to 2, 1 to -2, -1 to 2, -1 to -2)

// 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.
//
// Sealed rather than open, so a when over the six types is exhaustive and a
// seventh piece is a compile error everywhere that has to care.
sealed class Piece(val color: Color, private val letter: Char) {

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

    // The ray walker, and the reason rook, bishop and queen are one line 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 fun slide(board: Board, from: Position, directions: List<Step>): List<Position> =
        directions.flatMap { step ->
            buildList {
                var at = from + step
                while (at in board) {
                    val occupant = board[at]
                    if (occupant != null) {
                        if (occupant.color != color) add(at)
                        break
                    }
                    add(at)
                    at += step
                }
            }
        }

    // The same walk with the loop taken out, all a king or a knight needs.
    protected fun step(board: Board, from: Position, offsets: List<Step>): List<Position> =
        offsets.map { from + it }.filter { it in board && board[it]?.color != color }

    // Upper case for white, lower case for black.
    override fun toString() =
        (if (color == Color.WHITE) letter.uppercaseChar() else letter.lowercaseChar()).toString()
}

class Rook(color: Color) : Piece(color, 'R') {
    override fun targets(board: Board, from: Position) = slide(board, from, STRAIGHT)
}

class Bishop(color: Color) : Piece(color, 'B') {
    override fun targets(board: Board, from: Position) = slide(board, from, DIAGONAL)
}

class Queen(color: Color) : Piece(color, 'Q') {
    override fun targets(board: Board, from: Position) = slide(board, from, ALL_EIGHT)
}

// Not stepping into an attacked square, and castling, are rules about the whole
// position, so the game owns them and the king does not.
class King(color: Color) : Piece(color, 'K') {
    override fun targets(board: Board, from: Position) = step(board, from, ALL_EIGHT)
}

// 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.
class Knight(color: Color) : Piece(color, 'N') {
    override fun targets(board: Board, from: Position) = step(board, from, LEAPS)
}

// The awkward one, and the only piece that needed a 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.
class Pawn(color: Color) : Piece(color, 'P') {

    override fun targets(board: Board, from: Position): List<Position> {
        val forward = color.pawnDirection
        val ahead = from + (forward to 0)

        // 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.
        val pushes = buildList {
            if (ahead in board && board[ahead] == null) {
                add(ahead)
                val twoAhead = ahead + (forward to 0)
                if (from.row == color.pawnStartRow && board[twoAhead] == null) 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.
        val captures = listOf(forward to -1, forward to 1)
            .map { from + it }
            .filter { it in board && board[it]?.color == color.opponent }

        return pushes + captures
    }
}

Concurrency and edge cases

A game at one board is turn based and single threaded, so do not invent locks for it. If they ask about a server hosting many games, it is the same three lines as every other game problem. Serialise each game behind one lock so moves land in order, carry a turn token so a move from the player who is not to move is rejected rather than raced, and give every move a sequence number so a client retry after a dropped connection is idempotent rather than played twice.

The edge cases that decide whether the design is right.

A pinned piece. It offers its moves happily and the filter removes them. There is no pin detection code anywhere, and that absence is the point.
A king stepping into check. Same filter, same place. The King class never learns which squares are attacked.
Two kings next to each other. Falls out for free, because each king lists the other's neighbouring squares as targets, so the move that would stand them side by side is filtered.
A pawn directly in front of a king. Not check, because a push needs an empty destination square. Nothing had to encode that.
Stalemate read as checkmate. The most common bug in this problem. Both are an empty move list, and only the check test tells them apart.
Undo at the start of the game. Empty history, so it fails loudly rather than quietly flipping the turn.
Undo after checkmate. Legal, because the status is recomputed from the board rather than stored as a flag somebody has to remember to unwind.
A board with no king on it. Only reachable in a test position, and the check test answers no rather than throwing, so a partial board is still usable for exercising one piece.
Repetition and the fifty move rule. Out of scope here, and worth naming as out of scope. Both need position history rather than the current board, so both are a counter and a set of position hashes on the game, and neither touches anything else.