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."
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.
XML causes global warming.
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...
No, I'm empirically testing some NP theories...
I don't get it. They used math to figure out that tetris is hard, but math is hard too.
-- People who hate Windows use Linux. People who love UNIX use BSD.
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...
I don't think that tetris ever ends until you screw up. I remember playing tetris on my game boy when I was 13. I averaged around 250 lines before I would lose and my mother got anywhere from 300-500 lines until she would screw up.
I also remember playing a 3D tetris game on the pc about 12 years ago. It was alot more difficult that the normal 2d tetris , but to me it was a bugger challenge.
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.
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
Of all the things you can accomplish by screwing up your face and swearing into a dark room, sleep is not one of them.
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.
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
"Sic Semper Tyrannosaurus Rex."
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.
err that should say "flask", I've been studying my Tetris too hard...
The paper says this:
We study the offline 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 offline version suggests the difficulty of playing the online version.
Really, having knowledge of the whole piece list is *easier* than winging it one piece at a time? I'll stick with regular Tetris, thanks!
[self duck];
F-bacher
James Tiberius Kirk: "Spock, the women on your planet are logical. No other planet in the galaxy can make that claim."
Will someone please tell me what happens when Tetris ends? Is it like the end of the rainbow ... pots of gold and all that good stuff? I always thought it just kept going until you lost (or, in the old days, spent another quarter), which show you how far I've gotten.
Michael"No live organism can continue for long to exist sanely under conditions of absolute reality;..."
I wonder if the computer got the rocket ship to launch. I only managed to do it once when I was young.
there is no cure for most cancer
Choosing the lesser of two evils is a choice for evil.
Tetris match of the century Kasparov vs. Deep Blue!! I think Gary can take him this time.
STOP ROCK VIDEO
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.
My life in the land of the rising sun.
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.
Humorless sig goes here.
If you are good at tetris you can play online tournaments at 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 they hadn't kept playing the game! Bad scientists!
You'd be amazed at some of the Heuristics you have to use at Level 10!
... 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.
In Tetris, the player and opponent are on completely unequal grounds. All the 'opponent' has to do is throw enough shitty pieces at you to prevent you from reaching the next level, or scoring enough points. No intelligence can triumph against a random number generator given such a disadvantage.
All I really have to offer to these researchers is a well-enunciated 'DUHH'.
sig-free as of 28 July 02!
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!
Are there any other NP-hard games which were invented by dead Russians?
Can't you be satisfied with one? I mean do you have any idea how hard it is to get dead Russions to invent anything?
Tetris wouldn't be NP-hard if it just released that damn 1x4 brick when you need it!
Beware: In C++, your friends can see your privates!
I'd like to see them reduce Tetris to Mindsweeper, another NP complete problem. That'd be slick.
Everyone knows that Tetris solves by matrix inversion...
FRA: STFU GTFO
Did somebody crack this while I had my back turned? Last I heard, NP-hard meant (among other things) that no known polynomial-time solution exists, but that doesn't rule out the possibility that one might exist.
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?
.. can't these guys find something slightly more practical to work on? Finding out if Tetris is NP-Hard... honestly.. do something useful with your existence.
My question is this: How is it Nintendo et. al. can program an incredibly skilled Tetris AI, but scientists at MIT cannot?
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.
blog |
"Only got there once though."
I began to hum one of the theme songs. I'm sure creating that infectious tune wasn't NP-hard.
Most folk'll never lose a toe, and then again some folk'll...
Amazing the kind of shit people get paid for.
evil adrian
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?
If we created a tetris that moves really slowly, with no speed increase and full look-ahead, I bet you could keep that game going for days.
I am extremely skeptical to their final result, and suspect they simply have not understood the game and algorithms required well enough.
Stop the brainwash
Crispin
----
Crispin Cowan, Ph.D.
Chief Scientist, WireX Communications, Inc.
Immunix: Security Hardened Linux Distribution
Available for purchase
The inventor of Tetris is alive and well. In fact, I just saw him give a talk while visitng UIUC at their Reflections and Projections conference.
"The only way to win is not to play."
Is Tetrisphere also NP-hard?
Someone set us up the bomb, so shine we are!
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".
For those who still don't get it: this is about the abstract problem of fitting tetris pieces together, not about pointing a videocamera at the screen, and have a second computer recognize the pieces. The second computer (the one "playing") already has all the information it needs in a suitable form, the only things it needs to do is decide how to place it. That's the problem that's NP hard, the problem is not figuring out that we this blue piece falling down is indeed L-shaped...
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.
http://penguinppc.org/~olaf/tetris_japan_finals.mp eg
or just do a search for filename in GOOGLE.
JAPAN Finals??? for Tetris The Absolute Plus -The Grandmaster2- DEATH MODE.
I Think he makes it look easy. 12.8MB Video. 5 minutes plus.
I'm curious whether people hundreds of years from now will still be playing Tetris (I would bet that they will be). I've been playing Tetris on the game boy for over 10 years now and it's still fun.
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.
What are you talking about, what did the army use quake to do? Either you are way off base or you didn't link to the story where the army uses Quake. Basically I am saying, WTF?
What these guys have proven is that the mathematical concept behind the game is similar to a very important class of problems, a class that includes such gems as "finding the optimal stacking order of packages in a truck" and "finding the shortest route between points".
;-)
As you are no doubt aware, these are really tough problems, which no doubt explains why packages always arrive late and damaged (slamming the packages into the truck, while not a proper mathematical solution, appears to be UPS' favorite way of optimizing their stacking order).
The good news is this: if one of the problems in the class is solved, solutions for all the others can also be derived from that one solution.
Corrolary: if you win at Tetris UPS will start to deliver on time, without damaging your package!
GET PLAYING! THE WORLD DEPENDS ON YOU!
You forgot to include goatse link! Here it is: Click here!
makes me want to play.
MIT's "Game Theory" division we heard about in A Beautiful Mind
I'm sorry.
Now somebody just needs to find a way to solve Tetris in polynomial time and they will be rich.
This guy is a quantum computer.
This reminds me of when the Air Force funded research to proove that the bumblebee couldnt fly. In the end, they were still wrong... PS2 version Maxed out the points, the system crashed. w00t. :) I loooovvvveeee Tetris, and no, MIT, it isnt hard, I could show you how to create perfect combinations with any pieces. And its even easier if you know ahead of time. So, yes, Tetris is hard, and bumblebees can't fly. ;) Oh wait you used MATH to figure out tetris? Well when they randomized the irregular pieces and patterns that follow different rule sets of COURSE you figured out that it wasnt possible to predict any ending. Chess doesnt have random pieces in random placements random combinations etc... same with checkers, connect 4, and many other games that can be predicted and WON. [I use connect 4 as an example because while it can be called similar to tetris you still have a limited number of spaces, and moves to play.] Tetris isnt a game about winning, its a game about individual skill. If you wanted to figure out how to predict scores for tetris, base it on user skill. Someone might be able to get 200, another person 500, another could keep it going forever... And if you really know how to play Tetris, you can see your faults and prepare for possible shortcomings, many many many turns ahead. "Always keep a spot waiting for those long 4 x 1 pieces."
Solving a game of Tetris always requires O(infinity) time, because there are an infinite number of pieces :P
:P) value to playing Tetris, since you actually don't know what pieces you're going to get. A computer will always be able to beat a human due to the fact that they can react faster. A computer playing the most conservative game will still kill a person, due to the fact that can probably go 'forever', while the person will top out at a certain speed as the game gets faster.
:P
:)
Anyway, I doubt this will really have much 'theoretically practical' (I say that because obviously there is no practical practicality in any of this
If you coded in a 'reaction time' into a computer program it might get interesting.
Ultimately, Tetris is really about risk taking. By building up, and keeping 'clean' structures to get tetrises, you're taking a lot of risk. The higher up on the screen you are, the more risk you're taking.
The other risk you take is in 'sealing off' a hole for a long piece that would get you a Tetris in order to clear off some blocks or whatever.
I would suspect that a computer program designed to calculate those probabilities and risk factors, even with just a simple engine for figuring out where to put the blocks would be able to beat a human player, perhaps even with the same restrictions on response times. In fact, I'd be willing to bet on it
(btw, I had one of the highest scores in my high school on ztetris, a version of tetris for the ti-8x calculators (written in z80 assembler.) I got up to level 17, and over 49k points for anyone out there who played that version of the game
Lonely?
Find love on the internet
Uh, I was just reading the full paper and came to this comment which summarizes an important fact omitted in the abstract:
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.What is it with all these bastards relating simple, enjoyable, time-wasting games with math? First I heard Minesweeper was NP-Hard. No problem, I don't use Windows so my goofing off wasn't affected. Now Tetris is NP-Hard. No big deal, I haven't played Gameboy snce I was 8 probably. (I can see it now... "When I was a kid, we played Gameboy in black and white after walking 15 miles in the snow, uphill, with no shoes on...") But I swear on my geekhood that if someone dares to ever apply math to Snood I will have their head.
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.
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.
I hereby propose the use of 300.000 home computers
to solve the NP-Problem.
Join the Tetris@Home distributed computing effort!
--- Eat my sig.
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..."
You're making something of a large, unproven assumption there.
The fact it's clearly right doesn't matter...
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
Heck, Tetris has been a part of distributed computing for the last decade. It's being ran on school calculators, Diablo II, keychain devices, cell phones, sides of buildings. EVERYBODY is helping to compile this complex riddle. Eat your heart out Seti!
What you just said makes no sense. Memory 'optimization'? optimization on what vector? (size, speed of access, what?)
The only thing I can think of is like garbage collection or fragmentation... but memory is linear not 2dimensional. You don't need to 'rotate' anything.
Lonely?
Find love on the internet
"I went into a Cancer Research and there was no research going on at all! Just a bunch of old women selling clothes. No wonder we haven't found a cure."
Never mind if Tetris is in some sense NP Hard. This is hardly relevant in light of the fact that classical Tetris games have a finite expected length even for an angelic player (that is, one who magically plays the best possible move without need for an algorithm). I thought the proof was well known ? Just involves considering a sequence consisting only of 'S' and 'Z' pieces and showing that certain sequences cause a monotonic increase in the amount of cruft at the edges of the board... To put it informally, who cares that it probably takes exponential time to find the best move given that the best move won't save you anyway ?
It just gets harder and faster untill you die.
/ernie cline. :P
Just. Like. Life.
Lonely?
Find love on the internet
This is clearly true if taken at face value, however if you consider your implications, you are making a large implicit (though IMHO true) assumption: that the human brain is computationally equivalent to a Turing machine.
Until we understand the function of a brain completely (no, we can't just assume it is perfectly modeled as an ANN), we can't make that sort of assumption.
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
We don't know the mind works, no. But what we do know is the mechanism by which it works. There is absolutly no reason to think that the brain can't be modeled on a turing machine.
Lonely?
Find love on the internet
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.
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!
... like is Defender NP-Hard? All those buttons and the left-handed controls... you had to be a twitchy psychotic to score well on that game!
I thought NP meant Not Particularly. duh
There is a fine line between being a cultivated citizen and being someone else's crop. - A. J. Patrick Liszkie
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)
I miss my rubber keyboard.(Homepage)
Could this be used in encryption somehow?
"Fighting terrorists with millitary might is like killing a mosquitor on your Dad's forehead with a rifle."
Not only that, but you could use Tetris as the foundation of a public-key cryptosystem. Knapsack algorithms are cool. :)
:)
Not that I'm suggesting anyone do this for anything other than geek points, mind you. Knapsack algorithms are in disfavor (several kinds of knapsacks lend themselves well to cryptanalysis). But still, you could do it.
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.)
I just wasn't thinking very hard about what problems one comes up against during a game - sorry.
These kids think that if it was made before they were born, the inventor must be dead.
Hmmph.
.sig last updated Jan. 14, 2000
Are there any other NP-hard games which were invented by dead Russians?
Is Russian Roulette NP-hard?
"""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."""
The assumption here is that the complexity of the offline version gives a lower bound for the complexitity of the online version (without look-ahead). This may seem intuitive, but it does not hold. The reason is that without lookahead, the computer player is not restricted to a fixed sequence of pieces that it presents. In that scenario it can give you all the bad pieces.
Consider it a 2-player game. Say the player builds this 4-layer hole with the expectation to complete 4 layers with the next 4-long piece. In their game, the player knows when this piece arrives. In online tetris, the 'giver' can observe this setup and decide not to give any 4-longs at all.
That article reads like something straight out of The Onion:
"He even wore a red, white and blue, Star-Star Spangled Banner tie to emphasize the patriotic sentiments behind his efforts."
"Its like Neil Armstrong walking on the moon. No matter how many people accomplish the feat afterwards, it will always be Armstrong who will be remembered for doing it first."
Is it just me, or did somebody else think of NP-transistors when they read "NP-Hard"?
(Zap! Kapow! Kersplat!)
....I think my geek factor just increased by 1 x 10^2...ouch...
No, Russian Roulette can be solved in O(N) time.
At worst, you only drink N/2 glasses (if not, you're already dead from a previous glass...)
So if Tetris is NP-Hard does that mean that Bust-A-Move is NP-Crap? It sure feels that way...
[n8.r0n] http://petesweb.spymac.net/
I am quite shocked to see someone downmodded my suggestion we experimentally test the conclusion of the paper. They have created a theory that can be tested. Let's test it, folks.
The knowledge we have today comes from a careful interplay between theory and experiment. They have set forth theories that can be tested and verified. What appears to be solid logic may also have loopholes in it - maybe even hidden deep into the assumptions. Experimentation can at least sometimes expose incorrect theories.
So - get a grip, and lose the awe of what appears to be definite proof for the NP-completeness of the game you've struggeled with for so long.
Stop the brainwash
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.
Computers might have difficulties playing Tetris, some humans definitely do not. Check out this unbelievable movie if you want to know what I mean:e tris_ja pan_finals.mpeg
http://www.nem3d.net/download/movies/fun/t
but that doesn't give them the right to flat-out make up words. "Inapproximability" indeed!
Thanks,
--
Matt
Here's a Europop version of "Korobeyniki", which many players think of as "the Tetris song".
Will I retire or break 10K?
Consider it a 2-player game. Say the player builds this 4-layer hole with the expectation to complete 4 layers with the next 4-long piece. In their game, the player knows when this piece arrives. In online tetris, the 'giver' can observe this setup and decide not to give any 4-longs at all.
In most official TETRIS® products, each player has an independent PRNG seeded from the same value at the start; thus, the game gives the same pieces in the same order to both players. Thus, if you're not getting any sticks, the other player is just as screwed as you are.
Will I retire or break 10K?
Actually, the author (Alexey Pajitnov) may still be alive - but one of the co-authors [not sure to what degree - credit amongst authors is vague] of Tetris (Vladimir Pokhilko - see also: Dmitry Pavlovsky and Vadim Gerasimov) is indeed dead; murder/suicide.
http://www.kinox.org/articles/tetris.html
I learned about this through his last venture, AnimaTek, which created the excellent Animatek World Builder virtual worlds renderer.
http://www.digi-element.com/awb3_overview.shtml
I'm personally convinced that Tetris and all its clones have a highly sophisticated masochistic AI.
I don't know about most Tetris clones, but I do know that Tetanus On Drugs has only a simple linear congruential PRNG, not some sadistic AI.
Will I retire or break 10K?
http://www.math.uic.edu/~burgiel/Tetris/explanatio n.html
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.
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 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 at Clay for a really good description (unfortunately too long to quote here). And lastly, you might want to check out Tutorial: Does P = NP? at VB Helper for a little more info.
Ok, but what is it good for? The Compendium of NP Optimization Problems is a great place to look for real world examples of NP problems. Including everything from flower shop scheduling [nada.kth.se] to multiprocessor scheduling.
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. :)
-- null
Just for accuracy's sake ;)
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]).
I had Tetris from Windows Entertainment Pack, and finally reached a score so high (>~30000 something) so that it went negative and I ended up with -19000.
:(
I also remember a 3D tetris clone probably called Helltris or something. Can't remember and I can't find it
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.
¦ ©® ±
Can someone simply explain the meaning of NP Hard and NP Complete?
I played tetris lightly, but never owned it or played too much. Although, it (and some other games) a few times had me dreaming about playing (like, literally had me arranging blocks in a dream).
:-) We even had to take bathroom breaks. We were just so into the game that we were TOTALLY in the kirby zone. Kind of like when you're typing and you just hit exactly the right keys more quickly than usual, we were just placing the globs so perfectly and makin so many pumpkin combos :-)
However, when I was about 14, I played a match of Kirby's avalanche against my friend's au pair (mom was divorced and he had a little bro). We had been lpaying all summer, so we were pretty good, but this match lasted well over an hour. The game speed got ridiculous, where the pieces seemed to fall as fast as the graphics processor could display them
Ahhhhh, those were the days!
$8.95/mo web hosting
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?
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
It's so hard to win on Tetrinet. I always thought the winners cheated using bots, but now this tells me that isn't possible.
This guy is amazing. I think he might have solved this tetris problem in O time, but isnt telling anyone.
a n_ finals.mpeg
http://www.vulnerable.org/pics/video/tetris_jap
Obviously loads of people love Tetris. My favourite game is Sokoban, which is beloved of AI researchers as it is P Space complete.
Oh, and it's available for sed, as well as emacs
- Derwen
http://fsfeurope.org/
At least there's one geek classic that refuses to fall to the scrutiny of mathematicians.
'Go' is another.
But is Dr. Mario NP-Hard?
REAL geeks play Welltris and Blockout!!
~REZ~ #43301. Who'd fake being me anyway?
I've been playing Tetris seriously for a long time, and I've always put the hole on the right side...
Because of the width of the board and where the long piece is initially placed, it takes one extra translation move to get it to the left side of the screen.
I've tested putting the hole in the center and in various other locations, but I found it is much simpler to control one wide stack with various places for different blocks, instead on two stacks with only a small number of places for blocks.
When you get up to level 19 and above, things are moving so fast that the controller doesn't handle moving back and forth very quickly... you need to move pieces in a general direction (like all of them to the right, then slowly building to the left).
All of this is on the NES Nintendo brand of Tetris. I have played other versions, but none as extensively. I would love to know the optimal strategy, but I think each player chooses which one works best for them (so even though the center may be optimal, I like the left better). My best score was 470,000... The guys at TwinGalaxies have the top score at 999,999 which seems impossible to me.
IANAL, but I play one on
So next time around, is Deep Fritz going to compete in the world Tetris competition? From what I gathered, the big machine had a stored set of the chess moves and their optimal countermoves.
Tetris, it seems, could not even be pre-stored in such a way?
Not counting how the blocks will speed up, does this mean that humans have a better chance of winning at tetris than at chess?
What is this game tetris I've been hearing a lot about? Any good? How much does it cost?
Just keep giving it those * :P
**
*
Peices. You'll never get a tetris that way
Lonely?
Find love on the internet
Wow, and to think all these years I've been playing Tetris ever so diligently, trying to come up with all the combinations and permutations of the game just so I can prove the same thing by brute force.
I'm not sure I know what to do with my life anymore.
It is hardly news when yet another game is shown to be NP-hard. Consider that mindless solitaire game played with Mah Jong tiles called "Shang hai", where you can remove pairs of tiles that match and have exposed left or right edges. Even if there's only one layer of tiles, so you can see the entire state of the game at the start, determining whether it is possible to remove all the tiles is NP-complete.
An easy exercise for the bored nerd.
Is it just me, or is NP-Hard different from NP-Complete. I thought NP-Hard was unsolvable (i.e., the halting problem), whereas NP-Complete was intractable.
Do I really need to break out my computation books again?
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.
I put the 'fun' in fundamentalism
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."
I suspect it's similar to Go in that respect. People have been trying to make a computer good at Go for quite a while with limited success.
Although with Tetris, I'd assume that even though there isn't a good way to guess the quickest way to win, it is probably trivial to make a computer halfway decent at playing tetris.
that's no necessarily true. I always make gay comments when talking about Bill Gates or his underlying commercial product dick sucking.
> 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:
I don't know what slashdot you're thinking about, but I'm reading the version where no one reads the article.
Hell he mentioned X and Y in his post somewhere, so it MUST be insightful. I didn't even bother reading his whole post, I'm too busy playing flash adventure to care.
Triptych is like tetris with real physics. Blocks bounce and rotate a *full* 360 degrees;. It's addictive as hell - Works on Linux, Mac and Windows too!
Be sure to check out Pontifex - build bridges...One of the most addictive games I have ever played!
The controller won't let you place a piece off to the side fast enough. Even if you spot where it should be, the piece drops so fast that its only feasable to play the bottom 4 or 5 lines. Now thats hard.
I once won a Nintendo championship here in WA state back in 85. The game consisted of mario, rad racer, and of course, Tetris. However, the game wheighted the points the heaviest on Tetris. I love that game! Still do! It's a classic, like Metroid and Zelda.
Tetris is basically bin-packing...I don't see how this was a surprise. Guess what? Arranging your inventory in Diablo is just as difficult...
How about another challenge? Try scoring as many points as possible without getting a single line.
Back on Nintendo after you scored a certain amount of points (like 25000 or so) you would see a rocket take off. The rockets got progressively larger and more complicated looking as your score increased.
After an hour and a half of my fingers going crazy, I reached my highest score ever. I could not wait to see this! To my shock there was the dinkiest little rocket (it is the first one they show you) and while I was screaming ripoff at the tv, the kremlin, which is always next to the pad, ends up blasting off!
It was the single coolest video game surprise of my childhood.
--Joey
Don't get me wrong... I love mathematics and I love tetris... but ouch. Who honestly cares that much to dedicate so much time to something like that?
http://www.accountkiller.com/removal-requested
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.
Professional Wild-Eyed Visionary
That would be why they used them for arcade games.... you cant win. That was the point, you need not prove it.
My UID is prime and so is this number: 09 F9 11 02 9D 74 E3 5B D8 41 56 C5 63 56 88 C0.
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
The Raven
wouldn't you like to have a job like this - play a game and state the obvious: "it's hard"
how about playing with counter-strike all day, 365 days a week and declare it as R&D effort related to co-opetition...
Have any of you played a DOS game called BlockOut! I used to get real kicks playing that. It was like looking down from above, into the Tetris Well. I wonder what the difficulty levels of such a game could probably be! (I presume Maths won't get simpler, 2d to 3d!)
Centralization breaks the internet.
Yes, there's been some productive analysis of the endgame, but that's So Vastly Simpler than the opening or middle game.
More here. .
I understand go is EXPTIME-complete or EXPSPACE-complete depending on the ko rule (which isn't that central to the flow of the game).