Have you ever played the first Super Mario Brothers? Those who have all know the frustration and anger that comes from repeatedly losing a level. If it makes you feel any better, computer scientists have found that beating a level in Super Mario Brothers is the equivalent to solving some of the hardest problems in computer science. In computer science problems that are this hard are called "NP" problems, "P" problems are easy. Computer Scientists and Mathematicians often converse about solving the general statement that P does not equal NP. If P doesn't equal NP then there is no fast, easy way to solve hard problems. So if P does equal NP that would mean we could solve hard problems a lot faster, and easier.
MIT scientists have been doing research that shows solving a level in Super Mario Brothers is as hard as completing some of the hardest problems in the complexity space PSPACE. PSPACE is the complexity class higher than NP, meaning their even more difficult. Like NP, PSPACE contains challenging problems that take a lot of time and effort to solve compared to P problems . Figuring out how to complete a difficult level of “Super Mario Brothers” takes a long time for beginners and even experienced players who have already completed it. This is because of the difficulty of navigating the level and getting through each checkpoint. Even with the solution to the level it still takes a lot of time to beat it. It's almost unbelievable that such a simple, old game is as difficult as some of the most complex problems in computer science.
References:
http://gizmodo.com/playing-super-mario-brothers-is-like-solving-a-super-ha-1780010492
http://news.mit.edu/2016/mario-brothers-hard-complexity-class-pspace-0601
Hey William, interesting read about the use of Artificial Intelligence in computer science. Its fascinating how wide-spread AI is, from using brute-force methods to solve simple computer games to predicting price movements in financial markets.
ReplyDeleteThe one question that came to mind after I read this is that would this study insinuate that complex computers games are in anyway a cursor that could point towards a persons capability of solving complex problems in the real world? Or are there other factors which make individuals better at solving complex in game problems, but less effective at solving real world problems. Even though some of those in game problems are reported to be more complex than real world problems.
ReplyDelete