The AI Engine

By today’s standards, the Artificial Intelligence in Street Fighter 2 World Warrior isn’t very sophisticated. These days, when most people talk about AI they’re talking about machine learning. There’s not any of that in SF2. Anyone looking for some insight into how to write an AI engine for a game today will be disappointed.

Moves made by computer opponents are not made independently but are instead grouped into small scripts, written in a bytecode similar to machine language. A computer avatar has a repertoire of different scripts for each opponent they could face in the game*, and set of circumstances, such as a nearby fireball.

Instructions in the scripts can command the avatar to execute an attack (punch/kick/special/throw), walk or jump somewhere, and wait – either for a timer, or some condition such as the ability to throw another fireball.

Other instructions can directly manipulate variables in the AI state machine, test for certain conditions, and form primitive IF…END blocks. Here’s one of Ryu’s typical ‘easy’ attack routines: Throw three fireballs at you, and if you’re somehow silly enough to catch all three and get dizzy, run up to you and throw you.

ORG 0x99c88 sf2ua.bin
0x02,                   ; script header, type 2 
0x10, 0x50, 0x04, 0x00, ; throw a hi str fireball
0x00, 0x80,             ; wait until I have no fireball
0x10, 0x50, 0x04, 0x00, ; another hi str fireball
0x00, 0x80,             ; wait again
0x10, 0x50, 0x04, 0x00, ; another hi str fireball
0x92,                   ; are they dizzy?
0x04, 0x00, 0x18,       ;    walk until we're within 24 pixels  
0x00, 0x82,             ;    wait if they're still getting up
0x10, 0x84, 0x00, 0x00, ;    throw(4)
0x94,                   ; end if
0x00, 0x00, 
0x00, 0x00,             ; wait four frames
0x00, 0x00, 
0x00, 0x00, 
0x86,                   ; chain to another randomly chosen script

Apart from the header byte, the first byte of each row is the instruction byte. Instructions are grouped into avatar commands (0x0-0x7f) and control flow / variable access (0x80 – 0xff). Each of them mostly have a fixed number of parameters, for example the Attack instruction (0x10) always take three:

  1. The attack type (special moves are 0x50, 0x52, 0x54…, throws are 0x80, 0x82, 0x84…).
  2. The strength of the attack (in this case it’s a strong / fast fireball)
  3. A repetition count for attacks involving holds and multiple hits. (unused here)

 

The Wait (0x00) instruction usually takes one parameter, decoded as:

  • 0x0 – 0x7f: Wait for N frames
  • 0x80: Wait until I am able to throw a fireball
  • 0x81: Wait until opponent is within M pixels (additional second parameter)
  • 0x82: Wait until my opponent is attackable
  • 0xc0: Wait until opponent’s jump reaches height M (second param)

All of the instructions and many of the parameters are even multiples of two (there is no 0x01 instruction, for instance) so that they can be used directly against 16-bit jump tables. Low/mid/high strength translate to 0, 2 and 4, as are most internals in the game. Any odd numbers would cause a CPU bus error exception, which would result in the SF2 ROM restarting.

The AI engine has three main modes of operation:

  1. Waiting for an attack. Simple scripts are chosen at random which consist mainly of walking backwards/forwards small amounts.
  2. Actively attacking. Scripts such as the one above are selected.
  3. Reacting to an attack. Scripts suitable for countering the attack are selected. Sometimes. Depending on the AI difficulty setting the computer lets plenty of attacks through unguarded, of course.

For the first two modes, there are 8 levels of scripts, which are chosen based on how much time is left in the round. When reacting to an attack the scripts are chosen based on something called a yoke.

Each frame of animation for both avatars and projectiles contains a value for the yoke in the metadata, which the AI peeks at to select a script suitable for responding to that attack. The computer sees the yoke of your move as soon as you have input it, before the first animation frame has even displayed. As such it gets one more frame of advantage on top of your reaction time.

A question addressed in an earlier post in this blog was whether the AI “cheats”, and it certainly does. Charge moves such as blade kicks are simply executed as instructions, so they cannot fail. Guile can do a bladekick from a standing position simply because that’s what’s in the script. It’s probably possible for the AI to command special moves in the air. One instruction is available to disable collisions against the computer player for a certain number of frames. Using it, you could write a script to simply walk through an approaching fireball.

