{"id":436,"date":"2016-02-19T23:30:24","date_gmt":"2016-02-20T04:30:24","guid":{"rendered":"http:\/\/aristotle2digital.blogwyrm.com\/?p=436"},"modified":"2016-02-18T21:01:13","modified_gmt":"2016-02-19T02:01:13","slug":"nintendo-and-complexity","status":"publish","type":"post","link":"https:\/\/aristotle2digital.blogwyrm.com\/?p=436","title":{"rendered":"Nintendo and Complexity"},"content":{"rendered":"

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<\/a>.\u00a0 The essence being that no algorithm for solving the problem is known that scales as a polynomial function of the board size.<\/p>\n

I suppose that it was inevitable that analysis of this sort would be extended to a host of other games.\u00a0 After all, most computer scientists no doubt enjoy gaming as much as they enjoy computers.\u00a0 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.\u00a0 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<\/em><\/a>.<\/p>\n

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:\u00a0 Mario<\/em>, Donkey Kong<\/em>, Legend of Zelda<\/em>, Metroid<\/em>, and Pok\u00e9mon<\/em>.\u00a0 Using an approach much like what Kaye used in his analysis, Aloupis et al<\/em> examine the generalized form of each of these games.\u00a0 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.\u00a0 Rooms take on arbitrary sizes and configurations and the number of non-playing characters (NPCs) can be unlimited.\u00a0 Other than these liberties, the underlying mechanics of the game is maintained.<\/p>\n

Now, I will confess that I never sunk much time into Donkey Kong<\/em>, Legend of Zelda<\/em>, or\u00a0Metroid<\/em> (much to my regret) and that I had only a passing flirtation with the Mario franchise, but Pok\u00e9mon is a different story.\u00a0 I\u2019ve spent countless hours with that franchise and don\u2019t regret a minute of it.\u00a0 So, I thought I would discuss a little of how Pok\u00e9mon<\/em> can be thought of as NP-hard.<\/p>\n

The first and most primitive notion is what Aloupis et al<\/em> call the \u2018decision problem of reachability\u2019.\u00a0 This is a rather big and forbidding name for a basic problem that almost every gamer has asked himself during gameplay:\u00a0 \u2018Given where I am and my current status can I reach that spot there?\u2019\u00a0 This is a particularly familiar problem in such large and open worlds like Elder Scrolls V: Skyrim<\/em>.<\/p>\n

The image below is an actual screenshot from Skyrim, where a player encounters a dragon on a mountaintop.\u00a0 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.).\u00a0 Of course, the player doesn\u2019t 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.\u00a0 The mountains that appear in the distance remain undecided for many players throughout their interaction in the game.\u00a0 They don\u2019t figure in the plot and their accessibility is unknown unless the player manages to reach the peak.\u00a0 In absence of such a feat, the player has to conclude the answer as \u2018maybe\u2019 \u2013 thus showing how art imitates real life.\u00a0 I am sure that even the developers are not sure what answer to give.<\/p>\n

\"Skyrim<\/a><\/p>\n

Fortunately, the Pok\u00e9mon games, being 2-dimensional worlds, are much simpler.\u00a0 But not so simple that the paper by Aloupis et al<\/em> is a trivial read.\u00a0 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.<\/p>\n

Instead, I would like to convey the flavor of it in terms of a Pok\u00e9mon player.\u00a0 The general idea about \u2018decision problem of reachability\u2019 is captured in the game mechanic familiar to anyone who has ever played Pok\u00e9mon, the NPC enemy trainers.<\/p>\n

For those of you who are unfamiliar or who simply want me to define my terms carefully, here is a quick summary.\u00a0 In Pok\u00e9mon, the player takes on the role of a young trainer who has in his possession between 1 and 6 pocket monsters.\u00a0 His goal is to level up his Pok\u00e9mon primarily through engaging in battles with other Pok\u00e9mon either wild or in the possession of other trainers.\u00a0 As the player roams the world, he encounters other trainers who, if the conditions are right, challenge the player to a battle.<\/p>\n

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.\u00a0 First, the player can \u2018sneak up\u2019 on the enemy trainer by moving next to him without entering his line-of-sight. \u00a0Talking to the enemy trainer initiates the battle but leaves the NPC in its set location.\u00a0 Second, the player can walk through the enemy trainer\u2019s line-of-sight.\u00a0 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. \u00a0Alternatively, a player may choose to avoid the enemy trainer by either avoiding talking to the NPC or not entering his line-of-sight.\u00a0 This latter option is not always available.<\/p>\n

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.\u00a0 This behavior, when generalized, is at the heart of the proof by Aloupis et al<\/em>.<\/p>\n

The basic structure of their analysis is the creation of certain playable scenarios, called gadgets.\u00a0 There are 6 gadgets that they use to prove NP-hardness: Start<\/em>, Finish<\/em>, Variable<\/em>, Clause<\/em>, Check<\/em>, and Crossover<\/em>.\u00a0 The precise nature of these gadgets is involved, so I\u2019ll only touch\u00a0the Variable gadget as it is easy to understand.<\/p>\n

The Variable gadget\u2019s purpose is to provide the player with a single choice that flips a switch between two positions.\u00a0 The construction Aloupis et al provide is<\/p>\n

\"Pokemon<\/a><\/p>\n

The red rectangle indicates the line-of-sight of the enemy trainer and the set location of the trainer is (2,4) (2nd<\/sup> row, 4th<\/sup> column from the upper left \u2013 denoted by the caricature of a man with glasses in a lab coat).\u00a0 A player entering at a<\/em> has two choices.\u00a0 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<\/em> open.\u00a0 Second, the player may choose to take the bottom fork, forcing the enemy to come down to (3,4) to battle.\u00a0 Winning the battle then leaves the exit at b<\/em> open.<\/p>\n

The other 5 gadgets are constructed with similar elements and mechanics but often they are larger and more complicated to understand.\u00a0 And the details are not all that important unless one wants to understand the technical details.\u00a0 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.<\/p>\n","protected":false},"excerpt":{"rendered":"

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.\u00a0… Read more ><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-436","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/436","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=436"}],"version-history":[{"count":0,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/436\/revisions"}],"wp:attachment":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=436"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=436"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=436"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}