Joined: 10/3/2005
Posts: 1332
It's an idea I've been tinkering with. Consider that there are essentially infinite combinations of keypresses in a game like SMB, per frame, and that it's impossible to brute force with AI. (Note that we're probably dealing with computational intelligence when we're talking about a TAS-bot.) But what about a turn-based strategy game like... Shining Force, Tactics Ogre, or Front Mission? The decisions are far fewer. Move/attack/use item. So, if the bot is designed to use a few basic strategies, it might be able to simply try a whole lot of possibilities, most of which (hopefully) are not hopelessly insane. I'm still just tinkering with the idea, but I'd like to look into this more deeply after I've purchased a new computer, a few months from now. I'm planning on getting something fairly high-end, to replace my current 500mhz PIII, which can't really do much anymore. But before I get too carried away with this idea, I'd like to know a little more about what I can expect out of a new computer. What sorts of framerates do you guys get? I can barely get 60fps in most games, using Snes9x, if even that. If a modern machine is, say, 15x faster and also assuming that the AI is computationally inexpensive... that's a lot of trial and error. Any thoughts on this wacky, impractical idea?
Joined: 4/30/2006
Posts: 480
Location: the secret cow level
well, for every frame, there's 2^8 input possibilities, or 256. If you take a video that's 10 minutes long, that's 60fps * 600 sec = 36000 frames, giving you a total number of 9,216,000 different movie possibilities. If you can cull the amount of control input, say, no up+down; or if you give it instructions to watch for certain RAM values- no death, don't pick up a certain item; you could reduce that number to something more manageable.
Post subject: Re: Warbot?
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Dromiceius wrote:
Consider that there are essentially infinite combinations of keypresses in a game like SMB, per frame
There's actually a factorial amount of them (with respect to the number of pressable keys), which is far fewer than infinite. ;)
Joined: 10/3/2005
Posts: 1332
Titus Kwok wrote:
well, for every frame, there's 2^8 input possibilities, or 256. If you take a video that's 10 minutes long, that's 60fps * 600 sec = 36000 frames, giving you a total number of 9,216,000 different movie possibilities. If you can cull the amount of control input, say, no up+down; or if you give it instructions to watch for certain RAM values- no death, don't pick up a certain item; you could reduce that number to something more manageable.
That's why I'm talking about turn-based strategy. It would only be necessary to consider a handful of decisions. If a battle in Shining Force has one character and one enemy (which, granted, is unlikely) then you'd only need to consider... what? Two decisions? And of course, the purpose of the bot wouldn't be to randomly peck at the controller; the inputs would follow some sort of logic, such as reading the cpu and ram to know when and what to input. But, that's a bit technically advanced for me to even speculate about at this point.
Warp wrote:
There's actually a factorial amount of them (with respect to the number of pressable keys), which is far fewer than infinite. ;)
Har har. :D Ranting onward a little bit, I was thinking that a bot like this would probably work using a decision tree, in addition to random trial and error. The start of the battle is the "root" and decisions made for any member of the player's team is represented as a branch in the tree. So, at the start of combat, the bot gets control of the leader, who can move to X possible locations, attack, pass his turn, or use an item. Each subsequent action adds to each branch in like fashion. When some outcome is reached, the AI notes which branch was used, and what the outcome was and the time it took. Then it uses that information to weight the branch it just tried, and its sub-branches. It restarts and tries again, this time taking into account the weighting of each branch; it would make little sense to try the same course of action over and over if it always fails. Hopefully by doing that, it could narrow down the field enough to make a battle with millions of possible combinations of decisions, into something a PC could trawl through in a few hours.
Active player (328)
Joined: 2/23/2005
Posts: 786
This is an interesting idea. Many turn-based strategy games involve a lot of luck, so the warbot could also be programmed to take the enemy's turn by means of manipulation. For example, moving one of your units might make the AI do something totally different if done one frame later, causing the entire branch to be "incorrect".
Joined: 11/2/2005
Posts: 19
Titus, your math is wrong, the problem is much harder. The actual number of possible movies is (2^8)^36000, which is why it is impossible. Even if we can cut it down to 2 possibilities per frame, 2^36000 is impossible. We probably need it less than 2^20 ~ 1million to have any hope. Brute forcing is simply not an option. Even games like chess and checkers cannot be brute forced with todays technology, so it would have to a very simple game for anyone to map out the tree.
Joined: 10/3/2005
Posts: 1332
CtrlAltDestroy wrote:
This is an interesting idea. Many turn-based strategy games involve a lot of luck, so the warbot could also be programmed to take the enemy's turn by means of manipulation. For example, moving one of your units might make the AI do something totally different if done one frame later, causing the entire branch to be "incorrect".
I think you're right about that. But, in two of the four games I mentioned (Tactics Ogre and Shining Force) the RNG is impossible to manipulate by conventional means, such as waiting a few frames, or holding other buttons while pressing A. I assume that would keep the possibilities relatively low. Front Mission on the other hand, is almost as manipulable as Pokemon, IIRC. Though, adding luck wouldn't make a branch "incorrect"; it would make a separate branch. ...Or rather, infinite branches, one for each possible frame of waiting. But, I think that would be solved by having the AI read the RNG's memory address and picking the optimal frames on which to attack.
Player (198)
Joined: 12/3/2006
Posts: 151
I think your best bet would be to actually dissamble the rom and try to simulate the game. This would make programming much more easy and of course faster. If the RNG is actually manipulable on frame precision, I don't think it's possible to brute force, but you could always try different strategies until a sufficient fast one is found. Games with RNGs manipulable on a turn based precision on the other hand could actually be viable to brute force. Interesting idea I must say :).
Joined: 10/3/2005
Posts: 1332
Gunty wrote:
I think your best bet would be to actually dissamble the rom and try to simulate the game. This would make programming much more easy and of course faster.
You mean... program my AI to form strategies against the enemy AI? The thought had occurred to me, but the problem that arises is that a logical counter is not necessarily the fastest way to beat the game. Or more generally, that logic can't be trusted when there are so many possibilities. That, and disassembly is a pretty big task (not that programming an AI isn't. :D) If you look at what Mnrogar and co. have done with Final Fantasy VI disassembly, it represents a lot of work done by several people.
I wrote:
What sorts of framerates do you guys get? [in Snes9x]
This question still stands, if anyone wants to answer it and give their system specs... I doubt there's any proper way to benchmark, but a rough estimation of what I should expect would be very informative.
Player (198)
Joined: 12/3/2006
Posts: 151
I'm not sure if you understood what I meant, but the idea would be to recreate the enemy AI in your own program, so you wouldn't need to use the emulator at all. This custom AI would be faster for bruteforcing purposes since it doesn't calculate useless things like graphics, sound etc. As for the framerate in Snes9x, I usually get somewhere between 400 and 700 fps when using turbo mode without skipping frames. Edit: Using a Pentium M 1.70 GHz, 768 MB RAM, Ati Mobility Radeon 9600 with 64 MB video memory.
Emulator Coder, Former player
Joined: 10/2/2005
Posts: 563
Location: Toronto, Ontario
Not really sure if this is accurate, but SNES9x seems to indicate that I get about 59 FPS for NTSC games and around 49 for PAL. (Running a P4@3GHz w/2GB RAM & Radeon 9200SE@128MB)
Player (198)
Joined: 12/3/2006
Posts: 151
Maximus: you should try turning off the 'Automatic Frame Skip' option, that removes the cap from frame rate.
Joined: 10/3/2005
Posts: 1332
Gunty wrote:
I'm not sure if you understood what I meant, but the idea would be to recreate the enemy AI in your own program, so you wouldn't need to use the emulator at all. This custom AI would be faster for bruteforcing purposes since it doesn't calculate useless things like graphics, sound etc.
Ah. I was close. :D I think I can just edit the Snes9x source so that it won't process audio or video... which will cause desyncs, I imagine. It's still all speculation at this point, so it's worth a shot.
Maximus wrote:
Not really sure if this is accurate, but SNES9x seems to indicate that I get about 59 FPS for NTSC games and around 49 for PAL. (Running a P4@3GHz w/2GB RAM & Radeon 9200SE@128MB)
Sorry, I meant without throttle or skipping frames, as Gunty described in the above post.
Emulator Coder, Former player
Joined: 10/2/2005
Posts: 563
Location: Toronto, Ontario
Gunty wrote:
Maximus: you should try turning off the 'Automatic Frame Skip' option, that removes the cap from frame rate.
Still maxes out at 50 or 60 ... i think i'm doing something wrong ... though all of a sudden these games go retardedly fast :P EDIT: Screen overlay still says 50/50 or 60/60, though in turbo mode, only shows 03-05/50 (or 60)
Player (198)
Joined: 12/3/2006
Posts: 151
I don't think the ingame framerate counter can display higher than 60 or 50. I used fraps, using the OpenGL bilinear mode in the emulator. The reason because you get a lower framrate in turbo mode is because the emulator skips rendering a few frames, in your case around 10 I guess.
Joined: 10/3/2005
Posts: 1332
I think a reasonable way to estimate would be to set "skip rendering 0 frames in fast-forward mode" Start a movie in fast forward, and see how many frames it processes over, say, five seconds.
Editor, Active player (475)
Joined: 5/23/2006
Posts: 361
Location: Washington, United States
One thing I've been wondering is if somebody could just test a brute-force engine for a very simple game. I've always been very interested in these kind of topics, but in most cases nobody actually does anything past discussing the possibilities. I don't know much about coding for bots, but could somebody code up a brute-forcing bot for some simplistic game and run it for a day or so? At the very least we could see some results, and compare the best result with the TAS of the same game. I think it might be more interesting to do something like this rather than just talk about it. I certainly would enjoy seeing some results in addition to the speculation.
Player (198)
Joined: 12/3/2006
Posts: 151
The reason why this topic is usually kept at discussion is because it simply requires alot of time, both writing a bruteforce program and actually performing it. Most of the time it's faster to just manually find the fastest solution. Frustrating how fast the human brain can do this compared to a computer :P. If you're interested in brute force results you can find some in my Lufia II tas that recently got published. I used brute force on a few puzzles to find the fastest solution, though quite some bruteforcing results turned out to be just as fast as the ones I had found manually.
Player (198)
Joined: 12/3/2006
Posts: 151
Excuse my double post but; I have been working on something like this for the past few days. The game I chose to (partially) brute force is Lufia II (the Catfish fight) since I'm very familiar with it's AI and such. The first thing I did was building a simulator, which turned out to be able to simulate ~500000 battle rounds per second. However, now I was trying to make a program to actually test all possible actions using nested for loops, but somehow the different variables got mixed up :(. I suppose I could post the code here if I add some more comments to it, but I was wondering if someone could give me some generic advice on actually building such a program. PS: I worked in Java since that's the only language I'm (somewhat) familiar with. Edit: Here is the bruteforce method I constructed. state[] is an array containing the entire statespace for all rounds (maxim's health, catfish' health, RNG state etc). This statespace also contains the variable 'result' which contains the outcome of that particular round (0= no one died, 1= Maxim died, 2= Catfish died; no item drop, 3= Catfish died; Jewel dropped). The method state[round].action(i) perform action #i (0= defend, 1= attack, 2= dive, 3= boomerang, 4= potion) and stores the result in that same array. Anyways, when executing this method all goes well untill the third round. When Maxim defends 3 times in a row he dies, so the next action for that partical round should be tried. However, when trying the other action in round 3, Maxim's health is still at 0 meaning the statespace was not reloaded. Here's the method, but please keep in mind I'm a programming novice.
private void testallactions(int round){                 // round=1 to start at round 1

    for(int i=0;i<5;i++){                               // loop through all possible actions

        state[round]=state[round-1];                    // load last round's state
        state[round].action(i);                         // execute action #i

        command[round]=i;                               // log the executed action
        if(state[round].result==0 && round<maxround){   // no one died and max roundnumber is not reached
            testallactions(round+1);                    // test all possible actions in the next round

        }else{ 
            for(int j=1;j<=round;j++){
                System.out.print(command[j] + " ");     // print all executed actions
            }
            if(state[round].result==1){                 // maxim died
                System.out.println("Maxim died.");

            }else if(state[round].result==2){           // catfish died, no jewel
                System.out.println("Catfish died - no jewel.");

            }else if(state[round].result==3){           // catfish died, jewel dropped
                System.out.println("Catfish died - jewel dropped.");
            }
        }                                               // try next action
    }
}
Joined: 10/3/2005
Posts: 1332
I'm confused. Would using the attack command cause the enemy to do something different than if you had used a boomerang?
Player (198)
Joined: 12/3/2006
Posts: 151
In this case, yes. Attacking normally calls the RNG 21 times. Using a boomerang keeps calling the RNG until it's lesser than 46, after that 21 times and finally 30 times during the animation. I have tested the actual simulation program, and Im pretty sure it's bug free. The thing I'm having trouble with is the 'test all possible combinations' part.
Active player (286)
Joined: 3/4/2006
Posts: 341
Gunty wrote:
        state[round]=state[round-1];                    // load last round's state
If I'm reading the Java documentation correctly, this line adds another reference to the state object instead of making a new state object. Try making a copy constructor and using that instead. Of course, since I've never used Java, I may be completely wrong. Also, unless I'm mistaken, the targeting portion of boomerang's effect waits until the RNG is less than 43, not 46. P.S.: Just in case you weren't aware of this, the Catfish will never use Flash in two consecutive rounds.
Player (198)
Joined: 12/3/2006
Posts: 151
Hmm, you're right. According to this page I'm apparantly making a 'shallow copy' of the object, meaning both objects use the same fields (not sure if this is the right terminology). I'm sure I can figure this out now. Also, you're right about the boomerang targetting behaviour and I did not know the Catfish couldn't cast two consecutive flashes. Thanks a bunch (again!). Edit: Well this is neat. I was able to search through the first 5000'th sets of Random Numbers in less than a minute and it's actually possible to beat the Catfish within 4 rounds and getting the item drop. Unfortunately the first time this can happen is at the 1045'th Random Number set, while you will typically encounter the Catfish near the 200'th Random Number set. A 5 round victory on the other hand is possible at the 184'th and 242'th set of Random Number, so these might actually be possible (I have a 6 round victory in my current speedrun).
Joined: 10/3/2005
Posts: 1332
Gunty wrote:
The first thing I did was building a simulator, which turned out to be able to simulate ~500000 battle rounds per second.
Could you post the code for that? I'd like to see how it works.
Player (198)
Joined: 12/3/2006
Posts: 151
For some weird reason the AI's method doesn't get displayed when I paste it, so I'll try making another post after this one. Anyways this is the part that simulates Maxim's action (defends, attack, dive (IP attack), boomerang, potion). Now this version does not have any IP checks for performing Dive, and I'm pretty sure the way I calculated 'defend' is wrong, but it doesn't really matter since an optimal fight would only involve boomerangs and potions anyways.
public void action(int n){

    rng.wasteRN(6);                 		// agility check (but Maxim always wins)
    int def = 2;                    		// defence modifier
    int rngwaste = 0;               		// delayed RNG calls
    
    if(n==0){                       		// defend
        def = 1;
    }else if(n==1){                 		// attack   
        int damage = (rng.callRN()/4*maxim[3]/256+maxim[3]-10/2)/2;
        rng.wasteRN(20);
        cfhealth = cfhealth - damage;        
    }else if(n==2){                 		// dive (2x damage)
        int damage = (rng.callRN()/4*maxim[3]/256+maxim[3]-10/2);
        rng.wasteRN(20);
        cfhealth = cfhealth - damage;
    }else if(n==3){                 		// boomerang ("ATP" = 100)
        while(rng.callRN()>42){}
        int damage = (rng.callRN()/8*100/256+100-10/2)/2;
        rng.wasteRN(20);
     	rngwaste = 30;
    	cfhealth = cfhealth - damage;
    }else if(n==4){                 // potion   ("ATP" = 30)
        int heal = rng.callRN()*11/256*30/256+30;
        rng.wasteRN(20);
        maxim[0] = maxim[0] + heal;
        if(maxim[0]>maxim[1]){maxim[0] = maxim[1];}     // check if HP does not exceed max HP
    }

    if(cfhealth<1){                     	// if the catfish died:
        if(rng.callRN()<64>63 && a<128){          // secundary item drop check
                result = 3;             	// item drop checks succeeded
            }else{
                result = 2;             	// item drop checks failed
            }
        }
    }else{                              	// if the catfish lives:
        if(rngwaste!=0){                	// call the RNG during spell animation (after item drop checks)
            rng.wasteRN(rngwaste); 
            rngwaste=0;
        }
        AI(def);                       		// Catfish' turn
        if(maxim[0]<1){
            result = 1;
        }
    }
}
Edit: fixed copy/paste error