Adaptive AI Engine for RTS Games

Discussing the theory and practice

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.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: