Fleeting thoughts on AI

No doubt about it, AI is a fascinating topic and there are no clear cut answers, possibilities are simply endless. AI may depend first of all on the game genre, so a platform game will have a different AI compared to an evolutionary game.

Nowadays from what I have seen most seem to have some kind a Finite State Machine (FSM), where certain conditions are analyzed and actions are taken accordingly, this works similar to IF..THEN..ELSE statements. So a NPC just stands around forever on the same spot doing nothing or walking senselessly around day after day without rest, at most the NPC is going through its FSM and that's it. When aggroed, as pointed out, most NPCs keep a hate list, where the NPC sorts who has caused how much aggro, be it through heals or damage dealt and decides who to hit on. Run out of range and the NPC resets, the hate list is wiped, it's got a clean slate, boy do I envy those NPCs !!!

Well, IMHO I find this kind of NPC extremely boring. I envision a bit more and I'll mention an example inspired by Matt Buckland's book "Programming Game AI by Example".

A story from the fictitious mining town "Backwater":

Miner Irwin goes every morning out to the mine to fill his pockets with gold, during this process he will get thirsty, hungry and sleepy, but he also appreciates digging up a certain amount of gold, once satisfied he goes to the bank and deposits the money, if he gets thristy he visits the local saloon, has a drink and talks to his buddies, if he gets hungry he goes home to have his lady who serves him some stew (both will need to communicate as well), if he gets sleepy he will lay down, when rested he gets up and at it again. Let's add to this some more sense, he may be receiving input from his surroundings, so f.e. he one day detects within 50 yds. an orc, he also determines his level and notes that he has weapons equipped, his emotional ann determines fear and he runs back to town and alerts the guards. His goals may temporarily change in favor of self preservation, Irwin goes to the local saloon for more drinks until the danger is over. Guard Erl hears him shout and stands ready to fight the orc. Erl loses the fight to the orc with the rusty spoon.

-HALT- Design decision ahead -

Option 1: Normal MMO AI's would wipe their memories, Irwin engages in the fight before perishing, the new Erl is just as "savvy", as he was before, and both will just respawn and surely be killed again and again and again.

Option 2: Erl preserves his short term memory through death, he remembers that the orc with the rusty spoon was 3 levels higher than him, he modifies his internal state and makes a note to himself: if dead by attack and enemy_level + 3 then update in table fights[self+3] values pleasantness - 0.1 and control - 0.1 . When next confronted with that orc the ANNE with emotional responses will evaluate the situation differently, there will be a moment when anger becomes fear and he may just run for his life and/or call for additional help, this orc William is just too much for him alone. The internal goal seeker of Erl might determine that when he has lost 3 battles in a row, he needs further training and emerges as a level+1, he will now be tougher than before, after some cycles, the orc finally loses the battle and Erl, 4 levels higher and 20 generations later maybe feels invincible again. He keeps standing around for a while and his abilities might slowly degrade to the original skills/levels (or he might stay at his level), this learn and forget setup would avoid players farming certain NPCs but ensures that on the long run the game world is somewhat stable. He will slowly forget that he lost 8 battles against orc William and won 2. However he just might remember in his long term memory how many battles he lost and won sorted by enemy levels and how many attacked him. He may also communicate this to his peers, in case of SMASH maybe on the same city chat channel or a special guards channel. Erl will also change guards with others and not just stand there forever, but swap with Marlo, while Marlo stands guard, Erl goes for lunch or dinner and sleeps a while. Meanwhile our miner Irwin either asks the guards for dangers and/or notices that the threat has gone away, he no longer perceives orc William in the surroundings scanning some 100 yds (just to be sure) and goes back to his original goal of getting his pockets full of gold.

If enough orcs have attacked the city, the council members might stage an all out attack against neighboring orc villages to protect themselves.

While this is still future music, this is what I have in mind for the AI, a simulation rather than just a cheap FSM.

This requires an agent capable of perceiving its surroundings (sight and words), a certain personality to evaluate perceptions, a goal seeking Hierachical FSM (HFSM) capable of sorting goals, a neural network (-> ANNE) to analyze what emotions result from its current situation applied to the personality and a HFSM that decides on memory, learning and thresholds whether to pursue its goals or take alternate actions and then carry them out. Let's call this the perception system (PS), goal seeker (GS), personality profile (PP), ANNE you already know, the memory records (MR), the decision maker (DM) and the action machine (AM). If you wanted to implement a hive mind, you would need to sync the goal seeker, the memory and probably the personality profile or if you do it in Erlang, just call the processes that represent those per hive mind.

I believe this design should enable for different actions according to each NPC's personality: f.e. when insulted, Eliza might feel sad, run home and cry, while guard Erl while take his sword and apply a subtle lobotomy. When attacked, Irwin might run for his life, while Erl fights back. When applying evolutionary rules, their behavior might even change over time. Most literature does not recommend to enable long term learning when you go life, because results will inevitably be unpredictable, so only time will tell if long term evolution is a good choice or not.

I highly recommend downloading and running "AI Planet" from sourceforge.net and also read the author's design notes, it is fascinating to watch how creatures evolve over time. Imagine this in the settings of a MMO and I am sure it will create immersion for the player, but it would also mean the game to be different according to when you joined, tough call.

