April 15, 2013 report
Programmer creates lexicographic ordering code to play early Nintendo games
(Phys.org) —Computer scientist Tom "Tom7" Murphy, has created a software program that is capable of playing early Nintendo Entertainment System (NES) video games such as Super Mario Brothers. His paper describing how he created the program and how it works, has been published in SIGBOVIK 2013.
Other programmers have created code that allows a computer to play a video game, but their approach is to "learn" how humans play the game, and then to mimic that by interacting with the game both manually and by watching action on the screen. Murphy has taken a completely different approach—his code does nothing but examine the contents of the memory chips inside the NES game console and then uses that information to teach itself how to succeed at playing the game. Because of this, his code can be used to play a variety of NES games.
Murphy discovered that when programming games for the early NES console, certain areas in the memory were used by early engineers working with limited memory, for certain things—keeping track of level for example. He also noted that for almost every aspect of the game, numbers held in memory grew larger when the player was doing well. That led him to use the idea of rising numbers as the means for telling his code how to know if it was winning. To make that happen, he used lexicographic ordering, which is a way of ordering data or information based on size, or ranking. Size matters, as noted, because it indicates winning. Ranking matters because it's how decisions are made. The rest of the code revolved around creating commands to cause actions, such as jumping, at appropriate times.
To create a baseline, Murphy played the game manually for several minutes, while a module recorded snapshots of memory—generating successive frames that could be analyzed and later used by the code that was meant to play the game itself. With that information in mind, the code then took over control, placing data into memory as would normally be done in reaction to a person manipulating the physical controls. To play the game, the code (running on a different computer) emulates human button-pushing and notes the results, modifying its actions to get the numbers in memory that are put there by the game, to increase. In so doing, it successfully plays the game. The results can be watched on the NES console, as Super Mario Brothers, and other games, appear to play themselves.
© 2013 Phys.org