Skip to content

Chess - Low Level System Design#

Creating a low-level design (LLD) for a chess game involves defining the core classes, their attributes, and the interactions required to simulate a chess game. We’ll start with the basic object-oriented design, focusing on key entities and their relationships.

JavaScript Implementation#

1. Class Diagram Overview#

We’ll break down the main classes needed to design a chess game:

  1. ChessGame: Manages the overall game state.
  2. Board: Represents the 8x8 chessboard.
  3. Piece (and subclasses): Defines the properties and behavior of each piece (Pawn, Rook, Knight, Bishop, Queen, King).
  4. Player: Represents each player, tracking their moves.
  5. Move: Encapsulates the details of each move.
  6. Square: Represents each cell on the board.

2. Class Definitions and Responsibilities#

Let's define each of these classes with key attributes and methods.

ChessGame#

  • Attributes:
  • board: Board: The board on which the game is played.
  • players: List[Player]: List of two players.
  • current_turn: Player: Keeps track of which player's turn it is.
  • move_history: List[Move]: List of all moves made in the game.
  • is_game_over: bool: Status of the game.

  • winner: Optional[Player]: The winning player, if any.

  • Methods:

  • start_game(): Initializes the game, setting up the board and players.
  • make_move(move: Move) -> bool: Attempts to execute a move.
  • is_checkmate() -> bool: Checks if the current player is in checkmate.
  • is_stalemate() -> bool: Checks if the game is in stalemate.
  • switch_turn(): Switches the turn to the other player.

Board#

  • Attributes:
  • squares: List[List[Square]]: 8x8 grid of squares.

  • pieces: List[Piece]: List of all pieces on the board.

  • Methods:

  • setup_pieces(): Initializes pieces in their starting positions.
  • get_piece_at(square: Square) -> Optional[Piece]: Returns the piece at a specific square.
  • move_piece(start: Square, end: Square) -> bool: Moves a piece from start to end square.
  • is_in_bounds(square: Square) -> bool: Checks if a square is within the board limits.

Square#

  • Attributes:
  • x: int: Row number (0-7).
  • y: int: Column number (0-7).
  • piece: Optional[Piece]: The piece on this square, if any.

Piece#

  • Attributes:
  • color: str: Either 'White' or 'Black'.
  • position: Square: The current position of the piece.

  • is_captured: bool: Flag to indicate if the piece has been captured.

  • Methods:

  • move_to(square: Square) -> bool: Moves the piece to a new square.
  • get_valid_moves(board: Board) -> List[Square]: Returns a list of valid moves based on the board state.

Each specific piece type (Pawn, Rook, Knight, Bishop, Queen, King) will subclass Piece and implement its unique movement logic in get_valid_moves.

Player#

  • Attributes:
  • name: str: Player's name.
  • color: str: Player's color ('White' or 'Black').

Move#

  • Attributes:
  • piece: Piece: The piece being moved.
  • start: Square: The starting square of the piece.
  • end: Square: The destination square.
  • captured_piece: Optional[Piece]: The piece captured, if any.

  • is_castling_move: bool: Indicates if the move is a castling move.

  • Methods:

  • is_valid() -> bool: Checks if the move is valid based on the piece’s movement rules and board state.

3. Interactions and Flow#

  • Starting the Game: ChessGame.start_game() will initialize the Board with pieces in their respective positions.
  • Making Moves: When a player makes a move, ChessGame.make_move() will validate it and update the board state accordingly.
  • Turn Management: ChessGame.switch_turn() will alternate the turns between the two players after each valid move.
  • Check and Checkmate: After each move, ChessGame will evaluate if the current player is in check or checkmate using is_checkmate() and is_check() (which could be part of Player or ChessGame).
  • End Game: The game concludes when a checkmate or stalemate condition is reached, or if a player concedes.

Here's a translation of the design into JavaScript, implementing each enhancement step-by-step. This code will use ES6 classes and syntax, aiming for simplicity while highlighting each concept.

1. Piece-Specific Classes and Polymorphism#

Each piece has unique movement logic, so Piece will be a base class with subclasses (e.g., Pawn, Rook, Knight) that override the getValidMoves method.

