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."
Yeah, that's it; I'm not bad at it, it's just too hard. Just like, um, most every other video game I've played...
No, I'm empirically testing some NP theories...
I don't get it. They used math to figure out that tetris is hard, but math is hard too.
-- People who hate Windows use Linux. People who love UNIX use BSD.
those guys are dumb. Everyone knows you just leave a single block wide path in the center... you're _sure_ to get a 4-long column before you hit the... ARGH! ... this would be so much easier if I had a version of tetris that told me all the pieces in advance, like theirs does...
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
Ron Rivest of RSA Security (NASDAQ: RSAS) announced that are releasing a new assymetric encryption algorithm based on Tetris. Since Tetris has been under the scrutiny of millions of people, experts say that it is much more secure than current outdated algorithms such as RSA and Elliptic Curve. This will bring a new era in computer security, Ron says.
Is to prove the P = NP challenge. I think I'll play Quake 3 instead.
Mathematicians simply can't concentrate on the movement of the pieces, even given all the time they need, because it's too easy to get distracted by that wacky Russian folk music.
the game would be a whole lot easier if every piece was only one block instead of four, but then i guess they'd have to call it monris or something
"Sic Semper Tyrannosaurus Rex."
What the heck huh, I goto a "less glorified school" compared to MIT, and study / do research in semiconductor electron migrations, efficiency in cryptograhy systems, implementation of computer based voice and image recognition.
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.
My life in the land of the rising sun.
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
Next we'll see occultists studying Pacman.
At least Pacman has a perfect solution. No fancy math required, just a good hot meal beforehand and a little patience.
Am I the only one who heard Roxette to sing "I'm gonna get blitzed for some sex"?
Now whenever I lose the latest new game I can just say, "I have just determined that this game is very hard. Its NP-Hard, in fact." I'm sure that'll impress all the lady-geeks around that would otherwise have thought me intellectually inferior for losing the game.
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.
Mod me down and I will become more powerful than you can possibly imagine!
Tetris wouldn't be NP-hard if it just released that damn 1x4 brick when you need it!
Beware: In C++, your friends can see your privates!
Depends on the version. For the original gameboy version, in the count up mode (starting at level 1 and going up), you got to see images of a spaceship every 10 levels (if I remember right).
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.
Mod me down and I will become more powerful than you can possibly imagine!
My question is this: How is it Nintendo et. al. can program an incredibly skilled Tetris AI, but scientists at MIT cannot?
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:
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".
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.Just a warning to those becoming or already hooked on Tetris.
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.
Some have noted that women have always had a peculiar taste to play Tetris. It is interesting to note that the most fanatic players are usually women... Well, I am completely of a different mind and always considered this game as too boring. I wondered how could people play such thing for long hours. No more. I consider the game an excellent testing system. The next time I see a girl dealing with NP-hard algorithms and crying she can't hold up, I'll play the dirty trick:
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..."
Tetris is all about putting things where they fit, not some grand master strategy.
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.
Lonely?
Find love on the internet
(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.
It's also the case that Tetris is unwinnable against a malevolent machine, which chooses a nasty sequence of pieces. In the sense that even if you know the pieces in advance, you will eventually fill any tower of finite height.
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.
11.0010010000111111011010101000100010000101101000
Some little-known related references: A CS student at Univ of BC, John Brzustowski, did his Master's thesis on the problem of winning at Tetris if the computer is aware of your moves and reacting to them. He apparently proved that there is a finite sequence of tetrominos, which, if the machine selects them, you must lose. His work is cited in this later paper by H. Burgiel called "How to Lose at Tetris", which proves more generally that the computer can always produce a sequence of lose-forcing tetrominos, whether or not it's aware of your moves: paper is here.
A man, a plan, a canal: Suez!
Chronic Logic, the people who brought you the cool Pontifex bridge builder game, have a game called Triptych, which can loosely be defined as 'Tetris meets Columns with physics'.
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, so it runs on Windows, Mac or Linux. Check it out. (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.)
Are there any other NP-hard games which were invented by dead Russians?
Is Russian Roulette NP-hard?
but that doesn't give them the right to flat-out make up words. "Inapproximability" indeed!
Thanks,
--
Matt
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
There is a difference between a solution and an optimal solution. The fact that you don't lose doesn't mean that you're getting the best score. Finding the best way to fit a "T" block, for example, is simply much harder than just finding a place to place it.
¦ ©® ±
Last weekend I was priviliged enough to hear Alexey Pajitnov, the creator of Tetris, give a talk on how he came up with tetris, the design process of games, etc... The best part was at the end somene asked him about the dificulty of Tetris and he replied that even though he knew that each piece had the same probabilty (because he coded it) there must be some little guy inside the computer purposefully giving him the 'wrong' pieces and witholding the one he needed, "that Son-of-a-bitch!" (yes, he actually said that)
It's reasurring to know that even HE thinks it's rigged.
Now that we know it's NP hard, lets see if anyone can come up with a Tetris-based encryption scheme. Lets see, with just one shape (7 tetrominoes with rotations) there are 19 possibilities, so that's at least 4 bits of entropy right there.
This could make the Bovine distributed cracking clients a lot more fun to watch.
I put the 'fun' in fundamentalism