Optimize Tetris NP-Complete solution with AlphaEvolve
Tetris NP-Complete Problem
Many of us have spent countless hours playing tetris in our childhood! Watching that 4 brick blocks fall into a perfectly created gap and seeing the rows of blocks disappear one after the other gave a different sort of satisfaction. When you lay the blocks down you always wonder if the location is the best one, we often take the greedy approach and place the blocks where they fit without creating holes, without thinking too much, almost instinctively. We do this because we only know about 1 and sometimes 2-3 blocks in the pipeline. Imagine you knew about all the blocks that were coming your way in advance, would you be able to create a strategy to perfectly fit all the blocks so that you could create a perfectly clear board?
Turns out this is actually a very hard problem. It has actually been proven to be NP-Complete! In this blog we will explore how a naive brute force approach to solve this problem can be evolved into a more workable solution using Google AlphaEvolve.
1. Introduction to AlphaEvolve
Heuristic engineering has historically been a labor-intensive craft. Whether designing chess evaluation functions, packet routing algorithms, or game-playing agents, human developers spend weeks manually adjusting coefficients, balancing edge cases, and running trial-and-error experiments.
Google DeepMind's AlphaEvolve transforms this paradigm by merging evolutionary algorithms with Large Language Model (LLM) program synthesis.
Instead of traditional genetic algorithms that rely on brittle random bit-flips or primitive abstract syntax tree (AST) crossovers, AlphaEvolve employs LLMs as intelligent, context-aware mutation and crossover operators. The LLM understands code semantics, proposing domain-tailored improvements—such as introducing non-linear scaling exponents, dynamic progress ratios, and structural heuristics.
Paired with a strict, automated 3-Tier Evaluation Harness, AlphaEvolve systematically validates every candidate program for safety, functional correctness, and empirical performance, driving monotonic optimization across successive generations.
In order to use AlphaEvolve in Google Cloud, you first need to enable AlphaEvolve using these steps.
Tetris Problem Definition: An NP-Complete Challenge
Tetris is deceptively simple. Yet, in 2002, computer scientists Erik Demaine, Susan Hohenberger, and David Liben-Nowell proved that offline Tetris (where the full sequence of upcoming pieces is known in advance) is NP-complete.
Maximizing cleared lines, minimizing board height, or determining whether a sequence can result in a Perfect Clear (a completely empty board with 0 residual blocks) requires exploring a combinatorial explosion of states.
3. Evolving Tetris Solution with AlphaEvolve
3.1 Start with a Naive Solution
Initially we will start with a naive solution where the complexity grows exponentially. If we ran this solution for 50 tetris blocks, it would take billions of years of computation before we come to the solution. I ran the solution and as expected the amount of computation required climbed exponentially. Here are the results of the sample run.
Number of Blocks | Execution Time |
1 | 1.7 ms |
2 | 13.1 ms |
3 | 195.7 ms |
4 | 6.3004s |
5 | 125.91s |
3.2 Running AlphaEvolve with Naive Program as Seed
AlphaEvolve ran through a few evolutionary loops producing an algorithm that was much better than the original naive solution. Here is the runtime comparison of the naive solution and the AlphaEvolve solution.
N (Blocks) | Naive Search Time | AlphaEvolve Runtime |
N = 1 | 1.06 ms | 1.45 ms |
N = 2 | 14.10 ms | 21.55 ms |
N = 3 | 250.97 ms | 165.67 ms |
N = 4 | 9.12s | 418.84 ms |
N = 5 | 125.91s | 1,164.92 ms |
N = 6 | ~1.7 hours (Projected) | 679.42 ms |
N = 7 | ~1.6 days (Projected) | 947.97 ms |
N = 8 | ~37.4 days (Projected) | 953.45 ms |
N = 10 | ~54.2 years (Projected) | 1.29 s |
N = 12 | ~28,700 years (Projected) | 1.68 s |
N = 15 | 3.49 × 10⁸ years (Projected) | 3.48 s |
As it can be seen from the above table, AlphaEvolve was able to find a much efficient solution that cut the time from prohibitively long to just a few seconds.
AlphaEvolve made a few changes in the heuristics that resulted in a huge pruning of the search nodes. The key changes made are highlighted in the table below.
Improvement Factor | Naive Brute-Force Solution | AlphaEvolve improved heuristics | Performance Benefit |
Feasibility Testing | Attempts all paths before determining a Perfect Clear (PC) is impossible. | Runs O(1) divisibility (40 mod 10 = 0) and checkerboard T-piece parity checks. | Instant fail-fast: Skips entire search trees when PC is mathematically impossible. |
Search Space (Fallback) | Full breadth-first or depth-first search exploring every permutation. | Beam Search keeps only the top states at each step. | Drops complexity from O(B^N) to O(N * W * B) (≈ 36,000 evaluations max). |
Subtree Pruning | Explores moves even if they leave dead space or stack too high. | Zero-hole rule (count_holes() > 0) & strict ceiling cutoff (max_height = 6). | Prunes over 95% of branches within the first 1–3 piece placements. |
State Caching | Re-evaluates identical board layouts reached in different piece orders. | Hashes boards into integer bitmasks (to_row_tuples()) via transposition tables. | Eliminates redundant path calculations for commutative placements. |
Piece Rotations | Blindly tests all 4 orientations (0°, 90°, 180°, 270°). | Deduplicates identical shapes via spatial coordinate signatures. | Reduces branch factors (e.g., O-piece: 1 rotation; I, S, Z: 2 rotations). |
3.3 AlphaEvolve Configuration & Parameters
To guide AlphaEvolve's optimization process, we defined a structured parameter space spanning state evaluation, heuristic weights, and evolutionary search controls.
Category | Parameter | Value | Description |
Run Settings | programmingLanguage | "python" | The language of the mutated heuristic scripts. |
maxPrograms | 100 (default) | Maximum limit of candidate programs to generate throughout the campaign. | |
concurrency | 2 (default) | Number of evaluations allowed to run in parallel. | |
maxDuration | "86400s" (24 hours) | Absolute run-time limit for the experiment. | |
idleTimeout | "1800s" (30 minutes) | Timeout threshold if no active task queue activity is present. | |
Generation Settings | context | "Optimize the evaluate_move heuristic function for Tetris board states..." | Direct instructions to the LLM defining the objective metrics (cleared lines, holes, bumpiness, heights, 4-line clears). |
includeFullProgramInPrompt | TRUE | Forces the system to supply the entire candidate script context to the generator LLM rather than a snippet. | |
models | [{"name": "gemini-3.5-flash", "weight": 1.0}] (default) | Specifies the generative model(s) and their probability allocation weight. | |
Evolution Settings | paretoSamplingProbability | 0 | Probability for selecting parent solutions based on multi-objective Pareto-frontier criteria. |
4. Evaluation Process: A 3-Tier Multi-Objective Architecture
Evaluating candidate game-playing heuristics presents unique challenges in safety, compute costs, and reward alignment. To solve this, AlphaEvolve uses a 3-tier hierarchical validation harness paired with board topology simulation and a monotonic fitness function.
4.1 The 3-Tier Validation Pipeline
- Tier 1: Static AST Analysis & Security Screening: Python's ast module verifies syntax, enforces a strict whitelist (prohibiting I/O, non-deterministic calls, or global mutations), and guards the evaluate_move signature. Failures are rejected immediately (Fitness = 0.0).
- Tier 2: Functional Contract & Invariant Validation: Runs deterministic smoke tests—including finite float checks, extreme board configurations (empty, critical heights, discontinuous surfaces), and monotonicity checks—to weed out invalid heuristics before simulation.
- Tier 3: Quantitative Simulation Harness: Evaluated candidates steer a high-throughput Beam Search (k = 200) across diverse test scenarios (N = 5 to 15) on a bitboard representation to prune suboptimal branches.
4.2 Feature Extraction & Monotonic Fitness Formula
Key topological indicators are extracted to compute a single scalar score:
- Average Lines Cleared (L_avg): Primary game progression.
- Perfect Clears (N_PC): Full board wipes.
- Survival Rate (R_survival): Completed benchmark scenarios.
- Buried Holes (H_holes): Trapped empty cells (heavy penalty to prevent degenerative play).
- Surface Bumpiness (B_bumpiness): Skyline smoothness.
- Max Column Height (H_max): Peak block height.
These metrics are unified into the Monotonic Fitness Formula:
Fitness = (150.0 * L_avg) + (500.0 * N_PC) + (50.0 * R_survival) - (25.0 * H_holes) - (1.5 * B_bumpiness) - (1.0 * H_max)
- Anti-Degeneracy: The -25.0 weight on buried holes ensures long-term structural integrity over greedy line-clearing.
- Perfect Clear Super-Bonus: The +500.0 bonus rewards exact board resets.
5. Conclusion & Takeaways
Google DeepMind's AlphaEvolve represents a transformative leap in heuristic engineering by combining LLM-driven program synthesis with evolutionary optimization. As demonstrated by the Tetris case study, AlphaEvolve efficiently navigated an NP-complete search space, transforming a computationally prohibitive brute-force approach into a highly performant heuristic that reduces evaluation times from years to seconds. By eliminating manual trial-and-error and automating domain-tailored algorithm design, this framework opens exciting possibilities for solving complex, multi-objective optimization challenges across software engineering, AI design, and operations research.