Joined: 5/23/2006
Posts: 361
Location: Washington, United States
I am somewhat interested in how BisqBot and other brute-forcing bots work. I understand that the bot has to check memory addresses and restart if certain conditions are met, but I don't quite understand how a few other things are done. How does the bot actually "play" the game, i.e. how does the bot advance the emulator/rom to be able to compare memory addresses? Related to the previous question, how does the bot restore a previous position? Through a savestate?
I might want to create my own TAS-bot sometime, so I'd greatly appreciate any responses informing me of the basics for programming one.
IIRC, BisqBot, being part of the emulator code, makes calls to frame_advance() (or whatever it's actually called in FCEU) and other functions that the emulator normally uses.
Very good idea. I thought of that myself. My problem is, however, that I only have knowledge about Visual Basic, similar things and AutoIt.
What I don't understand, though, how can a such a bot be really used? I mean the time the bot needs grows exponentially with the input length. With 100 positions checked per second and only 4 input combinations per frame needs several hours.
Joined: 4/30/2006
Posts: 480
Location: the secret cow level
We need a quantum computer that can test every possible controller input combination simultaneously.
Bisqwit needs to get on the horn and get the ball rolling on this.
The brute-force bot would need its own programming language, or something like that. It could be a language similar to C. Here's an example of what could be done for a 100 frame search, for SNES, with only a few buttons allowed instead of the whole controller:
That's not real code by the way .. I know the syntax is probably wrong and everything, it's just to give a general idea. Of course there's more to it than just that. There are conditions to validate using memory addresses and comparison values.
This could either be a programming language that the user types himself, or you could make a GUI that would allow them to do it more easily. Like ... they select what buttons to use, write how many frames to brute-force, and then some kind of list of conditions that he could choose (enter a memory address, choose between <, <=, =, >=, > and !=, and then enter a value of comparison. Of course he could add many conditions, choosing AND or OR.
Those conditions would be there only to rule out some results, so that the bot doesn't test long things if that result isn't going to be used. For example, if you REALLY don't want your character to suffer damage, then a condition would be set so that when the memory address containing the health of your character decreases, you rule out that possibility and go to the next solution.
That's how I would see it, but then that's only my personal opinion. It looks like it could be a fairly big project to do, but any TASing emulator would definitely greatly benefit from such a feature. At least I would use it.
End of babbling. Just my two cents.
EDIT: Oh and you would also need a condition to determine which of the solutions is the best. Like "when $MEMADDR$ is the highest/lowest", or something.
EDIT2: This topic should be moved in the TAS Laboratory.
Very good idea. I thought of that myself. My problem is, however, that I only have knowledge about Visual Basic, similar things and AutoIt.
What I don't understand, though, how can a such a bot be really used? I mean the time the bot needs grows exponentially with the input length. With 100 positions checked per second and only 4 input combinations per frame needs several hours.
The bot generates random inputs, that the bot's author fine-tunes, according to the best understanding of the steps needed towards achieving the goal.
For example, in Rockman 1, when the goal is to achieve a weapon refill spawning, the following knowledge is gathered:
― Moving left and right is involved, with rightwards movement preferred. There is no pattern on the durations of holding either button.
― A jump or two may be involved. When doing a jump, the A button is held for a number of frames and then released; it does not make sense to bang it randomly 10 times in a second.
― Maybe a few extra shots need to be shot. There is no knowing when is the best time to fire them, so it can be completely random. However, there should be only two extra shots at maximum.
― The enemy is located on the right, so one of the shots should be fired towards the right.
We know the proper input is more likely to look like this:
― 11*A_B, 20*A, 7*B, 6*A, 6*B_R
than like this:
― 1*A_B, 1*B_R, 1*A, 1*A_B, 1*A, 1*A_B_R, 1*B, 1*R, 1*A, 1*A_R, 1*B_R, 1*A_B_R, 1*B_R, 2*A_B_R, 1*B, 1*00, 1*B_R, 1*00, 1*R, 1*A_B, 1*R, 1*A_B_R, 1*A_R, 3*B, 2*A_B, 1*A_B_R, 1*A_R, 1*B_R, 2*B, 1*A, 1*A_B_R, 1*A, 1*00, 1*A_B_R, 1*B, 3*A, 1*A_B, 1*00, 1*A_R, 1*B, 1*R, 1*A_B_R, 1*B_R
Using this knowledge, the input generator is devised.
This reduces the number of options to search significantly, and increases the chances of finding the solution within reasonable time. However, if our understanding of the means to achieve the goal is flawed, so will the bot be, and it will not achieve the goal.
Also, the bot needs control conditions. Using again the Rockman 1 example, here are some conditions that should be set:
― There will be 50 frames of time. Anything more is too slow. When 50 frames is elapsed without achieving goal, restart.
― If Rockman falls into a pit, that is obviously a wrong solution. Falling into pit is detected by observing the X and Y coordinates of Rockman (RAM monitoring). ⇒ restart.
― If Rockman receives damage, the attempt is a failure. ⇒ restart.
― If an enemy is killed but it does not yield the right powerup, the attempt is a failure. ⇒ restart.
― If the powerup is generated in an out-of-reach location, the attempt is a failure. ⇒ restart.
And so on.
Obviously, all of this requires programming.
Couldn't there be such a tool created? Of course it required lots of programming to produce proper results but I generally think it shouldn't be so hard to create something like that.
How many restarts/positions does it check per second (on average)?
Couldn't there be such a tool created? Of course it required lots of programming to produce proper results but I generally think it shouldn't be so hard to create something like that.
By such and that, you mean what?
Yrr wrote:
How many restarts/positions does it check per second (on average)?
A brute force bot. The best would be if it would be included directly in the emulator. You could then wright an own program for a special porpuse and the emulator tries the it with the brute force method.
Well, in case you're missing the point, what I previously described was how I did with the Rockman 1 TAS. I implemented such a bot.
The source code is here: http://bisqwit.iki.fi/src/fceu-bisqbot-patch-v5.zip
However, customizing such bot is done in the C++ programming language.
I know there are plenty of TAS makers who would like to have an easy tool to produce bots like that, but as far as my cases have been concerned, it all requires programming. And I program in C++, directly into the FCEU source code. I cannot produce a tool to do that job; the different cases have been complex enough to be troublesome to think of how to do it in C++; I don't think I am capable of making a tool that enables such level of control without having to write in C++, or some other programming language.
I recall, someone implemented a similar mechanismus in snes9x, using something called "LUA", but I think it also involved having to program the rules of the bot's play.
It would be possible to add an interpreter (or jit-compiler) for some scripting language into the emulator. Of course even if this scripting language is very simplified and many tasks automated, you still have to have at least some basic skills of general programming (so that you can write programs with that script).
The advantage of such a scripting language would be that it would not be necessary to recompile the emulator each time you make a change. The disadvantage is that it would be slower (although a jit-compiling language could somewhat alleviate this problem).
A scripting language to control the emulator doesn't actually need to be very complex. It simply needs some functions to read info from the emulator (such as the current frame, RAM contents, etc) and to submit info to the emulator (keypresses, saving and loading savestates, etc), and then some basic math support (variables, mathematical operators, perhaps some mathematical functions), control structures (conditionals, loops) and data structures (dynamic arrays at least, perhaps lists and trees).
