State Tree-based AI method

[RicePigeon]

So after looking at various AI tutorial and code, I've noticed a major flaw in almost all of them that remains unaddressed.

 

For anyone who knows Mugen code, you should know that Mugen processes states in a top-down fashion. What this essentially means is that for each state controller in a character's state, for every tick that character is in that state, Mugen will process each and every state controller in order. Take for example the following code snippet;

 

[state 200, CS]

type = Changestate

trigger1 = time >= 20

value = 0

ctrl = 1

 

[state 200, VA]

type = varadd

trigger1 = 1

var(19)=1

 

In this case, the Changestate controller is always processed before the Varadd controller, even if the Changestate controller doesn't actually change the character's state. Therefore, once the character reaches time 20 in state number 200, assuming that var(19) is initiated to 0 at the beginning of the state, Var(19) will be set to 19 by the time the character exits state 200 (the Varadd controller will never activate at time = 20 since the character will have already left the state by then. Note that there exists a bug in WinMugen where the Varadd controller will still be processed at time=20, even though the character will have already left the state by then.).

 

This processing order applies to all states, including the negative states -1, -2, and -3. Now let's take a look at an AI code snippet with this in mind.

 

[state -1, Shoryuken]

type = changestate

trigger1 = AILevel > 0

trigger1 = statetype != A

trigger1 = random<=500

trigger1 = p2bodydist x <= 40

value = 1100

 

[state -1, Hard Punch]

type = changestate

trigger1 = AILevel > 0

trigger1 = statetype != A

trigger1 = random<=500

trigger1 = p2bodydist x <= 40

value = 220

 

[RicePigeon]

Considering the identical conditions, we look at both controllers and see that when the conditions are right, and see that both have a 50% chance of sending the player into either state, at least thats what it looks like on the surface. Remember the top-down processing order I mentioned before? With that in mind, lets follow the code again. Lets assume the conditions are right. We see that Shoryuken has a 50% chance of occuring on the first possible tick. But what about that other 50%? That other 50%, we check for the Hard Punch, which itself has a 50% chance of occuring. This means that we have a 50% chance of using our Shoryuken, a 25% chance of the Hard Punch, or nothing at all.

If we want the AI to give the illusion of a human player, we want those odds to be roughly equal, so as to keep our opponent guessing like they would against a human player, as opposed to a predictable scripted AI. While it's impossible to make an AI that performs exactly as a human player would, we can at least remove the above problem from the equation. To do this, we need to take advantage of State Trees.

For those of you who aren't computer science geeks, a state tree is basically a graph of all states that a state machine, such as a mugen character can be in, and all possible outcomes or paths that machine can take. In our example, since we want to script our AI so as to not be so predictable, we want our AI to be able to perform several different options when conditions are right. For example, say the conditions are right for us to use an antiair attack, such as when an opponent is jumping in, we want to be able to do one of the following;

• Shoryuken
• Hard Punch
• Dash backward
• Roll forward
• Jump up

If we followed the pattern of the AI code snippet above, these five different actions would each have a split of 50% - 25% - 12.5% - 6.25% - 3.125% in that respective order. Ideally, each of these should have a 20% chance. Thats where this code comes in;

First, in your -2 state, make sure to add the following controller;
 
 

[state -2, AI Helper]
type = helper
trigger1 = AILevel > 0
trigger1 = numhelper(20010)=0
name = "AI Helper"
ID = 20010
pos = 0,0
postype = p1
stateno = 20010
ownpal = 0
facing = 1
ignorehitpause = 1

This will spawn a helper that will make all AI based decisions for us. The idea is that we are going to have the helper look at all possible conditions, look at a list of all possible states our character can go in to, randomly choose one and pass it back to the player. Now, inside our helper, we'll have the following code. We'll go over each one step by step and explain what they do.
 
 

; AI Tree Helper
[statedef 20010]
anim = 1998 ;Blank Anim

[state 20010, TURN]
type = turn
trigger1 = facing != root,facing
ignorehitpause = 1

[state 20010, BTR]
type = bindtoroot
trigger1 = 1
pos = 0,0
ignorehitpause = 1

This section contains the required Statedef for our helper state, and makes it so that the helper is always bound to the player and facing the player's direction. This way, we can simply call certain triggers without the need for redirection, such as p2dist x, pos y, and so forth.
 

[state 20010, RAND]
type = varset
trigger1 = 1
var(0) = random

Our helper's RNG. Basically, our Helper will be producing a constant stream of random numbers each tick to be used for state selection. The reason we don't simply call random in each instance is because random reinitializes itself every time it is called. If you don't understand yet, don't worry, as this will make more sense later on.
 

[state 20010, VS]
type = null;
triggerall = root,AILEVEL > 0 && var(2)=0
triggerall = <conditions>
trigger1 = floor(<number of outcomes>*var(0)/1000.0)=0
trigger1 = var(1):=<stateno of outcome #1>
trigger1 = var(2):=11-root,AILevel
trigger2 = floor(<number of outcomes>*var(0)/1000.0)=1
trigger2 = var(1):=<stateno of outcome #2>
trigger2 = var(2):=11-root,AILevel
.
.
.

This is the meat of our AI decision making:

