News Article

Mathematics Proves That Mario Games Are Difficult

Posted by Thomas Whitehead

Mario + Retro = Hard

Many gamers, including those of us who consider ourselves to be accomplished gaming ninjas, find older Mario titles such as Super Mario Bros. 3 and Super Mario World difficult to finish. Thanks to scientific research, we no longer need to feel shame when the dreaded 'Game Over' screen appears.

According to an analysis of the 'computational complexity' of video games, the main series of Mario platformers from the NES and Super NES era can be statistically classified as 'NP-hard'. As far as we can understand it, the challenge and structure of levels in titles such as Super Mario Bros. 3 and Super Mario World can be mathematically broken down in terms of probabilities, and they fit the NP-hard classification: the study involved creating amended versions of existing levels to prove the theory. Similar proofs have apparently been made for the Donkey Kong Country, The Legend of Zelda and Pokemon games from the 8-16 bit era.

The study also claims to have proven that mathematical problems can actually be recreated in a Mario level, and if the gamer beats a customised level they've actually completed a calculation, albeit through gaming skill rather than academic theory. This means that these Mario titles can also be classified as NP-complete, which is good to know.

We may not understand the details, but what we do know is that retro Nintendo titles have been the source of a thorough scholarly paper. If anyone criticises you for playing too much Nintendo, just tell them you're completing complex mathematical equations.

[via newscientist.com]

More Stories

User Comments (46)

SLiM

#2

SLiM said:

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

metafaniel

#3

metafaniel said:

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

ShadJV

#4

ShadJV said:

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

ThomasBW84Admin

#5

ThomasBW84 said:

@ShadJV Imagine how I felt trying to explain ;)

Even though I don't fully understand the source article word for word, the idea of a scholarly paper looking at Nintendo games in this way made me smile.

theblackdragonAdmin

#7

theblackdragon said:

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

ohhaime

#8

ohhaime said:

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

she_gamer

#10

she_gamer said:

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

StuffyStuff

#13

StuffyStuff said:

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.

TrueWiiMaster

#16

TrueWiiMaster said:

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

warioswoods

#17

warioswoods said:

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.

supermariolinux

#18

supermariolinux said:

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

warioswoods

#19

warioswoods said:

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

supermariolinux

#20

supermariolinux said:

@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

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

CorbsAdmin

#21

Corbs said:

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

Terrible_Majesty

#22

Terrible_Majesty said:

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

Capt_N

#23

Capt_N said:

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.

Blizzaga

#24

Blizzaga said:

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

benjamines

#25

benjamines said:

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

warioswoods

#26

warioswoods said:

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

ShadJV

#27

ShadJV said:

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

theblackdragonAdmin

#28

theblackdragon said:

@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

Neonpowerstar

#29

Neonpowerstar said:

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

grimbldoo

#30

grimbldoo said:

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?

Stuffgamer1

#31

Stuffgamer1 said:

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

skywake

#32

skywake said:

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.

StarDust4Ever

#36

StarDust4Ever said:

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! :D

not-just-yeti

#37

not-just-yeti said:

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

Mike1

#38

Mike1 said:

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

Dreadjaws

#39

Dreadjaws said:

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

BulbasaurusRex

#41

BulbasaurusRex said:

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.

Sh00kst3r

#43

Sh00kst3r said:

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

blikmansch

#44

blikmansch said:

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.

CzartD

#45

CzartD said:

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

Pichuka97

#46

Pichuka97 said:

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.

Leave A Comment

Hold on there, you need to login to post a comment...