This AI “solves” Super Mario Bros. and other classic NES games

In the 28 years since Super Mario Bros. was released, and it's obviously been comprehensively beaten, thoroughly, many thousands of times in that time by players around the world. But have you ever made the game beat itself?

That's what computer scientist Tom Murphy has done. At SigBovik 2013, he presented a program that "solves" how to play Super Mario Bros., or any other NES game, like it's just another kind of mathematical problem. And for those who know that SigBovik is an annual computer science conference dedicated to spoof research, hosted on April 1 every year, Murphy stresses that this is "100 percent real."

He outlines his method in a paper, "The First Level of Super Mario Bros. is Easy with Lexicographic Orderings and Time Travel... after that it gets a little tricky," but he also presented the results in the video you can see with this story.

Lexicographic ordering is a pretty simple mathematical technique used to determine the best order a set of values should come in. It's most commonly used in libraries or dictionaries for arranging books and words, for instance, with the alphabet determining the order of the letters.

Murphy created two programs, LearnFun and PlayFun, and began recording himself playing the first level (world 1-1) of Super Mario Bros. The NES puts out 60 frames of 2048 bytes per second, and each of these was fed into LearnFun. Everything in the NES's memory—the buttons being pressed, the number of lives left, the score, the locations of enemies, Mario's position as coordinates, and so on—is taken in by the LearnFun algorithm.

PlayFun then plays the game, and uses the knowledge from LearnFun to try and increase the values it knows it has to increase—Mario's score, and how far scrolled to the right Mario is in the level. "It's trying to find the sequence of inputs to make those values go up in the RAM," Murphy explains in the video.

The results are impressive. After some tweaking, Mario plays the first level just like a real person, jumping on enemies like Goombas and hitting boxes for coins. The program even learns how to take advantage of bugs and glitches, like timing jumps so that Mario begins falling again at the exact time that he makes contact with a Goomba. Mario's invincible when he's falling, so the touch kills the Goomba, not Mario, and it gives him a further jump boost.

It's still dumb in places, though—Murphy describes the whole method as "a really simple, mathematically elegant and stupid technique that really works"—so it still makes mistakes. At one point, until Murphy diagnoses a bug in LearnFun, Mario couldn't get himself to go backwards and try a different route. That's down to the simplicity of the approach, which relies on Mario always generally needing to scroll to the right while occasionally jumping over something to increase his score.

It never finishes the game, though—it gets stuck in world 1-3 at a particularly long jump. But it's pretty good considering the short development time. Murphy also shows it working on some other NES games, like the Karate Kid and Hudson's Adventure Island. In Bubble Bobble it's "totally pro," which is surprising because "it's single-screen, and there's no score gradient to help you out." It's also something of a daredevil when it comes to Pacman.

In Tetris, though, the method fails completely. It seeks out the easiest path to a higher score, which is laying bricks on top of one another randomly. Then, when the screen fills up, the AI pauses the game. As soon as it unpauses, it'll lose—as Murphy says, "the only way to the win the game is not to play."

This is not the first example of a Mario AI, and there's actually a Mario AI Championship that takes place every year. Contestants are given a Java clone of Super Mario Bros. and can enter several competitions relating to gameplay, level generation, and, for the first time in 2012, a Turing test. The audience watches footage of both AIs and humans playing the game, voting on which they think is the AI—the winner is the programmer who fools the most people.

The gameplay and learning algorithms rely on different methods to the one Murphy used, mostly related to pathfinding rather than solving it as a computational problem. The results are often impressive, as are the procedurally generated levels, which are rated based on how fun they are to play. Sticking the two together can occasionally create terrifying results too, as in this video of a well-trained AI trying to "beat" an endless level spawning dozens of monsters every few seconds.