Pac-Man Proved NP-Hard by Computational Complexity Theory

In recent years, a few dedicated mathematicians have begun to study the computational complexity of video games. Their goal is to determine the games’ inherent difficulty and how they might relate to each other and other issues.

Today, Giovanni Viglietta from the University of Pisa in Italy unveils a herculean body of work in this area in which he classifies a large number of games from the 80s and 90s including Pac-Man, Doom, Tron and many others. .

Viglietta’s work involves several stages. The first is to determine the class of computational complexity to which the game belongs. Then, it determines whether knowing how to solve the game also solves many other problems of the same class, a property that computational theorists complexity call “hardness”. Finally, it determines if the game is complete, that is to say if it is one of the “most difficult” in its category.

His approach is relatively simple. He first works on a number of proofs showing that any video game with specific game properties belongs to a certain complexity class.

It then classifies the games according to the game properties they possess.

For example, one type of game involves a player moving through a landscape visiting a number of locations. He calls this “traversing locations” and an example would be a game where certain objects are scattered across a landscape and the goal is to collect them all.

Some location traversal games allow each location to be visited only once. So-called single-purpose path games may include downhill races.

He then uses graph theory to prove that any game with both place traversal paths and single-use paths is NP-hard, i.e. the same complexity class as the traveler problem. of business.

It turns out that Pac-Man falls into this category (the proof is distributing energy pills around the maze in a way that imposes single-use paths).

It shows how games fit into other categories of complexity as well. For example, games that feature pressure pads to open and close doors are difficult to PSPACE if each door is controlled by two pressure plates. Doom falls into this category.

etc

The resulting list is impressive. Here are some of his results:

Boulder Dash (First Star Software, 1984) is NP-hard.

Deflektor (Vortex Software, 1987) is in L.

Prince of Persia (Brøderbund, 1989) is PSPACE-complete.

Tron (Bally Midway, 1982) is NP-hard.

For the full list and rationale, see the document below.

It was clearly a labor of love for Viglietta, given the title of her article: “Gaming is hard work, but someone has to do it!”

Interestingly, he says that this type of analysis is not necessary for modern games. “Most recent commercial games incorporate Turing-equivalent scripting languages ​​that easily allow the design of undecidable puzzles as part of the gameplay,” he says.

In a way, that makes those older games even more charming.

Ref: arxiv.org/abs/1201.4995 :The game is hard work, but someone has to do it!

Sharon D. Cole