Submission #4648: Lord_Tom's A2600 River Raid in 1:22:47.90

River Raid is a popular early vertical shooter where you pilot a plane down The River Of No Return. Key to its simple but addictive gameplay is blowing up everything you can while trying to grab enough fuel to keep going. The river's terrain is continuously generated via RNG, so it never repeats, though difficulty maxes out after the 48th bridge.

The goal of the game is to get 1,000,000 points, a feat which in the 33 years since its publication has likely been managed by only a handful of realtime gamers. My previous River Raid movie scored only 100,000 points in completing the first 56 bridge sections. This submission gets the full million with the destruction of 556 bridges, thereby completing the game.

As this run was started in 2013, I used BizHawk 1.5.3 and it will not synch with modern versions.

The goal is shortest input to score 1,000,000 points. Death is abused, enemy movements are manipulated.

Most input was generated by writing essentially a Java port of the game which simulates most aspects of the game's logic and uses a bot strategy to solve it and spit out a BizHawk movie (technical details at bottom, for those interested). Looks like BizHawk didn't like when I attempted to enter a re-record total of approx 1.3 trillion, but that is my estimate of the number of frames simulated making this...give or take several hundred billion. :)

Yeah, so I feel certain that not many people really want to watch a game as simple as River Raid for 80 minutes, but we've got that vault thingy now right?! I wanted to make this mainly because of the technical challenge of botting most of a game by an outside-of-emulator port and because AFAIK no one has ever published a start-to-finish video of the game.

In terms of game strategy, the main elements from the 100k movie are all there. Optimization is based on maximizing points scored per frame, while minimizing any slowdowns needed for sufficient fuel. Enemy movements are controlled by how far along the river the player is every 16th frame, so it's simply a matter of slowing down (or not) at key points.

The one new piece this run introduces is death abuse. It is not actually possible to beat River Raid in a single life; there is a span from sections 2xx-2xx without any fuel that would require more than a full tank to traverse at top speed. So some sort of death strategy is needed.

Dying in River Raid slows forward progress by between 136 (if bridge is blown up just as it becomes visible at the top of the screen) and 206 (if plane crashes into bridge) frames. Because bridges are worth by far the most points (500), it is often best to end a life just as a bridge is killed and the plane is about to run out of fuel. Because you get points for enemies that you kill by crashing into, the best death often dying by crashing into something shortly after the bridge blows up. If there's enough fuel and there are a lot of high-point helicopters and jets around the bridge it's sometimes profitable to travel a bit beyond the bridge and clean them up before dying.

The full tank of fuel that comes with each new life is equivalent to 128 frames of refueling. It's generally worth it to lose 136+ frames for this much fuel rather than slow down over fuel depots to milk them. (A single extra frame of refueling can be squeezed from a depot losing only 1 frame of time, but due to slow acceleration/deceleration the cost of additional frames rises rapidly.) Also, not planning the routes to be extremely "tight" on fuel allows more flexibility to take slowdowns to kill extra enemies without running out of fuel. Exceptions to this rule occur when stretching the available fuel at one point will allow the plane to reach a fuel-rich section, thereby extending the length of a life by 2+ bridge sections.

The vast majority of the input after 99,090 points (achieved by manual modification to the published 100,000 point run) was entirely bot-generated.

Otherwise, there were about 5 locations where, on careful viewing, I noted the bot could have killed something but didn't. In each case, I made minor adjustments to score the extra kill: 1 reachable-but-out-of-the-way helicopter the bot missed for some reason, ~4 cases where the bot didn't kill a fuel depot to meet a fueling target that was set a little higher than really necessary.

The above manual optimizations conveniently resulted in an endgame where 1,000,020 points could be achieved by killed a bridge (500 points) on the earliest possible frame. This is good because it means there wouldn't be any benefit to going back and trying to kill more enemies worth less than 480 points (i.e. 16 ships, 8 helicopters, 6 fuel or 5 jets).

Improvement could plausibly come from achieving the current set of kills with less slowdown. This is complicated by the need to optimize enemy movements, which often imposes frame rules of 16, 32 or more frames to lure helicopters and ships into position.

The other possible improvement would be to try to improve fuel management to win with fewer deaths. I worked hard to find a route that optimally balances fuel procurement with scoring. The decision making is quite complex, however, with uncertainties relating to enemy movements, so it's possible a better solution exists.

