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?"

Comments

The fun is in the simplicity

[Pojut]

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

[eldavojohn]

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 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:The fun is in the simplicity

[mdarksbane]

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:The fun is in the simplicity

[paeanblack]

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:Oblig XKCD

[Kingrames]

I don't think so. I believe that's O(0).

"human creativity"?

[martas]

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?

Re:"human creativity"?

[HarrySquatter]

Nothing really. It's just further proof that kdawson is even more incompetent than Jon Katz.

chess and go aren't np-hard, but they are also fun

[darkeye]

so where is the pattern?

Humans are *not* good at such games--see Sudoku

[mutualrecursion]

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.

Re:Oblig XKCD

[NoSleepDemon]

Already tried that, the game is made infinitely more difficult by the physics engine which treats each block as if they have minimal mass in an almost weightless environment, furthermore, the pieces continue to move after they are 'placed'.

Are there examples of games that AREN'T NP-hard?

[Dr. Spork]

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.

Re:No.

[Hatta]

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.

nonsense

[pydev]

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.

Re:Just to throw this out there

[tobiah]

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.