Mathematics Proves That Mario Games Are Difficult

Lol that's too funny. My hubby wouldn't believe me if I used that line lol

No wonder I get a headache after playing games for so long. All that number crunching I'm doing!

I wish I could play videogames all day at work just to complete the work I'm supposed to do. Imagine, for example, programming complex code just videogaming! I'll "work" all day haha even home =P

I just took a look at the source and... my brain hurts. I sort of want to check the original paper, but it's 21 pages and if I hardly understood this article summing it up, no way will I understand that. Already I'm dreading grad school enough.

Still, I am a little shocked Pokemon is ranked as "hard"; they're long, but I didn't think they could compete with a lot of the 8-bit classics. I'm sure if they released all these games as the logical Boolean puzzles mentioned, they would hardly be as enjoyable, haha

MATHMATICAL

dude i feel like some kind of freakin' wizard now considering i can blaze through SMB3 and SMW without breaking a sweat. thanks, Tom, haha :3

"I don't know what you're talking about, may I still stand here?" - Brian Regan.

Well, waddya know. I'm good at something.

@theblackdragon, a fellow genius at SMW I see, although I can't say the same for SMB3. I do feel special now regarding my DKC skills.

... Until I remember how many hours (days, weeks, etc) and lives it took to get those skills.

Hunh???

I don't find SMB3 or SMW to be very difficult at all, especially SMW with it's infinite supply of lives and the cape and Yoshi help out a lot. SMB on the other hand gives me trouble a lot of the time.

Uh, whats the "NP" stand for? Nintendo Power is the only thing that comes to mind...

Not Possible? Nuclear Power? Not Playable? Noodles Pending? hahaha

If those are NP-hard, what does that make the original Super Mario Bros. The Lost Levels? NP-really hard?

I'm tempted to say that the final (golden flagpole) bonus level of Super Mario 3D Land may be the hardest single level in any Mario game to date. And yes, I've played through SMB2 (Japan) but still didn't die that many times in a row.

@warioswoods

you mean S8-Bowser Castle?

yea, that one was pretty hard, still find SMB3 and Lost Levels to be The Most Difficult, i have beaten SMW Twice and SMB3 only once, only beat Lost Levels once in all stars since you can get as many game overs without having to restart the entire game.

@supermariolinux

(potential spoilers)

Not Bowser's Castle, but the super-secret bonus level that unlocks after you obtain all gold flagpoles and finish all levels with both brothers. It's at the beginning of S8 once it opens, and looks like a giant flagpole on the level select.

@warioswoods oh cool, i have gold flag and both brothers on l=almost everything, just a few things left....

by the way how do you get a gold flag exactly? completing it all in one shot?

but i will definitively wanna try that level

h wait never mind you have to get to top of flag, right?

If Super Mario Bros. 3 and Super Mario World are NP-Hard, then Super Mario Bros. 2 Famicom is MF-Hard.

Does that mean the Ninja Gaiden (NES) and Mega Man (NES) series are MENSA hard? I beat all of them except NG3.

I've beaten both SMB3/SMW games so many times, I'm a genius then. Then again, there are other game series I am terrible at.

The first Super Mario Bros. is way harder than the third installment. And the Lost Levels even more so.

Lost Levels is harder than SMB3 and SMW, but Super Mario Sunshine is harder than both combined, if you ask me. That stupid lily pad level...

@supermariolinux

Yeah you need the top of the flag on every level. Usually you can get that easily with a roll-jump combination, or a Tanooki if you want to remove the challenge.
; )

@ThomasBW84 Oh yes, you'd be surprised how often games (including Nintendo games) are used in scholarly papers. It is cool; assuming I have to do this sort of thing in grad school, I hope to be able to participate in this kind of study, as long as it doesn't kill my ability to enjoy games.

@she_gamer: oh lord yes — I don't want to know how many lives I burned through growing up either, but all that practice paid off, apparently :3

@ouroborous NP stands for Non-deterministic Polynomial time (or something along those lines).
I hope I don't sound like I'm just bragging about this, but I read the source article, and I understood every single word of it. I didn't have time to read the original paper, although I got the general idea of what they were doing.
Also, the source is somewhat misleading. The problem that they classified as "hard" was determining whether a level is possible to complete, not completing the level itself, despite the fact that the title and first sentence (from the source article) seems to suggest otherwise.

I wonder if modern "hardcore" gamer could even get past level one of Super Mario? or get 100 points on an original Game and Watch?

