from Hacker News

Can you be sure to clear a line at Tetris?

by a3_nm on 4/19/22, 7:38 PM with 38 comments

  • by tosh on 4/19/22, 8:09 PM

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

  • by georgecmu on 4/19/22, 9:41 PM

    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.

  • by Hogarth01 on 4/19/22, 9:33 PM

    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.

  • by Arcorann on 4/20/22, 12:08 AM

    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

  • by dragontamer on 4/19/22, 8:49 PM

    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.

  • by bombcar on 4/19/22, 8:25 PM

    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.

  • by m4lvin on 4/19/22, 9:20 PM

    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?

  • by alephnan on 4/20/22, 4:36 AM

    > 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

  • by gerdesj on 4/19/22, 11:37 PM

    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.