The Game That Never Was

Links 2009-12-29

• Winning the 2K Bot Prize with a Long-Term Memory Database using SQLite (AiGameDev.com):
  

  Most AI systems in the games industry focus on short-term reactive memory and combat behaviors applying techniques such as behavior trees. However, there seems to be little support for long-term memory, for example remembering locations in space that mark events that occurred. In our daily lives, we internally map, model and remember our surroundings and experiences. This begs the question, how can we similarly organize and leverage longer-term memory within modern AI?

Links 2009-11-24

• Die fade Fassade (Kommentar, 4players.de, German):
  

  Wieso hockt meine Mutter jahrelang (!) in ein- und derselben Position vor ihrem Bett? Wieso kann ich mich buchstäblich vor der Nase von drei Wachen in den direkt daneben befindlichen Eingang schleichen? Warum spazieren nachts ebenso viele Menschen in den Städten herum wie am Tag?

Representing conflicting states in the Workspace

One of the characteristics of Copycat is the ability to pursue alternate or conflicting views of its domain, although in a limited way only. When Codelets build up structures (groupings of and relations between entities) in the Workspace these structures go through “states,” from possible over proposed to established. There can be only one set of established, non-conflicting structures.

For example with three entities A, B and C, Copycat might first create the group G1={A, B}. Another sequence of Codelets might build up the conflicting (because each entity can only be direct member of one group) group G2={A, B, C}. In order to establish G2 the group G1 has to be torn down, but G2 can coexist with G1 as long as it is in proposed state.

This way Copycat can explore alternatives that conflict with the current view, but might turn out to be better. But the conflicting structures have to compete at a very low level. In the simple case above can easily measure that group G2 is superior to G1 and thus decide to tear down G1 in favor of G2. But in more complicated scenarios an alternative group G2' could seem less promising at first, but once it has been constructed it opens the possibility for a very complex structure which could not be built with G1. This makes Copycat kind of shortsighted, i.e. the presence of G1 suppresses groups which are scored lower than G1 if compared directly to it, but might act as a first part of a more complex structure.

Tabletop seems to have the ability to remember structures and when it explores an alternative that turns out to be a dead end, it can go back to the remembered structure. This way it can be more open to alternatives than Copycat. But I don’t know how this was implemented in Tabletop, because I have not yet read anything more detailed about it.

Last night, while lying in bed waiting for the sandman to come around, my brain was spinning around this and looking for ways to improve the situation. One possible option could be the introduction of “Branches” in the Workspace, which would be a generalization of the “snapshot” feature that Tabletop seems to have. Each Branch is a Workspace in the Copycat sense, but now the Workspace can contain multiple “sub Workspaces.” Each time a Codelet wants to establish a conflicting structure in a Branch, this Branch is forked and the alternative can be explored without interfering with the existing Branch. Now Branches would compete against each other instead of lower level structures. Each Branch gets a score and if one Branch falls behind too much, it is discarded.

There a various ways how this could be implemented. All Branches could be active at any time, which means that the processing capacity has to be shared by all Branches. This makes branching very expensive, so a mechanism that limits the number of Branches is required. The expected value of a proposed structure has to greater than a threshold value before it can be established – this is a mechanism that already exists in Copycat as it is now. If the structure now conflicts with other structures, a penalty is added to this value which is based on the number of existing branches, so it become very unlikely that a new Branch is created when already many Branches exist.

Another option would be to have only one Branch active at a time and every once in a while the system decides if it should switch to another Branch. Or it might shard its attention to all Branches based on the Branch’s scores, with a very large skew towards the highest score – but still leaving some attention to lower scored Branches.

Just an idea…

Workspace and Slipnet

There are some parts of the Copycat architecture that I haven’t touched yet. Namely the Workspace and the Slipnet. That’s mostly due to the fact that I don’t yet know, how they would fit into the system as I envision it. In some way the Workspace is the short term memory of the system and the Slipnet is the long term memory. But only in some way and I think both cannot that easily reused from Copycat as Codelets and the Coderack.

