...and not 'Sonic.'
Image: Georgia Institute of Technology
Super Mario Bros. is without question one of the finest video games of all time. Its game mechanics, physics, and challenges all form a cohesive experience that has kept gamers smashing goombas for decades. It's damn near perfect.
But in recent years, the plump plumber has found a new purpose beyond pure entertainment; for some, it is also a test bed for artificial intelligence research.
The game has been used to develop AI that can learn the nuances of Super Mario Bros. well enough to beat the game, and intelligently build its own playable levels. An annual Mario AI competition even ran from 2009 to 2012. And just this week, University of Manchester computer scientists Ke Chen and Peizi Shi posted a paper to the ArXiv preprint server describing how they used AI to generate Mario levels, noting that "Super Mario Bros, a classic 2D platform game, has become a popular test bed" for their research.
Games are ideal platforms for this sort of work; the logic, creativity, situational awareness, and decision-making skills required of players to both play and create new levels is what researchers are striving for in AI. But what, exactly, is it about Mario games that has made them the platform of choice for researching machine intelligence? Is it something about those finely-tuned mechanics, which made it such a legendary game in the first place? Perhaps AI researchers just love to play the game like the rest of us? As it turns out, the answer is a bit of both.
Mark Riedl and Matthew Guzdial are AI researchers at the Georgia Institute of Technology, where they use computer software to generate new Super Mario Bros. levels as a means of exploring how machines could one day help humans design games. One thing that makes Mario appealing to researchers such as themselves is a near-perfect balance between simplicity and complexity. Basically, the game's mechanics pose some interesting challenges for algorithms, but aren't so difficult that it's impossible to solve.
"It is a bit more fast-paced and dynamic than the Atari games that many are currently using to test AI," Riedl and Guzdial wrote to me in an email, regarding experiments that try to "teach" an AI to play the game. "The side-scrolling nature of the game means a lot of the game is unobservable to the AI, whereas many simpler arcade games have all information on screen at once."
Mario also inhabits a middle ground between simplicity and complexity for algorithms designed to generate Mario levels. "Mario levels definitely have pattern, but are also abstract," Riedl and Guzdial wrote. Levels may appear simple, but the tile-based design is "just hard enough to push the envelope" of AI research.
For Tom Murphy, a computer scientist at Carnegie Mellon who designed an algorithm called LearnFun that could "learn" to play through Super Mario Bros. flawlessly, it's the structure of the game that made it an ideal choice for his work. Specifically, it is how the stages follow a nested pattern—with each world containing four stages, a mechanic which permeates the game—that Murphy was drawn to.
Murphy's approach to building his algorithm depended on lexicographic ordering, which is really a simple math technique to order a set of values. The pervasive and easily-understood system of nested hierarchies in terms of stage design and item collection made Super Mario Bros. a perfect fit for Murphy.
"Other important things in the game follow this kind of nested structure," Murphy wrote me in an email. "Each 1UP sort of 'consists of' 100 coins, for example. It was thinking about Mario that led me to design LearnFun to learn only this kind of structure. It turns out that it works on many games, but nowhere is it as good a conceptual match as Mario."
Still, as perfect as Mario may be from a game design perspective—not to mention original, in terms of the history of video games—it's not exactly unique these days. There are plenty of platformers out there that followed in Mario's footsteps. Would Sonic, Contra, or Metroid, for example, work?
According to Julian Togelius, a professor of computer science at the New York University Tandon School of Engineering (he also founded the Mario AI competition), other games would work, although likely not as well. Super Mario Bros.'s biggest boon for AI researchers, so to speak, is ultimately its popularity and influence.
Yes, this is Super Mario World. Cut me some slack.
Everyone knows what it looks like to play Mario, so when an AI does it flawlessly, it's pretty attention-grabbing, Togelius said. "Most people have an idea of what it looks like to play Super Mario," Togelius told me over the phone. "Humans do things like stop and think, which an AI would never do. The ability to compare with yourself is very powerful."
Mario's influence on platformers that came after it also makes it a kind of "model organism," Murphy wrote me, since what can be learned by an AI in the Mario game universe is likely transferable to other games. And, Togelius said, that's exactly where the field is heading.
Although Togelius designed what is one of the most popular platforms for working with AI in the Mario game world, Super Mario Evolution, and founded the Mario AI competition, his next venture is a competition for AI that can play all kinds of games. Mario was a good starting point, but after a few years of everybody working with the same material, the tricks researchers use to beat the game with AI have gotten stale, Togelius said.
As for Riedl and Guzdial, they intend to pit their algorithm against the Sonic series next.
"Sonic is a bit harder because game levels are not as dependent on rectilinear features (e.g., ramps and slopes)," the researchers wrote. "Also the game is a bit faster. However, we believe Sonic is only slightly more difficult than Mario for this reason. By running the same game design learning algorithm on Mario and Sonic will yield a more general 'genre' knowledge."
It seems like Mario is a hit in the world of artificial intelligence research for many of the same reasons that made it a success with gamers. It's accessible yet challenging, logical yet surprising, and when Mario gets into the groove, it's mesmerizing—even if it's a machine doing the playing.
CORRECTION 10/30: An earlier version of this article stated that Julian Tongelius holds a position at the New York University School of Polytechnic Engineering. The school actually recently changed its name to the New York University Tandon School of Engineering, and this article has been updated to reflect that information. Motherboard regrets the error.