Computer program learns to play classic NES games
Readers of a certain age will recall spending a substantial amount of time during childhood playing games like Super Mario Bros. on the Nintendo Entertainment System (NES). Little did you know that all those hours spent staring at the radiant glow of the TV screen was just one marginally efficient path to victory. PhD computer science researcher Tom “Tom7” Murphy has developed a program called Playfun that can play NES games by itself. Surely the robots are ready to take over now.
The full (and very science-y) details of the process are available in the paper, titled “The First Level of Super Mario Bros. is Easy with Lexicographic Orderings and Time Travel… after that it gets a little tricky.” Just to be clear, this is a real paper that was published in SIGBOVIK 2013. The 22-page paper is a little dense, so Tom7 has thoughtfully recorded the above video version, and it’s amazing.
The technique he used leverages lexicographic orderings, a way of sorting items based on size or ranking. It’s the same way a dictionary is sorted, but Tom7 used lexicographic orderings to describe what it means to “win” a video game. There are certain things that increase when playing a game like Super Mario Bros. The score and level number will go up, for example. With enough data, Tom7 figured he could train Playfun to play the game.
The NES has just 2048 bytes of RAM, which isn’t a lot. Tom simply played the game himself and captured the RAM state every frame for several minutes. This block of data contains patterns — some of the RAM states are going up according to lexicographic ordering. The program can then play the game and emulate the RAM states, try various button inputs, and see if it can get the RAM to increment in the right direction.
That’s how you get to a program that can play Super Mario Bros without caring about the actual output. Playfun isn’t looking at the screen, it’s just trying to win with math. It can calculate ahead and anticipate actions based on the data it has. What’s particularly crazy is that Playfun instantly learns how to exploit bugs in the game. It doesn’t play like a human — Playfun plays with the cold methodical ruthlessness of a machine.
Super Mario Bros. works well, but some other games don’t obey the same rules. The Karate Kid, for instance, beats the machine every time. There are strategic elements in this title that don’t figure into lexicographic ordering.
If we can say anything, it’s that Tom7 is putting his PhD to use in the most awesome way. Feel free to dive into the full paper if you’re the intellectual sort. Playfun’s code is also posted to SourceForge for anyone to poke around with.
Now read: Macintosh Classic becomes NES arcade using a Raspberry Pi