• <conditions>: refers to the set of triggers you would normally put in your AI's state controllers, such as p2dist x, statetype !=A, and so on.
• <number of outcomes>: refers to the total number of possible outcomes you want for your set of conditions. In our above example, we have a total of 5 outcomes, so this would be set to five.
• <stateno of outcome #X>: this is the stateno for each of your possible outcomes

In this case, var(0) is the random number that we stored earlier. Var(1) stores the state number that we wish to pass back to the root. Var(2) is merely a flag for when we want our AI tree to decide which state to go to next, and dictates how long to hold that value for before we regenerate another outcome. We dont want to generate a stateno if we already have one generated. In this setup, higher AI levels generate outcomes more frequently, providing for quicker reaction times. Here is an example of this block of code in action;
 

 
 

[state 20010, VS]
; DESC: Opponent is lying down.
type = null;
triggerall = root,AILEVEL > 0 && var(2)=0
triggerall = root,movetype = I
triggerall = root,statetype != A
triggerall = enemynear(0),statetype = L
trigger1 = floor(5*var(0)/1000.0)=0
trigger1 = var(1):=1003
trigger1 = var(2):=11-root,AILevel
trigger2 = floor(5*var(0)/1000.0)=1
trigger2 = var(1):=1102
trigger2 = var(2):=11-root,AILevel
trigger3 = floor(5*var(0)/1000.0)=2
trigger3 = var(1):=1
trigger3 = var(2):=11-root,AILevel
trigger4 = floor(5*var(0)/1000.0)=3
trigger4 = var(1):=4000*ifelse(p2bodydist x>=30&&p2dist x<90,1,0)
trigger4 = var(2):=11-root,AILevel
trigger5 = floor(5*var(0)/1000.0)=4
trigger5 = var(1):=220
trigger5 = var(2):=11-root,AILevel

In this above example, we have five possible states that our AI controlled player can go into when the following conditions are true:

    player 2 is lying down
    player 1 is not attacking
    player 1 is not in the air

For each set of conditions, such as antiair, a certain distance between p1 and p2 is reached, etc, you will repeat this process for each set of states. Let us continue.
 
 

[state 20010, PVS]
type = parentvarset
trigger1 = var(2)=11-root,AILevel
trigger2 = var(2)=10-root,AILevel
var(58) = var(1)
;persistent = 0

This piece of code is what allows the helper to pass the stateno back to player 1 once the meat of the work is done.
 
 

[state 20010, VA]
type = varadd
trigger1 = var(2)>0
var(2) = -1

[state 20010, PVS]
type = parentvarset
trigger1 = var(2)<=0
var(58) = 0

This piece of code counts down Var(2), which doubles as a buffer. Once Var(2) reaches 0, we can generate another stateno for our root player. When this happens, we tell our root player that we do not currently have a state generated by setting the value to 0 (or any other sentinel value of your choosing).
 
 

[state 20010, Zeeky]
type = destroyself
trigger1 = root,AILEVEL <= 0

This destroys the helper if the player is not under the control of AI, since the helper is no longer necessary.

We're almost done. Go back to your CMD file, and under each Changestate controller where you would normally add your AI code, change each one to include the following:
 
 

[state -1, Stand Strong Attack]
type = ChangeState
value = 220
triggerall = statetype != A
triggerall = ctrl || (stateno = 100 && time > 4) || stateno = 101 || (movecontact && (stateno = 200 || stateno = 400));||stateno = 210 || stateno = 410))
; HUMAN CONTROL
trigger1 = AILevel <= 0
trigger1 = command = "z"
trigger1 = command != "holddown"
; AI CONTROL
trigger2 = AILevel > 0
trigger2 = var(58) = 220

Basically your global conditions, such as statetype, cancel ability, power requirements, etc should be moved to triggerall. Your trigger1s should be everything related to human control. For the AI control, remember Var(58), which we used to pass the stateno value back to player 1? This tells the player to change to that state ONLY when Var(58) is the same stateno value as the one in the controller here. In this case, this tells player 1 to only change to state 220 if the AI helper tells us to. You would repeat this for every single changestate in your CMD file.

[Алексей]

Rice, this is awesome. Very well written and informative. I hadn't thought about the impact that state machines have on AI like this. My AI usually is consolidated to one trigger2 per attack to keep things clean, but after reading this, I've been severely limiting my AI. That explains why they guard so much, lol. This just proves that I didn't know state machines as well as I thought I did. It's not as simple as just being procedural it seems. Excellent work. Thank you for this guide.

[Ryon]

I don't do A.I often but when I do.

 

It doesnt incorporate this.

I think im gonna implement this along with seravy's on my next character. (and read it completely later to)

[Алексей]

What bugs me is when I read stuff like this, mugen just keeps proving more and more that it's shit. Why the hell would random reinitialize itself every time you use it? That would lead to far less random results than we'd hope to believe.

[RicePigeon]

To be fair, most programming languages are like that when it comes to their own versions of the random() function. Java & C++'s equivalents behave exactly the same way, its not something that's exclusive to Mugen.

 

Also, for those wondering why I use floor(X*random/1000.0) instead of random%X, I've found that the former gives a much more even random spread than the latter, which tends to favor lower values, but I'll probably go more in-depth about that in another thread.

 

EDIT: and here is

[Galvatron]

Never was good at AI coding but you put it down in great detail Rice. :-)

..however its still very confusing to me.