Math Proves Super Mario Bros., Legend of Zelda Are (NP-)HardBy: Drew Bowling - March 14, 2012
If you grew up playing video games in the 1980s or early 1990s, you almost certainly tasted the bitter fruit of frustration when you lost at games from the Mario Bros. or Legend of Zelda canons. Personally, I would unleash ungodly fits of anger when I couldn’t beat games, throwing remote controls and kicking whatever was within leg’s reach. As an adult, it’s easier to recognize that, yes, those games were definitely difficult.
Up until now that assertion has just been a logically inferred conclusion my friends and I have used to console our early shortcomings as players of video games, but now it looks as if science is on our side. A team of researchers at MIT (see, now you know it’s legit) studied the computational complexity of some Nintendo classics and ultimately determined that the games belong to a class of mind-addling math problems known as non-deterministic polynomial-time hard, or NP-hard. If you’ve still got parts of your brain that didn’t melt while trying to comprehend that sentence, NewScientist explains that designation in layman terms: when playing those games, it’s hard to predict whether it’s even possible for a player to get to the end of a given game level.
The study looked at the difficulty of making a speed run through a game level, which is basically a style of play wherein a player attempts to finish the level as fast as possible. For example, a classic game people like to take a speed run attempt on is Super Mario Bros. for the NES. If you’re not familiar with the amazing level of finesse required to successfully complete Super Mario Bros. at a breakneck speed, check out the video below of someone besting the entire game in a little over five minutes.
Other games that the researchers looked at in addition to Super Mario Bros. were that title’s sequels, Metroid, Pokémon, Donkey Kong, and, as mention, games from the Legend of Zelda Catalog. The team analyzed the respective games’ difficulty in navigating between red Koopa shells, Goombas, Barrel Cannons, Hookshot mastery, and Morph Balls and ultimately determined that, yes, several of these games proved to be NP-hard. Or, in other words, hard enough to probably send you into a bezerker rage born of frustration and hopelessness.