7 ms·

A history of Tetris randomizers (2018)

120 points by Impossible 7y ago

evilotto 7y ago
Maybe not an "official" tetris game, but the the BasTet randomizer is worth a mention - it tries to give you the worst possible block at all times. >:) http://fph.altervista.org/prog/bastet.html http://fph.altervista.org/prog/bastet.html
- wwwhizz 7y ago
  Ohh, that's evil :D
  - needle0 7y ago
    Bastet's randomizer can be defeated by creating a huge overhang near the top of the playfield, then building your actual stack far below it. The evaluation algorithm works by trying to drop every piece in every horizontal position, and choosing the piece that fits the worst, but it only tries dropping pieces straight down and doesn't take sliding or navigating underneath overhangs into account.
    - lalaithion 7y ago
      Hatetris, then: https://qntm.org/files/hatetris/hatetris.html https://qntm.org/files/hatetris/hatetris.html
  - de_watcher 7y ago
    The tetris that's comes with the Debian/Ubuntu distribution has that "unfair mode" flag.
- digibo 7y ago
  There is also HATETRIS https://qntm.org/files/hatetris/hatetris.html https://qntm.org/files/hatetris/hatetris.html
maaaats 7y ago
> The 7-bag has a consistent piece output, making it more predictable. It’s easy to know where in a bag you are, and when a piece you need might come. Because of how predictable this random generator is, it’s actually possible to play forever. Overall it’s a silly system that makes you wonder how it ever became the official randomizer. I actually like the bag one, knowing where in a bag you are gives an edge, and thus it adds an extra dimension to the game I feel.
- taneq 7y ago
  Wouldn’t you want the game to be indefinitely playable regardless of RNG? Otherwise as player skill increases it tends towards a game of chance, not skill.
  - PetitPrince 7y ago
    I'm assuming solo play: Playing infinitely in Tetris means repeating a pattern over and over again. I would suspect that transforming Tetris so that it is universally infinitely playable (probably by somehow erasing the fact that an infinite SZSZ is a death sequence) would lead to a game where the optimal play is also to repeat a pattern over and over game. It would be indeed a game of skill but would rob the player out of all creativity and agency. Not a very fun game at the end. But I think that proving that such game is infinitely playable is a hard (np hard ?) problem.
    - taneq 7y ago
      > Playing infinitely in Tetris means repeating a pattern over and over again. Not necessarily - you could define an infinitely long non-repeating sequence (although it will have arbitrarily long repeating sequences inside it) which would still not contain any certain-death sequences.
- PetitPrince 7y ago
  This is true for multiplayer game where playing knowing more about the system can give you an edge against someone else. As said it the article: >> The clumsy 7-bag is unnatural feeling, but allows for many building strategies to be consistently viable. And consistency is one very important component of multiplayer games. However for solo play where you end up playing at 20G, the seam problem (repeat of SZSZ) can wreck your game if it happens when you have an unfavorable shape of the stack and/or if you get caught up by the lock delay. for the non-initiated: the piece spawns directly on the stack, on you have only a short time to react and place you piece
spbaar 7y ago
Not listed here is Tetris the Grandmaster 2. TGM2 hits the sweet spot between tgm1 and tgm3 in terms of predictability from the perspective of many fans. It increases the number of rolls to avoid dealing a piece in the 4-piece long history from 4 to 6. Essentially, it decreases the odds of a "history duplicate" from ~10% to 3%. With a 1 piece preview, it encourages a very unique type of planning, where you know what piece you need to prepare for immediately (at high speeds this means holding inputs before it even enters the play field), and also know with almost certainty the next piece is going to be 1 of 4 pieces. Unlike bag systems where the duplicate chance is 2% every 7 pieces here it's only 1% constantly, and the chance of drought is also much lower than bag. The chance of a 10 piece drought for I pieces is almost 0, but you're basically guaranteed to have a random unpleasant drought of 11-13 pieces in a long enough bag7 game. This strongly encourages you to use the hold mechanic strategically for safety, breaking flow and speed. This may all seem academic, and it is very important for the type of high speed games tgm is, but it really is the biggest thing I miss playing modern tetris games. Barring other gimmicks, you build and plan the exact same way in every modern tetris game. With the ever present hold mechanic to switch out a piece, you don't even need multiple piece previews that some new games give you. Consider, after playing 3 pieces, you know with certainty the next 4. With the hold plus 1 piece preview, you spend over half your time in the second half of the bag knowing the next three pieces.
- sverona 7y ago
  TGM2 doesn't have a hold.
  - simonlc 7y ago
    In the first paragraph they are talking about IRS, not holding pieces.
