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."
I think what is meant is, if the number of pieces is finite then finding a configuration for putting them without gaps is not polinomial in number of pieces.
ato
Because games can provide real world analogues. Yeah, I'm going to invoke Nash and his game theory. When he was studying at princeton, a large portion of the mathematicians there played games, some of which were invented at princeton based on some mathematical notion of some sort. Lots of those dumb little puzzles that you see in hobby shops have rigorous mathematical treatments. Moreover, a classic problem in computer science is to reduce one problem to another, so imagine taking a real world problem and modeling it as a simpler problem with the same characteristics. Say, a game. If you can analyze the game, then you've got at least a suitable starting point for analyzing the real world problem that you're actually interested in. Now, I don't know what practical application that knowing the approximation characteristics of optimizing parts of a tetris game are, but of the cuff I could see it having applications in packing problems or flow control (particles through a pipe?).
So, to answer your assertion that these studies are getting dumber and dumber by the day, I'd counter that while it may not produce immediate practical results, I could see this analysis being used elsewhere.
Humorless sig goes here.
If you are good at tetris you can play online tournaments at Worldwinner.com against an or some opponents.
The nice part: you bet real money. If you are somewhat good you can make some cash. I really made 25$,around 37$CDN. I stopped since it was too hard to win when I was classified as "intermediate" and I was loosing all my earnings I won "newbie".
Try it at your own risk.. Very addictive. You get 5$ free when you join. Everything is VeriSign Certified.
It isn't the Space Shuttle, it's the Buran, the russian Version of the space shuttle. AIIRC you needed 250000 points for it to launch, or 25 PERFECTS in game B. After getting a Buran, i quit tetris cold turkey.
... whenever a text is transmitted, variation occurs. This is because human beings are careless, fallible, and occasiona
The authors carefully defines that a Tetris problem is a starting board and a series of Tetrominoes. Several computational objectives are then defined, such as "can a game be played wherein k rows are collapsed?" or "can the board after the last tetrominoe have at most height k?".
So it is really a mathematical version of Tetris, but it applies to regular Tetris in that there are certainly games that simply are too hard for you.
Reality or nothing.
The inventor of Tetris is alive and well. In fact, I just saw him give a talk while visitng UIUC at their Reflections and Projections conference.
How is this modded up as insightful??? Object recognition has nothing to do with this being hard. Read what it says on the bottom of page 2:
That's just wrong.
If you read the article, you would see that the fact that tetrominos (that's what they call 'em) are four block combinations does not define the magnitude of the (likely, assuming P != NP) exponential relationship. In fact, they show that the problem scales in an NP fashion with the number of pieces - the number four doesn't come into it.
What the Nintendo version shows is that a simple AI (with perfect movement abilities) and so on can come close enough to optimal in a usual situation (the article presenet an extremely contrived worse case scenario) to beat a human player. This has no bearing on the NP completeness of the problem.
On another note, the authors admit that the Tetris problem is NOT NP-Complete except for arbitrarily large game fields.
(1) Eliminating all blocks on the playfield in a minumum number of moves.
(2) Maximising the possible number of tetrises obtained.
(3) Maximising the number of lines cleared.
(4) Minimizing the height of the block configuration.
Note that they prove (1) essentially by starting from a very particular arrangement of blocks on the playing field, such that the reduction to 3-Partition is "easy" to prove (I use the word "easy" in the loosest sense). They then go on to prove (2),(3), and (4) using small modifications to the basic setup.
The admit that the "empty initial field" problem is an open one, but I would imagine that that problem can also be proven NP-Hard.
http://www.math.uic.edu/~burgiel/Tetris/explanatio n.html
Has a great article about this. Essentially, in a truly random Tetris game, getting a long sequence of alternating Z and S pieces will make it impossible to complete the board; they're thicker in the middle than the sides, meaning you'll build up a little tower in the middle, no matter how good you are.
The page has links to a version of Tetris with only those pieces, if you want to try your luck on it.
Perhaps you are wondering what an NP-complete problem is or what this P vs. NP stuff is all about. You might want to check out the comp.theory FAQ and scroll down to 7. P vs NP. It gives a bit of history and a decent description.
Or check out The P versus NP Problem at Clay for a really good description (unfortunately too long to quote here). And lastly, you might want to check out Tutorial: Does P = NP? at VB Helper for a little more info.
Ok, but what is it good for? The Compendium of NP Optimization Problems is a great place to look for real world examples of NP problems. Including everything from flower shop scheduling [nada.kth.se] to multiprocessor scheduling.
Hopefully that helps. I was very clueless when it came to P vs. NP stuff that always seems to be mentioned on Slashdot. So I took the time to look it up. Now I'm clueless but I have links to share. :)
-- null