the robotic ruler of the river of no return

River Raid was one of the finest games produced for the Atari 2600. One of the first vertically scrolling shooters, this game was remarkably well designed. While the enemies (copters and boats and later small jets) could only threaten the player with menacing kamikaze moves upon approach, the constantly diminishing fuel supply would lead the player to recklessly hightail it down the "River of No Return" to pass over replenishing fuel depots, a tension-provoking detail most other games of the era couldn't match. And I am going to introduce you to the games indisputable conqueror.

First, a note about the game's author, Carol Shaw- the first professional female video game designer. This game is her singular masterpiece (I don't think many people really look back that fondly on "3-D Tic Tac Toe", and the 1-on-1 Pong-like action of her "Polo" tie-in game never saw the light of day...) This interview has her talking about her experience. But her peers thought she was great, designer Mike Albaugh said

I would have to include Carol Shaw, who was simply the best programmer of the 6502 and probably one of the best programmers period....in particular, [she] did the [2600] kernels, the tricky bit that actually gets the picture on the screen for a number of games that she didn't fully do the games for. She was the go-to gal for that sort of stuff.

As a guy who wrote an original Atari 2600 from scratch in assembly , I know how tricky that kernel stuff is... (and true confession, my game ended up having its kernel tweaked by genius Paul Slocum anyway.)

One of the cleverest bits of River Raid is its use of pseudorandom number generators to generate section after section of the river - this let the game pack in a consistent, huge game playing field even though the whole cartridge was only 4K bytes of ROM. The levels alternated between straight sections and split sections and went on practically forever.

Over a decade ago I got to wondering about how far the river went, and got so far as having B. Watson generate this image of the first 4 sections, guaranteed to bring a bit of nostalgia to the 80's gamer heart:

(Of course the funny thing about posting this kind of image is that River Raid scrolls from the bottom, but webpages scroll from the top...) That project to map out more of the river never went anywhere, but this AtariAge thread gets revived from time to time... and I would say, the indisputable Ruler of the River of No Return (and one of the participants in that thread) is one "Lord Tom"

For starters, here's Lord Tom's map of the first 600 river sections...

And how does Lord Tom know what the first 600 sections look like? I contacted him at AtariAge (such a damn fine resource!) and he said

To make the map, I wrote a Lua script for use in the BizHawk emulator that essentially cheated through the game with the plane offscreen somewhere, taking screen-shots of each enemy/terrain slot along the way (32 per map section). I assembled these into the big map with a simple Java app.

But that wasn't enough for Lord Tom. He's a member of the "TAS Community" - Tool Assisted Speedruns, folks who learn how to let machines help them drive through to the ending of games faster than any human ever could. They don't cheat - the actual code of the game is sacrosanct - but by abusing every input available to them they're like the crew of the Nebuchadnezzar getting ready to dive back into the Matrix, mastering the code behind the world that lets, say, Mario move like a crazy drug-fueld Ninja, or in Lord Tom's case, to build a frickin' robot to play the game better than any human (or 'bot) in history ever has. Specifically, to get the maximum possible score of 1,000,000 (or in Activision speak, !!!!!!) That looks like this:


To give that robot a script, he built a replica of River Raid in Java, one that could reproduce all the twists and turns and boats and helicopters and fuel tanks that that little cartridge's algorithm could churn out with incredible precision, and then used it to power something like the "Many Worlds Interpretation" of Quantum Physics, plotting out a millions of possible futures for each frame, then pruning and working the best 150,000 or so, until he got a damn near optimal path. (And to give you an idea of this robot's skill about this, not only does this well-nigh perfect path take an hour twenty to get to that million points, Activision would send you a patch designating you a "River Raider" if you sent in a photograph showing that you got 15,000!)

So, in his own words:

Yes, due to the technique I used for solving the game, I had to write a Java simulator, which I think ended up being something like 10,000 times faster than trying to do the bot computations through the emulator. And I only simulated the game's logic/state; I didn't actually output a display or sound, though in the grand scheme of things that would have been easy enough to do.

The solving algorithm focused heavily on fuel and (of course) score. Since fuel is consumed at the same rate regardless of speed, it's best to almost always go full throttle. There are a few terrain exceptions, and the other main exceptions are slow-downs to get extra fuel or manipulate which enemies move/don't move to make them easier to kill.

For fuel, I basically looked at the map and plotted out how far I'd get for each life (once fuel becomes rare, it's better score-wise to die for a full tank than to keep slowing down to milk depots). Then for various points along the route (e.g. section 5, 10th enemy) I'd specify a minimum fuel to have -- any solution paths with less fuel would be killed.

The only non-survivable states in the game relate to fuel, and then very limited times when e.g. you can't slow down fast enough to clear terrain, or avoid an enemy that's about to hit you.

Other than that, it was pure heuristic; 30 times a second it would simulate paths with each possible input, eliminate duplicates and deaths, and periodically score them and keep the best several thousand. To handle islands, I stipulated that a certain # of paths would always be kept alive on each side of the screen. As I recall, the algorithm would score and cull several times each section; it never really "looked ahead" at all, just periodically compared outcomes for 500,000 or so input possibilities and kept the best ones.

I think all in all, I calculate the bot simulated over 2 trillion game states to complete the game. 

You can read even more details at his TASVideos Submission Page, but I think you get the idea here.

Amazing. I've done Atari coding and even some Java-based "tool assistants" (to get photorealistic images into the long-lost site pixeltime, or to remove the scrolling credits from still backdrops) but nothing that comes ANYWHERE NEAR what Lord Tom (or Carol Shaw, for that matter) has done.