Slashdot Mirror
All the Best Games May Be NP-Hard
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?"
I'd say that this is most definitely NP, for humans and AI alike.
UNIX? They're not even circumcised! Savages!
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.
Living With a Nerd
FYI, Sokoban is NP-hard as well (according to wikipedia). I'm seeing a pattern here...
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.
sorry to burst your bubble, but there are many poly-time approaches to solving NP-hard/complete problems that are "good enough" for many purposes. and vice versa - many (most? all?) problems that are poly-time, humans solve using heuristics that lead to often sub-optimal solutions. so what exactly is new here?
weinersmith
so where is the pattern?
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 exponent. It's true that many hard problems are hopeless for computers while humans do detect some patterns and make some progress. (E.g., searches for mathematical proofs.) But the games listed have pretty well-defined, fairly small search spaces.
Plus, the proof for NP-hardness is for arbitrary sizes, not the usual dimensions that humans play the game at. Computers are hands down better at that.
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 (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.
This post contains no rudeness or derision of any kind. All arguments are friendly. Terms and exclusions may apply.
There is a fun book on this topic called "Games, Puzzles and Computation" by Hearn and Demaine that is well worth a read if you're interested in puzzles or complexity.
It seems to me that earning the title of being NP-hard is very easy for games. As someone said before, even sudoku is NP-hard, but intuition-less computers are still much faster at it than humans with all their intuition. So where is the list of the "boring" games that aren't NP-hard? If there aren't any such games, then this story is pretty trivial.
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 brain is receiving inputs from every possible sensory organ and responding to it - modifying it's actual structure because of it, and also responding to factors in its internal environment - chemical and electrical concentration gradients.
This is why even identical twins raised in identical environments will respond differently to the same stimulus - if only because on is sitting on the left and the other one on the right. Physics cannot explain why I, at this instant, choose to think about a magenta capybara and why you, having never heard of this creature I just made up, actually imagined one when you read it.
We are more than the sum of our parts.
Seven puppies were harmed during the making of this post.
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, 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.
I already wrote a solver for this exact game. It just isn’t efficient.
Alexander Peter Kristopeit bought his basement from his mommy for one dollar.
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, choose to think about a magenta capybara and why you, having never heard of this creature I just made up, actually imagined one when you read it.
Sure it can. Chaos theory. Sensitive dependence on initial conditions. Physics can't predict exactly where the next tornado will touch down either. That doesn't mean weather is independent of the laws of physics.
We are more than the sum of our parts.
I agree. We are the product of our parts.
Give me Classic Slashdot or give me death!
Proving that P = NP is easy... you just have to start with contradictory premises.
Alexander Peter Kristopeit bought his basement from his mommy for one dollar.
We just come with better software for it.
We also come with better hardware for it. For now...
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
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.
P=N*P
N=1
P! = N * P
(P-1)! = N
(P-1)! = 1
P = 1
Now where in my Nobel Peace Prize.
Knowledge = Power
P= W/t
t=Money
Money = Work/Knowledge so the less you know the more you make
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 for neurons, for which the normal level of operation is a lot smaller; a sufficiently accurate model would need to account for a lot of movement at the molecular level...
Either way, I think that in the absence of more data, the kind of strong determinism you're proposing is really just an article of faith.
More to the point, you aren't responding to my claim that brains can generate minds, something computers have never been shown capable of doing. I think that the ability to create a mind, and the ability to create concepts with "aboutness" through conceptual metaphor, both present in brains but not computers, are two fundamental hurdles to be overcome before we can really say that a brain is reducible to an algorithm/computer.
Freedom isn't free; its price is the well-being of others.
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.