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

Practice

1. What is the primary purpose of move validation in a chess game system?

easy

A. To ensure only legal moves according to game rules are accepted

B. To update the user interface after a move

C. To save the game state to a database

D. To detect if a player is in check

Solution

1. Step 1: Understand move validation role

   Move validation checks if a move follows the rules of chess, like piece movement and board boundaries.

2. Step 2: Differentiate from other functions

   Updating UI or saving state are separate tasks; detecting check is related but distinct from move validation.

3. Final Answer:

   To ensure only legal moves according to game rules are accepted -> Option A

4. Quick Check:

   Move validation = Legal move check [OK]

Hint: Move validation means checking if a move follows rules [OK]

Common Mistakes:

• Confusing move validation with UI updates
• Thinking move validation detects check
• Assuming move validation saves game state

2. Which of the following code snippets correctly represents a basic move validation check for a rook in chess?

easy

A. if abs(start_row - end_row) == 1 and abs(start_col - end_col) == 1: return True else: return False

B. if start_row == end_row or start_col == end_col: return True else: return False

C. if abs(start_row - end_row) == abs(start_col - end_col): return True else: return False

D. if end_row == start_row + 2 or end_col == start_col + 2: return True else: return False

Solution

1. Step 1: Recall rook movement rules

   A rook moves any number of squares along a row or column, so either row or column must be the same.

2. Step 2: Match code to rules

   if start_row == end_row or start_col == end_col: return True else: return False checks if start and end share the same row or column, which matches rook moves.

3. Final Answer:

   if start_row == end_row or start_col == end_col: return True else: return False -> Option B

4. Quick Check:

   Rook moves = same row or column [OK]

Hint: Rook moves straight: same row or same column [OK]

Common Mistakes:

• Confusing rook moves with diagonal moves
• Using absolute difference for rook incorrectly
• Checking only fixed steps instead of any distance

3. Given this simplified move validation function for a king:

def is_valid_king_move(start, end):
    row_diff = abs(start[0] - end[0])
    col_diff = abs(start[1] - end[1])
    return (row_diff <= 1 and col_diff <= 1) and (row_diff + col_diff != 0)

What will is_valid_king_move((4,4), (5,5)) return?

medium

A. True

B. False

C. None

D. Error

Solution

1. Step 1: Calculate row and column differences

   row_diff = |4 - 5| = 1, col_diff = |4 - 5| = 1

2. Step 2: Evaluate conditions

   row_diff <= 1 and col_diff <= 1 is True; row_diff + col_diff != 0 is True (1+1=2)

3. Final Answer:

   True -> Option A

4. Quick Check:

   King moves one step any direction = True [OK]

Hint: King moves one square in any direction, including diagonals [OK]

Common Mistakes:

• Ignoring diagonal moves for king
• Mistaking zero move as valid
• Confusing row and column differences

4. In a check detection system, a bug causes the game to allow moves that leave the king in check. Which is the most likely cause?

medium

A. The system only checks for check after the opponent moves

B. The move validation incorrectly rejects legal moves

C. The system updates the board state before validating moves

D. The system validates moves but does not check if the king remains safe after the move

Solution

1. Step 1: Understand check detection role

   Check detection ensures no move leaves the king under attack after it is made.

2. Step 2: Identify bug cause

   If moves are validated but king safety is not checked post-move, illegal moves leaving king in check can occur.

3. Final Answer:

   The system validates moves but does not check if the king remains safe after the move -> Option D

4. Quick Check:

   Check detection missing after move = bug [OK]

Hint: Always check king safety after move validation [OK]

Common Mistakes:

• Assuming move validation covers check detection
• Checking for check only after opponent moves
• Updating board before validation causing state errors

5. You are designing a chess engine's move validation and check detection system. Which approach best ensures both correctness and performance?

hard

A. Skip move validation and rely on players to avoid illegal moves

B. Only check if the king is in check before the move, ignoring post-move state

C. First validate move legality, then simulate the move to check if king is in check, rejecting if so

D. Validate moves and check detection simultaneously by scanning the entire board every time

Solution

1. Step 1: Separate move legality and check detection

   Validate if the move follows piece rules first to avoid unnecessary checks.

2. Step 2: Simulate move and check king safety

   Temporarily apply the move and verify if the king is attacked; reject if unsafe.

3. Final Answer:

   First validate move legality, then simulate the move to check if king is in check, rejecting if so -> Option C

4. Quick Check:

   Validate then simulate for check = best practice [OK]

Hint: Validate move first, then simulate for check detection [OK]

Common Mistakes:

• Ignoring post-move king safety
• Checking entire board every time causing slowdowns
• Skipping move validation entirely