All the Best Games May Be NP-Hard 322
Catullus writes "Following in the footsteps of Tetris and Minesweeper, the simple yet addictive multiplatform game Flood-It is the latest puzzle to be proven to be hard — NP-hard, to be exact. This means that there's no way to write an efficient program to beat the game, unless P=NP. This research by computer scientists from Bristol University raises the intriguing question: are these games fun precisely because they're hard for computers to solve, and need a spark of human creativity?"
Oblig XKCD (Score:3, Funny)
Re: (Score:3, Insightful)
Re:Oblig XKCD (Score:5, Informative)
Re: (Score:3, Interesting)
Re: (Score:3, Insightful)
Re:Oblig XKCD (Score:4, Funny)
I tied the top score!
0 (zero)
Re:Oblig XKCD (Score:4, Funny)
I doubled your score, Loser!
Re: (Score:3, Informative)
I made a nice line yet got no points. I guess they weren't thight enough or they just never plugged in the points calculation :)
Re: (Score:2)
Re: (Score:2)
Re: (Score:3, Informative)
First Person Tetris [firstpersontetris.com]
The fun is in the simplicity (Score:5, Insightful)
Tetris, to me, is the ultimate video game. It can be played by anyone ranging from someone who doesn't even know what a video game is all the way to competitive level hardcore pros.
No other video game in history has that kind of audience. The fact that, although variations on the original have been released, the most popular version is still the original version (which has remain mostly untouched throughout its existence) just gives more credit to its simplistic genius.
Re:The fun is in the simplicity (Score:4, Interesting)
I would argue that Mindsweeper has a far larger audience. And, yes, there are competitive mindsweeper players and leagues.
Re: (Score:2)
Not sure if I would agree with Minesweeper having a larger audience, however you are certainly correct in that Minesweeper also transcends gaming skill much in the same way as Tetris. I stand (sit?) corrected.
Re: (Score:2, Informative)
>>>Not sure if I would agree with Minesweeper having a larger audience
How many users of Windows are there? Approaching 1 billion homes? That's a bigger audience than even the best-selling console (~150 million PS2s) ever reached.
Re:The fun is in the simplicity (Score:5, Funny)
exactly, because every single windows user plays minesweeper, but not tetris which is unfortunately only available for ps2.
Re: (Score:2)
I think my point is that Minesweeper has been sitting on nearly every desktop in the world, from Windows 3 (1990) to Windows 7 (2010). Other games have not. QED Minesweeper has far wider "coverage" to borrow a term from Nielsen television.
Re: (Score:2, Informative)
I think my point is that Minesweeper has been sitting on nearly every desktop in the world, from Windows 3 (1990) to Windows 7 (2010). Other games have not. QED Minesweeper has far wider "coverage" to borrow a term from Nielsen television.
But if Windows users had the choice of the two, Minesweeper or Tetris, automatically available to them, I'm confident that Tetris would win hands down.
What was Peter playing in OfficeSpace? Not Minesweeper.
Re: (Score:2)
That doesn't mean they play mindsweeper. My mom has windows XP, but she uses my old gameboy to play tetris. Also, its not like there isn't a tetris clone made for every popular OS.
Re: (Score:2)
Come on...not everyone that uses Windows regularly plays Minesweeper.
Re: (Score:2)
Come on...not everyone that uses Windows regularly plays Minesweeper.
That's because it's a lousy game—there's no guarantee that it can be solved by logic; often you reach a point where you must guess. There's a variant I had on my (now abandoned) Palm Treo that was guaranteed to be solvable by logic. Can't remember who made it now.
Thinking about this, I was at first tempted to say that the first (Windows default) variant of the game is more difficult to solve by a computer (i.e. via an algorithmic solution), while a program could easily solve the second variety. But t
Re: (Score:2)
Yep, I recall an interview with Bill Gates years ago regarding Minesweeper. He was asked what his best time was and it was something like 1 second. The interviewer asked how he did it. He said he'd just randomly click until he got the 1 second score.
[John]
Re: (Score:2)
even higher yet. the thing is on every OS that exists, basically.
Re: (Score:2)
Is that what the army recruiter told you?
Re: (Score:2, Offtopic)
No, but you are inobservant. It's called Minesweeper.
Re: (Score:2)
Re: (Score:2)
Yes, but like checkers, just about ANYONE with basic cognitive functions can play Tetris...the concept itself very easy to understand.
A minute to learn, a lifetime to master comes to mind...
Re: (Score:2)
Re: (Score:2)
I remember when I first played Tetris on a Nintendo Gameboy. I was unimpressed.
Later I tried it again, and determined it was more fun that I initially thought, but whenever I play Tetris I grow tired of it rather quickly (less than half an hour). My longterm gaming addictions are: Space Invaders (Atari 2600/VCS version), Asteroids, Missile Command, and Ms. Pac-Man (arcade). I can play these games hour after hour.
I also like to revist simulations like Tom Clancy's Red Storm Rising. Boring graphics but
Re: (Score:2)
Have you played pac man C.E.? best pacman ever.
Tetris lasts five minutes now (Score:2)
whenever I play Tetris I grow tired of it rather quickly (less than half an hour).
That's why new versions of Tetris take five minutes to play through: either they're two- or three-minute time trials, or they speed up so fast that you're dead after 5 minutes. Watch this video [youtube.com] all the way through.
Re: (Score:2)
Heck, Go is even simpler than checkers, and it's nowhere even close to being solved (the current, top-ranked computer program is roughly 2p, and easily defeated by a strong professional player).
Re:The fun is in the simplicity (Score:5, Insightful)
Go is simpler than checkers? Is that a joke?
It's not a joke. I can write a program to solve Go in about a dozen lines of code, without even trying to compress it. It's about as complex as tic-tac-toe.
Building the computer that can complete this program before the heat-death of the universe? That's merely a hardware issue.
Re: (Score:3, Informative)
Are you saying that you couldn't write a program to solve checkers in twelve lines of code?
Such a simple brute force solver still needs an executable specification of the rules that converts a board state and a move into a new board. For checkers this function is simple. For Go this function needs to check the freedoms of each cluster of stones and would thus require recursion. This alone would make it a more complex program than the checkers solver.
Re:The fun is in the simplicity (Score:4, Informative)
I think your using a poor choice in words. Your saying that go has a simpler rule base than checkers, ie it's easier to determine whether a rule is valid or not, correct? Not the actual strategy and hence wining of the game.
Considering that checkers is a solved game with 10^31 moves. Chess being 10^50 and Go an estimated 10^80 if I recall correctly.
So figuring out a valid move may be easier in Go than in checkers; however, it's the gameplay/strategy that really counts.
Re:The fun is in the simplicity (Score:5, Insightful)
Tetris, to me, is the ultimate video game. It can be played by anyone ranging from someone who doesn't even know what a video game is all the way to competitive level hardcore pros.
No other video game in history has that kind of audience..
Wrong. The concept of a game being easy to begin playing but difficult to master dates back to Chess and even Go. As far as modern day video games are concerned there are a lot that actually fall into this category. I believe the phrase was first coined by Nolan Bushnell [wolfsheadonline.com] but I could be wrong.
You are free to say that in your opinion of "easy to learn, difficult to master" video games, Tetris is the ultimate. But even video games like Donkey Kong or Pac Man have the same simple laws that a novice understands which gradually become more and more restrictive until the true "mastery" title is nearly impossible to attain -- kill screen, anyone?
If you're designing a new video game, that seems to be one of the fundamental requirements so that you aren't too off-putting to new players. You can play World of Warcraft at your own pace and although the UI and input is infinitely more complex than Tetris, it exhibits this basic rule of thumb for game design -- quite successfully. That's why it enjoys a worldwide audience of 10+ million.
Tetris is legendary and fun but modern day video games (like the popular flash puzzle games) are building past Tetris while trying to maintain the principles that made it successful. I predict you're going to be upset that I might have just compared Tetris to Bejeweled but lets face it: they're both simple insanely popular video games that have a large swath of difficulties that seem to algorithmically scale in later levels.
As an avid Tetris player, I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?
Re: (Score:2)
Good points, all :-)
As an avid Tetris player, I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?
My definition would be when one starts to compete in tournaments...hence the "competitive level" and "pro" sandwiching the "hardcore" label.
Can you beat colour_thief? (Score:2)
I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?
Usually that happens once you get into the 8000s on Tetris DS or you can get M in Master or Death on TGM2+. Then you get to the tournament (i.e. "competitive level") and find that this ni**a can still steal your colour [youtube.com]. Two places where the hardcore players hang out are harddrop.com and tetrisconcept.net.
Re:The fun is in the simplicity (Score:5, Insightful)
There's a problem, though - both Go and Chess are generally multiplayer games. Tetris is in its purest form singular. Any sort of competitive game is much harder to get into for a novice, as it is only fun for them to be playing other novices, and you have the situation you see in general with Chess and Go - the few people who are really good, and the many who rarely play because they do not have the dedication to compete.
Look at the many addictive "casual" games - almost all of them are single player, and the ones that are multiplayer (such as farmville, or even wow) are multiplayer mostly in the social aspect than in the competitive aspect. There's a reason the majority of WoW players are on PvE. When you are facing a controlled computer opponent, you can apply a constantly ramping difficulty level that starts at a place a novice can still have fun. When you're playing competitively, the moment you have a significant skill imbalance the fun disappears.
Re: (Score:2)
Tetris, to me, is the ultimate video game.
You're in very good company. Warren Spector, especially when discussing video games as art, calls Tetris to be the greatest game ever. Something to do with it exemplifying how games, like all other art forms, can do things the others can't, which he believes is what game developers should make it their mission to do.
Sokoban (Score:5, Interesting)
FYI, Sokoban is NP-hard as well (according to wikipedia). I'm seeing a pattern here...
Re: (Score:2)
PSPACE-Complete: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.41 [psu.edu]
Re: (Score:2)
I'm seeing a pattern here...
..."People like puzzles"?
Re: (Score:3, Funny)
"I'm seeing a pattern here..."
Are you sure? Maybe determining if the pattern is correct is also NP-hard.
Re: (Score:2)
So you think there's a good game behind that? ;)
Re: (Score:2)
"I love humans. Always seeing patterns in things that aren't there." -- The Doctor (8th)
Re:Sokoban (Score:5, Informative)
Note that NP-hardness isn't about the average case, it's about the worst case. Many proofs of puzzles being NP-hard essentially go: "I can make a playing field so that the puzzle is only solvable if a related Boolean circuit can be satisfied, and I can transform any Boolean circuit into a playing field in this manner". Such a proof only tells you that these "gadget puzzles" (transformed circuits) are as hard as SAT, it says nothing about the average puzzle.
As another example, consider a problem where the input is either 0, an integer, and a number of integers; or 1, and a number of integers. Then the decision problem is defined as "if the first number is 0, then true if the second is the sum of all the subsequent integers of the input; if the first number is 1, then true if the circuit defined (in some given format) by the subsequent integers can be satisfied". Obviously, this problem is NP-complete because you can turn any SAT problem into an instance of this problem; but if the first number is 0, the problem is trivially decided.
Incidentally, that's part of the reason why cryptosystems based on NP-hard problems have done so badly: while the cryptosystem might be hard to crack, worst case, it usually turns out most instances of encryption can be broken.
Re: (Score:3, Informative)
Briefly (and wrongly, but it will do for a slashdot reply), NP complete problems require the computer to actually calculate all of the possible solutions and see which one is best rather than than using an algorithmic shortcut. For every extra item that has to be computed the complexity increases by quite a large amount relative to the difficulty of the smaller problem. The traveling salesman problem is the classic example - adding another town to visit means you have to recalculate all the routes because t
Just to throw this out there (Score:5, Informative)
Since I had to suffer through at least one professor who didn't understand basic complexity theory last night, and I know that Slashdot generally screws it up to.
NP-Hard means that there's no (deterministic) polynomial-time algorithm to solve the games. Additionally, you always have to generalize these games in order to make that claim. Since computational complexity is defined in terms of the length of the input, and certainly all of these games are being played on an input of fixed length.
However, there are effective approaches to solving NP-Hard problems. There are solvers for known NP-Hard problems. If you Google "sat solver" you'll find at least 5 that you can just download. SAT solvers are used in VLSI validation and other practical things. These solvers use heuristics to improve search performance, generally proposing answers and checking them (for NP-Complete problems).
Also, there are tons of games known to be NP or PSPACE complete. The reductions for those games are kind of a standard problem, since the AI community writes a bunch of these solvers.
Re:Just to throw this out there (Score:4, Funny)
I have no idea what you just said. Can you use a car analogy?
Re:Just to throw this out there (Score:5, Interesting)
Re: (Score:2, Interesting)
I should caveat all of this. The "no polynomial-time algorithm" bit is only true if P!=NP. If P=NP, then there is a deterministic polynomial-time algorithm for NP-Complete problems. NP-Hard, however, just means that it's at least as hard as NP, so, it's possible that there's no algorithm for that harder problem. You have to be really really precise when talking about this stuff.
Re: (Score:3, Informative)
The "no polynomial-time algorithm" bit is only true if P!=NP.
And to the best of human knowledge, it happens to be the case that P!=NP.
I solved it (Score:5, Funny)
N=1
P! = N * P
(P-1)! = N
(P-1)! = 1
P = 1
Now where in my Nobel Peace Prize.
Re: (Score:3, Interesting)
Even more, you have to know what problem you're trying to solve. There are two obvious possibilities:
The first is NP-Hard. But the second may be much easier... if possible, come up with an algorithm to solve every puzzle of that nature in 25 moves. Then your answer would always be yes (a tautology), and the problem is no longer NP-Hard. It's the same as if I asked if every puzzle w
Re: (Score:2, Interesting)
Since I had to suffer through at least one professor who didn't understand basic complexity theory last night, and I know that Slashdot generally screws it up to.
NP-Hard means that there's no (deterministic) polynomial-time algorithm to solve the games
Sadly, you seem not to understand the term yourself. NP-Hard means that given an efficient (deterministic polynomial-time) algorithm to this problem, one can devise an efficient algorithm for any NP problem, so any problem for which solutions can be verified. It might not mean that they aren't solvable (they are solvable efficiently iff P=NP), and a problem might not be solvable and still not NP-Hard. Discrete logarithm and factorization, for example, are suspected to be neither polynomial time computable n
Re: (Score:3, Insightful)
We might be attracted to hard problems, but since humans are unable to run algorithms in their heads, why would we use the notion of computational complexity for this "hardness"? It seems more likely that generating problems in the way we do is likely to produce NP-Hard problems than to say we're interested in them as games...
The appeal of these puzzles is that they're hard to solve but easy to verify the solution. If the puzzle were easy you'd get bored, and if it was difficult to verify you'd get frustrated. That's why I always look for the "Certified NP-Hard" sticker on the side of my new board game purchases.
Re: (Score:3, Interesting)
Ah, it doesn't mean that either. :-)
If a problem is NP-hard, it means it is at least as hard as any other problem that can be solved in polynomial time on a nondeterministic computer.
It is an open question (P=NP) whether this is equivalent to saying that there is no deterministic polynomial-time algorithm.
"human creativity"? (Score:5, Insightful)
Re: (Score:2, Insightful)
Nothing really. It's just further proof that kdawson is even more incompetent than Jon Katz.
Why?! (Score:2)
Probably because like any other good problem, they both offer a problem and they help start the solving process.
chess and go aren't np-hard, but they are also fun (Score:2, Insightful)
so where is the pattern?
Re: (Score:2)
The generalizations of both games are NP-Hard. They're only constant time because of the fixed number of pieces and places for those pieces to go.
Re:chess and go aren't np-hard, but they are also (Score:5, Informative)
Chess and Go are actually EXPTIME-complete, even harder than NP-complete problems and PSPACE-complete problems.
In general, one-player games of bounded length (like Flood-It, or Sudoku) tend to be NP-complete; one-player unbounded games (like sliding-block puzzles, or Sokoban) tend to be PSPACE-complete; two-player bounded-length games (like Hex, or Amazons) also tend to be PSPACE-complete, and two-player unbounded games (like Chess, Checkers, and Go) tend to be EXPTIME-complete.
I can't resist here a plug for my book (with Erik Demaine), Games, Puzzles, and Computation [amazon.com], which discusses all these issues in detail. A theme running throughout the book is the same as the view expressed in this paper: most interesting games and puzzles seem to be as hard as their "natural" complexity class, outlined above.
Re: (Score:2)
Get me a kindle version of that book and I'll consider purchasing it!
Re:chess and go aren't np-hard, but they are also (Score:5, Interesting)
I'll mention it to my publisher, but honestly it would lose a lot without all the color figures.
The book is based on my Ph.D. thesis, which you can download for free:
http://www.swiss.ai.mit.edu/~bob/hearn-thesis-final.pdf [mit.edu]
Humans are *not* good at such games--see Sudoku (Score:2, Insightful)
NP-hard just means you (most likely) need an exponential search. Maybe you want to take this as evidence that human creativity is needed, but that's a stretch. Humans don't do better than computers on NP-hard problems. In fact, they almost certainly do worse, because if you cannot skip the search part, computers are tremendously faster at that. See how quickly a human solves a sudoku, vs. a computer. Even though it's NP-hard (for arbitrary dimensions).
Of course the whole thing depends on the base of the exp
No. (Score:2, Interesting)
are these games fun precisely because they're hard for computers to solve, and need a spark of human creativity?"
No. The human mind is created by the brain which is governed by the laws of physics. The laws of physics are mathematical, so fundamentally the human mind is an algorithm. Because of Turing completeness, there's fundamentally nothing that the human mind can do that a computer cannot. It's not easier for humans to solve NP-hard problems. We just come with better software for it.
Re: (Score:3)
The human mind is created by the brain which is governed by the laws of physics.
Rubbish. While the underlying biochemical reactions occurring in the brain are completely dependent on physical laws, the actual connections between neurons, expression of certain genes in certain cells, and levels of neurotransmitters and receptors are governed by a myriad of factors. These factors range from past experiences, conditioning and training to diet, to current amount of sunlight, etc. The brai
Re: (Score:3, Insightful)
While the underlying biochemical reactions occurring in the brain are completely dependent on physical laws, the actual connections between neurons, expression of certain genes in certain cells, and levels of neurotransmitters and receptors are governed by a myriad of factors. These factors range from past experiences, conditioning and training to diet, to current amount of sunlight, etc.
All of which are fundamentally governed by the laws of physics. Math.
Physics cannot explain why I, at this instant, cho
Re: (Score:2)
All of which are fundamentally governed by the laws of physics. Math.
I think you're equivocating here. Governed by physics, yes, but not by math. Math is the language of description, not the laws themselves. So the equivocation here is between description and causation. Mathematics describes in a human/machine cipherable language the seemingly immutable physical principles of the universe. This type of sensual observation falls prey to Hume's complete skepticism, that we cannot say something is fundamental just because our experience of it has never been controverted. That'
Re: (Score:3, Interesting)
We just come with better software for it.
We also come with better hardware for it. For now...
Re: (Score:2)
The laws of physics are mathematical, so fundamentally the human mind is an algorithm.
This is where your logic breaks down. The laws of physics are mathematical, but that does not imply that the things they govern are algorithmic. The laws of physics govern the roll of dice, too, but you aren't saying there's a dice algorithm, are you? (if you are, cut me in, let's go make billions in Monaco, sound good?)
Because of Turing completeness, there's fundamentally nothing that the human mind can do that a computer cannot.
...love?
Re: (Score:2)
The laws of physics govern the roll of dice, too, but you aren't saying there's a dice algorithm, are you?
Of course there is. It's just incredibly complex. We could not possibly measure all the variables with enough precision to predict a dice roll. Doesn't mean there's not an algorithm.
Re: (Score:3, Interesting)
This is the old "is the universe deterministic" debate that's been raging for thousands of years.
My personal suspicion is that we would need to measure the variables to a sufficient degree of precision that we would hit the realm where physics is no longer strictly deterministic, i.e. that changes at the subatomic level could potentially alter the result. That's probably an overbold claim for dice (unless I want to throw in a "for sufficiently well-constructed dice" weasel), but even so, it may be the case
Re: (Score:2)
The idea the human mind is best understood as a physical object acting on itself, has always rubbed me the wrong way.
While having a basis in fact, it is not the most USEFUL model of the human mind.
It is like a book review that focuses on the number, length, and repetition of words in a book.
Based in fact, yes. But useful? No.
Fun == uncertainty (Score:5, Interesting)
Part of "fun" is uncertainty, a sense of challenge and the subsequent realization when you succeed, when there is no threat to more basic needs [wikipedia.org]. Such feelings would be lessened if solving the problem was a sure thing (or if on the other extreme it looks unlikely to solve, but that's off the topic), and that's why we pick games/levels according to our skill.
Indeed, to me Minesweeper quickly becomes boring, since most of the clicking obeys pretty simple rules ("2-3-2 along an edge - that's clear-3mines-clear"); then at the end it often becomes undecidable and it's eeny-meeny-clicky-boom.
Co-op minesweeper (Score:2)
Indeed, to me Minesweeper quickly becomes boring, since most of the clicking obeys pretty simple rules ("2-3-2 along an edge - that's clear-3mines-clear"); then at the end it often becomes undecidable and it's eeny-meeny-clicky-boom.
That's when you start playing games that slowly solve the boring stuff for you. My own Luminesweeper [pineight.com] is one of them: a line periodically sweeps across the screen and solves squares using the single-point method [neu.edu]. So it almost feels like you're playing co-op, and the goal is to do as much as you can to promote a healthy alternation between the hard stuff (your task) and the easy stuff (the CPU's task).
Re: (Score:3, Interesting)
Part of "fun" is uncertainty, a sense of challenge and the subsequent realization when you succeed, when there is no threat to more basic needs. Such feelings would be lessened if solving the problem was a sure thing
That's what my wife said when I asked her why she cheated on me.
Tetris is hard to solve? (Score:2)
Re: (Score:2)
The game can be theoretically played forever on an imperfect generator as long as you don't hit an endless stream of Z and S blocks.
In fact, it's against the rules for the game to give you a long stream of blocks. Tetris games since 2001 dish out pieces 7 at a time [harddrop.com], and the most snakes in a row that you'll ever get is four: xxxxxSZ|ZSxxxxx. This leads to an easily computable strategy for playing Tetris forever [harddrop.com].
I'll just have to prove P=NP then. (Score:2)
Look, I'll fire up a few smokes and toss back a cold one and sort out this whole P=NP problem for you.... I'm sure that I can come up with it right away... how hard can it really be? Tongue firmly in cheek!
Re: (Score:3, Funny)
Proving that P = NP is easy... you just have to start with contradictory premises.
Book on the Complexity of Games and Puzzles (Score:3, Informative)
Are there examples of games that AREN'T NP-hard? (Score:3, Insightful)
P = NP, eh? (Score:3, Funny)
I already wrote a solver for this exact game. It just isn’t efficient.
Re: (Score:2)
Tetris and Minesweeper fun? (Score:2)
I do not know about anyone else, but I never really got how anyone considered these games fun.
However-- (Score:2)
I think discussing your new iPhone game on slashdot is an NP-Easy way to get a substantial popularity boost.
I don't get why... (Score:2)
I don't get why people talk about NP hard in games that generally have fixed-sized worlds. The whole point of complexity in computer science is to talk about how an algorithm can scale up with N, but when N is fixed I would argue that the algorithm's complexity doesn't even matter; it is fixed for that game.
For example, who cares if an AI takes 10x longer every time you add 1 to the width of a tetris world? 99.999% of people play on a 10x20 board. When I hear someone say "blah" is NP hard, I always ask "wha
Re: (Score:2)
The reason that fun games tend to be NP-hard (or harder) is that if a game's "physics" supports interesting constructions requiring complex reasoning to solve, then probably that same physics can be used to build computational gadgets, which is how you show hardness of the generalized version. This quality expresses itself even on small, fixed-size board.
Floodit record (Score:2)
24 turns, but I'm a beginner.
nonsense (Score:5, Insightful)
This means that there's no way to write an efficient program to beat the game, unless P=NP.
All these games are small finite size in practice, so asymptotic complexity results tell you nothing about how difficult it is to solve them. In addition, the idea that "P = efficient program" is utter nonsense; for large problems, even quadratic complexity is a serious problem. A realistic notion these days is that a reasonable asymptotic complexity for "efficient programs" is no worse than n log^k n for small k. Anything larger than that and it won't scale. The converse is also nonsense. Just because a particular problem is NP hard in general doesn't mean that the problem instances you encounter in practice are hard cases. Furthermore, the assumption that you need to find an optimal solution is also wrong. In fact, in any competitive game, all you really care about is beating the other guy.
P=NP is a neat theoretical issue in computer science, but its practical significance has been completely overstated.
hands up... (Score:4, Interesting)
Who has no fucking idea what any of this means, and is only further confused by the wikipedia articles written by nerds who have no communication skills.
Re: (Score:3, Interesting)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Well, I think in the end he means something more along the lines of "why is the story tag visible on the front page". I find it annoying too sometimes.
Re: (Score:2)
What does this say about WoW, if it can be played quite successfully by a bot?
I'm sure that many NP-hard problems exist in WoW. Obviously, farming gold and leveling are not NP-hard. But other questions such as, "Can this raid boss be defeated?" would be extremely difficult in the general case.
Something that hasn't really been mentioned yet is that in NP-hard games played by humans, the difficulty has been dumbed down for humans. The versions played by humans have a very small problem space (Tetris, Sudoku) or avoid the nasty cases that are NP-hard (Picross). Some others like Mine
Re: (Score:2)
"Not a chance, you can play it half asleep without a single thought, just as easy as writing or talking. I've written a relatively simple algorithm for a computer to play tetris, it enumerates all possible options of placing a piece and compares certain properties of resulting landscape (number of holes, smoothness of surface, etc). Of course it is not perfect, but it can easily outplay most human players without any problems."
They probably tried to find an algorithm to actually *win* Tetris and failed. The