Personal
Chess Engine
A playable board with an opponent behind it: move generation, alpha-beta search, and an evaluation function that is honest about how little it knows. It beats me, which was the acceptance criterion and remains mildly annoying.
Move generation is the boring, load-bearing part
Everyone starts a chess engine wanting to write the clever search. The search is a week; move generation is a month, because the rules have more exceptions than anyone remembers. En passant, castling through check, pinned pieces, promotion, the fifty-move rule.
None of it is interesting and all of it has to be exactly right, because a search built on top of a subtly wrong move generator produces confident nonsense.
Searching without wasting the search
Alpha-beta is minimax that stops looking down a line as soon as it proves it cannot beat one already found. How much it saves depends entirely on move ordering: search the best move first and most of the tree never gets visited at all.
So the ordering heuristics matter more than the depth. Captures first, then checks, then everything else, and the improvement is dramatic enough that it changes what depth is affordable.
Correctness before cleverness
I wrote the search first and spent a fortnight debugging an engine that was fine. The bug was in castling. Building the unglamorous layer properly and testing it against known positions would have cost two days and saved twelve.