Roguelike Intelligence – Intrinsic Information and State Machine AIs

State machine AI for more complex monsters.

Stateless AIs as described in part 1, although they make your life as an implementor fairly simple, also make your monsters fairly simple. Stateless AI’s, generally, become easy for the players to predict, and thus detract from the challenge of the game.

Using state machine AIs, you can challenge the player with more interesting monsters. State means that the decision routines of each monster have recourse to stored information which is both intrinsic (internal to the decision code for a particular monster) and mutable (changeable by the decision code in a particular monster).

We have already seen some examples of state in monsters, but these do not represent state in monster AI’s: The “typical AI” presented in article 1B used information about the monster’s level of damage to make its charge-or-flee decision each round. Similarly, the decision routine can-attack-player in the “archer AI” was presumed to check whether the monster still had arrows available. In both cases, these are extrinsic information to the monster AI. These refer to the state of the model of the physical body of the monster and its dungeon surroundings and equipment; these are things that the AI itself can’t change arbitrarily.

(Note, archers are easier when you just presume they have an infinite supply of arrows; then you don’t have to keep track of this information. Of course, then players learn to “farm” archers for an infinite number of arrows…).

Finally, such things as “morale” and “too-close-to-player” and “too-far-from-player” are considered to be extrinsic as long as the monster AI doesn’t change these values.

You can get some interesting behavior in stateless AI’s by creatively using extrinsic information. But state is fairly easy to add, and with a state machine you can create almost any degree of complex behavior in monsters.

There are two basic places to introduce state to your monster decision code: I call them “learned information” and “tactical state”. Learned information is just that: something the monster has learned in the course of its brief life and dungeon encounters. Tactical state is high-level “what was I doing” or “what is my current goal” information that is used to choose between several different stateless AI’s depending on the current plan.

As an example of learned information, consider an AI for a goblin which sets a memory variable if that goblin ever sees the player kill another goblin or stronger monster with a single attack, or sees the player kill more than four goblins in less than eight rounds. Before the goblin sees that, it will treat the player as just another @-hooman, which goblins regard as good sources of food. But after it sees that, it will regard the player as a threat to be avoided, attacked at range, trapped, or ganged up on. The goblin AI need never check this variable explicitly; instead, it just calls a routine named “observe” every round which updates information that its other routines use, and then its AI, which otherwise looks just like a stateless AI, is calling functions like “player-is-too-powerful” which refer to things that “observe” has recorded.

You can implement “player-is-too-powerful” for a stateless AI too; in that case it will probably read the character’s level, weapon damage, or kill list in order to make its assessment. But this is information the goblin shouldn’t have access to; giving its AI recourse to it seems to make the critter omniscient in some ways. Of course, this omniscience is no stranger than that of monsters who don’t have line-of-sight or any particular detection abilities bunching up on the other side of a wall trying to get closer to the player character, but the omnscient goblin presents the player no way to influence it.

What you want is for the player to learn something about cowardly monsters who attack in packs; if you kill a few of them, quickly, where all the others can see, then the others will run away or change tactics. Now knowing this, the player has a choice to make about how he wants to manage his goblin encounter. He can switch to a less-damaging weapon, pause a lot in combat, fight a running battle while giving ground, and (slowly) slaughter the entire goblin tribe without them twigging to the fact that he’s toying with them; or he can just slice a few of them in half with his artifact sword and let the rest run away.

If the goblins are omniscient in their player-is-too-powerful assessment, the player doesn’t get this tactical decision to make, and the gameplay gets one element less interesting.

As an example of tactical planning state, consider a dragon who is encountered asleep. His tactical state is “SLEEPING,” and that means that the only things he can do in a given round are “sleep” and “wake up”. Now, the instant he wakes up, his tactical state becomes “enraged” if there’s treasure missing, “hungry” or “curious” otherwise. Depending on which state he enters, he will use different decision code in subsequent rounds.

