Slashdot Mirror
Tetris Is Hard: NP-Hard
bughunter writes "Analysts at MIT Laboratory for Computer Science, who have been busy translating, rotating and dropping, have demonstrated what the rest of us suspected: Tetris is hard. Technically, it's 'NP-hard,' meaning that there is no efficient way to calculate the necessary moves to "win," even if you know in advance the complete order of pieces, and are given all the time you need to make each move. At least there's one geek classic that refuses to fall to the scrutiny of mathematicians."
Next we'll see occultists studying Pacman.
At least Pacman has a perfect solution. No fancy math required, just a good hot meal beforehand and a little patience.
Am I the only one who heard Roxette to sing "I'm gonna get blitzed for some sex"?
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.
Mod me down and I will become more powerful than you can possibly imagine!
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.
Mod me down and I will become more powerful than you can possibly imagine!
My question is this: How is it Nintendo et. al. can program an incredibly skilled Tetris AI, but scientists at MIT cannot?
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.
Tetris is all about putting things where they fit, not some grand master strategy.
Actually, Tetris is all about risk management. See my other post on the subject. Once you get good at fitting the pieces together, the game becomes a question of figuring how risky building (and destroying) certain structures is, based on the probability of getting a long, or L shape.
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.
Hrm... What is an "if-then" loop?
Seriously though, in this case it shouldn't take more then a handful of loops and conditionals to figure out if a piece fits somewhere.
Playing Tetris is not actually a hard problem for a computer. NP-Hard and 'hard for a computer' are totally different things.
In general, the only reason human brains are better at some kinds of problems then computers is because computers are simply more limited in processing power. It would take thousands upon thousands of PCs hooked together to equal one human brain in terms of raw processing power.
(I've heard estimates that PCs will equal the human mind in 20 years, figuring with Moore's law, that would mean the human brain is about 2^13 times more powerful then a PC, or 8192 times)
Computational theory applies to all computing devices, including brains and other neural networks.
If something is NP-hard for a circuit, its NP hard for a brain too.
Lonely?
Find love on the internet
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.
11.0010010000111111011010101000100010000101101000
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.
A man, a plan, a canal: Suez!
Chronic Logic, 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, so it runs on Windows, Mac or Linux. Check it out. (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.)
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.
¦ ©® ±
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.