{"id":8900,"date":"2016-06-05T08:29:48","date_gmt":"2016-06-05T08:29:48","guid":{"rendered":"http:\/\/revoscience.com\/en\/?p=8900"},"modified":"2016-06-05T08:29:49","modified_gmt":"2016-06-05T08:29:49","slug":"super-mario-brothers-is-hard","status":"publish","type":"post","link":"https:\/\/www.revoscience.com\/en\/super-mario-brothers-is-hard\/","title":{"rendered":"\u201cSuper Mario Brothers\u201d is hard"},"content":{"rendered":"

Analysis shows popular video game is among the hardest problems in the \u201ccomplexity class\u201d PSPACE.<\/strong><\/em><\/span><\/p>\n

\"Illustration:<\/a>
Illustration: Christine Daniloff\/MIT<\/figcaption><\/figure>\n

CAMBRIDGE, Mass.<\/strong> —\u00a0Completing a game of \u201cSuper Mario Brothers\u201d can be hard \u2014 very, very hard.<\/span><\/p>\n

That\u2019s the conclusion of a new paper from researchers at MIT, the University of Ottawa, and Bard College at Simon\u2019s Rock. They show that the problem of solving a level in \u201cSuper Mario Brothers\u201d is as hard as the hardest problems in the \u201ccomplexity class\u201d PSPACE, meaning that it\u2019s even more complex than the traveling-salesman problem, or the problem of factoring large numbers, or any of the other hard problems belonging to the better-known complexity class\u00a0NP<\/span><\/a>.<\/span><\/p>\n

In a standard \u201cSuper Mario Brothers\u201d game, Mario runs across terrain that unspools from the right side of the screen. While battling monsters, he must complete various tasks, which can involve navigating brick structures that may rise from the ground plane of the game but may also hang in the air unsupported. The completion of a level is marked by Mario\u2019s reaching a flagpole.<\/span><\/p>\n

The new paper doesn\u2019t attempt to establish that any of the levels in commercial versions of \u201cSuper Mario Brothers\u201d are PSPACE-hard, only that it\u2019s possible to construct PSPACE-hard levels from the raw materials of the \u201cSuper Mario\u201d world.<\/span><\/p>\n

The work follows on a paper from two years ago, with two of the same coauthors, which showed that \u201cSuper Mario Brothers\u201d is at least as hard as the hardest problems in NP. But at the time, the researchers couldn\u2019t determine whether it was any harder. \u201cPSPACE is its final home,\u201d says Erik Demaine, an MIT professor of electrical engineering and computer science and a co-author on both papers.<\/span><\/p>\n

[pullquote]Mathematically, video games are not very different from computational models of real-world physical systems, and the tools used to prove complexity results in one could be adapted to the other.[\/pullquote]<\/p>\n

Demaine and his colleagues \u2014 Giovanni Viglietta, a postdoc in electrical engineering and computer science at the University of Ottawa and a coauthor of the earlier paper; and Aaron Williams, a professor of computer science at Bard College at Simon\u2019s Rock \u2014 will present their new paper at the International Conference on Fun with Algorithms next week.<\/span><\/p>\n

Questions of proportion<\/strong><\/span><\/p>\n

Theoretical computer scientists categorize algorithms according to their execution times, which they measure in terms of the number of data items the algorithms manipulate. An algorithm for finding the largest number in a list of N numbers, for instance, has a running time proportional to N. An algorithm that, say, calculates the flying distances between N airports on a map has a running time proportional to N^2, because for every airport, it has to calculate the distance to each of the others.<\/span><\/p>\n

Algorithms whose running times are proportional to N raised to a power are called \u201cpolynomial.\u201d A polynomial algorithm whose running time is proportional to, say, N^3 is slower than one whose running time is proportional to N. But those differences pale in comparison to the running times of exponential algorithms, whose running time is proportional to 2^N.<\/span><\/p>\n

If an algorithm whose execution time is proportional to N takes a second to perform a computation involving 100 elements, an algorithm whose execution time is proportional to N^3 takes almost three hours. But an algorithm whose execution time is proportional to 2^N takes 300 quintillion years.<\/span><\/p>\n

The complexity class NP is a set of problems whose solutions can be verified in polynomial time, even if finding those solutions takes \u2014\u00a0as far as anyone knows<\/span><\/a>\u00a0\u2014 exponential time. To use the most familiar example, factoring a 1,000-digit number is probably beyond the capacity of all the computers in the world in the lifetime of the universe, but verifying a solution \u2014 multiplying the factors together \u2014 is something a smartphone could do.<\/span><\/p>\n

Like NP, PSPACE contains problems that appear to require exponential time to solve. But the hardest problems in PSPACE \u2014 the PSPACE-hard problems \u2014 also take exponential time to verify. In some sense, that makes PSPACE a natural place for a video game to reside. Figuring out how to complete a fiendishly difficult level of \u201cSuper Mario Brothers\u201d could take a long time, but so could navigating that level, even with the solution in hand.<\/span><\/p>\n

Fundamental components<\/strong><\/span><\/p>\n

In their earlier paper, Demaine, Viglietta, and colleagues described a generic video-game structure that they call a locked door. The structure must have a path through it that can be either safe to traverse or not, and there must be a way for the player to switch the state of the path.<\/span><\/p>\n

Because the locked door has two possible states, it can represent a bit of computer memory, and because it has a path through it that can be opened or closed, it can serve as an element of a computational circuit. The researchers were able to show that any computational problem could be described by locked doors strung together in the right configuration. If the problem is exponentially hard, then figuring out how to complete the level is exponentially hard, too.<\/span><\/p>\n

In the earlier paper, Demaine, Viglietta, and their colleagues demonstrated how to build locked doors in several versions of the game \u201cDonkey Kong Country,\u201d but they couldn\u2019t figure out how to build one in \u201cSuper Mario Brothers.\u201d \u201cWe thought it was impossible,\u201d Demaine says.<\/span><\/p>\n

But it\u2019s not. The locked door described in the new paper uses a monster from the \u201cMario Brothers\u201d world called a \u201cspiny,\u201d which will move back and forth continuously between two barriers but will never spontaneously jump either of them. As the spiny approaches a barrier, however, Mario can bump the floor beneath it and send it over. In the researchers\u2019 new locked door, if the spiny is on one side of a barrier, the path through the structure is untraversable; if it\u2019s on the other, the path is open. And separate paths through the structure allow Mario to bump the spiny from one side to the other.<\/span><\/p>\n

Fun and games<\/strong><\/span><\/p>\n

The result could have implications beyond the design of ever-more-baffling games of \u201cSuper Mario Brothers.\u201d Mathematically, video games are not very different from computational models of real-world physical systems, and the tools used to prove complexity results in one could be adapted to the other.<\/span><\/p>\n

\u201cI\u2019m really excited about these kinds of hardness proofs, and I\u2019ve been pushing them a lot in the last couple years,\u201d Demaine says. \u201cI even taught an\u00a0entire course<\/span><\/a>\u00a0about them. I\u2019m pretty good at them, just through practice, and I wanted to somehow distill that into a form that other people could learn. So the class was a first attempt to do that. But it\u2019s already a really useful reference. I go and look at these lecture notes all the time to see, \u2018Is that variation of this problem hard?\u2019\u201d<\/span><\/p>\n

\u201cMy hope is through this class and these kinds of papers to encourage more people to do this, because it really does build up a lot of expertise that makes it easier to conquer problems,\u201d he continues. \u201cThe more practice we get as a collective, the better we are at solving these types of problems. And it\u2019s important to know the limitations of algorithms.\u201d<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Theoretical computer scientists categorize algorithms according to their execution times, which they measure in terms of the number of data items the algorithms manipulate. <\/p>\n","protected":false},"author":6,"featured_media":8901,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[43,30,17],"tags":[],"class_list":["post-8900","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-computer-science","category-entertainment","category-research"],"featured_image_urls":{"full":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",639,426,false],"thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0-150x150.jpg",150,150,true],"medium":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0-300x200.jpg",300,200,true],"medium_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",639,426,false],"large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",639,426,false],"1536x1536":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",639,426,false],"2048x2048":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",639,426,false],"ultp_layout_landscape_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",639,426,false],"ultp_layout_landscape":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",639,426,false],"ultp_layout_portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",600,400,false],"ultp_layout_square":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",600,400,false],"newspaper-x-single-post":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",639,426,false],"newspaper-x-recent-post-big":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",540,360,false],"newspaper-x-recent-post-list-image":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",95,63,false],"web-stories-poster-portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",639,426,false],"web-stories-publisher-logo":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",96,64,false],"web-stories-thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/06\/MIT-Mario-Bros_0.jpg",150,100,false]},"author_info":{"info":["Amrita Tuladhar"]},"category_info":"Computer Science<\/a> Entertainment<\/a> Research<\/a>","tag_info":"Research","comment_count":"0","_links":{"self":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/8900","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/comments?post=8900"}],"version-history":[{"count":0,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/8900\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media\/8901"}],"wp:attachment":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media?parent=8900"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/categories?post=8900"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/tags?post=8900"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}