Current fastest TAS run (22.43 sec)
Hey everyone, thanks for watching the Sprint TAS! I'm mat1jaczyyy, and as we're smashing the limits of Puyo Puyo Tetris (PPT), it might not be entirely intuitive if these TAS runs are legit or not. How does one achieve all these Perfect Clears (PCs) so fast? How do you get the pieces you need? Why do the PCs instead of doing normal Tetrises? I'll try to explain as much as possible here so you can understand what happens in the video.
In Sprint, the goal is to clear 40 lines as fast as possible. PPT employs a lot of delays - line clear delay, piece entry delay, hold delay, etc. Most of the logic that goes into constructing the ideal Sprint is minimizing these delays to minimize time.
The major timesave not only in TAS runs, but also RTA runs is the Perfect Clear. The line clear animation for a Single takes 40 frames (40f), a Double or Triple 45f, and a Tetris 50f. However, doing a PC doesn't require us to wait for the animation to resolve, rather we can start placing immediately (0f). So, stacking a PC instead can save up to 50f (0.83s) if we clear it with a Tetris. Clearing with lower lines still saves time, because the lower clears take less time to resolve than a Tetris that would be done for the respective 4 lines. Softdropping is also not viable because it is very slow in Sprint.
A special timesave is the final PC. If the last 4 lines are cleared with a PC, then the run ends having used exactly 100 pieces, which is the lowest amount required to finish. Using more is a waste of time, because we have to stack more pieces than required to finish the run.
To get all those PCs, we need an extremely specific set of a 100 pieces. This set should also require the least amount of holds, ideally 0. Tetris uses a 7-bag randomizer, which means you always get a different permuted bag of 7 different pieces for your Next queue. This slightly limits the freedom we have in selecting which pieces we get, but is not a major issue for routing.
The bigger issue is that the Random Number Generator (RNG) in simply does not work in a way is impossible to manipulate mid-game. RNG is a 32-bit value (unsigned int) whose roll function is RNG(x) = x * 5D588B65 + 269EC3. The game's RNG function loops consistently and all 2^32 seeds are uniformly distributed in one loop. The global RNG is rolled every game frame (which ticks only when the game itself is active, and not any of the menus we get beforehand - due to this you will always start the first game in your session with the same pieces), and a starting RNG value is taken as the game starts.
This value (piece RNG) is stored for our player outside of the global RNG, and used for piece generation. The game uses the Fisher-Yates method for generating a random bag permutation, which rolls our starting RNG 7 times when a new bag is required. The game stores exactly 2 future bags in memory for displaying in the Next queue preview. No other factors than requiring a new bag roll our piece RNG value, so there is no way to manipulate it outside of selecting an initial RNG value to work with. This also means that we can consistently predict as many pieces as we want, because the RNG remains unaffected.
Since our RNG value is 32-bit and not manipulatable mid-game, this means we can choose from 2^32 initial RNG seeds and thus that many sets of 100 pieces to work with. 100 pieces contain 14 full bags and 2 pieces from an incomplete 15th bag. As a full bag has 5040 different permutations, and the incomplete part of the bag 42 different permutations, this means the total number of different 100 piece sets is 2.866*10^53, which is much larger than the 4.295*10^9 sets we have available with the game's RNG seeds.
Routing an imaginary, made up ideal set of pieces is hopeless, because the rough chance of a specific set existing in the game is 1.5*10^-44. Instead, we have to create a sort of "seed finder" that would run through the entirety of the game's RNG seeds in hopes of finding a seed that meets the ideal requirements.
Ideally, we want our run to have as many Tetris PCs as possible, which save 50f compared to a normal Tetris. Right below it on the priority list are Single to Triple PCs, which save 10f. After that we have Double to Double and Triple to Single PCs which save 5f, and then finally normal Tetrises. The main goal is to find an RNG seed that fulfills as many of these requirements as possible.
To facilitate this I devised a directed graph system that represents piece dependencies, in which nodes represent pieces and hold one bit of information - whether they have been stacked yet or not. When stacking Hard Drop only, we always depend on certain pieces to be placed before we are allowed to place a certain piece. A graph where a piece connects an edge to all the pieces that need to be stacked before that piece, can easily be checked for if it can be stacked by checking if all the required pieces have been stacked already. This gives us a base for searching through bags, and thus RNG seeds - we can discard a seed if a piece cannot be stacked due to depending on another piece.
The graph should be constructed in a way that it represents stacks that allow for as many timesaves with PCs as possible, and a convenient way is to split it up per bag because it allows for easier indexing and tracking of the hold between bags, but most importantly because we can offer different stacks and solutions per each bag by allowing the search to take multiple pathways after finishing a bag, increasing the amount of bags that will get farther in the graph traversal.
Once the graph is constructed, we test all existing RNG seeds and 100 piece sets in the game against it, and have the program return all seeds that made it to the end. We can then use the found seed in game, and execute the run by looking back at the graph and relevant stacks. The source code of the program can be found here.
While I had no trouble reverse engineering the game's RNG, I am not too involved into the science behind Perfect Clears, so I asked expert PC researchers Galactoid and cosin307 to help me construct a route. As a start, we used the research notes from Galactoid's 10 PC guide at to find already known patterns for each PC bag with solutions that clear all 4 lines of a 4x10 area with a Tetris.
Theoretically, we realized that the maximum number of PCs ending in a Tetris is 7 out of 10, which can be easily proven with the concept of T piece parities and bag timings. By noting that you need either an even number of T pieces (or zero T pieces) to do a Tetris PC, and by knowing that only 1 T piece comes every 7 pieces, you can limit the number of PC Tetrises to just 7. Doing a PC with 1 T piece would require clearing a line to fix the parity, which is what we do for the PCs that cannot be done with a Tetris (2nd and 7th). Note that we only used vertical T placements throughout our search, and cosin307 has recently (but too late) realized we can in fact get all 10 PCs with Tetrises by using some horizontal placements. This is where an improvement and additional timesave might be possible in the future.
Galactoid found a route for all 100 pieces using his guide and some freestyle PCs that has 7 out of 10 PCs ending in a Tetris, simply by being attentive in the usage of T pieces - making sure some bags have exactly 2 T pieces or 0 T pieces, by holding the T to the right PC where it should be used. I converted it manually into the graph that we will feed the seed finder with, while generating variations such as mirrored solutions or inverted solutions that allow for more bags to pass through. I also added a bunch of my own, such as the 1st PC grace opener.
However, even with the graph search in place, the odds are still stacked against us, and only 4 best seeds in the game managed to reach 7 PCs total (out of which 5 are Tetrises). There was no more manipulating the order of pieces after this - we had 4 leftover sets of 30 pieces to work with for the last 12 lines of the run. To make at least 7 Tetris PCs and reach the full potential of the route, there should be at least 2 of them in last 12 lines, as Galactoid's routes finished the first 28 lines with 5.
cosin307 and Nilgiri306 then found a good setup for the final 12 lines - at first, they tried finding solutions for all of these being Tetris PCs, which would make 8 Tetris PCs in total, but because of the parity issue with T pieces described above, they weren't able to find it. However they were able a single seed that covered 7 Tetris PCs, 2 Single to Triple PCs and 1 Double to Double PC, saving a total of 370 frames worth of line clear delays compared to a 9 normal Tetris and 1 Tetris PC ending run. Finally we optimized the stacking placements to require the least time to input.
Throughout all of this, knewjade's PC solution finder was used to derive solutions, and we'd like to thank him for creating the program as it saved us a lot of manual work.
Now that we've found the ideal RNG (whose value is A353F9A4), it's time to tell the game to make use of it. To set the initial RNG, we would directly modify it to a desired value in the register ecx right before executing the instruction at address 0x141574208 (imul ecx,ecx,5D588B65) using Cheat Engine's debugger when the game rolls it for the first time while generating the first bag. The same effect would be achieved without hacks by letting the game run until we reached our seed (since the RNG loops uniformly), but this is not too practical since it could take anywhere between 0 and 4.295*10^9 frames of waiting (instant and 54 years).
Now that the game has started with the RNG seed and 100 piece set we found, all that's left is to stack it. The game is paused and resumed manually by suspending and resuming the process, not using the in-game pause. This allows me to write a program that pauses the process based on a memory read, so we can always frame perfectly suspend the game when a piece spawns. We reused lots of Zetris' code for doing the inputs, namely the input engine (using a virtual Xbox 360 controller). By simply replacing the AI decision-making call from Zetris with a dialog presenting us with a sandbox that shows the current state of the game, it's easy to experiment around and do all the correct inputs very quickly and optimally. The dialog takes the decision from us (by having us place the piece in the sandbox), and then passes it to Zetris' input engine which resumes the game and places the piece.
We already know exactly what the stack should look like and what the fastest inputs for any piece placement are, but we must still care about minor timesaves come from optimizing movement - this is mostly trial and error, and includes choosing between right side well or 6-3 stacking and optimizing for least holds (the first hold has a 10f delay while all subsequent holds have a 2f delay).
Another optimization that cuts the time down is hard dropping on the same frame as rotating, as the game processes inputs in the order: Rotation, Hard Drop, Movement. I had also missed that you can start inputting movements after holding immediately, instead of having to wait one frame. These improvements are also something Zetris' input engine had been missing and are improvements to the bot as well. All that's left is to do the run, and save the replay.
Our TAS is useless if it is not able to be easily replayed. Due to our hacky RNG injection, the game still saves the replay with the RNG as it was initially before the injection. This results in the replay playing incorrectly, and topping out within just seconds of playback.
The game stores the replays inside the binary save file (data.bin), where all the other information about your game is stored (such as rating, stats, etc). With some reverse engineering about how the game overwrites RNG from a replay, I was able to find the offset in the replay where the RNG value is stored. However, there are precisely 1987 RNG calls that happen before the piece generation, presumably to shuffle the RNG around a bit without a real purpose. So we must roll our RNG back exactly 1987 times and replace the RNG value in the replay with that one.
Inverting the RNG function is not easy because it relies on major overflows to generate randomness, so I wrote a quick script that iterated through all of the game's RNG and remembered 1987 previous values, printing the earliest one remembered when we hit our injected value.
Opening the file up in a hex editor and modifying this offset to that desired value allows the replay to play correctly on any unmodded game. Note that elsewhere in the save file, a checksum is employed for making sure no unauthorized modifications are done, but the check doesn't seem to exist for replay sections, which made doing this a lot easier.