[MUD-Dev] Efficient AI?

Hans-Henrik Staerfeldt hhs at cbs.dtu.dk
Thu May 19 03:04:38 New Zealand Standard Time 2005

On Tuesday 22 March 2005 20:15, Douglas Goodall wrote:

> Neural Networks can always be hard-coded. Unless I'm
> confused... I'm not an AI expert. Here's my reasoning: NNs can be
> represented as Cellular Automata, which can be represented as
> k-tape TMs, which can be represented as single-tape
> TMs. Hard-coding doesn't have to remove their ability to "learn,"
> but making a "learning" single-tape TM would be... challenging.

To be more precise, artificial neural networks can be implemented in
a read-only optimized way, that rules out training in any real sense
- 'challenging' as you put it.

> I'm not sure how converting the NN to a hash would be an
> improvement over starting with a static method. Cellular Automata
> could be a bit faster than a Neural Net, and even I coudl convert
> a NN to CA. However, if you want the CA implementation to keep
> learning, "training" would be tricky. Or so I imagine. Did I
> mention that I'm not an AI expert?

Having written the text below, i realize now how it fits very poorly
with the title of this thread - my apologies!

If I were to go with some AI model, it would be hidden Markov chains
that are carefully designed to sample the world state over time, and
structured to mirror the situations you want to have behaviour
for. This way you can fit a behaviour over time, as well as
recognize an event series you are currently in. The Markov chain
method is superior to simple hashing in that it is less prone to
rejecting a model because of a small change in a single
parameter. It is inferior in that it is much more hard to implement
and takes way more CPU cycles actually to run.

Your model would have 'Exit' nodes all over describing 'Here I am in
the series of events i expect to come, and this node tells me what
action to take.', and have a behaviour related to any such exit
node. This model is of course self-amplifying, as the reaction
becomes part of the model, where the AI would pick the path to the
next exit-node with a high probability. The model would also have
loop-nodes ensuring that 'unimportant' events that can be ignored
for a given event series.

Each 'situation' the AI should recognize would then have its very
own model. The AI would continuously evaluate its models to guess
which (more than one) situation it is currently in, as well as what
to do, by fitting the logged events to the markov models and getting
probabilities. As time is modeled here, the time at which to take
action can also be modeled.

This also gives the opportunity to detect a 'new' situation. That
would be situations where none of the models fit the previous events
very well.  Im not suggesting some magic algorithm to 'discover'
their structure, but the 'situation' could be dumped for a developer
to look over and make sense of.

Getting good data for the models could involve building your world
state sampling system, and following an NPC around and then
annotation which situation it is in at given times, and suggesting
actions to take. This would give you some samples of timed world
states that you can use to develop your models. Finding common
patterns etc. Having build an initial model, you can hope to refine
its world state probabilities by continuing to train! it with more
such sampling, now in a more automated fashion.  (indication yes/no)
to given suggested actions.

You could try to make the models evolve by either training or some
modification scheme, modifying probabilities or inserting nodes into
the model by some heuristic (sounds simple, but doing it well is

Then, finally, I will assume you have a supercomputer to run your
game on, as well as do your data analysis :P

--Hans-Henrik Stærfeldt
MUD-Dev mailing list
MUD-Dev at kanga.nu

More information about the MUD-Dev mailing list