In Copycat the Slipnet is a network of nodes that is not unlike other networks, i.e. typical neural network implementations. Nodes have activation levels and this activation spreads to connected nodes. But unlike a pure neural network “brain,” the Slipnet is not the place where the main action happens. Instead the nodes and their connections capture the (abstract) knowledge that the system has about the domain and the activation levels reflect what Copycat currently considers as important. Highly activated nodes can spawn Codelets, e.g. if the node “successor” is activated, it may spawn Codelets that actively search for more successor groups. Information flows in the other direction by Codelets that do discovers certain structures and then add some activation to the corresponding node (some generic search Codelets are constantly spawned and if they find something they activate a node – which then triggers more targeted Codelets looking for things like that).

The Slipnet in Copycat is (apart from the activation levels) completely static. So it’s not really “memorized memories,” because it has no way to learn, but more “a priory knowledge.”

The workspace is the place where Copycat builds up the structures and representations of its domain. It is a highly dynamic network of nodes, which is constantly modified by the Codelets. It also has some properties that make it very different from the network of the Slipnet (or neural networks). Connections are built up in several stages, i.e. they are first “proposed” and only later (if they survive long enough) “established.” And while two nodes can only be connected by one established connections, there might exist other, contradicting connections at the same time, which are still in the proposed state. That means that Copycat can build up and evaluate an alternate view of the domain without replacing the current view right away, but only when the new view seems better that the old.

The Workspace is also able to build up hierarchic structures of groups and treat those groups as nodes to operate on.

Both of these components need some changes to be used in a NPC brain. There definitely needs to be some notion of learning and memory. The lack of memory is one of the biggest issues I see in current Game AI (it is somewhat emulated by scripting, but in a very limited way). The Slipnet in Copycat only contains very abstract knowledge, e.g. characteristics of platonic letters and such things (instantiations of letters only exist in the Workspace). So putting knowledge like “Fred has red hair and owes me 20 bucks” in there is a very different thing.

The Workspace will also need some adaptions for my use of it. For example spatial information is one important domain that needs to be represented, so a character can find its way around the world and correctly react to its environment. And there are many other things that need modeling, e.g. relations with other characters, dialogs, etc.

I will have to spend much more time thinking about these things. But I’ll leave that for another day (not implying that I could even scratch the surface on a single day).

Links 2009-11-01

• Artificial Intelligence and the Future of Games as an Expressive Medium (Youtube):
  

  Artificial intelligence methods open up new possibilities in game design, enabling the creation of believable characters with rich personalities and emotions, interactive story systems that incorporate player interaction into the construction of dynamic plots, and authoring systems that assist human designers in creating games. Games are fast becoming a major medium of the 21st century, being used for everything from education, to editorial news commentary, to expressing public policy and political opinions. Game AI research can radically expand the expressiveness of games, supporting them in becoming a mainstream medium for societal discourse. These ideas will be illustrated by looking at two projects: the interactive drama Façade (released July 2005, downloadable from www.interactivestory.net) and current work on automated game design support.

• Belief-Desire-Intention software model (Wikipedia):
  

  [...] is a software model developed for programming intelligent agents. Superficially characterized by the implementation of an agent’s beliefs, desires and intentions, it actually uses these concepts to solve a particular problem in agent programming. In essence, it provides a mechanism for separating the activity of selecting a plan (from a plan library) from the execution of currently active plans. Consequently, BDI agents are able to balance the time spent on deliberating about plans (choosing what to do) and executing those plans (doing it). A third activity, creating the plans in the first place (planning), is not within the scope of the model, and is left to the system designer and programmer.

