My quest to see all of Tetris | Antithesis

Early in 2026 I was sweating. A few years before, I had made the statement that Antithesis had “beaten” Tetris. We have a tradition that we name conference rooms after games that we have beaten, and since 2021 there has been a room in the office named Tetris. However, my statement of victory had been overtaken by events. As we shall see, teenage gamers had learned how to extend human performance into parts of the game our product had not reached. I made it my side quest to use my free time to catch up to the teenagers. The goal was “rebirth” — running through all the levels of Tetris until the level counter rolled over from 255 back to 0. When this happens, the game returns to the speed and color scheme of level 0 and starts the climb through the levels again. If we could see all of Tetris, surely we could claim we had beaten it. Unfortunately, our exploration was stuck on level 160. I was about to join a new department, and I knew once that happened I would not have time to work on Tetris, maybe ever again. Yet there I was, stuck. But I am getting ahead of myself. I want to say up front that this does have a happy ending, despite a most exasperating resolution of the “stuck” situation. I should start the story at the beginning. If you just want to see what we did in the end, and the weird glitches we found on the way, you can jump straight to Rebirth! Why Tetris? Back in the early days of Antithesis, new engineers would go through an initiation rite: learn our system by using it to play and hopefully beat a game from the iconic 1980s Nintendo Entertainment System. Over time we’ve tackled a lot of classics, including Mario, Zelda and Metroid. When I joined in 2019, I chose Arkanoid, because it was my second favorite NES game. My favorite game, Tetris, had already been tried.1 1 I am happy to say that today we have a conference room named “Arkanoid”. But that’s another story. I had become semi-addicted to Tetris in the 90s when I was flying back from visiting a customer in Europe.

The then-revolutionary in-flight entertainment system had a version you could play at your seat. I enjoyed using spatial reasoning to figure out how to rotate and position a piece mid-flight. Seeing completed rows vaporize as my score increased gave me an immediate sense of accomplishment. Of course, Tetris doesn’t let you stay comfortable for long. Just when you get in the groove, the pieces drop faster. If you make a mistake, like covering up an empty spot with a new piece, you’re now playing defense and having to trade off future health for not crashing out right now. There is no such thing as a finish line: you simply keep playing until you lose. No one gets out clean. (Maybe this is all a metaphor for something.) When we had tried before to beat Tetris we had made progress, but we had not managed to get very far in the game. But the idea of beating Tetris stuck with me, and became a (very) long-running side project. But what does “beating” even mean? Normally at Antithesis, “beating” a game means that we discover a set of user inputs that play the game to a winning conclusion. As Tetris has no win state, defining exactly should count as beating the game is a bit slippery. Our understanding of this evolved along the way (with some help from the teenage gamers). How Antithesis plays games Antithesis plays Tetris in an unusual way, so first I’ll explain how that works. We don’t do the typical kind of tool-assisted speedrun that crafts a set of perfect user inputs from first principles. Nor do we create a robot that knows how to play the game, watches the screen and reacts. Instead, we run smallish trials of random inputs at known starting game states, evaluate the effect each trial has on the game, and remember game situations that we deem to be interesting with respect to a goal. We take advantage of the fact that what happens in a NES game is completely determined by the user inputs it receives, which allows us to be stingy about taking game snapshots. As long as we save every input we have sent to the game, we can recreate an arbitrary game state by starting from the closest snapshot in the state’s history and feeding it the inputs needed to get us to the exact game moment we want.2 2 Our deterministic hypervisor lets you do the same thing with arbitrary programs!

