Three States and a Plan, twenty years later

What is the best enemy AI you played against? What a deep question. My answer would be F.E.A.R., a horror shooter from 2005. I don't remember most of the story details or the mechanics, but I remember the enemy AI. In 2006 Jeff Orkin gave a GDC talk about it called "Three States and a Plan", and young and impressionable me fell in love with it. If you have never seen it, read it. It is a much better use of an evening than this post.

The enemies in F.E.A.R. have 3 very interesting things: a planner, goals and a coordinator. A soldier has goals (kill the player, dodge, get to cover) and a bag of actions, each with preconditions and effects. When a goal fires, the planner searches for a chain of actions that gets the soldier to that goal. It is like pathfinding, only through actions instead of corridors. Then the enemy executes the chain through the state machine, and when the world changes (the player moved, the crate got shot to pieces) it throws the plan away and plans again.

On top of the enemies sits a squad coordinator. It looks at the situation, picks a squad behaviour (advance under cover, flank, fall back, search) and hands each soldier an order. A soldier can refuse if the situation offers a more appealing decision. The last piece is that the soldiers announce what they are doing ("I'm flanking!"), and the chatter makes the team look smart and reactive.

So I had to re-implement this idea with the coolest tools.

The coolest tool I picked up was Jev. Larithea as a game lends itself pretty well to a deterministic approach because it has no randomness: all fights happen on an 8x4 field, turn based, heroes on the left, enemies on the right, with a limited number of options available. In general terms there is a limited set of good or even perfect options. If the AI always picks them you are completely screwed and will lose (which makes you very sad!), so I can't have an overly smart AI in the story. But I could experiment with another game mode: the arena. I took the F.E.A.R. shape and the Jev decision model and rebuilt the arena enemies on them.

Zoom out and let's talk about logic. It has 3 layers, same as F.E.A.R. The pack decides together. Each enemy works out how to do its part. Everyone acts, and next turn it all gets decided again. The planner for one enemy searches every sequence of up to five turns (step, stay, wait for energy, cast) and picks the one that carries out its part soonest with the hardest hit. It is tiny: 16 cells, a handful of energy values, five turns, a few hundred states. The team plans are the squad behaviours: focus fire on one hero, split between two, hunt the nearest or the healer or the tank, or pull back out of reach and strike together next turn. And an enemy can refuse its order for exactly one reason: if it can kill a hero this turn, it takes the kill.

Jev is the coordinator. You give it a situation and a list of options, and it gives you one pick, a confidence, and a probability for every option. Once per enemy turn my code builds every team plan, works out each enemy's part, and writes the whole thing up in words. One option reads like this: "Focus fire on Maya. Elemental, Ghoul and Wraith hit Maya this turn; Husk steps back to build energy. This turn: Maya falls. Over the plan: Tara is next, reachable in 2 turns. Risk: afterwards Ghoul and Wraith stand in Tara's reach." Jev reads seven to ten of those and picks one. It answers in about a quarter of a second and costs a few thousandths of a cent per turn. If it does not answer in time, code picks from the same list by a fixed score, cause fallbacks are important.

And because Jev reads words, I can give a pack a personality in one sentence. Every pack rolls a temperament per fight per day: Relentless ("attacks every turn"), Cautious ("hates being hit"), Cunning ("the healer first, then whoever is weakest"), Brutal ("picks one hero and does not stop until that hero falls").

Sidenote: Cautious is temporarily out, cause it was driving me crazy. Chasing it all across the field made fights very, very, very long, and on a long fight everyone gets killed by the field anyway.

Now the evaluations, cause you may remember I have simulations for everything.

I ran the sim on the original mechanics (the same as in story mode). Then I ran simulations on the fallback. And then I ran simulations on Jev. This gave me a comparison to dive into and tweak the logic (mostly the wording) for Jev, with an average across all three to hold it against.

The wording was very important. For example, one sentence of temperament barely moved a decision model: Brutal and Relentless packs kept pulling back even when told "it never pulls back". The fix was to stop asking. Those two packs are simply never offered "pull back".

Or another one (totally my fault): in a fight with no healer in the party, a pack picked "hunt the healer" in 188 of 210 turns. There was no healer, so it hunted the nearest hero instead of the weakest one, turn after turn, just moving around and not attacking. Yes, the solution was easy: offer "hunt the healer" only when there is a healer.

Diogo Almeida's launch post for Jev asked early-access builders to tell TypeSafe AI where Jev works and where it falls short. So here is my report, Diogo Almeida and Sasha Sheng. It works: a quarter of a second per turn, a fraction of a cent, and a pack that reads a situation in plain words and picks sensibly. You just need to find the right words to describe the options.

So write your simulations first…

One more F.E.A.R. lesson I had to relearn in my own stack: decide once, then act. Jev and the planner run when the server accepts the turn, and the enemies' actual moves are stored with that turn. Replaying a fight replays moves, never a decision. I can rewrite the wording, retune the planner or upgrade Jev tomorrow, and no old fight changes.

All of this is going into v9.3 next week. Maybe I will add the cool banter so my enemies look smarter. Generally I release a new version every Monday, so I have time.

I am also making an itch.io build so I can get more playtesting easily.

But what a fine ride. I guess the moral is: try Jev as your enemy AI engine?