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

Oblig XKCD

[Zocalo]

I'd say that this is most definitely NP, for humans and AI alike.

Re:Oblig XKCD

[bondsbw]

You can play it here. I'd say it's undecidable.

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'.

Re:Oblig XKCD

[Crudely_Indecent]

I tied the top score!

0 (zero)

Re:Oblig XKCD

[Anonymous Coward]

I doubled your score, Loser!

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

[HarrySquatter]

I would argue that Mindsweeper has a far larger audience. And, yes, there are competitive mindsweeper players and leagues.

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

[quantumplacet]

exactly, because every single windows user plays minesweeper, but not tetris which is unfortunately only available for ps2.

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

[Lando]

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.

Sokoban

[am 2k]

FYI, Sokoban is NP-hard as well (according to wikipedia). I'm seeing a pattern here...

Re:Sokoban

[kvezach]

The minesweeper decision problem is actually: "Given these mine hints, is there any possible way mines could be set on the field so that you would get these hints when uncovering these squares?". It's a reduction from SAT. It's NP because given an answer, you can check if the mine hints would be what the problem states. It's NP-hard because SAT is. Together, NP and NP-hard makes NP-complete.

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.

Just to throw this out there

[NitsujTPU]

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

[Anonymous Coward]

I have no idea what you just said. Can you use a car analogy?

Re:Just to throw this out there

[SomeJoel]

If you drive from Los Angeles to New York without using cruise control, it's hard to figure out exactly how many inches you'll drive (accounting for curves in roads on whichever route you choose), but there are ways, such as maps, to get pretty close approximations.

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

Fun == uncertainty

[arielCo]

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.

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

[Bob Hearn]

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.

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

[Bob Hearn]

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

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.

I solved it

[jimbolauski]

P=N*P
N=1

P! = N * P
(P-1)! = N
(P-1)! = 1
P = 1

Now where in my Nobel Peace Prize.

hands up...

[drsquare]

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.