Slashdot Mirror

← Back to Stories (view on slashdot.org)

Tetris Is Hard: NP-Hard

Posted by timothy on 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."

3 of 343 comments (clear)

  1. Tetris NP-hardness results by po8 · · Score: 5, Insightful

    Technically, it's 'NP-hard,' meaning that there is no efficient way to calculate the necessary moves to "win"

    It is more correct to say that "there is no known efficient way to calculate the necessary moves to win, and it is unlikely that one will be discovered." Technically, there is no efficient method unless P = NP. See Garey and Johnson 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".

  2. Re:Wait a second... by cosyne · · Score: 5, Insightful

    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.

  3. Only proven hard if started screwed up enough... by po8 · · Score: 5, Insightful

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

    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.