Adaptive AI Engine for RTS Games

Discussing the theory and practice

Archive for December, 2009

CaS System – An Introduction

Posted by Ogail on December 14, 2009

Hello all,

I’d like to introduce CaS (Case-Based Strategies) its a CBR system that is able to adapt itself depending of the opponent strategies. We consider CaS as a future work for CaT (CBR system developed bt David W. Aha). CaS is a mixture of CBR techniques and is mapped to BDI model. Till now we’ve finished the design of:

  • Case representation technique.
  • Retrieval method.
Advertisements

Posted in CaS-RTS Platform | Leave a Comment »

Case Based Planner Platform For RTS Games

Posted by Ogail on December 6, 2009

Posted in CaS-RTS Platform, Presentations | Tagged: , , , , , , , | Leave a Comment »

05-12-2009 Meeting Minutes

Posted by Ogail on December 6, 2009

  • Goal of meeting:
    • Discussing what we’ve done till now.
    • Introducing RL Platform.

  • Discussing what we’ve done till now:
    • Built a good knowledge about:
      • RTS Games architecture.
      • General game AI.
      • Latest advances in RTS Games AI.
      • Common used techniques in RTS Game AI.
      • Case-Based Reasoning.
      • Case-Based Planning.
      • Reinforcement Learning.
    • Also we’ve started to develop our own:
      • Case-Based Planner in RTS Games.
      • Heuristically accelerated Hierarchical RL in RTS Games

  • Find Heuristically accelerated Hierarchical RL in RTS Games Platform presentation in this link.
  • Drs said to us that we should concentrate on these issues next period:
    • We should determine time of finishing the platform design.
    • Draw architecture of Wargus and AI of it.
    • Find references for our work.

Posted in Meeting Minutes | Leave a Comment »

Thank You Hassan Ibraheem !

Posted by merothehero on December 5, 2009

Thanks to Hassan Ibraheem -our colleague and friend- we were able to compile and run the Wargus Game on windows at last. In case we switch our test-bed from BosWars to Wargus , that would be a great favor to us.

Hassan spent with us a lot of hours and effort to do this, THANK YOU HASSAN !

Posted in Thanks | 5 Comments »

Introduction To Heuristically accelerated Hierarchical RL in RTS Games

Posted by merothehero on December 5, 2009

Posted in HAHRL-RTS Platform | Tagged: , , , | 1 Comment »

Just an Intro : Heuristically Accelerated Hierarchical Reinforcement Learning in RTS Games

Posted by merothehero on December 3, 2009

Introduction

In this document I will analyze the game play and strategies of RTS Games, and then I will give a brief about how the Heuristically Accelerated Hierarchical Reinforcement Learning System (HAHRL-RTS System) will work.

The Strategy Game: An Analysis

There’s no doubt that strategy games are complex domains: Gigantic set of allowed Actions (almost infinite), Gigantic set of Game States (almost infinite), imperfect information, nondeterministic behavior, and with all this: Real-time Planning and Reactions are required.

Many of the Approaches to applying learning or planning to RTS Games considered the AI as one solid learning part; this leads to the great complexity at applying the techniques used.

I thought about: How can I simplify everything?

Firstly, I listed all the primitive actions which could be done by a human player:

1-      Move a unit

2-      Train/Upgrade a unit

3-      Gather a resource

4-      Make a unit attack

5-      Make a unit defend

6-      Build a building

7-      Repair a building

NB: Upgrading units or buildings is not available in BosWars but found in most RTS Games.

Any player wins by doing 2 types of actions simultaneously, either an action that strengthens him or an action that weakens his enemy (Fig 1).
NB: We neglect useless actions here and suppose the player is perfect.

When a human plays a strategy game, he doesn’t learn everything at the same time. He learns each of the following 6 sub-strategies separately:

1-      Train/Build/Upgrade attacking Units: What unit does he need to train??

  1. Will he depend on fast cheep units to perform successive fast attacks or powerful expensive slow units to perform one or two brutal attacks to finish his enemy? Or will it be a combination of the two which is often a better choice?
  2. Does his enemy have some weak points concerning a certain unit? Or his enemy has units which can infiltrate his defenses so he must train their anti-units?
  3. Does he prefer to spend his money on expensive upgrades or spend it on more amounts of non-upgraded units?

NB: I deal with attacking Buildings as static attacking units

2- Defend: How will he use his current units to defend?

  1. Will he concentrate all his units in one force stuck to each other or will he stretch his units upon his borders? Or a mix of the two approaches?
  2. Will he keep the defending units (which maybe an attacking building) around his buildings or will he make them guard far from the base to stop the enemy early. Or a mix of the two approaches?
  3. If he detects an attack on his radar, will he order the units to attack them at once, or will he wait for the opponent to come to his base and be crushed? Or a mix of the two approaches?
  4. How will he defend un-armed units? Will he place armed units near them to for protection or will he prefer to use the armed units in another useful thing? If an un-armed unit is under attack how will he react?
  5. What are his reactions to different events while defending?