One of the (more hidden) test screens in the game performs a sanity check on the AI bytecode. It’s not immediately obvious what it’s for as it just displays “OK” and nothing else, but the disassembly reveals the developers were perhaps testing and developing the AI code on CPS machines. The error messages in the test code reveal names for some of the instructions as MOSI, KON, KYON, TIGA, TAN, GTAN and END IF, but apart from the obvious latter name I haven’t figured what they might mean.

Viewers at home can find Ryu’s AI bytecode starting at ROM address 0x9966e on sf2ua. Set a breakpoint at 0x2ad2a to stop at the main entry to the AI code. Avatar AI state variables start at 0x200 from the player struct (0x5c6 and 0x8c6 for P1/2 respectively on sf2ua).

[* WW contains no scripts for battling the four bosses since that shouldn’t happen, and in any case the formulae for each of the opponents are all the same anyway! Maybe the developers ran out of ROM space or time, but the WW computer players use the same formula no matter who they’re fighting]

Advertisements
The AI Engine

21 thoughts on “The AI Engine

  1. JORDI says:

    Realize that you are the first person that has shared how SF2 AI works behind the scenes in 25 years… Thank you very much for this tremendous post!
    AI scripting byte code… outstanding.

    Like

    1. Thanks Mark, that’s helpful! There’s a few Japanese words around the place in some of the debug screens. I had some success at googling them, (i.e: “Kage” for “Shadow”), but not with any of the AI instruction names. Arigatō

      Like

      1. Mark (not cooke) says:

        “Kon” is usually a prefix meaning “this”, or “now”, “Tiga” is usually rendered as “Chiga” (from ちが), and it means a difference (well, “Chigai” does, and “Chigau” is the verb “to differ”). I’d guess that “TIGA” might mean “ELSE”, in context.

        Liked by 1 person

  2. Have seen your posts on various sites about this, really glad to finally see some details get posted. A suggestion to avoid copyright problems: post a program that takes the ROM (with a given md5 / sha1) as input and produces a partial disassembly.

    Like

  3. Simon says:

    Hello sf2platinum,

    I’m so excited to see this blog! I’m a big fan of SF2 and I used to spend countless time on it.
    As a programmer, I really would like to know if we can change the AI level (to be more specific, make it HARDER). If possible, how can we do it? Would you mind explaining what tools are needed to improve the AI?

    You did a great job and I like it very much.

    Simon

    Like

    1. The arcade version has jumpers to select from one of 8 levels of difficulty. I’ve done most of my testing at the easiest setting, but in the next AI post I’ll take a look at the scripts of the higher difficulties.

      Like

  4. From a simple Romaji translator at http://jisho.org/search I was able to find an equivalent for all of the instructions besides GTAN

    MOSI, KON, KYON, TIGA, TAN, GTAN and END IF

    MOSI == IF

    KON == THIS

    KYON == HOPPING VAMPIRE? / ZOMBIE? ( MAYBE GOTO )

    TIAG == DIFF ?

    TAN == ORIGIN? / FAULT ?

    GTAN == couldn’t find anything

    Hope that helps you explore the code further ^_^

    Like

  5. I think this is awesome. Is there a chance to stuff on how the AI in other iterations of SF2 work in the future?

    Also, I assume you mean Flash Kick when you said Blade Kick, right?

    Like

    1. Maybe I’ll do a post detailing all this as it’s a bit much to answer in a comment, but here goes: To begin with, you need to be familiar with the machine language used in the ROM, in this case MC68000. Fortunately I already had that from my Amiga days, but when I started going through the assembly back in 2005 I knew nothing about how games were programmed, or how the CPS hardware worked beyond using tiles to display graphics. For me, I didn’t so much have all these “prerequisites” before I started, this was a learning exercise for me.

      There’s a lot of guesswork involved. You go through the assembly looking for common patters, identifying subroutines, backtracking to see where these subroutines are called, and so on, making notes all the way, replacing hex addresses with names when you figure one out.

      You can also make good use of the debugger built into MAME, setting breakpoints at places you’d like to investigate, examining contents of variables while the game is running, etc. This was invaluable at the early stages, when I was trying to figure out what a particular function was for, I’d set a breakpoint on it and play the game through, noting which circumstances caused the execution to take that path, and eventually deducing what it was for.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s