Scientists Verify Your Mario Maker Struggles, Show Mario Levels Can Be Incredibly Difficult to Solve

I see someone's been playing Japanese Mario 2.


Most of us played Mario Bros., in one form or another, growing up, and we learned the basics of video games from the series. It’s not just other games that have built those established rules out into increasingly complex forms, though—Mario Bros. inherently has that potential within itself, as some scientists (or Mario Maker) have pointed out.

If you’ve played one of the more demanding Super Mario Maker levels floating around out there on the Internet, this may come as no surprise to you, but a group of scientists from MIT’s Computer Science and Artificial Intelligence Lab (CSAIL), the University of Ottawa, and Bard College at Simon’s Rock have written a paper explaining that Mario levels can potentially fall into a category of difficulty known as “PSPACE.” That means they can be not only extremely difficult and time-consuming for both humans and computers to solve—as is the case with the slightly simpler “NP” difficulty class—but the correct path can be difficult to verify, even with the solution already known.

So, every time you frustratingly fall into a pit or lose a life to a spiky enemy, just think of how much smarter you’re getting! They do note that you won’t find this level of difficulty in any of Nintendo’s own Mario levels, but the raw materials and rules available in the world allow for the complexity to spring up—probably why Super Mario Maker is so addictive. You may not be able to solve other problems in the “PSPACE” complexity class, but no one ever made them quite as fun as a Mario level.

That’s part of the point of papers like these, according to study co-author Erik Demaine. Demaine and his colleagues demonstrated the potential difficulty of Mario by creating a “locked door” with a “Spiny” enemy (thrown by those Lakitu things that ride clouds) that can either result an a traversable or untraversable path. With the two-state nature of the locked door behaving like bits in a computer, they’d be able to produce exponentially difficult levels with a bit of fun creativity with familiar Mario baddies, and Demaine said,

My hope is through this class and these kinds of papers to encourage more people to do this, because it really does build up a lot of expertise that makes it easier to conquer problems. The more practice we get as a collective, the better we are at solving these types of problems. And it’s important to know the limitations of algorithms.

(via Wired, image via Nintendo)

The Mary Sue has a strict comment policy that forbids, but is not limited to, personal insults toward anyone, hate speech, and trolling.—

Follow The Mary Sue on Twitter, Facebook, Tumblr, Pinterest, & Google+.

Have a tip we should know?

Filed Under:

Follow The Mary Sue:

Dan is a video game modding hobbyist and secret ninja who lives in North Carolina with his wife, Lisa Brown, and his dog, Liz Lemon, both of whom are the best.