Live data from Hacker News

Can you be sure to clear a line at Tetris?

a3nm.net

21–30 of 39 posts

Re: Can you be sure to clear a line at Tetris?

#21

Earlier quoted context omitted.

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…

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…

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

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

Re: Can you be sure to clear a line at Tetris?

#22

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…

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 ar…

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.

Re: Can you be sure to clear a line at Tetris?

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

Re: Can you be sure to clear a line at Tetris?

#24
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

Re: Can you be sure to clear a line at Tetris?

#25

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 bro…

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

Re: Can you be sure to clear a line at Tetris?

#27

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

Re: Can you be sure to clear a line at Tetris?

#28
post #2

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 great idea and article needing some LaTex formatting

Re: Can you be sure to clear a line at Tetris?

#29

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 bro…

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

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

Re: Can you be sure to clear a line at Tetris?

#30
post #21

Earlier quoted context omitted.

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…

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.
Post reply on HN