Adaptive AI Engine for RTS Games

Discussing the theory and practice

Archive for May, 2010

Situation Assessment Empirical Analysis in IStrategizer

Posted by Ogail on May 14, 2010

  • In this article we’ll introduce the idea of situation assessment in IStrategizer.
  • Situation Assessment is a process of gathering high-level information using low-level data to help in better decision making.
  • We’ll use 3 terms here:
    • Situation: is a high-level representation of the state of the world
    • Situations can be predicted based on raw features that can be directly computed from the game state, i.e. shallow features.
    • However, shallow features by themselves are not strong enough for selection of a strategy in a game. Additional derived deep features for a situation are needed.
  • For example, shallow features, like the ratio of a player’s resources to that of the opponent, by themselves are less suggestive of usefulness of an appropriate strategy. However deeper features, like knowing the existence of path or a barrier between the player and its opponent, can help in choosing a rush or a tunneling strategy.
  • We’ve 3 Situations:
    • Note that for each set of shallow features above we’ve a set of deep features that will help us to pick the most suitable set of plans to choose from.
    • Base Development Situation:
      • Shallow Features:
        • Basic player infrastructure is not available.
        • Advanced player infrastructure is not available.
        • Near resources for player base are not available.
        • Player has a lot of resources that are not consumed well in building the army.
      • Deep Features:
        • Basic player infrastructure is not available.
          • What’s the missing building exactly? Is it farm? Town Hall? Lumber Mill…
        • Advanced player infrastructure is not available.
          • What’s the advanced building you would to upgrade to? Get new units (i.e. dragons)? Upgrade unit attributes?
        • Near resources for player base are not available.
          • What’s the resource that is not available?
          • Where’s the proposed place to gather from?
        • Player has a lot of resources that are not consumed well in building the army.
          • What are units that you’d like to build their building more?
          • What’s the proposed direction for expanding your empire?
    • Build Army Situation:
      • Shallow Features:
        • Player has enough resources and infrastructure to construct an army.
        • Opponent is attacking/constructing the player and the player has no enough units to defend on himself.
      • Deep Features:
        • Player has enough resources and infrastructure to construct an army.
          • What’s the most available resource to construct an army?
          • From history, what are preferred units by my opponent?
          • What’s natural situation of the map (islands, no paths in between).
          • How opponent defend his base?
        • Opponent is attacking the player or constructing, army where the player has no enough units to defend on himself.
          • What are the most available resources and buildings to construct an army?
          • What are anti-units for the current opponent units?
    • Attack Situation:
      • Shallow Features:
        • Player has enough units to attack opponent.
        • Player resources are obsolete and he wants to get an opponent resources.
        • Player wants to expand his empire and enemy captures a near place.
        • Enemy is near from player base.
      • Deep Features:
        • Player has enough units to attack opponent.
          • What’s the natural of enemy’s base and current player units to utilize them for attacking? (i.e. backdoor exists, enemy doesn’t have long range units …).
        • Player resources are obsolete and he wants to get an opponent resources.
          • What’s the natural of enemy’s base and current player units to utilize them for attacking? (i.e. backdoor exists, enemy doesn’t have long range units …).
        • Player wants to expand his empire and enemy captures a near place.
          • What’s the natural of enemy’s base and current player units to utilize them for attacking? (i.e. backdoor exists, enemy doesn’t have long range units …).
        • Enemy is near from player base.
          • What’s the natural of enemy’s base and current player units to utilize them for attacking? (i.e. backdoor exists, enemy doesn’t have long range units …).
        • Here let us talk more about the deep feature used in this assessment.
          • Natural of player’s army:
            • Ranged.
            • Anti air-attack.
            • Air attack.
            • Strong units.
            • Massive number of units.
          • Natural of enemy’s base:
            • Not defended at all.
            • Has backdoors.
            • Has an air attack defense.
            • Has an anti air attack defense.
            • Has lot of units inside.
            • Has weak points (i.e. important buildings that are not defended well)
          • So, based on combination of these 2 natures we can pick a suitable attack strategy. Example:
            • Natural of player’s army: Air attack.
            • Natural of enemy’s base: has backdoors, has weak points
            • Air Attack Strategy is used!
    • Defense Situation:
      • Shallow Features:
        • Player base is not defended.
        • Enemy is attacking player or constructing an army.
      • Deep Features:
        • What’s the natural of the map duo to defending player’s base? (i.e. surrounded with wood)
        • Where are backdoors in player’s city?
        • Where are most important regions in my city?
        • From history, what are preferred units that player attack with?
Advertisements

Posted in Technical Documents | 2 Comments »

Situation Assessment for Plan Retrieval in Real-Time Strategy Games

Posted by Ogail on May 12, 2010

  • Abstract:
    • 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.
  • A Situation is a high-level representation of the state of the world. For example, in the WARGUS domain the player might be in an attacking situation, or in a base development situation, among others.
  • Situations can be predicted based on raw features that can be directly computed from the game state, i.e. shallow features.
  • However, shallow features by themselves are not strong enough for selection of a strategy in a game. Additional derived deep features for a situation are needed.
  • For example, shallow features, like the ratio of a player’s resources to that of the opponent, by themselves are less suggestive of usefulness of an appropriate strategy. However deeper features, like knowing the existence of path or a barrier between the player and its opponent, can help in choosing a rush or a tunneling strategy.
  • Situation Assessment is a process of gathering high-level information using low-level data to help in better decision making.
  • Our general situation assessment technique comprises of four steps:
    • Shallow feature selection.
      • During this first step, a situation annotated trace is provided to a feature selection algorithm. An annotated trace consists of a sequence of world states annotated with the set of shallow features computed for each world state and the appropriate situation that world state corresponds to. 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.
    • Model generation.
      • In this step the following three models are generated:
        • The Situation-Classification Model, , is built by providing and to a classification algorithm. This model is useful for classification of a world state to a situation using shallow features in . In Darmok, we have used a standard algorithm inducing a decision tree classifier model.
        • The Situation-Case Model, , provides a mapping from the set of situations to a subset of cases in the case-base . It can be built using statistical or empirical analysis. This model captures the intuition that not all the cases will be useful in all the situations.
        • The Situation-Deepfeature Model, , provides a mapping from to deep features in the set . This mapping is done using a feature selection algorithm or by using empirical knowledge.
    • Model execution.
      • In this third step, the models generated in the previous step are executed to get the current situation , the subset of cases from the case-base C and the subset of deep features which are most relevant to s. s is obtained by running over . Once s is known, using and , C’ and are obtained respectively.
    • Case retrieval.
      • This is the last step where using and the most similar case in retrieved from C0 using normal retrieval techniques
  • Situation Assessment Working Mechanism:
    • Firstly, a subset of shallow features is selected which are used for classification of a game state into a situation.
    • Then three models:
      • For classification of game state into situations based on shallow features.
      • For mapping of situations to cases.
      • For mapping of situations to deep features respectively are generated.
  • Shallow features are generally computationally inexpensive but lack the high-level inferential knowledge about the world.
  • The deep features are generally computationally expensive but provide information very relevant for case selection in specific situations.

  • How Situation Assessment is applied in Darmok:
    • The Offline Stage: comprising of Feature Selection and Model Generation before the game-play.
    • The Online Stage: comprising of Model Execution and Plan Retrieval during the game-play.
  • We perform situation assessment in two stages since the models required for predicting the situation during Darmok’s game-play are built just once at the start. Therefore, the models can be easily generated offline using standard feature selection and classification algorithms

Posted in Papers Summaries | Leave a Comment »