The role of randomness in the Copycat architecture

This is an addendum to my post The Coderack and Codelets.

I forgot to write about one important characteristic of the Copycat architecture. In traditional Game AI randomness is used to make the character behave less predictable and thus look more human. But this randomness is applied at a very high level, for example upon an encounter there is a 80% chance that the character reacts hostile to the player and 20% chance that he is not. While this might be fine in many cases, there might be situations where such “dumb” randomness leads to quite absurd behaviors. So the random weights would need to be adjusted to the situation, which in itself is a very hard job.

Copycat also makes extensive use of randomness, i.e. every time it picks the next Codelet to execute it will do so randomly – weighted but still random. But this randomness happens at a very low level. As can be seen in Copycat the top level behavior is much more stable – if there is one obvious behavior, it will pick that quite deterministically. Only if there are multiple conflicting behaviors which are valid reactions to the situation, each one will have a certain probability to win (if you repeat the decision making process multiple times with the same input, it will pick decision A_i with probability p_i). But these probabilities are highly dynamic, depending on the input, and will (hopefully) always lead to decisions that “make sense” in the given situation. And the probabilities are not defined in advance by the programmer but a result of the interactions of the different Codelets as the system comes to a conclusion.

The problem of Game AI

This is the second part of the thread I started in The Coderack and Codelets, which was a brief and probably incomprehensible introduction to the Copycat architecture. Now I want to look at the actual problems that I want to solve, i.e. the problems and limitations of Game AI as it exists today.

Consider are fairly typical but complex situation that a good Game AI should be able to handle: a group of warriors that does an ambush on a bandit’s lair. As the battle evolves each character AI has to perform a number of tasks (in no specific order):

• Path finding: don’t run into trees or get trapped in a dead end.
• Group movement: the group should stay in formation, warriors should not get singled out and become easy prey for the enemy, and gaps in the formation should quickly be closed so the enemy cannot break through and split the group.
• Battle: well, fight for you life or you’ll be dead.
• Communicate: listen to orders and adjust behavior, or react to a comrade’s call for help.
• Situation assessment: where are the enemies, who should I attack?

The biggest challenge is to make these tasks interact properly. For realistic behavior the fact must be acknowledged that each character has just a limited “cognitive capacity.” Let’s look at an example:

A character that is busily defending himself against two enemy fighters will not turn around to help a comrade, he might not even hear (or better: have the mental capacity to process) his call. His movement is mostly determined by the battle and his enemies, so his path finding is reduced to hold position or retreat – and he has no time to look around to realize that the direction is he moving to is a deadly dead end. Once his enemies are defeated the character is able to spend more cycles on other actions, like looking where the battle has taken him, reassessing the situation, regrouping, looking for new enemies to attack or noticing the archer hiding on a roof.

These are just the most obvious tasks which are directly related to a combat situation. Characters have much more behaviors which – on first sight – are not related to combat. For example taking shelter when it is raining, because getting wet is somewhat unpleasant. This is of course a behavior that should be suppressed while fighting. But what if it is a pitch black night and the torch in his hand is the only source of light? Letting the torch get extinguished would be suicide, so in some circumstances seeking shelter from rain can make sense even in the middle of a fight.

And a combat situation is one of the easiest things to handle, because of its nature only short term and tactical decisions have to be made. Dialogs or strategic decisions are much harder because they can be influenced by all previous player actions. Traditional system quickly reach their limits here, for example I encountered several situations in games like Oblivion or Fallout 3 where I completed quests in an order that was not anticipated by the designers and the dialogs conflicted with my previous interactions with certain characters.

Many, many rules will not apply or get activated in any situation, but there’s no a priori way to sort out unneeded rules. At any given point the whole repertory of behaviors as well as the full range of sensory input the character gets from his environment has to be considered by the AI engine. Selecting a subset in an “intelligent” way just moves the problem to another layer without reducing the complexity. And just applying some simple heuristics to cut down the complexity leads to strange and nonsensical actions and discontinuities in behavior (which can often be seen is current titles).

The point is that the complexity of the problem growth exponentially with the wealth of rules and behaviors that the characters have. And for more realistically behavior of characters you want a lot of rules. The current state-of-the-art AI architectures, which build on rather rigid algorithms (finite state machines, decision trees, etc.), become very hard to maintain and their runtime characteristics go down the drain when faced with this combinatorial explosion.

After this short exploration of what is problem is, let me try to explain why I think the Copycat architecture could solve these issues.

The Coderack and Codelets

I haven’t done anything substantial over the last few weeks, so I’ll just continue with my meaningless ramblings about a system that lacks any kind of clue if it is anywhere near feasibility. Originally I started this as one big post covering several topics, but now it is sitting here for two weeks at least as a draft, every few days I add some sentences and it still keeps on growing. So I’ll split it up into several posts and this is the first section.

I already talked a bit about Copycat and how its architecture could be used in games. Let me now try to explain this a bit more. A central component of the Copycat architecture is the Coderack and its Codelets, and I believe that it can be used to efficiently manage AI rules and subsystems even without designing a sophisticated cognitive model for the “Computer Game” domain. (The point of the Copycat project was to design such a model and validate that it actually works. I will simply ignore that fact and just use the underlying software architecture for my own purposes.) I will explain later what I believe the problem of current Game AI is and how the Coderack architecture could solve it – let me first try to explain what it is and how it works.

Codelets are small pieces of code that perform a simple function. Usually a single Codelet only implements a small step of a larger process and creates another Codelet that continues where the first Codelet stopped. In the case of Copycat such a ‘larger process’ could be recognizing the group of letter ABC as a successor group.

But the way that the Codelets are executed is not just sequentially running the steps of predefined processes – we wouldn’t need some special architecture for that. Instead Codelets are put onto the Coderack, each one with a certain priority. At each step a single Codelets is randomly, but weighted by priorities, chosen from the Coderack and executed. If the Codelet generates new followup Codelets, it can decide which priority they should have, i.e. it should decide how important or promising the followup action is and how much resources the system should spend on pursuing that path.

As a more concrete example take an imaginary path finding algorithm. Each Codelet implements a specific function of the algorithm, e.g. finding all possible steps that can be made from the start position and generate followup Codelets for each of them, with a priority based on some metric how close it gets me to the end position. High priority Codelets a chosen more often from the Coderack, so if the direct path is unobstructed, mostly those Codelets will be executed that build that path and just a little bit of CPU time is spend on exploring non-direct paths. But if the initially high priority Codelets die out, because they got stuck in a dead end, the algorithm will automatically move on to explore a lower priority path, while still avoiding the even lower priorities.

It is important to understand that this is not just a priority queue, which only picks on the highest priority item, while completely ignoring the rest. Because of the randomization a small amount of CPU time is given to low priority Codelets, so it is a bit more like a process scheduler that divides the available CPU time to various processes proportional to their priorities. But then it is not a classical process scheduler, because there are no real processes in the system. A certain sequence of Codelets could be seen as a micro-process, but there is nothing that is comparable with OS processes/threads, which are very long (by Codelet’s standards) sequences of steps that are execute from the beginning to the end.

I am not sure if this explanation makes any sense to my humble readers. If not (or if it does and you want to learn more about it), I refer you to the book Fluid Concepts and Creative Analogies: Computer Models of the Fundamental Mechanisms of Thought by Douglas R. Hofstadter. For now let’s move on to the problem that I am trying to solve.

Sign of life

Almost two month without a post. Did I mention that I suck at blogging?
I will not promise to do a better job from now on, because I know the chances are high that this won’t happen…
Didn’t I read somewhere that most blogs are dead or just have posts with excuses for no real updates?