You can exactly recreate any moment from a test execution by replaying the randomness we injected into the system to get there. During a run, this lets us return to interesting places in the programs we are testing. After a run, it lets us spin up a recreation of bug situations so customers can capture data and do what-if analysis. In a typical setup for a test run, one Antithesis fuzzer feeds 32 emulated NES sessions, each loaded with the game we are fuzzing. We host each session with the fceux emulator, and use fceux’s Lua integration to create a harness script that runs the emulator in headless mode.3 3 We use the original unmodified NTSC version of Tetris, from the ROM with MD5 of 0x5b0e571558c8c796937b96af469561c6. For the emulator, we use fceux version “2.2.3 debug”. To create the examples in this post, we generate an fceux movie from the fuzzer inputs, and play the movie with fceux version “2.7.0-interim git”. Inside the fuzzer, we have a component called a “tactic” which generates input for the game we are testing. A second “strategy” component then observes what the result of the input is and guides the fuzzer for what to do next. (See our previous post on beating Gradius for more on this.) To see how this all fits together, it helps to zoom into a single frame. An NES game cycles at a rate of 60 screen updates per second. Each cycle has the following actions: Our harness receives an input byte from the fuzzer from an input pipe. The harness reads the input byte and sends it to the waiting emulator. The emulator processes the input byte, modifying game memory, and generating a new game screen, and then returns to the harness. The harness interrogates the emulator and captures values of specific game memory locations and optionally the new game screen. The results get put on an output pipe that goes back to the fuzzer to process asynchronously. The harness loops back to process the next input. The fuzzer is asynchronous with respect to this loop.

It pre-generates batches of inputs for the harnesses, and observes the returns from the harnesses as they arrive. With that machinery in place, beating a game comes down to two things: Finding the right tactic (algorithm for generating inputs) Finding the right strategy to guide the fuzzer to winning the game. For Tetris, a game with no end, our first thought was that beating it would mean to do as well as the best humans could do. The thing we failed to take into account was all the other humans. Round one: learning My coworker Alex Pshenichkin had already tried getting the fuzzer to play Tetris. He’d figured out the foundations of how to get the current piece layout by reading emulator memory. He used this to calculate our first goodness measure, based on some research he found about playing Tetris. This version took a long time to play because the tactic that generated input created basically random inputs.4 When we took the results of our runs and converted them into a movie, watching the pieces drop was like watching snowflakes caught in a gentle breeze. They would slowly meander down the screen, undulating back and forth, and eventually settle in a random place. 4 The only exception was the button-press to pause the game. We needed that key to get past the start screen, but then never emitted it once game play started. Our strategy measured the board state at each frame, and explored in parallel many diverse patterns of board layout. Combined with the random tactic, this gave us an approach where we were all-in on randomness. In the time we devoted to running this, we never could clear more than a few lines. Alex did amazing work getting the core setup working, but his real job pulled at his time, and he went on to be the key person on the deterministic hypervisor at the core of our product. Tetris would have to sit on the shelf until a global pandemic brought it front and center again.5 5 This is likely the post hoc ergo propter hoc logical fallacy, but being stuck at home did make my mind crave some “fun” work. Round two: naive success In 2020, while we were stuck at home due to COVID, I started work on Tetris as a side project. I wanted to make our tactics and strategy behave more like the best humans did.

Our aim was to beat the game for good by getting past level 29, the point that traditionally defeated human gamers. At level 29 the speed that pieces drop suddenly doubles, from 2 frames per row to 1 frame per row, so that a piece falls the full height of the playfield in about a third of a second. At this speed, the standard method of holding down left or right can’t move a piece all the way from the spawn point to the far edge before it reaches the bottom. So for decades, level 29 was considered unsurvivable: a “kill screen” where the game effectively ended itself no matter how good you were. My new tactic generated input bytes specifically for Tetris. It mimicked what the top players did when encountering a new piece — first rotate, then move left or right to a particular column, then go down-down-down until the piece was placed. I coupled this with a revamped strategy. I took the game board evaluation function from the first attempt, and converted it to an objective function that was designed to run when a new piece was ready to drop. The objective function took into account how tall the stack of pieces was (smaller is better), how far down the board the piece was when we locked it (deeper is better), and how many “bubbles” we left in the assembled mass of pieces, where a bubble is a trapped empty square we can’t fill. More bubbles, more troubles. The strategy we used ran the objective function when game memory told us there was a new piece. With each new piece, we also determined what “strategy bucket” we had reached. A bucket is defined by a tuple made up of: (number of pieces seen so far in the game, column the last piece was placed into). In each bucket, we stored its score from the objective function and a game state we could use to return to that point in the game. When the strategy chose a bucket to explore, the fuzzer loaded the saved game state into an emulator. From there, it invoked the tactic to generate random Tetris moves. We were constantly jumping back in time to interesting game states and trying again. When we landed back in a bucket we had already filled, the objective function decided whether to keep the state we had, or replace it with the newly-discovered one.