Post subject: Robot-assisted speedruns
Editor, Active player (296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
As many people here know, I used a computer program to help me in some parts of my Rockman Movie. I programmed "BisqBot" to attempt to find the fastest ways to play some sequences of the game. It works best when the sequences are short (30 to 90 frames long) and the user has at least some understanding of what kind of input is required. This kind of approach has plenty of uses for speedrun purposes. Such robot can be used to invoke "once-in-a-lifetime" occurances in many games, for example the mountain-warp trick in Castlevania 2. Therefore I'm trying to formalize my code to make it general-purpose. Here's my current code. It's not an existing programming language, and there is no interpreter written for it yet. It's merely a plan. However, these rules imply precisely what kind of settings for BisqBot I used at some point in my run.
/* GLOBAL SETTING */
MAX_FRAMES 120

--------------------------
/* GAME MONITORING */
/* A, X, Y, PC correspond to the values of the CPU registers. */

// D57D = FrameUpd
// C5AB = RandomFunc
// BF25 = CreateDrop
// A231 = HurtFunc
// C833 = GotItem
// C219 = KillFunc
// BEEC = EnemyKill
WHEN PC = 0xBF25
    DEFINE RockmanBonus = Y  /* Y identifies the item that was generated */
WHEN PC = 0xA231
    DEFINE RockmanHurt = 1
WHEN PC = 0xC219
    DEFINE RockmanHurt = 2
WHEN PC = 0xC833
    DEFINE RockmanItem = A  /* A identifies the item that was collected */
WHEN PC = 0xBEEC
    DEFINE RockmanKill = A /* A identifies the enemy that was destroyed */

/* Bonus items in Rockman:
 * 0x3B = no item
 * 0x3c = score
 * 0x3D, 0x3E =small refills (wpn,nrj)
 * 0x3F, 0x40 = big refills (wpn,nrj)
 * 0x41 = 1up
 */

--------------------------

/* How to restart */
CLEAR RockmanBonus
CLEAR RockmanHurt
CLEAR RockmanItem
CLEAR RockmanKill

--------------------------

/* RULES, HOW TO CONTINUE AT EACH FRAME */

WHEN RockmanHurt COUNT_AT_LEAST 1
  OR RockmanItem COUNT_AT_LEAST 1
  OR RockmanBonus IS_NOT 0x3F,0x3B
    RESTART
WHEN RockmanBonus HAS 0x3F COUNT_AT_LEAST 2
  /* When two refills have been found, accept this result */
  ACCEPT
  /* Set this as a new cap (don't try to find longer sequences) */
  SET_LIMIT
  /* And go find more solutions. */
  RESTART

--------------------------

/* HOW TO CREATE INPUT */
/* These hex numbers are bitwise ORs of controller input
 * bits. 0x01 = A, 0x40 = left, 0x80 = right, 0x02 = B
 */
INPUT_TABLE 0x00 0x01
            0x40 0x41
            0x80 0x81
            0x01 0x41 0x81
            0x01 0x41 0x81
            0x01 0x41 0x81

// initialize input with zero.
INPUT 0x00
// 1:20 chance that B will be held this frame
IF_RANDOM 20 INPUT_OR 0x02
// 1:20 chance that LastInput will be changed
IF_RANDOM 20 RANDOM_ASSIGN LastInput INPUT_TABLE
// Include the LastInput in this frame
INPUT_OR LastInput
The purpose of this post is to call programming-oriented people to further refine this plan and to make it actually useful.
Post subject: Re: Robot-assisted speedruns
Emulator Coder, Skilled player (1300)
Joined: 12/21/2004
Posts: 2687
I was actually thinking about this recently... the biggest difficulty is in the game-specific information, mainly in finding the PC values and memory addresses of interest. Without a good way of finding that information or a large database of it, such a system wouldn't be very usable in general no matter how general-purpose the code is. But, besides that part of it... One thing that should be included in the scripting for continuing at each frame and for generating input is the ability to refer to some variables and do some simple calculations with them, since allowing the robot keep internal state (and modify it) opens up a lot of possibilities, perhaps allowing it to work for longer sequences given good enough rules that change depending on what happened so far. Also, something that allows the input to start out very random (a chance to push normally useless buttons or change buttons more frequently) and get less crazy (more toward what buttons you know typically need to be pressed) after more retries might yield more interesting results. Perhaps it could even decide which buttons to press less often depending on the results so far, but that might be going beyond what's easier to do simply by running multiple trials and seeing what worked best. It seems that a robot tool like this would help very much with combat in RPG runs, when there is a lot of randomness that is tedious to manipulate manually, rules for reasonable input that are very clear, and results that are often displayed directly as numbers and usually easy to track to memory values. Also, maybe this could be used to find the fastest way to beat a boss in action games. The address of the health of the boss would be easy to find, and a condition for restarting is if the boss health fails to decrease within a certain number of frames. Maybe we think we already know the fastest way to beat the boss, but it's possible the robot would discover something interesting like a glitch that kills it instantly or a way to make a weapon do more damage than it should, if there are enough options considered in the possible input and the time interval / max frames isn't too low. (And even if it just finds the fast "regular" way to beat it, there's a chance it would put on a good show anyway in the process. I found those short luck manipulation sequences fun to watch, at least.)
nesrocks
He/Him
Player (241)
Joined: 5/1/2004
Posts: 4096
Location: Rio, Brazil
A more general way of setting the "goal" that the emulator has to find is to set it as being "earliest frame that has sprite #(insert address here) loaded on the graphics palette". That would be one way of knowing that the level has ended, for example, or that the enemy died, or that you got the power up, etc.
Emulator Coder, Skilled player (1300)
Joined: 12/21/2004
Posts: 2687
FODA wrote:
A more general way of setting the "goal" that the emulator has to find is to set it as being "earliest frame that has sprite #(insert address here) loaded on the graphics palette". That would be one way of knowing that the level has ended, for example, or that the enemy died, or that you got the power up, etc.
Don't you mean, a more specific way? Not everything you might be interested in doing results in a sprite being loaded, and maybe that's not how things work at all on non-NES systems.
Post subject: Source code
Editor, Active player (296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
http://bisqwit.iki.fi/src/fceu-bisqbot-patch-v2.txt (patch of FCEU source code) BisqBot code updated. It's now separated into a separate file, bisqbot.cc, which contains the settings that can be changed per-game and per-task. It still requires the recompilation of the source code every time the subjective is changed, though.
Joined: 5/3/2004
Posts: 1203
Objective* Any thoughts of making a program that can work with multiple emulators, and can search memory and help you find the positions and values you are looking for?
adelikat
He/Him
Emulator Coder, Site Developer, Site Owner, Expert player (3599)
Joined: 11/3/2004
Posts: 4739
Location: Tennessee
dont matter how you look at it, the user will have to know the relevant ram addresses. In many cases these are already known (either from people here or searching gamefaqs, etc) How about making it so that when you run the "bot" that it requires manually entering the ram address and 2 value ranges (one for succesfull one for failed) and then how many frames to run for. Of course this method would be specifically for luck manipulation so randomly trying all combinations of button presses would be perfectly fine. To further optimize it perhaps you could toggle which buttons would be used in the random searches (for instance in DW4, select and start always have the same seed) Finding earliest frame that sprite x would appear would require a different type of code. Maybe it could evovle into different kinds of bots like luckbot, speed bot, etc? All user friendly and easily adaptable for different games.
It's hard to look this good. My TAS projects
Emulator Coder, Skilled player (1300)
Joined: 12/21/2004
Posts: 2687
adelikat wrote:
dont matter how you look at it, the user will have to know the relevant ram addresses.
Keep in mind that it's not just RAM addresses (which can often be found without too much trouble via a cheat finder), it's also the value of the program counter - sometimes (maybe even quite often) the only reliable way to tell when something happens is to know what "line" of code gets executed to make it happen, which in general probably requires disassembling and understanding the game's code. Well, for some things it might be possible to look at what gets executed when something good happens and (a few times) subtract what gets executed when it doesn't. RAM values alone can go pretty far in some cases, but Bisqbot certainly wouldn't have worked as well (or maybe at all) without any monitoring of executing CPU instructions.
Joined: 5/3/2004
Posts: 1203
dont matter how you look at it, the user will have to know the relevant ram addresses
Probably wrong. I've never done this sort of low level debugging, but I suspect people find such information by comparing snapshots of memory before and after events occur, and noticing what changes happen and when those changes occur. This process could obviously be somewhat automated by a program. (e.g. You feed the program a movie and tell it you dropped an item on frame 50, and you picked it up on frame 75. The program says, "Hey, here's a memory value that remained constant until frame 50, then changed once, and then remained constant until frame 75, when it changed back to what it was before frame 50.")
Former player
Joined: 3/13/2004
Posts: 706
Location: Elyria/Oberlin, OH
Wow, interesting stuff here! I've finally started working on something again...namely, Castlevania 3. I can't think of any *big* improvements to the existing movies, but I'll be eliminating 2 Famtasia vids if I can finish this. I also want to make a Grant movie which covers the remaining levels that haven't been done yet (sunken city, etc.). The problem is, I cannot figure out how Phil and Genisto were able to get so lucky with drops. Nothing I've tried has worked; could this bot possibly help out with that? I might think about doing the original CV as well if this plan does indeed work out. Sure, aside from Rockman 2, these are the BEST Famtasia movies around...but they're still Famtasia movies. Thanks, Josh.
but then you take my 75 perchance chance of winning, if we was to go one-on-one, and then add 66 and two-thirds ch...percents...i got a 141 and two-thirds chance of winning at sacrifice
Editor, Active player (296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
I tried to pit BisqBot against Gutsman, but besides the fact that he had very poor success (he only managed to kill Gutsman five times in the 8 hours that I let him run), the instructions he left for me didn't work :D http://bisqwit.iki.fi/src/bisqbot-gutsman.zip is the source code (not standalone, replaces files in the earlier patch) if someone wants to take a look. BisqBot still seems to be quite useful in optimizing weapon refill drops and the Wily3 boss battle (bubble machines).
Emulator Coder, Skilled player (1300)
Joined: 12/21/2004
Posts: 2687
The instructions didn't work, as in, there's a bug somewhere so it didn't save the same input it used to play with? From the code, it looks like the problem that's making it so slow is that you wait until a MAX_FRAMES for the entire battle before deciding that an attempt has failed. It would be a lot faster if BisqBotTick returns BisqBotRestart whenever it has been more than 1.5 times the invulnerability time of the boss since the last time the boss was hit (maybe with some extra leeway for the first hit). And, even much better would be to have BisqBot optimize each hit individually, and only roll back all the way if it can't find any input that works at all for one of the later hits (or if it succeeds in killing the boss and wants to try again). That's what I had in mind when suggesting to try it in boss battles, that the segmented nature of the battle be taken advantage of to speed up the search. (I'm talking about boss battle optimizations in general so maybe I'm overlooking something specific to Gutsman here...) I have no idea if the input generation function is reasonable but that is also something that can likely be made smarter. (Also, I think the code would be clearer if you replaced numbers like 0x81 with INPUT_LEFT | INPUT_UP or whatever).
Editor, Active player (296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
nitsuja wrote:
The instructions didn't work, as in, there's a bug somewhere so it didn't save the same input it used to play with?
Exactly. Somehow, the instructions had a desync :P > From the code, it looks like the problem that's making it so slow is that you wait until a MAX_FRAMES for the entire battle before deciding that an attempt has failed. That's only half the truth. The inner layer is in functions whose names start with BisqBot, and the outer layer is in functions whose names start with BotFront. The BotFront functions also have this "Cap" feature, which limits the maximum number of frames to try, to the fastest time found so far. > It would be a lot faster if BisqBotTick returns BisqBotRestart whenever it has been more than 1.5 times the invulnerability time of the boss since the last time the boss was hit In fact, because I kind of handcoded/hardcoded the pause trick mechanism to the code, such situation is impossible. The line UnPause = FrameNo + 7+rand()%6; is responsible for unpausing in a timely manner. You're right though, such test wouldn't hurt. However, most of the time BisqBot spent was spent in restarting over and over again because he got hurt, over and over again. > And, even much better would be to have BisqBot optimize each hit individually, and only roll back all the way if it can't find any input that works at all for one of the later hits (or if it succeeds in killing the boss and wants to try again). Yes, that would be awesome, and it would open a door for a full-featured Super Mario Bros optimizer. I haven't got that far yet. > Also, I think the code would be clearer if you replaced numbers like 0x81 with INPUT_LEFT | INPUT_UP or whatever). Sure... But I've already learned to read those numbers, and they're fast to type :P    But you're absolutely right.
adelikat
He/Him
Emulator Coder, Site Developer, Site Owner, Expert player (3599)
Joined: 11/3/2004
Posts: 4739
Location: Tennessee
nitsuja wrote:
much better would be to have BisqBot optimize each hit individually, and only roll back all the way if it can't find any input that works at all for one of the later hits (or if it succeeds in killing the boss and wants to try again). That's what I had in mind when suggesting to try it in boss battles, that the segmented nature of the battle be taken advantage of to speed up the search. (I'm talking about boss battle optimizations in general so maybe I'm overlooking something specific to Gutsman here...)
for bigger events, the only potential problem with this method is that is would eliminate the possibilty of skipping the "goal" entirely. for instance if you were to try to make this play the wily stage of mm1 and one of the goals was to get to cutman as soon as possible it would never "discover" how to bypass the boss entirely.
It's hard to look this good. My TAS projects
Emulator Coder, Skilled player (1300)
Joined: 12/21/2004
Posts: 2687
adelikat wrote:
for bigger events, the only potential problem with this method is that is would eliminate the possibilty of skipping the "goal" entirely. for instance if you were to try to make this play the wily stage of mm1 and one of the goals was to get to cutman as soon as possible it would never "discover" how to bypass the boss entirely.
It could find it if the logic was inclusive enough. For instance, checking if you're at or beyond the boss room instead of only checking if you're at it. If it has to go too far out of the way to bypass it, then it wouldn't find it due to the time constraints, but without those time constraints or specific guidance, it would take much too long anyway. This will still be something that has to be limited to relatively short encounters, unless you can come up with really good rules for dealing with longer things (which even for Super Mario Bros would be quite difficult, I think). Here's another idea: Something that takes in a goal and a set of input that reaches the goal, and attempts to modify that input to reach the same (or better, depending on how you define it) goal state in fewer frames by removing or substituting frames of input and checking that the goal is still met after each step. This could be used for taking input that another bot has generated and either removing unnecessary frames or verifying that there aren't any clearly unnecessary frames. Or maybe taking a very short segment of a run and seeing how precise the playing is.
Joined: 10/29/2005
Posts: 31
I wonder if Generic Algorithms would be of any use here? Although calculating the fitness value for just *one* genotype could be quite expensive.
Joined: 8/1/2004
Posts: 143
Location: Colorado
This kind of discussion makes me wish I had taken those AI programming courses in college.
Joined: 6/4/2005
Posts: 130
Location: Ontario, Canada
You guys are beautiful. I wish I could really grasp this, I understand it's uses are gorgeous.
Editor, Active player (296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Yumiko wrote:
I wonder if Generic Algorithms would be of any use here? Although calculating the fitness value for just *one* genotype could be quite expensive.
You probably mean genetic, not generic. (For the record: I later made the same typo in this post…) I've been thinking about it, but there isn't any "learning", or room for learning, in the current system. I don't see how it could work... Edit: What I mean is that it doesn't help to use a genetic algorithm to optimize the parameters of the current 60-frame sequence, because the next 60-frame sequence might already need different parameters. The reusability is the key. But then again, perhaps someone who actually has studied those algorithms would know better than I. And the reason why the entire game can't be fed into the genetic algorithm is that currently, BisqBot is stupid. It does not have any understanding of the game. It literally bangs its head into wall 1000 times until it accidentally finds the hole where its head will go through. It knows if Mario gets hurt, but it has no idea why it happens. It will just try again, a new random try. Such algorithm can only be used for small lengths of the game. Otherwise the chances of actually accomplishing something diminish to nonexistence.
Joined: 10/29/2005
Posts: 31
You probably mean genetic, not generic.
Omg, what an embarassing typo! Yes, I meant "genetic algorithm". T_T
I've been thinking about it, but there isn't any "learning", or room for learning, in the current system. I don't see how it could work...
My idea is, if you're trying to use a GA to optimize how the game is played for a 10-second stretch in a 30fps game (for example), then there's 300 frames to be played. With each frame, the direction pad can be in 1 of 8 directions (3 bits), the A button is either on or off (1 bit) and the B button is either on or off (1 bit). So a complete genotype for playing 10 seconds would be 1500 bits (187.5 bytes). In practice, the space of possible solutions could be shortened by eliminating redundant ones. For example, in some games you can't change your trajectory while jumping, so if you just jumped, then for X frames after the jump, the direction pad input is meaningless. Applying heuristics like this to weed out redundant and obviously-bad solutions significantly reduces the amount of work that the GA has to do. The genetic algorithm would initialize a random population of 1500-bit strings. Then it would play through each one and evaluate how well it did. Then it "kills off" the bad ones, reproduces new ones using crossover/mutation, etc. and starts the cycle again until some time limit is reached, or a solution that performed above a certain threshold is found. The theory is that if you take a good solution and change it around, you have a better chance of getting a better solution than if you picked something at random. (This probably wouldn't work if you're trying to manipulate luck since the outcome is so random, but for doing something more normal it could.)
Editor, Active player (296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Yumiko, your idea sounds certainly worth of testing. I'll see when I can try it in SMB :) Of course, it will only work for situations where there is a scalar method of evaluating the success, and the better with more precision. I don't believe it would be very successful with the luck manipulation in Rockman, for example: there the goal is to accomplish a very unlikely event (it either happens or doesn't happen) in least possible time. You can't find a faster way by refining an existing method. You just have to try until you find a new one.
Former player
Joined: 3/30/2004
Posts: 1354
Location: Heather's imagination
I think it should work by mutation only. Crossover I think would not work because what is a good second half for one individual would not be a good second half for pretty much any other invidivual inless their respective first halves are also identical. But simple mutation would work, just take a very long time.
someone is out there who will like you. take off your mask so they can find you faster. I support the new Nekketsu Kouha Kunio-kun.
Emulator Coder, Skilled player (1300)
Joined: 12/21/2004
Posts: 2687
Mutation would probably get better results if duplicating or removing a frame of input were possible things it could do in addition to simply changing the input of existing frames, because often that's the only thing that can be done to improve a sequence of input, and the likelihood of doing one of those things by randomly flipping bits can be very low. (Removing could duplicate the last frame to keep the input stream the same length, if that is necessary.) Also, crossover might work if something very smart is done about choosing how to combine the two, but I'm not sure what that would be or if it would be worth doing.