Monday, August 17, 2009

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 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.




Lincoln said...

Aye. It seems like the AI is going to take quite a bit of processing power compared to the crummy little FSMs used in most games!

I think it's pretty fascinating that you can implement something as seemingly alien as a hive mind of sorts by simply syncing a few of the agents together. I think that alone is a pretty awesome demonstration of the power of a language like Erlang in the context of message passing.

I call reading something about how Ork culture develops in Warhammer. IIRC, it typically starts out with snotlings and grots building up the framework of an Ork camp, and then the Ork Boyz appear, and then eventually a Warboss arises from the sparring and in-fighting of the Boyz. You sort of a get a snowball effect of growth and momentum of a tribe as it progresses into a full-scale WAAAGH!

I've always thought that would be a brilliant system for building a dynamic world. You could sort of have tribes that spawn and grow into war-machines if left unchecked. It seems only natural that players would beat down the small skirmishes and uprisings near their starting area, whilst a sprawling mass of carnage could lie just a few hills away, because no one ever thought to go over there.

Tying it in with what you have designed, these entities would have objectives to stretch across the world, only to be stopped by players or perhaps opposing tribes. As small empires are carved out, the difficulty of purging, and hence the rewards for doing so, become greater. I think this addresses a common problem I've seen in modern games: when new areas are introduced, old places that didn't have particularly high traffic in the first place are now left completely barren. Since the area is static anyway, there's no real incentive to players to go there other than to get comparatively crappy EXP and bad loot.

Sunweaver said...

Yes, what you are describing is exactly what I have in mind, the Sim should play whether anyone is online or not, Empires should come and fall and players should be able to live in this dynamic world.
Yet there is one thing I cannot quite define yet, what should happen to new low level players ?? Should they sort of play in an instanced zone in the past maybe where f.e. those tribes were still low level ? Or should those NPCs "appear" to them around their level, even if they are much higher, and when they level up the NPCs hide less and less their true level (and hence their XP + loot improves as well)? If so, should those "lowered" NPCs ignore hits from higher level chars once they are tagged ?

I have no solution to this issue yet to be honest. Any suggestions are welcome.

Lincoln said...

It's a tough question.

Ideally there would be a gradient of difficulty leading outward towards the wild that would arise naturally through the actions of players. If cities and townships appropriately reward higher level players for cleaning up the particularly nasty baddies outside of town, then ideally the area surrounding town should become manageable for new players because veterans won't bother to pick off measly level 1 enemies.

That is to say, if a band of level 20 trolls wander toward the gates of town, then the town will offer a bounty to banish the trolls. This works out pretty well for level 20 players who would otherwise be killing level 20 trolls in the wild for far less reward.

Not to mention with ANNE, the wiser, higher level trolls might know better than to wander near the gates of town whilst the scrappy young ones aren't smart enough to know any better.. which is coincidentally a great situation for new players and a very poor one for the young trolls! :)

With that said, I think to have a dynamic world you're going to need to strongly reinforce the player-community aspects as well.

Anonymous said...

This is a great project and blog - I'm surprised there hasn't been more interest. Even if it turns out to be vapourware, the blog entries alone making interesting reading.

I'm not sure you could make interesting large scale MMO worlds full of NPCs all as individuals, even if you use separate servers just for NPCs like planeshift do (their NPCs are fairly simple). What you could do is have low level npc's such as townfolk, guards, peasants, bandits, creatures that are very basic, and individuals such as knights, captains, lords, monster bosses, kings that are far more complex.

It'd be interesting if you could do some kind of erasmatron storytelling system, when engaging with the important NPCs - giving you a unique and interesting storyline to follow, that's woven into the current game world (using people/objects/places/tasks). The low level NPCs could even join in to a small extent, in that there's a chance they could know some information, or on asking a town guard a question about their old king's precious youngest daughter, then turn nasty and attack you!

Anyway - just some thoughts, keep up the good work!

Sunweaver said...

Hello Epoll, thank you very much for your comment !! It is always encouraging to hear positive feedback =). I started this Blog as a public notepad and I haven't announced it anywhere, so I believe people just find it by mere accident. The reason I state it's vaporware, is because I develop this in my spare time, of which I don't have as much as I would like, so I have no real deadline for a public beta. The reason you haven't seen much news lately is because I am test driving ANNE for a financial forecasting model actually, I am also studying a lot of other AI algorithms, I am learning Apocalyx & LUA on the side lines and it is also quite hard to do server and client development at the same time, it's a lot of work, rest assured the project WILL continue, I will not rest until I have a working prototype MMO. And I appreciate your NPC comments, I think you are right, it maybe a complete overkill to create a hardcore AI for each NPC, I believe AI-sharing will be key and I love the storytelling part you mention, I think I will be able to cover that with my version of Eliza, because Erlang offers rich pattern matching and THIS Elisa returns the answer together with a configurable tuple of what the answer means to your NPC, so actions could easily be derived from that tuple. Thanks for posting and I will still have some updates before the year is over, hopefully a first multiplayer test and maybe a short video illustrating it. If you have specific interests, let me know, I could do a specific post for it and all input is always appreciated, many brains can think of more stuff =) !!