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.

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

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.