In the end though, some restrictions may apply, according to how much processing power you have on the server side, if you have 200'000 NPCs in your game world, you'll probably downsize the AI a bit to match CPU power versus NPC numbers, I am eyeing the shared process structure as mentioned above.

Cheers,

Sunweaver

News on ANNE

The toughest task in a programmer's life is not the actual algorithm but the bug hunting, I noticed that something was still weird in ANNE and I found some more bugs in my code, but well.

I implemented some improved trainers for XOR operation and for the emotion part, but this time not by running a fixed number of epochs, but by checking for the LMS (least mean squares) of the training sets, which actually works nicely so. When setting the trainer to 0.01% LMS: ann structure = input:(hidden layers): output

* XOR works after 11422 epochs with 2 hidden layers and it takes 11855 epochs with 1 hidden layer, 2:(2:2):1 versus 2:(2):1. Precision seems to be on par of both by 1%.

* Emotions are trained after 25201 epochs with 2 hidden layers and 18387 epochs for 1 hidden layer, the first is 6:(6:6):6 and the other is 6:(7):6. Their precision is about on par for learned values, but the first is much more precise towards one or the other emotion when interpreting new values, the second would allow for some more varied emotions (like primary and secondary).

My interpretation here is that while for most practical purposes a second layer is not required, it does add a lot of precision if you care for it and if you don't mind the extra time for the training.

I believe ANNE is now working correctly. Now I will start trying different AI scenarios for NPCs, it seems that ann's are suited to be the brains of a NPC, let's see.

Regards,

Sunweaver

ANNE to ELIZA: Think before you talk !!

As I said before, there are so many, many components that need to be built for the complete SMASH, one that I have barely mentioned so far is the AI part, no game ever would be really complete without some intelligence. So let's talk smart today.

Eliza will most likely be part of the NPC perception system and and it will be important for stateful conversations with the added context info (which will later form a sort of decision tree) and when I coded Eliza, I had the idea of also including something else, one thing that I find about basic Eliza is that it feels too cold, there are no emotional reactions behind it. We humans associate words with feelings, like it or not, so I started looking into that.

Now, how do we translate input into emotions ??

In order to do that association I dug up a couple of AI books on my shelf and found a nice model about how a NPC (I recommend the book: Programming Believable Characters for Computer Games by Dr. Penny Baillie-de By) can translate situational information into emotions, which turns out to be an artificial neural network (ann), so after some real messy programming sessions ANNE was born: Artificial Neural Network Entity.

ANNE is a fully connected multilayer feedforward network with normal error backpropagation. I will spare you yet another explanation of how ann's (also called sometimes multilayer perceptrons) work, mathwise, I found however this very insightful page: Introduction to Neural Networks which does an awesome job at explaining them.

While it's tempting to implement each neuron in Erlang as a process, I didn't, because I do not like to have processes just laying around doing nothing 99% of the time, rather, I implemented this as a list of lists, which can now very conveniently be saved to KVS*. This way you don't have to retrain it every time, just save a trained version on KVS2 and with KVS* replication, you now have the model ready to use across all SMASH nodes.

I wanted to see just how many neurons ANNE could support, so after some partial testing I can say that I was able create f.e. an ann with 500 inputs, 2 hidden layers with 5000 neurons each and 500 outputs, let me tell you that this a hell of a list of lists with a total of 30 Mio internal weights, so be patient during the training process. Most literature also does not speak about how many iterations are required to train an ann, but it would seem to me that it requires about 50'000+ epoch (epoch = 1 run with all training sets) to perceive a convergence of the weights. Erlang impressed me yet again, I was unsure if it could hold THAT much data in a single list .... but it did.

Now, let's get a feel for it: My first test was as suggested by Mrs. Penny a simple XOR operation (with 2 inputs, 2 hidden layers neuron in a single layer and 1 output neuron) which after sufficient training works just fine. Once it passed the initial runs I grabbed that emotional model described in the book looks like this (chapter 7.5.2):

What you see here on the left is the lower part of the trained ann with 6 inputs, 1 hidden layer with 7 neurons and 6 output neurons. The ann is then trained with 6 x 6 samples for about 50'000 epochs, returning the new trained ann, the output values should be loosely binary as intended, meaning 5 ceros and a single 1 value.

The call to anne:ann([INPUT], ANN) accesses the anns knowledge, so I fed the values from the book into it, knowing that those values will need to be interpreted and hoping that the 4th value is clearly the highest one of them, .... indeed the 4th parameter is the highest with 0.88 ... which is correct !!! In this example it represents: "fear", also note that the 3rd value is 0.24 which stands for "anger", the beauty of an ann is that it states the most prevalent emotions, but you could also take into account the 2nd strongest one, so maybe this input to the NPC will cause it to run away in fear cursing angrily.

I now need to find some example with 2 hidden layers to test ANNE on, but so far everything works just fine.

I have not decided yet how a fully grown NPC will have to work, it might be a sort of hierarchical finite state machine (HFSM) with modules of Eliza and ANNE integrated into it or just ANNE + Eliza, but I believe this is good progress already on the NPC AI.

One more nice thing is, if you embed an ann into a looped process you would only need a single instance on all of the SMASH servers for all NPCs to interpret that input. Maybe several anns will feed its data into a HFSM and make it trigger its actions and responses.

ANNE is still an uncooked meal, but the ingredients look fine. And that's all for now folks. Until next time.

Cheers,

Sunweaver