simonlc 7y ago
One randomizer I left out of this article (for the sake of brevity) is the Game Boy's version. It has much more bias as detailed in the post below. According to The Tetris Company founder it was also a last minute addition to the game. When they were testing a late build by Nintendo, it had a fixed sequence or something like that. So Nintendo flew in some devs to where Henk was, and over the weekend they programmed this new randomizer. https://tetrisconcept.net/threads/randomizer-theory.512/page-9#post-51035 https://tetrisconcept.net/threads/randomizer-theory.512/page...
- ginko 7y ago
  It seems weird that they leave out the GB version of all things since it's probably the most popular version of Tetris by far.
- Sniffnoy 7y ago
  Oh yikes it's not left/right symmetric! Do you have a direct description of the algorithm? Extracting it from those forum posts seems a bit difficult.
  - pixelbath 7y ago
    http://harddrop.com/wiki/Tetris_(Game_Boy)#Randomizer http://harddrop.com/wiki/Tetris_(Game_Boy)#Randomizer
    - Sniffnoy 7y ago
      Thanks! To repeat it here: we assign each piece a piece a vector of 3 bits; thinking of these vectors as numbers from 0 to 7 (or rather 0 to 6, since 111 is unused), the pieces go in the order (L, J, I, O, Z, S, T). Note that this assignment is not left-right symmetric; there's no particular relation between a piece and its mirror image. Like, L is 000, but J is 001; and Z is 100, but S is 101. That seems like kind of a dumb mistake -- it would've been easy enough to maintain symmetry. (As just one example among the 24 possible ways (assuming 111 must be kept unused), one could have used instead (O,J,I,Z,L,T,S).) Anyway, each turn you pick one of these at random, and you look at the last two pieces; let's call these previous_1 and previous_2. If -- considering pieces as their sets of 1-bits -- we have both that previous_1 is a subset of previous_2, and that the picked piece is a subset of previous_2 -- we reroll. After the third try we just take the piece no matter what. Note that this means that there are some weird interactions between the previous two pieces. Like, if previous_1 is not a subset of previous_2, then we won't reroll no matter what piece we picked, so the new piece will be totally random. But if it is, then we may or may not reroll. Definitely pretty weird. Have to wonder how on earth this was thought up...
