Slashdot Log In
Tetris Is Hard: NP-Hard
Posted by
timothy
on Fri Oct 25, 2002 01:21 AM
from the lots-of-chin-scratching dept.
from the lots-of-chin-scratching dept.
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."
This discussion has been archived.
No new comments can be posted.
Tetris Is Hard: NP-Hard
|
Log In/Create an Account
| Top
| 345 comments
(Spill at 50!) | Index Only
| Search Discussion
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
(1)
|
2
(1)
|
2
Winning (Score:3, Interesting)
Re:Winning (Score:5, Informative)
Re:Winning (Score:5, Informative)
(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.
Re:Winning (Score:5, Informative)
Re:Winning (Score:5, Informative)
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.
Tetris is NP-hard! (Score:5, Funny)
Are you goofing off playing tetris... (Score:5, Funny)
They used math to figure this out? (Score:5, Funny)
I don't get it. They used math to figure out that tetris is hard, but math is hard too.
Re:They used math to figure this out? (Score:5, Funny)
Instead of studing for my Linear Algebra exam,
I've been busy proving tecmobowl is NP-Fun!
Hey... (Score:5, Funny)
Re:Hey... (Score:4, Interesting)
Plus, you can use both right- and left-handed L blocks as a makeshift solution if your stack gets too high.
In Other News (Score:5, Funny)
The only way to win at Tetris... (Score:5, Funny)
Re:The only way to win at Tetris... (Score:5, Funny)
Re:Further studies... (Score:5, Interesting)
At least Pacman has a perfect solution [twingalaxies.com]. No fancy math required, just a good hot meal beforehand and a little patience.
It's not that Tetris is HARD... (Score:5, Funny)
I always sucked at tetris... (Score:4, Funny)
Re:Poll (Score:5, Funny)
It's reasurring to know that even HE thinks it's rigged.
So that's why... (Score:3, Funny)
[self duck];
F-bacher
Re:Tetris "ends"? (Score:5, Interesting)
It launched when you reached the final level, I think. I did it once, and was very happy, but it sure wasn't as much fun as the game itself.
If you play the countdown mode (start with 40 pieces at a constant level and eliminate all of them) at the highest level (9, I think, or maybe 10), then when you finish you got to hear all of the instruments playing together (each of the other levels had instruments playing).
The ending of Dr. Mario was a lot more interesting.
man... that is so not fair (Score:4, Funny)
MIT kids do research in TETRIS.
wtf? tell me again why MIT is one of the best engineering school again?
oh wait... i just got it.
Online Tetris tournaments (Score:4, Informative)
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.
I was doing home-work the whole time. (Score:3, Funny)
You'd be amazed at some of the Heuristics you have to use at Level 10!
NOW I'VE GOT MY EXCUSE! (Score:5, Interesting)
Interesting thing about NP-hard stuff, though, especially when it comes to things like video games. There are a group of techniques that work to solve NP-hard problems SOME of the time based around searching. Because there are multiple winning solutions for Tetris, and there is are several quite obvious heuristics to aid in the search (such as planning so that you leave indentations that will fit the next piece(s), and attempting to fill lower lines before higher ones), it's probably still solvable in polynomial time MOST of the time.
Of course, solvable is relative. The optimal solution (highest score) for a finite number of moves cannot be proven without trying all combinations of states, but to simply finish, there are lots of solutions.
My theory (Score:5, Funny)
Wait a second... (Score:5, Interesting)
My question is this: How is it Nintendo et. al. can program an incredibly skilled Tetris AI, but scientists at MIT cannot?
Re:Wait a second... (Score:5, Informative)
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.
Re:Wait a second... (Score:5, Insightful)
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.
Re:Wait a second... (Score:4, Insightful)
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.
Duh (Score:3, Informative)
Crispin
----
Crispin Cowan, Ph.D.
Chief Scientist, WireX Communications, Inc. [wirex.com]
Immunix: [immunix.org] Security Hardened Linux Distribution
Available for purchase [wirex.com]
Not your father's tetris... (Score:5, Informative)
Tetris NP-hardness results (Score:5, Insightful)
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 [amazon.com] 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".
Only proven hard if started screwed up enough... (Score:5, Insightful)
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.Tetiris / Eyeball RSI Warning (Score:5, Interesting)
I used to be a serious Tetris junkie, and played on many different versions on different platforms.
Playing so much, I became "quite good", and this meant that blocks were falling extremely rapidly.
To play tetris at high speed, you glance very quickly at the arriving piece, then move your gaze back to the pile to asses the position - moving the piece without looking at it. Repeat until bored.
Then my eyes packed up. I basically developed something like "RSI" in both eyes - my eyes would twitch repeatedly up and down in the exact movements used in high speed tetris. This whilst not even playing tetris.
I diagnosed the problem myself and quit playing, but it took a few months to clear up.
Just a warning. I still play it on and off.
Re:Tetiris / Eyeball RSI Warning (Score:5, Funny)
Thanks, if I ever meet you I'll be sure not to be freaked out
A good new view into women... (Score:4, Funny)
New fresh roast student - "Excuse me, but this task it's too hard for me. It deals with a NP-hard task and I don't have the brains for it... Couldn't you give a more simple task for me?.."
Me - "Well go and play some Tetris while I think how we can ease your work..."
After a few hours - "Well what's the score? And you say NP-hard algorithms are too hard for you? You trying to solve a NP-hard algorithm for more than an hour! Cool, go and try to do the same with that task you don't have brains for..."
Re:A good new view into women... (Score:5, Funny)
And here I thought the rest of your story would involve the use of the pickup line, "Hey baby, wanna play with something that is very NP-Hard?!"
Tetris unwinnable against malevolent machine (Score:4, Interesting)
I've seen two independent proofs of this (and other people have surely done it too) but I can't find an online proof. But I think that one way for the machine to win is to drop S and Z pieces in any irrational proportion.
Tetris is very easy on a Hercules - I should know (Score:3, Funny)
How can this be easy, you ask? Well, I put a delay in there too, it was adjustable from the command line of the TSR. When my score went past -32768 at the highest level, I decided enough was enough, and I didn't play Tetris for many years after.
Earlier Tetris Papers on 'Loseability' (Score:5, Interesting)
This is not about tetris as you know it (Score:3, Insightful)
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)
Tetris with physics: Triptych (Score:4, Interesting)
When you drop blocks, gravity affects them, and you can move blocks around with other blocks. (If your blocks aren't placed square, they don't land square! V shaped blocks tend to sit upside down etc) You get rid of blocks not by making lines, but by getting 3 of the same colour in a row, which then 'energize' and let you eat other blocks of the same colour.
And the best part - it's written in the Simple DirectMedia Layer [libsdl.org], so it runs on Windows, Mac or Linux. Check it out [chroniclogic.com]. (The main site is in Flash; this site takes you straight to it.
(Disclaimer - I am nothing to do with Chronic Logic - I just like the game.)
Look, I know they're from MIT and all... (Score:5, Funny)
Actually, Tetris is impossible (Score:4, Informative)
http://www.math.uic.edu/~burgiel/Tetris/explanatio n.html [uic.edu]
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.
P vs. NP and why should I care? (Score:5, Informative)
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 [cs.unb.ca] 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 [claymath.org] at Clay [claymath.org] for a really good description (unfortunately too long to quote here). And lastly, you might want to check out Tutorial: Does P = NP? [vb-helper.com] at VB Helper for a little more info.
Ok, but what is it good for? The Compendium of NP Optimization Problems [nada.kth.se] is a great place to look for real world examples of NP problems. Including everything from flower shop scheduling [nada.kth.se] [nada.kth.se] to multiprocessor scheduling [nada.kth.se].
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. :)
Tetris is only NP-hard when you try to maximize! (Score:4, Interesting)
AI: Tetris vs Dr. Mario (Score:3, Interesting)
They published a SNES game with both Tetris and Dr. Mario on one cartrige. I'm assuming both were programmed by the same team, since it let both games run simultaneously.
In either game you could play against the AI. You could choose the AI player's smarts, piece drop speed, and starting clutter. When I played against the smartest AI in Tetris, and made all else equal for it and me, I could just beat it, especially when starting with a clear field where I guess the player must be most "creative". But in Dr. Mario the AI was nearly perfect! As fast as possible and the best possible moves! Even on top speed and max clutter the AI almost never caved in! And to me, Dr. Mario is a more complicated game than Tetris.
How could this be?
Time Out! (Score:3, Interesting)
Years ago I wrote a program to play tetris and it did just fine! I know because it played directly against the tetris I had on my computer.
I'll explain how it worked:
In 1989 I lived in England and had lots of spare time to tinker with my computer (it was an old PC running at 4.77Mhz).
I thought DOS Tetris was the coolest thing since mini skirts and was also dabbling with TSR programs at the time (TSR = Terminate and Stay Resident). These would let you run one program in the background while another program runs.
So, naturally, I wrote a TSR program to play Tetris.
I would start the TSR and then start the game. The TSR would look in the video buffer and analyze tetris as it ran. It would look at the layout of the board and look at the next piece. With some relatively simple logic and a series of rules it weighed the merits of various positions for the piece. To make the move it would stuff keystrokes in the keyboard buffer, such as Rotate, Rotate, Left, Left, Left, Drop. Then it simply waited till the keyboard buffer was empty (the piece had been moved) and look for the next piece.
I could just sit back and watch...
At first it wasn't very good but with some tweaking of rules it improved drastically.
It would do much better than I could do manually, with pieces spinning, moving and dropping like crazy until the game really sped up. Then, with the limitations of a slow computer it couldn't analyze the best move and get the keystrokes in the buffer in time. Once it hit this threshold the pieces would start to stack up and it would be 'game over'.
I think at the time and the version I had I personally could get a score of around 8000. The TSR could get scores up to around 15000.
Just something to think about.....
--
Geoff
128-bit Tetris encryption (Score:4, Funny)
This could make the Bovine distributed cracking clients a lot more fun to watch.
What this proof is really about (Score:3, Informative)
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
Re:What? (Score:5, Informative)
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.
Re:Hrm. (Score:3, Funny)
Can't you be satisfied with one? I mean do you have any idea how hard it is to get dead Russions to invent anything?
Re:ending of tetris (Score:3, Funny)
Re:Because the game is hard, or... (Score:3, Informative)
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.
Re:Hrm. (Score:5, Informative)
Re:Because the game is hard, or... (Score:5, Informative)
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:
You don't know much about CS or Tetris, actualy. (Score:4, Interesting)
Actually, Tetris is all about risk management. See my other post on the subject. Once you get good at fitting the pieces together, the game becomes a question of figuring how risky building (and destroying) certain structures is, based on the probability of getting a long, or L shape.
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.
Hrm... What is an "if-then" loop?
Seriously though, in this case it shouldn't take more then a handful of loops and conditionals to figure out if a piece fits somewhere.
Playing Tetris is not actually a hard problem for a computer. NP-Hard and 'hard for a computer' are totally different things.
In general, the only reason human brains are better at some kinds of problems then computers is because computers are simply more limited in processing power. It would take thousands upon thousands of PCs hooked together to equal one human brain in terms of raw processing power.
(I've heard estimates that PCs will equal the human mind in 20 years, figuring with Moore's law, that would mean the human brain is about 2^13 times more powerful then a PC, or 8192 times)
Computational theory applies to all computing devices, including brains and other neural networks.
If something is NP-hard for a circuit, its NP hard for a brain too.
Re:Hrm. (Score:5, Funny)
Are there any other NP-hard games which were invented by dead Russians?
Is Russian Roulette NP-hard?