Piece Class (Base)#

class Piece {
    constructor(color, position) {
        this.color = color; // 'White' or 'Black'
        this.position = position; // Position as { x: number, y: number }
        this.isCaptured = false;
    }

    // Abstract method - to be implemented by subclasses
    getValidMoves(board) {
        throw new Error("This method should be overridden by subclasses");
    }

    moveTo(position) {
        this.position = position;
    }
}

Pawn Class Example#

class Pawn extends Piece {
    getValidMoves(board) {
        const moves = [];
        const direction = this.color === 'White' ? 1 : -1;

        // Standard move
        const forwardPosition = { x: this.position.x, y: this.position.y + direction };
        if (board.isSquareEmpty(forwardPosition)) {
            moves.push(forwardPosition);
        }

        // Capture moves
        [-1, 1].forEach(dx => {
            const capturePosition = { x: this.position.x + dx, y: this.position.y + direction };
            const pieceAtTarget = board.getPieceAt(capturePosition);
            if (pieceAtTarget && pieceAtTarget.color !== this.color) {
                moves.push(capturePosition);
            }
        });

        return moves;
    }
}

Each subclass (e.g., Rook, Knight) would similarly override getValidMoves to reflect specific movement rules, showcasing polymorphism in action.

2. Validation and Rules Management (MoveValidator)#

Let’s add a MoveValidator class to handle game-specific rules like castling, en passant, and check conditions.

MoveValidator Class#

class MoveValidator {
    constructor(board) {
        this.board = board;
    }

    isMoveValid(move, currentPlayerColor) {
        if (move.piece.color !== currentPlayerColor) return false;
        if (move.targetPiece && move.targetPiece.color === currentPlayerColor) return false;
        return !this.wouldCauseCheck(move);
    }

    wouldCauseCheck(move) {
        const { start, end, piece } = move;

        // Simulate move
        const originalTargetPiece = this.board.getPieceAt(end);
        this.board.placePiece(piece, end);
        this.board.removePiece(start);

        const inCheck = this.board.isKingInCheck(piece.color);

        // Undo move
        this.board.placePiece(piece, start);
        this.board.placePiece(originalTargetPiece, end);

        return inCheck;
    }
}

The MoveValidator class ensures that moves follow game rules and prevent invalid moves that would place the player’s king in check.

3. Tracking Game State (Check, Checkmate, Stalemate)#

In ChessGame, we can add methods to detect checkmate and stalemate.

ChessGame Methods#

class ChessGame {
    constructor(board, moveValidator) {
        this.board = board;
        this.moveValidator = moveValidator;
        this.currentPlayer = 'White';
    }

    isCheckmate() {
        const pieces = this.board.getPieces(this.currentPlayer);
        for (const piece of pieces) {
            const moves = piece.getValidMoves(this.board);
            if (moves.some(move => this.moveValidator.isMoveValid(move, this.currentPlayer))) {
                return false;
            }
        }
        return true;
    }

    isStalemate() {
        if (this.board.isKingInCheck(this.currentPlayer)) return false;
        const pieces = this.board.getPieces(this.currentPlayer);
        for (const piece of pieces) {
            const moves = piece.getValidMoves(this.board);
            if (moves.some(move => this.moveValidator.isMoveValid(move, this.currentPlayer))) {
                return false;
            }
        }
        return true;
    }
}

The isCheckmate and isStalemate methods check for the absence of valid moves, based on check and stalemate conditions.

4. Coordinate System and Notation#

Implement utility functions to convert between algebraic notation (e.g., e4) and board coordinates.

Notation Utilities#

class Notation {
    static toAlgebraic(position) {
        return String.fromCharCode(position.x + 97) + (position.y + 1);
    }

    static toCoordinates(algebraic) {
        return {
            x: algebraic.charCodeAt(0) - 97,
            y: parseInt(algebraic[1], 10) - 1
        };
    }
}

This utility makes it easier to work with chess notation, which is useful for move recording and display.

5. Data Structures for Performance#

The board will use a 2D array to represent squares. We could discuss alternatives like bitboards for performance optimization if required.

6. Unit Testing with Jest#