• Automated Support for Game Design (Youtube – more detailed version of the second part of the first talk above):
  

  Game designers currently have no formal, abstract tools or representations they can use to reason about designs in progress. This talk describes research in the Expressive Intelligence Studio at UC Santa Cruz that seeks to build systems that can reason about the consequences of and interactions between game design mechanics, as well as make heuristic game design suggestions. Michael and his team have identified four different design domains that interact during game design, the thematic, abstract mechanics, game state representation, and input mapping domains, and seek to provide semi-automated and automated support to assist with these domains. They have experimented with common-sense reasoning approaches for reasoning about game thematics, and event calculus representations of game mechanics and state representation. This talk provides an overview of the research agenda, present the demo systems they’ve created, and describes the two primary application directions they’re pursuing, namely, design support tools (’CAD for game designers’) and computer creativity systems that discover new and interesting game mechanics.

• ConceptNet 3 – A Semantic Network Representation of the Open Mind Common Sense Project (MIT):
  

  ConceptNet aims to give computers access to common-sense knowledge, the kind of information that ordinary people know but usually leave unstated.
  The data in ConceptNet is being collected from ordinary people who contributed it over the Web. ConceptNet represents this data in the form of a semantic network, and makes it available to be used in natural language processing and intelligent user interfaces.
  

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?

Bubble Tank

One image that formed in my head when thinking about Copycat at al is that of a water tank in which bubbles (the structures which are built up by the codelets) slowly form, shrink, disappear, grow, merge and finally reach the surface when they prove to be big, strong and stable. If the Fluid Analogies model of Copycat is really a valid approximation of what’s going on in hour own head, then this analogy opens up some nice interpretations.

The codelets slowly build structures based on the input – in the case of the human brain, nerve signals from our senses. They make connections, dig up possibly related memories and try to bring this into a coherent state. In the beginning this is very undirected and may produce complete nonsense, later the structures become less chaotic but might still be very far fetched and only when they really make sense they make it to the surface. The surface being the border between unconscious and conscious thinking.

Following the analogy further: what happens if we change some parameters of the system, for example lower or rise the surface or let bubbles rise faster or slower? If it is harder for a bubble to reach the surface – that is a certain interpretation of a situation make it to the conscious mind – then this bubble has to be very stable. The codelets have lots of time to grind away all irregularities and the existing memories enforce their expectations. In other words: boring, conventional and uncreative. And if you turn the wheel into the other direction: unconventional, often wrong, but sometimes there might be a solution that turns out to be very creative.

And if you push the wheel even further? Then you expose the conscious mind with the chaos of half-baked ideas, structures of mostly random connections which only made it to the surface, because they did not have to prove themselves. Which to me sounds very much like a description of paranoia, psychosis or other mental dysfunctions.

As an example: Someone might look into a dark cloudy sky. Add some flashes and distant thunder for the dramatic effect. This visual impression kicks off all kinds of cognitive processes in the subconscious mind. The result that bubbles up to the surface between subconsciousness and consciousness is usually something like “no picnic today, let’s check the movies,” or “where’s my umbrella?” But if the parameters are badly tuned it could also be “the aliens are preparing their invasion.” Or a bit less extreme: “let’s see what happens it a flash strike a kite.” Pretty stupid idea in my opinion, unless you’re a brilliant researcher.

The point is that every mind potentially has those crazy or plain insane ideas, they just don’t make it to the surface, because they loose the race against more conservative and thus more stable structures. Creative minds lower the bar and every once in a while they can find a gem. Insane minds get lost in a cloud of random bubbles that obfuscate their sight (unfortunately it seems to be hardwired into our minds that we willingly trust whatever makes it through the surface).

And here’s what triggered this particular bubble to form in my mind:

We’re all familiar with the stereotype of the tortured artist. Salvador Dali’s various disorders and Sylvia Plath’s depression spring to mind. Now new research seems to show why: a genetic mutation linked to psychosis and schizophrenia also influences creativity.

New Scientist Health, July 16, 2009: Artistic tendencies linked to ’schizophrenia gene’

Via: KurzweilAI.net