Emerging Technology from the arXiv

A View from Emerging Technology from the arXiv

Pac-Man Proved NP-Hard By Computational Complexity Theory

The classic ’80s arcade game turns out to be equivalent to the travelling salesman problem, according a new analysis of the computational complexity of video games

  • January 26, 2012

In the last few years, a few dedicated mathematicians have begun to study the computational complexity of video games. Their goal is to determine the inherent difficulty of the games and how they might be related to each other and other problems.

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

Viglietta’s work involves several steps. The first is to determine the class of computational complexity to which the game belongs. Next, he works out whether knowing how to solve the game also allows you to solve many other problems in the same class, a property that complexity theorists call ‘hardness’. Finally, he determines whether the game is complete, meaning that it is one of the ‘hardest’ in its class. 

His approach is relatively straightforward. He first works through a number of proofs showing that any video game with specific game-playing properties falls into a certain complexity class. 

He then classifies the games according to game-playing properties they have. 

For instance, one type of game involves a player moving through a  landscape visiting a number of locations. He calls this ‘location traversal’ and an example would be a game in which certain items are strewn around 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 use path games might include downhill races. 

He then uses graph theory to prove that any game exhibiting both location traversal and single-use paths is NP-hard, that’s the same class of complexity as the travelling salesman problem. 

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

He shows how games fall into other complexity categories too. For example, games that feature pressure pads to open and close doors are PSPACE-hard if each door is controlled by two pressure plates. Doom falls into this category.

And so on.

The resulting list is impressive. Here are a few 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 reasoning, see the paper below.

That’s clearly been a labour of love for Viglietta, given the title of his paper: “Gaming Is A Hard Job, But Someone Has To Do It!”

Interestingly, he says this kind of analysis is unnecessary 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 these older games all the more charming still.

Ref: arxiv.org/abs/1201.4995 :Gaming Is A Hard Job, But Someone Has To Do It!

Want to go ad free? No ad blockers needed.

Become an Insider
Already an Insider? Log in.

Uh oh–you've read all of your free articles for this month.

Insider Premium
$179.95/yr US PRICE

More from Intelligent Machines

Artificial intelligence and robots are transforming how we work and live.

Want more award-winning journalism? Subscribe and become an Insider.
  • Insider Premium {! insider.prices.premium !}*

    {! insider.display.menuOptionsLabel !}

    Our award winning magazine, unlimited access to our story archive, special discounts to MIT Technology Review Events, and exclusive content.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

    First Look. Exclusive early access to stories.

    Insider Conversations. Listen in as our editors talk to innovators from around the world.

  • Insider Plus {! insider.prices.plus !}* Best Value

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus ad-free web experience, select discounts to partner offerings and MIT Technology Review events

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning magazine and daily delivery of The Download, our newsletter of what’s important in technology and innovation.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

/
You've read all of your free articles this month. This is your last free article this month. You've read of free articles this month. or  for unlimited online access.