Connect Four
Win detection, move validation, and a depth-limited AI opponent, backtracking and game-state design with a bug → feature → scale arc.
Problem
A Connect Four game tracks a 7×6 board. The starter code has a bug.
Phase 1 — Fix the bug
checkWin() misses some diagonal wins and reports false positives on others. All four directions — horizontal, vertical, and both diagonals — must be correct.
Phase 2 — Feature
Add play(column): reject full columns and out-of-range columns. Then add a chooseMove() for the AI: a depth-limited minimax search with a board evaluation heuristic, so it blocks immediate threats and takes wins.
Phase 3 — Scale
Support configurable board sizes and win lengths (e.g., 4-in-a-row on a 10×8 board). The win check and search must adapt to the parameters.
What interviewers watch
Win detection sweep (each cell, each direction, within bounds) — the most common AI bug is asymmetric direction handling. For the AI, verify it actually uses the depth limit and doesn't hang.