Skip to main content

Mathematicians prove that video games are hard to solve

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.

Share this story

Mario leap
Mario leap

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.

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.