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

Eliza expands its mind

I have looked at many Eliza implementations and most only match a single word in the sentence, or a word in the middle and the rest after the match, so I took it a bit further, I can now match stuff like: "I %% flowers **" and also stuff like "I %% and %% flowers **". This would catch several multi-word patterns in between and whatever goes behind flowers. Given that Eliza does pattern matching but the humans employ several words for the same thing if only your Eliza could group by similarities for example by ["love","like","fond of","don't hate","don't dislike"] . Another example: how many Elizas can tell that these are equivalent to a human: ["MAC", "MACs", "Macs", "Mac", "Macintosh", "mac", "macintosh", "apple", "Apple", "Macbook", "mac mini", "Macmini"] ?? So how do you catch different ways of expressing tastes with different nouns, that tell you more or less the same thing ??

Answer: pattern expansion !! I expanded Eliza's linguistic abilities to match similar patterns, you only need to create a pattern list of synonyms and specify that list in another pattern as an expansion pattern like "I ## ##" where ## stands for the synonym list, here is how:

To recreate the above example you would create 3 records in the Eliza file, the first is the pattern and the other 2 are merely variables.

{["I ## ## **"],
["I live inside a computer","I can live inside a Mac","Maybe I reside in a Mac right now"],
{subject,computers,["##1", "##2"],["like","Mac"],[]}},
{["##1"], ["love", "like", "fond of", "don't hate", "don't dislike"], {internal,synonyms,[],[],[]}},
{["##2"],
["MAC","MACs", "Macs", "Mac", "Macintosh", "mac", "macintosh", "apple", "Apple", "Macbook", "Ibook", "Macmini"],
{internal,synonyms,[],[],[]}},

So now the pattern "I ## ##" is expanded against both variables ["##1", "##2"]. which creates in this case 150 patterns in run-time, but your file only required a simple entry and again Eliza returns some values that your AI can now chew on. Those variables can obviously be reused in other patterns and it's needless to say that I will be able to teach her new stuff in run-time.

Things that I find are still needed be it either on Eliza's or the AI's side is to catch specifically nouns and verbs, maybe by matching against another list and trying to find a corresponding context for them, like when your application knows nothing about flowers, but flowers are plants and maybe your AI knows something about plants or maybe it lacks info on Mac's but knows about computers. And Eliza should also be able to ask the user and remember its question. But for the time being, I am quite happy with the implementation, it will suit SMASH well to have NPCs that the user can actually talk to. The current version is stand alone, future ones will likely put their info on KVS* for easy data access and replication.

Cheers,

Sunweaver

Eliza speaks Erlang with a twist

As I said in the previous post, Eliza should be fairly easy to implement in Erlang and so it was, I present to you the first Eliza that speaks Erlang:

The image on the left shows the Erlang Shell where you can see some examples of Eliza being called as eliza:start(Text) [also possible: eliza:start(Text, Bot) (not shown) to choose some kind of personality]. Eliza will try to load its text file for interpretation from disk.
Eliza prints out in the shell and returns a tuple with: the input string, context information, extra words from the pattern matching and the answer from Eliza.

What for ?? A normal Eliza implementation has no idea what you are talking about, it does no provide or save the context of the conversation, so my implementation has a little twist, you can provide some additional info to each question-answer list, meant to be used by an AI implementation, so like above when stating your name, Eliza answers with {name,player} and the player name, so your AI could register that Eliza just got the player's name or whatever the player tells Eliza, like dislikes, likes, emotions, hobbies or whatever, your AI could then save the data to a database or you could also load a different Bot context file to chat more specifically on a topic. I will incorporate this in my AI modules in the future and in the meanwhile this will serve for some "dump" entertainment in SMASH. A miniature dictionary to showcase Eliza is included in the code. I also see a use for this on the CNPC's to detect automatically abusive or foul language, as mentioned on many previous posts.

If there is anybody interested in the code, let me know and I'll publish it here on the Blog, it's deceptively simple, just under 200 lines and not yet optimized, but it's a first step towards implementing AI in Erlang.

And now back to CAM.

Cheers,

Sunweaver

Huh ?? Did you SAY something ??

As CAM goes forward, I am defining user permissions, channel permissions, guild structures and user levels which go from guest to game developer with each level having unique commands, which of course brings us to the point of what the final command structure will look like, I believe it's going to be something like: {CHANNEL:REQ:PARAMS} where each REQ that comes from the socket is seen as a request for action by the CC component before being sent to its Action handler (AH) and from there to the channel controlling NPC (let's call it CNPC for future reference). Only the CNPC's can return commands that need to be applied to each CC. Some commands will need to take into account distances, which will be done in the CC, commands like "SAY", movement and position data or Area of Effect spells, Thor gives in his book an example on how to do that kind of calculation easily and without spending much on calculations. Apocalyx will need to translate the server packages from {CHANNEL:WHO:{CMD1:PARAMS}{CMD2:PARAMS}{CMD3:PARAMS}} into action on the client and WHO is obviously derived from the CC.

Note to self: Commands are better off as binary structures or at least send the commands list with a number to the client and have the client use a number to shorten sent IP packets. Maybe SOX will translate and package this at some point into a binary format.

Once again I find that prototyping takes so much longer than actual coding, because it really pays off to think before you program and avoid conventional code at all cost !! Erlang rewards those who create the application logic by pattern matching.

Which reminds me, a nice little Eliza implementation for a CNPC might be fun to start with, for those who don't know Eliza, it was invented as a program that would apparently answer with AI to a sentence by analyzing the sentence structure, recognizing certain words and answer with premanufactured phrases, making people think they were talking to a person, well, in the 70's it was surprising, that is. It's still fun though and with little modifications, KVS could provide a short term memory for Eliza to keep track of what users talked about. You may notice that pattern matching is precisely what makes Eliza strong ;) and hence should be trivial to implement in Erlang.

One last side note, I have not yet replaced Mnesia in SMASH given that I am still debugging KVS*.

That's all for now folks,

Sunweaver

Tuples here, there and everywhere

As I am trying to make some progress on the authorization module, I find that the required databases are getting more and more complex and with them the record structure, meaning that tuple pattern matching is quickly becoming a logistical nightmare, stuff like {_,_,_,_,Variable,_,_,_,_,_,_,_,_,_,_,_,_} = Some_tuple is not very practical. Erlang has a native record definition, but it has some important restrictions, so I had to create a record structure for KVS2, that can correctly create, modify and read records in KVS2 by naming the fields, for this you need to create a list entry on the 2 DB structure tables. After that, you can simply call kvs2:crtrecord(DB,Key,Data), where DB is the table & table structure, Key is the record name and Data is a list of tuples of {field_name, Value}, you can read with getrecord(DB, Key, [Fields]) and modify an entry with updrecord(DB,Key,Data), which works similar to crtrecord, you only need to specify the fields that will be modified. This greatly simplifies data management and allows to change the database format in the future, too. You can also use this functionality to manage any kind of tuple with crttuple & updtuple. This should provide some more flexibility than native Erlang to manage structured tuples. With this addition KVS2 can now handle Key-Value pairs with structured value tuples.

This tuple management and the magical pattern matching will make authorizations ... almost ... a breeze.

BTW, for those of you who can already employ version R13, note that there is a new function called: erlang:make_tuple(Arity, Default, InitList) which can create tuples with initial values, very nice addition, unfortunately Ubuntu has no support for R13 yet (unless I compile manually , yuk!), well, you can't have everything I guess.

Soon more on the Chat Authorization Module (CAM).

Cheers,

Sunweaver