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
How the hell do you win at tetris?
The best Tetris game that I remember playing was Super Tetris. It had a bunch of extra features compared to classic Tetris, and 10 different levels that you could complete. The best feature was the ability to save/reload the game, so in higher levels I would just reload the game every time I made a bad move, and completed the game this way.
You may be able to find it on some abandonware site, it is lots of fun.
When men used to be men
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
Alexey Pajitnov.
Read the article, it is amazingly accessible.
Humans and NP problems
There are two things people look at when they find a new NP problem. First is reducing a currently known NP problem to the new problem. In this case, they reduced the 3 bucket problem. Second is the difficulty of approximation. Apparently Tetris also happens to be difficult to approximate. Humans happen to be _really_ good at approximation, while sucking at exact calculations. That is the whole reason we designed computers in the first place.
Note for those who don't read the article. Their proof is _not_ for a basic tetris game. They assume a prebuilt structure that you are trying to fit pieces into. This structure is designed to allow the mapping from the 3-bucket problem to Tetris. They specifically mention the starting point of an empty board as an open problem.
Crispin
----
Crispin Cowan, Ph.D.
Chief Scientist, WireX Communications, Inc.
Immunix: Security Hardened Linux Distribution
Available for purchase
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.
Crispin
----
Crispin Cowan, Ph.D.
Chief Scientist, WireX Communications, Inc.
Immunix: Security Hardened Linux Distribution
Available for purchase
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.
In the center? That gives you two narrow columns to build. I always leave the single block wide path at the extreme left or right.
(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.
You are partly right; it is never NP-complete. It is also often solvable. However, in the general case it is not solvable - sometimes you just have to guess.
In fact, take the first move you have to make and tell me with 100% certainty that you're not clicking on a mine. You can't - the problem is not solveable.
Not-losing tetris is impossible in the long term. All you need to loose is a very long sequence of Z and S pieces. These pieces don't tile the plane. Even if a normal tetris game program may forbid such sequences, your "any arbitrary sequence" definition clearly includes such seq.s
As far I as remember you only had to beat game mode B with speed 9 and high 5 (half the screen filled at start) to win. (or get that high score in mode A)
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
> the case of a constant-size gameboard in time
> polynomial in the number of pieces
Here is one relatively simple dynamic programming solution.
Suppose the game board has size k. Each cell in the game board can be either on or off, so we can represent the state of the board in a bit vector with k bits. Now define a recursive procedure that takes a sequence of n blocks and a state of the game board as input:This will calculate the optimal solution, but unfortunately the program runs in exponential time. To fix that, observer that solve will only be called with 2^k * n different sets of parameters. This means that since the function only does constant work when we disregard the recursive calls, caching the results of calls to the procedure in a table of size 2^k * n, we can make it run in time O(n).
Note however that the O here is hiding a constant of size 2^k, where k is the size of the game board. This means that this algorithm, while nominally O(n), is not practical when the gameboard gets even moderately big.
They have shown, by reducing one NP-Complete problem to Tetris with full-lookahead, that optimal Tetris with full-lookahead is NP-hard.
Now, the reducing works by taking any instance (i.e. input) of the original problem and converting it into an instance of the tetris problem, not the other way around. So the conversion won't produce all possible Tetris games, in fact only a very restricted class of them.
This ignores two important aspects of Tetris playing:
The game is not bound by the number of pieces (so suboptimal behaviour is not really a problem)
The game is played with *random* input sets
But, as always, it's very easy to discuss something that you have no idea what it means. And, btw, being NP-complete or NP-hard doesn't mean necessarily exponential complexity (neither P=NP nor PNP have been shown).
The Raven
The Raven