Move validation and check detection in LLD - System Design Exercise

Design: Chess Move Validation and Check Detection System

In scope: move validation logic, check and checkmate detection, special move handling, concurrency for multiple games. Out of scope: user authentication, game matchmaking, UI design.

Functional Requirements

FR1: Validate if a player's move is legal according to chess rules

FR2: Detect if a move results in a check or checkmate

FR3: Support all standard chess pieces and their movement rules

FR4: Handle special moves: castling, en passant, pawn promotion

FR5: Provide real-time feedback on move validity and game state

FR6: Support concurrent games with multiple players

Non-Functional Requirements

NFR1: Must validate moves within 100ms to ensure smooth gameplay

NFR2: System should handle up to 10,000 concurrent games

NFR3: Availability target of 99.9% uptime

NFR4: Memory usage should be optimized for running multiple game states

NFR5: System must prevent illegal moves and invalid game states

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Game state manager to track board and piece positions

Move validator module implementing chess rules

Check detection engine to identify check and checkmate

Special moves handler for castling, en passant, promotion

Concurrency controller for managing multiple games

Cache or memoization for repeated state evaluations

Design Patterns

State pattern for managing game states

Command pattern for encapsulating moves

Observer pattern for notifying game state changes

Caching pattern to optimize repeated validations

Event-driven architecture for move processing

Reference Architecture

Client
  |
  v
Move Request --> Move Validator --> Game State Manager --> Check Detection Engine
  |                                         |
  |                                         v
  |---------------------> Special Moves Handler
  |
  v
Response (valid/invalid, check status)

Multiple concurrent games managed by Concurrency Controller

Components

Move Validator

Custom logic module

Validate if a move is legal based on piece type, position, and chess rules

Game State Manager

In-memory data structure

Maintain current board state and piece positions

Check Detection Engine

Algorithmic module

Detect if the current player is in check or checkmate after a move

Special Moves Handler

Rule-based logic

Handle castling, en passant, and pawn promotion rules

Concurrency Controller

Thread-safe game session manager

Manage multiple simultaneous games and isolate their states

Request Flow

1. 1. Client sends a move request with current game ID and move details.

2. 2. Concurrency Controller routes request to the correct game session.

3. 3. Move Validator checks if the move is legal for the piece and position.

4. 4. If special move, Special Moves Handler validates special conditions.

5. 5. Game State Manager updates the board state if move is valid.

6. 6. Check Detection Engine analyzes the updated board for check or checkmate.

7. 7. System responds to client with move validity and check status.

8. 8. If invalid, state remains unchanged and error is returned.

Database Schema

Entities: - GameSession: game_id (PK), player_white_id, player_black_id, current_turn, game_state (serialized board) - Move: move_id (PK), game_id (FK), player_id, from_position, to_position, move_type, timestamp Relationships: - One GameSession has many Moves - Each Move belongs to one GameSession and one Player Game state stored in-memory for fast access; persistent storage for game history.

Scaling Discussion

Bottlenecks

High CPU usage for validating moves and detecting check in many concurrent games

Memory consumption for storing multiple game states in memory

Latency increase when many move requests arrive simultaneously

Complexity in handling special moves and edge cases efficiently

Solutions

Use efficient data structures (bitboards) to speed up move validation and check detection

Partition games across multiple servers or processes to distribute load

Implement caching for repeated board state evaluations

Use asynchronous processing and queueing to smooth spikes in move requests

Optimize special move logic with precomputed rules and early exits

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing components and data flow, 10 minutes discussing scaling and trade-offs, 5 minutes summarizing.

Explain how chess rules translate into move validation logic

Describe handling of special moves and their challenges

Discuss data structures used for efficient board representation

Highlight concurrency management for multiple games

Address latency and availability targets with scaling strategies