Tetris Is Hard: NP-Hard 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."
Winning (Score:3, Interesting)
Re:Winning (Score:3, Interesting)
Re:Poll (Score:2, Interesting)
Charlie
Re:Further studies... (Score:5, Interesting)
At least Pacman has a perfect solution [twingalaxies.com]. No fancy math required, just a good hot meal beforehand and a little patience.
NOW I'VE GOT MY EXCUSE! (Score:5, Interesting)
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.
memory optimization (Score:2, Interesting)
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?
Re:Tetris "ends"? (Score:5, Interesting)
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:Winning (Score:3, Interesting)
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.
Wait a second... (Score:5, Interesting)
My question is this: How is it Nintendo et. al. can program an incredibly skilled Tetris AI, but scientists at MIT cannot?
Tetiris / Eyeball RSI Warning (Score:5, Interesting)
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.
You don't know much about CS or Tetris, actualy. (Score:4, Interesting)
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.
Tetris unwinnable against malevolent machine (Score:4, Interesting)
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.
Earlier Tetris Papers on 'Loseability' (Score:5, Interesting)
Tetris with physics: Triptych (Score:4, Interesting)
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.)
Re:Winning (Score:1, Interesting)
These are from Tetris the Grandmasters 2 Plus arcade machine playing on Death mode.
At least there's an end to Death mode.
http://homepage2.nifty.com/arika_download/mpeg/de
bastion strategy (Score:3, Interesting)
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.
Another version of the tetris song on mp3.com (Score:3, Interesting)
Tetris is only NP-hard when you try to maximize! (Score:4, Interesting)
AI: Tetris vs Dr. Mario (Score:3, Interesting)
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)
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
Re:Hey... (Score:4, Interesting)
Plus, you can use both right- and left-handed L blocks as a makeshift solution if your stack gets too high.
I can't believe it's not Tetris (Score:2, Interesting)