Can a Linux-powered robot play video games faster than you? Only if he takes a hint from piano rolls...and doesn't desync.

Let me begin with a brief history of tool-assisted speedruns. It was 2003. Less than half the developed world had internet access of any kind, and YouTube hadn't been created yet. Smartphones were rare and nascent. Pentium III processors still were commonplace, and memory was measured in megabytes. It was out of this primordial ooze that an interesting video file circulated around the web—an 18MB .wmv labeled only as a "super mario bross3 time attack video" [sic]. What followed was an absolutely insane 11-minute completion of the game by someone named Morimoto replete with close calls, no deaths and Mario destroying Bowser after apparently effortlessly obtaining 99 lives. The only other context was a link to a page written in Japanese, and the rough encoding that Windows Media Video format was known for in that era made it difficult for casual viewers to observe that it was an emulator recording rather than the output of a real Nintendo Entertainment System (NES) console.

Figure 1. Morimoto's 2003 Super Mario Bros. 3 (SMB3) Time Attack Video

The video encode had in fact been made with the Famtasia NES emulator using Tool-Assisted Speedrun (TAS) re-recording tools consisting of a "movie file" of the sequence of all buttons pressed along with the use of savestates, or CPU and memory snapshots allowing returning to a previous state. Morimoto had in essence augmented his own human skill by using tools that allowed him to return to a previous save point any time he was dissatisfied with the quality of his play. By iteratively backing up and keeping only the best results, he had created what he considered at the time to be a perfect play-through of the game. I didn't know anything about how it was made the first time I saw the run, but it blew my mind and had me asking questions to which I couldn't find answers.

The human speedrunning community members were naturally highly offended by what they saw as an unlabeled abomination akin to a doped athlete being allowed to compete in the Olympics. Their view was that anything that augmented raw human ability in any way (even as rudimentary as keyboard macros in PC games) was considered cheating, and Morimoto's run was nothing more than a fraud best left ignored. There was fascination, intrigue and division. It was, in retrospect, the perfect recipe for a new website.

An industrious viewer going by the name Bisqwit was especially impressed by Morimoto's run of SMB3 and in late 2003 founded what ultimately would become TASVideos.org. He worked to ensure the human speedrunning community was as appeased as possible by providing disclaimers on all Tool-Assisted encodes of gameplay to help ensure that later viewers knew it was not purely human skill on display. He provided context for Morimoto's run through a history revival project.

Others quickly joined him, and a thriving community rallied around the creation of superplays and speedruns as well as around the creation of various tools like frame advance and embedded Lua emulator scripting to further allow "perfect" input with no mistakes. Older TAS runs inspired by Doom Done Quick that took segmented Doom runs to previously unheard of extremes were added to the site, bringing light to TAS content that substantially predated Morimoto's SMB3 run.

I was one of many who saw Morimoto's SMB3 run early on, and then I promptly put it out of my mind until TASVideos had grown in size to the point that it caught my attention circa 2006. By 2008, I had joined the site myself under the name dwangoAC in order to submit my first TAS attempt completing the NES pinball sim High Speed using the Linux-compatible FCEUX NES emulator. I was along for the ride, as TASes became a distinct art form anchored at TASVideos.org with a highly organized community of judges, publishers (video encoders) and emulator coders. TASVideos has since matured as the de facto repository of TAS content, and it now hosts a vast number of TAS movies across many game platforms.

Self-Playing Instruments: a Prior Art Interlude

I want to pull back for a moment and talk about a bit of history. Multiple centuries ago, incredible inventors started creating the first self-playing musical instruments using large drums with pegs like oversized music boxes and more complex devices using air forced through holes punched in cardboard, paper or even metal sheets to drive organs. Regardless of the mechanism, the end result was a pre-arranged sequence of notes that could be deterministically played back with the art form gaining widespread adoption by the 1920s. An entire industry of piano roll manufacturers with more or less agreed upon standardized piano roll formats for at-home player pianos existed.

Figure 2. An Aeolian Company Roll Library, Madrid, Spain, c. 1918; Image Credit: pianola.org

Some piano rolls were made by having a famous pianist sit at a reproducing piano that would faithfully record every note (good or bad) often by punching perforations or holes in a paper roll in real time as the pianist played. Eventually after a few attempts, the pianist's result would be satisfactory, and the piano roll would be copied and sold to customers to play on their own player pianos at home. The modern gaming equivalent would be human speedrunners recording their single-segment attempts and posting their best results online.

