Subject: AI for enemies

From: Owen Brand <[email-masked]>
Date: Wed, 30 Jun 2010 22:01:24 -0400

I've been reading some game creation theory articles and I've come  
across some difficulties.  I need to develop some kind of artificial  
intelligence (for the higher level characters) in my battle engine...   
Q: how does one develop such a concept in code?  I'm not looking for  
code samples, per se, but rather a concept--- how do I make higher  
level enemies know when to use a magic--- when to attack--- when to  
parry--- when to heal... Some if this stuff is pretty  
understandable--- for instance the enemy "knows" his stats and knows  
when he is running low on health... Good time to heal?  So I guess i'm  
really wondering how to use a common engine for all enemies, but  
manipulate the "intelligence" of the enemy.  Hope this makes sense.

Owen Brand

        **webmaster**
http://www.Opry99er.com

---

From: "Tursi" <[email-masked]>
Date: Wed, 30 Jun 2010 20:54:10 -0700

> manipulate the "intelligence" of the enemy.  Hope this makes sense.

I remember one of your very first question back on Lemonade Stand, that
being how to determine how many customers actually bought lemonade.

That question was pretty easy, because it was pretty simple to boil down the
factors into a formula that would suit the needs of that game.

But good AI is a subject that entire books are written on, and there's no
"right" answer. I can give you some tips though.

First, put yourself in the computer's position, if you can, and play a
couple of rounds yourself. See what kind of decisions you would make. What
makes the difference between a good move and a bad move?

The second thing to consider is, how aggressive should the computer be? Will
the computer always go for the hardest hit, or will it sometimes show
compassion? Perhaps it's wary, defensive, even scared - different creatures
might have different behaviors. You'll want to consider this.

A third thing to consider is whether the computer should "cheat", that is,
should the computer use information that the player may not have access to
(if there is any!) in order to make it a more challenging opponent. While
this sounds horrible on the surface, most computer players in most games do
cheat to some extent. As long as it isn't blatent, and solves an actual
problem, this is not so bad. For instance, if the computer AI in a maze game
knows where the player is and moves towards him even though it doesn't have
line of sight, most find that acceptable, but if the computer AI in a poker
game looks at your hand to decide if you are bluffing, that's probably
crossing the line. ;)

All of the above will help you decide what information is available, and
what makes for a good move. The second step is to decide how to find the
actual move the computer will do. There are a couple of ways to do this.

If the number of possible actions in a turn is finite, the computer can
actually examine ALL of them. The idea is to "score" each possible move with
how "good" a move it is - then you can use the highest scoring move. Notice
"score" and "good" are in quotes -- that is because it's entirely up to your
algorithm to decide both of these terms. During this phase, it's conceivable
for the computer to "look ahead", too, and see what the consequences of its
move might be - the player's possible retorts could vastly affect the "good"
score.

When considering the player's response, you could again consider all
possible responses, or you could use a history of the player's moves, and
try to statistically guess their next move.

Now that I've been vague, let me try an example. I'll use a extremely
simplified concept.

Let's say it's the player versus a single AI. Each character has two stats -
power and life, which are arbitrary numbers. Each character has three
options:
-rest/defense (which recovers a point of life if they are not struck and
increases chance of the other missing by 20% otherwise)
-attack with sword (50% chance of hitting, 2 x POWER pts damage)
-attack with magic (80% chance of hitting, 1 x POWER pts damage)

We join this battle already in progress.

The player has 4 points of life, and a POWER of 3.
The AI has 3 points of life, and a POWER of 4.

--

Let's consider first, the AI just considers its possible moves. We need to
decide what results we care about. In this simple case, we'll say the least
resulting player health. Remember in this example, we will not consider the
player's response.

REST: Player has a 0% chance of being hit, and will end up losing no points
of health. 5-0 = 5, so 5 is the score.
SWORD: Player has a 50% chance of receiving 8 points of damage. We'll
average that out, and say 4 points of damage on average. 5-4 = 1, so 1 is
the score.
MAGIC: Player has an 80% chance of receiving 4 points of damage. We average
that out, and say 3 points is the average. 5-3 = 2, so 2 is the score.

The lowest score is SWORD at 1, so that appears to be the best move, and
maybe the computer should use that!

