Chess

Chess is a two-player strategy board game played on a chessboard, which is a checkered gameboard with 64 squares arranged in an 8×8 grid. There are a few versions of game types that people play all over the world. In this design problem, we are going to focus on designing a two-player online chess game.

Features

We’ll focus on the following set of requirements while designing the game of chess:

The system should support two online players to play a game of chess.
All rules of international chess will be followed.
Each player will be randomly assigned a side, black or white.
Both players will play their moves one after the other. The white side plays the first move.
Players can’t cancel or roll back their moves.
The system should maintain a log of all moves by both players.
Each side will start with 8 pawns, 2 rooks, 2 bishops, 2 knights, 1 queen, and 1 king.
The game can finish either in a checkmate from one side, forfeit or stalemate (a draw), or resignation.

Rough Solution (LLD-Machine Coding)

public enum GameStatus {
    ACTIVE, BLACK_WIN, WHITE_WIN, FORFEIT, STALEMATE, RESIGNATION
}

public enum AccountStatus {
    ACTIVE, CLOSED, CANCELED, BLACKLISTED, NONE
}

// Observer Pattern for Game Events (check, checkmate, etc.)
interface Observer {
    void update(String message);
}

class Player implements Observer {
    private Person person;
    private boolean whiteSide = false;

    public Player(Person person, boolean whiteSide) {
        this.person = person;
        this.whiteSide = whiteSide;
    }

    public boolean isWhiteSide() {
        return this.whiteSide;
    }

    @Override
    public void update(String message) {
        System.out.println("Notification for Player: " + person.getName() + ": " + message);
    }
}

// Factory Method Pattern for creating different pieces
abstract class PieceFactory {
    public abstract Piece createPiece(boolean white);
}

class KingFactory extends PieceFactory {
    @Override
    public Piece createPiece(boolean white) {
        return new King(white);
    }
}

class KnightFactory extends PieceFactory {
    @Override
    public Piece createPiece(boolean white) {
        return new Knight(white);
    }
}

// Strategy Pattern for movement strategies
interface MoveStrategy {
    boolean canMove(Board board, Box start, Box end);
}

class KingMoveStrategy implements MoveStrategy {
    @Override
    public boolean canMove(Board board, Box start, Box end) {
        int x = Math.abs(start.getX() - end.getX());
        int y = Math.abs(start.getY() - end.getY());
        return x + y == 1;
    }
}

class KnightMoveStrategy implements MoveStrategy {
    @Override
    public boolean canMove(Board board, Box start, Box end) {
        int x = Math.abs(start.getX() - end.getX());
        int y = Math.abs(start.getY() - end.getY());
        return x * y == 2;
    }
}

// Command Pattern for moves
interface Command {
    void execute();
    void undo();
}

class MoveCommand implements Command {
    private Move move;
    private Board board;

    public MoveCommand(Move move, Board board) {
        this.move = move;
        this.board = board;
    }

    @Override
    public void execute() {
        Piece piece = move.getStart().getPiece();
        move.getEnd().setPiece(piece);
        move.getStart().setPiece(null);
    }

    @Override
    public void undo() {
        move.getStart().setPiece(move.getEnd().getPiece());
        move.getEnd().setPiece(move.getPieceKilled());
    }
}

// Template Method Pattern for handling common movement logic
abstract class Piece {
    private boolean killed = false;
    private boolean white = false;
    private MoveStrategy moveStrategy;

    public Piece(boolean white, MoveStrategy moveStrategy) {
        this.white = white;
        this.moveStrategy = moveStrategy;
    }

    public boolean isWhite() {
        return this.white;
    }

    public boolean isKilled() {
        return this.killed;
    }

    public void setKilled(boolean killed) {
        this.killed = killed;
    }

    // Template method to handle piece movement
    public final boolean move(Board board, Box start, Box end) {
        if (!moveStrategy.canMove(board, start, end)) {
            return false;
        }
        if (end.getPiece() != null && end.getPiece().isWhite() == this.isWhite()) {
            return false;
        }
        return true;
    }
}

class King extends Piece {
    private boolean castlingDone = false;

    public King(boolean white) {
        super(white, new KingMoveStrategy());
    }

    public boolean isCastlingDone() {
        return castlingDone;
    }

    public void setCastlingDone(boolean castlingDone) {
        this.castlingDone = castlingDone;
    }
}

class Knight extends Piece {
    public Knight(boolean white) {
        super(white, new KnightMoveStrategy());
    }
}

