[MUD-Dev] NPC AI and Learning.

[Travis S. Casey]

On Sun, 7 Sep 1997, Michael Hohensee wrote:

> I believe there was a thread on the subject of how to make NPCs
> act/fight in a more intelligent manner.  Instead of writing complex
> programs, or mirroring the actions of a (supposedly) intelligent player,
> one could institute a learning process for NPCs.
> 
> The idea (cheerfully stolen from one of the "Berserker" stories) is
> based on the fact that for any given situation, there are a certain
> number of possible actions to take.  Which action is actually taken by
> the NPC is determined randomly from the availible choices. 
>
> If the NPC is successful (ie, wins a game, gains something, or survives
> a fight) the choicelist stays the same.  If the NPC loses, all choices
> it selected are deleted as possibilities for future events.

What you're describing is a simplified version of the basic neural net
algorithm:  the main differences are that in neural nets, a successful
choice has the probability of its being chosen again increased, and
an unsuccessful choice has its probability decreased instead of being
completely eliminated.  Neural nets also decide which choice to make 
based on a number of inputs -- if you were designing a neural net to
teach a monster on a traditional mud what tactics to use, good inputs
to use would be the opponent's class and level, and the wielded weapon 
and worn armor of both the monster and its opponent.  (Presuming that
the monster's weapon and armor can vary over time, but not it's class
and level.)

> At first, this creates increadably stupid NPCs.  They'll go around
> hitting themselves in combat, attacking walls, trees, and large
> monsters, and basicly losing at every turn.  But as time goes on, they
> lose less and less, as the negative behaviors are wiped from the
> possible choices.

Of course, nothing says that the NPCs have to start out as "blank
slates."  If you know some rules that will help them, you can program
those in.  Also, you can pre-train the NPCs -- let them interact with
each other for a while.

> So we end up with fiendishly efficient NPCs, while retaining a random
> element for variety. :)
> 
> The only problem with this is the tremendous overhead it would generate
> if implemented per creature.  Perhaps a better way would be to have one
> unified "action bank" which all NPCs draw from.  That would be something
> special.  If Bubba the goblin slayer goes out and stomps lots of goblins
> to dust, they'll eventually become more resistant (as possible) to his
> attacks.  If Bubba then tries to seek greener (and wimpier) pastures,
> he'll find that the neighboring orc tribe has heard about the new goblin
> tactics, and have an interesting time of it. :)

With a neural net, you could make the creature's class and level part of
the inputs.  If you wanted to, you could also add other inputs --
presence of friendly creatures, etc.

> This effectively makes killing creatures very difficult.  The only safe
> way I can see to kill NPCs under this system would be to either grossly
> outclass them, or kill them instantly, before they can react. :)
> 
> Any comments on this?

Well... it's all very nice -- in theory.  In practice, it may not work out
so well.  Part of the problem lies in the definition of success:  for
example, what constitutes a successful attack?  A naive answer might be,
"an attack which hits."  A better answer would be "an attack which does
damage -- and the more the better."  A still better answer might be,
"an attack in which the attacker does more damage than it takes."  Even
better, measure the damage as a fraction of the damage each combatant
can take:  if I'm doing 20 points a round and only taking 10, I'm 
still going to lose if I can only take 30 points and my opponent can take
100.

Secondly, success in the short term doesn't always equal success in the
long term.  For example, a monster might always succeed in combat by
our last definition above, but still lose.  How?  Any number of ways:
the opponent might periodically retreat and heal up while the monster
doesn't do so, for example.  Thus, a number of variables might be 
involved in determining "success," which makes the problem harder...
and makes it more time-consuming, since we may have to wait a considerable
time before we know whether a tactic was successful.

Multiple behaviors may be involved in the optimum strategy, and correct
sequencing of them may be necessary.  For example, the idea strategy 
for a low-powered monster to use might be to begin by harrying its 
opponent with hit-and-run-tactics and missile attacks to soften it up,
and then go in to melee for the final kill.  Cooperation may also be
necessary; for example, setting up an ambush, then sending out scouts to
lure/drive victims into the ambush.  These sorts of things are hard to 
model well with neural nets -- doing it involves feedback loops and 
other things.

Lastly, remember that you're in an arms race -- the problem isn't just 
to learn good tactics, it's to do so better than the opposition does.
If you set up a mud which does this sort of thing, mudders who don't
like to have to think about what they're doing will quickly learn to
stay away, and you'll be left with mudders who enjoy these sorts of
challenges -- some of whom have years of experience at them, in games,
RL, or both.  In other words, you'll definitely make the game more
challenging, but your player base will change as a result.  Humans
are very, very good at this sort of thing when they actually apply
themselves -- you might find that the players come up with new tactics
that work much faster than the monsters do.

(Please note that I still think that making monsters harder to fight
is a good idea -- I'm just pointing out that doing so is likely to
be an ongoing effort, even with monsters that learn.  If you actually
manage to make monsters that can learn faster than humans, you might
want to start looking for grants.  :-)
--
       |\      _,,,---,,_        Travis S. Casey  <efindel at io.com>
 ZZzz  /,`.-'`'    -.  ;-;;,_   No one agrees with me.  Not even me.
      |,4-  ) )-,_..;\ (  `'-'  Keeper of the rec.games.design FAQ:
     '---''(_/--'  `-'\_)      http://www.io.com/~efindel/design.html