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.

There are many things that can be found online about the game Tetris: high scores (see for instance this great documentary), implementation details (did you know there was a specification for Tetris games?), intellectual property surprises (this post is not related to or endorsed by The Tetris Company)... But for many years I have not been able to find on the Internet the answer to this question: can you be sure to clear a line at Tetris?

Of course, in practice, most Tetris players seem to be able to clear lines at least some of the time^{[citation needed]}. But maybe they are just being lucky! Maybe an evil computer or extreme bad luck could prevent you from ever clearing a line, no matter how you played. For instance, consider the game Hatetris, which is programmed to give you unpleasant pieces. Clearing a line in Hatetris is much more challenging, though good players can do it. Could a worse version of Hatetris, with a more clever opponent, give you pieces that will always make you lose without scoring a single line?

Mathematically, we can formulate this a sequential zero-sum game with perfect information. We have a standard Tetris board of 10 columns by 20 rows. The computer and human play alternatively: the computer gives a piece to the human (one of the seven tetrominoes), and the human responds by positioning it somewhere according to the usual Tetris rules. If the screen is filled up then the human has lost, and if the human completes a line then the human has won. Mathematically, there are then only two possibilities:

• either the computer has a strategy to give pieces (depending on how the human has played so far) that guarantees that the human will lose without completing a single line, no matter what they do;
• or the human has a strategy to place pieces that guarantee that they will score a line before losing, no matter which pieces they receive from the computer.

My question was to figure out which one of the two is true. The same question was asked by qntm in 2011, but leaving the question open for the standard Tetris board size. After some coding and much computation, it turns out that the human wins: it is possible to guarantee a non-zero score when playing Tetris. If you want to see an example strategy, you can test it with the Tetris board below. You play the computer, i.e., you select which piece to give, and the chosen piece will be placed according to a winning strategy. Try preventing your opponent from scoring a line! (the point of this post is that this is impossible)

Your navigator does not support iFrames, please go here.

An alternative challenge: try preventing the computer from scoring a line in the 5 bottom rows! This is possible for precisely 759 piece sequences out of the 427513 winning sequences. Can you find them?

In the rest of the post, I explain some details about the exact problem statement, and give more details about the strategy and how to check it. Then, I explain how I computed the strategy, possible improvements to the computation, and then present related work and remaining open problems.

Technical details

Here are some detail about the problem and strategy:

• I restrict the human player to only rotate and then drop pieces vertically, i.e., playing a piece means choosing a rotation and a column where to drop it. (You cannot slide a block under another block, no t-spins, etc.) Of course, if the human can win under this restriction, they can win even when we allow more moves.
• I do not require the computer to show the next piece, i.e., commit to what the next piece will be before the human has dropped their current piece. Of course, if the human can win in such conditions, they can also win with a next piece display.
• Under such circumstances, the human can play so as to guarantee that they can complete one of the lowest 6 rows of the board. The exploration also shows that the computer can prevent the human from scoring one of the bottom 5 lines, subject to the above restrictions, and assuming that the human does not play "above" the fifth line, i.e., dropped pieces cannot touch a full column which has height at least 5. (See below to know more about this limitation.¹)
• In the worst case, the human needs to position 13 pieces to complete its first line among the bottom 6 rows. This is optimal under the above restrictions: when only considering completion of the first 6 rows, dropping pieces without sliding them, and prohibiting dropped pieces from touching a full column. I think it is very likely that the human can win faster if we allow the player to slide pieces; and possible that the human can win faster by going above the 6th row.
• Where several moves achieve the same distance to a win, they are chosen arbitrarily, following the order in which the possible choices of where to put a piece are considered (first by rotation, then by column). This is why the strategy above is not symmetric, e.g., between l-shaped and j-shaped tetrominoes.

Checking the strategy

I provide the strategy as a file describing how the human can play and guarantee a win. Each line of this file corresponds to a possible "game state", numbered from \(0\) to 5249 (the file has 5250 lines²). Each line consists of 21 integers, numbered from \(0\) to \(20\) as \(3p+q\) with \(0 \leq p < 7\) and \(0 \leq q < 3\). The triple \(3p, 3p+1, 3p+2\) explains what to do when receiving piece \(p\): the number \(3p\) indicates the rotation \(0 \leq r < 4\) to use, the number \(3p+1\) indicates the column \(-2 \leq c < 10\) where to drop the piece, and the number \(3p+2\) indicates the game state from which we should follow the rest of the winning strategy (the special value "-1" indicates that the player has won). The pieces, rotations, and column offsets are according to the following description of the pieces:

== piece 0 rotation 0 ==
#...
#...
#...
#...
== piece 0 rotation 1 ==
....
....
....
####
== piece 0 rotation 2 ==
...#
...#
...#
...#
== piece 0 rotation 3 ==
####
....
....
....
== piece 1 rotation 0 ==
.#..
##..
#...
....
== piece 1 rotation 1 ==
....
....
##..
.##.
== piece 1 rotation 2 ==
....
...#
..##
..#.
== piece 1 rotation 3 ==
.##.
..##
....
....
== piece 2 rotation 0 ==
.##.
##..
....
....
== piece 2 rotation 1 ==
....
#...
##..
.#..
== piece 2 rotation 2 ==
....
....
..##
.##.
== piece 2 rotation 3 ==
..#.
..##
...#
....
== piece 3 rotation 0 ==
###.
.#..
....
....
== piece 3 rotation 1 ==
....
#...
##..
#...
== piece 3 rotation 2 ==
....
....
..#.
.###
== piece 3 rotation 3 ==
...#
..##
...#
....
== piece 4 rotation 0 ==
###.
#...
....
....
== piece 4 rotation 1 ==
....
#...
#...
##..
== piece 4 rotation 2 ==
....
....
...#
.###
== piece 4 rotation 3 ==
..##
...#
...#
....
== piece 5 rotation 0 ==
###.
..#.
....
....
== piece 5 rotation 1 ==
....
##..
#...
#...
== piece 5 rotation 2 ==
....
....
.#..
.###
== piece 5 rotation 3 ==
...#
...#
..##
....
== piece 6 rotation 0 ==
##..
##..
....
....
== piece 6 rotation 1 ==
....
....
##..
##..
== piece 6 rotation 2 ==
....
....
..##
..##
== piece 6 rotation 3 ==
..##
..##
....
....

The strategy thus describes a DAG (with labeled edges). In particular, we can get to the same game state by different paths, and indeed the same game state can correspond to different states of the board but from which we can use the same winning strategy.

The strategy in this file is the one used in the Javascript game above. I have written a program (with helper file) that checks the strategy by systematically going over all possible moves by the computer, playing according to the strategy, and checking that the human indeed wins when the strategy says they do. Hence, the mathematical "proof" that the human has a winning strategy would consist of this file and of the verification program.

Finding the strategy

I could stop here and say that the strategy and the verification program are an answer to the question I had posed :) but let me say a few words about how I found it. This is performed using the minimax algorithm, i.e., systematically exploring the game tree. Formally, we define inductively who wins on a given board state, among the human (H) and computer (C):

• Base 1: H wins on board states where one of the bottom 6 rows is filled
• Base 2: C wins on board states where we cannot place a piece without touching a full column, i.e., one where there are already blocks above the 6th row.
• Induction 1: In a given board state \(b\) where H is given some piece \(p\), if H can drop it and get to a board state which is winning for H, then \((b, p)\) is winning for H; if all moves by H get to a board state which is losing for H, then \((b, p)\) is losing for H.
• Induction 2: In a given board state \(b\), if C can give H a piece \(p\) such that \((b, p)\) is losing for H, then \(b\) is losing for H; if any pieces given by C are such that \((b, p)\) is winning for H then \(b\) is winning for H.

This is just a simple recursive exploration. The naive way to implement this would be to compute who wins on every board state, remembering in the board state if each cell of the bottom 6 rows is filled or not: this would be \(2^{6 \times 10}\) possible board states, where 10 is the number of columns. This amounts to 1153 peta states, which is too much.

Since we are only allowing pieces to be dropped (without sliding them), we can do better: in each column, we only need to remember the height of the highest completed block³. The status of the cells below the topmost filled cell of a column have no influence on which moves are possible. The only extra thing to remember is the set of rows having a "hole", i.e., an empty cell above which there is a filled cell. As we cannot slide pieces, these holes can never be filled, so we must remember that the rows that have a hole cannot be completed. We say that these lines are "sacrificed".

For an example, consider the state of the board after dropping a vertical I-tetromino in the second column, pictured below. We represent this as the sequence of heights written at the bottom.

Imagine now that we drop a vertically oriented z-block, getting to the configuration below:

