vendredi 14 octobre 2011

Anatomy of a Quantum Entity

During the implementation of my retro-causality prototype, I quickly got stuck by the naïve implementation I did for the “collapsing process” of Quantum Entities. An upgrade of this system was urgently needed and I continued to use Quantum Mechanics metaphors to do it.

As a reminder, a Quantum Entity is the root class of nearly everything in DramaticGames. It is an abstract class that is “just” a collection of properties. Contrary to classical objects, each property has several potential values at the same time.

The properties of an Entity are “collapsed” when they are observed. That is to say that when the player does an action that needs a single value of an entity property, the collapsed value is selected randomly amongst the potential values of the property. 

The random selection takes into account the probability of each potential value and, by doing so, allows the DramaManager to influence the outcome of the collapse process.

This collapsing process can be enhanced by remembering the different observations made for a value and by logging them. This logging mechanism allows the DramaManager to later ignore observations at will and creates even more flexibility for influencing the system (what I named the backstage in my other post).

In addition to the collapsing process, another mechanism is necessary to support the previously described retro-causality and entanglement system. This additional mechanism introduces a representation of the interactions in-between entangled entities. 

The handling of those interactions is done by what is called “decoherence” (this is just a metaphor, real Quantum decoherence is calculated differently). Interactions can appear and disappear during the life time of an entity, depending of the DramaManager priorities when trying to realize Intentions.

Finaly, the retro-causality process needs to query the past states of an entity, to be able to check goals’ constraints that are retro-planned in the past (in retro-time). To simplify things, we just consider consolidated short term past and consolidated long term past.

The fact that the past states of an entity are the consolidation of some of his previous potential states brings the notion of potential and flexible past. A notion very important to leverage fully retro-causality.

vendredi 9 septembre 2011

Entanglement and retro-causality

I would like to (try) to explain you the most difficult concept I have recently wrestled with in the context of DramaticGames. That is to say: Entanglement, or keeping causally dependent non-collapsed entities and behaviors in synch.
A definition of entanglement can be found here, but it can be summarized as the link that keeps in synch two non collapsed particles that have potentially interacted with each others. For instance, a non collapsed electron (superposed at multiple places) that potentially have collided and bounced from another non collapsed electron (also in states superposition).  As the two electrons are entangled, when one will collapse by being observed, the other electron will also collapse in a position that, some time, will be influenced by the potential collision that virtually occurred.  Actually, it’s collapsing post synchronization, or a form of retro-causality. This phenomenon is proven experimentally.

To explain entanglement in the context of DramaticGames, we first need to explain what a behavior is. We will take the example of the behavior of the murderer (the Perpetrator) in the context of our previous criminal investigation game example. This behavior could be represented by a classical goal tree as follow:

We see that the murder has a dynamic behavior to “oppose” to the player that investigate the criminal case. This is what I previously named the “Thinking Villain”. This mechanism insures that the game is a dynamic interactive experience and not a static puzzle.

This goal tree example shows a classical reactive behavior, with goals and sub goal triggered by conditions to be matched against the current beliefs of the Perpetrator.  This is the classical way of doing AI.  However, what we want to achieve is completely different; we want to do retro-causality as explained is my previous post: “Does the past exist yet?”.  To do so, we need to implement what I call a “Potential-Goal trees”. Here is the previous reactive-goal tree restated as a potential-goal tree:

Click to enlarge, then save the image for a better viewing experience in an external image viewer

You will notice three changes:
  1. The conditions are now named causes
  2. The leaf goals are named effectors and have an effect definition
  3. Most sub goals have been defined as “generic” goals using goal variables definition. This is not related to retro-causality because, for the sake of generic representation, this is also done in reactive goal trees.

Now, the difficult part is explaining how it all works J
Here is the same potential-goals tree but with a retro-causality process example:

Click to enlarge, then save the image for a better viewing experience in an external image viewer

This is quite difficult to grasp because it is counter intuitive.  The good news is that entanglement seems enough to avoid the many world interpretation of Quantum physics that would have been cumbersome to implement in a story world.  It must also be noted that things can get even more complicated when we consider that different potential-goals tree can be entangled together, to represent “joint intentions”, when one character potentially interact with another one.

Before getting to this complexity level, let’s try to implement basic entanglement and retro-causality in a prototype…

samedi 27 août 2011

Sharing research code

I started to set my research code public. This will allow the interested people to understand how I progress on the prototype implementation and how it relates to the ideas exposed in this blog.

The code (under the GNU GPL v3 license) can be found on:

Prototype screenshot