Other compositions of arranged music were made tediously by hand by reading the original arrangement and punching holes one row at a time while compensating for factors such as changing tempo and the fact that a piano roll shrinks in diameter causing the paper movement speed to change as the piece plays. I would equate this to making a normal TAS. At some point, someone making one of these pre-arranged compositions pieced together that there are 88 keys on a keyboard but only ten fingers on humans and reasoned that because the piano roll wasn't designed for a human anyway, a few extra simultaneous keys to add some punch to the composition couldn't hurt. The logical end result many decades later is now known as a Black MIDI composition, but that's an article for another day. The point is that if you take human limitations out of the equation, you can do some rather interesting things in many art forms.

The Dawn of Replay Devices

As PC specifications improved through the years, it became possible to use the increased resources to improve emulation accuracy without making the emulator unbearably slow. This allowed an even more ambitious concept to form: the idea of taking a TAS movie file and coercing an original unmodified console to behave the same way. The feat relies on extremely accurate emulation of each component of a console including any cartridge-based memory mappers and expansion chips. The theory is that if an emulator can step through the execution and interrelated dependencies of an entire system accurately enough, it should logically be possible to provide that same sequence of button presses to a real console and achieve the same result. This deterministic behavior is viable even on games that appear to contain randomness, because many consoles contain no external source of entropy and rely on player input as the only seed for a pseudo-random number generator—meaning a given sequence of button presses sent in order from power-on results in the same game state every time.

The idea was first raised in 2006, but it wasn't until 2009 that a TASVideos user going by the name true started working on a device to send prerecorded input to an NES via the controller ports. That same year, a hacker named Jaku independently created a device that was able to play back the entire first level of SMB1, unbeknownst to the TASVideos community. Finally in 2011, micro500 successfully completed an entire play-through verification of SMB1, thanks to accuracy improvements in the FCEUX emulator, and he created an Instructables guide on how he built his NESBot. DarkKobold followed micro500's guide to make his own device and played back SMB2 and Wizards and Warriors 3 publicly at SGDQ 2011 (more on that in a moment). By the end of the year, SoulCal had created a replay device named Droid64 that was capable of playing back the full 120-star completion of the N64 game Super Mario 64.

Interest in playing back TAS movie files on original hardware using replay devices increased from 2011 on and became known as console verification, but only a small number of creators had the requisite replay device hardware. TASVideos was updated with a special category to denote runs that had been console-verified with proof provided using camera shots of real consoles playing back runs. GhostSonic adapted his replay device to work on a Sega Genesis, and later endrift created a Game Boy Advance device using the Gamecube's Game Boy Player. Despite the progress on all those fronts, the concept that input could be sent to a console was generally not well known outside TASVideos.

Gaming for Charity

Over time, SpeedDemosArchive.com, or SDA, became the most used site for recording human speedrun attempts of video games. Several SDA users decided to hold a charity fundraiser in which speedrunners would complete one game after another without stopping in a 2010 24/7 marathon event they called Classic Games Done Quick (in homage to the earlier Doom Done Quick naming). The event was a success, raising more than $10,000 for CARE. The organizers went on to form a series of increasingly successful week-long marathon events held twice a year at GamesDoneQuick.com primarily benefiting Doctors Without Borders and the Prevent Cancer Foundation, in time arguably overshadowing SDA in visibility.

Back when DarkKobold used an NESBot at Summer Games Done Quick (SGDQ) 2011, the events still were being held in the basement of one of the organizers, but by the time the winter Awesome Games Done Quick (AGDQ) 2014 marathon was being planned, the events had increased in size substantially, with hundreds of attendees watching runs live in increasingly larger hotel ballrooms. It was around this time that I became interested in attending an event myself, but I wasn't content with just showing up to watch. I wanted to participate somehow. A lot of other people had the same idea, and it was fairly clear that only the most interesting or well executed runs had a chance to get in. For some reason, the idea of doing TAS-related content wasn't initially on my mind (and embarrassingly, I briefly entertained the idea of doing a speedrun of the game Scribblenauts Unlimited until I quickly discovered I lacked the requisite skills without a lot more practice, but I digress).

In time I came to my senses, remembered my TAS'ing roots, and volunteered to present TAS replays at the event. Although there were some dissenting voices from established SDA members who still were upset about the Morimoto conflict, the overall reaction was positive. In the end, the TAS submission was accepted and allotted 30 minutes of the marathon schedule.

Talking to a Console (and Hoping It Talks Back)

When I made the AGDQ 2014 TAS replay submission, I wasn't initially sure whether I could pull off console verification of the runs. At the time, I had no hardware and limited experience, and it was a daunting learning curve becoming familiar with everything from oscilloscopes to shift registers. I borrowed an Arduino from a colleague and set about attempting to build my own NESBot based on micro500's Instructables guide. Although I technically succeeded, in the sense that I was able to play back a run of Tetris, it quickly became clear to me that my amateur attempt using haphazard parts on an old breadboard was extremely fragile. After contemplating what it would take to get the device to survive a plane flight intact, I made the wise decision to abandon the design.

Figure 3. Fragile doesn't begin to describe the SD card pin connections.

My next attempt was, in theory, going to be far more simple from a wiring perspective by employing only the GPIO pins on a Raspberry Pi 1 Model B along with some resistors to allow it to handle the 5v voltage coming from the console. It didn't take me long before I knew I needed help, in part because I was out of my depth on the electrical engineering front. Folks like zid helped me in long troubleshooting sessions, but before that, they patiently had to help me sort out a mental model of how input from a controller actually works.

When I was a kid, I was very confused about how an NES controller could possibly work. I noticed there were eight buttons on the controller, but I saw only seven pins on the oddly shaped NES connector, and I assumed each button needed an individual wire. Early designs found on Atari and similar consoles did exactly that, but as more buttons were added to controllers, it made sense to use a shift register that could ingest all buttons in parallel but send the data down a single serial data line toward the console to reduce cabling costs.

The process of reading player input from a normal controller on an NES, SNES or any similar serial controller reading console goes like this. First, consider a situation where a player is pressing down one or more buttons—let's assume Right and B to Run Right for Great Justice. The game sends a latch signal to the controller effectively telling it to be prepared to be read, and then a clock line signal is sent at which point the state of the first button in an agreed-upon sequence is returned from the controller to the console on the serial data line; let's say it's the A button. Since that button isn't being pressed, a binary 0 is sent back by holding the line high (the logic is inverted on an NES). The process repeats for each button, and in this case, Right and B would be sent back as a 1 by holding the serial line low after the appropriate clock. All of those individual button presses eventually will be stored as a byte (or, for SNES, two bytes) in memory to be operated on by the game. That's all relatively straightforward, but the challenge is that while the time between latches is usually measured in milliseconds, the time between each clock pulse is potentially on the order of nanoseconds.

Figure 4. Latch, Pulse (Clock) and Data Line Example

Getting back to the poor Raspberry Pi—GPIO polling in nanosecond timeframes isn't one of its strong points. We quickly discovered it would frequently miss clock signals and sometimes even latch signals due to the Linux kernel's inadequate polling frequency of the GPIO pins. I was the President of the North Bay Linux Users' Group by that point, and I wanted to represent Linux as best I could, so I pushed hard to find a way to incorporate it. The solution was using a device designed by true that he named his NES/SNES replay device to buffer controller input that allowed the Raspberry Pi to send serial data at a much more achievable rate. The fusion of the two boards mounted to an R.O.B. robot inspired me to call the whole thing a ROBBerry Pi, but the name did not stick around for long. Possibly as a result of my (in retrospect) somewhat terrible name, multiple community members converged on the name "TASBot", and the name stuck. I now consider myself to be the keeper of TASBot, a one-of-a-kind individual with his own personality who uses a variety of replay devices to partake in his favorite pastime of smashing through games inhumanly fast.

Figure 5. TASBot in His Early Days before LEGOs

Snake, Pong and ACE

For TASBot's debut at AGDQ 2014, we started with the NES game Gradius, but it desynchronized a minute or so in. A desync is akin to the paper roll jamming or tearing during the middle of playing it back on a player piano; the piano roll keeps spinning, but you can generally be certain that nothing sane will come of it. In the case of Gradius, the result of the input desynchronizing with what the game state needed to be at that moment was instant death at the hands of a volcano. We set Gradius aside grudgingly and moved on to a TAS replay of Mario Kart 64 led by Weatherton and micro500, which went flawlessly and restored our confidence.

The real stand-out piece at AGDQ 2014 was Super Mario World. Masterjun had somewhat recently at the time discovered an Arbitrary Code Execution (ACE) glitch in SMW that allowed him to take total control of the game using techniques impossible for humans to achieve, just like those more-than-ten-fingers-required piano roll compositions. Initially, we were just going to use it to jump straight to the end credits, but in the hours leading up to our portion of the event, he was able to pull off something a lot more interesting in the form of causing the game to glitch, go to a black screen, and then suddenly start playing Pong with Mario's head. This was followed up with an implementation of the classic game Snake. We even handed the controller off and had humans play to show it wasn't a trick.

The compounded results of the event were beyond anything we had ever anticipated. News outlets including ExtremeTech and especially Ars Technica's Kyle Orland covered the exploits and hundreds of thousands watched the shenanigans on YouTube after the fact. Over the course of eight GDQ events and several auxiliary appearances since then, TASBot has repeatedly demonstrated the amazing talent of hackers, coders and brilliant minds like Ilari, p4plus2, total, Lord Tom and many others. TAS content at GDQ events has conservatively raised more than $400,000 for charity, and for their part, GDQ events have raised more than $16M for charity while often breaking $2M in a single event with live viewership often exceeding 200,000 live viewers at any given time. Multiple new replay devices have been made like true's unique standalone multireplay device, micro500's TASLink 4-port and extremely versatile device, and total's PSoC5-based high datarate devices.

Figure 6. TASBot with micro500's TASLink Board Held by dwangoAC

Personally speaking, TASVideos site staff members, including Nach and Mothrayas, invited me to join them, and I came on staff as the official TASVideos Ambassador. I went on to present what we had done at DEFCON, GeekPwn, Thotcon and other conferences with the help of graphics from Ange Albertini and showed how hunting for glitches in games using TAS techniques can help teach reverse-engineering skills.

The Many Ways TASBot Plays

I'm still astounded at what the teams I've led for have accomplished. I may be the primary organizer and presenter, but none of what we've done ever could have been possible without the talent and drive of a huge team of folks. TASBot.net has a full listing where you can see some really wild stuff:

• Super Mario Bros. 1, 2, 3 and Lost Levels by agwawaf beaten simultaneously with the same sequence of button presses using micro500's TASLink 4-port replay device.
• Super Mario Bros. being played inside Super Mario World thanks to a truly inspired setup conceived and executed by p4plus2.
• micro500's Brain Age consisting of artwork like drawing a picture of a dog's head and still answering math problems with the correct answer.
• Pokemon Plays Twitch from p4plus2 and many others where we messaged Twitch chat with Linux scripts and displayed it on Pokemon Red inside a Super Game Boy.
• Sk'Hype where two NES consoles for stereo audio plus an SNES for video were used to perform a remote video call scripted entirely from Linux at 10 fps with help from a truly massive team spearheaded by micro500, MediaMagnet, p4plus2, total, Ilari, fuzyll and many more.

It's the Cables

So if you're feeling masochistic, you may be asking yourself if you can do this at home on your own retro console. The answer is a fairly easy yes in one sense, as several reference designs exist from which to choose—the PSoC5 DevKit board in particular is only $15, although it can be tricky to flash with total's firmware load using Linux. That's not the biggest problem, however, as that honor goes to cables. The biggest issue is that the higher datarate runs require one or sometimes even two extra NES or SNES data lines that are usually used only for things like the light gun and aren't populated on extension cables, which are the easiest way to connect to the console ports. It's surprisingly difficult to add extra wires to the connectors, because they often are nothing more than thin foil to allow the controller cables to be flexible.

Even if you stick to simple runs that require only a single data line, it can require rather delicate soldering work to connect an extension cable to something durable enough to hang off a breadboard or directly off a PSoC5. Beyond that, dealing with the 5v nature of the consoles also can be a bit of a challenge. We've often thought about what it would take to mass produce a replay device that connects directly to NES or SNES consoles, but so far, it isn't clear if it would be market-viable.

Figure 7. Your cables probably will look something like this.

But...Linux?