Columns 2 and 3 are now full, i.e., the blocks stack up to the 6th row. Hence, we store their height as 6, and forget what happens above the 6th row (i.e., we forget the block in column 3 with a black cross) -- because of this, we will no longer allow blocks to touch one of these full columns. Further, the new block has now created holes -- the gray cells with red crosses. The sequence of heights does not account for these holes; to remember that they are there, we store that the bottom 5 rows have been "sacrificed", materialized by the red crosses to the left of the board. This is sufficient, because our way to drop pieces will never allow H to slide a piece and fill these holes. Now, the 6th row is the only row where H can ever hope to complete a line. (In fact, the configuration is now clearly losing for H: if C no longer gives H any I-tetromino, H can never fill the cell at column 1 and row 6, so H can never complete the only non-sacrificed line.)

To summarize, the board state consists of the height of each column (between 0 and 6 inclusive) and the set of sacrificed lines, for a total of \(7^{10} \times 2^6\) board states. This is much better: there are now 18 billion states. There are other small savings, e.g., board states where all lines are sacrificed are immediately losing. In practice, a complete exploration considers around 2 billion states, i.e., only around 11% of the possible board states are reached.

For efficient implementation, a board state is represented as a 64-bit integer consisting of a 16-bit mask describing the sacrificed lines (only the 6 lowest bits are useful), and 10 4-bit integers describing the heights (only the 3 lowest bits are useful).

As the same board state can be reached by many different paths in the game tree, we use memoization: when we are done exploring the tree from some board state, we remember whether this state is losing or winning, and if it is winning we remember in how many moves. This is done with a hash table (a C++ unordered set). This means that the program requires a large quantity of RAM to run (around 20-30 GB): for this, I thank the INFRES department at Télécom Paris for giving us access to suitable computing resources.

This explains how the winning strategy is found. It is fast (one hour) to check that a winning strategy exists by terminating the search for a board state and piece as soon as a winning move is found. It is longer (18 hours) to find a strategy that wins as fast as possible, because this requires us to explore the full tree. To speed things up, we use a form of alpha-beta pruning: when trying to put a piece, when we have found a winning option, we consider other options but only exploring them up to a depth that would give a strictly shorter strategy than the currently known best option. This lowers the running time to 10 hours and lowers the number of explored states from 2 billion states to around 750 million states, of which 9 million are winning. The resulting program is here. (Sorry, it is not very clean...)

Once the program has produced a strategy, we need to "compress" it. To do so, we first "trim" it by removing unreachable board states: we go from 9 million states to just 21 thousand states: this is done here. Then we minimize it by merging states from which the strategy is the same: this is done here. As the DAG is acyclic, we can perform this in linear time simply by processing the DAG bottom-up and hashing configurations. We get to the 5250 states of the strategy file.

Other possible optimizations

The following optimizations would have been possible, but I did not implement them:

• There would be an easy saving of a factor 2 by breaking the left-right symmetry, which would also probably make the winning strategy more concise (but it is less convenient to reconstruct it).
• When checking the cache of possible board states, we could check "shifted" configurations where we remove any one of the lowest \(d\) lines, provided each column has a height of at least \(d\). We could also check configurations with a subset, or superset, of sacrificed rows: if a configuration with identical column heights and with a subset of sacrificed rows is known to be losing then the current configuration also is, and if a configuration with identical column heights and a superset of sacrificed rows is known to be winning then the current configuration also is.
• Rather than exploring all possibilities to the maximal depth before giving up, a better solution is to use iterative deepening. I did this in an earlier version of the code that followed a different approach. Likewise, ordering the possible moves with a piece using some heuristic (e.g., putting the piece as low as possible, or sacrificing as little new lines as possible) would possibly make the search faster (thanks to alpha-beta pruning).

Related work

The most related work is the 2011 study by qntm, which set out to solve the same question. His work did not conclude that the human had a winning strategy for the standard board size of 10 columns, though the cases with less columns were solved. The analysis showed that a height of 6 was not sufficient to have a winning strategy. For qntm's analysis, playing up to height 6 means not allowing a piece to protrude above line 6, whereas for me it means not allowing a piece to land on a column that goes to height 6 and not considering filled lines strictly above line 6. This would imply that qntm should find a solution for height 9 or less. A difference is also that qntm considers more moves than simply rotating and then dropping pieces as I do; this may be part of the reason why I was able to conclude the analysis and qntm was not.

