Perfect Tetris

Features

• Returns a single solution instead of all possible solutions
• Supports any rotation system (6 are available by default)
• Optionally select piece to save in the hold slot
• Specify minimum height of perfect clear to find
• Input and output in fumen format
• Available as a Zig package

Testing & Benchmarks

I tested Perfect Tetris by searching for PCs on all the 57,750 2-line and 79,516,080 4-line PC queues, and the number of solvable queues matched up with the numbers calculated by other people online.

The benchmark results below are agregated over 200 consecutive PCs with a 7-bag randomiser:

Most PC sovlers can only return multiple solutions, and thus have significant latency. The fastest PC solver I could find online was multi-threaded and still multiple times slower than Perfect Tetris.

TL;DR: Perfect Tetris is blazingly fast.

Background

This project is part of my (now somewhat abandoned) goal of making the strongest Tetris bot.

Originally, I wrote a brute-force backtracking perfect clear solver in C# so that the bot would not need to learn how to perform perfect clears by itself. The playfield and tetrominoes were represented by bitfields and some basic optimisations were made, but it wasn't very fast, usually taking 1 to 2 seconds to find a single solution. For a bot operating at 0.33s per piece, this meant it usually didn't have a solution.

I wrote another solver (again in C#) that modeled perfect clears as an exact cover problem, and solved them with Knuth's Algorithm X. The time to first possible solution was much faster. However, while I managed to model placing tetrominoes and line clears, I'm pretty sure there's no way to add path finding constraints to the exact cover problem.

This means that many possible solutions are checked and discarded, increasing the runtime to roughly the same as before. Futhermore, my code for checking if a solution was possible based on the current rotation system was buggy and ended up being too strict, and perfect clears which could previously be solved became unsolvable.

After re-writing the engine in Zig, I set out to make the fastest solver that:

1. Returns the first solution (most solvers return all)
2. Is single threaded (more CPU available to the bot)
3. Has no large pre-computed tables
4. Minimises memory usage (this correlates with speed)

Implementation

Check out my blog post for more details.