For testing, we’ll assume using Jest as a testing framework. Here's a sample test for Pawn movement:

const board = new Board();
const pawn = new Pawn('White', { x: 1, y: 1 });
board.placePiece(pawn, { x: 1, y: 1 });

test('Pawn initial moves', () => {
    const moves = pawn.getValidMoves(board);
    expect(moves).toEqual([{ x: 1, y: 2 }, { x: 1, y: 3 }]);
});

test('Checkmate detection', () => {
    const game = new ChessGame(board, new MoveValidator(board));
    // Setup checkmate position on the board
    expect(game.isCheckmate()).toBe(true);
});

This verifies the correctness of movement rules and game-ending conditions, covering edge cases like initial double move for Pawn.

7. Error Handling and Edge Cases#

Error handling should prevent illegal moves like moving a captured piece or moving out of bounds. Example in ChessGame.makeMove():

class ChessGame {
    makeMove(start, end) {
        const piece = this.board.getPieceAt(start);
        if (!piece || piece.isCaptured) throw new Error("Invalid piece");
        if (!this.moveValidator.isMoveValid({ start, end, piece }, this.currentPlayer)) {
            throw new Error("Invalid move");
        }
        this.board.movePiece(start, end);
    }
}

Error handling ensures robust gameplay, preventing issues from affecting the game state.

8. Extensions and Scalability#

We can discuss possible extensions:
- AI Opponent: Implement an AI using algorithms like Minimax.
- Network Multiplayer: Add support for online play.
- Move Hints: Suggest valid moves by highlighting them on the board.

This JavaScript-based low-level design showcases object-oriented principles, handling of special cases, and extensibility for future features. Let me know if you’d like additional details on any component!

---#

python implementation#

To enhance this chess implementation, we'll add features such as check detection, checkmate, castling, and en passant. These improvements require refining movement rules and adding checks for specific game states. Here’s how we can implement these features in Python.

Improved Chess Game Implementation in Python#

class Piece:
    def __init__(self, color, position):
        self.color = color  # 'White' or 'Black'
        self.position = position
        self.has_moved = False

    def move_to(self, position):
        self.position = position
        self.has_moved = True

    def get_valid_moves(self, board):
        raise NotImplementedError("This method should be implemented in subclasses.")


class King(Piece):
    def get_valid_moves(self, board):
        moves = []
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        for dx, dy in directions:
            target = (self.position[0] + dx, self.position[1] + dy)
            if board.is_within_bounds(target) and (not board.get_piece_at(target) or board.get_piece_at(target).color != self.color):
                moves.append(target)
        return moves

    def get_castling_moves(self, board):
        moves = []
        if not self.has_moved and not board.is_in_check(self.color):
            row = 0 if self.color == 'White' else 7
            for rook_position in [(0, row), (7, row)]:
                rook = board.get_piece_at(rook_position)
                if isinstance(rook, Rook) and not rook.has_moved:
                    if board.is_clear_path(self.position, rook_position) and not board.would_be_in_check(self.position, rook_position, self.color):
                        moves.append((self.position[0] + 2 * (1 if rook_position[0] > self.position[0] else -1), self.position[1]))
        return moves


class Queen(Piece):
    def get_valid_moves(self, board):
        moves = []
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        for dx, dy in directions:
            x, y = self.position[0] + dx, self.position[1] + dy
            while board.is_within_bounds((x, y)) and (board.is_square_empty((x, y)) or board.get_piece_at((x, y)).color != self.color):
                moves.append((x, y))
                if board.get_piece_at((x, y)):
                    break
                x += dx
                y += dy
        return moves


class Rook(Piece):
    def get_valid_moves(self, board):
        moves = []
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for dx, dy in directions:
            x, y = self.position[0] + dx, self.position[1] + dy
            while board.is_within_bounds((x, y)) and (board.is_square_empty((x, y)) or board.get_piece_at((x, y)).color != self.color):
                moves.append((x, y))
                if board.get_piece_at((x, y)):
                    break
                x += dx
                y += dy
        return moves


