Hacker News new | past | comments | ask | show | jobs | submit login
A history of Tetris randomizers (2018) (simon.lc)
120 points by Impossible 17 days ago | hide | past | web | favorite | 41 comments



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...


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.


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.



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...


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.


TGM2 doesn't have a hold.


In the first paragraph they are talking about IRS, not holding pieces.


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



Ohh, that's evil :D


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.



The tetris that's comes with the Debian/Ubuntu distribution has that "unfair mode" flag.


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/

"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


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 :)


> 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.


Wouldn’t that problem be solved by simply setting both players seed value to the same?

I believe the order of balls is the same for both players in bust-a-move, but still the boards will quickly diverge a lot.


> Wouldn’t that problem be solved by simply setting both players seed value to the same?

Lets say drop 100 through 110 were unlucky SZSZSZSZ pattern. The faster player will come across the "unfortunate" pattern first and then lose. In contrast, the slower player will only be on drop 80.

The bag system ensures that high-speed play is possible for both players, and favors the faster player in all cases. A true randomized system would have "unfortunate" patterns which will eventually kill the faster player.

------

With that being said: Tetris Classic competitions seed the two competitors with the same pattern. But similarly, Tetris Classic has no concept of "garbage damage".

In Tetris Friends / Puyo Puyo Tetris / etc. etc, you "damage" the opponent by doing a Tetris, or a T-spin (a complicated maneuver). Its actually a very good, very well balanced game (although some would argue that "combos" are a bit strong in the current iteration of the damage formula).


> Lets say drop 100 through 110 were unlucky SZSZSZSZ pattern. The faster player will come across the "unfortunate" pattern first and then lose. In contrast, the slower player will only be on drop 80.

Does the faster player get nothing in return for their speed advantage? If so, then shouldn't they just play slower? If not, then aren't they compensated fairly for the risk of running into a difficult sequence earlier in the game?


> Does the faster player get nothing in return for their speed advantage?

In Guidelines Tetris, you only deal damage if you do a sufficiently complicated maneuver. A Tetris (4-line clear), a T-Spin ("spinning" a T-block into place), or a "Combo" (repeatedly clearing lines non-stop). As such, you only can do a major damage from I-blocks (a 4-line clear / Tetris), or T-blocks (TSpins).

No other block in the game can deal major damage by themselves. So the placement of I blocks and T-blocks is fundamental.

---------

Also note: Garbage is a "comeback" mechanism: large amounts of garbage "feed" the opponent lines to perform a combo with. If you deal non-lethal damage to the opponent, it is common for the opponent to use the garbage you sent him to "combo" into a large amount of damage back to you.

As such: the game becomes more garbage is sent around. There is a chance the opponent can see a 12-combo through the garbage you sent them. Its difficult for the untrained players to see combos, but it definitely comes into play at higher-levels.

---------

The current system (including the bag-randomizer) has been carefully balanced between many issues, and playtested for years. Aside from occasional issues (ex: TSpin singles becoming too easy in an early version: leading to the development of "TSpin Minis" to nerf that technique), the overall Tetris Guidelines rules are quite good. I recommend playing a modern competitive version of Tetris and trying it out yourself.

Combo-play is definitely considered one of the strongest strategies right now. Moving to a true-randomizer will necessarily nerf Tetris / T-Spin play, because you can no longer predictably get Tetris or T-blocks.

In my experience, most players want to play Tetris: that is, create Tetrises (4-line clears). Combo play is certainly fun, but it makes sense to "buff" the canonical "Tetris" strategy of the game since that's what people expect. Tetris is the name of the game after-all, and you can only play "Tetris" if you have some kind of assurances that I-blocks are on the way.

Nerfing Tetris and buffing Combos seems to be the wrong direction for balance. If anything, Combos need to be nerfed.

Perfect-clear play is also lovely to watch. Computers are better than humans, but when a human perfect-clear player comes in, its truly intense and fun to watch (and play against). Perfect-clear play relies upon the bag-randomizer to a severe degree, and isn't even that strong of a strategy (a good perfect-clear player needs to threaten 3x perfect clears within 20 seconds to be competitive at high levels). Moving to "true random" would erase this obscure style of play completely.

-----------

In any case, there's a big community which prefers to play with true randomizers: the "Tetris Classic players". They play by a separate set of rules entirely.

As a Guidelines Tetris player, I obviously have my bias. I think the game is more fun with Tetris, Combos, and Perfect-clear openings in play.


Difficult to extract the pertinent info out of that, but I take it you're saying that the player is compensated for speed. They can send more garbage and increase their chances of winning by placing pieces faster. In which case, that undermines the earlier point that bag randomizer is better because it rewards fast play. In reality, both kinds of randomizers reward fast play, as the net advantage of playing fast with the classic randomizer is still positive.


> as the net advantage of playing fast with the classic randomizer is still positive.

Only if T-blocks and I-blocks come. If there's a drought of T-blocks and I-blocks, then the combo-player wins.

