Punching bricks, pouncing on Goombas, and sliding down flagpoles might not seem challenging to veteran Super Mario Bros. speed-runners, but what about to number-crunching computers? A group of mathematicians analyzed the computational complexity of Mario, Donkey Kong, the Legend of Zelda, Metroid, and Pokemon, to find out how difficult it is to divine the quickest path to victory in each game — and they claim to have proven that some of the games are “NP-hard,” which means it’s very difficult to find out even whether it’s possible for the player to reach the end, let alone the quickest route to completion.
Mathematicians prove that video games are hard to solve
A group of mathematicians analyzed the computational complexity of Mario, Donkey Kong, the Legend of Zelda, Metroid, and Pokemon, to find out how difficult it is to divine the quickest path to victory in each game — and they claim to have proven that some of the games are “NP-hard,” which means it’s very difficult to find out even whether it’s possible for the player to reach the end, let alone the quickest route to completion.
A group of mathematicians analyzed the computational complexity of Mario, Donkey Kong, the Legend of Zelda, Metroid, and Pokemon, to find out how difficult it is to divine the quickest path to victory in each game — and they claim to have proven that some of the games are “NP-hard,” which means it’s very difficult to find out even whether it’s possible for the player to reach the end, let alone the quickest route to completion.
is executive editor who has obsessed over headlines and internet speeds since 2011. He previously worked as an advocate for the National Park System.
While the practical consequences of this discovery are not likely to impact the average video game player — games are designed to be completed, even if not by the most optimal route — New Scientist points out that the results show that level designers may not be able to easily decide whether a level can be successfully completed through the use of an algorithm. Be sure to check out the team’s scientific paper if you’ve got the mathematical chops.
Follow topics and authors from this story to see more like this in your personalized homepage feed and to receive email updates.
