Adaptive AI Engine for RTS Games

Discussing the theory and practice

Author Archive

Example of situation assessment for case retrieval

Posted by Ahmad Atta on December 3, 2009

Posted in Case-Based Planning, Presentations | Tagged: , , | Leave a Comment »

Situation Assessment for Plan Retrieval

Posted by Ahmad Atta on December 2, 2009

Traditionally, in Case-Based Reasoning the process of case retrieval is done by selecting the case from the case-base that has the closest similarity to the world state of the problem. This similarity is measured over the various features that are computed from the representation of the world state.

Omar asked “How will you determine the importance of a feature?”

This paper : Situation Assessment for Case Retrieval by Kinshuk Mishra, Santiago Ontan˜on, and Ashwin Ram answers this question as follows:

The importance of features depends on their relevance in representing the high-level world state, this is high level game state is defined here as a Situation. For example, in the WARGUS domain the player might be in an attacking situation, or in a base building situation among others. Situations can be predicted based on the raw features that are directly computed from the world state i.e. shallow features.

THUS, Situation assessment is a process of gathering high-level information using low-level data to help in better decision making.

The general situation assessment algorithm is described in Figure 3. It comprises of four main steps:

1- Shallow feature selection

a. Given situation annotated trace T is provided to a feature selection algorithm. This algorithm returns the set of shallow features which have high information gain. Specifically, in Darmok, we have used best-first greedy hill-climbing algorithm for filtering the high information gain shallow features.

2- Model Generation.

a. The Situation-Classification Model Mcf

This model is useful for classification of a world state to a situation using shallow features. In Darmok, we have used a standard algorithm inducing a decision tree classifier model.

b. The Situation-Case Model Mc

Provides a mapping from the set of situations S to a subset of cases in the case-base C. It can be built using statistical or empirical analysis.

c. The Situation-Deep feature Model Mdf

Provides a mapping from S to deep features in the set Fd. This mapping is done using a feature selection algorithm or by using empirical knowledge.

3- Model Execution.

In this third step, the models generated in the previous step are executed to get the current situation S, the subset of cases C’ from the case-base C and the subset of deep features Fd’ which are most relevant to S. S is obtained by running Mcf over Fs’. Once S is known, using Mc and Mdf , C ‘ and Fd’ are obtained respectively.

4- Case Retrieval.

This is the last step where using Fd’ and FS the most similar case in retrieved from C’ using normal retrieval techniques.

clip_image002

Posted in Case-Based Planning | Tagged: , , , , , | Leave a Comment »

A survey of common techniques used in developing CBR systems

Posted by Ahmad Atta on November 3, 2009

Abstract
After reading many papers related to CBR, CBP, and their use in RTS games, I collected the common techniques used for applying CBR concepts, and sub-tasks. At first, I want to assure that online adaptation of planning in RTS games has been already implemented (in contrast to what we had thought). Thus, I will mention some of the important techniques used in Darmok system; the CBR system that implements the architecture for case-based planning in the WARGUS RTS game. In addition to these techniques, I added some ideas which we can apply in our new CBR system.
Read This Doc

Posted in Case-Based Planning, Case-Based Reasoning | Tagged: , , , , , | Leave a Comment »

On-Line Case-Based Plan Adaptation for RTS Games

Posted by Ahmad Atta on October 22, 2009

Abstract

After reading about Case-based Reasoning, the second step we should talk is understanding Case-based planning, my reference in this post will be the paper of Neha Sugandh, Santiago Ontanon, and Ashwin Ram titled: On-Line Case-Based Plan Adaptation for Real-Time Strategy Games. This paper presents techniques allow the system to create and adapt plans in an efficient and effective manner while performing the task.

Case-Based Planning in WARGUS

In this section we will briefly describe the Darmok system, which applies the plan adaptation techniques. Darmok was designed to play the game of WARGUS . In order to achieve this, Darmok learns behaviors from expert demonstrations, and then uses case-based planning to play the game reusing the learnt behaviors. Figure 2 shows an overview of our case-based planning approach.

Darmok System

Basically, we divide the process in two main stages:

• Behavior acquisition:

During this first stage, an expert plays a game of WARGUS and the trace of that game is stored. Then, the expert annotates the trace explaining the goals he was pursuing with the actions he took while playing. Using those annotations, a set of behaviors are extracted from the trace and stored as a set of cases.

Behavior Execution:

The execution engine consists of several modules that together maintain a current plan to win the game.

  1. The Plan Execution module: Executes the current plan, and updates its state (marking which actions succeeded or failed).
  2. The Plan Expansion module: Identifies open goals(a goal still doesn’t have an assigned behavior) in the current plan and expands them.
  3. The Behavior Retrieval module: Given an open goal and the current game state, it retrieves the most appropriate behavior to fulfill the open goal.
  4. The Plan Adaptation module (the focus of this paper): Adapts the retrieved plans according to the current game state.

————————–

Posted in Case-Based Planning | Leave a Comment »

Online Case-based planning (Part 2)

Posted by Ahmad Atta on October 22, 2009

Plan Representation Language

1. A behavior has two main parts:

  • The declarative part has the purpose of providing information to the system about the intended use of the behavior. The declarative part of a behavior consists of three parts: a goal, a set of  preconditions , a set of alive conditions.
  • The procedural part contains the generation module to generate behaviors. The procedural part of a behavior consists of 1) Executable code (basic actions) and 2) Subgoal (that need to be further expanded).

2. The state of a behavior can be:

  • pending (when it still has not started execution)
  • executing
  • succeeded
  • failed.

3. When a goal still doesn’t have an assigned behavior, we say that the goal is open.

4. A goal that has a behavior assigned and where the behavior has failed is also considered to be open.

5. Open goals can be either ready or waiting.

Run-Time Plan Expansion and Execution

1- A partial plan tree in our framework is represented as a tree consisting of two types of nodes: goals and behaviors. In the remainder of this paper we will refer to the partial plan tree simply as the “plan”.

2- Initially, the plan consists of a single goal: “win the game”.

3- The plan expansion module asks the behavior generation module to generate a behavior for that goal.

4- That behavior might have several subgoals, for which the plan expansion module will again ask the behavior module to generate a behavior for it.

5- that behavior is sent to the behavior adaptation module, and then inserted in the current plan, marked as pending.

6- The plan execution module has two main functionalities: check for basic actions that can be sent to the game engine and check the status of plans that are in execution:

7- For each pending behavior, the execution module evaluates the preconditions, and as soon as they are met, the behavior starts its execution.

8- Basic actions that are ready and with all its preconditions satisfied are sent to WARGUS to be executed. If the preconditions are not satisfied, the behavior is sent back to the adaptation module to see if the plan can be repaired. If it cannot, then the behavior is marked as failed.

9- Whenever a basic action succeeds or fails, the execution module updates the status of the behavior that contained it. When a basic action fails, the behavior is marked as failed, and thus its corresponding goal is open again.

10- If the alive conditions of an executing behavior are not satisfied, the behavior is marked as failed. If the success conditions of a behavior are satisfied, the behavior is marked as succeeded.

11- Finally, if a behavior is about to be executed and the current game state has changed since the time the behavior generation module generated it, the behavior is handed back to the plan adaptation module to make sure that the plan is adequate for the current game state.

On-Line Case-Based Plan Adaptation

Plans are composed of four basic types of elements:

  1. Actions, which are the basic actions that can be executed.
  2. Parallel plans which consist of component plans which can be executed in parallel.
  3. Sequential plans which consist of component plans which need to be executed in sequence.
  4. Sub-goal plans requiring further expansion.

We can deduce dependencies between different plans using their preconditions and success conditions. We specifically consider only plans which are completely expanded and do not contain a sub- goal which further needs to be expanded. We generate a plan dependency graph using the preconditions and success conditions of the actions. This plan dependency graph informs the plan adaptation process.

Plan Dependency Graph Generation

1- Each action has preconditions and success conditions, and each goal has only a set of success conditions.

2- Further, every plan has a root node that is always a subgoal.

3- The plan dependency graph generation, begins by

  • Taking the success conditions of the root of the plan.
  • Finding out which actions in the plan contribute to the achievement of these success conditions.
  • These actions are called direct sub-plans for the sub-goal.

4- All direct sub-plans are added to the plan dependency graph. Then the plan dependency graph generator analyzes the preconditions of each of these direct sub-plans.

5- Let B1 be an action in the plan which contributes to satisfying the preconditions of a direct sub-plan D1. Then, it adds B1 to the plan dependency graph and forms a directed edge from B1 to D1 . This directed edge can be considered as a dependency between B1 and D1 .

6- This is done for each of the direct sub-plans. Further this is repeated for each of the actions which are added to the graph. This process results in the formation of a plan dependency graph with directed edges between actions representing that one action contributes to the achievement of the preconditions of another action.

precondition-success condition matcher (ps-matcher).

  • In our system, we have developed a rule-based ps-matcher that incorporates a collection of rules for the appropriate condition matching. For example, our system has six different conditions which test the existence of units or unit types.
  • In some cases it is not clear whether a relation exists or not. However it is necessary for our system to capture all of the dependencies, even if some non- existing dependencies are included. Clearly, executing extra actions is better than missing some needed actions.

The plan adaptation after the creation of the plan dependency graph has two sub-processes: elimination of unnecessary actions, and insertion of extra actions.

————————-

Posted in Case-Based Planning | Leave a Comment »

Fundamentals of CBR Methods

Posted by Ahmad Atta on October 14, 2009

Posted in Case-Based Reasoning | 2 Comments »