[pythian] Re: CODE - AI
- From: Mike Hearn <mike@xxxxxxxxxxxxx>
- To: pythian@xxxxxxxxxxxxx
- Date: Wed, 19 Jun 2002 14:15:51 +0000
Wow, I'd forgotten. That really was years ago. At the end of the GCSEs
Ken! We were but minnows.....
Anyway. Hmm. It's good to see criticisms of my system from real world
experience. I'm surprised to see it boil down to a neural net, as the
reason I shied away from them originally was that they were too hard to
train and predict - program in essence. But if the AIs need as much
tweaking as you say, then presumably the problems converge.
>actually this sounds damn cool. "Hey, let's go to server (3), I hear one
>of the monsters has formed a cult who worship the table_b model file."
>
>
LOL! I like the sound of that. It has got nice legs......
>I've been trying to think of how we could manage input into the voting
>system, but I don't really know. If everything in the game had some sort
>of meaning to an AI, i.e. there is a rock, the sky is upward, my sword
>causes pain; then these values could be equated in voting system by
>processes in the NN and controlled somewhat by personality and feedback.
>I don't know how well this would work but it sounds damn cool.
>
Congratulations, you just invented Cyc (www.cyc.com) - it has been in
development for over 15 years though ;) I think we have other
priorities. Still you're right, it is a very cool technology indeed, and
I wouldn't be surprised if one day we started to see characters based on
Cyc.
One thing, I don't think we need to worry too much about AI processing
time. Most of the AIs (all?) will be running on the server, where we'll
have plenty of spare cycles, so I think we can afford to experiment.
The problem basically boils down to this: traditional scripted AIs are
too limited. They take ages to program, easily get confused and feel too
rigid because they can't learn.
My voting idea sounded good in theory, but unfortunately doesn't appear
to scale too well. Neural nets are the opposite extreme, the ultimate in
flexibilty and of course they can learn, but that's the problem - they
have to "learn" everything, you can't just tell them to do something. We
found this out the hard way in Phase 1 development with the dancing
skeletons.
I'm not sure where to go from here, though I'll give it some thought.
Perhaps a combination of all these strategies? Still, it's easy to
glibly say that, it's harder to produce a working idea.
thanks -mike
Ken Pierce wrote:
>Firstly, I'd like to say that "The spider is biting my head" should be
>our new motto, lol.
>
>Anyway, the AI. I don't know a lot about what goes on inside an AI
>system in terms of code, but Mike has explained his system to me and it
>sounded like a good idea. This 'voting' system sounds good, apart from
>the problems you mentioned with bias, so I think that it could be
>layered with a NN.
>
>I like the idea of a neural network, I used a set of bots once for CS
>with a neural network AI and they were very realistic and did seem to
>learn my tactics well; so if this could be used to equate the decisions
>in a 'voting' system, perhaps a personality could give more weight or
>random element to inputs, and feedback such as "I am in pain" and "I
>have lost my leg" could give negative feedback and deter that character
>from doing something.
>
>However, we'd have to be careful, if all monsters/enemies get killed too
>often, they might stop fighting, so we'd have to put a limiter or
>something like 'courage' of 'strength of character' to keep them on the
>right path. After all, this is an online cooperative game, so we can
>equate it to a single player experience at a base level with
>monsters/enemies being fought.
>
>Oh, that's another thing I just thought of, this is an online game,
>where the AI will be interacted with by multiple users from different
>local machines; for the AI to learn, it would have to write to some sort
>of file, but where would this be. It would have to be server side, which
>would mean that different servers would have different acting AIs ...
>actually this sounds damn cool. "Hey, let's go to server (3), I hear one
>of the monsters has formed a cult who worship the table_b model file."
>
>I've been trying to think of how we could manage input into the voting
>system, but I don't really know. If everything in the game had some sort
>of meaning to an AI, i.e. there is a rock, the sky is upward, my sword
>causes pain; then these values could be equated in voting system by
>processes in the NN and controlled somewhat by personality and feedback.
>I don't know how well this would work but it sounds damn cool.
>
>Then, we could create a load of AIs, each with a personality geared
>towards something different, leave them running in a level somewhere
>with loads of different input to learn from and see what happens. It
>wouldn't even need to be graphical (i.e. display the world, models
>etc.). If it were though, we could watch them and stream it over the net
>and it would become a Big Brother style phenomenon ... well, maybe not,
>but it would be fun to see what would happen.
>
>Finally, could you explian "genetic algorithms and/or iterative state
>machine training" sometime, this is interesting stuff.
>
>
>
>>I've decided to open this one up for general discussion, since it was
>>Mike's idea originally and maybe there are some new ideas from the new
>>members.
>>
>>Our AI system, proposed by Mike a few years ago, was to have a "voting"
>>system. The AI would have several candidate things it could do, and it
>>would vote on each thing to see which it should execute.
>>
>>The AI has many inputs. An input is information about the outside
>>world, the AI's feelings, location, history, etc.
>>
>>The AI has ideas. An idea is something to do. Examples are "walk over
>>there", "attack the giant spider", etc. Each AI has a set of inputs
>>which affect the worth of the idea. For instance, "attack the giant
>>spider" depends on the "there is a giant spider nearby" input.
>>
>>Each decision-making step, the AI looks at each idea and evaluates it
>>based on the importance of the inputs affecting that idea. If an input
>>makes the idea less appealing, it gives a negative value to the input,
>>and if it makes the idea for appealing, it gives a positive value. For
>>instance, the inputs affecting "attack the giant spider" may be as follows:
>>
>>"There is a giant spider" -> +1
>>"I have a sword" -> +1
>>"I love everything" -> -1
>>"The spider is biting my head" +1
>>
>>In total, the idea to attack the giant spider is given a vote count of
>>+3 (the sum of all input values). If the last input had been "The
>>spider is ignoring me" -1, then the vote would have been "0" and this
>>idea would not be appealing.
>>
>>The AI does this for every idea it could possibly have, every decision
>>making stage. It must look at such ideas as "Eat cheese", "Go to
>>sleep", "Run away", etc. because at any given time, the AI needs to be
>>able to change his mind and do something different.
>>
>>The first problem here is that the AI may be considering a huge number
>>of idea, thereby consuming a lot of CPU time. An alternative to this is
>>to have a multi-layered system where the first layer makes "high-level"
>>decisions such as "I am in combat" or "I am doing domestic things".
>>This first layer is evaluated, and then the second layer is considered
>>depending on which idea won the first-layer vote. If "I am in combat"
>>wins, then only combat-related idea are considered. Anyway, it's
>>basically the same system.
>>
>>I implemented this system for the Phase 1 demo and learned a lot about
>>it. First of all, most of the AI in the game boils down to a simple
>>state machine, despite using the voter system. The AI would have very
>>few inputs, and perhaps 2 or 3 ideas. I simplified the input-weighting
>>system as much as possible so it was almost entirely deterministic which
>>idea would be picked. I did this to keep the AI simple so I could
>>actually tell what it was going to do.
>>
>>There's you background. I hope that was clear enough to bring you
>>up-to-date in the discussion.
>>
>>Now the problem: how to attach "importance" to the inputs. The issue I
>>found during Phase 1 was that it was very difficult to decide how much
>>importance an input should have for a given idea. If an input has too
>>much importance, then it ends up winning the vote too often or at
>>inappropriate times. It required several iterations of tuning just to
>>get the AI for a bird to fly around in circles or for a character to
>>follow a predetermined path. And these were simple AIs with only a few
>>ideas each.
>>
>>The problem quickly compounds as you add more ideas. Not just
>>computationally, but for tuning the AIs as well. You must make sure that
>>the importance of an input isn't too high or else the AI will make
>>stupid decisions, like running forward to attack and thus walking into
>>the path of a fireball. Each of these values must be carefully tweaked
>>to allow optimal performance.
>>
>>This is a major problem. We will have tens or hundreds of different AIs
>>in our game. Even for Phase 2 we will have quite a few. To adequately
>>tweak this sytem for all these AIs would take months if not years, with
>>the length of time exponentially dependent on the number of ideas each
>>AI has. The only solution to this I could imagine is to have the AIs
>>learn, but currently this system doesn't allow for learning.
>>
>>The next problem is that the weighting of inputs must be "fair" or
>>"equal" across all ideas. For instance, if the idea to attack is
>>unaware of the inputs for defensive operations such as blocking, then
>>the attack idea may get a high vote because it doesn't know that
>>sometimes defense is necessary. For instance:
>>
>>Attack Inputs:
>>"I have an opponent" +1
>>"I have a weapon" +1
>>"My opponent is within stiking distance" +1
>>"Someone is attacking me" -1
>>
>>Defend Inputs:
>>"Someone is attacking me" +1
>>"I have a shield" +1
>>
>>In this case, the idea of Attack will almost always win. Note that this
>>is true no matter what system you use for evaluating the votes (e.g.
>>floats in the range 0-1, fuzzy values, etc.) I've tried a few different
>>methods and the problem arises for all of them.
>>
>>The only solution is to have every input for every idea in the idea set
>>(e.g. the Combat Idea Set) apply to every idea in the set. That is, if
>>an input is relevent for Attack, it must also be relevant for Defend.
>>This means that if there are "m" possible inputs for the "n" different
>>ideas in the set, you have n*m connections between inputs and ideas.
>>
>>This equation immediately made me realize I was dealing with something
>>most of you have heard about: Neural Networks. In fact, this system is
>>called a "fully connected Neural Network", where each input has a
>>weighted connection to each output (idea). Mike's system essentially
>>equates to a Neural Network. :p
>>
>>Well, that solves the learning problem, since NNs have been thoroughly
>>researched to allow learning, but that's not really what we want, is it?
>>Neural networks are computationally heavy and training (or learning) is
>>slow and often unpredictable with such problems as local minima,
>>over-training, and reward weighting issues.
>>
>>Should we revert to state machines? Should we rely on NNs? Should we
>>explore genetic algorithms and/or iterative state machine training? Or
>>should we combine all of the above?
>>
>>I've been thinking about it a lot and now I'm feeling stuck. Can anyone
>>help me?
>>
>>Darryl
>>
>>
>>
>>
>
>
>
>
>
>
Other related posts:
