Programmer creates lexicographic ordering code to play early Nintendo games

Apr 15, 2013 by Bob Yirka report
Programmer creates lexicographic ordering code to play early Nintendo games
Credit: Tom Murphy

(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 have created that allows a computer to play a , 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 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.

This video is not supported by your browser at this time.

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 . The results can be watched on the NES console, as Super Mario Brothers, and other games, appear to play themselves.

Explore further: Engineer leads effort to develop computer systems that can see better than humans

Related Stories

Global sales of Nintendo's Wii top 50 million

Mar 26, 2009

(AP) -- Japanese game maker Nintendo Co. said Thursday global sales of its popular Wii video game console have topped 50 million since it went on sale worldwide in late 2006.

Recommended for you

Hacking Gmail with 92 percent success

7 hours ago

(Phys.org) —A team of researchers, including an assistant professor at the University of California, Riverside Bourns College of Engineering, have identified a weakness believed to exist in Android, Windows ...

User comments : 5

Adjust slider to filter visible comments by rank

Display comments: newest first

Expiorer
1.5 / 5 (4) Apr 15, 2013
this algorithm is only for arcade games
Mycobacter
5 / 5 (1) Apr 15, 2013
So instead of simply being an emulation, this would be taking it a few steps further so the computer itself could play the game without needing a human user?
evropej
2.6 / 5 (5) Apr 15, 2013
The best part of the program was it paused the game since it knew it was going to lose lol
Lurker2358
1 / 5 (2) Apr 15, 2013
this algorithm is only for arcade games


2-D games are easier to program an a.i. Also, a lot of modern games don't even keep a score any more.

It would be a lot harder to program an a.i. which could play the more advanced mario games in 3-d, because of multiple goals and open exploration.
MCPtz
not rated yet Apr 15, 2013
@Mycobacter:
It can watch a human play and then 'get' some of the fundamentals of a simple game such as Mario, solving the game in its own weird ways.
He describes some simple drawbacks, e.g. Tetris and Karate Kid, as well as having some trouble exploring the solution space.