Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

All the Best Games May Be NP-Hard

kdawson posted more than 4 years ago | from the easy-for-you-to-say dept.

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

cancel ×

322 comments

Sorry! There are no comments related to the filter you selected.

Oblig XKCD (3, Funny)

Zocalo (252965) | more than 4 years ago | (#31790828)

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

Re:Oblig XKCD (2, Insightful)

Kingrames (858416) | more than 4 years ago | (#31790924)

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

Re:Oblig XKCD (5, Informative)

bondsbw (888959) | more than 4 years ago | (#31790940)

You can play it here [swfme.com] . I'd say it's undecidable.

Re:Oblig XKCD (2, Interesting)

Zocalo (252965) | more than 4 years ago | (#31791108)

Cool. I have a strategy that might work, but it involves getting the first piece dead centre in the bottom such that it creates a level "base", then building a platform up from that on which you can actually complete rows, albeit on a reduced height playing field. The pre-requistite is that the first piece is suitable for creating the platform which, depending on whether the screen width is an odd or even number of boxes across, is a different subset of the available pieces. If you get a "Z" or "S" piece to start though, I think it's pretty much game over, no matter what you do.

Re:Oblig XKCD (3, Insightful)

NoSleepDemon (1521253) | more than 4 years ago | (#31791218)

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 (3, Funny)

Crudely_Indecent (739699) | more than 4 years ago | (#31791390)

I tied the top score!

0 (zero)

Re:Oblig XKCD (4, Funny)

Anonymous Coward | more than 4 years ago | (#31791484)

I doubled your score, Loser!

Re:Oblig XKCD (2, Informative)

PIBM (588930) | more than 4 years ago | (#31791510)

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:Oblig XKCD (1)

Idiomatick (976696) | more than 4 years ago | (#31791436)

The game doesnt have code the remove lines though.

Re:Oblig XKCD (0, Redundant)

Lord Bitman (95493) | more than 4 years ago | (#31791408)

that is not tetris.

The fun is in the simplicity (5, Insightful)

Pojut (1027544) | more than 4 years ago | (#31790838)

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 (4, Interesting)

HarrySquatter (1698416) | more than 4 years ago | (#31790912)

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 (1)

Pojut (1027544) | more than 4 years ago | (#31791106)

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:The fun is in the simplicity (1, Informative)

theaveng (1243528) | more than 4 years ago | (#31791204)

>>>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 (4, Funny)

quantumplacet (1195335) | more than 4 years ago | (#31791326)

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 (1)

theaveng (1243528) | more than 4 years ago | (#31791740)

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

coolsnowmen (695297) | more than 4 years ago | (#31791338)

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

Pojut (1027544) | more than 4 years ago | (#31791424)

Come on...not everyone that uses Windows regularly plays Minesweeper.

Re:The fun is in the simplicity (1)

poetmatt (793785) | more than 4 years ago | (#31791588)

even higher yet. the thing is on every OS that exists, basically.

Re:The fun is in the simplicity (0)

Anonymous Coward | more than 4 years ago | (#31791708)

If your going to pull the ole "Windows is bigger and better" hat out you should REALLY think about it. MOST people who use windows for something besides gaming run to solitare for "game fun".

Re:The fun is in the simplicity (0)

Anonymous Coward | more than 4 years ago | (#31791200)

What's Mindsweeper?

Re:The fun is in the simplicity (-1, Troll)

Anonymous Coward | more than 4 years ago | (#31791274)

Are you ignorant?

Re:The fun is in the simplicity (1, Offtopic)

somersault (912633) | more than 4 years ago | (#31791554)

No, but you are inobservant. It's called Minesweeper.

Re:The fun is in the simplicity (0, Troll)

dskzero (960168) | more than 4 years ago | (#31791568)

And I wonder how you were modded as a troll and he wasn't. Wait, Linux doesn't installs minesweeper, i guess?

Re:The fun is in the simplicity (1)

jellomizer (103300) | more than 4 years ago | (#31791742)

Is that what the army recruiter told you?

Re:The fun is in the simplicity (1)

Azarael (896715) | more than 4 years ago | (#31790938)

I'd like to point out though, that just because a game has simple rules, doesn't mean it isn't very complicated to play. Look at how long it too for someone to completely 'solve' the game of checkers (using a computer).

Re:The fun is in the simplicity (1)

Pojut (1027544) | more than 4 years ago | (#31791042)

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

Azarael (896715) | more than 4 years ago | (#31791158)

Yes, that was the point that I was attempting to make.

Re:The fun is in the simplicity (1)

theaveng (1243528) | more than 4 years ago | (#31791160)

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 addictive gameplay.

Re:The fun is in the simplicity (1)

coolsnowmen (695297) | more than 4 years ago | (#31791358)

Have you played pac man C.E.? best pacman ever.

Tetris lasts five minutes now (1)

tepples (727027) | more than 4 years ago | (#31791416)

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

Abcd1234 (188840) | more than 4 years ago | (#31791208)

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 (4, Insightful)

eldavojohn (898314) | more than 4 years ago | (#31791078)

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

Pojut (1027544) | more than 4 years ago | (#31791146)

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? (1)

tepples (727027) | more than 4 years ago | (#31791478)

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 (1)

mqduck (232646) | more than 4 years ago | (#31791662)

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.

Metaquestion (-1, Offtopic)

camperdave (969942) | more than 4 years ago | (#31790862)

games science complexity story
it askslashdot wiki iso9001 goodluckwiththat story
crime atm bank malware money story
science space planets pluto leavepoorplutoalone story
crime privacy yro identitytheft money story

Why is every story tagged story?

Re:Metaquestion (1)

GenP (686381) | more than 4 years ago | (#31790880)

Well, they are stories.

Re:Metaquestion (1)

HarrySquatter (1698416) | more than 4 years ago | (#31790892)

Because it is tagged so automatically.

Re:MetaMetaquestion (-1, Offtopic)

Anonymous Coward | more than 4 years ago | (#31791036)

Why do tacos taste like tacos?

Re:MetaMetaquestion (1)

HarrySquatter (1698416) | more than 4 years ago | (#31791070)

Because they are made from recycled tacos?

Re:Metaquestion (1)

ZERO1ZERO (948669) | more than 4 years ago | (#31791222)

Why is every story tagged story? The answer is in your question...

Re:Metaquestion (1)

somersault (912633) | more than 4 years ago | (#31791688)

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.

Sokoban (4, Interesting)

am 2k (217885) | more than 4 years ago | (#31790914)

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

Re:Sokoban (1)

amplt1337 (707922) | more than 4 years ago | (#31791530)

I'm seeing a pattern here...

..."People like puzzles"?

Re:Sokoban (2, Funny)

owlstead (636356) | more than 4 years ago | (#31791730)

"I'm seeing a pattern here..."

Are you sure? Maybe determining if the pattern is correct is also NP-hard.

For people without mobile platforms (0)

Anonymous Coward | more than 4 years ago | (#31790918)

An essentially identical game, Drench, is available as a Flash game at Flash by Night [flashbynight.com] .

Re:For people without mobile platforms (1)

sexconker (1179573) | more than 4 years ago | (#31791242)

I think you mean "for people who want to play the game without paying for a ripoff some schlub threw up and tried to make money off of".

Just to throw this out there (5, Informative)

NitsujTPU (19263) | more than 4 years ago | (#31790934)

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 (4, Funny)

Anonymous Coward | more than 4 years ago | (#31791022)

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

Re:Just to throw this out there (1, Interesting)

NitsujTPU (19263) | more than 4 years ago | (#31791050)

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:Just to throw this out there (2, Informative)

tepples (727027) | more than 4 years ago | (#31791564)

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.

Re:Just to throw this out there (1, Informative)

Anonymous Coward | more than 4 years ago | (#31791100)

Well to be pedantic, you aren't quite right either. NP-Hard means there is no KNOWN (deterministic) polynomial-time algorithm. If P==NP, then there will be some polynomial-time algorithm.

Re:Just to throw this out there (0)

Anonymous Coward | more than 4 years ago | (#31791202)

I got there 2 minutes before you did.

Re:Just to throw this out there (2, Interesting)

Bob Hearn (61879) | more than 4 years ago | (#31791376)

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.

Re:Just to throw this out there (2, Interesting)

bondsbw (888959) | more than 4 years ago | (#31791320)

Even more, you have to know what problem you're trying to solve. There are two obvious possibilities:

  • What is the smallest number of moves I can make to complete a 14x14 puzzle?
  • Can I complete a given 14x14 puzzle in 25 moves?

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 with at least 5 colors can be solved in 1 move. That's an obvious no (a contradiction), so that question is also not NP-Hard. (I don't know if every puzzle can be solved in 25 moves... perhaps so, but maybe not.)

Re:Just to throw this out there (2, Interesting)

yariv (1107831) | more than 4 years ago | (#31791538)

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 nor NP-Hard (on classical models, not quantum).

In general, the idea that we are attracted to NP-Hard problem seems quite unlikely to me. 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...

Re:Just to throw this out there (0)

Anonymous Coward | more than 4 years ago | (#31791726)

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.

Wow. You proved your point rather nicely. NP-Hard means that if you solve it in (deterministic) polynomial time, then all NP problems can be solved in (deterministic) polynomial time. It doesn't mean that they are not in P (though, granted, it seems unlikely). A subset of NP-Hard is NP-Complete: the NP-Hard problems that are also NP. Wikipedia [wikipedia.org] has pretty drawings about it.

"human creativity"? (4, Insightful)

martas (1439879) | more than 4 years ago | (#31790964)

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"? (2, Insightful)

HarrySquatter (1698416) | more than 4 years ago | (#31791048)

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

Why?! (1)

RyuuzakiTetsuya (195424) | more than 4 years ago | (#31790986)

Probably because like any other good problem, they both offer a problem and they help start the solving process.

-1 obvious (1)

waddgodd (34934) | more than 4 years ago | (#31791028)

the conclusion drawn is pretty much one that you're taught in basic-level game theory. If its easy to solve, nobody wants to play it

Re:-1 obvious (1)

sexconker (1179573) | more than 4 years ago | (#31791152)

the conclusion drawn is pretty much one that you're taught in basic-level game theory. If its easy to solve, nobody wants to play it

I would love to go to a game theory class and just troll the professor every fucking day with "What about Farmville?".

chess and go aren't np-hard, but they are also fun (2, Insightful)

darkeye (199616) | more than 4 years ago | (#31791040)

so where is the pattern?

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

NitsujTPU (19263) | more than 4 years ago | (#31791272)

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 (0)

Anonymous Coward | more than 4 years ago | (#31791288)

I think you're underestimating the difficulty of these games. They are definitely np-hard (actually a bit harder even)

http://www.ics.uci.edu/~eppstein/cgt/hard.html

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

Bob Hearn (61879) | more than 4 years ago | (#31791308)

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:chess and go aren't np-hard, but they are also (1)

TheKidWho (705796) | more than 4 years ago | (#31791684)

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 (4, Interesting)

Bob Hearn (61879) | more than 4 years ago | (#31791768)

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]

Search Space (0)

Anonymous Coward | more than 4 years ago | (#31791064)

Sufficiently large search space makes it possible to invent a heuristics suitable for the personality of the player. This way the game becomes a way of self expression and continual reinvention.

Humans are *not* good at such games--see Sudoku (2, Insightful)

mutualrecursion (1625757) | more than 4 years ago | (#31791086)

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.

No. (1, Interesting)

Hatta (162192) | more than 4 years ago | (#31791090)

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:No. (2)

Dunbal (464142) | more than 4 years ago | (#31791298)

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.

Re:No. (2, Insightful)

Hatta (162192) | more than 4 years ago | (#31791362)

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.

Re:No. (1)

mrnobo1024 (464702) | more than 4 years ago | (#31791522)

The laws of physics are mathematical, so fundamentally the human mind is an algorithm.

That does not follow. There are plenty of things one can describe mathematically but which are nevertheless uncomputable. The obvious example: A function defined as f(p,i) = { 1 if p halts on input i, 0 if not }, where p ranges over programs in some Turing-complete language.

Re:No. (2, Interesting)

MobyDisk (75490) | more than 4 years ago | (#31791544)

We just come with better software for it.

We also come with better hardware for it. For now...

Re:No. (1)

amplt1337 (707922) | more than 4 years ago | (#31791658)

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?

Fun == uncertainty (4, Interesting)

arielCo (995647) | more than 4 years ago | (#31791148)

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 (1)

tepples (727027) | more than 4 years ago | (#31791690)

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

WoW (1)

Aragorn DeLunar (311860) | more than 4 years ago | (#31791174)

What does this say about WoW, if it can be played quite successfully by a bot?

Re:WoW (1)

Myria (562655) | more than 4 years ago | (#31791422)

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 Minesweeper avoid nasty cases by randomness: the nasty cases are simply unlikely.

P=NP? (0)

Anonymous Coward | more than 4 years ago | (#31791176)

Plug equals Not Play?

Tetris is hard to solve? (1)

bluefoxlucid (723572) | more than 4 years ago | (#31791210)

What? 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. It's possible to roughly categorize the blocks and sort them efficiently as they come, perpetually lining up for a full Tetris every time a line comes down. Every piece that shows up has a computationally obvious columnar location under this strategy, but orientation is still obvious but less naively computable; it's pretty boring to play that way though.

Re:Tetris is hard to solve? (1)

tepples (727027) | more than 4 years ago | (#31791756)

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. (1)

tjstork (137384) | more than 4 years ago | (#31791226)

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:I'll just have to prove P=NP then. (2, Funny)

clone53421 (1310749) | more than 4 years ago | (#31791476)

Proving that P = NP is easy... you just have to start with contradictory premises.

Book on the Complexity of Games and Puzzles (2, Informative)

jefu (53450) | more than 4 years ago | (#31791256)

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.

Proven to be hard??? (-1, Offtopic)

thijsh (910751) | more than 4 years ago | (#31791278)

My P is proven to be hard for a girl with NP.

Are there examples of games that AREN'T NP-hard? (2, Insightful)

Dr. Spork (142693) | more than 4 years ago | (#31791294)

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.

P = NP, eh? (2, Funny)

clone53421 (1310749) | more than 4 years ago | (#31791346)

I already wrote a solver for this exact game. It just isn’t efficient.

Re:P = NP, eh? (1)

thijsh (910751) | more than 4 years ago | (#31791584)

If you want efficiency you should just have made N = 1. :-)

Tetris and Minesweeper fun? (1)

wisnoskij (1206448) | more than 4 years ago | (#31791350)

I do not know about anyone else, but I never really got how anyone considered these games fun.

However-- (1)

bill_kress (99356) | more than 4 years ago | (#31791396)

I think discussing your new iPhone game on slashdot is an NP-Easy way to get a substantial popularity boost.

Tetris need creativity? (1)

Cheburator-2 (260358) | more than 4 years ago | (#31791454)

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.

I don't get why... (1)

rm999 (775449) | more than 4 years ago | (#31791456)

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 "what is N?" You'd be amazed how many people can't answer that question.

Also, calling games like these NP-hard misses the more important point of how good heuristic algorithms are, which is the way most humans and current AIs attempt to solve them. A game is not more fun because is it NP-hard, it is often more fun because finding, learning, and applying the heuristics on the game is fun.

Re:I don't get why... (1)

Bob Hearn (61879) | more than 4 years ago | (#31791714)

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.

Great, another color-blind insensitive game (0)

Anonymous Coward | more than 4 years ago | (#31791460)

At least why can't game designers stay away from the "problem" colors like reds/greens, blues/purples etc.??

Floodit record (1)

Notquitecajun (1073646) | more than 4 years ago | (#31791486)

Math, math, blah, blah. Post your record people.

24 turns, but I'm a beginner.

"Easy to Learn, Hard to Master” (1)

imnotanumber (1712006) | more than 4 years ago | (#31791592)

It is another way of saying “Easy to Learn, Hard to Master” .

If a game with simple rules poses a problem that is complicated enough so that you can't find a trivial solution, that is half way to have a fun game.
There are other aspects like some randomness, enough to create variety but not to make it a luck game, etc...
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?