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...
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.
Next we'll see occultists studying Pacman.
Then NASA will use Moon Buggy as a simulator for the next Mars mission.
And eventually the Army will use Quake to train... ummm... too late on that one. Hey, at least they build their own!
Ravenn
Of all the things you can accomplish by screwing up your face and swearing into a dark room, sleep is not one of them.
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."
[self duck];
F-bacher
James Tiberius Kirk: "Spock, the women on your planet are logical. No other planet in the galaxy can make that claim."
I wonder if the computer got the rocket ship to launch. I only managed to do it once when I was young.
Tetris match of the century Kasparov vs. Deep Blue!! I think Gary can take him this time.
STOP ROCK VIDEO
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.
You'd be amazed at some of the Heuristics you have to use at Level 10!
Are there any other NP-hard games which were invented by dead Russians?
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?
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!
Your mother could beat you at Tetris? Boy, were you in the wrong generation.
"Only one cure for cancer in nearly 6 years!"
"If you are good at tetris you can play online tournaments at Worldwinner.com [worldwinner.com] against an or some opponents.
The nice part: you bet real money. If you are somewhat good you can make some cash."
Maybe the MIT dudes should have known about this...
They could have made their Tetris simulator pay for
their research project and more.
I'm sure creating that infectious tune wasn't NP-hard.
:-)
No, but, from own experiences, it's an NP-hard problem to get it out of your head once you've heard it, so please don't give me a link to where it can be downloaded.
Beware: In C++, your friends can see your privates!
I believe the game you're referring to is Blockout.
:O
My father brought it home from work one day, and I played it for the next few months. Took me a while to finally see the 3D blocks. =\
It's scary watching Tetris blocks fill up to the screen TOWARDS you.
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..."
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.
Are there any other NP-hard games which were invented by dead Russians?
Is Russian Roulette NP-hard?
Is it just me, or did somebody else think of NP-transistors when they read "NP-Hard"?
(Zap! Kapow! Kersplat!)
....I think my geek factor just increased by 1 x 10^2...ouch...
but that doesn't give them the right to flat-out make up words. "Inapproximability" indeed!
Thanks,
--
Matt
Just a warning. I still play it on and off.
Thanks, if I ever meet you I'll be sure not to be freaked out
I can quit any time I want to.
I played tetris lightly, but never owned it or played too much. Although, it (and some other games) a few times had me dreaming about playing (like, literally had me arranging blocks in a dream).
:-) We even had to take bathroom breaks. We were just so into the game that we were TOTALLY in the kirby zone. Kind of like when you're typing and you just hit exactly the right keys more quickly than usual, we were just placing the globs so perfectly and makin so many pumpkin combos :-)
However, when I was about 14, I played a match of Kirby's avalanche against my friend's au pair (mom was divorced and he had a little bro). We had been lpaying all summer, so we were pretty good, but this match lasted well over an hour. The game speed got ridiculous, where the pieces seemed to fall as fast as the graphics processor could display them
Ahhhhh, those were the days!
$8.95/mo web hosting
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.
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.
It's probably more fun when it's on, right?
"And like that
It's so hard to win on Tetrinet. I always thought the winners cheated using bots, but now this tells me that isn't possible.
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