The current prototype is extremely simple and primitive; it’s just a text based key/door puzzles JIT synthesizer. You can just click on buttons to do three possible actions: move to room, pickup keys and open doors. The implicit goal is to visit each room of the house. At each program execution, the doors will be locked differently. The keys’ locations also change at each run. The goal of this prototype was to grasp the first Quantum Physics inspired paradigm to create a JIT synthesizer for the game “opposition”.  I also played a bit with rules (in DramaManager) to increase the interest of the generated puzzles.

This prototype is implemented in Lua and use wxLua as a GUI. If you want to try the prototype, you will have to first install wxLua.  Then launch MainDev.lua from wxlua.exe.  To have it running, you will also have to change the gRootPath in MainDev.lua

Unfortunately, most of the sources are in a flat directory structure. This is done to be able to later use the code on Android devices with, for instance, the Corona SDK.  Actualy, Android constraints directories structure (dixit Corona documentation).  However, it’s possible to see the sources in a directory tree by using the .projet file with the Eclipse IDE.  I recommend Subversive as a way to get the project in Eclipse because other SVN integrations break the virtual folders. There are also plugins for Eclipse to get Lua support. Install Eclispe and the plugins then do an "File->Import->SVN->Project from SVN". You can also use TortoiseSVN to just checkout the sources outside of Eclipse.

In the docs directory, there is a yEd file named Classes.graphml that describes the interesting classes of the system.  The prototype being currently evolving toward most advanced concepts, some “Mind” related classes already exist but are not yet used.

Here is a list of the interesting packages of the project:

  • DevViews implement the wxLua views
  • Reality implements the base classes that use the Quantum Physics metaphor
  • Matter implements classes derived from the ones present in the Reality package to specialize them as physical objects
  • Spirit implements classes derived from the ones present in the Reality package to specialize them as spiritual objects such as Mind…
  • Drama implements the rules to bias the entity collapsing to get a more interesting experience. This is mostly about pace management.
  • Test implements the unit tests

Don’t hesitate to comment this post to ask questions and discuss about ideas.

vendredi 19 août 2011

Does the past exist yet?

Two weeks ago, I finished a first prototype of a key/door puzzles generator using some quantum physics paradigm to drive the states of keys and doors at observation time. This proved me that it was possible to synthesize (JIT) a big part of a game world while keeping it interesting and procedurally generated.

Now, I would like to extend this idea beyond simple key/door puzzles.  To achieve that, i need to add NPC and behaviors to the mix.  The big change is that NPC behaviors imply causality, that is to say: cause and effects.  Here is a causality example in the context of my crime investigation prototype: the murderer NPC wants to steal evidences on the crime scene (cause) but he is spotted by the player that just happen to be also there. The murderer flees (effect).  This simple example shows how the player can use causality reasoning to get clues on the murder and to use them progress in his investigation.  In this example, the NPC that arrives on the crime scene, and that all of a sudden flees, instantaneously becomes suspect for the player.

If we try to implement this example, we will quickly run into a big problem:  
if the murderer NPC have a standard goal oriented IA, how big are the chances that he would arrive on the crime scene to steal evidences when the player just happen to be also there ?  The chances for this coincidence are actually very low.  However, those story-pushing coincidences happen all the time in non interactive stories such as TV series and movies.
In regard to this problem, it’s important to define two notions:

1.       “Player Centricity” is the fact that the interesting events (the murderer fleeing the crime scene) happen when the player is there to observe them and to interact with them.  This is what happens all the time in non-interactive stories and this is what we would like to implement.

2.       “Agent Centricity” is the fact that the NPC AI acts in accordance to their own needs and goals (agency) and not in accordance to what would be the best for the player experience. In our example, chances are high that the murderer NPC would be doing something else when the player decides to quickly visit the crime scene.

Player Centricity is achieved in games by scripting. The “Call of Duty” series being one of the best example of this principle.  Unfortunately, this has to be implemented in a linear way to insure NPC behavior causality chain coherence.

In less scripted games, Agent Centricity allows NPC AI to have coherent “cause and effect” chains in a nonlinear way.  But then, the problem is that very interesting things are done by NPC AIs but are never noticed by any players because those events are not happening while the player is watching. This is one of the most frustrating issues for squad based combat AI developers ;-)

For DramaticGames, what I would like to implement, is a mix of both Player Centricity and Agent Centricity.  Here is how it could work:

  1. Each NPC has a special AI that generates all the simplified plausible behaviors that they can potentially have at the current moment, while they are not observed. This Potentiality-AI generates a “potentiality tree” quite similar to traditional AI goal trees.  The main difference is that all the “plausible” behavior’s branches stay active at the same time.  In our example, that means that our murderer NPC potentially does many things at the same time to vindicate oneself when he is not observed by the player.  For instance: hide, corrupt or frighten witnesses, steal evidences on the crime scene, etc…  All that, "happening" in parallel (thanks to Quantum states superposition).

  2. The DramaManager AI changes the probabilities of some potential NPC’s behaviors in accordance to the player context and to predefined dramatic rules.  In our example, the DramaManager strongly increase the probability of the murderer potential behavior that consist of stealing evidences on the crime scene when the player arrives there.

  3. When the player interact with the story world, the entity he interact with “collapse” (in the Quantum Physics way of thinking).  In our example, when the player arrive on the crime scene, the system looks at all NPC potential behaviors that involve the crime scene and “collapse” them as being the current NPC behavior or not.  The criterions to collapse a behavior depend of a statistical selection process (random driven) integrating the probability weights set by the DramaManager AI.

  4.  If a behavior collapsed as being the current one for an NPC, the NPC Potentiality-AI is temporarily mutated into a classical Reactive-AI.  This allows the NPC to interact in a regular way with the player that now observes him.  During the AI mutation, the collapsed potentiality branch is expanded as the current goal branch of the standard Reactive-AI. 

    On a side note, the mutation of potential past behaviors into a real present behavior inspired the title of this post:  ”Does the past exist yet?”.  Indeed, the described mechanism maintains all the plausible NPC simplified pasts and “chooses” one at observation time to expand it, thus defining the NPC in present time.  If we integrate the fact that the DramManager AI biased the weights of the past behavior possibilities to insure the present behavior it preferred, then this can be seen as an approximation of retro-causality.

  5. Finally, each NPC that are in Reactive-AI mode will be mutated back in Potentiality-AI mode after a given time of non-observation by the player.   So, the system must be capable to do bidirectional translations between simplified Potentiality-AI and expanded Reactive-AI.

I think that the superposition of unseen NPC behaviors creates a kind of “behavioral and causality backstage”. This allows us to implement a DramaManager that is “free” to bias NPC behaviors in the back of the player.  This allows us to mix and statistically arbitrate Player Centricity with Agent Centricity.

This seems to be an interesting paradigm to test. However, things can rapidly grow in complexity, especially when the potential behaviors involve NPC to NPC interactions and relationships.  But the good news is that now, we have a lead to reconcile player autonomy and experience intensity…

jeudi 11 août 2011

Criminal investigation tycoon

In my previous posts, I speak a lot about what I call the “story engine”.  It must be noted that this engine is just a design metaphor and have nothing to do with runtime game engines.  The story engine can be seen as what Dramatica names the “Overall Story Throughline”; or what McKee names the “Central Plot”. This is the backbone structure of the player experience. The goal is to have the player know what he has to do to push the story forward.

The best way to explain what I mean by “story engine” is to show an example diagram. In this case, the example depicts a murder investigation “dramatic game” (that will be my first implementation prototype):

It is important to notice that the story engine is an abstract model of the player experience. It doesn’t specify the name nor the number of entities (objects, characters, locations, information…) nor the order of the needed interactions.  The transformation of this abstract model into a concrete experience is done at player observation & interaction time, by the “quantum uncertainty” inspired system. This system use control rules to collapse the possibilities into a unique reality. This paradigm insure, amongst other things, the player freedom (order of actions) and the optimality of the dramatic experience (player centricity).

The story engine is a real gameplay system. The most prominent feature demonstrating that, is the “proofs points” system.  Indeed, the player has to accumulate “proofs points” from different sources to pass a given threshold where the Judge will decide to incriminate the given suspect and thus end the game in a winning condition.  It must be noted that it doesn’t exist a losing condition.  The player can continue as long as he wants to gather proofs points.  The proofs points also support the non linearity of the experience because they can be gathered in any order, and this from the source that the player will want to focus on.  

As this model mostly involve non physical entities (information, relationships, investigation states, …), it is extremely important to find a proper way to render those concepts to the player. To achieve this, I think that I will use an elaborated dashboard system that will display all the immaterial concepts.  This dashboard will include a structured notepad that will automatically log known information. It will also feature detailed and specific reports. Finally, it will include a big board that will show all the characters and objects with their respective relationships (as in real criminal investigations).

Another important problem to handle is the difficulty level of the experience. That’s why, at the beginning of the game, the player will select his desired level of difficulty.  This difficulty level will be used by the “uncertainty collapsing” mechanism to control the deepness of dependencies and the number of entities in the game.

This “crime investigation model” is quite simple but, with time, will be extended to include: victim body searching, complicities, denunciations, lies, secondary murders or kidnapping to eliminate witnesses, evasions, evidences stealing or destruction, political game, witness reversal, etc…  As TV criminal dramas show, this field is quite vast.  The story engine will also try to add a maximum of NPC behavior triggering, to leverage the information-relationship-behavior economy.

The specificity of this story engine approach is that it deeply simulates a domain specific model. It doesn’t rely on a story surface generative grammar.   Even if we can nearly feel the experience as an episode of “Law & Order” :-)   this model does not yet produce dramatically interesting experiences. To achieve that, we will have to include many other key elements, such as: interesting key characters, a “thinking villain”, some interesting conflicts, a lot of emotions and last but not least: meaning.  But now, we have a nice support for all these things…

samedi 6 août 2011

Toward a behaviors economy

One of the main challenge to tackle to achieve a dramatically interesting game is to extend the classical object economy found in games. Here is a simplified diagram that represents such an object economy:

Click to enlarge

Off course, object economies are far more elaborated in current games. They also include some information and behavior economies.

Here is what I will try to implement for my DramaticGames experiment:

Click to enlarge

The huge difference with economies found in current games is the fact that this one is generalized; this means that the DramaManager AI can manipulate it as it wants to enhance the player experience.

Another difference is the fact that relationships and the way to change them are multiple. So, the goal of the game is not finding how to get the good actuator but: what actuators will be the best ones and why?

This economy is just one part of the equation. The other part is the “thinking” villain, the dynamic opposition that will transform the experience from being a puzzle to being a competition with the game antagonist…

mardi 26 juillet 2011

The goals...

A lot of fantasies are anticipated when we start to talk about interactive storytelling. This is why I think it’s important to clarify the goals of such an approach. Here is my personal opinion on the subject. Let’s start by what I think are the goals to avoid:
  • Interactive story telling is not about player expressiveness. It doesn’t have to insure that the player will be able to do a lot of different things, as in real life.
  • Interactive story telling is not about player free will, it's not about open ended game play and it’s not about multiple possible endings.

Even if expressiveness and player free will are needed to support an interactive story, they are means and not goals.  This relaxes a lot of the pressure often put on those features. This allows the designer to include just the minimum of player expressiveness and player free will to support the true goals.

I think that the most important goals of interactive storytelling are:
  • Having the players feel ”first person emotions”.
  • Having the players freely explore a given theme.

By first person emotions, I mean emotions that the player feels because of his own acts and his own decisions. Emotions that are generated thanks to non-playing characters that adapt their behaviors around the values that the player exhibit when he play the experience.  Off course, the point is to have the player makes decisions as often as he can, not at given forking points in a predefined plot.

First person emotions are in opposition to emotions generated by cinematics because prerecorded cinematics freeze the causes of the emotions and by doing so; put the player out of the causality chain and ultimately out of the experience.  Prerecorded scenes only offer emotions that we can feel by empathy.  In my opinion, “1st person emotions” are far more powerful than empathic emotions and if we consider that emotions generation is what can qualifies an art form, we have to focus our efforts there. 
Here is a good essay on the different level of emotions

The second goal that i propose is about allowing the player to interactively explore all the facets of a given theme. That’s means that the elements of the story world have to allow the player to make choices that will push him to think about a given theme. He has to be able to think about the chosen theme thanks to the consequences of his own acts.  In that sense, an interactive story is a way of storing an interactive discussion between the author and the players (has holograms store a 3d image). This discussion between the author and the players doesn’t specially have to be moralizing, but it can. As in other Medias, it’s up the author to choose his position on the subject.

Both those two goals complement each others very well. Indeed, emotions are a way to give feedback to the player to allow him to feel the consequence of his act. And exploring a theme also serves as a fertilizer for emotion generation.

You will have maybe noticed that in this post, I often use the word “play”. This is because I think that, in the end, an interactive storytelling experience must be designed as a game.

Designing an interactive storytelling experience as a game allows us to use proven design principles. It also gives us an important ingredient: what is sometime named a “story engine”. That is to say, something that motivates the player in the long run and that will drive him during the experience.  
The story engine can be seen as what Dramatica ( names the “Overall Story Throughline”; or what McKee ( names the “Central Plot”.  The story engine is the support that fixes other story “threads”, where emotions generation and theme exploration can be fully implemented. 

The story engine also offers many decision points, to allow the player to exhibits his values (the system has to progressively make a model of him). All those decision points (for instances, the way he build something over the course of the game) are exactly what we need to implement 1st person emotions and theme exploration.

Some of the previous attempts to create interactive storytelling systems shared the same goals as the ones I listed but they failed.  In my opinion, it’s maybe because they were attempting to do something else than a game.

This vision now explains the term “Dramatic games” that I really prefer over the term “interactive storytelling” that embed too much paradox to my taste.

Now, even if it’s about games, it’s about games with a very different pallet of emotions and themes than usual, and that still is a long way to go…