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

Re:Winning

[agurkan]

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

[targo]

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:What?

[mizhi]

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.

Online Tetris tournaments

[wilbrod]

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:Winning

[Kong the Medium]

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:Poll

[robertchin]

Alexey Pajitnov.

Re:Because the game is hard, or...

[McBeth]

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.

Duh

[Crispin Cowan]

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:Winning

[Lars Arvestad]

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.

Re:Hrm.

[Wrexen]

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.

Re:Wait a second...

[Crispin Cowan]

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]

Not your father's tetris...

[travd]

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.

Re:Because the game is hard, or...

[sahala]

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

Re:Online Tetris tournaments

[hfastedge]

Just analyzing and categorizing the problem is usually far from formulating a solution.

Re:Wait a second...

[travd]

But since there are only 4 blocks in each piece, "exponential" is not that big, the computer can easily compute an optimal placement without breaking a sweat.

That's just wrong.

If you read the article, you would see that the fact that tetrominos (that's what they call 'em) are four block combinations does not define the magnitude of the (likely, assuming P != NP) exponential relationship. In fact, they show that the problem scales in an NP fashion with the number of pieces - the number four doesn't come into it.

What the Nintendo version shows is that a simple AI (with perfect movement abilities) and so on can come close enough to optimal in a usual situation (the article presenet an extremely contrived worse case scenario) to beat a human player. This has no bearing on the NP completeness of the problem.

On another note, the authors admit that the Tetris problem is NOT NP-Complete except for arbitrarily large game fields.

Re:Duh

[donutello]

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.

Re:Hey...

[tbspit]

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.

Re:Winning

[travd]

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:Interesting Reduction

[gazbo]

No it is not.

You are partly right; it is never NP-complete. It is also often solvable. However, in the general case it is not solvable - sometimes you just have to guess.

In fact, take the first move you have to make and tell me with 100% certainty that you're not clicking on a mine. You can't - the problem is not solveable.

Re:Winning

[Gubble]

Not-losing tetris is impossible in the long term. All you need to loose is a very long sequence of Z and S pieces. These pieces don't tile the plane. Even if a normal tetris game program may forbid such sequences, your "any arbitrary sequence" definition clearly includes such seq.s

Re:Winning

[Lev_Arris]

As far I as remember you only had to beat game mode B with speed 9 and high 5 (half the screen filled at start) to win. (or get that high score in mode A)

Actually, Tetris is impossible

[watanabe]

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.

P vs. NP and why should I care?

[rtos]

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

Re:Not your father's tetris...

[Plutor]

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

Re:This is not about tetris as you know it

[Sandmann]

> ... a relatively simple dynamic program solves
> the case of a constant-size gameboard in time
> polynomial in the number of pieces

Here is one relatively simple dynamic programming solution.

Suppose the game board has size k. Each cell in the game board can be either on or off, so we can represent the state of the board in a bit vector with k bits. Now define a recursive procedure that takes a sequence of n blocks and a state of the game board as input:

def solve (c, B_1, ..., B_n):
if n == 1:
(given c):
find best placement of B_1;
find the score you get with
that placement
return ([B_1], score)

best_so_far = ([], 0)
for each possible placement p of B_1:
c' = c with p applied
s = solve (c, B_2, ..., B_n);

if (s is better than best_so_far)
best_so_far = s

return best_so_far

This will calculate the optimal solution, but unfortunately the program runs in exponential time. To fix that, observer that solve will only be called with 2^k * n different sets of parameters. This means that since the function only does constant work when we disregard the recursive calls, caching the results of calls to the procedure in a table of size 2^k * n, we can make it run in time O(n).

Note however that the O here is hiding a constant of size 2^k, where k is the size of the game board. This means that this algorithm, while nominally O(n), is not practical when the gameboard gets even moderately big.

What this proof is really about

[vlad_petric]

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