Combo is currently the strongest strategy, under the current Tetris Guidelines.

If you have "too many" I blocks, you run out of Tetris room very quickly (You can only form a Tetris if you've built up 4-rows of 36-minos, with the last 4-square hole being where you use the I-block). If you have "too few" I blocks, you literally can't clear the hole and die.

My overall point is that the bag-randomizer "buffs" Tetris and T-spin players, while "nerfing" combo play. I argue that Tetris-players are the "main strategy", and probably should be buffed to be stronger.


Currently tetris players are not the ones winning usually. Combo is still really strong because it basically stun locks you by throwing garbage at you and a sufficiently strong combo player can make you top out from an empty playing field even if you clear three tetrises back to back.

Tetris players also get wrecked by t-spinners as t-spins do double damage compared to how many pieces you clear. The t-spin is the only piece that can send 6 lines back. And with about three bags worth of pieces you can do a t-spin triple + t-spin double + t-spin single = 12 lines.

Only way you can top that is with three all-clears which you most likely won't get.

With the current rules, if you wanna win, you gotta be either t-spinning or comboing in pvp tetris.


Its great to see another good Guidelines player discussing these issues :-) Its clear you have a lot of experience in this matter.

You are correct in that TSpins are a great upstacking strategy. Tetris however is a downstacking / defensive strategy.

Consider a "Counter-Tetris": You clear 4-lines of garbage, while dealing 4-damage (+B2B). That's a "effective garbage differential" of 8-lines (+B2B) (you lost 4-garbage, while dealing 4-damage to the opponent). This ideal doesn't always happen, but its far more powerful than a TSpin Triple.

It is impossible to build a TSpin Triple out of garbage, you MUST create a specially crafted overhang. TSpin Triples always leave an overhang. As such, TSpin Triples and TSpin Doubles can at best, clear 1-line of garbage. (and a TST will block your garbage hole until the TST is executed AND the overhang is somehow cleared).

TST into 1-line of garbage is 7 "garbage differential" (2-lines of upstack, 1-garbage cleared + 6 damage sent + B2B). TSD into 1-line of garbage is 5 garbage differential (+B2B) (1-line of upstack, 1-garbage cleared + 4 damage sent + B2B).

Counter-Tetris is 4-garbage lines cleared, 4-damage sent+B2B (8-garbage differential). 3-garbage lines cleared is 7-differential, and 2-garbage lines cleared is 6-differential.

As such, even a 2-garbage + 2-upstack Tetris is more "garbage differential efficient" than all TSpin Doubles, while a 3-garbage+1-upstack beats a pure-upstack TSpin Triple.

Just don't upstack a Tetris, and you'll do fine. Upstacking for a Tetris is grossly inefficient compared to Upstacking TSD or TST.

---------

My recommended strategy is: TSD for upstack, Tetris for downstacking. TSD keeps the "hole" open for an emergency Tetris if the opponent starts to spike you (an incoming I OR T block can be executed).

A TST overhang blocks the hole however forcing ordering. (you MUST use a T-block), and the overhang will block the I-block until you clean it up somehow.

---------

Anyway, I argue that going for Tetris should be a stronger strategy... because "Tetris" is literally the name of the game. The "namesake" strategy is weaker than people expect as it is, weakening it further by using a full-randomizer would probably be a bad idea.


Yeah, it is interesting to ponder how much the game changes by a seemingly simple detail like how the pieces are generated. If they are generated uniformly then it is certain that the player will lose sooner or later (getting too many S or Z pieces in a row). It also has been shown that such a setup makes the game NP complete. https://arxiv.org/abs/cs/0210020 It's way above my head but intuitively it feels like any randomization based on the bag model would give rise to optimal strategies, even making it possible to play indefinitely. PVP play as you say of course makes it much more interesting. It wouldn't surprise me if the strategies for playing well are just as deep as for playing Go or Chess.


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?


> Are there any negatives to this approach?

Well, probs[x] can go negative when you decrease it, if I'm not mistaken.


Ah yes, good catch :)


> 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.


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


To further clarify 20G, a regular Tetris playfield is 21 blocks high and in 20G gravity your piece falls 20 in a frame. So, it doesn't technically spawn directly on the stack, but it will fall on top of your stack before you can move it horizontally.

It is only possible to play 20G if you have what is called TLS (Temporary Landing System) and IRS (Initial Rotating System) in TGM games. This means that even before your piece spawns and falls, you can rotate it by one rotation either clockwise or anticlockwise and when the piece drops, it doesn't lock into its' place immediately, you can move it for a short while.

Also, if the piece drops vertically, the locking time resets which means that you should build a pyramid shaped stack so that you can slide your pieces down on either side and rotate it where you want it before it locks.


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 aften less than seven pieces, to increase randomness (and thus difficulty) over time.


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.


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.


> 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.


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.


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.


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


> 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?


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.




Applications are open for YC Winter 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: