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.