The last few enemies before 1,000,000 points is reached were hand-optimized to end input on the earliest possible frame. The final life is somewhat unusual in that fuel is almost perversely plentiful. As a result, the initial bot run ended with about a quarter tank of fuel despite not having to sacrifice frames to get more. I considered manually reducing the fuel collected to win the game on the last drop of fuel, similar to how the 100,000 point run ended. However, I felt that ending with plenty of fuel and without any nearby enemies/terrain serves to emphasize the game author's seemingly bizarre decision to have the plane explode when you win the game. Atari 2600 fireworks, I suppose.

Making the 100k movie took me about an hour for each bridge section completed. Multiplying that by 10 didn't seem doable in this lifetime so I thought about writing an AI to solve the game. Simple as the gameplay is, developing an algorithm to optimally travel the river, select targets to hit or pass, all the while maintaining fuel was, however, far from simple.

A bot approach seemed technically simple and feasible -- I'd written simple Lua bots for various parts of other games with good results. However, circa 2013 my laptop would only run River Raid on Biz Hawk 1.5.3 at about 150% realtime speed (my present laptop is a bit better at about 400%).

To get around this, I implemented the logic of River Raid in a standalone Java program and wrote a bot against that. This was a very involved but interesting project, from trying to understand the source code, creating and publishing a complete map of River Raid, correctly extracting the game's data and replicating its behavior precisely enough to synch an 80 minute TAS.

I wrote Lua scripts to go through the first 1,000 bridge sections with the plane invulnerable, taking screenshots. This seemed easier and less error-prone than trying to replicate the rng-based assembly logic by which the real game generates terrain/enemies. A Java program would then analyze the screenshots, dumping terrain features and enemy positions into data files which the bot uses as input. A second routine assembled the screenshots into the first-ever "complete" map of River Raid]. Having this map was invaluable in planning fuel-strategy for the bot.

After many, many tweaks, I got the game engine to a state where it could synch my 100k point run, and got to work designing my bot. Extending the run out to 1,000,000 points revealed many other minor disconnects between my engine and the emulated game. I was able to resolve most of these, though two issues (rarely a helicopter's rotors will flicker out of synch in a way that affects collision detection; rarely a missile will travel more slowly than expected) sometimes required me to tweak the input file to synch with both engine and emulator.

The bot underwent several generations as I tried to make it approximate my human TASing skills using both reasonable CPU time and memory. The end solution uses a "Route Criteria" file where I specify minimum fuel the plane must have at various points in the game (typically after a fuel depot), as well as a scoring system to compare possible routes that weights score, fuel and progress down the river to various degrees.

Where to take each death is based on the bridge section at which it stops becoming profitable to squeeze extra fuel from the available depots. Once a single path kills the target bridge and dies, the bot starts a timer -- other paths have 240 frames to do the same. Once that timer expires, the path with the highest points-per-frame is chosen as the winner (this is different from the frame-by-frame scoring scheme, as we no longer care about fuel or river progression), and that single path starts the next life.

Scoring the last life is slightly different, as we only care about ending input on the earliest frame that will reach 1,000,000 points -- getting to 1,000,490 10 frames later has a higher points-per-frame but would be an inferior movie for this goal.

To keep the number of possible paths reasonable did require some sacrifies: the bot will only try to change input every other frame, and will only change acceleration/deceleration every 8th frame. In general, the effect of these design constraints is minimal.

To get the bot to run quickly, I used a Java heap size of 2 GB and used the Java concurrency framework to make use of all of my laptop's CPU cores. The final bot simulates about 1 million possible paths for each frame, keeping the best 150,000. Storing 300,000 frames of input for each of 1 million paths would require far more than 2GB of memory so every 100 frames the input for the current set of paths is written to disk. A chain of id's is tracked for each path to allow it to be reconstructed later from these files.

I'd estimate I simulated the game in its entirety about 5 times, so I put the re-record count at 5 million per frame beyond the first 99,090 points I TAS'd manually, or 1.3 trillion. After a lot of time optimizing the bot's performance, it was able to average over 1.6 million simulated frames per second, or about 26,667 times faster than realtime and 6,000 times faster than Biz Hawk.

One final aspect of gameplay the bot optimizes is "twitchiness." For each set of states that otherwise score equally, the bot keeps the one which has made the fewest number of turns. The result is, to me, a very "smooth" bot player with gameplay that looks more or less indistinguishable from my manual TAS.

Noxxa: Judging.

Noxxa: It's interesting how the game has a defined end point at such a high score. It means that maxing out the score here does clearly qualify as game completion, unlike many other games of its nature that just go on infinitely. The action is nice and consistent, but not very varied, and the run is simply way too long for what it is. Accepting for the Vault, and since this run's goal of getting 1 million points also supersedes the goal of 100,000 points, accepting to obsolete the 100,000 point run.

fsvgm777: Processing.