“Tetris is NP-Complete” – D. Demaine et al.
Brief history:
Tetris is a popular computer game that was invented by mathematician Alexey Pazhitnov in the mid-1980s.
Terminology:
- Board (B): Grid of m rows and n columns, indexed from bottom-to-top and left-to-right.
- Tetris piece type: There are 7 types of tetris pieces that can appear in the game (shown on the figure below)
- Position: This refers to the position of a tetris piece on the board i.e. the grid it’s center is located on the board.
- Orientation: This is the change in angle of the piece from it’s base orientation in the number of degrees clockwise. A piece can have an orientation of 0°, 90°, 180° and 270° from it’s initial orientation.
- Fixed/Unfixed: Before a piece lands on a previously placed tetris piece, it is in an unfixed state. Otherwise, its fixed.
In this post, we examine the paper – Tetris is Hard, Even to Approximate by Demain et al. The question we are going to answer is: How hard is it to maximize the number of rows cleared while playing Tetris?
In order to answer this question, the “offline” version of the tetris game was analyzed. The offline version enabled the player to have advance knowledge of the tetris pieces in the game and the order in which they will appear on the gameboard. The player is also allowed to change orientation and position infinitely many times before the piece moves a grid down.
Show that Tetris is in NP
Given a game, G=(B, P1,P2,…,Pn) where B is the initial board, and P1 to Pn are tetris pieces in that order, show that Tetris is in NP.
Proof:
Certificate: An acyclic trajectory sequence ∑.
Goal: To confirm that ∑ is a legal, acyclic trajectory in poly(|G|).
Each piece has a trajectory of at most (4*|B|+1) states, (4|B|) states where the piece is unfixed on each orientation, and one in a fixed state. This is a total of n*(4|B|+1) trajectory for all n pieces in the game.
Since ∑ is acyclic, then are no repeated patterns in the pieces. Thus, to check that ∑ is a legal acyclic trajectory takes n*(4|B|+1) steps which is in polynomial time.[2] 𞠡
Show that Tetris is NP-complete
Tetris: Given a tetris game G=(B, P1,P2,…,Pn) , does there exist a trajectory sequence, Σ, that clears the entire game board?
3-partition problem: Given a sequence of non-negative integers, {a1,…, a3s}, and an integer T, can the sequence be partitioned into s disjoint subsets, A1,…,As , so that for all 1≤j≤s, we have ⅀(i∈Aj) ai=T?
The 3-partition problem is NP-complete and by reducing it to the Tetris problem, we show that Tetris is NP-hard. This combined with the fact that Tetris is in NP, would make Tetris NP-complete.
Proof: 3-partition reduces to Tetris: i.e. for any “yes” instance P={a1,…, a3s,T} of 3-partition, there is a trajectory sequence that clears the entire gameboard of G(P) without triggering a loss.
Since P is a “yes” instance, there exist a partition of {a1,…, a3s}, into sets A1,…,As such that ⅀(i∈Aj) ai=T.
Begin with the initial gameboard shown below:
The first 3s+O(1) rows are empty and for rotations and translations. The white spaces are the buckets. There are s buckets, 6 columns wide, each corresponding to sets A1,…,As in the instance of 3-partition. The last 3 columns of the gameboard forms a lock which blocks access to the last column. Until a piece is placed into the lock to clear the top two rows, no lower row can be cleared.
An overview of how the game would work with that setting is showed in the following picture.
The tetris instance G(P) has size polynomial in the size of the 3-partition instance P, since a1,…, a3s and T are represented in unary, and can be constructed in polynomial time. [1]
Discussion
The fact that maximizing the number of rows cleared in the Tetris game is NP-complete seems intuitive. However, the paper was initially hard to follow and understand. Still unclear to us, although the paper tries to clear that, is why when reducing the 3-partition problem to the Tetris problem, that particular initial gameboard (Figure 2) is used and why the lock is necessary. Every other part of the proof is clear.
The paper goes on to prove other problems in Tetris like the problem of maximizing the number of pieces placed before a loss occurs, maximizing the number of times the simultaneous clearing of four rows occurs and so on. These proves are somewhat dependent on the question we focused on.
The proof gives an insight to how complex a similar real life situation should be; a situation where given a limited set of diverse items (in this case, tetris pieces), one has to optimize on a characteristic of their combination (rows cleared).
In our opinion, the paper covers every relevant question about Tetris. However, in future, we hope answers to the question: what number of tetris pieces types makes the Tetris problem polynomial time solvable?
Conclusion
The proofs presented show that Tetris is in NP and, with the reduction to the 3-Partition problem (which is NP-Complete) that Tetris is an NP-Complete game. In this research, we assumed that the board was empty at the beginning of the game and, because we were offline, we knew which shapes were falling and we were able to make them change positions and orientations.
However, at more difficult levels of the game, it may be very hard to make two translations before the piece drops another row in height (we have a faster speed). Suppose each piece can be translated and rotated as many times as the player pleases, and then falls into place but no manipulations are allowed after the first downward step. Is the game still hard?
Contributions:
We, (Dorcas and Astou) shared the work equally and worked together in understanding the paper, making the slides and the web page as well as everything else involved in the project.
References
- Demain et al. Tetris Is Hard, Even to Approximate. https://link.springer.com/chapter/10.1007/3-540-45071-8_36
- Breukelaar et al. Tetris Is Hard, Even to Approximate*. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.110.5860&rep=rep1&type=pdf
- Picture (GIF) of Tetris – https://giphy.com/gifs/tetris-xstpzu2xZE0JG
Is Tetris Np-Complete ? 