Pac-Man is NP-hard, same as traveling salesman problem

 By Sebastian Anthony

An Italian researcher with a penchant for retro games — or perhaps just looking for an excuse to play games in the name of science! — has used computational complexity theory to decide, once and for all, just how hard video games are. In a truly epic undertaking, Giovanni Viglietta of the University of Pisa has worked out the theoretical difficulty of 13 old games, including Pac-Man, Doom, Lemmings, Prince of Persia, and Boulder Dash.

To begin with, Viglietta defines a few basic gameplay mechanics and sorts them into categories of complexity theory. Location traversal and single-use paths, ala Pac-Man, is NP-hard. Pressure plates, ala Prince of Persia or Portal, is PSPACE-hard if there are two pressure plates, and NP-hard if only one is required to open a door. In the case of switches, one switch is P-hard, two is NP-hard, and three or more is PSPACE-hard.

Viglietta then uses these characteristics to classify each of the 13 games. Boulder Dash, which involves traversing a map strewn with boulders, is NP-hard. Prince of Persia, thanks to its pressure plates, is PSPACE-complete. Doom, with its multiple switches, is PSPACE-hard (and Viglietta claims that most other FPSes and adventure games are the same).

Lemmings proved to be a bit harder to classify: If you just use Bashers and Miners, it is a traversal problem and NP-hard. Viglietta doesn’t try to tackle the complexity of using other types of lemming. A similar stretch allows him to classify StarCraft as NP-hard, where by each player is trying to produce the right units to allow him to traverse a certain path (to the enemy’s base).

If you’ve never heard of computational complexity theory, the best known example is the traveling salesman problem (TSP), which is NP-hard. In the TSP, you have to devise the most optimal route that visits a list of locations. This can be optimized as the shortest route, the fastest, the path of least resistance, and so on. Variants of the TSP are used to optimize transport systems, CPU designs, computer algorithms, and more. PSPACE represents much more complex problems and puzzles that takes in games like Mahjong, Reversi, or Doom. If you want to know more, hit up Wikipedia — but be warned, complexity theory is a bit of a beast.

Source:  Extremetech