Robust and Authorable Multiplayer Storytelling Experiences

Interactive narrative systems attempt to tell stories to players capable of changing the direction and/or outcome of the story. Despite the growing importance of multiplayer social experiences in games, little research has focused on multiplayer interactive narrative experiences. We performed a preliminary study to determine how human directors design and execute multiplayer interactive story experiences in online and real world environments. Based on our observations, we developed the Multiplayer Storytelling Engine that manages a story world at the individual and group levels. Our flexible story representation enables human authors to naturally model multiplayer narrative experiences. An intelligent execution algorithm detects when the author’s story representation fails to account for player behaviors and automatically generates a branch to restore the story to the authors’ original intent, thus balancing authorability against robust multiplayer execution.

Read the paper:

Robust and Authorable Multiplayer Storytelling Experiences

by  Mark Riedl, Boyang Li, Hua Ai, Ashwin Ram

in Seventh International Conference on AI and Interactive Digital Entertainment (AIIDE-2011).

www.cc.gatech.edu/faculty/ashwin/papers/er-11-06.pdf

User-Generated AI for Interactive Digital Entertainment

User-generated content is everywhere: photos, videos, news, blogs, art, music, and every other type of digital media on the Social Web. Games are no exception. From strategy games to immersive virtual worlds, game players are increasingly engaged in creating and sharing nearly all aspects of the gaming experience: maps, quests, artifacts, avatars, clothing, even games themselves. Yet, there is one aspect of computer games that is not created and shared by game players: the AI. Building sophisticated personalities, behaviors, and strategies requires expertise in both AI and programming, and remains outside the purview of the end user.

To understand why Game AI is hard, we need to understand how it works. AI can take digital entertainment beyond scripted interactions into the arena of truly interactive systems that are responsive, adaptive, and intelligent. I discuss examples of AI techniques for character-level AI (in embedded NPCs, for example) and game-level AI (in the drama manager, for example). These types of AI enhance the player experience in different ways. The techniques are complicated and are usually implemented by expert game designers.

I argue that User-Generated AI is the next big frontier in the rapidly growing Social Gaming area. From Sims to Risk to World of Warcraft, end users want to create, modify, and share not only the appearance but the “minds” of their characters. I present my recent research on intelligent technologies to assist Game AI authors, and show the first Web 2.0 application that allows average users to create AIs and challenge their friends to play them—without programming. I conclude with some thoughts about the future of AI-based Interactive Digital Entertainment.

CMU Robotics & Intelligence Seminar, September 28, 2009
Carnegie-Mellon University, Pittsburgh, PA.

MIT Media Lab Colloquium, January 25, 2010
Massachusetts Institute of Technology, Cambridge, MA.

Stanford Media X Philips Seminar, February 1, 2010
Stanford University, Stanford, CA.

Pixar Research Seminar, February 2, 2010

Try it yourself:

• The social gaming application is at: http://MakeMePlayMe.com and is free to play!
• The AI engine (based on real-time case-based reasoning) is open source for non-commercial use: https://sourceforge.net/projects/darmok2
• Games are at: https://sourceforge.net/projects/mmpmgames and it’s easy to contribute your own.

Learn more about the algorithms:

• Planning: http://cognitivecomputing.wordpress.com/2009/01/20/on-line-case-based-planning
• Learning: http://cognitivecomputing.wordpress.com/2009/07/12/learning-from-human-demonstrations-for-real-time-case-based-planning

View the talk:

www.sais.se/blog/?p=57

View the slides:

Run-Time Behavior Adaptation for Real-Time Interactive Games

Intelligent agents working in real-time domains need to adapt to changing circumstance so that they can improve their performance and avoid their mistakes. AI agents designed for interactive games, however, typically lack this ability. Game agents are traditionally implemented using static, hand-authored behaviors or scripts that are brittle to changing world dynamics and cause a break in player experience when they repeatedly fail. Furthermore, their static nature causes a lot of effort for the game designers as they have to think of all imaginable circumstances that can be encountered by the agent. The problem is exacerbated as state-of-the-art computer games have huge decision spaces, interactive user input, and real-time performance that make the problem of creating AI approaches for these domains harder.

In this paper we address the issue of non-adaptivity of game playing agents in complex real-time domains. The agents carry out run-time adaptation of their behavior sets by monitoring and reasoning about their behavior execution to dynamically carry out revisions on the behaviors. The behavior adaptation approaches has been instantiated in two real-time interactive game domains. The evaluation results shows that the agents in the two domains successfully adapt themselves by revising their behavior sets appropriately.

Read the paper:

Run-Time Behavior Adaptation for Real-Time Interactive Games

by Manish Mehta, Ashwin Ram

IEEE Transactions on Computational Intelligence and AI in Games, Vol. 1, No. 3, September 2009

www.cc.gatech.edu/faculty/ashwin/papers/er-09-09.pdf

Using Meta-Reasoning to Improve the Performance of Case-Based Planning

Case-based planning (CBP) systems are based on the idea of reusing past successful plans for solving new problems. Previous research has shown the ability of meta-reasoning approaches to improve the performance of CBP systems. In this paper we present a new meta-reasoning approach for autonomously improving the performance of CBP systems that operate in real-time domains.

Our approach uses failure patterns to detect anomalous behaviors, and it can learn from experience which of the failures detected are important enough to be fixed. Finally, our meta-reasoning approach can exploit both successful and failed executions for meta-reasoning.

We illustrate its benefits with experimental results from a system implementing our approach called Meta-Darmok in a real-time strategy game. The evaluation of Meta-Darmok shows that the system successfully adapts itself and its performance improves through appropriate revision of the case base.

Read the paper:

Using Meta-Reasoning to Improve the Performance of Case-Based Planning

by Manish Mehta, Santi Ontañón, Ashwin Ram

International Conference on Case-Based Reasoning (ICCBR-09), Seattle, July 2009

www.cc.gatech.edu/faculty/ashwin/papers/er-09-06.pdf

Learning from Human Demonstrations for Real-Time Case-Based Planning

One of the main bottlenecks in deploying case-based planning systems is authoring the case-base of plans. In this paper we present a collection of algorithms that can be used to automatically learn plans from human demonstrations. Our algorithms are based on the basic idea of a plan dependency graph, which is a graph that captures the dependencies among actions in a plan. Such algorithms are implemented in a system called Darmok 2 (D2), a case-based planning system capable of general game playing with a focus on real-time strategy (RTS) games. We evaluate D2 with a collection of three different games with promising results.

Read the paper:

Learning from Human Demonstrations for Real-Time Case-Based Planning

by Santi Ontañón, Kane Bonnette, Praful Mahindrakar, Marco Gómez-Martin, Katie Long, Jai Radhakrishnan, Rushabh Shah, Ashwin Ram

IJCAI-09 Workshop on Learning Structural Knowledge from Observations, Pasadena, CA, July 2009

www.cc.gatech.edu/faculty/ashwin/papers/er-09-04.pdf

On-Line Case-Based Planning

Some domains, such as real-time strategy (RTS) games, pose several challenges to traditional planning and machine learning techniques. In this paper, we present a novel on-line case-based planning architecture that addresses some of these problems. Our architecture addresses issues of plan acquisition, on-line plan execution, interleaved planning and execution and on-line plan adaptation. We also introduce the Darmok system, which implements this architecture in order to play Wargus (an open source clone of the well-known RTS game Warcraft II). We present empirical evaluation of the performance of Darmok and show that it successfully learns to play the Wargus game.

Read the paper:

On-Line Case-Based Planning

by Santi Ontañón, Neha Sugandh, Kinshuk Mishra, Ashwin Ram

Computational Intelligence, 26(1):84-119, 2010.

www.cc.gatech.edu/faculty/ashwin/papers/er-09-08.pdf
www3.interscience.wiley.com/journal/123263882/abstract

Stochastic Plan Optimization in Real-Time Strategy Games

We present a domain independent off-line adaptation technique called Stochastic Plan Optimization for finding and improving plans in real-time strategy games. Our method is based on ideas from genetic algorithms, but we utilize a different representation for our plans and an alternate initialization procedure for our search process. The key to our technique is the use of expert plans to initialize our search in the most relevant parts of plan space. Our experiments validate this approach using our existing case based reasoning system Darmok in the real-time strategy game Wargus, a clone of Warcraft II.

Read the paper:

Stochastic Plan Optimization in Real-Time Strategy Games

by Andrew Trusty, Santi Ontañón, Ashwin Ram

4th Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE-08), Stanford, CA, October 2008

www.cc.gatech.edu/faculty/ashwin/papers/er-08-09.pdf

Real-Time Plan Adaptation for Case-Based Planning in Real-Time Strategy Games

Case-based planning (CBP) is based on reusing past successful plans for solving new problems. CBP is particularly useful in environments where the large amount of time required to traverse extensive search spaces makes traditional planning techniques unsuitable. In particular, in real-time domains, past plans need to be retrieved and adapted in real time and efficient plan adaptation techniques are required.

We have developed real-time adaptation techniques for case-based planning and specifically applied them to the domain of real-time strategy games. In our framework, when a plan is retrieved, a plan dependency graph is inferred to capture the relations between actions in the plan suggested by that case. The case is then adapted in real-time using its plan dependency graph. This allows the system to create and adapt plans in an efficient and effective manner while performing the task.

Our techniques have been implemented in the Darmok system, designed to play WARGUS, a well-known real-time strategy game. We analyze our approach and prove that the complexity of the plan adaptation stage is polynomial in the size of the plan. We also provide bounds on the final size of the adapted plan under certain assumptions.

Read the paper:

Real-Time Plan Adaptation for Case-Based Planning in Real-Time Strategy Games

by Neha Sugandh, Santi Ontañón, Ashwin Ram

9th European Conference on Case-Based Reasoning (ECCBR-08), Trier, Germany, September 2008

www.cc.gatech.edu/faculty/ashwin/papers/er-08-06.pdf

Situation Assessment for Plan Retrieval in Real-Time Strategy Games

Case-Based Planning (CBP) is an effective technique for solving planning problems that has the potential to reduce the computational complexity of the generative planning approaches. However, the success of plan execution using CBP depends highly on the selection of a correct plan; especially when the case-base of plans is extensive.

In this paper we introduce the concept of a situation and explain a situation assessment algorithm which improves plan retrieval for CBP. We have applied situation assessment to our previous CBP system, Darmok, in the domain of real-time strategy games. During Darmok’s execution using situation assessment, the high-level representation of the game state i.e. situation is predicted using a decision tree based Situation-Classification model. Situation predicted is further used for the selection of relevant knowledge intensive features, which are derived from the basic representation of the game state, to compute the similarity of cases with the current problem. The feature selection performed here is knowledge-based and improves the performance of similarity measurements during plan retrieval. The instantiation of the situation assessment algorithm to Darmok gave us promising results for plan retrieval within the real-time constraints.

Read the paper:

Situation Assessment for Plan Retrieval in Real-Time Strategy Games

by Kinshuk Mishra, Santi Ontañón, Ashwin Ram

9th European Conference on Case-Based Reasoning (ECCBR-08), Trier, Germany, September 2008

www.cc.gatech.edu/faculty/ashwin/papers/er-08-07.pdf

On-Line Case-Based Plan Adaptation for Real-Time Strategy Games

Traditional artificial intelligence techniques do not perform well in applications such as real-time strategy games because of the extensive search spaces which need to be explored. In addition, this exploration must be carried out on-line during performance time; it cannot be precomputed. We have developed on-line case-based planning techniques that are effective in such domains. In this paper, we extend our earlier work using ideas from traditional planning to inform the real-time adaptation of plans. In our framework, when a plan is retrieved, a plan dependency graph is inferred to capture the relations between actions in the plan. The plan is then adapted in real-time using its plan dependency graph. This allows the system to create and adapt plans in an efficient and effective manner while performing the task. The approach is evaluated using WARGUS, a well-known real-time strategy game.

Read the paper:

On-Line Case-Based Plan Adaptation for Real-Time Strategy Games

by Neha Sugandh, Santi Ontañón, Ashwin Ram

23rd AAAI Conference on Artificial Intelligence (AAAI-08), Chicago, IL, July 2008

www.cc.gatech.edu/faculty/ashwin/papers/er-08-04.pdf