AI: Towards Utility-Based AI

I started reading and watching presentations by Dave Mark on utility-based AI. It’s excellent stuff!

The gist of utility-based AI is that you make decision for which action to select based on the “fitness” of each action, which is calculated as a function of an arbitrary number of inputs (considerations). There is an important distinction between the value of an input, and its utility for a particular action. The value is objective (e.g. getting an ice-cream is not that important in life); the utility is subjective and context-specific (if I’m really really hungry, the ice-cream’s perceived value skyrockets).  A utility score is calculated from a value using response curves (linear, quadratic, logistic, etc) of the form y= f(x) , where x,y in [0,1].

I’ve already implemented my own version (heavily borrowed, slightly adjusted, developed with the help of the wonderful Desmos) of the curves so that they are as simple to use as possible. So far, there are 3 curves:

(below images link to the corresponding Desmos graphs when clicked)

Linear/Quadratic

rc_linquad.png

Logistic

rc_logistic.png

Logit

rc_logit.png

and planning to add a sine and a normal distribution and that should be it for starters. In the above graphs, m and k modify the shape of the curve while b and c translate it in x/y axes.

What doesn’t make sense with the utility AI that I’ve seen so far is the combinatorial explosion that looks like it is encouraged: e.g. for an Attack decision score, it would calculate scores for Attack(Target0) Attack(Target1) for N targets. But what happens when there are lots of targets? In one presentation, number of targets is limited to 12, which is a poor approach, although practical. But what happens if actions are parameterizable in many more ways? I don’t want to create multithreaded AI and evaluations once-per-X-seconds because it takes forever.

Problem Scenario: Spellcaster NPC with a dagger, with a sword and an axe in the inventory, able to cast Frost Ray, Fire Bolt, Acid Touch and Lightning, is surrounded by 10 enemies. A melee attack can be a Power Attack, Normal or Quick Attack. This creates (10 x 3 x 3) + (10 x 4) combinations of attack actions only! Not even considering retreat or other actions. This is way too many decisions to be evaluated just for a single unit.

What some people advocate is to use utility-based AI as part of a Behavior Tree: the Selector node. That node will run the utility calculations to select the best-scoring child node . Of course that requires a behavior tree implementation, which is something that I’m planning for later. Of course, it also complicates the implementation, as we now have 2 AI systems to worry about.

A simple alternative that I’ve been thinking is to use for starters a tiered form of utility calculations, akin to a behavior tree composed only of Selector nodes.

Tier 1: Select between high-level behaviors (e.g Attack, Retreat, SelfBuff, Idle)

Tier 2: Select among commands that satisfy that behavior (e.g. MeleeAttack, RangedAttack, HeadButt, SuperKick, TornadoStrike)

Tier 3: Execute a mini-FSM that sets up the command’s parameters and executes the command. A melee attack FSM would for example select a target, and if the target was at melee range, it would schedule the attack (and the FSM completes), or if the target is not at melee range, it would schedule a move towards the target (and the FSM, again, completes). Such small FSMs are not a big fuss to implement, and allow scriptability and fast execution. The FSM should be able to reuse whatever intermediate data have been computed by the previous tiers.

A couple notes: sometimes tier 1 could directly lead to tier 3 (e.g. there are no particular “retreat” skills, besides I guess an Expeditious Retreat spell 🙂 ). Additionally, while I mentioned FSM, there no reason why that could not be a small behavior tree, or even a class that runs a few if-then-else statements. The goal of tier 3 is the same: set the parameters and schedule a command for execution.

So that’s it for now, all talk and no action. Next time hopefully with an implementation of the above tiered system.

“AI” Part One

One of my internal, early milestones in AoT is to have an automatic simulation on the world map where 2 AI factions go about their business of expanding their empire and try to conquer the world. It’s going to be overworld only. The reason for that is to figure out what kind of resources make sense in the world, how to place adventure locations, and the general functionality and growth opportunities for cities. It’s like a simplistic AI-driven fantasy Civilization game. The overworld gameplay is turn-based. So, given the above, I need some AI fit for a turn-based game, fit for both dungeoneering, overworld movement, faction/city handling logic.

I want to evaluate a few approaches for AI (I’m not a gameplay/AI programmer by trade) so I need a testbed for this. I imagine in the end it’s going to be a hybrid approach. So, part one in AI land is … LumberWolf!

Actors:

  • Lumberjack: Chops wood and brings them to the shop. When he sees the wolf, he drops any wood being carried and runs for shelter.
  • Wolf: Wanders all time. When he sees the lumberjack, chases him; if he reaches the lumberjack, he starts biting. Stays away from the shelter.
  • Tree: Can be harvested for wood. Contains 4 wood units.
  • Wood pile: A wood unit. Carried by the lumberjack.
  • Hut: A place to drop off wood
  • Shelter: Safe space for the lumberjack

The current AI controller is implemented as simple if/then/else statements (e.g. if wolf nearby, drop wood, etc). It’s pretty dumb. It’s a mix of conditions, which are evaluated instantly, and timed entity commands, which are scheduled normally in the game turn manager and will take some time.

Writing the if/then/else statements is simple but oh my, for any non-trivial behavior the bugs come creeping in immediately, as the order/structure of conditions and actions is very brittle.

I want to evaluate the following approaches: Finite State Machines, Goal Oriented Action Planning, Utility Systems and Behavior Trees, as these look like they’re the most prominent practical ones for games.  As additional fluff, the testbed will incorporate FoV and proper movement costs (can’t go through trees)