// Board class to manage the board
public class Board {
    private Box[][] boxes;

    public Board() {
        this.resetBoard();
    }

    public Box getBox(int x, int y) throws Exception {
        if (x < 0 || x > 7 || y < 0 || y > 7) {
            throw new Exception("Index out of bounds");
        }
        return boxes[x][y];
    }

    public void resetBoard() {
        // initialize board with pieces (skipping code for brevity)
    }
}

// Game class to manage the game state
public class Game {
    private Player[] players;
    private Board board;
    private Player currentTurn;
    private GameStatus status;
    private List<Move> movesPlayed;
    private SystemNotifier notifier;

    public Game(Player p1, Player p2, SystemNotifier notifier) {
        players = new Player[2];
        players[0] = p1;
        players[1] = p2;
        this.notifier = notifier;
        board = new Board();
        movesPlayed = new ArrayList<>();
        currentTurn = p1.isWhiteSide() ? p1 : p2;
    }

    public boolean playerMove(Player player, int startX, int startY, int endX, int endY) {
        try {
            Box startBox = board.getBox(startX, startY);
            Box endBox = board.getBox(endX, endY);
            Piece piece = startBox.getPiece();

            if (piece == null || player != currentTurn || piece.isWhite() != player.isWhiteSide()) {
                return false;
            }

            if (piece.move(board, startBox, endBox)) {
                Move move = new Move(player, startBox, endBox);
                MoveCommand moveCommand = new MoveCommand(move, board);
                moveCommand.execute();
                movesPlayed.add(move);
                notifier.notifyObservers("Move made by " + (player.isWhiteSide() ? "White" : "Black"));

                // Switch turn
                currentTurn = (currentTurn == players[0]) ? players[1] : players[0];
                return true;
            }
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        return false;
    }

    public boolean isGameOver() {
        return status != GameStatus.ACTIVE;
    }

    public void setGameStatus(GameStatus status) {
        this.status = status;
    }
}

// Supporting classes remain unchanged
// Example: Box, Address, Person, Move, etc.

// System Notifier class (Observer pattern)
class SystemNotifier {
    private List<Observer> observers = new ArrayList<>();

    public void addObserver(Observer observer) {
        observers.add(observer);
    }

    public void removeObserver(Observer observer) {
        observers.remove(observer);
    }

    public void notifyObservers(String message) {
        for (Observer observer : observers) {
            observer.update(message);
        }
    }
}

// Main class to run the game
public class Main {
    public static void main(String[] args) {
        // Initialize game with players
        Player whitePlayer = new Player(new Person("John Doe"), true);
        Player blackPlayer = new Player(new Person("Jane Doe"), false);

        // Add players to observer list
        SystemNotifier notifier = new SystemNotifier();
        notifier.addObserver(whitePlayer);
        notifier.addObserver(blackPlayer);

        // Start game
        Game game = new Game(whitePlayer, blackPlayer, notifier);
        game.playerMove(whitePlayer, 1, 1, 2, 1);  // Sample move
    }
}

🔴 Key Problems & Drawbacks

⚠️ 1️⃣ Concurrency Issues in Online Multiplayer Mode

❌ Problem:

Multiple users playing the game simultaneously can lead to race conditions when accessing the game state (board updates, move history).
No locking mechanism to prevent two players from making a move at the same time.

✅ Solution: Will be covered in our premium course.

⚠️ 2️⃣ Inefficient Move Validation (O(N) Complexity)

❌ Problem:

Each piece’s movement is checked inefficiently.
Currently, move validation iterates over the board each time, making it slow for large move sets.

✅ Solution: Will be covered in our premium course.

⚠️ 3️⃣ Inefficient Game Log Storage

❌ Problem:

Storing move history in a list (ArrayList<Move>) is inefficient for searching and undo operations.
Searching for a previous move is O(N) instead of O(log N).

✅ Solution: Will be covered in our premium course.

⚠️ 4️⃣ No Stalemate & Checkmate Detection (Edge Cases Ignored)

❌ Problem:

The current design does not check for checkmate/stalemate properly.
It only validates individual moves, not overall game state.

✅ Solution: Will be covered in our premium course.

⚠️ 5️⃣ No Timeout for Player Moves (Game Can Stall)

❌ Problem:

If a player doesn’t move, the game hangs indefinitely.

✅ Solution: Will be covered in our premium course.

Design (LLD) Chess - Machine Coding Interview