--

Let's throw in considering the player response. This really increases the
number of possibilities, since each action has three possible reactions. We
will also consider our own resulting health as well as the player's. We want
our health high and the player health low, so we can score by subtracting
the player health from ours.

AI REST: As above, the player result is 5. Now consider the player responses
to it.
  PLAYER REST: Player does not attack, so we gain a point of life, raising
us to 4. 4-5 gives a score of -1.
  PLAYER SWORD: Player has a reduced chance of hitting - 50-20=30% chance of
hitting for 6 points. 30% of 6 (for the average) is about 2, so presume on
average we are hit for 2, leaving us at 1. 1-5 gives a score of -4.
  PLAYER MAGIC: Player has reduced chance of hitting - 80-20=60% chance of
hitting for 3 points. This is again about 2, so we end up at 1 life. 1-5
also gives a score of -4.
Now we can add this all up to get a total score for AI REST - -1 + -4 + -4
= -9.

AI SWORD: As above, the player result is 1. Now consider the player
responses.
  PLAYER REST: We take no damage (and we don't look far enough ahead to know
if we attack next round, so we can't add the player's health bonus yet). The
player remains at 1 and we remain at 3. 3-1 = 2.
  PLAYER SWORD: We have a 50% chance of taking 6 points of damage, so an
average of 3. This leaves us at 0 points and dead. Because dead is an
undesirable state, you might want to add a modifier to weaken this score -
but in this case I will not. 0-1 = -1.
  PLAYER MAGIC: We have an 80% chance of taking 3 points of damage, so
average is 2. This leaves us 1 point of life. 1-1 = 0.
Now add it all up: 2 + -1 + 0 = 1.

AI MAGIC: As above, the player result is 2. Now consider the player
responses (which will be similar to sword).
  PLAYER REST: We take no damage (and we don't look far enough ahead to know
if we attack next round, so we can't add the player's health bonus yet). The
player remains at 2 and we remain at 3. 3-2 = 1.
  PLAYER SWORD: We have a 50% chance of taking 6 points of damage, so an
average of 3. This leaves us at 0 points and dead. Because dead is an
undesirable state, you might want to add a modifier to weaken this score -
but in this case I will not. 0-2 = -2.
  PLAYER MAGIC: We have an 80% chance of taking 3 points of damage, so
average is 2. This leaves us 1 point of life. 1-2 = -1.
Now add it all up: 1+ -2 + -1 = -2.

With this math, we're interested in the highest score, which turns out to be
AI SWORD, with a total score of '1'.

--

It's easy to see that the sword is always the best move in my scenario, but
it would not hurt to throw a little randomness in to mix things up. Random
numbers, used in moderation, let you "trend" the data towards the best move
without always choosing it. For instance, if I randomly added -1, 0, or 1 to
the above scores, the computer would PREFER the sword but might still pick
anything.

The more variables you take into account in this sort of thing, the smarter
the computer can be about it. Of course, looking ahead through every
possible move can very quickly take a lot of time or memory, so you have to
decide if that is even possible. There are numerous ways to reduce the
search space when you can't search every possibility, and we'll save those
for a future note. :)

---

From: Owen Brand <[email-masked]>
Date: Thu, 1 Jul 2010 00:17:34 -0400

Wow--- brilliant response man!  It affirmed a few assumptions I had  
and made the whole thing a bit clearer.  I have questions for you, but  
they will have to wait til tomorrow.  Thanks for the lucid and speedy  
response.  :)

Owen Brand

        **webmaster**
http://www.Opry99er.com

---

From: "hjalmarii" <[email-masked]>
Date: Thu, 01 Jul 2010 21:28:50 -0000

Let me add my Wow! to Owen's, Tursi.  I will never write a game but I enjoyed reading your tutorial, and learned a lot.  Thanks for taking us through the process of figuring out ways to make the computer a worthy opponent.  When my kids were playing "Legends," I used to ask them why they never, ever just "greeted" the monsters they encountered.  They said they always got their butts whipped, and now I begin to see why.  --Hal

--- In [email-masked], Owen Brand <owenbrand@...> wrote:
> On Jun 30, 2010, at 11:54 PM, "Tursi" <yahoogroup@...>  
> wrote:
>