@NeonSh3llz: I was starting to think (as I read through the comments) that nobody got it but me...thanks!

I agree completely; the article clearly stated that it's difficult to logically prove whether or not a level can be completed. But that actually has nothing whatsoever to do with how hard it is to complete the level while playing the game. Video games are weird that way.

Also...I have those Super Mario World skills for certain, but much less so with Mario Bros. 3, just like she_gamer. I blame that fact on Super Mario World being far and away the superior game, thus demanding more of my play time.

As some have said this is not the same as the hard people are thinking. In a nutshell it's possible to quickly verify whether a level is possible to be finished if someone has finished it regardless of how complicated. At the same time it could potentially take billions of years for a computer to prove either way whether it's possible to finish.

The million dollar prize is about something a bit different. That's about whether it is possible to solve these hard problems in the same time it takes to verify them.

@grimbldoo Since thay say that mario is a "kiddy" character, yeah, lets see them beat the first world! XD

I guess it's kinda like this:

http://www.youtube.com/watch?v=J2shAMA0dfM

You just have to know all the variables and odds etc.

It's funny how Marios jumps are parabolic in nature, and the algorithms necessary for Mario's precision can be expressed as a series of simple 8-bit signed integers (from -128 to +127). So next time you decide to rescue the princess, you can get your jump on and your 8-bit math as well!

Just to be clear: they're not saying SMB is hard; they are saying that a level can potentially be hard to figure out (even if you have ultra-perfect reflexes). More concretely, they can take a difficult computational problem like:

• "Given a list of shift preferences and constraints, schedule everybody so that all shifts are covered (or determine it's not possible)", or:
• "Here is a big circuit diagram; is there some combo of inputs that can make it output 111001011" (wikipedia: "satisfiability"), or
• wikipedia: "Traveling_salesperson_problem"

And they can turn any such question into a (complicated but not exponentially-long) SMB level, where you need to jump on some switches in a certain order to win, and the order of the switches actually translates back into a schedule/circuit-input/city-order that solves the original problem.

So they're saying "we've proven that the puzzle elements of a SMB level are rich enough to encode any instance of these known-difficult problems".

The first SMB is very difficult, followed by SMW. I always thought SMB2 and SMB3 were pretty easy.

Well, there's a reason they coined the phrase "Nintendo Hard". But then again, having grown up with those games I don't think they were particularly difficult to figure out. What I think is that games today are far too easy in comparison.

Now, I haven't played SMB3 in a while, but I remember it being easier than SMB, despite having many more choices and bigger worlds and levels. And the hardest one in the franchise has to be the japanese SMB2, the one known here as "The Lost Levels".

mario world isnt hard. Super mario 2 is hard

How do you guys figure SMB is harder than SMB3? I can get through the first 3 worlds in SMB without too much trouble, but I've yet to get anywhere close to beating the 2nd world in SMB3.

What does this mean if I make really hard Super Mario World levels?

Yes. I do not understand any of it, but my brain is enjoying the math oh so much.

It's in interesting article, but I think it is possible to give an explanation that should be a bit more clear for people who are not into computation complexity.

The question that is studied, is whether it is possible to finish a given level for one of these games. For the levels in the original games this question is not very interesting, because the games would not be very fun to play if you weren't able to finish them. But given any level, the question whether it is possible to finish such a level can be a very complicated.

Now the problem of finding the solution to such a question is NP-complete if you are able to show two things: 1) that it is NP-hard and 2) that it is in NP.

A problem is in NP if somebody who claims that the answer to a problem is "yes" can backup his claim with a proof that can be checked efficiently. In the case of Super Mario, it is quite easy that it is in NP: somebody who claims that a level can be finished, can just play the level until the end, while you sit next to him on the couch making sure he doesn't cheat.

A problem is NP-hard if you can show that your problem is at least as difficult as a problem that is known to be NP-hard. This is quite a challenge to show and it is what makes the mathematical proof so long. They basically take a well known puzzle from mathematics and show that the "pieces" of this puzzle can be translated to pieces of a level, in such a way that the complete level can only be finished if and only if there was a solution to the original puzzle. This shows that the problem is NP-hard, which wraps up the proof that deciding whether you can finish any level in one of these games is NP-complete.

Still stuck in one of those last levels in SMB3. >.< Personally, I think that SMW is easy.

Mario 3 and Mario World are super easy to me. I feel really good now. I mean I grew up playing these games. Some levels are hard like the specail world in Mario World but all in all, those two are pretty easy games to me.