Can you be sure to clear a line at Tetris? | Hacker News Reader

Can you be sure to clear a line at Tetris?

a3nm.net

185 pointsa3_nm38 comments

Related: in the official specification of the game the pieces ("tetrominoes") are drawn from a bag to prevent the possibility of an unfavorable sequence of pieces that force you to lose the game.

IIRC early implementations of the game did not always behave like that.

https://tetris.fandom.com/wiki/Tetris_Guideline

> You might have heard of the result that you can play forever with bag randomizer, Hold and 3 previews (a similar setup even works with 0 previews). However, the opposite is true, if you play with a randomizer that can generate all piece sequences (e.g. memoryless randomizer). In this article we will present a piece sequence that will top you out - no matter what you do.

https://harddrop.com/wiki/A_deadly_piece_sequence

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55...

"A history of Tetris randomizers (2018)"

> IIRC early implementations of the game did not always behave like that.

And they were also much better for it, in my opinion (and that of many classic NES Tetris fans).

This is the perfect illustration of the gambler's it-isn't-necessarily-a-fallacy!

Despite a uniform distribution of tetrominoes, if you haven't seen that all important I in awhile, the run is "cold" and you are in fact "due".

For the gambler's fallacy to apply, events have to be both random and uncorrelated, where most interesting real-life situations (i.e. not games) the degree of correlation between events isn't zero: that's one way to observe a normal distribution, but not even the usual one.

https://simon.lc/the-history-of-tetris-randomizers

A great idea and article needing some LaTex formatting

If you want to test a strategy against an adversarial tetris opponent: https://qntm.org/files/hatetris/hatetris.html

The method by which the AI selects the worst possible piece is extremely simple to describe (test all possible locations of all possible pieces, see which of the pieces' best-case scenarios is the worst, then spawn that worst piece), but quite time-consuming to execute, so please forgive me if your browser chugs a little after locking each piece. If you can figure out a way to accelerate the algorithm without diminishing its hate-filled efficiency, do let me know. The algorithm for "weighing" possibilities is to simply maximise the highest point of the "tower" after the piece is landed.

The resulting algorithm seems to be "spawn z and s pieces on repeat". I only got one long piece and one L piece.

The author may have written a brute force algorithm when a greedy solution would have worked :)

