Tetris Solver
Adaptive beam-search algorithm that solves Tetris move sequences 80× faster than a fixed-width baseline, with no loss in win rate.
The Problem
Solving Tetris optimally is NP-hard. The state space explodes exponentially with lookahead depth. A fixed-width beam search wide enough to solve hard games was far too slow on easy ones. The challenge: make it fast on average without failing on hard cases.
Architecture
- →
Decoupled engine layer: drop, place, clear, score (no solver logic in the game simulation)
- →
Adaptive (progressive) beam search: tries widths 1 → 5 → 20 → 100, stops the moment a solution is found
- →
Heuristic scoring: lines cleared (+1000/line), column height (−51), holes (−35), bumpiness (−18)
- →
Piece sequences follow the official Tetris 7-bag system; all 7 tetrominoes with valid rotations pre-loaded
- →
Simulation mode with Python multiprocessing to run hundreds of seeds in parallel
- →
Frontend: Flask, HTMX, Alpine.js, D3.js for SVG board rendering
Technical Challenges
- →
State space explosion: with lookahead the number of possible boards grows too fast to search naively
- →
Tuning beam width thresholds: too narrow misses solutions, too wide is slow
- →
Balancing heuristic weights without overfitting to specific board configurations
Results
- ✓
80× speedup: 100 games in ~2.4s vs ~194s with a fixed width-200 beam, same win rate
- ✓
Easy games solved instantly at beam width 1; hard games scale up as needed
- ✓
Parallel simulation mode can evaluate hundreds of seeds concurrently
