After More Than 20 Years, 1980s Video Games Officially Hard

If you ever felt guilty about spending too much time playing those old Nintendo video games and never achieving victory, you may have some relief. It’s official: those eight-bit video games were very hard, or at least mathematically difficult.

A research team that includes Professor Erik Demaine and doctoral candidate Alan Guo analyzed the computational complexity of classic Nintendo video games, including the first three Super Mario Bros., Donkey Kong, and the Legend of Zelda franchise. Their math-heavy study, “Classic Nintendo Games are (NP-) Hard,” discovered that many games fall into a category of mathematical problems called “NP-hard,” or equivalent to the most difficult solvable mathematical theory.

From SlashGear:

“Basically, the researchers mapped out every hazard, every bottomless pit, every flying enemy, every bullet bill, as a ‘city’ and discovered that, while there is a mathematical way to solve the most efficient route, it is pretty darn difficult.”

The team, which also includes Free University of Brussels faculty member Greg Aloupis, asked one basic question: given the starting position, how difficult is it to reach the goal? They determined the games were very similar–each begins at a specific point with a task-completing objective –and are scaled-down versions of another problem, “NP-complete,” or computationally unsolvable. The NP-complete problems are simplified in the games, therefor reverting to NP-hard.

From The New Scientist:

“(It’s the) travelling salesman problem - finding the shortest route between a series of points - which is of real interest in the field of logistics, and also the knapsack problem, used in deciding how to allocate resources. So theoretically you could convert an example of either problem into a Mario level, and play the game to solve it. That approach would be fun, says Demaine, although it would probably be simpler to solve the satisfiability problem directly.”