Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Tetris Is Hard: NP-Hard

timothy posted more than 11 years ago | from the lots-of-chin-scratching dept.

Games 345

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."

cancel ×

345 comments

frost pist (-1, Troll)

Anonymous Coward | more than 11 years ago | (#4527795)

fp biatches!!!! Y'all can lick the nutz

Re:frost pist (-1)

Carp Flounderson (542291) | more than 11 years ago | (#4527895)

Has anyone else ever noticed that when you're considering sucking another man's cock, the subject of linux always comes up? Wassup with that?

Hrm. (-1, Troll)

Anonymous Coward | more than 11 years ago | (#4527797)

Are there any other NP-hard games which were invented by dead Russians?

Re:Hrm. (3, Funny)

Anonymous Coward | more than 11 years ago | (#4527862)

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?

Re:Hrm. (5, Informative)

Wrexen (151642) | more than 11 years ago | (#4527960)

The inventor of Tetris is alive and well. In fact, I just saw him give a talk while visitng UIUC [uiuc.edu] at their Reflections and Projections conference.

Winning (3, Interesting)

scotch (102596) | more than 11 years ago | (#4527798)

How the hell do you win at tetris? I remember it getting faster and faster but never ending. Maybe I just sucked at the game, or was playing a clone.

Re:Winning (5, Informative)

agurkan (523320) | more than 11 years ago | (#4527811)

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.

Re:Winning (3, Interesting)

kjd (41294) | more than 11 years ago | (#4527830)

In the Game Boy version (1989), you got little audiovisual rewards for breaking certain point barriers. If you broke 50,000, you'd get to see a little rocket launch. 100,000 lines (I think this is the right number) would net you a takeoff of the Space Shuttle.

Re:Winning (5, Informative)

Kong the Medium (232629) | more than 11 years ago | (#4527853)

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.

Re:Winning (0)

Anonymous Coward | more than 11 years ago | (#4527885)

Your game is weak! It's all about Level 28, baby! Only got their once though :(

There. (0)

Anonymous Coward | more than 11 years ago | (#4527929)

"Only got there once though."

Re:Winning (3, Informative)

targo (409974) | more than 11 years ago | (#4527835)

How the hell do you win at tetris?

The best Tetris game that I remember playing was Super Tetris [mobygames.com] . 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.

Re:Winning (2)

silvaran (214334) | more than 11 years ago | (#4527884)

The Playstation one is pretty sweet. The pieces are rendered (though it's still 2D-looking most of the time). When you play multiplayer, and you're kicking ass, the other player's boart twists and spins making it harder to play.

The only drawback is, as long as you keep rotating the piece, it will appear to "bounce" on the other pieces below. You could keep quickly rotating the pieces back and forth until you found a place to fit. In essence, you could bounce a piece around for a limitless amount of time until you got it just right...

Re:Winning (3, Interesting)

stevey (64018) | more than 11 years ago | (#4527917)

You also win if all your opponents are dead in the multiplayer games, like Tetrinet [tetrinet.org] . (There's a good client out for Linux too - gTetrinet [sourceforge.net] ).

Unfortuntately there is a limit of six players to the game; but it's still been taking my workplace by storm for the past two weeks.

Re:Winning (5, Informative)

Lars Arvestad (5049) | more than 11 years ago | (#4527954)

Read the paper. One does not need to understand it to see what the actual questions are.

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.

What? (-1)

vcv (526771) | more than 11 years ago | (#4527801)

Tetris hard? Can't be. Why the hell are analysts studying how hard a game is? Seems all these "studies" being done are getting dumber by the day.

Re:What? (5, Informative)

mizhi (186984) | more than 11 years ago | (#4527840)

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.

Tetris is NP-hard! (5, Funny)

DeadMoose (518744) | more than 11 years ago | (#4527802)

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...

Re:Tetris is NP-hard! (0)

Anonymous Coward | more than 11 years ago | (#4527873)

To be more specific, tetris is NP-Butt Hard.

Re:Tetris is NP-hard! (0)

Anonymous Coward | more than 11 years ago | (#4527907)

Now all you need to prove is all games can be derived from Tetris or Nethack.

Are you goofing off playing tetris... (5, Funny)

aero6dof (415422) | more than 11 years ago | (#4527803)

No, I'm empirically testing some NP theories...

They used math to figure this out? (5, Funny)

Uhh_Duh (125375) | more than 11 years ago | (#4527804)


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? (5, Funny)

the.jedi (212166) | more than 11 years ago | (#4527866)

Yeah well we mit people are crazy like that.
Instead of studing for my Linear Algebra exam,
I've been busy proving tecmobowl is NP-Fun!

Re:They used math to figure this out? (1, Funny)

Anonymous Coward | more than 11 years ago | (#4527908)

Sounds like a talking Barbie:

"Math is hard!"

"Pink is pretty!"

"Ken is hard, and I am easy!"

Hey... (5, Funny)

bluemilker (264421) | more than 11 years ago | (#4527807)

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...

The answer you seek (-1, Redundant)

papasui (567265) | more than 11 years ago | (#4527812)

...lies within the flash of Russian Vodka.

Re:The answer you seek (2)

papasui (567265) | more than 11 years ago | (#4527822)

err that should say "flask", I've been studying my Tetris too hard...

ending of tetris (0)

eleven357 (449450) | more than 11 years ago | (#4527813)

I don't think that tetris ever ends until you screw up. I remember playing tetris on my game boy when I was 13. I averaged around 250 lines before I would lose and my mother got anywhere from 300-500 lines until she would screw up.

I also remember playing a 3D tetris game on the pc about 12 years ago. It was alot more difficult that the normal 2d tetris , but to me it was a bugger challenge.

Re:ending of tetris (2)

\\ (118555) | more than 11 years ago | (#4527856)

you know, my gameboy tetris record for lines was 227. that's 27 lines at level 20, which was basically the devil.. and youre claiming you averaged 250, and your mother 300-500.

i'm not saying you're a liar, but i really, really doubt anyone can maintain level 20 on gameboy tetris for 200+ lines. maybe you're remembering something wrong, but.. no. it hurts just to think about.

Re:ending of tetris (3, Funny)

silvaran (214334) | more than 11 years ago | (#4527874)

Your mother could beat you at Tetris? Boy, were you in the wrong generation.

Re:ending of tetris (2)

Babbster (107076) | more than 11 years ago | (#4527920)

Moms beating their gamer kids at Tetris is no surprise (I'm in the same boat). I've played hundreds [upon hundreds] of different games over the years, while my mom has spent months at a time just playing Tetris. I do wonder if there was ever a Gameboy-like device that ONLY played Tetris. It would have saved me quite a few bucks over the years replacing her Gameboy over and over again when she would wear it out. :)

Re:ending of tetris (2, Funny)

feceus (450222) | more than 11 years ago | (#4527946)

I believe the game you're referring to is Blockout [sonic.net] .

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. :O

In Other News (5, Funny)

GroovBird (209391) | more than 11 years ago | (#4527814)

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.

Re:In Other News (1)

Urox (603916) | more than 11 years ago | (#4527966)

They'd better not put it on two player mode or the second computer connected will be able to generate the exact same encryption algorithm!

The only way to win at Tetris... (5, Funny)

gpinzone (531794) | more than 11 years ago | (#4527815)

Is to prove the P = NP challenge. I think I'll play Quake 3 instead.

Further studies... (2, Funny)

Ravenn (580407) | more than 11 years ago | (#4527816)

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

Re:Further studies... (5, Interesting)

Flakeloaf (321975) | more than 11 years ago | (#4527855)

Next we'll see occultists studying Pacman.

At least Pacman has a perfect solution [twingalaxies.com] . No fancy math required, just a good hot meal beforehand and a little patience.

Re:Further studies... (-1, Offtopic)

MrMetlHed (518539) | more than 11 years ago | (#4527861)

Moon Buggy? No no no... Moon Patrol. That way they could blow up or jump over everything in their path on the Martian surface.

Charlie

It's not that Tetris is HARD... (5, Funny)

Steve Cowan (525271) | more than 11 years ago | (#4527817)

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.

I always sucked at tetris... (4, Funny)

Cyno01 (573917) | more than 11 years ago | (#4527818)

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

Re:I always sucked at tetris... (0)

Anonymous Coward | more than 11 years ago | (#4527923)

Actually its called Quayle Tetris. You can play it on a Mac or Unix. Google is your friend.

Poll (2)

SexyKellyOsbourne (606860) | more than 11 years ago | (#4527819)

The highest level you got on Tetris?

23 for me, on the SNES version.

I used to be really, really good at it.

But Tetris is nearly impossible when they're dropping at breakneck speed -- in fact, it falls so fast that even a computer controlled bot operating in microseconds could not rotate it to keep it perpetuating, even if the speed weren't increasing after 20 (or even 15).

I didn't think the non-speed aspect would be so difficult: Pazhatiniov (sp?) is truly a genius.

Re:Poll (2, Interesting)

MrMetlHed (518539) | more than 11 years ago | (#4527839)

Level 30 on Tetris DX for the Gameboy color. But only because it stops getting faster at level 30. All told I had over a thousand lines, something like 2.2 million points. At that speed you basically end up playing the game in the Next Piece window and hoping you tap the buttons fast enough to make it fall properly.

Charlie

Re:Poll (3, Informative)

robertchin (66419) | more than 11 years ago | (#4527903)

Alexey Pajitnov.

the NP-complete version is easier?? (0)

fat32 (620360) | more than 11 years ago | (#4527824)

The paper says this:

We study the offline version because its hardness captures much of the difficulty of playing tetris; intuitively, it is only easier to play Tetris with complete knowledge of the future, so the difficulty of playing the offline version suggests the difficulty of playing the online version.

Really, having knowledge of the whole piece list is *easier* than winging it one piece at a time? I'll stick with regular Tetris, thanks!

So that's why... (3, Funny)

Ghoser777 (113623) | more than 11 years ago | (#4527826)

there's a security bug in kadmind4, as mentioned in the previous slashdot [slashdot.org] story! Instead of focusing on checking for buffer overflow errors, they were busy playing Tetris ;)

[self duck];

F-bacher

Tetris "ends"? (1)

mcubed (556032) | more than 11 years ago | (#4527828)

Will someone please tell me what happens when Tetris ends? Is it like the end of the rainbow ... pots of gold and all that good stuff? I always thought it just kept going until you lost (or, in the old days, spent another quarter), which show you how far I've gotten.

Michael

Re:Tetris "ends"? (5, Interesting)

fireboy1919 (257783) | more than 11 years ago | (#4527898)

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.

Re:Tetris "ends"? (2)

DEBEDb (456706) | more than 11 years ago | (#4527940)

Will someone please tell me what happens when Tetris ends?


We are actually living in a section of a
Tetris figure falling down in a cosmic
Tetris game played by the great Pajitnasana.
When it falls, our universe ends. When the
entire game ends... Oh, I shudder to think
of that...

Re:Tetris "ends"? (2)

Jugalator (259273) | more than 11 years ago | (#4527953)

Will someone please tell me what happens when Tetris ends? Is it like the end of the rainbow ... pots of gold and all that good stuff?

Yeah, I think it's like the end of the rainbow, but not as you describe it. Rather "you never get there". :-)

I wonder... (2, Funny)

SparkyTWP (556246) | more than 11 years ago | (#4527831)

I wonder if the computer got the rocket ship to launch. I only managed to do it once when I was young.

Re:I wonder... (1)

MrMetlHed (518539) | more than 11 years ago | (#4527852)

The best was in the NES version when they carted out a small ship for a ton of points. Suddenly the whole Russian City takes off into space... Now that was worth all the tension in staring at a TV of falling pieces for far too long.

Charlie

and yet (1)

madsenj37 (612413) | more than 11 years ago | (#4527832)

there is no cure for most cancer

Re:and yet (1, Funny)

Anonymous Coward | more than 11 years ago | (#4527879)

"Only one cure for cancer in nearly 6 years!"

Re:and yet (1)

DeadMoose (518744) | more than 11 years ago | (#4527892)

there is no cure for most cancer

Wait, if I get an L-shaped block, and rotate it into place at just the right moment............THERE! He's gone into remission!

Brain Strain in the Ukraine (1, Funny)

vaguelyamused (535377) | more than 11 years ago | (#4527836)

Tetris match of the century Kasparov vs. Deep Blue!! I think Gary can take him this time.

This article is false...there is one who can (-1, Offtopic)

dolphin558 (533226) | more than 11 years ago | (#4527837)

http://www.geocities.com/lilmacumd/escape.html

man... that is so not fair (4, Funny)

lingqi (577227) | more than 11 years ago | (#4527838)

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.

Online Tetris tournaments (4, Informative)

wilbrod (471600) | more than 11 years ago | (#4527843)

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. 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.

Re:Online Tetris tournaments (3, Funny)

Cheese Cracker (615402) | more than 11 years ago | (#4527906)

"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.

They would've figured it out (0)

Anonymous Coward | more than 11 years ago | (#4527844)

If they hadn't kept playing the game! Bad scientists!

I was doing home-work the whole time. (3, Funny)

DougJohnson (595893) | more than 11 years ago | (#4527848)

Now I can get my Computer Science Theory mark reviewed under the grounds that I put hours of research into attempting to find a solution to an NP Hard problem.

You'd be amazed at some of the Heuristics you have to use at Level 10!

Because the game is hard, or... (0, Insightful)

Guppy06 (410832) | more than 11 years ago | (#4527851)

... because object recognition is hard for computers? Tetris is all about putting things where they fit, not some grand master strategy. 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.

Re:Because the game is hard, or... (0)

The Trix Rabbit (619782) | more than 11 years ago | (#4527887)

It has nothing to do with that. They reduced Tetris to a NP-Complete problem called 3-Partition.

NP Completeness implies that there is no polynomial time algorithm to compute the solution. This is not proof, though, since it's not been proven that P != NP.

Re:Because the game is hard, or... (3, Informative)

McBeth (1724) | more than 11 years ago | (#4527926)

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.

Re:Because the game is hard, or... (0)

Anonymous Coward | more than 11 years ago | (#4527927)

..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..

No surprise really, evolution has selected for those with this specific ability.

Re:Because the game is hard, or... (0)

Anonymous Coward | more than 11 years ago | (#4527978)

Wow, I knew evolution was good but I never thought it would evolve humans to play Tetris well.

Re:Because the game is hard, or... (5, Informative)

sahala (105682) | more than 11 years ago | (#4527974)

... because object recognition is hard for computers? Tetris is all about putting things where they fit, not some grand master strategy. 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.

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:

Our results. We introduce the natural full-information (offline) version of Tetris: we have a deterministic, finite piece sequence, and the player knows the identity and order of all pieces that will be presented. We study the offine version because its hardness captures much of the difficulty of playing Tetris; intuitively, it is only easier to play Tetris with complete knowledge of the future, so the difficulty of playing the offine version suggests the diffculty of playing the online version. It also naturally generalizes the one-piece lookahead of implemented versions of Tetris.

Moderidiots! (0)

Anonymous Coward | more than 11 years ago | (#4527988)

How about -5 Non sequitur instead of +5 Insightful. If at least it was +5 Funny, I'd understand, but insightful?

For those who still don't get it: this is about the abstract problem of fitting tetris pieces together, not about pointing a videocamera at the screen, and have a second computer recognize the pieces. The second computer (the one "playing") already has all the information it needs in a suitable form, the only things it needs to do is decide how to place it. That's the problem that's NP hard, the problem is not figuring out that we this blue piece falling down is indeed L-shaped...

Everybody's a Loser (1)

The Rolling Blackout (556170) | more than 11 years ago | (#4527857)

Tetris is a game in which seemingly random no-win situations are introduced as part of the game. Certain pieces (e.g. the infamous S) simply are not compatible with what the player needs to 'score'. (+5 funny, thankyouverymuch)

In Tetris, the player and opponent are on completely unequal grounds. All the 'opponent' has to do is throw enough shitty pieces at you to prevent you from reaching the next level, or scoring enough points. No intelligence can triumph against a random number generator given such a disadvantage.

All I really have to offer to these researchers is a well-enunciated 'DUHH'.

Re:Everybody's a Loser (1)

Terralthra (618067) | more than 11 years ago | (#4527911)

They showed it was NP-complete to solve even when pieces were known in advance from start to finish, with the goals of maximum lines, maximum tetrises, minimum height of any column, and a couple others.

In short, RTFA.

NOW I'VE GOT MY EXCUSE! (5, Interesting)

fireboy1919 (257783) | more than 11 years ago | (#4527860)

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.

My theory (5, Funny)

Jugalator (259273) | more than 11 years ago | (#4527863)

Tetris wouldn't be NP-hard if it just released that damn 1x4 brick when you need it!

Re:My theory (1)

Yottabyte84 (217942) | more than 11 years ago | (#4527948)

Internet Irony: www.noads.com

Konqueror blocked 8 onloads, and 1 onclose

Interesting Reduction (0)

The Trix Rabbit (619782) | more than 11 years ago | (#4527870)

I'd like to see them reduce Tetris to Mindsweeper, another NP complete problem. That'd be slick.

Re:Interesting Reduction (2)

pyrote (151588) | more than 11 years ago | (#4527950)

Minesweeper is math..it is solvable, and I have yet to find a version to challange me. 6 sided blocks too. it's all math that can be calculated logically.

Oh come on.. (1)

The Creator (4611) | more than 11 years ago | (#4527872)

Everyone knows that Tetris solves by matrix inversion...

P = NP solved? (0)

Anonymous Coward | more than 11 years ago | (#4527876)

Did somebody crack this while I had my back turned? Last I heard, NP-hard meant (among other things) that no known polynomial-time solution exists, but that doesn't rule out the possibility that one might exist.

memory optimization (2, Interesting)

fat32 (620360) | more than 11 years ago | (#4527877)


It seems to me that this would have some applicability to memory stacks. After all, Tetris is a stack that doesn't need to be emptied in order for the rows above it to be used efficiently.

First I was thinking that Tetris is just a recursive problem; if a certain subset of pieces can be used to achieve a Tetris (4-row removal) then they can be removed from consideration. But then I realized that this would affect one's options for clearing rows below that, or pieces to come. It sounds like the only way to do this is by considering all (n_pieces*rotation)! possible plays.

Is this perhaps proof that memory usage cannot be optimized beyond a certain point?

researchers (1)

clockwise_music (594832) | more than 11 years ago | (#4527890)

.. can't these guys find something slightly more practical to work on? Finding out if Tetris is NP-Hard... honestly.. do something useful with your existence.

Obligatory Teris link... (1)

ChristW (18232) | more than 11 years ago | (#4527913)

Well, the guy that is linked from this page [crazywalker.com] can solve Tetris pretty well on his own...

what about columns? (2)

austad (22163) | more than 11 years ago | (#4527914)

I wonder if Columns for Sega would turn up the same results. You're not dropping shapes, you're dropping lines of colored jewels that you can change the order of on the way down.

Tetris used to be my favorite game on my old gameboy back in like 89. I made it to level 32 once, but it was going so insanely fast at that point you had to look at the next piece window and start pressing the buttons right when the last piece dropped. But once I got my hands on Columns, I never looked back. Made it to level 52 on Columns once. At that point, it's almost impossible to get the pieces to the edge of the playfield.

Wait a second... (5, Interesting)

Chemical (49694) | more than 11 years ago | (#4527918)

A lot of Tetris and Tetris type games had a two player mode that had the option for CPU controlled player two if you didn't have any friends. If you set the AI to the maximum level, you would be instantly crushed no matter how good you were. The CPU could instantly decide where to place the blocks, and never made a bad move. Try setting Tetris Attack for the SNES to play against itself for a while. It's kind of impressive.

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... (1, Informative)

Crispin Cowan (20238) | more than 11 years ago | (#4527964)

How is it Nintendo et. al. can program an incredibly skilled Tetris AI, but scientists at MIT cannot?
"NP-hard" means that they have a proof that the computational complexity of tetris is exponential in the number of blocks to be placed. But since there are only 4 blocks in each piece, "exponential" is not that big, so the computer can easily compute an optimal placement without breaking a sweat. "NP-hard" does not mean that that the problem is unsolvable, or even particularly difficult to solve, just that you can't scale it up to a zillion blocks without having approximately 2^zillion compute cycles.

Crispin
----
Crispin Cowan, Ph.D.
Chief Scientist, WireX Communications, Inc. [wirex.com]
Immunix: [immunix.org] Security Hardened Linux Distribution
Available for purchase [wirex.com]

Re:Wait a second... (0)

Yottabyte84 (217942) | more than 11 years ago | (#4527967)

I can play tetris attack endlessly with zsnes running at half speed. at full speed it's just too fast

Re:Wait a second... (5, Insightful)

cosyne (324176) | more than 11 years ago | (#4527987)

My question is this: How is it Nintendo et. al. can program an incredibly skilled Tetris AI, but scientists at MIT cannot?

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.

Thoughts... (2)

superdan2k (135614) | more than 11 years ago | (#4527925)

I don't see how this is an issue -- I haven't got a math degree, in fact, I suck at it. (Hence, my English degree.) But with a finite playing field and finite set of shapes, one would think that a computer would be much better at it than a human if it knew the order of the pieces.

You could probably create a genetic algorithm that would look at the order of groups of N and figure out macro-structures, and how those macro-structures best interacted with one another.

Whatever the case, I'm still of the opinion that Tetris is a Soviet Meme Weapon that was released too early. If they'd waited until the Internet was in every office and home, Western Civilization would have ground to a halt, and we'd all be drinking vodka and wearing furry hats by now.

the second I read the article (1)

ferrocene (203243) | more than 11 years ago | (#4527934)

I began to hum one of the theme songs. I'm sure creating that infectious tune wasn't NP-hard.

Re:the second I read the article (3, Funny)

Jugalator (259273) | more than 11 years ago | (#4527943)

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. :-)

Amazing (0)

Evil Adrian (253301) | more than 11 years ago | (#4527935)

Amazing the kind of shit people get paid for.

Historical value (2)

Dexter77 (442723) | more than 11 years ago | (#4527936)

What are your opinions dear slashdotters, now that Tetris has proven itself in the eyes of mathematicians should we place it on the same line with Chess and Go or maybe rubik's cube?

Computer world has not yet produced any historical classics, but I think if there should be one the Tetris might be the best candidate. Tetris is a game that can't be produced without computers, but it holds the same gaming value as Chess or Go, it can be played infinitely which in my opinion is the most important feature of a classic game.

Please share your thoughts?

Maybe a human can disprove it? (0)

Jeppe Salvesen (101622) | more than 11 years ago | (#4527941)

If we created a tetris that moves really slowly, with no speed increase and full look-ahead, I bet you could keep that game going for days.

I am extremely skeptical to their final result, and suspect they simply have not understood the game and algorithms required well enough.

Duh (3, Informative)

Crispin Cowan (20238) | more than 11 years ago | (#4527947)

Well, duh. Tetris is based on bin packing [gsu.edu] , a classic NP-hard optimization problem. That's what makes it such a compelling game: you have to solve a really hard problem in real time.

Crispin
----
Crispin Cowan, Ph.D.
Chief Scientist, WireX Communications, Inc. [wirex.com]
Immunix: [immunix.org] Security Hardened Linux Distribution
Available for purchase [wirex.com]

Remember what WOPR said... (2, Insightful)

jonblaze (140753) | more than 11 years ago | (#4527965)

"The only way to win is not to play."

Not your father's tetris... (5, Informative)

travd (608286) | more than 11 years ago | (#4527972)

The top of the third page, the authors reveal a major change to the definition of Tetris they made in order to prove NP-Completeness:
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.
Of course every version of Tetris that I have played has been on a "constant-size game board" - and so the real result is that Tetris, as the rest of the world knows it, is NOT NP-Complete, and is solvable in P(n) time - I find that the generalization to m x n gameboards breaks the problem, while the other simplifications or generalizations they introduce are reasonable.

Tetrisphere? (2)

Ziviyr (95582) | more than 11 years ago | (#4527973)

Is Tetrisphere also NP-hard?

Minesweeper too? (1)

sahala (105682) | more than 11 years ago | (#4527979)

Interestingly enough, the paper also notes that Minesweeper is NP-hard...

Related work: other games and puzzles. A number of other popular one-player com- puter games have been shown to be NP-hard, most notably Minesweeper, or more precisely, the Minesweeper \consistency" problem [6]. See the survey of the first author [3] for a summary of other games and puzzles that have been studied from the perspective of computational complexity. These results form the emerging area of algorithmic combinatorial game theory, in which many new results have been established in the past few years.

Tetris NP-hardness results (5, Insightful)

po8 (187055) | more than 11 years ago | (#4527985)

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".

technically, that is wrong (2)

g4dget (579145) | more than 11 years ago | (#4527989)

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.

Even if we stick with the traditional meaning of "efficient" as "solvable in polynomial time", that is wrong: we simply don't know whether NP-hard problems can be solved in polynomial time or not.

Of course, the whole definition of "efficiency" used in the theory of NP completeness is bogus. Just because something runs in polynomial time doesn't mean it can be solved "efficiently" or even that it "scales well", and just because something is NP-hard doesn't mean that it's not solvable efficiently in most or all cases you would be interested in.

NP completeness is a cute theory, but the misleading use of the term "efficient" it has brought into vogue in some computer science circles has really done a lot of harm and caused a lot of confusion.

Then you haven't seen this guy play (0)

Anonymous Coward | more than 11 years ago | (#4527991)

http://penguinppc.org/~olaf/tetris_japan_finals.mp eg

or just do a search for filename in GOOGLE.

JAPAN Finals??? for Tetris The Absolute Plus -The Grandmaster2- DEATH MODE.
I Think he makes it look easy. 12.8MB Video. 5 minutes plus.
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...