3- Attack: How will he use his current units to attack?

  1. Will he attack the important buildings first? Or will he prefer to crush all the defensive buildings and units first? Or a mix of the two approaches?
  2. Will he divide his attacking force to separate small forces to attack from different places, or will he attack with one big solid force? Or a mix of the two approaches?
  3. What are his reactions to different events while attacking?

4- Gather Resources: How will he gather the resources?

  1. Will he train a lot of gatherers to have a large rate of gathering resources? Or will he train a limited amount because it would be a waste of money and he wants to rush (attack early) in the beginning of the game so he needs that money? Or a mix of the two approaches?
  2. Will he start gathering the far resources first because the near resources are more guaranteed? Or will he be greedy and acquire the resources the nearer the first? Or a mix of the two approaches?

5-      Construct Buildings: How does he place his buildings? Will he stick them to each other in order to defend them easily? Or will he leave large spaces between them to make it harder for the opponent to destroy them? Or a mix of the two approaches?

6-      Repair: How will he do the repairing? Although it’s a minor thing, but different approaches are used. Will he place a repairing unit near every building in case of having an attack, or will he just order the nearest one to repair the building being attacked? Or a mix of the two approaches?

The HAHRL-RTS System

Since the 6 sub-strategies do not depend on each other (think of it and you’ll find them nearly independent),  So, I will divide the AI system to a hierarchy as shown in figure 1, each child node is by itself a Semi-Marcov decision process (SMDP) where Heuristically Accelerated Reinforcement Learning Techniques will be applied. Each child node will be later divided into other sub-nodes of SMDPs.

So now you’ve understood why it is hierarchical, but you may be wondering why “heuristically accelerated”?

Well, because heuristic algorithms will be applied to guide and accelerate the learning process. I hear you asking what the heuristic algorithms are. But that’s another story will be said later!

Posted in HAHRL-RTS Platform | Tagged: , , , , | Leave a Comment »

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 »

Cases Representation Techniques

Posted by Ogail on December 2, 2009

  1. Hash Map.

The key (identifier) of each element will be determined using a hash function depends on the identifier features of the case.

  1. A Simplex Plan.

The problem of acquiring amount of peons to train will be formalized in a Simplex method form and then solved.

  1. Hierarchical Memory Structure.

The most important features are placed in the top of this hierarchy and the less important ones led us to certain sub groups of cases till we reach the most similar cases to the new one we have.

Posted in CaS-RTS Platform | Leave a Comment »

Defeating Novel Opponents in a Real-Time Strategy Game

Posted by Ogail on December 2, 2009

  • Abstract:
    • The Case-Based Tactician (CAT) system, created by Aha, Molineaux, and Ponsen (2005), uses case-based reasoning to learn to win the real-time strategy game Wargus. Previous work has shown CAT’s ability to defeat a randomly selected opponent from a set against which it has trained. We now focus on the task of defeating a selected opponent while training on others. We describe CAT’s algorithm and report its cross-validation performance against a set of Wargus opponents.
  • Spronk and Ponsen developed a genetic algorithm and a technique called dynamic scripting to learn plans spanning the entire game which win against fixed opponent.
  • CAT is the first case-based system designed to defeat an opponent that uses tactics and strategies that it has not trained against.
  • CAT employs sources of domain knowledge to reduce the complexity of WARGUS:
    • Building state lattice: to abstracts the state space.
    • Set of tactics for each state.
      • This was acquired using Ponsen and Spronck’s genetic algorithm (2004). This was used to evolve chromosomes, representing counterstrategies, against specific opponents.
  • Idea of breaking game into periods in order to current available buildings.
  • Building state is time between the constructions of such building to the time the next is built.
    • Building state defines the set of actions available to the player at any one time.
  • It is important not to confuse building state with the game state, which encompasses all of the variables of the game, and changes much more frequently, whether the player takes action or not.
  • The building state lattice (Figure 1) shows the transitions that are possible from one building state to the next. In their research (Spronk’s), plans spanned an entire game, which we call strategies. These strategies are made up of tactics, which are subplans that span a single building state. The tactics are made up of individual actions; using the state lattice, Ponsen and Spronck ensured that all actions used were legal for the corresponding building state, and that the entire plan was therefore legal.

  • Table 1 shows opponent actions that WARGUS can correspond to.

  • Case is a tuple of four objects: C = <BuildingState, Description, Tactic, Performance>
    • BuildingsState: integer node index in the building state lattice.
    • Description: is a set of features of the current situation.
    • Tactic: is a counter-strategy’s sequence of actions for that building state.
    • Performance: real value in the range [0,1] that reflects the utility of choosing that tactic for that building state, where higher values indicate higher performance.

  • CAT retrieves cases when a new state in the lattice is entered.
  • The similarity between a stored case C and the current game state S is defined as:
    • SimC, S = (CPerformance/dist(CDescription, S)) – dist(CDescription, S)
    • where dist() is the (unweighted, unnormalized) Euclidean distance between two cases for the eight features.
  • Evaluation Function:

  • In retaining C’ if we found C with same <Description, Tactic> then we update it. Otherwise create new case.

Posted in Papers Summaries | 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 »