Super Mario RPG's Beetle Mania minigame. 99,999,999 points in 45:35.
Game objectives
- Emulator used: snes9x 1.43 v17 svn123
- Starts from SRAM
- Aims for 99,999,999 points in the fastest time
- Almost entirely botted
- Manipulates the bajeezus out of luck.
- Is still really, really boring.
Note: So as not to bore the viewer with a playthrough of one of the greatest RPGs of all time, I've started this game from an SRAM state.
DarkKobold: This was a really difficult decision - as it is a 2 hour game played entirely by a bot... Well, a well-written bot.(Rampage A Button Bot, anyone?). Sadly, the game choice is just so plainly and pitifully bad. Once you see the first 3 crooks get arrested, there isn't anything to be seen for 1 hour and 55 minutes more. Awesome achievement, but a horrid result. Even the people who voted yes said they were bored silly. Rejecting for horrid game choice, but keep up the good work with amazing bots.
Well, DarkKobold, I'm here to say, "Lol!"
Oh no, not again, Bobo! Why are you doing this???
For the lulz.
No, seriously, what's up with these runs?
What? My previous answer wasn't good enough?
I don't have any specific answer in mind. Part of the reason why I made this run is because it interests me, especially as an exercise in botting, part of the reason is because I have a lot of experience with Beetle Mania on the console, and part of it is just because I want you all to have a good laugh. Interesting games tend to be nearly impossible to bot, so the boring, monotonous ones end up getting submitted.
So is this a joke submission or not?
Why does it need to fall into one bin or the other? It's a silly run, so that's why I'm submitting it on April 1st, but one of the points I tried to make with Carmen Sandiego and this run is that stupid runs can actually have very high underlying quality. If you like this run for its botting, that's awesome. If you like it because it completes a monotonous and inconsequential minigame in a popular game, that's great too. If you don't like it, vote no-- I won't protest. I'll repeat what I said about my Carmen Sandiego run: if this run starts an argument, then it has totally and abysmally failed to do its task. Just enjoy it for what it is or vote no and move on. If this run is rejected, I'll get by.
I want this run to make people think about-- but not challenge-- the submission criteria. Make sense?
About the Minigame
Beetle Mania is a minigame in the brilliant jointly-produced Square/Nintendo game Super Mario RPG. It can be purchased for 500 coins from the young toad hanging out at the Mushroom Kingdom inn after you have defeated Yaridovich. In the game, you play as a beetle and must dodge dozens of explosive shells. What is likely the most effective strategy (and the one implemented in this TAS) is to wait until the screen is largely filled with shells before firing into them and attempting to set off a large chain reaction. The total number of points you receive varies roughly exponentially with the number of shells you destroy with a single shot.
I have maxed out the score in Beetle Mania on the console. I recall that it took about 6 hours. Maybe my strategy was suboptimal, because this is an RTA by was0x [dead link removed] that completes it in just 2 hours, 20 minutes. (If you like Forest Maze music and the green SMW background, that's the video for you.)
The Nuts and Bolts of the Minigame
The above explanation suffices for a basic overview, but there are a lot of little intricacies to know about this deceptively complex game.
- Shell bouncing and detonation: Shells spawn at the top of the screen and bounce off the bottom of the screen. The beetle is constrained to move only along the bottom. After each bounce, the shell loses some of its "energy" (in the physical sense) and so reaches a shorter height. This can be problematic for the beetle because if a shell is bouncing along the bottom of the screen, it becomes effectively unavoidable. Once its energy is nearly depleted, the shell explodes.
- Shell explosion: The beetle can shoot yellow stars to destroy shells, but when they explode, the shells also emit their own orange stars which can set off other shells. Four stars are spewed in seemingly random directions by each destroyed shell. The beetle can be stunned by these stars, but this effect is disregarded as inconsequential by the bot.
- Scoring: The first shell destroyed (whether by the beetle or by self-destruction) is worth one point. Additional shells killed directly by stars from this shell are worth two points. Shells destroyed by those shells are worth four points, and so on. Each shell is worth twice as many points as the shell that destroyed it, up to 9,999 points, upon which the shells are all worth that same amount. This is a very important property! If the shells are too sparse, a chain reaction can't be sustained. On the other hand, if the shells are too densely packed, each shell will destroy many others, wasting many points. Ideally, the shells should be just numerous enough to sustain a lengthy chain reaction with each shell destroying exactly one other shell. The ideal case can never fully be reached, but as you will see, this bot comes close many times. By exhaustively testing the opportunities to fire, the bot is able to complete the game in under 46 minutes, many times faster than ideal human play.
- Drop rate: When the game first starts, the shells come down at a moderate trickle. With time, the shells come down faster and faster until they reach a torrent. This affects the scoring rate. As the game progresses, the chain reactions become more self-sustaining, nearly reaching a critical rate beyond which it might never stop. Do not be put off by the slow initial scoring-- the speed picks up dramatically as the movie progresses.
- Damage: When the beetle is hit by a shell, it is stunned. At this point, the player must press A and B as quickly as they can to recover. Damage starts at 0 and increments by 1 every time the beetle is hit. As damage increases, it becomes harder to recover. Damage can be reduced by three points for each heart collected. The bot makes no explicit effort to collect hearts, but still ends the movie with virtually no net damage. (Fun fact: If your damage exceeds 146, it is literally impossible to recover, even by alternating rapid-fire between A and B.)
- Recovery: When the beetle is hit, a certain byte is set equal to the value of the damage byte plus four. With each press of A or B, this counter decrements by one. If the counter reaches zero, the beetle recovers. If the counter remains nonzero through about 150 frames, the beetle explodes.
- Death: When the beetle explodes after failing to recover, it releases one last shower of orange stars that can potentially start a chain reaction.
Useful RAM Addresses
- s04000: The beetle's state.
- s04004: Beetle's position.
- s04088+22*n: The nth shell's horizontal position (n=0,1,2,...).
- s0408B+22*n: The nth shell's vertical position (n=0,1,2,...).
- i030E0 (2 bytes): Timer to increase spawn rate. Every 480 frames, it attempts to decrement i030E2 by 1.
- i030E2: Spawn rate-- number of frames until the next shell drops. Whenever the word at i030E0 reaches 00 00, this value decreases by 1 to a minimum of 6. (Set to 2 for fun times!)
- i030E3: Counter to next shell. Decrements by 1 every frame until reaching 1, then spawns a shell and is set to the value in i030E2.
- i030E5: Damage (explained above).
- i030E6: Recovery (explained above).
- i030F0 (4 bytes): Score, stored as a little endian binary-coded decimal. In other words, the score 12,345,678 is stored as 0x78 0x56 0x34 0x12 in those four bytes.
- i030FB: Number of shells in play.
- i030FC: Number of stars in play.
- 1: Number of beetles in play.
The beetle and shells are confined to a playing-field with x coordinate ranging from 0 to 239. Every movement of the beetle increments or decrements its x coordinate by 2. Thus, if the beetle's position is even, it will always be even until the player presses right at coordinate 238, at which point it increases to 239. For simplicity, I confine its motion to 0 to 238.
About the Bot and the Run
The script can be found
here.
I've been tempted to run this game for a long time-- maybe even longer than Carmen Sandiego. The key thing that led me to it is the idea of
percolation theory, which I studied briefly as an undergraduate. Under the theory, one is essentially interested in how far an ideal drop of fluid can navigate down into a randomly generated "maze". By considering shells that happen to be at the bottom of the screen as obstacles to be avoided, the central task of this game (avoiding shells) can be modeled as a simple percolation problem; how long can the beetle dodge shells until it cannot avoid being hit by one?
Here is a list of the three central behaviors of the bot:
- Percolate: Already mentioned above. Under this behavior, the beetle dodges shells for as long as it possibly can.
- Fire and wait: Fire one shot and don't press anything until the score ceases to increase. By implementing percolation at this stage, the beetle could continue to dodge shells, but since the score should be increasing in the meantime, there is no real reason to. (Also, I didn't check where in the RAM the stars are stored, so I have no means to dodge them.)
- Recover: If the beetle has been hit, alternate pressing A and B with each frame until the beetle has recovered.
So the basic structure of the program looks something like this:
- Save the state (state1). Run the game for 20 seconds with invincibility turned on to construct a map of when the shells will hit the bottom of the screen.
- Find every accessible part of this map, then start from the farthest point and work backwards until the beetle's initial position is reached. This is where the percolation occurs.
- Load state1.
- Save a new state (state2). Fire a shot and frame advance (again, with invincibility) until the score doesn't increase. Calculate the rate at which the score increased in points per frame. If this is the best rate calculated so far, store it along with the frame at which it was found. Rates vary wildly at this stage in the program from hundredths of points per frame to several hundred.
- Load state2. Move the beetle according to the percolation map constructed in (2) and advance one frame.
- Execute steps (4) and (5) until the end of the percolation map is reached.
- Now load state1 again and percolate until the best frame to shoot is reached. Fire this shot and wait until the score ceases to increase. Recover as necessary.
- Return to step (1) and execute all steps until 99,999,999 points are reached.
If you would like to see the percolation in action, simply uncomment the line in the script that says
--showpercolation(dodge,cango,x)
White is shells, magenta is accessible territory, and blue is the suggested path. You will need to press pause/break to advance the script and emulation past the graphic displayed. I've included a sample of its output below, for the lazy:
I put Toadstool in the middle slot of the party to change the background to clouds, which I like more than the Super Mario World-inspired background (too green for my tastes). I also saved in Bandit's Way for its music. I had considered Forest Maze's music for its popularity, but decided it was too cliche and not appropriate for the minigame. I also considered the Midas Way theme, but Bandit's Way won out for most appropriate music.
The run was entirely botted except for navigating the title screen and menus. I hope you trust me when I say I could have botted those parts as well, but I was just a little bit lazy. As such, I don't think it's a stretch to say the run was entirely botted (the meaningful parts, anyway). If anyone really wants me to, I can add a few lines of code to make it entirely botted, but I hardly think it's worth it.
Short timeline of the bot's inception and completion:
- Spring, 2007-- I took a class in computational methods in physics. My group's project happened to be on percolation theory. I contributed almost nothing and still got a B in the class...
- Around 2009-- I somehow connected the percolation theory I learned to the idea of botting Beetle Mania. I was new to TASing and the project seemed too ambitious, so I shelved it.
- June 20, 2011-- After about a week of work, I complete my first bot that can run an entire game, Where in Time is Carmen Sandiego?. Much lulz are had.
- November 5-- Finding a short break in schoolwork, I spend the evening working on the percolation algorithm in Beetle Mania. After just a few hours' work, I have a working script that can dodge shells like a pro.
- November 6-- I complete my script and begin running it that evening.
- November 7-- 16 hours after starting it, my run is finished.
- April 1, 2012-- Hi, everybody!
Run Statistics
Note: My statistics script picked up a few instances where the number of points per shell exceeded 10,000. Since this is absurd, I've omitted those combos. (I think my script occasionally counted two combos as one, so many of these statistics are approximations or need amending.)
- Number of combos: 423
- Biggest combo (points): 925,622, combo 37, frame 17262
- Biggest combo (shells destroyed): 147, combo 37, frame 17262
- Longest combo duration in frames: 729, combo 37, frame 17262
- Most points per shell: 8,170.625, combo 111, frame 44865
- Most stars on screen at one time: 60, frame 135123
Post suggestions for other statistics in the forum.
Possible Improvements
A small improvement could be made by having the last points of the run acquired by the beetle's explosion. This will save a few seconds at most. I didn't implement this because it would require changing the bot's behavior-- when the score nears 99,999,999 points, it would have to move the beetle to every possible x coordinate and see where (if anywhere) it can die the fastest while still reaching the maximum score. My current implementation is slightly suboptimal in that sense, but only for 0.1% of the run.
The only other improvement would be to search for good scoring opportunities more exhaustively. Maybe getting 50,000 points with one shot will put the beetle or shells in a bad position, forcing you to get no more than 5,000 points with the next shot. These kinds of tradeoffs are always present when you attempt to bot a highly randomized game. Since it already took 16 straight hours of intense computation to achieve the result I've submitted, I doubt it would be worthwhile to optimize the script in this sense.
It would instead be more plausible to run the exact same script with varying initial conditions. Maybe a totally different and better result occurs when the beetle is displaced a few pixels to the left or right from its default starting point. I don't care to investigate this possibility (I suspect it could save just a few minutes at most), but you might.
The bot's behavior is just slightly unusual at some points in the run. I noticed that the beetle is hit before firing a shot on two or three occasions. This shouldn't be possible and it may be as simple a problem as not setting a sufficiently large threshold for shell collisions. Nevertheless, with the massive combos it produces, I think you'll agree that the bot's performance is pretty damn near optimal for each segment.
Special Thanks
was0x-- Primarily for kindly offering his movie file for the creation of the SRAM state. Also, secondarily for creating an amazing run of an amazing game, for creating this RTA [dead link removed] (previously linked above), and for previewing this TAS.
FatRatKnight-- For assisting me in RAM searching and statistics compilation after the run's completion. We've taken on a few projects together and I remain in awe at FatRatKnight's ability to think like the games' programmers. For example:
(22:02:43) FatRatKnight: As a wild guess, perhaps i030FC is the red star counter?
(22:02:54) bobotheking: huh... I'll check on that...
(22:02:58) FatRatKnight: Well, count, anyway.
(22:03:45) bobotheking: I hate when your guesses are right...
Dacicus-- For being an all-around nice guy and for being a brief outlet for this run, back when it was made. I have a hard time keeping secrets, so I felt compelled to tell someone what I was up to.
Flygon-- Seriously, where the hell is he?
Suggested Screenshot
None off the top of my head. I would like a screenshot filled with something. Either stars and points or just shells. I'll leave it up to the viewers to suggest some good ones that catch their eye.
My God, it's full of stars:
- 65530 (with scores)
- 98416 (with scores)
- 98417 (without scores)
- 122242 (without scores)
- 122243 (with scores)
- 148800 (with scores, I rather like this one)
- 148801 (without scores)
- 149511 (with scores)
- 149512 (without scores)
DarkKobold: Again with this bobo? *sigh*. Judging.
DarkKobold: bobotheking has amazed us all in two ways. The first being his ability to write massively complex bots, that require a level of programming well beyond the abilities of 99.9% of the community. The second amazement comes from his ability to find mind-numbingly boring games to make movies out of; with the end result making paint drying look like the first run of Citizen Kane. While this run garnered great feedback, I highly doubt that any of those yes votes watched all 45 minutes in its entirety. This movie clearly gives Ambien a run for its money, and currently pharmaceutical companies are suing to prevent its publication, for fear of loss of revenue in sleep aids. In short, I'm sad to reject epic work, but I damn near fell asleep writing this rejection, just for being within proximity of this submission.
