[MUD-Dev] Efficient AI?

[olag at ifi.uio.no]

Robert Zubek wrote

> I'm a big fan of all things Markov, and I was wondering if you
> could include more details about what you have in mind? I suppose
> it's not clear to me what is the process that's being modeled with
> the Markov chain, what the state space represents, etc. More
> details - or maybe an example - would be much appreciated. :)

Yes... :-D

I only described the main concept, which is an attempt to take
advantage of some "facts" that holds for NPC AI, but not for optimal
AI:

  1. It doesn't have to be perfect (so we can use hash)

  2. It is OK with some mistakes, if it isn't too predictable (the
  noise component)

  3. It would be nice if it was fast, so we can run a full
  simulation of NPCs even if no players are present (hashing is
  fast)

  4. It is ok to have somewhat static AI (tiny state-space, static
  hash function, and not to forget: it makes play testing more
  robust.)

Of course, I shouldn't really call it a "hash-function", and I
shouldn't really call it a "markov chain", but I figured those terms
were the best ones for efficiently communicating the basic idea as
they are quite close to the pragmatic simplicity I was aiming for.

A naive version would be to take a real markov chain and find an
approximation for it using a series of hashfunctions/tables as
described.  You could get the initial chain by having developers
play the NPCs (if you have a very limited set of events). Or, you
could specify rules (heuristics) which state that a state X should
be picked with a probability Px given a particularly configuration
of the event history.  This wouldn't really be all that useful
though, you would be better off if you allowed some aggregation of
significant information in a given state in order to avoid
rescanning the entire event history. Significant being: information
that probably is useful in the set of likely next-states for a given
current state.

E.g. if the markov chain takes the preceding 50 events into account
(pretty extreme) then maybe we could boil that down to a set of
hash-functions-like mechanisms that only look at 4 events.

Just to avoid confusion: the main point was not to have good AI, but
very fast AI (approx 100 cycles per decision?) with a small memory
footprint (static code/tables).

I'll supply an example later if this was confusing.

Ola
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://kanga.nu/lists/listinfo/mud-dev