This isn't an exploit of a specific PRNG algorithm, just the constraints specific to Tetris-- 1 of each piece is put into a bag, and pieces are chosen from the bag at random. The bag is refilled when empty.
The current article title ("Playing Tetris forever by exploiting the PRNG") is indeed misleading. It would be better titled "...by exploiting piece generation constraints in recent versions."
For what it's worth, a similar pattern could be made without Hold, but it would be far more complicated. The singularly important gameplay element that allows patterns like this is the "bag" style randomizer.
>The following outlines a method of playing forever given the following conditions, which apply in many Tetris products since 2001:
Ah this explains why things didn't seem right to me. I played hundreds of hours of Tetris as a kid and I would have noticed this statistical pattern, but since my games were pre-2001, I never saw this piece pattern to exploit.
Disclaimer: I'm a longtime Tetrisconcept.net member and thus a Tetris nerd.
As pointed by Scaevolus, this isn't exploiting the PRNG per se but rather the algorithm that distribute the piece, or in the Tetris jargon "the randomizer" (also "random generator").
The subject of the randomizer is such an interesting one to study.
Very early in the history of Tetris the developers have noticed that the distribution of similar piece was detrimental to the gameplay. Not because necessarily of the famous "get enough S and Z and then you automatically die" effect (that's frankly such an improbable event that you'd better try to do be struck four consecutive time be a lightning bolt), but because it often lead to the creation of a shitty stack.
So they implemented technical measure to correct that. IIRC, Nintendo's version of Tetris for NES and Gameboy were the first to do that (it's a direct detection of repetition: if PieceGenerated == lastPieceGenerated, then reroll for another piece).
Then as time went on, more elaborate system appeared
My favorite one is used in the TGM series [0] : it keeps memory of the 4 most recent pieces and denies their distribution if the next generated piece is in that history.
There one remarkable thing in its design is that is still distribute the piece if the "rolling of a dice" fails more than 4 times.
By doing that, they managed to have a randomizer that is both reliable (gives enough variety in the distribution of piece so to not be screwed) and unpredictible. It is a very good thing for such a single player focused game.
The "7-bag" system that is assumed to be used in this article is a mandatory gameplay element for all modern official Tetris (meaning, as far as I know, you cannot release a game called “Tetris” if you don’t use it).
As sp332 pointed out, this randomizer uses a metaphoric “bag” throughout which you take all the 7 pieces that it contains. Once you’ve run out of piece, you put them all back in and you repeat the procedure.
It a simpler system to understand, but it has some flaws.
The main one is that depending how you connect the "seam" of the bags, you can get some unwanted repetitions (e.g finish Bag3 with a T piece and start Bag4 with a T piece as well). This phenomena is even amplified when variant of the 7-bag algorithm is used such as in (now deceased) Tetris Online Japan, where they have a 8 bag strategy or in the New Tetris ("new" here being 1999, and being the N64), where they use a 63 bag (that was actually wanted in order to build 4x4 golden square, which is the gimmick of that version).
One criticism is that it is 100% predictable: you will get any given piece in at least 14 pieces generated. Since the officiel Tetris nowadays seems to relies on multiplayer gameplay (see also: T-Spin and its offensive bonus), having a 100% predictable randomizer could be actually a strength by adding a layer of "fairness".
Further reading: there's an awesome thread [1] in Tetrisconcept.net that talk about randomizer theory. It's a old though, and some image link are dead. Fortunately, archive.org can help us restore them. Two highlights are: A comparison of different randomizer in term of predictability [2] and reverse engineering a randomizer [3] with a graph that gives the probability of having a given piece in exactly X piece [4] or in at least X piece [5].
If anyone has weeks or months to kill on a totally awesome but utterly useless side project, someone should try to use an emulator to see if it's possible to actually exploit the PRNG on the NES version. I.e., using the fact that you can control the low bits of button press timestamps (or whatever entropy source the game's random number generator uses), see if there's some input pattern (together with cycle-precise input timings to get the PRNG to deterministically do what we want) that creates a fully eliminable set of pieces while also returning the PRNG to its initial state, allowing the sequence to be repeated indefinitely.
You could do this on any version, but the solution would probably be hardware- and implementation-specific; I just mention the NES version because AFAIK it's regarded as the most "authoritative" version.
NES might not be a good version for such a project, as most of the time would likely be devoted to working around bugs that start cropping up as you play far beyond the Level 29 "kill-screen." NES was never intended to be humanly playable beyond that point, so weird things start cropping up as you progress that can cause strange behavior or lock up the game.
It could still be possible, but you'd have one more thing to reverse engineer beside just the randomizer. The game does eventually loop back to Level 0 if you get through all the bugs in "the outlands," so I guess as long as you start your game there and are able to manipulate the RNG properly then it may be feasible. The RNG is a LFSR with 32,767 positions, and the selection method is also dependent on the previous piece dealt (starts empty) and number of pieces dealt since power-on (stored in a byte).
(EDIT: There are also ways to indefinitely prolong entry delay via pause cycling. Actually, scratch that, you could even just pause a bit at the end and wait for the proper frame, assuming the other variables are properly aligned. That almost seems a bit unfair though, heh.)
The 1988 Sega arcade version might also be good for such a project. What NES was to North America in terms of being an authoritative "classic" version, Sega Tetris was to Japan. It fills an array with 1000 pieces at the start of each game, so creating some sort of looping pattern would be very possible there.
There's a whole bunch of Tetris TASes (tool-assisted speedruns) available on TASvideos[1], including console-verified plays of the NES version. No infinite plays, though, but luck manipulation is already used in the existing runs.
My brain confused Tetris with Pac-Man, the latter of which is impossible to play after level 255, and I worried this was a glitch to get past that barrier, which would've probably meant the death of poor Woz from unending Tetris playing.
Assuming an infinite series of random tetris blocks, any finite pattern occurs, including one of alternating z- and s- blocks. I don't see how the holding mechanic saves you from this. Anyone care to share some insight on this?
The other crucial factor is the 7 Bag randomizer. Pieces are dealt in shuffled sets (or "bags") or seven pieces. The maximum length of alternating S/Z in that case would be four -- xxxxSZ SZxxxx, at the head and tail of adjacent bags.
i worked on an official tetris game, and so i've had the chance to pour over the official spec. it's been a while, but i believe the official rules for marathon don't allow you to play forever. so, in trying to play forever, you pass up higher scoring moves and then you're cut off at the end of level 19 (again, that's iirc). in multiplayer, trying to play forever is a great way to lose.
the official tetris rules are a thing to behold. i just wanted to throw in my 2 cents worth to keep people from thinking this is an exploit for such an amazingly refined game.
there are modes of tetris that i've played that go to level 20, which means the moment the piece is spawned it's on the floor. but because of that limited maneuverability, i don't think you'd be able to use this strategy very well.
You are correct that it is not optimal play. What it is is a lot more interesting than what it isn't: it's a clear demonstration that survival is trivialized with the "7-bag" random generator. Tetris games used to be enjoyable to play for survival, and that is lost in recent games.
Regarding extreme speeds, you make a good observation. This pattern cannot cope with pieces spawning on the floor. That said, I 100% believe it is possible to construct such a solution.
But the existing pattern stands as something to remind people that Tetris used to be fun without extreme speeds or awareness of scoring gimmicks.
For anyone who doesn't know: I'm not big in the Tetris scene, but I do play a lot of a famous game called TGM2P. colour_thief is pretty famous around the Tetris scene for being one of the few Western Grand Masters around.
colour_thief: I'd love to talk "offline" with you sometime, is there an email I can reach you at?
Which one ? I'm interested :) . There's very little available information on the creation process of a Tetris game (well, publicly at least).
20G gameplay (i.e. where the piece spawns on the floow)) is definitely an issue, but I think that using (or rather: abusing) the Tetris Guideline very lax rotation system and "climbing" potential[1] you may be able to reach a sufficient mobility of your piece so you can place them wherever you want.
it was a port of tetris party to the xbla that got cancelled by the developer a couple weeks before alpha. that was the heartbreak that convinced me to get out games.
with 20g the big difficulty is when you build yourself a wall, say a single I standing upright on the floor, a couple spaces from the left side of the playfield.
now, because this is 20g, it's impossible to fill the gap on the left without first filling the gap to the right. it's true that you can move around really for as long as you like, with only the rare exception (i'm not sure, for instance, if it's possible to spin out of a spot you t-spinned into), but the problem is that it's all too easy to limit the playable area on the board. actually, i think it's unavoidable.
Ah, as long as the generator of pieces has a couple properties, this will always work. I find this interesting, mostly because if the generation of pieces is truly random, eventually you will lose; a sufficiently long alternation of S and Z tetrominoes cannot cleanly tessellate.
FTA: Because the random generator provides strings of bags containing each of the 7 pieces in a random order, it is possible to construct a strategy around the relatively small variation, with looping patterns.
There is also a variant of Tetris called Bastet, which always gives you the most unhelpful possible piece :)
Not always. When the well consists of mountains and valleys perfect for fitting S/Zs into, Bastet will deal you an O (square).
Though it is possible to get the best of Bastet: its algorithm for determining the worst possible piece works by attempting to drop every piece straight down from all possible horizontal positions, and does not take sliding maneuvers into consideration. Taking advantage of this, you can create a large overhang at the top of the well, then play by building the majority of your stack under it.
> I find this interesting, mostly because if the generation of pieces is truly random, eventually you will lose
That's correct, but Tetris specifies that pieces are not chosen using a sequence of random pieces selected with equal probability. Instead, it uses "selection without replacement".
Think of it as you get one of each piece and stuff them in a bag. Pull a piece from the bag. That's the next piece. Do not put it back in (hence "without replacement"). Repeat until the bag is empty then refill the bag.
