Is there winning strategy in Tetris ? What if Young diagrams are falling?

Question

Question 1 Is there a winning strategy (algorithm to play infinitely) in Tetris, or is there a sequence of bricks which is impossible to pack without holes?

Consider generalized Tetris with Young diagrams (for some $n$) are falling down.

Question 2 Is there winning strategy? If not - consider some probability measure on Young diagrams (e.g. uniform). What will be "losing speed"? I.e. how fast the height of uncancelled rows will grow for best possible algorithm?

Question 3 Can one relate such Tetris like questions on Young diagrams with some conceptual/conventional theories where Young diagrams appear - representation theory of symmetric group or something else?

Answer 1

Heidi Burgiel's first paper "How to Lose at Tetris" (which she wrote towards the end of our time in grad school in Seattle) answers Question 1 in the negative. It was published in the Mathematical Gazette volume 81 (1997) 194--200. If you want to see the published version, that volume is still on JSTOR where you can access some number of articles for free, http://www.jstor.org/stable/3619195. (Current Gazettes are on the Cambirdge journals site.) As mentioned in the comments, there's a version at the old Geometry Center site, http://www.geom.uiuc.edu/java/tetris/tetris.ps.

A related article "Tetris is Hard, Even to Approximate" by Erik Demaine, Susan Hohenberger, and David Liben-Nowell shows the difficulty of dealing even with a finite sequence known in advance. Although it generalizes the board size, it keeps tetris pieces. The document http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-865.pdf is much longer than the published http://erikdemaine.org/papers/Tetris_COCOON2003/paper.pdf.

To your other questions: For the simple part of Question 2, I'd think the answer is "no" since any "pentris" or larger Young tableaux / Ferrers diagrams for $n \ge 5$ would be extensions of the Tetris pieces that are already too much for a winning strategy. The details of the Demaine et al. paper(s) may help address the rest of that question.

Towards Question 3, there are skew tableaux which can be thought of as building blocks for a Young tableau. Also, there's the notion of removing rim hooks to get to the $p$-core of a partition.

Answer 2

My answer is regarding the first part of your Question 1. There is a paper linked in comments (below your question) which shows that, in general, there is no winning strategy. The paper is based upon essentially assuming that any given sequence of tetrominoes can occur.

The rules for what sequences of tetrominoes are or aren't allowed in a game is usually called a "Randomiser" (in terminology of the game). A randomiser that allows any sequence of tetrominoes is called "memoryless". So the paper shows that given a memoryless-randomiser, there is no general winning strategy. However, the analysis might not apply to games(even otherwise assuming exactly same game mechanics as in paper) which implement a different randomiser because certain sequences of tetrominoes are forbidden with probability 1 (at any possible point in the game).

It has already been hinted in the other answer that the winning strategy for single player with, what is called a bag randomiser, and some further rules/features has been known for almost a decade (see for example one of the answers: https://math.stackexchange.com/questions/1135388/an-impossible-sequence-of-tetris-pieces). It should be mentioned that some aspects(I think) have been improved upon for this loop in recent years.

But, at any rate, what is surprising for me is that there doesn't seem to be much work done beyond that. Considering "just" the single-player gravity based variant of endless tetris there are three main aspects (keeping it as short as possible):

(1) Basic Features: These include, among other things, features such as "Hold" and "Number of Next Piece Previews".

(2) Gravity Rules: There are two main choices "0G" and "20G". 0G or very close to 0G occurs in most commercial games. 20G (instant drop) occurs in the well-known TGM series. With 0G one can decide whether to include "softdrop" or not. What that means is that when a tetromino falls on the surface it can be moved around on the surface (of the stack), before finally locking in (the proof I linked actually seems to use that in a couple of situations). With 20G there are certain basic "kick-rules" (the full explanation of rules would be little longer but they are well-documented).

(3) Randomiser: Randomiser, as has been mentioned, desrcibes rules for which sequences of tetrominoes are or aren't allowed. In actuality, this is done to reduce probability of unfair situations. As far as I know, "7 piece bag" is the most common randomiser for commercial iterations (atleast for some time now). However, there is no shortage of other randomisers (some with very basic and short descriptions) that have been used in fairly noteable fan-made or commercial games.

Note that I have abridged the post enormously (leaving out discussion of myriad of modes that might be interesting for analysis) just to emphasise a somewhat more focused question about which it seems not much is known: " Suppose we set certain rules of play regarding the falling tetrominoes -- coming under points (1) and (2) in my description above. Given a certain randomiser, how do we find out that endless play is possible in general or not? " It would be interesting to see some progress on this question regarding reasonably large classes of randomisers.

P.S. Randomisers also include probabilistic considerations with them, which I glossed over (which might only be relevant if we are interested in questions beyond just a guaranteed winning strategy). For example, the more strict definition of memoryless-randomiser would be that at "any" point in the game, regardless of what finite sequence of tetrominoes was handed over, the probability for every tetromino(to be the next one) would be 1/7 (uniform across tetrominoes).