Utility Based AI

Utility Based AI is a method of assigning scores to behaviors based on some heuristic, usually involving curves. Then algorithm analyzes those scores and chooses the most suitable behavior.

Basic concepts of Utility

Consideration

Consideration is a number representing a subset of gamestate which, from the perspective of the algorithm, is worth being considered during score calculation.

Considerations you may come up with given the necessity of evaluating AttackOpponent behavior

  • agent’s health

  • opponent’s health

  • distance between agents

  • agent’s weapon damage

  • etc.

Curve

Curve is a function which converts one value into another. It usually takes form of an analytical curve.

Evaluator

Evaluators are responsible for processing considerations and returning final score assigned to the evaluated behavior.

Selector

Selectors are responsible for selecting most suitable behavior based on scores received from evaluators.

Flow of Utility

  1. Considerations are gathered.

  2. Considerations results are passed through corresponding curves.

  3. After all curves results are calculated, they are aggregated by evaluator.

  4. When all behaviors are evaluated, one of them is chosen by a selector.

Example

Let’s say that our example situation involves two archers shooting at each other and trying to defeat his opponent.

Agent can execute one of the following behaviors

  • Attack

  • Flee

Available considerations

  • agent’s health

  • opponent’s health

  • distance between agents

All considerations' values will be in range [0, 100].

Let’s assume that Attack behavior will look into health considerations while Flee behavior should consider agent’s health and distance.

We want to implement berserk-like behavior, so our character should prefer attacking when he is at full health or at very low health. Additionally the less health his opponent has, the more likely agent is to attack.

Flee should be executed whenever opponent comes too close to us. Also it should be more likely with each health loss.

Curves corresponding to available behaviors may look like this:

Attack Utility
Figure 1. Attack utility curves
Flee Utility
Figure 2. Flee utility curves.

After curves are prepared we decide that attack evaluations should be aggregated by multiplication. On the other hand flee should make use of min function.

We decide that selector should choose behavior with highest score.

Let’s check how it will behave in some test scenarios.

Scenario 1

  • agent’s health = 100

  • opponent’s health = 100

  • distance = 100

Attack evaluation = ah(100) * oh(100) = 1 * 0.5 = 0.5
Flee evaluation = min(ah(100), d(100)) = min(0, 0) = 0

Chosen behavior - Attack

Scenario 2

  • agent’s health = 12.5

  • opponen’s health = 100

  • distance = 100

Attack evaluation = ah(12.5) * oh(100) = 0.5 * 0.5 = 0.25
Flee evaluation = min(ah(12.5), d(100)) = min(0.625, 0) = 0

Chosen behavior - Attack

Scenario 3

  • agent’s health = 12.5

  • opponent’s health = 100

  • distance = 30

Attack evaluation = ah(12.5) * oh(100) = 0.5 * 0.5 = 0.25
Flee evaluation = min(ah(12.5), d(30)) = min(0.625, 1) = 0.625

Chosen behavior - Flee

Scenario 4

  • agent’s health = 6.25

  • opponent’s health = 10

  • distance = 30

Attack evaluation = ah(6.25) * oh(10) = 0.75 * 0.95 = 0.7125
Flee evaluation = min(ah(6.25), d(30)) = min(0.6875, 1) = 0.6875

Chosen behavior - Attack