You’d write this part of the dragon AI as something like this:

       DRAGON AI (partial)

  State:  Obs: Action:          input L    input M    input H   NULL

  SLEEPING L   asleep-ai        WAKING:1              HUNGRY:1
  WAKING   C   none                        ENRAGED:1  HUNGRY:1  CURIOUS:1
  ENRAGED  C   typical-ai, p1                                   WAKING:1
  HUNGRY   C   typical-ai, p2              ENRAGED:1
  CURIOUS  A   curious-ai                  ENRAGED:1  HUNGRY:1  BORED:0.1

The inputs I’ve labeled L, M, H, and NULL mean, respectively, loud noise, missing treasure, hungry, and none of the above. Each state, except for the WAKING state, is associated with “Action:”, a stateless AI that chooses the action for monsters in that state. The WAKING state is associated with “none”, which means that, instead of running a stateless AI and performing the resulting action the system immediately checks further inputs and shifts to a different state. Finally, the column labeled Obs: is for Observation, which defines a creature’s alertness in general. The SLEEPING AI has observation L, which means it observes loud noises; most of the other states have observation C, which means they observe anything casually visible. The Curious state has observation A, which means all; it observes carefully and intentionally, as though the dragon had performed a “look” command.

Note that the typical-AI is engaged for both “enraged” and “hungry” behavior, with different sets of parameters. This provides two different sets of similar behavior, but with different details. This is where the state machine sets the information that was formerly regarded as extrinsic to the AI for the stateless AI’s.

The numbers that follow each state name in the table entries are probabilities of transition. The probabilities of transition are almost all 1, which makes it nearly deterministic. We can have more than one input true at a time; For example, a sleeping monster could wake up to both hunger and loud noise, and then would he be waking, or hungry? As matters stand, we check inputs from left to right and therefore he’ll be WAKING.

But look what happens when our critter is CURIOUS and gets no input. Next round, he has a 90% chance of being CURIOUS and a 10% chance of being BORED. So this is, actually, an NFSA.

pseudocode for operating the DFSA looks something like this, although I have simplified it by pretending I don’t have to bother with parameter lists for the stateless AI’s:

acted = 0;
while (!acted)
{
    observe(statemachine[obs][currentstate]);
    shifted = 0;
    for (inputs=FIRSTINPUT; inputs < LASTINPUT && !shifted; inputs++)
    {
       if (input_is_true(input))
       {  /* note that what's stored in the statemachine is an expression, 
             not necessarily just a number. getshiftprob substitute in 
             values from the monster's extrinsic info and solves the expr.*/
          probshift = getshiftprob 
                 (statemachine[input][currentstate].probshift);
          if random() < probshift
          {
             currentstate = statemachine[input][currentstate].state;
             shifted = 1;
          }
       }
    }
    if statemachine[action][currentstate] != NULL
    {
       do_stateless_ai(statemachine[action][currentstate]);
       acted = 1;
    }      
}

Given this code, plus a few mild complications like parameter lists for the stateless AI’s, You can make arbitrarily complex state machines simply as arrays of states versus inputs, where each state additionally has an observation power and a stateless AI to pick actions. Your NFSA’s for complex monsters can just be arrays, simple to store, handle, read from file, and so on. For each input you’ll need additionally a way to detect that input.

It’s common for roguelikes to bypass the need for a general “observe” function. For example, the dragon might have a chance to wake up, per round, if the character moves, depending on the character’s stealth. This sort of thing can be reasonably effective (meaning that fixing it doesn’t become a high priority) but always seems to wind up with flocks of weird special cases and inconsistencies.

It is more general to mediate things through the dungeon itself: When something moves, store noise information in the dungeon map with the current round number, and when something is listening, have it check the dungeon map for “recent” (ie, since its last action) noise through an observe routine. Basically, the idea is that any “observable” act should leave evidence in the dungeon map, and “observe” should pick up that evidence and notify the monsters of what they have seen, heard, or smelled. Observe will become complicated: there’s no getting around that. But it’s best, I think, to have one observe routine, or as few as you can possibly manage, because it keeps things consistent when everything that’s supposed to be related uses the same routine.