ArtWomb 7y ago
Thanks for posting. I love research like this ;) Reminds me of a similar result in which "locally noisy" bots inserted into human coordination games can yield a positive outcome! https://www.nature.com/articles/nature22332 https://www.nature.com/articles/nature22332
bjourne 7y ago
There is actually a "Tetris Standard" written by Colin Fahey which mandates that tetrominoes should be drawn from a Bernoulli distribution. https://www.colinfahey.com/tetris/ https://www.colinfahey.com/tetris/ "When a piece is spawned, the type of piece is selected using the following algorithm: pieceIndex = 1 + (randomInteger % 7); // 1..7 Because there is a constant p (= 1/7) chance of selecting a specific kind of piece, and all pieces of the same type are indistinguishable, the probability of having exactly k pieces of a specific type after n trials follows a Binomial distribution" However, the standard isn't adopted by all. A competing set of guidelines says that the tetrominoes should be generated using the bag of 7 system described in the article. https://tetris.wiki/Tetris_Guideline https://tetris.wiki/Tetris_Guideline
- httpsterio 7y ago
  The 7 in a bag is the official current standing mandated by TTC (The Tetris Company) and all new Tetris games must adhere to this. The reason is quite simple, it is absolutely impossible to hit a drought. The maximum number of same pieces you can get in a row is two (unless you count holding a piece) and at worst if you're waiting for a piece is that you might get 12 pieces inbetween. This makes the game quite a bit more predictable and more beginner friendly which is what TTC is going for apparently. In say, classic Tetris (NES) it wasn't uncommon of having a drought for over 20 pieces if not even more. The 7 in a bag enables a lot of different kinds of builds (like All-clears or the Albatross Special and its' variations) which suit PVP Tetris games like Tetris 99 quite well but it's kinda boring when you're playing solo against the game. I personally enjoy the randomizer in Tetris the Absolute: The Grandmaster 2 PLUS (TAP+) and Tetris the Grandmaster 3 Terror Instinct (TGM Ti) because it definitely had an element of surprise without screwing you totally over. I've never actually done the math, but it would be interesting to calculate the success rates of different build strategies in the 7 in a bag games. Anyways, I'm rambling on. Tetris just always warms my heart :)
  - dragontamer 7y ago
    > more beginner friendly Not necessarily beginner friendly, but more importantly... competitive friendly. Since there's a high amount of determinism between bags, Tetris is a great competitive game. As such, Tetris can be played in an arcade setting without worrying about "bad luck" messing with one player or the other. This has led to the development of many good multiplayer Tetris games, such as Tetris Friends, Tetris Ultimate, Puyo Puyo Tetris, and Tetris 99.
PavlikPaja 7y ago
I think the best compromise would be a bag with let's say five of each piece; every time 7 pieces are dealt, you add a whole set to the bag. No need for unnecessary complications - the pice becomes less numerous and less likely to come when there was a flood, and more common and more likely to come when there was a drought. You can even add a set after less than seven pieces, to increase randomness (and thus difficulty) over time.
bArray 7y ago
My thinking would be to bias piece selection based on a complete history of previous selection, i.e.: const pieces = ['I', 'J', 'L', 'O', 'S', 'T', 'Z']; byte[] probs = [32, 32, 32, 32, 32, 32, 32]; piece getRandPiece(){ int v = Math.random(pieces.length * 32) int sum = 0; int r = 0; for(int x = 0; x < pieces.length; x++){ sum += probs[x]; // check if random value with range if(v < sum){ probs[x] -= pieces.length + 1; r = x; } // increase the probability of each piece being selected ++probs[x]; } return pieces[r]; } I think the benefits would be: * Unlikely flood and drought * Completes in a predictable time (will always loop for each piece) * One random number requested (can be surprisingly expensive if on a slow processor or excessive numbers of calls are made) Are there any negatives to this approach?
- leni536 7y ago
  > Are there any negatives to this approach? Well, probs[x] can go negative when you decrease it, if I'm not mistaken.
  - bArray 7y ago
    Ah yes, good catch :)
te 7y ago
> Pseudo random number generators try to mimic real randomness, but don’t have the properties required to deal out 70,000 Z-pieces in a row. Citation?
- simonlc 7y ago
  I should have specified, but I mainly have experience with simple ones like LCG's, and these are the ones usually used in Tetris games. Another interesting note is that people have processed full periods of some popular Tetris games, and obviously sequences like this never appear.
Balanceinfinity 7y ago
Have to say, I liked the original in the floor console. It wasn't "fair" except in the sense that the chance was evenly distributed, so when I was playing against my friend, over a period of 2-3 hours, the positive and negative breaks evened out (like in backgammon - play it enough and the randomness from the dice rolls gets netted out). The bag approach seems too easy.

120 points by Impossible 7y ago

Maybe not an "official" tetris game, but the the BasTet randomizer is worth a mention - it tries to give you the worst possible block at all times. >:) http://fph.altervista.org/prog/bastet.html http://fph.altervista.org/prog/bastet.html

wwwhizz 7y ago
Ohh, that's evil :D
- needle0 7y ago
  Bastet's randomizer can be defeated by creating a huge overhang near the top of the playfield, then building your actual stack far below it. The evaluation algorithm works by trying to drop every piece in every horizontal position, and choosing the piece that fits the worst, but it only tries dropping pieces straight down and doesn't take sliding or navigating underneath overhangs into account.
  - lalaithion 7y ago
    Hatetris, then: https://qntm.org/files/hatetris/hatetris.html https://qntm.org/files/hatetris/hatetris.html
- de_watcher 7y ago
  The tetris that's comes with the Debian/Ubuntu distribution has that "unfair mode" flag.
digibo 7y ago
There is also HATETRIS https://qntm.org/files/hatetris/hatetris.html https://qntm.org/files/hatetris/hatetris.html

maaaats 7y ago

> The 7-bag has a consistent piece output, making it more predictable. It’s easy to know where in a bag you are, and when a piece you need might come. Because of how predictable this random generator is, it’s actually possible to play forever. Overall it’s a silly system that makes you wonder how it ever became the official randomizer. I actually like the bag one, knowing where in a bag you are gives an edge, and thus it adds an extra dimension to the game I feel.

taneq 7y ago
Wouldn’t you want the game to be indefinitely playable regardless of RNG? Otherwise as player skill increases it tends towards a game of chance, not skill.
- PetitPrince 7y ago
  I'm assuming solo play: Playing infinitely in Tetris means repeating a pattern over and over again. I would suspect that transforming Tetris so that it is universally infinitely playable (probably by somehow erasing the fact that an infinite SZSZ is a death sequence) would lead to a game where the optimal play is also to repeat a pattern over and over game. It would be indeed a game of skill but would rob the player out of all creativity and agency. Not a very fun game at the end. But I think that proving that such game is infinitely playable is a hard (np hard ?) problem.
  - taneq 7y ago
    > Playing infinitely in Tetris means repeating a pattern over and over again. Not necessarily - you could define an infinitely long non-repeating sequence (although it will have arbitrarily long repeating sequences inside it) which would still not contain any certain-death sequences.
PetitPrince 7y ago
This is true for multiplayer game where playing knowing more about the system can give you an edge against someone else. As said it the article: >> The clumsy 7-bag is unnatural feeling, but allows for many building strategies to be consistently viable. And consistency is one very important component of multiplayer games. However for solo play where you end up playing at 20G, the seam problem (repeat of SZSZ) can wreck your game if it happens when you have an unfavorable shape of the stack and/or if you get caught up by the lock delay. for the non-initiated: the piece spawns directly on the stack, on you have only a short time to react and place you piece

spbaar 7y ago

Not listed here is Tetris the Grandmaster 2. TGM2 hits the sweet spot between tgm1 and tgm3 in terms of predictability from the perspective of many fans. It increases the number of rolls to avoid dealing a piece in the 4-piece long history from 4 to 6. Essentially, it decreases the odds of a "history duplicate" from ~10% to 3%. With a 1 piece preview, it encourages a very unique type of planning, where you know what piece you need to prepare for immediately (at high speeds this means holding inputs before it even enters the play field), and also know with almost certainty the next piece is going to be 1 of 4 pieces. Unlike bag systems where the duplicate chance is 2% every 7 pieces here it's only 1% constantly, and the chance of drought is also much lower than bag. The chance of a 10 piece drought for I pieces is almost 0, but you're basically guaranteed to have a random unpleasant drought of 11-13 pieces in a long enough bag7 game. This strongly encourages you to use the hold mechanic strategically for safety, breaking flow and speed. This may all seem academic, and it is very important for the type of high speed games tgm is, but it really is the biggest thing I miss playing modern tetris games. Barring other gimmicks, you build and plan the exact same way in every modern tetris game. With the ever present hold mechanic to switch out a piece, you don't even need multiple piece previews that some new games give you. Consider, after playing 3 pieces, you know with certainty the next 4. With the hold plus 1 piece preview, you spend over half your time in the second half of the bag knowing the next three pieces.

sverona 7y ago
TGM2 doesn't have a hold.
- simonlc 7y ago
  In the first paragraph they are talking about IRS, not holding pieces.

simonlc 7y ago

One randomizer I left out of this article (for the sake of brevity) is the Game Boy's version. It has much more bias as detailed in the post below. According to The Tetris Company founder it was also a last minute addition to the game. When they were testing a late build by Nintendo, it had a fixed sequence or something like that. So Nintendo flew in some devs to where Henk was, and over the weekend they programmed this new randomizer. https://tetrisconcept.net/threads/randomizer-theory.512/page-9#post-51035 https://tetrisconcept.net/threads/randomizer-theory.512/page...

ginko 7y ago
It seems weird that they leave out the GB version of all things since it's probably the most popular version of Tetris by far.
Sniffnoy 7y ago
Oh yikes it's not left/right symmetric! Do you have a direct description of the algorithm? Extracting it from those forum posts seems a bit difficult.
- pixelbath 7y ago
  http://harddrop.com/wiki/Tetris_(Game_Boy)#Randomizer http://harddrop.com/wiki/Tetris_(Game_Boy)#Randomizer
  - Sniffnoy 7y ago
    Thanks! To repeat it here: we assign each piece a piece a vector of 3 bits; thinking of these vectors as numbers from 0 to 7 (or rather 0 to 6, since 111 is unused), the pieces go in the order (L, J, I, O, Z, S, T). Note that this assignment is not left-right symmetric; there's no particular relation between a piece and its mirror image. Like, L is 000, but J is 001; and Z is 100, but S is 101. That seems like kind of a dumb mistake -- it would've been easy enough to maintain symmetry. (As just one example among the 24 possible ways (assuming 111 must be kept unused), one could have used instead (O,J,I,Z,L,T,S).) Anyway, each turn you pick one of these at random, and you look at the last two pieces; let's call these previous_1 and previous_2. If -- considering pieces as their sets of 1-bits -- we have both that previous_1 is a subset of previous_2, and that the picked piece is a subset of previous_2 -- we reroll. After the third try we just take the piece no matter what. Note that this means that there are some weird interactions between the previous two pieces. Like, if previous_1 is not a subset of previous_2, then we won't reroll no matter what piece we picked, so the new piece will be totally random. But if it is, then we may or may not reroll. Definitely pretty weird. Have to wonder how on earth this was thought up...

ArtWomb 7y ago

Thanks for posting. I love research like this ;) Reminds me of a similar result in which "locally noisy" bots inserted into human coordination games can yield a positive outcome! https://www.nature.com/articles/nature22332 https://www.nature.com/articles/nature22332

