Several months ago, I wrote about the proof, due to Richard Kaye of Birmingham University in 2000, that the seemingly innocent-looking game Minesweeper is an example of an NP-Complete problem. The essence being that no algorithm for solving the problem is known that scales as a polynomial function of the board size.
I suppose that it was inevitable that analysis of this sort would be extended to a host of other games. After all, most computer scientists no doubt enjoy gaming as much as they enjoy computers. In addition, unless there is some odd aspect of computer-scientist biology, each of them was once a child and, undoubtedly, was captivated by play. But it was with a particular satisfaction that, after aimlessly wandering across the internet, I discovered the charming paper entitled Classic Nintendo Games are (Computationally) Hard.
This paper, written by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta, is an exploration of five of the classic 8-bit Nintendo franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Using an approach much like what Kaye used in his analysis, Aloupis et al examine the generalized form of each of these games. A generalized form means that the size and structure of an individual board is open to manipulation but that the basic rules of the game are not altered. Rooms take on arbitrary sizes and configurations and the number of non-playing characters (NPCs) can be unlimited. Other than these liberties, the underlying mechanics of the game is maintained.
Now, I will confess that I never sunk much time into Donkey Kong, Legend of Zelda, or Metroid (much to my regret) and that I had only a passing flirtation with the Mario franchise, but Pokémon is a different story. I’ve spent countless hours with that franchise and don’t regret a minute of it. So, I thought I would discuss a little of how Pokémon can be thought of as NP-hard.
The first and most primitive notion is what Aloupis et al call the ‘decision problem of reachability’. This is a rather big and forbidding name for a basic problem that almost every gamer has asked himself during gameplay: ‘Given where I am and my current status can I reach that spot there?’ This is a particularly familiar problem in such large and open worlds like Elder Scrolls V: Skyrim.
The image below is an actual screenshot from Skyrim, where a player encounters a dragon on a mountaintop. Because this meeting is essential to the storyline, the game limits access to the summit until the player has completed certain changes in status (i.e., solved a number of puzzles or quests, etc.). Of course, the player doesn’t know this when the game commences and often the question as to whether the player can find a way up to the summit is left undecided until the plot advances to the point where the way becomes clear. The mountains that appear in the distance remain undecided for many players throughout their interaction in the game. They don’t figure in the plot and their accessibility is unknown unless the player manages to reach the peak. In absence of such a feat, the player has to conclude the answer as ‘maybe’ – thus showing how art imitates real life. I am sure that even the developers are not sure what answer to give.
Fortunately, the Pokémon games, being 2-dimensional worlds, are much simpler. But not so simple that the paper by Aloupis et al is a trivial read. In fact, I found it to be quite difficult in the sense that the framework being used is familiar only to the specialist and I have neither the time nor the inclination to get completely up to speed.
Instead, I would like to convey the flavor of it in terms of a Pokémon player. The general idea about ‘decision problem of reachability’ is captured in the game mechanic familiar to anyone who has ever played Pokémon, the NPC enemy trainers.
For those of you who are unfamiliar or who simply want me to define my terms carefully, here is a quick summary. In Pokémon, the player takes on the role of a young trainer who has in his possession between 1 and 6 pocket monsters. His goal is to level up his Pokémon primarily through engaging in battles with other Pokémon either wild or in the possession of other trainers. As the player roams the world, he encounters other trainers who, if the conditions are right, challenge the player to a battle.
Each enemy trainer possesses a set location, a direction in which he faces, and a line-of-sight. There are two ways to trigger a battle with an enemy trainer. First, the player can ‘sneak up’ on the enemy trainer by moving next to him without entering his line-of-sight. Talking to the enemy trainer initiates the battle but leaves the NPC in its set location. Second, the player can walk through the enemy trainer’s line-of-sight. The moment the player enters a space within the line-of-sight his motion is stopped and the enemy trainer moves from his set location to challenge the player. Alternatively, a player may choose to avoid the enemy trainer by either avoiding talking to the NPC or not entering his line-of-sight. This latter option is not always available.
Depending on which choice the player makes, certain areas in the game become accessible or inaccessible as the NPCs move to open or block certain spaces. This behavior, when generalized, is at the heart of the proof by Aloupis et al.
The basic structure of their analysis is the creation of certain playable scenarios, called gadgets. There are 6 gadgets that they use to prove NP-hardness: Start, Finish, Variable, Clause, Check, and Crossover. The precise nature of these gadgets is involved, so I’ll only touch the Variable gadget as it is easy to understand.
The Variable gadget’s purpose is to provide the player with a single choice that flips a switch between two positions. The construction Aloupis et al provide is
The red rectangle indicates the line-of-sight of the enemy trainer and the set location of the trainer is (2,4) (2nd row, 4th column from the upper left – denoted by the caricature of a man with glasses in a lab coat). A player entering at a has two choices. First, the player may choose to sneak up on the enemy by taking the top fork and beating him in battle, thus leaving the exit at c open. Second, the player may choose to take the bottom fork, forcing the enemy to come down to (3,4) to battle. Winning the battle then leaves the exit at b open.
The other 5 gadgets are constructed with similar elements and mechanics but often they are larger and more complicated to understand. And the details are not all that important unless one wants to understand the technical details. Rather, the basic message is that even cloaked behind the guise of a game, even ones as fun as the five famous Nintendo franchises analyzed, logic and decidability are all around us.