With all of that context out of the way, it's finally time show something involving a Linux terminal. It's worth mentioning that every GDQ event has been primarily driven by Linux aside from some obvious exceptions, such as playing back the Windows version of VVVVVV using the Hourglass rerecording framework. Some runs have used Linux the same way the first Gradius run did as merely a method to shove a bitstream of data stored on a Linux device through a USB-attached serial interface, but several payloads have done far more extreme things.

There's one setup in particular that pushes an unmodified SNES to the limits—a full 16-bit 32kHz stereo audio player I've dubbed JukeSNES created by total using ideas and snippets of code from a large swath of hackers who came before him. If you want to play along at home, you'll need a rather daunting list of equipment including an SNES, a copy of Super Mario World, every dataline on both controller ports connected to cables, and a device fast enough to handle the datarate like the PSoC5 design from total.

All of the scripts and code listed below can be found in this GitHub repository. After connecting everything with the power off and no saves on the SMW cartridge, run python3 play_r16y.py /dev/ttyACM0 smw_stereo_pcm_v6.r16m. The first argument to the script is the serial interface the replay device is connected to, and the second argument is the file containing the bitstream of data to send consisting of the raw string of bits that needs to be sent to the console. (As a side note, there are separate "dump scripts" written for individual emulators that create these bitstream files, but the files themselves contain no metadata about how many controllers are present, so there's an ongoing desire to find someone to step up and create a headerfile format.)

Once everything is staged and connected, the next step is to power on the console. If everything goes right, the game will start, and Mario will appear to do some rather strange and random things in the first level, eventually triggering a glitch that causes the screen to change to a static view showing text about playing audio. The next step is to issue a command similar to this:

ffmpeg -i http://radiotasbot.com:9989/ocremix" -hide_banner
 ↪-v quiet -f s16le -ac 2 -ar 32000 -acodec pcm_s16le - |
 ↪./tasbot_stream_snes_stereo16.py

where the section after -i can be any ffmpeg source. There's a lot to unpack here, but essentially what's happening is ffmpeg is massaging the audio data to use stereo, 16-bit, 32-kHz raw PCM audio, which is piped into the streaming script, which then rearranges the data into exactly the bitstream format we need it in for the replay device. The result is beautiful sounding audio that demands every last clock cycle out of the poor SNES. I personally use the device to play background music with the help of MediaMagnet when I'm streaming on Twitch just for the sheer geek cred, but even I confess it's absurdly complex.

Figure 8. Why keep audio routing simple if you can make it ridiculously complex?

The TAS Journey from Here

The road to this point has been long. There have been some painful losses of past volunteers. There have been times where we just couldn't get an idea to pan out (Donkey Kong Country, I'm looking at you). I've personally made some leadership decisions I now regret. Despite all the missteps, desynchronized runs and bungled performances, I'm proud of what the teams have done.

Processors are now fast enough to emulate consoles as new as the Wii using the Linux-compatible Dolphin emulator for Wii and Gamecube, and 2018's GDQ events have featured TASBot playing Gamecube games as a result. Miraculously, after I started writing this article, a new Linux SDL rerecording framework named libTAS was created by Clement Gallet, which makes it possible to TAS even complex OpenGL games directly within Linux. I'm continually amazed at the levels of perfectionism on display in new submissions at TASVideos. The vibrant community at #tasbot on Freenode IRC and bridged at http://Discord.TASBot.net as well as my own Twitch streams at http://Twitch.tv/dwangoAC has bloomed into an amazing example of awesome people with a shared vision—namely using TAS content to raise money for charitable causes. It's been a personal blessing to be a part of something greater than myself and an absolute joy that it has involved my two favorite things: video games and Linux.

Resources

• TASVideos.org
• Morimoto's Run
• TASVideos Official Site History
• Doom Done Quick
• Black MIDI
• YouTube Video of Super Mario Brothers Played on a BS2 by jaku@hax.by
• Instructables Guide for NESBot: Arduino Powered Robot Beating Super Mario Bros for the NES
• SpeedDemosArchive.com
• GamesDoneQuick.com
• TASBot.net
• Arbitrary Code Execution (ACE) glitch in SMW
• GitHub Repository: snes-pcm-streaming — Tools and Code for Streaming High-Quality PCM Audio to the SNES through the Controller Ports
• Linux-compatible Dolphin emulator for Wii and Gamecube
• libTAS, Created by Clement Gallet
• http://Discord.TASBot.net
• Author's Twitch Streams at http://Twitch.tv/dwangoAC