As many computer- and video-game players have long known, the insanely addictive, immensely popular game of Tetris is tough. You can’t really win; you merely try your best to improve upon previous results.
The game was invented in 1985 by mathematician Alexey Pajitnov, then a computer engineer at the Academy of Science’s Computer Center in Moscow. The game board is a rectangular grid of squares, initially occupied by a given configuration of filled squares. The player is given, one by one, a sequence of what are called p tetrominoes. A tetromino is a set of four squares (or blocks) arranged into a larger square, a “T,” an “L,” or some other configuration. Each piece starts in the middle of the top row of the game board and falls downward at a constant speed. As it falls, the player can rotate the piece or slide it sideways.
Pieces travel downward as far as they can go, then stop, permanently fixed in place. As soon as one piece reaches its resting spot, the next one begins its descent. If, when a piece comes to rest, all the squares in an entire row of the grid are filled, that row is cleared. All higher rows drop down one row. A player loses when a new piece is blocked by filled grid squares and cannot descend at all. The player’s goal is to maximize his or her score, which increases as pieces are placed and rows cleared.
Now, Erik D. Demaine, Susan Hohenberger, and David Liben-Nowell of the Massachusetts Institute of Technology’s Laboratory for Computer Science have analyzed Tetris from a computational perspective, focusing on the computer resources required to play the game successfully. In effect, they determined the relative running time or amount of memory a computer would require to play the game in its most demanding form.
The researchers initially focused on a version of Tetris in which the player knows the identity and order of all the pieces that will be presented. They also allowed the player an arbitrary number of shifts and rotations before a piece dropped into place.
We studied this version “because its hardness captures much of the difficulty of playing Tetris,” they remarked. “Intuitively, it is only easier to play Tetris with complete knowledge of the future, so the difficulty of playing the offline version suggests the difficulty of playing the online version.”
To get a measure of the computational complexity of Tetris, Demaine and his coworkers considered a generalized version of the game–one in which the game board grid could be any number of squares wide and high.
In this context, the computer scientists discovered that maximizing the number of rows cleared while playing the given sequence of pieces belongs to a category of problems described as NP-complete. An NP problem is one for which it is relatively easy to check whether a given answer is correct, but may require an impossibly long time to solve by any direct procedure. Interestingly, the computer game Minesweeper also belongs to the NP-complete category.
It turns out that other goals of Tetris, such as maximizing the number of pieces placed before a loss occurs or minimizing the height of the highest filled grid square, also belong to the NP-complete category. So, even if you know all the pieces in advance and can take as long as you want for each move, the game is still challenging.
Demaine and his collaborators also looked at other variants of Tetris. They evaluated, for example, the effect of restrictions on rotations, limitations on player agility, and the use of smaller sets of different tetrominoes.
What about the computational complexity of the actual game, where the sequence of pieces is generated randomly and the pieces can fall very quickly? That’s still an open question.
