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!

Classic Nintendo Games Are NP-Hard

Soulskill posted more than 2 years ago | from the travelling-plumber-problem dept.

NES (Games) 204

mikejuk writes "You may have have thought games like Super Mario Bros., Donkey Kong, and so on were hard at the time you were playing them, but you probably didn't guess they were NP-hard. Now we have some results from computer scientists at Universite Libre de Bruxelles and MIT Computer Science and Artificial Intelligence Laboratory that many classic games contain within them an NP-hard problem. It has been proven that the following game franchises are NP-hard (PDF): Mario, Donkey Kong, Legend of Zelda, Metroid and Pokemon. At least you now have an excuse for your low scores."

cancel ×

204 comments

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

Not just nintendo games (3, Interesting)

Janek Kozicki (722688) | more than 2 years ago | (#39301795)

My favorite NP-hard game is adom. Just try it - see my sig.

Re:Not just nintendo games (4, Interesting)

K. S. Kyosuke (729550) | more than 2 years ago | (#39302061)

Adom may or may not be NP-hard, but first and foremost, it's insanely complex for anyone but a basement gaming zombie. I adore the whole concept, but I don't have the time for playing something like that. The endless stream of "What? The game takes XYZ into account, in addition to all the food, curse, day of the year etc. stuff?" kind of wore me down rather quickly. Now if you excuse me, I'd like to finish eating my uncursed large bat. (Mmm, tastes like chicken.)

Re:Not just nintendo games (2)

Janek Kozicki (722688) | more than 2 years ago | (#39302115)

I'm not a basement gaming zombie ;) I'm a scientist.

I'm careful to avoid playing adom more often than once per 2 or 4 years. Otherwise a month is lost.

Kid Icarus (3, Funny)

donotlizard (1260586) | more than 2 years ago | (#39301803)

Kid Icarus for Nintendo is the most difficult game in the history of mankind.

Re:Kid Icarus (5, Funny)

kerohazel (913211) | more than 2 years ago | (#39301843)

Harder than Battletoads? I think not.

Re:Kid Icarus (3, Insightful)

lambent (234167) | more than 2 years ago | (#39301923)

There's a pretty big difference between "hard" and "fundamentally broken".

Battletoads was hard because it was designed poorly.

Re:Kid Icarus (5, Funny)

Anonymous Coward | more than 2 years ago | (#39302043)

There's a pretty big difference between "hard" and "fundamentally broken".

Battletoads was hard because it was designed poorly.

Sounds like SOMEONE'S still bitter they couldn't even beat the Turbo Tunnel.

Re:Kid Icarus (1)

pecosdave (536896) | more than 2 years ago | (#39301965)

I never could get past that lava jet ski level!

I could whoop up all the way there and I kept getting just a little bit further, but then, nothin.
I'll bet the final baoss wasn't that hard!

Re:Kid Icarus (3, Informative)

gauauu (649169) | more than 2 years ago | (#39302327)

I never could get past that lava jet ski level!

I could whoop up all the way there and I kept getting just a little bit further, but then, nothin.
I'll bet the final baoss wasn't that hard!

No, the final boss level (and final boss) were as tough as the rest of the game. I spent a couple months in college where I dug out my old nes and vowed to beat Battletoads (on the real thing, with no save state cheating). It was incredibly painful. It was hard all the way through. The only real hope you have is juggling the vultures on the 2nd level to gets tons of 1-ups.

Re:Kid Icarus (0)

Anonymous Coward | more than 2 years ago | (#39302145)

Not nearly as hard as beating spy hunter?

Re:Kid Icarus (1)

TheCycoONE (913189) | more than 2 years ago | (#39302909)

Did spy hunter have an ending? I don't think I ever made it past fall.

Re:Kid Icarus (2, Insightful)

Hatta (162192) | more than 2 years ago | (#39302231)

Ahem. Silver Surfer.

Re:Kid Icarus (1)

PRMan (959735) | more than 2 years ago | (#39302411)

C'mon. I solved Battletoads. It was hard, but not that hard.

Re:Kid Icarus (1)

tepples (727027) | more than 2 years ago | (#39301849)

Is Kid Icarus harder than Super Mario Frustration [youtube.com] ? (Video; swearing; mute if at work)

Re:Kid Icarus (0)

Anonymous Coward | more than 2 years ago | (#39302085)

I wish I could find a working link to the actual game mod. The megaupload link is dead.

Super Mario Forever IPS (3, Informative)

tepples (727027) | more than 2 years ago | (#39302195)

The IPS file [zophar.net] for Super Mario Forever, the map pack featured in the Super Mario Frustration video, is still available.

Re:Kid Icarus (1)

icebraining (1313345) | more than 2 years ago | (#39302641)

Syobon Action is hellish too, although mostly because the traps are hidden.

Re:Kid Icarus (0)

Anonymous Coward | more than 2 years ago | (#39302203)

How is it difficult? The gameplay is relatively simplistic. One-way scrolling either up or sideways, except in the fortresses which turn into a Zelda-ish one-room map deal. There doesn't appear to be a time limit, enemies generally always appear at the same spots, rooms are always in the same spot AND have the same contents, and you can grind early on for points and hearts/money. The former is a good thing, as you can get an extra life block at the end of a stage if you cross specific point thresholds. Also, you can buy as much as you can afford in the fortresses, so you can stock up on items once you find decent rooms to earn hearts from.

So take it slow, get a feel for how the enemies move, and pick up a feather or two just in case you slip and fall off the bottom of the screen.

If it helps, read about the mechanics of the Chamber of Pots. There is a set # of places the God of Poverty can be, and a 100% successful way of determining that (based on which level you are on) one. If you get his pot last, he instead becomes a valuable item.

Re:Kid Icarus (1)

PRMan (959735) | more than 2 years ago | (#39302359)

Not true. My friend solved it. That alone makes it easier than SunSoft's Fester's Quest (which he never solved) or Batman (which he also solved somehow once, he's the only person I knew that solved it).

Re:Kid Icarus (4, Insightful)

elrous0 (869638) | more than 2 years ago | (#39302385)

Desert Bus is WAY harder to beat.

Quote from a friend while playing NES games: (1)

oodaloop (1229816) | more than 2 years ago | (#39301827)

"Isn't it great we can usually beat an 8-bit video game?"

This was the early 2000s on an ancient Nintendo box.

Scoring is NP-hard (1, Interesting)

DigiShaman (671371) | more than 2 years ago | (#39301829)

I thought all games were NP-hard. That is, the path to optimal scoring is dynamic based on random events (true or simulated random). For example in a standard shoot-em-up, you're always thinking about the order in which kill an object and in what particular order all while avoiding being shot at.

Re:Scoring is NP-hard (2)

fuzzyfuzzyfungus (1223518) | more than 2 years ago | (#39302175)

My understanding, admittedly layman's, is that a lot(all of?) the early console systems were hardware constrained as hell and certainly didn't have the luxury of a hardware RNG or even many peripheral interfaces with the unpredictable outside world, so their games tended to not only lack randomness; but rely on techniques for faking randomness sufficiently rudimentary that "luck manipulation" [tasvideos.org] becomes viable...

Buzz (3, Insightful)

Anonymous Coward | more than 2 years ago | (#39301837)

Is "NP-hard" the next buzz word?

Re:Buzz (5, Insightful)

TheVelvetFlamebait (986083) | more than 2 years ago | (#39301991)

No, NP-Hard cannot be, nor ever become, a buzz word, because NP-Hard has a clear, well-defined meaning. Buzzwords are defined by their own lack of definition, making them perfect for marketing and generally impressing people without saying anything meaningful.

Re:Buzz (1, Insightful)

Anonymous Coward | more than 2 years ago | (#39302053)

It has a well-defined meaning for the people who understand it.

Re:Buzz (2, Insightful)

Anonymous Coward | more than 2 years ago | (#39302281)

Should NP-hard become a buzzword, it would be first spread by people who understand it badly, and then by people who have completely misunderstood the idea but think it's neat. It doesn't matter that it has a precise technical meaning, if only a few people understand that meaning. In fact many buzzwords start out being well defined in some community of experts, but whatever meaning there was to begin with is quickly diluted to another feel-good word associated with a vague cloud of ideas.

Re:Buzz (4, Insightful)

jellomizer (103300) | more than 2 years ago | (#39302337)

Buzzwords have a well defined meaning... They just abuse them. Using them in cases where they shouldn't be used.

For example
Synergy: Is when the output of a team or groups activity is greater then the sum of each member.
This happens when you are working together and you come up with a solution together that no one by themselves would come up.

The word had been misused because of its closeness to Synchronous and Energy and used more to express things working well together.

Re:Buzz (1)

icebraining (1313345) | more than 2 years ago | (#39302673)

So did REST, if you read the thesis, but it didn't help.

Re:Buzz (4, Insightful)

phantomfive (622387) | more than 2 years ago | (#39303021)

This paper is as close to marketing as science ever comes. The use of the words 'NP-Hard' and "video games" were chosen specifically because they sound impressive, not because they've shown anything useful. They came up with some way to connect those two words in a paper (by morphing Mario, and defining it in a way that never entered any cartridge. If you have a finite number of paths through Mario in an arbitrarily large map, and some choices make the game impossible to beat because you get stuck, then yes you have an NP-Hard search problem. But there is no Mario level like that, and never will be because it would be boring).

It also fulfills the other requirement of marketing, that it makes me feel dumber after reading. This super-annoying movie comes very close to showing the method used in this proof [youtube.com] . It solves a problem that no gamer would ever face, and no level designer would ever face either, unless his method was to randomly drop blocks on the screen, rearrange them into chunks of which some are impossible to pass, and then rearrange those randomly. Can you see how this has absolutely nothing to do with the game we call Super Mario Bros?

In other words, the authors saw the attention people got for using the word "NP-Hard" in relation to Tetris (look! Made it on BBC! [bbc.co.uk] ), and though "wow, maybe if we use the word NP-Hard in relation to Super Mario Bros, we can get on the BBC too!

There is absolutely nothing novel about this result, and in fact, it might be a homework problem you would give to students in an undergraduate class on computer theory. Given the right introduction, the students could easily do it. It is a blatant attention whore attempt.

Re:Buzz (5, Funny)

robthebloke (1308483) | more than 2 years ago | (#39302083)

Where have you been for the last 5 weeks? Didn't you get the tweet? The term "NP-hard" has been superseded by "NP-cloud-based-social-media-hipster". Keep up!

Re:Buzz (5, Funny)

Chris Burke (6130) | more than 2 years ago | (#39302713)

Where have you been for the last 5 weeks? Didn't you get the tweet? The term "NP-hard" has been superseded by "NP-cloud-based-social-media-hipster". Keep up!

An "NP-cloud-based-social-media-hipster" would be proof that P=NP, since you're saying this cloud-based-social-media-hipster is in NP(Non-Pretentious), when it has already been proven that all hipsters are in P.

Re:Buzz (0)

Anonymous Coward | more than 2 years ago | (#39302089)

No, that would be , Sustainable Quantum Cloud.

Re:Buzz (0)

Anonymous Coward | more than 2 years ago | (#39302569)

I desperately whish that it would become an often used word in gaming magazines. It's about fscking time that we'd get actual challanges from games again, instead of interactive cutscenes where all kind of shit happens that doesn't affect my play.

Once upon a time gaming was for nerds, now it's for everyone. Not that gaining acceptence is any problem for me, but what is a problem for me is that everything is so damn fscking easy and boring in terms of an actual challenge with rules, instead of a button pushing cinema experience. Not that cutscenes and movie stuff in Metal Gear Solid sucks (it's awesome), but some people clearly didn't get it. What they did get where the sales figures.

Therefore I still play most oldskool games, because the majority of them sucks balls and can only still theoretically be labled as being a game. /rant

Re:Buzz (0)

Anonymous Coward | more than 2 years ago | (#39302971)

I read through the PDF files of the test results, the wikipedia definition of NP-hard, and than the PDF file test results again.

I still do not understand what NP-Hard is and how it applies to games.
Maybe because it's Friday afternoon or maybe I am getting old.

Where's the simple easy stories I don't have to think about like the iPad or the US government taking away my rights and giving them to corporations? It's Friday afternoon man!

solstice (0)

Anonymous Coward | more than 2 years ago | (#39301841)

Solstice may be the most difficult game ever

Re:solstice (1)

olof_k (2093198) | more than 2 years ago | (#39301901)

Oh yes! I failed to beat it even with the cheat code that gave you unlimited lives. I think even the cheat code itself was hard to get right

Castlevania (2)

logical_failure (2405644) | more than 2 years ago | (#39301847)

Castlevania was harder than Mario, Zelda, or Metroid -- especially the Grim Reaper fight. If you didn't have triple-shot boomerangs, when the Reaper started spamming you with Scythes you were in trouble.

Battletoads was another one that was brutally hard...

I saw where someone thought the Mega-Man games were hard... but those always seemed easy to me.

Tool-assisted speedrun (2)

tepples (727027) | more than 2 years ago | (#39301873)

Battletoads was another one that was brutally hard

Is it hard to TAS, or just demanding in reaction time and memorization? Because the article is assuming tool-assisted speedrun conditions: "Indeed, the clicking of the button at the right time is factored out of these proofs of complexity - these are results that apply to a perfect player with infinite speed and reaction times of zero."

Re:Tool-assisted speedrun (0)

Anonymous Coward | more than 2 years ago | (#39302285)

The latter for what most people say are the hardest parts of the game. Notably, the Jet Bike parts and the... unicycle thing. In both, it's you versus the environment with a VERY tight timeline (the latter enforced by a Big Ball 'O Death right on your tail). So you have to have precision timing, pretty much knowing when to move up, down, jump, etc. so that you have enough time to actually make the next move. With memory and no randomness, it should be trivial for a TAS to work in those sections; I can't recall if there's any parts that have you actually fighting enemies while on the bikes.

Most likely, a TAS would also still work in the combat sections, if you always started and ended with the same exact memory state (such as with an emualtor, to make sure there's no actual randomness.)

Fantastic (4, Funny)

Anonymous Coward | more than 2 years ago | (#39301851)

Now Billy Mitchell's ego can finally get a much needed boost.

What? (2)

Anonymous Coward | more than 2 years ago | (#39301855)

I Honestly don't understand what NP refers to.

Re:What? (-1)

Anonymous Coward | more than 2 years ago | (#39301877)

NP = Nigger Pussy.

Re:What? (2)

who_stole_my_kidneys (1956012) | more than 2 years ago | (#39301895)

was about to say the same thing. The Wikipedia entry makes my head hurt, like watching 'Lost' for the first time in the middle of the 2nd season, i throw my hands up in the air and say "WTF?".

For a gentler introduction (5, Informative)

tepples (727027) | more than 2 years ago | (#39302017)

There are three classes of problems at issue here:
  • NP, problems for which you can verify a solution in polynomial time (e.g. O(x^2) or O(x^3) operations);
  • NP-hard, problems that are at least as hard as the hardest problems in NP; and
  • NP-complete, problems that are both NP and NP-hard.

For a gentler introduction, see P vs. NP [wikipedia.org] .

Re:What? (1)

Quiet_Desperation (858215) | more than 2 years ago | (#39302029)

Post above yours: "N****** pussy"

Yours: "was about to say the same thing."

Unfortunate alignment, but I had to chuckle.

To compensate: http://en.wikipedia.org/wiki/NP-hard [wikipedia.org]

Re:What? (3, Informative)

Anubis IV (1279820) | more than 2 years ago | (#39301971)

For an intro to NP and NP-hard, might I suggest Wikipedia's entry on NP-hard [wikipedia.org] ? You get to stuff like this in any classes that cover computational complexity, such as coursework covering algorithms. NP comes up every few weeks on Slashdot since it's an interesting-ish topic for most of us.

Re:What? (2, Informative)

Oxford_Comma_Lover (1679530) | more than 2 years ago | (#39302047)

"Not polynomial."

It refers to the complexity of a computing problem being significant enough that it cannot be guaranteed to be solved in polynomial time.

So doing an operation on a two digit number is easy, but as the number of digits goes up, and you try to do the same operation on the bigger numbers, it gets harder at a rate which is greater than polynomial with the size of the input.

It's a little more complex than that, but that's basically it.

Re:What? (3, Informative)

SorcererX (818515) | more than 2 years ago | (#39302493)

NP is "Nondeterministic polynomial", not "Not polynomial."

Re:What? (0)

Anonymous Coward | more than 2 years ago | (#39302533)

Please return your CS degree, if you ever had one.

Re:What? (2)

Sqr(twg) (2126054) | more than 2 years ago | (#39302631)

No, NP stands for "nondeterministic polynomial time". Informally, it means that the problem can be solved in polynomial time if you are really, really lucky.

Re:What? (1)

TuringTest (533084) | more than 2 years ago | (#39302633)

Wrong. N=Non-deterministic, like the Turing machine.

Re:What? (1)

Anonymous Coward | more than 2 years ago | (#39302237)

NP is a set of problems for which we can efficiently (in no worse than polynomial time) verify an answer.
P is a set of problems for which we can efficiently find an answer.

Right now, no one knows if those are the same set of problems. Most people think that, in fact, there are problems that are easy to verify, but hard to solve. In a particular flash of brilliance, Stephen Cook and Leonid Levin proved that there was one problem that encapsulated all the difficulty of finding solution to problems that are in NP but not necessarily in P (basically, they proved that if you can solve this problem efficiently, you can solve any other problem in NP efficiently). It turns out that there are a whole bunch of different ways of representing this problem, and all of those different representations are called NP-complete. If you can solve an NP-complete problem simply, you prove that P = NP, and if you're smart about it, it might make you rich. On the other hand, people a lot smarter than you have been trying to do that for a long time, and no one has figured it out, so that's pretty unlikely.

NP-hard is the set of problems that are at least as hard as the hardest problems in NP. It's not a particularly useful definition, because it includes both problems in NP-complete (which we can actually use), and problems that are undecidable (Alan Turing proved that there are problems for which no solution can exist--it's a pretty elegant proof). Basically, saying that something is NP-hard is the same thing as saying that trying to solve the problem is infeasible--just with a lot more math than you might otherwise say that.

pointless (4, Interesting)

khipu (2511498) | more than 2 years ago | (#39301871)

These games aren't "NP-hard" because they are fixed size and fixed levels. Complexity results show you nothing about the difficulty of individual instances.

What is "NP-hard" is some generalization of these games chosen by the authors, with a particular chosen outcome (e.g., maximum score). Whether that generalization is still a good game, or even the same game, is questionable.

Re:pointless (1)

tepples (727027) | more than 2 years ago | (#39301893)

What is "NP-hard" is some generalization of these games chosen by the authors

Isn't a generalization like this realizable using ROM hacking tools such as Mario Improvement or Lunar Magic?

Re:pointless (1)

TheVelvetFlamebait (986083) | more than 2 years ago | (#39301931)

Another possible example: the best way to collect all pickups in Metroid while minimising the encounters hazards (and the chance of getting killed).

NP-hard is overrated (1)

Anonymous Coward | more than 2 years ago | (#39301875)

Almost any interesting game will be NP-hard. Mostly only boring games will be NP-complete though.

NP is the second-most boring class of problems (and it might even be the most-boring class, if NP=P).

Look into some lecture of AI-planing, most problem solving problems are EXP(EXP())- complete, and if you want optimal solutions, it might even get harder....

Re:NP-hard is overrated (2)

slew (2918) | more than 2 years ago | (#39303045)

Almost any interesting game will be NP-hard. Mostly only boring games will be NP-complete though.

NP is the second-most boring class of problems (and it might even be the most-boring class, if NP=P).

Look into some lecture of AI-planing, most problem solving problems are EXP(EXP())- complete, and if you want optimal solutions, it might even get harder....

Even more interesting than an NP-hard game is a game that simulates real life. With NP-hard game you know there is an optimal solution and you usually get a chance to try it over and take another decision path if you fail (even if you can't verify the optimality of your decision in polynomial time). In games that simulate real life, you know that you aren't playing optimally, and you don't get to try again and make another different decision, so NP-complete may be the third-most boring class of problems. As a simple example, take the secretary problem [wikipedia.org] . Of course if you "replay" the secretary problem, you can get the optimal result (basically a P-problem with order 1), but if you can't, well isn't that more interesting?

On the other hand maybe such a game would be so interesting that it's boring (too much like real life, not escapist enough). Which leaves open the other possiblity that a game can be so boring, that it can be made interesting again. Say like a favorite drinking game, or playing inverse checkers for example.

I'm sure ... (3, Informative)

gstoddart (321705) | more than 2 years ago | (#39301899)

I'm sure I've seen this before. Ahh, yes here it is [slashdot.org] , almost two years ago.

I guess not the exact same thing, since the last story didn't explicitly mention Donkey Kong ... but certainly the NP-hard part has been discussed for a while.

Pfft, they were... (5, Insightful)

Anubis IV (1279820) | more than 2 years ago | (#39301915)

They were "Nintendo hard" long before anyone realized they were NP-hard, and that's a much more meaningful measure for difficulty of video games on a practical level.

Re:Pfft, they were... (2)

medv4380 (1604309) | more than 2 years ago | (#39302137)

I always used "Mega Man Hard"

Re:Pfft, they were... (1)

Anonymous Coward | more than 2 years ago | (#39302535)

As long as you mean the first one in the series, I agree. The second one was much easier, and the third one, with the addition of the various flavors of Rush and the new slide move, was a complete joke. Not to brag, but I completed MM3 the second day I owned it. I remember being pretty disappointed considering I spent $50 on the damn thing when it came out (about $80 in today's dollars, take that all you kids that bitch about the cost of Xbox 360 games!).

Didn't really care for the 4th one, and I discovered girls before I could ever get around to giving it another whirl, as well as try any of the subsequent ones. Perhaps I'll break out the emu and give it another shot...

Re:Pfft, they were... (3, Insightful)

GameboyRMH (1153867) | more than 2 years ago | (#39302339)

Better than "80's arcade hard" 8-(

No, you don't have an excuse (5, Interesting)

Chemisor (97276) | more than 2 years ago | (#39301929)

Whether a problem is NP-hard has nothing to do with it being hard for you. NP is hard only for computers, because they are restricted to brute force search for the solution. As a human being, you use your intuition to probabalistically arrive at a likely solution instead of using a logical process to arrive at an exact and perfect solution. People do not care much about absolute knowledge, which is the province of science; we care about practical knowledge, which is the province of engineering. For example, the infamous travelling salesman problem is NP-hard, which makes it impossible for a computer to come up with the optimal solution in a predictable amount of time. However, in real life this has minimal utility because the difference between the optimal solution and the "good enough" solution that millions of travelling salesmen come up with every day is likely not financially significant. This is true in most everyday situations: we simply don't care if the solutions we use are the best available, only that they are the best we can think of in a reasonable amount of time.

This is not to say that we don't need the absolute knowledge that science provides; in many cases it does indeed lead to the practical knowledge that improves our lives. But because most absolute knowledge has no useful applications, it does make sense to have a lot fewer scientists than engineers.

Re:No, you don't have an excuse (4, Insightful)

Whatsisname (891214) | more than 2 years ago | (#39302437)

This post isn't correct. It's just as hard for humans as computers, if you are searching for the optimal solution.

You're claiming it's easier for humans because we don't actually need the optimal solution, which changes the problem.

When you change the terms of the problem to accept a "good enough" solution, there are also computer algorithms that can find "good enough" solutions very quickly and are very useful for problem sets that are out of the realm for a human being to solve in a reasonable amount of time.

Human brains solve NP-Hard problems (5, Interesting)

cyberfringe (641163) | more than 2 years ago | (#39301963)

Assuming the analysis is correct and these games are NP-hard, then what is interesting is not that some of us failed miserably at the games but so very many people did quite well. The human brain is a special-purpose computer that excels at solving problems critical to the species' survival. This suggests to me that reformulating problems of interest into a form that the brain can process (e.g., video games) might be an excellent way to tap the computational power of the brain. Wouldn't it be interesting if the millions of brains playing games were actually solving major problems in physics, biochemistry, etc.? Call it "crowd-sourced computation".

Re:Human brains solve NP-Hard problems (1)

wstrucke (876891) | more than 2 years ago | (#39302069)

After all, that's how Eli got on the Destiny.

Re:Human brains solve NP-Hard problems (1)

Jeidon (1015797) | more than 2 years ago | (#39303095)

After all, that's how Eli got on the Destiny.

Exactly what I was thinking. Here's hoping Star Trek Online is really waiting for me to solve some... problem that... damn

Re:Human brains solve NP-Hard problems (4, Interesting)

timeOday (582209) | more than 2 years ago | (#39302133)

NP hard doesn't necessarily mean something is hard in any practical sense. It might be a tiny problem instance (like traveling salesman with 3 or 4 cities). Or more commonly, it might be very hard to definitely find an optimal answer, but easy to get a good answer (within a couple percent of optimum), which is the normal way living things get by in the world. And since the computer is solving a mathematical model of your real problem and not the real problem itself, optimizing the model to the tenth decimal point is often a complete waste of time.

Re:Human brains solve NP-Hard problems (1)

Anonymous Coward | more than 2 years ago | (#39302163)

You mean like folding proteins?
http://fold.it/portal/

Re:Human brains solve NP-Hard problems (2)

Hatta (162192) | more than 2 years ago | (#39302317)

Nonsense. Just because someone can solve a specific instance of an NP hard problem in a finite amount of time doesn't mean he's capable of solving NP hard problems in P time.

Re:Human brains solve NP-Hard problems (2)

sourcerror (1718066) | more than 2 years ago | (#39302371)

This suggests to me that reformulating problems of interest into a form that the brain can process (e.g., video games)

That's what "gamification" is. Not a new idea. It even has its own Wikipedia page.

http://en.wikipedia.org/wiki/Gamification [wikipedia.org]

Re:Human brains solve NP-Hard problems (1)

sourcerror (1718066) | more than 2 years ago | (#39302483)

Sorry, the wiki page is about the way marketing people use it.

Re:Human brains solve NP-Hard problems (2)

The Raven (30575) | more than 2 years ago | (#39302421)

Not exactly... there's a huge difference between getting a solution to a problem, and getting the best solution to a problem.

The traveling salesman problem is a classic NP Hard one. But that doesn't mean you can't get an OK answer just by looking at the possible routes and making a pretty good choice. Human brains (and computer algorithms) can get 'pretty good' answers on many NP Hard issues. That's not the same as finding the best solution. I wager no human has ever gotten the 'optimal' play through of any of the listed games.

Re:Human brains solve NP-Hard problems (1)

hbar squared (1324203) | more than 2 years ago | (#39302615)

This is actually a burgeoning field of research right now. There are several games that use human effort to solve NP-hard problems. The ones I know about are foldit [fold.it] (a protein folding simulation) and phylo [mcgill.ca] (a comparative genomics engine), but I'm sure there are more.

Infinite Mario (3, Interesting)

wisnoskij (1206448) | more than 2 years ago | (#39301975)

I think it might all come down to how you look at the problem.
many people have programmed AI to beat Mario, I believe a few years ago their was some random Mario level generator (possibly called Infinite Mario) and a contest to create AI to play it. The simple act of taking it one frame at a time, dodging and jumping, is not hard to program AI or resource intensive I think, but any problem can be made complicated. If you are saying take a static level, how do you get the absolute maximum score, now of course that is NP hard.

Re:Infinite Mario (0)

Anonymous Coward | more than 2 years ago | (#39302333)

I believe you're referring to this video: http://youtu.be/DlkMs4ZHHr8

As Mario advances, you can actually see the algorithm calculate many different paths in real time and choose the best one. Really impressive.

What? (2)

snowgirl (978879) | more than 2 years ago | (#39301985)

The proofs are based on showing that the problem of deciding if a goal point is reachable from a starting point is NP-hard. The games are also generalized in that the size of the board is increased.

But the goal points are always reachable from the starting point... otherwise it would be a really shitty computer game.

The fact that the games are not randomized every play-through, and of limited size...

Grr... "NP-Hard" doesn't mean actually hard to solve... There is a proper subset of generalized NP-Hard (NP-Complete even) problems that are not particularly difficult to solve.

While the original Super Mario Brothers may have had one level that has an actual real maze to it, and as such, the underlying principles of the game may be extrapolated to be NP-hard, the first level of Super Mario Brothers is clearly not. In fact, most of the original Super Mario Brothers doesn't have any splits or deviations from the linear path that do anything but take you to a point further along in the linear path.

What I'm saying is, it seems like they generalized at least some of the games beyond all meaningful criteria... especially when these early games were specifically constructed to ensure that they the goals remained always potentially reachable.

Subtle distinction (0)

davidbrit2 (775091) | more than 2 years ago | (#39302005)

Battletoads and Adventure Island are, on the other hand, mother-fucking-hard.

Try Battle Kid (1)

tepples (727027) | more than 2 years ago | (#39302057)

Is this Battletoads? No, it's Battle Kid [youtube.com] .

Get off my lawn (1)

Rik Sweeney (471717) | more than 2 years ago | (#39302093)

Those games aren't hard, modern games are just too easy.

Anyone played Demon's Souls? That's how hard games should be.

Re:Get off my lawn (1)

GameboyRMH (1153867) | more than 2 years ago | (#39302367)

Some modern games I've played that are bloody hard are DMC4 and Prince of Persia: Warrior Within. Dunno about Demon's Souls, haven't played it.

Re:Get off my lawn (0)

Anonymous Coward | more than 2 years ago | (#39302543)

Demon's Souls and it's successor Dark Soul's are two of the best games I've played this generation. If you consider yourself any kind of gamer you should check them out.

NP-Hard is not so daunting ... (0)

Anonymous Coward | more than 2 years ago | (#39302101)

... for non-polynomials that work out to a constant size.

Re:NP-Hard is not so daunting ... (1)

JonySuede (1908576) | more than 2 years ago | (#39303119)

constant is a polynomial of degree 0

c*x^0 + 0 * x + 0 * x^2 + .... = c

 

It's really interesting (1)

aglider (2435074) | more than 2 years ago | (#39302153)

to know how scientist use their resources, nowadays.
It'd be also very interesting in knowing how these breakthrough can help the mankind and the Science.

Probably not in NP (0)

Anonymous Coward | more than 2 years ago | (#39302177)

It seems that these problems are not in NP, either, since one would hazard that a certificate that one has achieved the fastest possible run would involve exponentially much information. Proving that one has made the correct decision at each step seems hard if one doesn't include exponentially much information about the future.

since when is.. (1)

Truekaiser (724672) | more than 2 years ago | (#39302183)

pokemon considered np hard.
that's the simplest game i have played, it's just one big rock paper scissors simulator.
the video game version's of the card game on the other hand were hard because the ai cheated, it had a pool of all possible cards from it's deck. you only had what you had chosen.

Re:since when is.. (0)

Anonymous Coward | more than 2 years ago | (#39302765)

Read the article. The game of pokemon isn't considered hard - it's the pathfinding from a start point to a finish point with trainers that will move around and battle you as you walk in front of them. Deterministically deciding whether or not it is possible to make it to the end or not is NP-Hard.

abstract (1)

pr0fessor (1940368) | more than 2 years ago | (#39302185)

I've played Mario, Donkey Kong, and legend of zelda and I enjoyed them, especially legend of zelda. The wikipeadia article on NP-Hard is so poorly written using broken circular logic I really have no clue what they were trying to express.

Hey. Pedants. (0)

Uberbah (647458) | more than 2 years ago | (#39302219)

You may have have thought games like Super Mario Bros., Donkey Kong, and so on were hard at the time you were playing them, but you probably didn't guess they were NP-hard

Go ahead and use pedantic terms as much as you want when writing summaries - but it's rather annoying when you don't take .5 seconds to define them. Linking to a pendantic explanation of your pedantic writing makes it only marginally less annoying.

Like:

Here let me tell you a story where a vulpini [wikipedia.org] went after a sciuridae [wikipedia.org] in my back yard.

vs

Here let me tell you a story where a vulpini [wikipedia.org] (fox for you plebeians) went after a sciuridae [wikipedia.org] (squirrel) in my back yard.

Low scores!?!? (1)

GameboyRMH (1153867) | more than 2 years ago | (#39302267)

Looks at my name. You think my scores are low?

NP Hard Games (1)

PerfectionLost (1004287) | more than 2 years ago | (#39302311)

Isn't an NP hard game effectively any game you can't save, reload, and try again?

Re:NP Hard Games (0)

Anonymous Coward | more than 2 years ago | (#39302579)

No.

so in simple words (0)

Anonymous Coward | more than 2 years ago | (#39302429)

in simple words
in order to win you have to make that seemingly impossible jump
or you lose, you can make all the shorter jumps in between
but in the end you'll have to make that jump
there's no way around

god, i read that godawful wikipedia article
think i lost couple of braincells reading the examples section

Game Genie!!! (0)

Anonymous Coward | more than 2 years ago | (#39302479)

And that is why they invented game genie.
So, impatient folks like myself could see what the game ending cut scene was with minimal effort in very little time.

Next step on this... (1)

grumpyman (849537) | more than 2 years ago | (#39302801)

...is to prove that it's also NP-complete, and in theory NP-hard problems can then be mapped to Mario Brothers and solved by avid gamers :)

Game Center CX (0)

Anonymous Coward | more than 2 years ago | (#39302911)

KEEP CALM and KACHO ON

Please (0)

Anonymous Coward | more than 2 years ago | (#39302921)

i'm from the NP-hard games generation, BITCHES!

Solomon's Key (0)

Anonymous Coward | more than 2 years ago | (#39302923)

That was a hard game. Probably the hardest I ever played.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>