For the related question of whether the player can win at Tetris, i.e., play indefinitely, it is known that this is not the case. The computer can force the player to lose, even with a strategy which is oblivious to how the human plays and alternates S-shaped and Z-shaped pieces: see Burgiel's 1997 paper "How to Lose at Tetris" or this page. This does not contradict the result presented here, which says we can clear a line (but eventually lose). Optimizing the number of lines cleared (in the worse case or in expectation) vs guaranteeing that you make one line are different goals, that may be at odds with each other.

On the other hand, with stronger assumptions on how the computer can propose pieces, it is possible to play forever: see this page.

There are other results of this kind in Brzustowski's 1992 master thesis Can you win at Tetris?.

There is a 2002 study by Demaine et al. of the computational complexity of Tetris play, which does not seem related to the results here. For more related work on Tetris, there is a great literature review in this FUN'2022 paper by Dallant and Iacono.

There are many Tetris implementations that try to give the worst possible pieces to the player: at least Hatetris, bastet, and LTris in "expert mode".

A relevant question seems to be the study of "adversarial Tetris", introduced at a reinforcement learning competition in 2009 (see here), and followup, e.g., Beatris. However, I wasn't able to find works in this area which considered the question of whether the human could guarantee that they score at least one line assuming perfect play.

Open problems

I do not know what is the minimal number of rows and/or maximal necessary height to score a line if the human can slide or rotate pieces as they fall; the latter would depend on the exact rules implemented for rotation which is somewhat unpleasant (similar subtleties are considered in Demaine et al.'s paper).

I do not know what happens for a different number of columns. Odd number of columns clearly allow the computer to win by giving only square tetrominoes, and two columns clearly allow the human to win (every piece can score a line by itself in every configuration except I-tetrominoes where this can be achieved in two moves). Of course one can generalize the problem to different polyomino sets, etc.

I do not know if the human can guarantee scoring multiple lines at once: if the computer only gives O-shaped blocks then the human cannot hope to score three or four lines at once⁴; I don't know if guaranteeing that you can score two lines at once is possible.

I do not know if the result implies that the human can score any arbitrary number of lines provided that the board is sufficiently high. The strategy I presented does not ensure this, because it only works from the empty board; it could be the case (although unlikely) that the board states reached after scoring one line in this strategy no longer themselves have a winning strategy (no matter the height). More generally, one can ask what is the behavior of the function that maps the number of rows of the board to the number of lines that can be guaranteed by the player.

After at least 10 years, I thought it was time to revamp my home page. The main goal was to make it more focused towards my current activities. I also wanted to make it less frightening, by having text instead of bullet points.

I have also tried to avoid presenting my research as a list of publications: I think that publication lists are hard to understand outside a specific area and do not show the big picture. Accordingly, I have written a high-level presentation of my research to make it more understandable, and will try to keep it up-to-date. I am also considering to announce new results (e.g., posted papers) on this blog, which I think is more interesting than simply updating a list. Of course I still have a list of publications on a dedicated page for those interested.

Another novelty is that I now have a list of students I supervised, and a list of internship and PhD offers for prospective students.

I'm honored to be part of the team behind the new open-access journal in theoretical computer science, TheoretiCS, which just opened earlier this month.

The goal of TheoretiCS is to publish the best papers in all areas of theoretical computer science, while guaranteeing a fast turnaround time (3 months for a first opinion). It is a diamond open-access journal, which is free for readers and authors: the articles are hosted on arXiv following the overlay journal model, and the reviewing platform¹ is Episciences, which is open-source software hosted by the CNRS CCSD. The journal belongs to an independent nonprofit, which avoids any interference from for-profit publishers and also from the large scholarly societies that are currently failing to ensure the free dissemination of our work.

I am involved in TheoretiCS as a "managing editor", together with Nathanaël Fijalkow. We are in charge of handling technical aspects of running the journal and making sure everything is going smoothly and steadily. :) For now, our main work has been to study how to adapt the Episciences platform to the needs of the journal, to open issues, and to document how to use the platform.

I am impressed by the journal's editorial board, its distinguished endorsers, and its representatives for many of the major computer science conferences. Making all of this happen has been underway for several years by the team; I only joined rather late, at a point where the editorial board was mostly finished.

I hope that this journal will be a success and an example of how research should be published in the 21st century, i.e., entirely online and at no cost. My involvement in this effort is in line with my commitments towards open access, and I hope it can help make things move in the right direction.