class Bishop(Piece):
    def get_valid_moves(self, board):
        moves = []
        directions = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
        for dx, dy in directions:
            x, y = self.position[0] + dx, self.position[1] + dy
            while board.is_within_bounds((x, y)) and (board.is_square_empty((x, y)) or board.get_piece_at((x, y)).color != self.color):
                moves.append((x, y))
                if board.get_piece_at((x, y)):
                    break
                x += dx
                y += dy
        return moves


class Knight(Piece):
    def get_valid_moves(self, board):
        moves = []
        offsets = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
        for dx, dy in offsets:
            target = (self.position[0] + dx, self.position[1] + dy)
            if board.is_within_bounds(target) and (not board.get_piece_at(target) or board.get_piece_at(target).color != self.color):
                moves.append(target)
        return moves


class Pawn(Piece):
    def get_valid_moves(self, board):
        moves = []
        direction = 1 if self.color == 'White' else -1
        forward_position = (self.position[0], self.position[1] + direction)

        if board.is_square_empty(forward_position):
            moves.append(forward_position)

            # Initial double step move
            if not self.has_moved:
                double_forward = (self.position[0], self.position[1] + 2 * direction)
                if board.is_square_empty(double_forward):
                    moves.append(double_forward)

        # Capture moves
        for dx in [-1, 1]:
            capture_position = (self.position[0] + dx, self.position[1] + direction)
            piece_at_target = board.get_piece_at(capture_position)
            if piece_at_target and piece_at_target.color != self.color:
                moves.append(capture_position)
            # En passant capture
            if board.can_en_passant(self.position, capture_position, self.color):
                moves.append(capture_position)

        return moves


