Slashdot Mirror
Tetris Is Hard: NP-Hard
bughunter writes "Analysts at MIT Laboratory for Computer Science, who have been busy translating, rotating and dropping, have demonstrated what the rest of us suspected: Tetris is hard. Technically, it's 'NP-hard,' meaning that there is no efficient way to calculate the necessary moves to "win," even if you know in advance the complete order of pieces, and are given all the time you need to make each move. At least there's one geek classic that refuses to fall to the scrutiny of mathematicians."
Technically, it's 'NP-hard,' meaning that there is no efficient way to calculate the necessary moves to "win"
It is more correct to say that "there is no known efficient way to calculate the necessary moves to win, and it is unlikely that one will be discovered." Technically, there is no efficient method unless P = NP. See Garey and Johnson for details.
At least there's one geek classic that refuses to fall to the scrutiny of mathematicians.
Actually, even the (surprising, novel, and cool) approximation results only tell us about the asymptotic complexity of the game, and then only of the "offline" game in which you know the sequence of pieces that will be coming. Note that optimal restacking of blocks is also asymptotically NP-hard and inapproximable [Gupta and Nau], but quite tractable for humans and machines even for very large stacks in practice. Short version: in spite of these results, a good AI programmer can easily build a Tetris-playing program that will kick your sorry human behind :-).
One assumption in the paper that I disagree with is that "intuitively" the offline version (full knowledge of piece sequence) should be easier than the version in which the piece sequence is not known. My intuition says the opposite: in the online version, the most one can do is optimize one's probability of a win. This more modest goal should be easier to attain than the loftier goal of "prove a win if one exists".
My question is this: How is it Nintendo et. al. can program an incredibly skilled Tetris AI, but scientists at MIT cannot?
First, a disclaimer- IHNRTFA. But still, my guess is that the optimal solution is NP-hard. That is, given the exact sequence of blocks, give the sequence of moves which will get rid of them all as fast as possible and/or with the highest score possible. If you just know the current piece, you have about 48 moves to evaluate (assuming it's like 12 blocks wide and there are 4 possible rotations). If you know the next you have 48^2, but even an NES could probably evaluate those faster than you could given some simple cost function. A lot of computer science is coming up with approximations which are close to optimal (ie they beat humans or at least don't pile up and die) while remaining computationally feasible.
Uh, I was just reading the full paper and came to this comment which summarizes an important fact omitted in the abstract:
In other words, "normal offline Tetris" (whatever that means) may still be in P. (And, BTW, when they say "complicated", they really mean it: check out the full paper for details.) Sigh.Pay attention to page three: It is natural to generalize the Tetris gameboard to m-by-n, since a relatively simple dynamic program solves the case of a constant-size gameboard in time polynomial in the number of pieces
I guess this means that hey, they are talking about something else that the normal constant-size gameboard!
Also, page 25, gives a subtle hint that this is not about standard Tetris:
What is the complexity of Tetris for a gameboard with a constant number of rows?
What can we say about the difficulty of playing online Tetris if pieces are generated independently at random according to the uniform distribution?..
Also, the authors concentrate on playing optimal with respect to the number of lines cleared and the number of tetrises achived (either objective, not both) - and do not concentrate on, say, not losing (They give references to the hardness of not losing in the first chapter)
I miss my rubber keyboard.(Homepage)
These kids think that if it was made before they were born, the inventor must be dead.
Hmmph.
.sig last updated Jan. 14, 2000
True, but the state space of go (or chess) also stays small, yet this does not prevent the optimal play problem from being intractable (on today's hardware, with today's algorithms). The difference is that to analyse possible future moves beginning from the current (small) state space, a program (traditionally) must investigate a huge, typically exponential, number of possible future state spaces, based on possible future moves, etc.
Note that the version of tetris considered in the paper is the offline version, where the sequence of pieces is known in advance, rather than just the next piece - certainly if they considered the model of the game where only the next piece was known, then deterministically optimal play would be impossible, rather than simply intractable, and the question would be a probablistic one instead. For example it has been shown that the optimal solution for the Mastermind style of game is calculable in a probabalistic sense, yet is intractable (due to the size of the payoff matrix).
1) The Nintendo AI doesn't have to be optimal. It just has to be better than a human.
2) Being better than a human at Tetris is less about placement than it is about agility. You may be better at figuring out where pieces should go, but the Nintendo will always be better at actually getting them into place.
3) The problem Nintendo solved is much more tractible because it only deals with two pieces at once. The problem MIT posed deals with the entire sequence, potentially hundreds of pieces. The problem is (probably) exponential, so each additional piece that must be considered makes the problem about 20x harder.
But interestingly enough, then I decided to see whether the game was deterministically winnable, or only statistically winnable -- so I used the same strategy algorithm to "cheat" by always picking the piece that was hardest to fit, and then presenting that piece as the next one for the human player to deal with.
Both when I played, and when my autoplayer algorithm played, we always lost immediately without being able to remove even one row. It is truly maddening to get absolutely nothing but the "wrong" pieces. Even in slow motion, they just don't fit.
The way to interpret this is that tetris is unplayable in the absolute worst case of bad luck, but that it is strangely nicely tuned so that it is winnable in a statistical sense -- for a while .
But even if it doesn't speed up too much, eventually you'll run into a statistical streak of bad luck with just the wrong pieces, and you will lose! Guaranteed.
Alexey was a friend of a friend at the time, and I mentioned this result to him. He said he was not at all surprised, but didn't say much else about it.
Professional Wild-Eyed Visionary