bjourne 7y ago

There is actually a "Tetris Standard" written by Colin Fahey which mandates that tetrominoes should be drawn from a Bernoulli distribution. https://www.colinfahey.com/tetris/ https://www.colinfahey.com/tetris/ "When a piece is spawned, the type of piece is selected using the following algorithm: pieceIndex = 1 + (randomInteger % 7); // 1..7 Because there is a constant p (= 1/7) chance of selecting a specific kind of piece, and all pieces of the same type are indistinguishable, the probability of having exactly k pieces of a specific type after n trials follows a Binomial distribution" However, the standard isn't adopted by all. A competing set of guidelines says that the tetrominoes should be generated using the bag of 7 system described in the article. https://tetris.wiki/Tetris_Guideline https://tetris.wiki/Tetris_Guideline

httpsterio 7y ago
The 7 in a bag is the official current standing mandated by TTC (The Tetris Company) and all new Tetris games must adhere to this. The reason is quite simple, it is absolutely impossible to hit a drought. The maximum number of same pieces you can get in a row is two (unless you count holding a piece) and at worst if you're waiting for a piece is that you might get 12 pieces inbetween. This makes the game quite a bit more predictable and more beginner friendly which is what TTC is going for apparently. In say, classic Tetris (NES) it wasn't uncommon of having a drought for over 20 pieces if not even more. The 7 in a bag enables a lot of different kinds of builds (like All-clears or the Albatross Special and its' variations) which suit PVP Tetris games like Tetris 99 quite well but it's kinda boring when you're playing solo against the game. I personally enjoy the randomizer in Tetris the Absolute: The Grandmaster 2 PLUS (TAP+) and Tetris the Grandmaster 3 Terror Instinct (TGM Ti) because it definitely had an element of surprise without screwing you totally over. I've never actually done the math, but it would be interesting to calculate the success rates of different build strategies in the 7 in a bag games. Anyways, I'm rambling on. Tetris just always warms my heart :)
- dragontamer 7y ago
  > more beginner friendly Not necessarily beginner friendly, but more importantly... competitive friendly. Since there's a high amount of determinism between bags, Tetris is a great competitive game. As such, Tetris can be played in an arcade setting without worrying about "bad luck" messing with one player or the other. This has led to the development of many good multiplayer Tetris games, such as Tetris Friends, Tetris Ultimate, Puyo Puyo Tetris, and Tetris 99.

PavlikPaja 7y ago

I think the best compromise would be a bag with let's say five of each piece; every time 7 pieces are dealt, you add a whole set to the bag. No need for unnecessary complications - the pice becomes less numerous and less likely to come when there was a flood, and more common and more likely to come when there was a drought. You can even add a set after less than seven pieces, to increase randomness (and thus difficulty) over time.

bArray 7y ago

My thinking would be to bias piece selection based on a complete history of previous selection, i.e.: const pieces = ['I', 'J', 'L', 'O', 'S', 'T', 'Z']; byte[] probs = [32, 32, 32, 32, 32, 32, 32]; piece getRandPiece(){ int v = Math.random(pieces.length * 32) int sum = 0; int r = 0; for(int x = 0; x < pieces.length; x++){ sum += probs[x]; // check if random value with range if(v < sum){ probs[x] -= pieces.length + 1; r = x; } // increase the probability of each piece being selected ++probs[x]; } return pieces[r]; } I think the benefits would be: * Unlikely flood and drought * Completes in a predictable time (will always loop for each piece) * One random number requested (can be surprisingly expensive if on a slow processor or excessive numbers of calls are made) Are there any negatives to this approach?

leni536 7y ago
> Are there any negatives to this approach? Well, probs[x] can go negative when you decrease it, if I'm not mistaken.
- bArray 7y ago
  Ah yes, good catch :)

te 7y ago

> Pseudo random number generators try to mimic real randomness, but don’t have the properties required to deal out 70,000 Z-pieces in a row. Citation?

simonlc 7y ago
I should have specified, but I mainly have experience with simple ones like LCG's, and these are the ones usually used in Tetris games. Another interesting note is that people have processed full periods of some popular Tetris games, and obviously sequences like this never appear.

Balanceinfinity 7y ago

Have to say, I liked the original in the floor console. It wasn't "fair" except in the sense that the chance was evenly distributed, so when I was playing against my friend, over a period of 2-3 hours, the positive and negative breaks evened out (like in backgammon - play it enough and the randomness from the dice rolls gets netted out). The bag approach seems too easy.