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."
... because object recognition is hard for computers? Tetris is all about putting things where they fit, not some grand master strategy. And us biological constructs have an advantage, where we can more or less decide on the fly if X piece will fit decently enough in Y hole without having to go through a bajillion IF-THEN logic loops.
"The only way to win is not to play."
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.this is what we do in our spare time. but seriously, the lcs has declined much since i've come to mit. i think they got too complacent with too much money during the internet boom and started putting huge capital in go nowhere projects like project oxygen. and now things like this. i shake my head. and now they have so little money, they can't support grad kids like me anymore who are the ones who really drive the research in my opinion. sigh. i remember being awed before coming here at the things this place used to research and churn out. how sad.
I don't think the "N remains small, no matter how you look at it" - consider the case where many hundreds of pieces are played - certainly not unusual among higher level players. A number of this magnitude is certainly enough to make many NP problem intractable.
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)
we do know...the mechanism by which it works
Which is it? Either we know how it works or we don't. If we know how it works (same as ANNs?) then fine, go ahead and make assumptions based on that. If we don't, then don't make those assumptions. Just because people have evidence to support theories doesn't mean they can be stated as fact. We do not know how the brain works.
These kids think that if it was made before they were born, the inventor must be dead.
Hmmph.
.sig last updated Jan. 14, 2000
That is, the tetris problem scales intractably with column size, not necessarily with piece count. My impression is, if I say, for example, that checkers is NP-complete, then I am talking about the complexity involved in looking n moves into the future, or computing an optimal solution for the next n moves, rather than the complexity of increasing the board size to n * n.
Furthermore, I'm unsure that the dynamic algorithm that allows the piece size dependency to be polynomial is really so simple - they leave it as an excercise for the reader I suppose!
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).
And that is wrong too.... Because NP means "Non-Deterministically in Polynomial time". This means you *can* solve the problem in polynomial time, but that you need to approach the problem by attacking it in a parallel way. Look at it this way: if you have a problem that needs 2^1000 different calculation and each of those calculations lasts 1 day. Given you have 2^1000 computers, you can solve the problem in 1 day, which is *definately* polynomial (it's constant!)
Now, please explain *why* those statement are wrong for parallelism and non-determinism (I know that non-determinism != parallelism, but it's a way to *illustrate*). That's the way I used to remember the difference between P and NP, worked fine you know. Of course, I'm willing to learn if you know so much better.
You are right that not every problem is parallelizable. Your example doesn't really "solve" anything, it just displays a list of "hello" encrypted with 2**1000 different keys. But even then it is synchronizable, let each of your computer start the encryption 1ms apart and send it to a queue: the results will come in nicely sequential and you have your result. This would take very very very long (since 1ms * 2**^1000 seconds = very very long), but it would be Polynomial time. Polynomial time does not imply "in our lifetime". Note also that you would only need 86400000 computers, since after 86400000ms the first one is done and can start the next calculation.
A better example would have been this:
String unencryptedMessage="Hello World";
String encryptedMessgae="fqwdwezufzd";
for( verylong key=0; key < 2^1000; key++ ) {
if ( encrypt( key, unencryptedMesage).equals( encryptedMessgae ) ) { System.out.println( "The encryption key is: " + key ); }
}
This is solving a problem: namely finding the key of a known encrypted message. And very easy to solve when computing non-deterministically. Just let each of your nodes do exactly one calculation. Things like DNA-Computing and Quantum computing are based on this philosophy: try everything at the same time and filter out the result.
I have to admit that my thinking was more in the lines of the classics like Travelling Salesman, or the one with the boolean expression where you have to fill in booleans in order to get it true with a give set of operators.
Finally, since all NP-hard problems can be reformulated as another NP-hard problem, it is should be possible to transform any non-synchronizable (ahem!) NP-hard problem into a synchronizable NP-problem. Not sure about that, as said... long time ago I had that course.
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.
Is this that hard to comprehend? It's one word that is missing that makes the statement false, and that is it.
The point is: We KNOW that NP-hard problems are solvable in polynomial time, just NOT in a deterministic way.
The question here is not at all if NP=P, since NP is defined as "Solvable non-deterministically in Polynomial time" and P is defined as "Solvable deterministically in polynomial time". *sigh* Hence: both techniques solve in Polynomial time only the way of processing is drastically different in order to archieve a solution.
You know, you forget stuff while aging....
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