Wopple wopple wopple wopple

Talk to anyone who grew up with video games in the late 80s, and you’ll often see them launch into crotchety old man mode. “Back when I was a kid, games were meant to be difficult! There weren’t any arrows that pointed where you had to go! You didn’t get save points every ten minutes! Heck, you were lucky to make it past stage three with all your lives intact!”

Yeah. Video games were hard back then. We get it. But, exactly how hard were they? It’s usually a subjective experience. How do you objectively determine a game’s difficulty? Giovanni Viglietta, a doctoral candidate studying computer science at the University of Pisa in Italy, found that by distilling a game’s mechanics down to the very basics, you can treat it like any other computational problem.*

At its core, Pac-Man is what Viglietta describes as a “location traversal game with single-use paths.” He starts the game at a fixed location and wanders around the environment until reaching an exit point. In this case, the exit point could be anywhere in the maze, since it’s ultimately the spot where Pac-Man munches his last dot.

But Pac-Man is not alone. Ghosts chase him down at every nook and cranny (or at least they seem to). He spends the majority of the game weaving in and out of corners until he chomps down on a power pellet. The roles have reversed. He stalks the ghosts until finally gobbling them up for extra points. This surge of power is not infinite though, and after a few seconds, he becomes a helpless target once again. His temporary invincibility results in single-use paths: once he eats a power pellet, he can walk through ghosts until the power-up’s effect wears off.

Viglietta classified Pac-Man as being NP-Hard, or non-deterministic polynomial-time hard. Parsing out what NP-hard means is no easy task, due to the convoluted nature of computational complexity and the fact that I am most definitely not a computer scientist. However, what I do know is that it a problem that an NP-Hard problem is on par with the travelling salesman, one of the most famous mathematical conundrums.

Math problems are best solved with doodles. [Image credit: Matt Hempel via Flickr]

Imagine that you are a salesman salesperson (hey, let’s at least make it gender neutral) that has to visit every state’s capital to peddle your wares. You know the distances of each city’s airports to one another. The company will only subsidize you up to an arbitrary distance, say 30,000 miles. Can you find a way to complete your job without going over your limit? In what order should you visit each city to achieve the shortest possible distance?

Working it out by hand is a daunting task that’s prone to error. How many times have you forgotten to carry a two or thought that 3 + 4 somehow equaled  8? You’re better off leaving it to a computer algorithm to figure it out. While it could quickly find the best route for a small number of cities, adding in more cities makes finding a solution more difficult. It increases at a polynomial rate, so instead of something x² number of steps, it could take x³, x⁴, and so on, eating up more and more computational time with each higher power. Researchers are still trying to figure out how to best deal with these types of problems and they are no strangers to frustration.

So Pac-Man is NP-Hard. What about other games? Viglietta chose to analyze other retrostyle games like Lemmings (NP-Hard), Starcraft (NP-Hard), and Doom (PSPACE-Hard). However, his research doesn’t apply to today’s games. Modern AI now includes an element of unpredictability. Maybe your computer opponents won’t always make the best choice. Maybe they’ll opt for the second or third best, keeping you (the player) on your toes. Complexity theory falls apart once uncertainty is integrated into the gameplay.

Then again, if you’re ripping aliens apart with a chainsaw gun or running away from the cops after committing mass vehicular homicide, I somehow doubt that these are the type of questions that pop into your head.

*This sentence was corrected for a factual error, 12:45pm March 1, 2012.