class Board:
    def __init__(self):
        self.grid = [[None for _ in range(8)] for _ in range(8)]
        self.en_passant_target = None  # Tracks en passant target square for one turn

    def place_piece(self, piece):
        x, y = piece.position
        self.grid[y][x] = piece

    def move_piece(self, piece, position):
        old_x, old_y = piece.position
        new_x, new_y = position

        if piece.get_valid_moves(self).count(position) > 0:
            self.grid[old_y][old_x] = None
            piece.move_to(position)
            self.grid[new_y][new_x] = piece
            if isinstance(piece, Pawn) and abs(old_y - new_y) == 2:
                self.en_passant_target = (old_x, (old_y + new_y) // 2)
            else:
                self.en_passant_target = None
        else:
            raise ValueError("Invalid move")

    def get_piece_at(self, position):
        x, y = position
        return self.grid[y][x]

    def is_square_empty(self, position):
        return self.get_piece_at(position) is None

    def is_within_bounds(self, position):
        x, y = position
        return 0 <= x < 8 and 0 <= y < 8

    def is_in_check(self, color):
        king_position = None
        for row in self.grid:
            for piece in row:
                if isinstance(piece, King) and piece.color == color:
                    king_position = piece.position
                    break
        for row in self.grid:
            for piece in row:
                if piece and piece.color != color:
                    if king_position in piece.get_valid_moves(self):
                        return True
        return False

    def would_be_in_check(self, start, end, color):
        piece = self.get_piece_at(start)
        target_piece = self.get_piece_at(end)
        self.grid[start[1]][start[0]] = None
        self.grid[end[1]][end[0]] = piece
        piece.position = end
        check_status = self.is_in_check(color)
        self.grid[start[1]][start[0]] = piece
        self.grid[end[1]][end[0]] = target_piece
        piece.position = start
        return check_status

    def is_clear_path(self, start, end):
        direction = (1 if end[0] > start[0] else -1, 1 if end[1] > start[1] else -1)
        x, y = start[0] + direction[0], start[1] + direction[1]
        while (x, y) != end:
            if self.grid[y][x] is not None:
                return False
            x += direction[0]
            y += direction[1]
        return True

    def can_en_passant(self, pawn_position, target_position, color):
        return self.en_passant_target == target_position


class ChessGame:
    def __init__(self):
        self.board = Board()
        self.setup_board()

    def setup_board(self):
        # Setup initial positions (same as previous setup)

    def make_move(self, start, end):
        piece = self.board.get_piece_at(start)
        if piece is None:
            raise ValueError("No piece at start position")
        if self.board.would_be_in_check(start, end, piece.color):
            raise ValueError("Move would leave king in check")
        self.board.move_piece(piece, end)

# Initialize and use game
game = ChessGame()

Certainly. Let's continue with a breakdown of the improvements added and how they work:

Improvements Added:#

  1. Castling Logic:

  2. Implemented in the King class using the get_castling_moves method. This checks if the king or rook involved has moved before and if the path between them is clear. Also verifies that the squares the king would pass through are not under attack (king cannot castle out of or through check).

  3. En Passant Logic:

  4. Implemented in the Pawn class’s get_valid_moves method and in the Board class.

  5. En passant captures are possible only immediately after an opponent pawn advances two squares. We store the en passant target square in self.en_passant_target, which is then checked during the pawn’s move validation.

  6. Check Detection:

  7. Implemented in the Board class with the is_in_check method.

  8. After each move, we check if the player’s own king is in check, prohibiting any move that would leave the king in danger. This logic is also used to validate castling and prevent it through check.

  9. Checkmate Detection:

  10. Checkmate could be detected by looping through all of the current player's pieces and finding if any move would get them out of check. If no moves prevent check, then it's a checkmate.

  11. While the full code for checkmate isn't in the snippet yet, it can be implemented in the ChessGame class by creating a is_checkmate method that loops through all valid moves.

  12. Path Validation:

  13. Added is_clear_path in the Board class to verify if there are any pieces between the start and end squares for pieces like rooks, bishops, and queens.

Example Usage#

With these enhancements, here’s how you might use this code to play a game or check for checkmate:

game = ChessGame()

# Move a piece
try:
    game.make_move((4, 1), (4, 3))  # Example pawn move
    game.make_move((4, 6), (4, 4))  # Opponent pawn move
    game.make_move((5, 0), (2, 3))  # White queen moves to set up check
except ValueError as e:
    print(e)  # Output any invalid moves or check violations

Detecting Checkmate and Stalemate#

Adding checkmate and stalemate detection requires a method that will:
- For checkmate: If a player is in check and has no valid moves that could prevent the check.
- For stalemate: If a player is not in check but has no legal moves.

class ChessGame:
    def __init__(self):
        self.board = Board()
        self.current_turn = 'White'
        self.setup_board()

    def is_checkmate(self, color):
        if not self.board.is_in_check(color):
            return False

        # Try every move for each piece to see if any move escapes check
        for row in self.board.grid:
            for piece in row:
                if piece and piece.color == color:
                    for move in piece.get_valid_moves(self.board):
                        if not self.board.would_be_in_check(piece.position, move, color):
                            return False  # Found a move that prevents check
        return True  # No moves available to prevent check

    def is_stalemate(self, color):
        if self.board.is_in_check(color):
            return False

        # Try every move for each piece to see if any legal move is possible
        for row in self.board.grid:
            for piece in row:
                if piece and piece.color == color:
                    for move in piece.get_valid_moves(self.board):
                        if not self.board.would_be_in_check(piece.position, move, color):
                            return False  # Found a legal move
        return True  # No legal moves, so it's a stalemate

Game Loop for Testing Checkmate and Stalemate#

while True:
    color = game.current_turn
    if game.is_checkmate(color):
        print(f"Checkmate! {color} loses.")
        break
    elif game.is_stalemate(color):
        print("Stalemate!")
        break

    # Assume we get start and end coordinates from player input
    try:
        start = input("Enter start position (e.g., 'e2'): ")
        end = input("Enter end position (e.g., 'e4'): ")
        start = (ord(start[0]) - ord('a'), int(start[1]) - 1)
        end = (ord(end[0]) - ord('a'), int(end[1]) - 1)

        game.make_move(start, end)
        game.current_turn = 'Black' if game.current_turn == 'White' else 'White'
    except ValueError as e:
        print(e)

Summary#

This Python implementation now includes essential chess mechanics:
- Castling (both kingside and queenside).
- En passant for pawns.
- Check and checkmate detection.
- Stalemate detection.

This version, although simplified, represents most major rules in chess and provides a solid foundation for further enhancement, such as adding a UI, an AI opponent, or advanced game state persistence.

---#

For a Low-Level Design (LLD) explanation of a chess game that would impress an interviewer, you should focus on clearly communicating the structure and logic of your code. Here’s how you might break it down:

1. Class Structure and Design Patterns#

  • Piece Class:

    • The Piece class serves as an abstract base class for all chess pieces, encapsulating shared behavior (e.g., position, color).
    • This class has subclasses (Pawn, Knight, Bishop, Rook, Queen, King) where each subclass defines unique movement rules.
    • Explanation: Using inheritance allows each piece to implement its unique movement logic while inheriting shared characteristics like position and color.

  • Board Class:

    • Manages an 8x8 grid of Piece objects, responsible for piece placement, movement validation, and tracking the game state.
    • This class includes helper methods (is_clear_path, is_in_check, move_piece, etc.) that enforce movement rules, detect check conditions, and validate moves for special rules.
    • Explanation: This centralized class manages all aspects of the board state, enforcing encapsulation by making the board responsible for updating, moving, and validating pieces.

  • ChessGame Class:

    • The ChessGame class serves as the controller, managing game flow, turns, and win/loss conditions.
    • It checks for check, checkmate, and stalemate after each move and toggles turns.
    • Explanation: This high-level class helps isolate game logic from board and piece details, improving code modularity and separating responsibilities.

2. Key Features and Rules Implemented#

  • Standard Movements:

    • Each piece’s movement patterns are defined in the respective subclasses.
    • Methods like get_valid_moves are overridden in each subclass to define unique moves (e.g., Knight's L-shaped moves, Bishop's diagonal moves).

  • Special Rules:

    • Castling: Implemented in King and Board. The King verifies that it and the rook have not moved, and the Board ensures squares between them are empty and not under attack.
    • En Passant: Implemented in Pawn and managed in Board using an en passant target square to capture opponent pawns when appropriate.
    • Check and Checkmate Detection:
    • Board has an is_in_check method, which determines if a move places the king in check.
    • Checkmate: Implemented by verifying if all possible moves result in a check, thus confirming there’s no escape for the king.
    • Explanation: These features involve board-wide conditions and require a view of all pieces, justifying their implementation in the Board class.

3. Helper Methods#

  • Move Validation:
    • The Board class includes utility methods like is_clear_path, which checks for obstacles in a piece’s movement line (used by Rook, Bishop, Queen).
    • Explanation: These helper functions encapsulate reusable functionality and simplify move validation within each piece class.

4. Design Decisions and Trade-offs#

  • Encapsulation and Responsibility:
    • Each class has clear responsibilities (e.g., Board manages positions and move validations, Piece handles individual moves).
    • Encapsulation simplifies debugging and enables efficient unit testing (e.g., is_in_check can be tested independently).
  • Extendibility:
    • The use of a Piece superclass and dedicated subclasses means future modifications (like adding new pieces for variant games) can be achieved with minimal changes to existing code.
  • Readability:
    • Each method performs a single task, improving code readability, maintainability, and scalability.

5. Efficiency and Optimization#

  • Time Complexity:
    • Most moves and checks involve iterating over a limited 8x8 board, so time complexity is kept low.
    • The is_in_check function optimizes by only verifying moves that affect the king, minimizing computational load.

Example Code Explanation (in Python)#

class Piece:
    def __init__(self, color, position):
        self.color = color
        self.position = position

    def get_valid_moves(self, board):
        pass  # To be overridden by each specific piece type
  • Explanation: The Piece class is designed to be overridden by each chess piece subclass, making it the foundational building block for any piece type, enforcing a consistent interface.

Final Thoughts#

This design showcases:
- OOP Principles: Effective use of encapsulation, inheritance, and polymorphism.
- Responsibility Segregation: Each class has a clear role, ensuring easy debugging and code reuse.
- Modular Approach: By isolating movement logic and special rules, this design allows easy testing, extendibility, and scalability, which is critical for a complex system like a chess engine.

By structuring the explanation this way, you’ll show a deep understanding of both the code's structure and the reasoning behind each design choice, which will impress interviewers looking for solid software design principles and practical coding skills.