Games & SimulationsProblem 10 of 11
Games & SimulationsAdvanced
Chess
Strategy PatternCommand PatternTemplate Method
Each piece owns its move generation via Strategy. Command pattern wraps every move so you can undo it during check validation. Board stays clean.
Key Abstractions
Game
Turn management, game state transitions, coordinates between board and move validation
Board
8x8 grid, executes and undoes moves, tracks piece positions by color
Piece
Abstract base with color, position, and delegated move generation
King / Queen / Rook / Bishop / Knight / Pawn
Concrete pieces, each implementing its own legal move generation
MoveValidator
Filters pseudo-legal moves by checking if they leave the king in check
Move
Value object with from/to squares, captured piece, and special flags (castling, promotion)
GameState
Enum: IN_PROGRESS, CHECK, CHECKMATE, STALEMATE
Class Diagram
Every Piece Knows How It Moves
Chess has six piece types and each one moves differently. You could put all the movement rules in a giant switch statement inside Board, but that turns the Board class into a knowledge dump for every piece's quirks. Instead, give each piece its own getPseudoLegalMoves method. King knows it moves one square in any direction. Knight knows it jumps in L-shapes. Sliding pieces (rook, bishop, queen) share a template method that walks along direction vectors until hitting the edge or another piece.
"Pseudo-legal" is an important distinction. A piece might generate a move that looks valid based on its own movement rules but actually leaves the king in check. That filtering happens one level up, in the MoveValidator. This two-phase approach keeps piece logic simple and testable in isolation.
The other critical pattern here is Command on moves. Every Move object carries enough information to undo itself: the piece that moved, where it came from, where it went, and what it captured. This undo capability isn't just nice for implementing a "take back" feature. It's essential for check validation. To determine whether a move is legal, you execute it, check if your king is in check, then undo it. Without undo, you'd need to clone the entire board for every candidate move. On a board with 30+ legal moves per position, that's a lot of garbage.
Requirements
Functional
- Standard 8x8 board with all six piece types
- Each piece generates its own legal moves based on chess rules
- Move validation rejects moves that leave the king in check
- Detect check, checkmate, and stalemate after every move
- Support basic pawn movement (forward, two-square start, diagonal capture)
Non-Functional
- Move generation per piece should be self-contained and independently testable
- Check validation should reuse move/undo rather than cloning the board
- Adding a new piece type should not require modifying existing piece classes
Design Decisions
Why does each piece own its move generation?
Single responsibility. A King, a Knight, and a Pawn have completely different movement rules. Centralizing them in Board creates a class that changes every time any piece's rules change. With move generation on the piece itself, adding a fairy chess piece (like an Amazon or Archbishop) means writing one new class. Nothing else changes.
Why Command pattern for moves instead of board cloning?
Check validation requires "what if" analysis: execute a candidate move, see if the king is attacked, then roll back. Cloning an 8x8 board with piece references for each of the ~30 candidate moves per turn is wasteful. A Move object that stores the before-state (from position, captured piece) gives you O(1) undo. Execute, check, undo. No allocations, no deep copies.
Why not use inheritance for piece color (WhiteKing, BlackKing)?
Color doesn't change behavior. A white rook and a black rook move the same way. Color is just a data field that determines which side a piece belongs to. Creating separate subclasses per color doubles the class count for zero behavioral difference. Composition handles this cleanly: the piece has a color field, and move generation uses it to determine which pieces are friendly vs. enemy.
Why separate MoveValidator from Board?
Board manages the grid: placing pieces, executing moves, undoing moves. MoveValidator answers the question "is this move legal?" and "is this color in check?" These are different responsibilities. You can test Board's execute/undo without involving check logic. You can test check detection with a carefully arranged board without going through the full game flow.
Interview Follow-ups
- "How would you add castling?" Special-case in King's move generation. Check that the king and rook haven't moved (add a
hasMovedflag), that squares between them are empty, and that the king doesn't pass through check. Represent it as a Move with a special flag that triggers both king and rook movement in execute/undo. - "How would you add en passant?" Track the last move. If it was a pawn double-step, the adjacent pawn can capture to the square behind it. Store a board-level
enPassantTargetposition that resets every turn. - "How would you implement an AI player?" Minimax with alpha-beta pruning. The Game class already produces legal moves. AI evaluates board positions using a heuristic (material count, piece-square tables) and picks the best move.
- "How would you handle draw by repetition or the 50-move rule?" Maintain a move history list and a hash of each board position. Three identical position hashes triggers a draw. A counter that resets on captures and pawn moves tracks the 50-move rule.
Code Implementation
1 from abc import ABC, abstractmethod
2 from dataclasses import dataclass
3 from enum import Enum
4 from typing import Optional
5
6
7 class Color(Enum):
8 WHITE = "white"
9 BLACK = "black"
10
11 def opposite(self) -> "Color":
12 return Color.BLACK if self == Color.WHITE else Color.WHITE
13
14
15 class GameState(Enum):
16 IN_PROGRESS = "in_progress"
17 CHECK = "check"
18 CHECKMATE = "checkmate"
19 STALEMATE = "stalemate"
20
21
22 @dataclass(frozen=True)
23 class Position:
24 row: int
25 col: int
26
27 def is_valid(self) -> bool:
28 return 0 <= self.row < 8 and 0 <= self.col < 8
29
30
31 @dataclass
32 class Move:
33 piece: "Piece"
34 from_pos: Position
35 to_pos: Position
36 captured: Optional["Piece"] = None
37
38
39 class Piece(ABC):
40 def __init__(self, color: Color, position: Position):
41 self.color = color
42 self.position = position
43
44 @abstractmethod
45 def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
46 """Generate moves without considering check constraints."""
47 ...
48
49 @abstractmethod
50 def symbol(self) -> str: ...
51
52 def _slide_moves(self, board: "Board", directions: list[tuple[int, int]]) -> list[Move]:
53 """Template method for sliding pieces (rook, bishop, queen)."""
54 moves: list[Move] = []
55 for dr, dc in directions:
56 r, c = self.position.row + dr, self.position.col + dc
57 while 0 <= r < 8 and 0 <= c < 8:
58 target = Position(r, c)
59 occupant = board.get_piece(r, c)
60 if occupant is None:
61 moves.append(Move(self, self.position, target))
62 elif occupant.color != self.color:
63 moves.append(Move(self, self.position, target, captured=occupant))
64 break
65 else:
66 break
67 r, c = r + dr, c + dc
68 return moves
69
70 def __repr__(self) -> str:
71 return f"{self.symbol()}@({self.position.row},{self.position.col})"
72
73
74 class King(Piece):
75 def symbol(self) -> str:
76 return "K" if self.color == Color.WHITE else "k"
77
78 def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
79 moves: list[Move] = []
80 for dr in (-1, 0, 1):
81 for dc in (-1, 0, 1):
82 if dr == 0 and dc == 0:
83 continue
84 target = Position(self.position.row + dr, self.position.col + dc)
85 if not target.is_valid():
86 continue
87 occupant = board.get_piece(target.row, target.col)
88 if occupant is None or occupant.color != self.color:
89 moves.append(Move(self, self.position, target, captured=occupant))
90 return moves
91
92
93 class Queen(Piece):
94 def symbol(self) -> str:
95 return "Q" if self.color == Color.WHITE else "q"
96
97 def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
98 directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
99 return self._slide_moves(board, directions)
100
101
102 class Rook(Piece):
103 def symbol(self) -> str:
104 return "R" if self.color == Color.WHITE else "r"
105
106 def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
107 return self._slide_moves(board, [(-1, 0), (1, 0), (0, -1), (0, 1)])
108
109
110 class Bishop(Piece):
111 def symbol(self) -> str:
112 return "B" if self.color == Color.WHITE else "b"
113
114 def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
115 return self._slide_moves(board, [(-1, -1), (-1, 1), (1, -1), (1, 1)])
116
117
118 class Knight(Piece):
119 def symbol(self) -> str:
120 return "N" if self.color == Color.WHITE else "n"
121
122 def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
123 moves: list[Move] = []
124 offsets = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
125 for dr, dc in offsets:
126 target = Position(self.position.row + dr, self.position.col + dc)
127 if not target.is_valid():
128 continue
129 occupant = board.get_piece(target.row, target.col)
130 if occupant is None or occupant.color != self.color:
131 moves.append(Move(self, self.position, target, captured=occupant))
132 return moves
133
134
135 class Pawn(Piece):
136 def symbol(self) -> str:
137 return "P" if self.color == Color.WHITE else "p"
138
139 def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
140 moves: list[Move] = []
141 direction = -1 if self.color == Color.WHITE else 1
142 start_row = 6 if self.color == Color.WHITE else 1
143
144 # Forward one
145 one_ahead = Position(self.position.row + direction, self.position.col)
146 if one_ahead.is_valid() and board.get_piece(one_ahead.row, one_ahead.col) is None:
147 moves.append(Move(self, self.position, one_ahead))
148 # Forward two from starting row
149 two_ahead = Position(self.position.row + 2 * direction, self.position.col)
150 if (self.position.row == start_row
151 and board.get_piece(two_ahead.row, two_ahead.col) is None):
152 moves.append(Move(self, self.position, two_ahead))
153
154 # Diagonal captures
155 for dc in (-1, 1):
156 diag = Position(self.position.row + direction, self.position.col + dc)
157 if not diag.is_valid():
158 continue
159 occupant = board.get_piece(diag.row, diag.col)
160 if occupant is not None and occupant.color != self.color:
161 moves.append(Move(self, self.position, diag, captured=occupant))
162
163 return moves
164
165
166 class Board:
167 def __init__(self):
168 self._grid: list[list[Optional[Piece]]] = [[None] * 8 for _ in range(8)]
169 self._pieces: dict[Color, list[Piece]] = {Color.WHITE: [], Color.BLACK: []}
170
171 def place_piece(self, piece: Piece) -> None:
172 self._grid[piece.position.row][piece.position.col] = piece
173 self._pieces[piece.color].append(piece)
174
175 def get_piece(self, row: int, col: int) -> Optional[Piece]:
176 return self._grid[row][col]
177
178 def get_pieces_by_color(self, color: Color) -> list[Piece]:
179 return list(self._pieces[color])
180
181 def find_king(self, color: Color) -> Position:
182 for piece in self._pieces[color]:
183 if isinstance(piece, King):
184 return piece.position
185 raise RuntimeError(f"No {color.value} king on the board")
186
187 def execute_move(self, move: Move) -> None:
188 """Apply a move. Modifies board state in place."""
189 if move.captured is not None:
190 self._pieces[move.captured.color].remove(move.captured)
191
192 self._grid[move.from_pos.row][move.from_pos.col] = None
193 self._grid[move.to_pos.row][move.to_pos.col] = move.piece
194 move.piece.position = move.to_pos
195
196 def undo_move(self, move: Move) -> None:
197 """Reverse a move. Used during check validation."""
198 self._grid[move.to_pos.row][move.to_pos.col] = move.captured
199 self._grid[move.from_pos.row][move.from_pos.col] = move.piece
200 move.piece.position = move.from_pos
201
202 if move.captured is not None:
203 self._pieces[move.captured.color].append(move.captured)
204
205 def display(self) -> str:
206 rows = []
207 for r in range(8):
208 row_str = ""
209 for c in range(8):
210 piece = self._grid[r][c]
211 row_str += piece.symbol() if piece else "."
212 row_str += " "
213 rows.append(f"{8 - r} {row_str}")
214 rows.append(" a b c d e f g h")
215 return "\n".join(rows)
216
217
218 class MoveValidator:
219 def is_in_check(self, board: Board, color: Color) -> bool:
220 king_pos = board.find_king(color)
221 enemy_color = color.opposite()
222 for piece in board.get_pieces_by_color(enemy_color):
223 for move in piece.get_pseudo_legal_moves(board):
224 if move.to_pos == king_pos:
225 return True
226 return False
227
228 def is_legal(self, board: Board, move: Move) -> bool:
229 """A move is legal if it doesn't leave the moving player's king in check."""
230 board.execute_move(move)
231 in_check = self.is_in_check(board, move.piece.color)
232 board.undo_move(move)
233 return not in_check
234
235 def get_legal_moves(self, board: Board, color: Color) -> list[Move]:
236 legal: list[Move] = []
237 for piece in board.get_pieces_by_color(color):
238 for move in piece.get_pseudo_legal_moves(board):
239 if self.is_legal(board, move):
240 legal.append(move)
241 return legal
242
243 def has_legal_moves(self, board: Board, color: Color) -> bool:
244 for piece in board.get_pieces_by_color(color):
245 for move in piece.get_pseudo_legal_moves(board):
246 if self.is_legal(board, move):
247 return True
248 return False
249
250
251 class Game:
252 def __init__(self, board: Board):
253 self._board = board
254 self._validator = MoveValidator()
255 self._current_color = Color.WHITE
256 self._state = GameState.IN_PROGRESS
257
258 @property
259 def state(self) -> GameState:
260 return self._state
261
262 def make_move(self, from_pos: Position, to_pos: Position) -> bool:
263 piece = self._board.get_piece(from_pos.row, from_pos.col)
264 if piece is None or piece.color != self._current_color:
265 print(f"No {self._current_color.value} piece at {from_pos}")
266 return False
267
268 legal_moves = [
269 m for m in piece.get_pseudo_legal_moves(self._board)
270 if m.to_pos == to_pos and self._validator.is_legal(self._board, m)
271 ]
272
273 if not legal_moves:
274 print(f"Illegal move: {from_pos} -> {to_pos}")
275 return False
276
277 move = legal_moves[0]
278 self._board.execute_move(move)
279
280 opponent = self._current_color.opposite()
281 in_check = self._validator.is_in_check(self._board, opponent)
282 has_moves = self._validator.has_legal_moves(self._board, opponent)
283
284 if in_check and not has_moves:
285 self._state = GameState.CHECKMATE
286 elif in_check:
287 self._state = GameState.CHECK
288 elif not has_moves:
289 self._state = GameState.STALEMATE
290 else:
291 self._state = GameState.IN_PROGRESS
292
293 self._current_color = opponent
294 return True
295
296 def display(self) -> None:
297 print(self._board.display())
298 print(f"Turn: {self._current_color.value} | State: {self._state.value}")
299 print()
300
301
302 def setup_standard_board() -> Board:
303 board = Board()
304 # Black pieces (rows 0-1)
305 piece_order = [Rook, Knight, Bishop, Queen, King, Bishop, Knight, Rook]
306 for col, piece_cls in enumerate(piece_order):
307 board.place_piece(piece_cls(Color.BLACK, Position(0, col)))
308 for col in range(8):
309 board.place_piece(Pawn(Color.BLACK, Position(1, col)))
310
311 # White pieces (rows 6-7)
312 for col, piece_cls in enumerate(piece_order):
313 board.place_piece(piece_cls(Color.WHITE, Position(7, col)))
314 for col in range(8):
315 board.place_piece(Pawn(Color.WHITE, Position(6, col)))
316
317 return board
318
319
320 if __name__ == "__main__":
321 board = setup_standard_board()
322 game = Game(board)
323
324 print("=== Chess Game Demo ===\n")
325 game.display()
326
327 # Scholar's mate sequence (4-move checkmate)
328 moves = [
329 # White: King's pawn to e4
330 (Position(6, 4), Position(4, 4)),
331 # Black: King's pawn to e5
332 (Position(1, 4), Position(3, 4)),
333 # White: Bishop to c4
334 (Position(7, 5), Position(4, 2)),
335 # Black: Knight to c6
336 (Position(0, 1), Position(2, 2)),
337 # White: Queen to h5
338 (Position(7, 3), Position(3, 7)),
339 # Black: Knight to f6 (trying to block)
340 (Position(0, 6), Position(2, 5)),
341 # White: Queen takes f7 (checkmate)
342 (Position(3, 7), Position(1, 5)),
343 ]
344
345 for i, (from_pos, to_pos) in enumerate(moves):
346 color = "White" if i % 2 == 0 else "Black"
347 piece = board.get_piece(from_pos.row, from_pos.col)
348 piece_name = piece.__class__.__name__ if piece else "?"
349 print(f"Move {i + 1}: {color} {piece_name} {from_pos} -> {to_pos}")
350 success = game.make_move(from_pos, to_pos)
351 if not success:
352 print("Move failed!")
353 break
354 game.display()
355
356 if game.state in (GameState.CHECKMATE, GameState.STALEMATE):
357 print(f"Game over: {game.state.value}")
358 breakCommon Mistakes
- ✗Putting move generation logic in the Board class instead of each piece. You end up with one massive switch statement.
- ✗Not implementing undo on moves. Without it, check detection requires cloning the entire board for every candidate move.
- ✗Using inheritance for color (WhiteKing, BlackKing). Color is data, not behavior. Use composition.
- ✗Forgetting that a move is only legal if it doesn't leave your own king in check, including discovered checks.
Key Points
- ✓Each piece generates its own pseudo-legal moves. MoveValidator filters out ones that leave the king exposed.
- ✓Command pattern on Move allows execute/undo. You need undo to test whether a candidate move leaves you in check.
- ✓Board tracks all pieces by color for fast iteration when checking if any enemy piece attacks the king's square.
- ✓GameState is computed after every move: if the opponent has no legal moves, it's either checkmate or stalemate.