Building a Chess Game

Hello! Welcome to another Low-Level Design case study.

In our last lesson, we designed a hotel reservation system. The core challenge was managing shared inventory (rooms) over date ranges, which led us to focus on database schemas, transactions, and concurrency control mechanisms like pessimistic and optimistic locking.

Today, we're shifting from a data-centric problem to a behavior-centric one: designing a chess game. Your learning outcome for this lesson is to design a chess game, modeling piece movements, game rules, and state.

This classic LLD problem will challenge us to model a complex set of rules and behaviors using Object-Oriented principles. Instead of worrying about concurrent transactions, our focus will be on state management, encapsulation, and applying design patterns to create a flexible and maintainable structure.

Step 1: Understanding the Requirements

As with any design problem, we start by clarifying the scope. A chess game has well-defined rules, but it's crucial to state our assumptions explicitly.

Based on the video and standard chess rules, let's summarize the core requirements for our design:

• Game Board: A standard 8x8 board.
• Players: Two players, White and Black. White always moves first.
• Pieces: Each player starts with 16 pieces (1 King, 1 Queen, 2 Rooks, 2 Bishops, 2 Knights, 8 Pawns).
• Turns: Players alternate turns.
• Move Validation: The system must validate every move based on the rules for the specific piece.
• Game State: The system must track the current state of the game, including whose turn it is and game-ending conditions.
• Winning/Drawing: The system must detect check, checkmate, and stalemate conditions.

For a 45-minute LLD interview, implementing every special move (like en passant) might be out of scope, but our design should be extensible enough to accommodate them.

Step 2: Identifying Core Entities and Behaviors

With the requirements defined, we can start modeling the system. What are the "nouns" in our problem description?

• Game: The main orchestrator.
• Player: The actors who make moves.
• Board: The playing area.
• Cell (or Square, Box): An individual square on the board.
• Piece: The items that are moved.
• Move: An action taken by a player.

A key part of LLD is not just identifying entities, but also their behaviors and how they differ.

This brainstorming leads us to the central design challenge: How do we model the different movement rules for each piece in a clean, extensible way?

Step 3: The Strategy Pattern for Piece Movement

A naive approach would be to have a giant if/else or switch statement in a move method, checking the piece type and applying the correct logic. This violates the Open/Closed Principle; adding a new piece (e.g., for a fantasy chess variant) would require modifying this core logic.

A much better solution is the Strategy Pattern. This pattern allows us to define a family of algorithms, encapsulate each one, and make them interchangeable.

Our "algorithms" are the movement rules.

1. Define a MovementStrategy interface: This interface will declare a method like getPossibleMoves().
2. Create concrete strategy classes: We'll implement this interface for each piece: KingMovementStrategy, QueenMovementStrategy, PawnMovementStrategy, etc. Each class will contain the specific logic for that piece's movement.
3. Compose the strategy in the Piece class: The Piece class will hold a reference to a MovementStrategy object. When a piece needs to move, it delegates the call to its strategy object.

This design is flexible, maintainable, and adheres to SOLID principles.

Here's the core idea in code:

The Strategy Interface:

public interface MovementStrategy {
    List<Position> getPossibleMoves(Position currentPosition, Board board);
}

A Concrete Strategy:

public class KnightMovementStrategy implements MovementStrategy {
    @Override
    public List<Position> getPossibleMoves(Position currentPosition, Board board) {
        // ... logic for L-shaped moves ...
    }
}

The Piece Class (Context):

public abstract class Piece {
    protected final PieceColor color;
    private MovementStrategy movementStrategy; // Composition

    public Piece(PieceColor color, MovementStrategy strategy) {
        this.color = color;
        this.movementStrategy = strategy; // Strategy is injected
    }

    // Delegate the call to the strategy object
    public List<Position> getPossibleMoves(Position currentPosition, Board board) {
        return movementStrategy.getPossibleMoves(currentPosition, board);
    }
}

Step 4: Assembling the Full Class Structure

Now that we've solved the core movement problem, we can build out the full class structure. We'll use other design patterns to improve our design.

• Board as a Singleton: In any single game, there is only one board. Making the Board class a singleton ensures that there's a single, globally accessible instance.
• PieceFactory: To avoid littering our board setup code with new King(...), new Pawn(...), we can use a Factory to centralize piece creation. PieceFactory.createPiece(PieceType.ROOK, PieceColor.WHITE) is much cleaner.

The following UML diagram gives a comprehensive view of how these classes and patterns fit together.

Let's watch a final clip that puts these pieces together and discusses the overall game flow.

Step 5: Managing the Game Flow and Rules

The Game class is the engine of our system. It's responsible for:

1. Initialization: Creating the players and using a BoardFactory to set up the board with pieces in their starting positions.
2. Turn Management: Keeping track of the currentPlayer. After a valid move, it switches the turn.
3. Executing Moves: This is the most complex piece of logic. A makeMove(player, from, to) method would orchestrate the following checks:
   • Is it player's turn?
   • Is there a piece at the from position, and does it belong to player?
   • Is the move to to in the piece's list of getPossibleMoves()?
   • Crucially: Does this move leave the player's own King in check? This is a non-trivial check. A common way to implement this is to:
     a. Create a temporary, hypothetical copy of the board.
     b. Make the move on the temporary board.
     c. Check if the current player's king is under attack on this new board.
     d. If it is, the move is illegal.
4. Updating State: If a move is legal, the Game class updates the Board state, captures any pieces, logs the Move, and switches the currentPlayer.
5. Checking for Game End: After each move, the Game class must check if the new board state results in a checkmate or stalemate, updating the GameStatus accordingly.

The Move itself can be encapsulated in a class, which aligns with the Command Pattern. A Move object would store the startPosition, endPosition, pieceMoved, and pieceCaptured. This is extremely useful for keeping a game log or implementing an "undo" feature.

Conclusion

We have successfully designed a chess game, focusing on creating a flexible and extensible object-oriented model. This exercise highlighted a different set of challenges compared to our previous booking system designs.

Key Takeaways:

• Behavior over Data: The primary challenge was modeling complex and varied behaviors (piece movements), not managing concurrent data access.
• Strategy Pattern is Key: For components that share an action (move) but implement it differently, the Strategy pattern is the ideal solution. It promotes clean, decoupled, and extensible code.
• Other Core Patterns:
  • Singleton: Useful for ensuring a single instance of a global object like the Board.
  • Factory: Decouples object creation from client code, making initialization cleaner.
  • Command: Encapsulating actions like Move into objects allows for logging, queuing, and undo functionality.
• Model Complex Rules Incrementally: The logic for move validation, especially checking for self-check, is complex. In an interview, break it down logically: first, check piece-specific rules (via Strategy), then check board rules (like blocked paths), and finally, check game-state rules (like not putting your own king in check).

In our next lesson, we will continue exploring state-driven design by tackling another classic LLD problem: designing a vending machine. This will reinforce the importance of managing state transitions and object interactions in a clean and predictable way.