This reminds me of Futilitris (although that's adversarial in a less algorithmic and more existential sense.)

It produces only S for me. which is fine, but then produces only a 4bar. seems pretty boringly simplistic as an outcome.

I also got this message at the end, pretty random and cryptic

ԊටຯߢதؿଈϠଵദເם௨කໃݹதغƬݷȿට༠ਡ௨

I think the last line is a replay, encoded in base2048: https://github.com/qntm/base2048

But when I tried your replay, it didn't work. Perhaps HN's text editor mangled something.

I remember seeing this at one point and clearing a grand total of 5 lines in one game. Turns out it's hard if the game is trying to make you lose.

There was a kid I knew in school who I would consider a very good tetris player. One time someone else was lamenting that they always get bad pieces and he said, "The Tetris gods will never give you a piece you can't play, you just don't know how to play it." Which has resonated with me for an oddly long time in my life.

This sort of thing comes up a lot in card games like mtg. Some players are convinced they're naturally unlucky. I like to phrase it as "bad decks get bad draws". To improve one has to be luck oblivious: improve what you can, accept what you can't. Bit of a serenity prayer approach

It's also important to understand that in a best of 3 format, if you have a 80% winrate per game against every player (which is insane btw), you still lose 10% of those matches. In a 9 round tournament day (which is standard for YuGiOh iirc), your chance of winning every single round for the entire day is merely 40%. If your edge is more realistic, say 60% winrate, then you lose 35% of those matches. More games per match are your friend for determining who is actually better.

qntm, creator of Hatetris [1], once did an analysis of this exact problem using brute force methods. While he managed to solve the problem for 4, 6 and 8 wide boards (including the minimum board height required, assuming game over if any part of a piece locks above the ceiling), solution eluded him for 10 wide, though he did prove that 6 height was insufficient.

As it happens, since this work assumes a 20 high board and there are some sequences (e.g. ZSOLJJJ) for which the solution here goes up to height 8 (it could potentially go up to height 9 but I have no plans to check), there's a little bit of a gap that still needs to be filled.

[1] https://qntm.org/hatetris

[2] https://qntm.org/tetris

Thanks for the pointer to https://qntm.org/tetris -- that's very relevant, I'll add it to the post.

Yes in "Tetris Guidelines". In fact, greater feats can be accomplished in modern Tetris games, thanks to these strong guidelines.

https://www.youtube.com/watch?v=qmG0NcbrLTE

Strong players practice these loops all the time. Its possible thanks to the "bag randomizer".

--------

The BT Cannon is a TSpin double (4 damage + B2B bonus) + TSpin Triple (6 damage + B2B bonus), for a total of 11 damage.

The DT-cannon followup is a TSpin Triple followed by TSpin Double for a total of 12 damage.

Finally, the Perfect Clear is 10 damage, for a total of 33 damage per loop.

--------

Other players practice triple-perfect clear starts, for 30-straight damage in some ~30 tetriminos dropped. But the BT-cannon + DT Cannon -> Perfect clear setup is a beautiful arrangement.

The whole loop is carried out over 5 bags IIRC, or 35 pieces (5 bags * 7 pieces per bag == 35 sets of each piece). That's enough for the 4x T-pieces needed for the BT-cannon + DT Cannon (which offer significant amounts of damage)

35 pieces * 4 pieces == 140 minos, or 14 lines (the Tetris board is exactly 10 pieces wide). Which lines up with not only a perfect bag loop (the 35th piece finishes the bag, meaning piece#36 is a new bag, allowing you to loop), but also divides perfectly with 140 minos aka 14 lines, meaning the perfect clear is possible.

------

Thanks to Tetris Guidelines bag randomizer, bag#6 is effectively the same situation as bag#1 (start of a new bag). So you loop the sequence and can continuously apply the BT-cannon / DT-cannon / perfect clear loop almost perpetually. In practice, its "only" a 90%+ chance of continuing each loop, but that's a high enough probability to effectively use the technique in competitive games.

EDIT: The existence of the "Hold Piece", in combination with the "easy to count" 7-bag randomizer, allows for some incredible feats in Tetris Guidelines that classic-Tetris players are unfamiliar with. Its a different game, more about quick-reaction speed and twitch reaction rather than the planning-centric classic-Tetris. But its these attributes that make Tetris-Guideline games better for player-vs-player setups. Practiced strategies are more reliable and less contingent on luck.

I think we had this discussion a year or two ago, but personally I find the guideline algorithm to be boring. It's definitely more oriented to PVP Tetris. Something like TGM would be boring if you can just execute builds instead of preparing your stack and play for just about anything.

It's true that there's a lot of different builds (I'm personally more partial to the albatross special than DT cannons) and builds are not only related to what you can build, also how you should respond to your opponent. Like, is the game even fun when you're just spamming t-spins with Tafokint's T-spin factory?

I'm a pretty highly ranked Tetris player, top ten in Finland in T99, Tetr.io and Puyo Puyo Tetris and somewhere in the top 100 as well, and in reality I think fancier builds like DT-cannons are too fragile and reliant on a clean-ish stack that they're not even viable in high level play. If you take ten seconds to set up a tetris or 15 seconds for a triple T-spin then you're gonna get spammed to death before you can reply with your fancy build.

In modern PVP Tetris I think there's only three tactics. If you're not too technical, you need be fast at tetrises and hope you can outpace your opponent.

If you're slower, you have to deal more damage in the same time or less = T-spins for double damage. It took me a year of practicing to intuitively start leaving t-spin doubles in more unconventional setups. There's the risk of being outpaced and spammed but the double damage mitigates it a bit.

Third option is comboing. I think it's the hardest to pull off but it's also the most effective. With a three wide hole it's fairly easy to get a combo going but there's always a huge risk of topping out by a badly timed attack from the opponent. Four wide is harder to keep going but it's safer.

Depending on the game and network code, combo builds can be game breaking and actually stagger the enemy so that they can't even reply to your attacks. It is however the least effective build in terms of how many pieces you need and the return damage for each clear and there's the most unknowns in how you're supposed to stack.

But to sum up in short, I don't think "builds" per se are the way to go in PVP. The "stack, attack and reply" formula simply leaves too large holes for your opponent to attack and it's not variable enough. Seeing parts of builds as patterns, like using a roof on a T-shaped hole to build a triple T-spin is useful if you can figure it out whilst clearing garbage and keeping a constant battering on your enemy going.

Personally, I think TTC forcing guidelines on single player games is boring. TGM TAP+ was the pinnacle in terms of game behavior and algorithms, IMO holds and the floor kicks in Terror Instinct made everything a bit too easy and all the difficulty comes from being ridiculously fast instead of being super meticulous and eloquent in your stacking.

I'm not a top-100 player, but I think I know enough about the game to hold a discussion.

My personal style is a severe and heavy focus on TSpin-double setups: TKI3 and Albatross. But I "respect" other players who have taken the time/effort to try other strategies, and I even see the advantages of their setups.

> and in reality I think fancier builds like DT-cannons are too fragile and reliant on a clean-ish stack that they're not even viable in high level play.

But players I respect and study are extremely strong with DT-cannons. Doremy and Amemiya (especially Amemiya) use DT cannons regularly. The "Amemiya Cannon" is the famous DT-cannon + perfect clear / DT-cannon + TSD option select (depends on RNG) for example.

> Third option is comboing.

Amemiya does both. DT-canon leaves the "z" shape overhang ready for the most reliable side-4w builds. Side-4w is more risky, but provably faster to build than center-4w.

After all, bag-randomizer is still... somewhat random. If the pieces aren't setup for one possibility, you need contingency plans. I'm sure top players like Amemiya is constantly looking ahead and deciding upon "DT-canon + Perfect Clear" and/or "DT-canon + side-4wide" depending on what the RNG-blesses him with.

---------

I've also had the pleasure to play vs Wumbo on multiple occasions. A lot of people complain about Wumbo's absurdly fast comboing skills, but in my experience, Wumbo is also a top-tier player in simple TSpin-double setups.

> If you're not too technical, you need be fast at tetrises and hope you can outpace your opponent.

IMO, Tetris only works as a downstacking strategy. Especially since guidelines tetris often has "clean garbage" (if you deal 7 damage from a B2B TSpin Triple, your opponent will have all 7-garbage lined up and ready for a counter-Tetris to erase 4-of that garbage).

As an upstacking strategy, Tetris is pretty weak. You require 10-pieces (40-minos) to build a Tetris, but only deal 4 damage+B2B, maybe 5-damage at the best case. Pretty bad all else considered.

As a downstacking strategy, Tetris requires zero-pieces to setup (assuming garbage is lined up), removes 4-lines of garbage from your side, retains B2B bonus, and deals 4 damage to the opponent. That's a garbage-conversion of 9 total and zero-pieces of investment.

In contrast, TSpin-singles (favored by Amemiya, especially vs Puyo players) require only 1-lines of upstack, one of which can be from garbage (!!). A singular Z or S piece is all you need to setup a TSpin-single that digs into your garbage and digs downward. (-1 garbage line, one-piece of upstack, B2B bonus retained, 2-damage + B2B for a 3rd damage). That's roughly 4-converted damage with only 1 or 2 pieces used, and the king of efficiency.

3-lines of damage that requires only 2-pieces (s/z + T) and digs into garbage is extremely solid. That's 2-pieces dropped and a conversion of 4 lines, far more efficient than an "upstack-tetris" (10-pieces dropped and a conversion of 5-lines, assuming B2B bonus)

In a pure upstacking scenario: TSS, TSD and TST are all far more efficient in a "pieces per garbage" situation. 3-lines of upstack turn into 6 damage + B2B for TST, far more efficient than 4-lines of upstack turning into 4 damage+B2B for an upstack Tetris.

King Crimson (TST + 2x TSD) turns 7-lines of upstack into 16 damage + B2B. Extremely efficient.

-------

So from my perspective, the game is in roughly 3 phases:

1. Opening -- Because the bag randomizer is so predicable, both players can execute pre-concieved strategies extremely reliably. It seems like c4w is the strongest strategy in the current meta, but there's some "rock-paper-scissors" play involved (I find that TKI3 / 3x TSpin Doubles in the first 3 bags is a solid counter vs enemy c4w players as well as perfect-clear players, which is why its my favored opening)

2. Downstacking -- Removing garbage from your side of the field as efficiently as possible. Tetris tends to be the best strategy, but some players (ex: Wumbo) have the ability to "combo downstack". Combo-downstack is the strongest strategy but is incredibly difficult to pull off. Amemiya's TSpin-single setups demonstrate efficiency in practice. (TSpin-single when garbage "doesn't line up", to retain B2B bonus while downstacking)

3. Upstack -- Once you "reach the bottom", you need to build the stack back up before you deal damage. Tetris is a poor option for Upstack, but dedicated builds (King Crimson, Super Tspin double, etc. etc.) perform the best in my experience. Bonus points for "Bursty" builds like King Crimson or DT-cannon, because many players hold onto a "Defensive Tetris" to cancel out some of your upstack damage in this situation. So you need a plan to reliably deal in excess of 9-lines of damage to the opponent.

This is one of those questions that seems to be wide open for elaborate proofs - but it turns out the total number of possibilities isn't that large, and you can simply enumerate each one.

Heh, yup. I remember an article on here about some low-level calculation optimization for 32-bit ints that bugged out even with extensive edge-case testing. The conclusion being “just test all the numbers”, 2^32 isn’t that much!

maybe https://randomascii.wordpress.com/2014/01/27/theres-only-fou...

Is there a good way to reduce SAT or other decision problems to Tetris? Do we need to enlarge the grid to reduce larger problem instances, or can the duration of the play / length of the sequence be used for that?

I would hope for something like "This list of clauses is satisfiable iff there is a winning strategy to clear at least N lines when given the following sequence of tetrominoes". (Where the article here says that there is no hope for anything like this with N=1, but )

Or does knowing the whole sequence in advance make any sequence easy to play / clear any number of lines?

In my experience, strong human players can consistently keep track of random-bags and plan out holds, and do so at surprisingly high speeds.

I'm not sure if a computer SAT-solver is needed to accomplish any of the tactics in Tetris-Guidelines.

Maybe it'd be a fun exercise, like using SAT-solvers on human-level Sudoku puzzles. Or for maybe inventing "harder" versions of Tetris, designed for computer players instead of human players.

-------

I've given some degree of idle thought in how a SAT-solver can maybe discover patterns that would help an intermediate-player develop the eyesight / instincts that strong players have. (Ex: SAT-solver to see the patterns an intermediate player is using, and then analyzing which patterns the player doesn't see yet).

Its a vague / idle thought however, I never seriously attempted to solve the problem. But "training exercises" exist in many video games, and developing tools for human-training / self-training are always useful.

Ex: if a SAT solver could see that the human _COULD_ have performed a King Crimson at some point (https://harddrop.com/wiki/King_Crimson), but the human-player made a mistake and only saw an easier TSpin-Triple setup instead (https://harddrop.com/wiki/T-Spin_Triple).

Such "computer automatic advice" into which elements of your play was possible, and solving it automatically (and determining if it was a good strategy or not) would be very helpful in training.

Most NP-complete problems have really good heuristics that come to within a hair of optimal on most useful real-world inputs, e.g. things like integer partitioning, bin packing, traveling salesman, etc. You need really unusual inputs to give an optimal solver a drastic advantage. Case in point, with real-world TSP the fact that the cities are embedded on a plane means their distances have constraints that don't exist in the general problem.

I'm pretty sure 2-D Euclidean TSP is NP-Hard.

https://en.m.wikipedia.org/wiki/Travelling_salesman_problem (Computational Complexity).

It is, but there are polynomial-time approximation algorithms that can get you arbitrarily close to the optimum.

No, there aren't? The last time I checked, the best polynomial-time approximation algorithm to symmetric TSP (Christofides) could only guarantee finding a tour with no more than 3/2 of optimal length. Has something better been found since then?

Euclidean TSP is easier than general symmetric TSP. Polynomial-time approximation schemes (PTAS) were discovered in parallel by Arora (1998) and Mitchell (1999). AFAIK those algorithms are not very practical though. I haven't followed subsequent work in any detail, but I haven't heard of any major breakthroughs since then.

Well, damn. I imagine the reason why didn't know about this is because I have never been able to formulate any of my particular problems in terms of Euclidean TSP (even just metric was hard enough at times), so all interesting stuff was about metric TSP for me. I'll have to look at that work, though. Thanks for the pointers.

You are correct for Metric TSP (weights satisfying the triangle inequality) but not for Euclidean TSP.

Further, for metric TSP, an approximation algorithm with a slightly better ratio was found, and received a best paper award at STOC'21. See the second paragraph of https://en.wikipedia.org/wiki/Christofides_algorithm.

Yes.

https://www.google.com/search?q=tetris%20n-p%20complete

> Mathematically, we can formulate this a sequential zero-sum game with perfect information.

Is this not just restating that Tetris is NP-hard? https://arxiv.org/abs/2009.14336

No, there are plenty of zero sum games with perfect information that aren’t np-hard (eg tic tac toe).

This is a classic example of: "Assume a spherical cow". The game is also about hand/eye coordination, as well as solvability. So given the helpful precis:

"Summary: it is possible to play Tetris and guarantee that you will score at least one line, no matter which pieces are given to you, i.e., even assuming they are chosen adversarially."

We can confidently respond: "bollocks".

Great write up and analysis.

Reply on news.ycombinator.com