Cases Representation Techniques

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.

Defeating Novel Opponents in a Real-Time Strategy Game

• 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:
  • Sim_{C, S} = (C_Performance/dist(C_Description, S)) – dist(C_Description, 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.

Situation Assessment for Plan Retrieval

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.