Move validation and check detection in LLD - Scalability & System Analysis

Scalability Analysis - Move validation and check detection

Growth Table: Move Validation and Check Detection

Users / Games	Move Requests per Second	Validation Latency	CPU Usage	Memory Usage	Storage for Game States
100 users (~50 games)	~5 moves/sec	<10 ms	Low	Low	Small (few MB)
10,000 users (~5,000 games)	~500 moves/sec	10-50 ms	Moderate	Moderate	Medium (GBs)
1,000,000 users (~500,000 games)	~50,000 moves/sec	50-200 ms	High	High	Large (TBs)
100,000,000 users (~50,000,000 games)	~5,000,000 moves/sec	200+ ms (unacceptable)	Very High	Very High	Very Large (PBs)

First Bottleneck

The first bottleneck is the CPU and memory on the application servers that perform move validation and check detection. This logic is computationally intensive because it requires analyzing the current game state, applying chess rules, and detecting check conditions.

At small scale, a single server can handle all validations quickly. As users grow, the CPU load increases linearly with move requests. Memory usage also grows due to storing many active game states.

Eventually, the server CPU cores become saturated, causing increased latency and slower validation responses.

Scaling Solutions

• Horizontal scaling: Add more application servers to distribute move validation load. Use a load balancer to route requests.
• State partitioning: Partition games by user or game ID so each server handles a subset of games, reducing memory and CPU per server.
• Caching: Cache recent validation results or partial computations to avoid repeated heavy calculations.
• Asynchronous processing: For non-blocking UI, validate moves asynchronously and notify clients when done.
• Offload check detection: Use specialized microservices or optimized libraries (e.g., native code) for check detection to improve performance.
• Database optimization: Store game states efficiently and use in-memory stores (like Redis) for fast access.

Back-of-Envelope Cost Analysis

• At 1M users with ~50,000 moves/sec, assuming each validation takes 10 ms CPU time, total CPU time needed per second is 500 seconds. With 8-core servers, each core can handle ~100 validations/sec, so ~63 servers needed.
• Memory per game state ~10 KB, for 500,000 games = ~5 GB RAM needed just for game states.
• Network bandwidth per move is small (~1 KB), so 50,000 moves/sec = ~50 MB/s, manageable on 1 Gbps links.
• Storage for historical game data grows with users; archiving old games reduces storage pressure.

Interview Tip

Start by explaining the move validation process and why it is CPU intensive. Then discuss how load grows with users and moves per second. Identify the CPU and memory on app servers as the first bottleneck. Propose horizontal scaling and partitioning as primary solutions. Mention caching and asynchronous processing as optimizations. Finally, discuss database and network considerations briefly.

Self Check

Your database handles 1000 QPS. Traffic grows 10x to 10,000 QPS. What do you do first?

Answer: Since move validation is CPU intensive, first add more application servers to horizontally scale validation. Also partition game states to distribute load. Then consider caching and database read replicas if needed.

Key Result

Move validation and check detection scale linearly with move requests, making CPU and memory on application servers the first bottleneck. Horizontal scaling and partitioning are key to handle growth beyond thousands of concurrent games.

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