Forgot your password?
typodupeerror
Games Entertainment

Tetris Is Hard: NP-Hard 345

Posted by timothy
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

Comments Filter:
  • Winning (Score:3, Interesting)

    by scotch (102596) on Friday October 25, 2002 @01:23AM (#4527798) Homepage
    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 (Score:5, Informative)

      by agurkan (523320) on Friday October 25, 2002 @01:30AM (#4527811) Homepage
      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 (Score:5, Informative)

        by travd (608286) on Friday October 25, 2002 @03:35AM (#4528140)
        More particularly, they show that given an arbitrary size game board, and prior knowledge of the sequence of pieces, the problem of computing the optimal solution to four problems is NP-Hard:

        (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:3, Interesting)

      by kjd (41294)
      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 (Score:3, Informative)

      by targo (409974)
      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.
      • 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 (Score:3, Interesting)

      by stevey (64018)

      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 (Score:5, Informative)

      by Lars Arvestad (5049) on Friday October 25, 2002 @02:17AM (#4527954) Homepage Journal
      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.

    • I imagine "winning" in Tetris would be defined as "not-losing". I'd guess the goal of a winning algorithm would be for an initially empty board to calculate a strategy to never stack-out (lose) for any arbitrary inifite sequence of Tetris pieces.

      Probably to help prove that, the tool you'd want is an algorithm to determine if an arbitrary board is winable or losable for any given N-finite sequence of pieces; where N is the number of remaining empty grids divided by four. You'd want to use that algorithm to determine a large set of initial board configurations that you'll never leave for any given sequence of pieces. That first algorithm is probably the one they say is NP-hard.

  • by DeadMoose (518744) on Friday October 25, 2002 @01:25AM (#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...
  • by aero6dof (415422) <aero6dof@yahoo.com> on Friday October 25, 2002 @01:26AM (#4527803) Homepage
    No, I'm empirically testing some NP theories...
  • by Uhh_Duh (125375) on Friday October 25, 2002 @01:27AM (#4527804) Homepage

    I don't get it. They used math to figure out that tetris is hard, but math is hard too. :(
  • Hey... (Score:5, Funny)

    by bluemilker (264421) on Friday October 25, 2002 @01:28AM (#4527807) Homepage
    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...
    • Re:Hey... (Score:3, Informative)

      by tbspit (460062)
      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.
      • bastion strategy (Score:3, Interesting)

        by Animaether (411575)
        The reason you'd leave it open in the center is because.. if a beam block appears, you...

        1. Won't die immediately, when the block is vertical and Your stacks are high, as it'll slot into the gap.
        2a. can drop it immediately, making a tetris.
        2b. have to only rotate once to make it vertical, followed by 2a.
      • Re:Hey... (Score:4, Interesting)

        by athmanb (100367) on Friday October 25, 2002 @09:22AM (#4529491)
        If you leve the open column in the center, you have an even count of blocks on the left side, and an odd count on the right side. This means you have more possibilities to stack different classes of blocks.

        Plus, you can use both right- and left-handed L blocks as a makeshift solution if your stack gets too high.
  • by GroovBird (209391) on Friday October 25, 2002 @01:31AM (#4527814) Homepage Journal
    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.

  • by gpinzone (531794) on Friday October 25, 2002 @01:31AM (#4527815) Homepage Journal
    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
  • by Steve Cowan (525271) on Friday October 25, 2002 @01:32AM (#4527817) Journal
    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.
  • by Cyno01 (573917) <Cyno01@hotmail.com> on Friday October 25, 2002 @01:32AM (#4527818) Homepage
    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
  • 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 (Score:2, Interesting)

      by MrMetlHed (518539)
      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 (Score:3, Informative)

      by robertchin (66419)
      Alexey Pajitnov.
    • Re:Poll (Score:5, Funny)

      by Limynali (620117) on Friday October 25, 2002 @08:10AM (#4528918) Homepage
      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.
      • Ages ago I modified Xtetris to play automatically. I figured I had succeeded when it continued to play at top speed for a full week without losing.

        But interestingly enough, then I decided to see whether the game was deterministically winnable, or only statistically winnable -- so I used the same strategy algorithm to "cheat" by always picking the piece that was hardest to fit, and then presenting that piece as the next one for the human player to deal with.

        Both when I played, and when my autoplayer algorithm played, we always lost immediately without being able to remove even one row. It is truly maddening to get absolutely nothing but the "wrong" pieces. Even in slow motion, they just don't fit.

        The way to interpret this is that tetris is unplayable in the absolute worst case of bad luck, but that it is strangely nicely tuned so that it is winnable in a statistical sense -- for a while .

        But even if it doesn't speed up too much, eventually you'll run into a statistical streak of bad luck with just the wrong pieces, and you will lose! Guaranteed.

        Alexey was a friend of a friend at the time, and I mentioned this result to him. He said he was not at all surprised, but didn't say much else about it.

  • by Ghoser777 (113623) <fahrenba.mac@com> on Friday October 25, 2002 @01:34AM (#4527826) Homepage
    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

  • I wonder... (Score:2, Funny)

    by SparkyTWP (556246)
    I wonder if the computer got the rocket ship to launch. I only managed to do it once when I was young.
  • by lingqi (577227) on Friday October 25, 2002 @01:37AM (#4527838) Journal
    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.
  • by wilbrod (471600) on Friday October 25, 2002 @01:38AM (#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.
    • "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.
  • by DougJohnson (595893) on Friday October 25, 2002 @01:39AM (#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!

  • by fireboy1919 (257783) <`rustyp' `at' `freeshell.org'> on Friday October 25, 2002 @01:42AM (#4527860) Homepage Journal
    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 (Score:5, Funny)

    by Jugalator (259273) on Friday October 25, 2002 @01:42AM (#4527863) Journal
    Tetris wouldn't be NP-hard if it just released that damn 1x4 brick when you need it!
    • if it just released that damn 1x4 brick when you need it

      3 buddies of mine and I spent many hours playing tetris, especially the Versus mode on the SNES version. When we needed a piece, we would say "why don't they give me what I need!" or "they know they are screwing me over, i need a line!" The point being we assumed there was some committee ("they") inside the game, or possibly we were referring to the group that made the game, that was not giving the right pieces at the right time. The "they" became a running joke...

      God what a pointless story.... I guess you had to be there.
  • memory optimization (Score:2, Interesting)

    by fat32 (620360)

    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?
  • 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... (Score:5, Interesting)

    by Chemical (49694) <nkessler2000@hot[ ]l.com ['mai' in gap]> on Friday October 25, 2002 @02:00AM (#4527918) Homepage
    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?

    • by cosyne (324176) on Friday October 25, 2002 @02:32AM (#4527987) Homepage
      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.
    • by Patrick (530) on Friday October 25, 2002 @09:27AM (#4529534)
      How is it Nintendo et. al. can program an incredibly skilled Tetris AI, but scientists at MIT cannot?

      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.

  • 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.
  • 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?
    • From the point of view of computer terminolgy, and also heavy game players, Tetris is not a game at all. Both the Game Theory branch of mathematics and any big playing group will tell you that games are all about opposition- two competitors pitting their skills against each other using a set of rules. Pure tetris has only one player, and (like things called Solitare) isn't really a game.

      (The mathematicians go even further, and only classify problems as a game if there is are no elements unknown to the players- so no facedown cards, and no rolling of dice)
  • Duh (Score:3, Informative)

    by Crispin Cowan (20238) <[moc.nawocnipsirc] [ta] [nipsirc]> on Friday October 25, 2002 @02:15AM (#4527947) Homepage
    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]

    • Re:Duh (Score:3, Informative)

      by donutello (88309)
      Nope. Tetris has nothing to do with bin packing. Bin packing is about putting numbers in buckets such that no bucket has a total more than so much. Tetris looks like a bin you're packing but there is no similarity between tetris and the bin packing they are refering to.
  • "The only way to win is not to play."
  • by travd (608286) on Friday October 25, 2002 @02:24AM (#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.
    • Not really. All NP-hard problems are relatively "easy" if you use a constant-size (and small) set. By the Minesweeper analogy: If the board is 5x5, it's easy to solve. Only by generalizing the problem to an arbitrarily large set, can they show that it actually is NP-complete.

      x^n doesnt look like much when n is 'small'.
  • Is Tetrisphere also NP-hard?
  • by po8 (187055) on Friday October 25, 2002 @02:31AM (#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, 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.

  • Technically, it's 'NP-hard,'

    To me, Tetris seems to be analogous to the 0-1 Knapsack problem, which is also NP-complete. Except maybe Tetris moves the problem into the second dimension. OTOH, we know that P=NP [1], so this problem can be solved readily.

    [1] The Simpsons, "Treehouse of Horror VI", #3F04, 1995.
  • by po8 (187055) on Friday October 25, 2002 @02:52AM (#4528039)

    Uh, I was just reading the full paper and came to this comment which summarizes an important fact omitted in the abstract:

    An essential part of our reduction is a complicated initial gameboard from which the player must start. A major open question is whether Tetris can be played efficiently with an empty initial configuration: What is the complexity of Tetris when the initial gameboard is empty?
    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.
    • And wait, there's still more. The proof fails if you fix the number of columns in the game board! In other words, this is not just offline Tetris on a normal-width Tetris board: the complexity is a function of the fact that as the piece sequence gets longer, the board width also increases.

      I was excited about this paper half an hour ago: now, not so much.

  • by Boss, Pointy Haired (537010) on Friday October 25, 2002 @02:56AM (#4528053)
    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.
  • by Ektanoor (9949) on Friday October 25, 2002 @03:11AM (#4528089) Journal
    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..."
  • by Stephen (20676) on Friday October 25, 2002 @03:39AM (#4528149) Homepage
    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.
  • by delphi125 (544730) on Friday October 25, 2002 @03:42AM (#4528153)
    A long time ago, Tetris for the PC printed different coloured spaces for the blocks. Unfortunately, a Hercules monochrome card pretending to be able to deal with colour would display them all the same. So I could see the score etc, but not the pieces themselves. Since that would be a little too hard, I wrote a TSR which hooked into INT 10 which would change spaces to other characters. This depended on the colour, so for example the Blue 2x2 would print as 4 'O's.

    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.

  • by Keev (573393) on Friday October 25, 2002 @03:47AM (#4528166)
    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 [nec.com].
  • by LS (57954)
    I thought NP meant Not Particularly. duh
  • by olethrosdc (584207) on Friday October 25, 2002 @04:12AM (#4528232) Homepage Journal

    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)

  • by Plug (14127) on Friday October 25, 2002 @04:50AM (#4528304) Homepage
    Chronic Logic [chroniclogic.com], 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 [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.)
  • by MattRog (527508) on Friday October 25, 2002 @06:43AM (#4528520)
    but that doesn't give them the right to flat-out make up words. "Inapproximability" indeed!
  • by watanabe (27967) on Friday October 25, 2002 @07:04AM (#4528588)
    Actually, Tetris is impossible.

    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.

  • by rtos (179649) on Friday October 25, 2002 @07:05AM (#4528593) Homepage
    [I posted this before, but I thought it was apropos to this story as well.]

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

  • by frleong (241095) on Friday October 25, 2002 @07:33AM (#4528717)
    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.
  • by Vegan Pagan (251984) <deanas@earthliLISPnk.net minus language> on Friday October 25, 2002 @08:10AM (#4528922)
    If Nintendo is to be believed, Tetris is hard for computers and Dr. Mario is hard for humans.

    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)

    by kiwifr00t (620461) on Friday October 25, 2002 @08:35AM (#4529056)
    I'm either missing something or the boys at the MIT lab are thinking too hard.
    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
  • by c64cryptoboy (310001) on Friday October 25, 2002 @10:59AM (#4530225) Homepage Journal
    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.
  • by vlad_petric (94134) on Friday October 25, 2002 @08:12PM (#4534797) Homepage
    Dear slashdotters who either never took or just completely ignored an algorithms/complexity class,

    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

For every bloke who makes his mark, there's half a dozen waiting to rub it out. -- Andy Capp

Working...