If you are an OO fan, you may choose to bypass storing information in the dungeon map itself, instead favoring explicitly sending messages representing noise or observable acts from one actor to another in the dungeon. This works if you are disciplined, but it still manages to leave a lot more room for unhandled cases than the dungeon-map-as-sensorium model – and the dungeon-map-as-sensorium model, which is better, can also be implemented in OO.

If you don’t do either of these approaches, having monsters respond to dungeon events becomes a huge mass of exception-based code with quirky holes and problems. For example, in games where the chance for a sleeping monster to wake up is based on player movement and player stealth, you can have fireballs from traps go off next to the sleeping monster’s head, or a herd of rhinoceri wearing plate barding tramp through the room, and the monster will go on snoozing peacefully. And if, in the process of making all your sleeping monsters wake-up calls a bit more reliable, you overlook other behaviors that are (or should be) noise sensitive, you will develop monsters that hear more when they’re asleep than when they’re awake. Many examples of such idiosyncratic behavior can be found in existing games.

Oh, speaking of existing games, remember what I mentioned about angband’s monsters being _mostly_ stateless? In fact they have three states. Angband’s monster AI, expressed in these terms, may look roughly like this:

State:      obs.   Action:        input-P       input-D              NULL

SLEEPING:    C    asleep-ai       ATTACKING:1   ATTACKING:1           
ATTACKING:   A    typical-ai(p1)                RETREATING:dt/maxhp
RETREATING:  A    typical-ai(p2)                BERSERKING:0.05       ATTACKING:1
BERSERKING   A    typical-ai(p1)                RETREATING:dt/(4*maxhp)

input-P means “player has been detected”.
input-D means “damaged”.
dt is damage taken;
maxhp is maximum hitpoints.

This allows angband monsters to decide to go on the attack again even while badly damaged, which the typical-AI didn’t do. These monsters start out asleep, then go on the attack when they wake up. Each round they are attacking, they have a chance to start retreating that depends on their damage taken and max hp. Once they retreat, they have a chance to start attacking again, only this time it’s berserking, with a much lower chance of retreating. They alternate between berserking and retreating for as long as they’re damaged. If one becomes undamaged, it will revert to ordinary attacking.

Observation is very rudimentary in Angband; the “observe” routine (or whatever angband uses for its functionality) checks the amount of damage the monster has taken, checks for lineofsight to the character, and, I think, that’s it. I don’t think these monsters are even aware of individual attacks, just of how badly damaged they are at that moment.

typical-ai(P1) uses a “too close to player” function that is never true and
a “too far from player” function that is never false.

typical-ai(P2) uses a “too close to player” function that is never false and
a “too far from player” function that is never true.

Now, this looks simplistic, certainly; but remember that a lot of stuff is folded into typical-ai. And if typical-ai looked simplistic, remember that ten times that amount of stuff is folded into the various behaviors and checks it calls.

Anyway, this is my general architecture for monster AI:

behaviors and functions are implemented directly in the source language.

Stateless AI’s are implemented in terms of a repertoire of interchangeable behaviors and functions. The Stateless AI serves as a “pattern” that brings these things together, but different kinds of behavior can fill in its specific elements.

and State machine AI’s are implemented in terms of stateless AI’s with parameter lists, and state transition tables. In the same way that the interchangeable behaviors and functions fit into the stateless AIs, the stateless AI’s fit, as interchangeable building blocks, into the pattern formed by the state machine.

State transition tables are implemented in terms of the above routine for doing transitions and calling stateless AI’s, and “observe”, which runs over the dungeon map looking for evidence of specific observed events and changes intrinsic information that the behaviors and functions of a stateful AI can access.

I want to make one point about the “observe” function. You can spend as much time as you like writing it. Even a very simplistic “observe” such as that in Angband is functional. But there is always and forever stuff you can add to it and more patterns it hasn’t learned. You have to pick your own point of diminishing returns here.

In the next article, before moving on to minimaxing, neural networks and genetic algorithms, I’ll talk about “reactive” intelligence; how to store information about how to act on the objects that a creature interacts with.