January 26, 2012

Pac Man Video Game is NP Hard

Arxiv - Gaming is a hard job, but someone has to do it! (12 pages)

We establish some general schemes relating the computational complexity of a video game to the presence of certain common elements or mechanics, such as destroyable paths, collecting items, doors activated by switches or pressure plates, etc.. Then we apply such \metatheorems" to several video games published between 1980 and 1998, including Pac-Man, Tron, Lode Runner, Boulder Dash, Deektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble 3, and Starcraft. We obtain both new results, and improvements or alternative proofs of previously known results.

A game is said to exhibit the location traversal feature if the level designer can somehow force the player's avatar to visit several specifi c game locations, arbitrarily connected together, in order to beat the level. Locations may be visited multiple times in any order, but the first one is usually fi xed (starting location), and sometimes also the last one is (exit location).

Metatheorem 1. Any game exhibiting both location traversal and single-
use paths is NP-hard.

Doors and pressure plates

A door is a game element that can be open or closed, and may be traversed by the avatar if and only if it is open. A door's status may be modifi ed
by certain actions of the avatar, such as activating a pressure plate. A
pressure plate is a button that is pushed whenever the avatar steps on it,
and its e ffect may be either the opening or the closure of a specifi c door.
Each pressure plate is connected to just one door, and each door may be
controlled by at most two pressure plates (one opens it, one closes it).

Metatheorem 2. If a game features doors and pressure plates, and the
avatar has to reach an exit location in order to win, then:

a) Even if no door can be closed by a pressure plate, and if the game is non-planar, then it is P-hard.
b) Even if no door is controlled by two pressure plates, the game is NP- hard.
c) If each door may be controlled by two pressure plates, then the game is PSPACE-hard.

Metatheorem 3. If a game features doors and k-switches, and the avatar
has to reach an exit location in order to win, then:

a) If k greater than or equal to 1 and the game is non-planar, then it is P-hard.
b) If k greater than or equal to 2, then the game is NP-hard.
c) If k greater than or equal to 3, then the game is PSPACE-hard.

Boulder Dash (First Star Software, 1984) is NP-hard.
Deflektor (Vortex Software, 1987) is in L
Doom (id Software, 1993) is PSPACE-hard
Lemmings (DMA Design, 1991) is NP-hard
Lode Runner (Br derbund, 1983) is NP-hard
Mindbender (Magic Bytes, 1989) is NL-hard

Pac-Man (Namco, 1980) is NP-hard. The decisional problem is whether a level can be completed without losing lives. We assume full con gurability of the amount of ghosts and ghost houses, speeds, and the durations of Chase, Scatter, and Frightened modes

Pipe Mania (The Assembly Line, 1989) is NP-complete.
Prince of Persia (Br derbund, 1989) is PSPACE-complete
Puzzle Bobble 3 (Taito, 1996) is NP-complete
Skweek (Loriciel, 1989) is NP-complete
Starcraft (Blizzard Entertainment, 1998) is NP-hard
Tron (Bally Midway, 1982) is NP-hard

The Complexity of well known games are listed at wikipedia