2. TIELT

2.1 What is TIELT?
Tielt is a software tool developed by the Naval Research Lab (NRL) to facilitate AI researchers in the evaluation of intelligent decision systems in various game engines (e.g., real-time strategy, discrete strategy, role playing, team sports, first-person shooter). Emphasis has been placed upon games that are applicable to military simulations, which is part of why Call to Power 2 was selected in conjunction with the Transfer Learning Project. [Aha, 2007] One might ask why is TIELT necessary at all? Given that Call to Power 2 is open-source, why not simply modify the existing AI engine for the computer player directly? The answer to these questions is time and integration complexity. Even though a game may be open-source, it would still be a daunting task to come to a complete enough understanding of the system architecture to be able to modify the AI code directly. Additionally, modifying the AI directly would make it difficult to test the performance of more than one algorithm for an intelligent agent. Since your newly developed code would be very tightly bound to the architecture of the game, it would require almost a complete rewrite of the code to test a different type of agent program. As for complexity, given that the purpose of the transfer learning project is to test a variety of intelligent agents across a variety of simulators, for each one of x agents you would need to perform an integration for each one of the y simulators you want to test the agent on. This requires a total of x*y integrations. TIELT, however has the advantage of acting as an intermediary between the simulators and the agent programs. Once a simulator is integrated with TIELT, it does not need to know how to communicate with any of the agent programs because it TIELT hides the details of the communication from 5
the simulator. Likewise all the agents need to know is how to communicate with TIELT; they do not need to know how the communication is performed with the simulation engine. Therefore, with the aid of TIELT, the number of integrations required to test a suite of intelligent agents is reduced from x*y to x + y. See the figures below.

Methods: Constructors: o API_Location( const MapPoint p_pPoint ) o API_Location( const sint16 p_iXCoord, const sint16 p_iYCoord ) o API_Location( const API_Location & p_lOther ) Destructor: o ~API_Location() Accessors: o sint16 GetXCoord(): access the x-coordinate member o sint16 GetYCoord(): access the y-coordinate member
API_City Description: This is a class that represents a city on one of the tiles in the game Members: API_Player m_pPlayer: reference to the player that owns this city sint32 m_iCityId: integer identification for this city, this represents an index into an array of the players cities Methods: Constructors: o API_City( const API_Player p_pPlayer, const sint32 p_iCityId ); Destructor: o ~API_City(); Accessors: o API_Location GetLocation(): access the location of the city o sint32 GetIndex(): access the index of the player who owns this city
API_Army Description: This is a class that represents an army unit (military or non-military) on one of the tiles in the game Members: API_Player m_pPlayer: reference to the player that owns this city sint32 m_iArmyId: integer identification for this army, this represents an index into an array of the players armies Methods: Constructors: o API_Army( const API_Player p_pPlayer, const sint32 p_iArmyId ) Destructor: o ~API_Army(); Accessors: o API_Location GetLocation(): access the location of the army o sint32 GetIndex(): access the index of the player who owns this army
It is worth noting that because of the abstraction of the game that this API provides, this project is not solely of use to researchers who wish to use TIELT. Since the API provides a simple C++ interface to control the actions of the computer player, any AI researcher could write an intelligent agent in C++ to interface with Call to Power 2 directly. It can even be of use to members of the Apolyton community who wish to make further modifications to the games functionality since it simplifies ways of dealing with the details of the data structures used for controlling the game.

3.4 Code Reference

The Call to Power 2 API is a constantly evolving project. The most current version of the API can always be found freely available at the InSyTe labs website for the Call
to Power 2 TIELT Integration project: http://www.cse.lehigh.edu/InSyTe/CTP2TieltIntegration/CTP2Integration.html
4. The TIELT Call To Power 2 Model
4.1 What is the TIELT Call to Power 2 model?
In Section 2 we discussed the purpose of TIELT and explained the steps necessary to set up a domain for to model the rules of a game in TIELT. This section will explain specifically how Call to Power 2 was modeled in TIELT and some of the design decisions made for this purpose. Note that similar to the API, the Call to Power 2 model in TIELT also occasionally changes to fit the needs of the project. The TIELT specs can also be found online at the InSyTe lab website: http://www.cse.lehigh.edu/InSyTe/CTP2TieltIntegration/CTP2Integration.html

4.2 Environment Model

As mentioned in Section 2, the TIELT Environment Model is where an abstract model of the game world is made. This includes the rules of the game, state variables, TIELT-specific classes, actions possible in the game world, and observations about changes to the game state. We will begin by discussing the TIELT-specific classes made since they will be referenced in the other parts of the game model. Similar to how the API abstracts the internals of Call to Power 2 in four different classes, TIELT uses classes to abstract information about objects and state information in Call to Power 2. The first classes are those which correspond to the classes used by the API: API_Player, API_Location, API_Army, and API_City. Note that even though these classes share the same name as the classes in the API, they are not identical. The TIELT classes have member variables, but no associated methods. This is because these classes are used in order to wrap information passed through messages to the game into objects that are easier to conceive. These classes are defined as follows: 37
API_Player Description: This is a class that represents a one of the players in the game Members: int m_iIndex: an integer which represents a single player
API_Location Description: This is a class that represents a tile on the map Members: int m_iXCoord: x-coordinate of this location int m_iYCoord: y-coordinate of this location
API_City Description: This is a class that represents a city on one of the tiles in the game Members: API_Player m_pPlayer: reference to the player that owns this city sint32 m_iCityId: integer identification for this city, this represents an index into an array of the players cities int x_pos: the x-coordinate of this city int y_pos: the y-coordinate of this city
API_Army Description: This is a class that represents an army unit (military or non-military) on one of the tiles in the game Members: API_Player m_pPlayer: reference to the player that owns this city sint32 m_iArmyId: integer identification for this army, this represents an index into an array of the players armies
In addition to these classes above, three more classes were added in order to represent sets of these objects. These classes are named API_Location_List, API_Army_List, and API_City_List, respectively. These classes were designed to function similarly to an ArrayList in Java, in that the lists could grow and shrink dynamically as needed as objects are added or removed from them. These objects are useful for representing collections of objects. For example, an API_Army_List is used for representing every unit a player controls in a single, easy to reference object. These classes are defined as follows:
API_Location_List Description: This is a class that represents a collection of API_Location objects Members: API_Location[] location_array: an array of API_Location objects int last_filled_index: the last index in the array where an object has been placed

Methods: void Insert( API_Location element ): insert an API_Location object to the end of location_array void Delete( int x_coord, int y_coord ): delete the element in location_array whose x coordinate equals x_coord and whose y coordinate equals y_coord int GetNumElements(): access last_filled_index int FindElement( int x_coord, int y_coord ): return the index of the API_Location object in location_array whose x coordinate equals x_coord and whose y coordinate equals y_coord void GrowArray(): increase the size of the array void ShrinkArray(): decrease the size of the array
API_City_List Description: This is a class that represents a collection of API_City objects 39
Members: API_Location[] city_array: an array of API_Location objects int last_filled_index: the last index in the array where an object has been placed
Methods: void Insert( API_City element ): insert an API_City object to the end of location_array void Delete( int cityid ): delete the element in city_array whose ID equals cityid int GetNumElements(): access last_filled_index int FindElement( int x_pos, int y_pos ): return the index of the API_City object in city_array whose x coordinate equals x_pos and whose y coordinate equals y_pos int FindElement( int cityid ): return the index of the API_City object in city_array whose ID equals cityid void GrowArray(): increase the size of the array void ShrinkArray(): decrease the size of the array
API_Army_List Description: This is a class that represents a collection of API_Army objects Members: API_Location[] army_array: an array of API_Army objects int last_filled_index: the last index in the array where an object has been placed
Methods: void Insert( API_Army element ): insert an API_Army object to the end of army_array void Delete( int armyid ): delete the element in army_array whose ID equals armyid int GetNumElements(): access last_filled_index int FindElement( int armyid ): return the index of the API_Army object in army_array whose ID equals armyid void GrowArray(): increase the size of the array void ShrinkArray(): decrease the size of the array 40

With those classes defined, we can now look at the list of TIELT state variables used to model the current state of the world in Call to Power 2. As a design decision, we are not keeping an object to represent the number or locations of enemy army units. This is because enemy unit positions can change every turn, and due to the fog of war in Call to Power 2, it is extremely difficult to keep accurate information in such an object. Similarly, we do not keep track of the number of enemy units since the player cannot tell when an enemy unit that cannot be seen has died. The state variables used are as follows:
API_Location_List enemy_city_locations: the list of locations for every enemy city encountered
API_Army_List my_army_locations: the list of all armies you control API_City_List my_city_locations: the list of all cities you control int curr_turn: keeps track of how many turns have been taken int my_player_id: integer value of your player ID int game_state: integer representation of current game state: 0 = game lost, 1 = in progress, 2 = game won.
int num_enemy_cities: the number of enemy cities you have found int num_my_cities: the number of cities you control int num_my_armies: the number of armies you control
Now we will explain the Action Models used defined for Call to Power 2. Recall that the Action Models represent the actions available for an agent to make in the environment. Also, keep in mind that only the actions required to play a subset of the 41
game have been implemented due to the complexity of the entire game. It should also be noted that due to the fact that some of the C++ API calls cannot give you an immediate result as to whether they succeeded or failed (for example, the AttackEnemyPosWithArmy function only returns whether it was possible to perform the attack) it was decided to implement a query-driven system for the Action Models. That is, if an agent wants to perform an action, it issues a query as to whether the action is possible. If the action is possible, the agent is notified that the action is possible and a command to perform that action is automatically issued by TIELT without requiring input from the agent. If the action is not possible, the agent is simply notified that the action is not possible. The only action that does not require a query is the action to end the current turn. The list of available TIELT Action Models follows: Load a game Message Name: Load Description: Loads a game Parameters: @name //name of game to be loaded Relevant Phases: Playing Precondition: none Triggers message: GAME_LOAD Save a game Message Name: Save Description: Saves a game Parameters: @name //name of game to be loaded Relevant Phases: Playing Precondition: 42

NewUnitComplete Description: A new unit has finished building Parameters: @int armyID @int x_pos @int y_pos Conditions: none Triggered By: NEW_UNIT_COMPLETED
//ID of army unit being produced //x-position of the city making the new unit //y-position of the city making the new unit
Unexplored Map Tile Message Name: UnexploredTile Description: Query response with x-y position of an unexplored tile by a unit. Note that this is not guaranteed to be the closest unexplored tile with respect to the unit. Parameters: @bool success //set true if there is an unexplored tile around that unit @int armyID //ID of army that is performing the search @int x_pos //x-position of the tile returned @int y_pos //y-position of the tile returned Conditions: none Triggered By: UPD_UNEXPLORED_MAP Enemy Units Nearby Message Name: NearEnemyUnit Description: Query response with x-y positions of an enemy unit near a unit you control Note: this is triggered once for each enemy unit near the unit you are querying with respect to Parameters: @bool success //set true if there are any enemy units in visual range of your unit @int x_pos //x position of the enemy unit found @int y_pos //y position of the enemy unit found Conditions: none Triggered By: UPD_ENEMY_UNIT Enemy Cities Nearby 49
Message Name: NearEnemyCity Description: Query response with x-y positions of an enemy city near a unit you control Note: this is called once for each unit near the unit you are querying with respect to Parameters: @bool success //set true if there are any enemy units in visual range of your unit @int x_pos //x position of the enemy city found @int y_pos //y position of the enemy city found Conditions: none Triggered By: UPD_ENEMY_CITY Unit Position Update Message Name: UpdatePosition Description: Informs you of new position for unit with ID of armyID Parameters: @int armyID //ID of army unit that has been moved @int old_x //old x position of the unit @int old_y //old y position of the unit @int new_x //new x position of the unit @int new_y //new y position of the unit Conditions: none Triggered By: UPD_ARMY_XY City Can Be Attacked Message Name: CityAttackable Description: Query response whether a city can be attacked by a given unit Parameters: @bool success //set true if the city can be attacked @int armyID //ID of the unit that will attack @int x_pos //x-location of the city to be attacked @int y_pos //y-location of the city to be attacked Conditions: none Triggered By: UPD_CITY_ATTACKABLE

Unit Can Be Attacked Message Name: UnitAttackable Description: Query response whether a unit can be attacked by a given unit Parameters: @bool success //set true if the unit can be attacked @int armyID //ID of the unit that is attacking @int x_pos //x-location of the unit to be attacked @int y_pos //y-location of the unit to be attacked Conditions: none Triggered By: UPD_UNIT_ATTACKABLE City Can Be Built Message Name: CityBuildable Description: Query response whether a city can be built on a given tile Parameters: @bool success //set true if there is an a city can be built on the x,y position passed in from QU_CITY_BUILDABLE message @int armyID //ID of the unit that will build the city @int x_pos //x-location where city will be built @int y_pos //y-location where city will be built Conditions: none Triggered By: UPD_CITY_BUILDABLE Unit Can Be Moved Message Name: UnitMoveable Description: Query response whether a unit can move to a given tile Parameters: @bool success //set true if the unit in question can move to the tile passed in from the QU_MOVEABLE message @int armyID //ID of the unit that will move @int x_pos //x-location where city will be built @int y_pos //y-location where city will be built Conditions: none Triggered By: UPD_MOVEABLE 51
Unit Can Be Built Message Name: UnitBuildable Description: Query response whether a unit can be built Parameters: @bool success //set true if the unit type in question can be built @int cityID //city the unit will be built in @int unit_type //type of unit being built Conditions: none State Changes: none Triggered By: UPD_UNIT_BUILDABLE City Improvement Can Be Built Message Name: ImprovementBuildable Description: Query response whether a city improvement can be built Parameters: @bool success //set true if the improvement type in question can be built @int cityID //city the improvement will be built in @int improvement_type //type of city improvement to build Conditions: none Triggered By: UPD_IMPROVEMENT_BUILDABLE Unit Is Garrisoning Message Name: Garrisoning Description: Indicate whether a unit is garrisoning Parameters: @bool success //set true if the unit is garrisoning a city @int armyID //ID of unit that is garrisoning @int x_pos //x-position of the unit @int y_pos //y-position of the unit Conditions: none Triggered By: UPD_GARRISON
Unit Has Stopped Garrisoning Message Name: StoppedGarrisoning Description: Indicate whether a unit has stopped garrisoning Parameters: @bool success //set true if the unit is garrisoning a city @int armyID //ID of unit that is garrisoning @int x_pos //x-position of the unit @int y_pos //y-position of the unit Conditions: none Triggered By: UPD_UNGARRISON A Turn Has Ended Message Name: TurnOver Description: Indicates that any turn has ended Parameters: none Conditions: none Triggered By: GAME_TICK Your Turn Has Started Message Name: MyTurn Description: Indicates that your turn has begun Parameters: none Conditions: none Triggered By: GAME_MYTURN Your Player ID Message Name: MyID Description: Indicates what your player ID is Parameters: @int playerID //your player ID 53

Conditions: none Triggered By: GAME_MYID Total Number of Players Message Name: NumPlayers Description: Indicates how many players are in the current game Parameters: @int num_players //total number of players Conditions: none Triggered By: GAME_NUM_PLAYERS Note: this is supported in TIELT, but the message is not yet implemented in CTP2 Program Begins Message Name: Connected Description: Indicates start of CTP2 program Parameters: @int num_players //total number of players Conditions: none Triggered By: CTP2_START Game Has Started Message Name: GameStarted Description: Indicates start of an individual game Parameters: none Conditions: none Triggered By: GAME_START Lost Game Message Name: Lose Description: 54
Indicates a game loss Parameters: none Conditions: none Triggered By: GAME_LOSE Won Game Message Name: Win Description: Indicates a game win Parameters: none Conditions: none Triggered By: GAME_WIN Saved Game Message Name: GameSaved Description: Indicates success or failure of attempt to save a game Parameters: @bool success //set to true if game saved successfully, otherwise false Conditions: none Triggered By: UPD_SAVE Loaded Game Message Name: GameLoaded Description: Indicates success or failure of attempt to load a game Parameters: @bool success //set to true if game saved successfully, otherwise false Conditions: none Triggered By: UPD_LOAD Game Finished Message Name: 55
GameOver Description: Indicates end of an individual game Parameters: none Conditions: none Triggered By: GAME_DONE Program Closed Message Name: Disconnected Description: Indicates end of CTP2 program Parameters: none Conditions: none Triggered By: CTP2_END Table 2: Call to Power 2 Observation Models

4.3 Simulator Interface

The Simulator Interface model defines the messages which TIELT uses in order to communicate with the game engine. The Simulator Interface is broken down into outgoing messages from TIELT to Call to Power 2, and incoming messages from Call to Power 2 to TIELT. We will start with the outgoing messages. Note that these messages will also make use of instantiated objects of the TIELT-specific classes that we defined in the Environment Model. Also, there will be some messages defined here that are used exclusively for handshaking with Call to Power 2 when initiating the TIELT-Call to Power 2 connection before starting an experiment. The outgoing messages used for this project are as follows:
Attack Enemy City Message Name: ACT_ATTACK_CITY 56
Description: Instructs a unit to attack an enemy city Message Arguments: @API_Army p_aArmy //army unit to attack with @API_Location p_lDestination //location of city to attack Triggered By: Incoming Message: UPD_CITY_ATTACKABLE API Functions this will call: AttackCityPosWithArmy( API_Army p_aArmy, const API_Location p_lDestination ) Replied to with: UPD_ATTACK_CITY if attack was won DESTROYED_UNIT if attack was lost Attack Enemy Unit ACT_ATTACK_UNIT Description: Instructs a unit to attack an enemy army Message Arguments: @API_Army p_aArmy //army unit to attack with @API_Location p_lDestination //location of enemy unit to attack Triggered By: Incoming Message: UPD_UNIT_ATTACKABLE API Functions this will call: AttackEnemyPosWithArmy( API_Army p_aArmy, const API_Location p_lDestination ) Replied to with: UPD_ATTACK_UNIT if attack was won DESTROYED_UNIT if attack was lost Build City Message Name: ACT_SETTLE Description: Instructs a Settler to move to a point on the map and build a city there Message Arguments: @API_Army p_aArmy //Settler to build the new city Triggered By: Incoming message: UPD_CITY_BUILDABLE API Functions this will call: Settle( API_Army p_aArmy ) Replied to with: UPD_SETTLED_CITY_ID Defend a City Message Name: ACT_GARRISON Description: 57

Query Messages

Query Attackable Enemy City Message Name: QU_ATTACK_CITY Description: Query whether your unit can attack an enemy city Message Arguments: @API_Army p_aArmy //army unit to do the exploration @API_Location p_lDestination //location of city to attack 60
Triggered By: Action Model: QueryAttackCity API Functions this will call: QueryCityAttackable( API_Army p_aArmy, API_Location p_lDestination ); Replied to with: UPD_CITY_ATTACKABLE Query Attackable Enemy Unit Message Name: QU_ATTACK_UNIT Description: Query whether your unit can attack an enemy unit Message Arguments: @API_Army p_aArmy //army unit to do the exploration @API_Location p_lDestination //location of city to attack Triggered By: Action Model: QueryAttackUnit API Functions this will call: QueryUnitAttackable( API_Army p_aArmy, API_Location p_lDestination ); Replied to with: UPD_UNIT_ATTACKABLE Query Map Message Name: QU_UNEXPLORED_MAP Description: Query for an unexplored map square around a unit. Note that this will only provide one unexplored map square, and it is not guaranteed to find the nearest one. Message Arguments: @API_Army p_aArmy //army unit to do the exploration Triggered By: Action Model: QueryUnexploredMap API Functions this will call: FindUnexplored( API_Army p_aArmy, API_Location & p_lUnexplored ) Replied to with: UPD_UNEXPLORED_MAP Query Enemy Units QU_ENEMY_UNIT Description: Query for enemy army units in visible range of a unit Message Arguments: @API_Army p_aArmy //army unit to do the exploration @int p_iVisionRange //Vision range of the unit (either 1 or two) Triggered By: Action Model: QueryEnemyUnit 61
API Functions this will call: FindEnemyUnit( API_Army p_aArmy, const int p_iVisionRange, DynamicArray<Unit> * p_pEnemyList ) Replied to with: UPD_ENEMY_UNIT Query Enemy Cities QU_ENEMY_CITY Description: Query for enemy cities in visible range of a unit Message Arguments: @API_Army p_aArmy //army unit to do the exploration @int p_iVisionRange //Vision range of the unit (either 1 or two) Triggered By: Action Model: QueryEnemyCity API Functions this will call: FindEnemyCity( API_Army p_aArmy, const int p_iVisionRange, DynamicArray<Unit> * p_pCityList ) Replied to with: UPD_ENEMY_CITY Query Buildable Tile QU_CITY_BUILDABLE Description: Query if a unit can build a city at its current location Message Arguments: @API_Army p_aArmy //army unit to build the city Triggered By: Action Model: QueryCityBuildable API Functions this will call: CityBuild( API_City p_cCity, const API_UnitType p_iUnitType ); Replied to with: UPD_CITY_BUILDABLE Query Moveable Tile QU_MOVEABLE Description: Query if a given unit can move to a given tile (ex: Settlers cant move onto ocean, ships cant move onto land) Message Arguments: @API_Army p_aArmy //army unit to move @API_Location p_lLocation //location to move that unit to Triggered By: Action Model: QueryMoveable API Functions this will call: QueryMoveable( API_Army p_aArmy, API_Location p_lLocation ); 62

Replied to with: UPD_MOVEABLE Query Buildable Unit QU_UNIT_BUILDABLE Description: Query if a given unit can be built in a city (ie: you are far enough in the tech tree to build it) Message Arguments: @integer unit_type //integer representation of unit you want to build @API_City p_cCity //city you want to build that unit in Triggered By: Action Model: QueryUnitBuildable API Functions this will call: QueryUnitBuildable( int unit_type, API_City p_cCity ); Replied to with: UPD_UNIT_BUILDABLE Query Buildable City Improvement QU_IMPROVEMENT_BUILDABLE Description: Query if a city improvement can be built in a specified city (ie: you are far enough in the tech tree to build it) Message Arguments: @integer improvement //integer representation of the improvement you want to build @API_City p_cCity //city you want to build the improvement in Triggered By: Action Model: QueryImprovementBuildable API Functions this will call: QueryImprovementBuildable( int improvement_type, API_City p_cCity ); Replied to with: UPD_IMPROVEMENT BUILDABLE Query Garrisoning Unit QU_GARRISON Description: Query whether a given unit can garrison its current location Message Arguments: @API_Army p_aArmy //army you are querying about Triggered By: Action Model: QueryGarrison API Functions this will call: QueryGarrison( API_Army p_aArmy ); Replied to with: UPD_GARRISON 63
Query Stopping a Garrison QU_UNGARRISON Description: Query whether a given unit can stop garrisoning its current location Message Arguments: @API_Army p_aArmy //army you are querying about Triggered By: Action Model: QueryUngarrison API Functions this will call: QueryUngarrison( API_Army p_aArmy ) Replied to with: UPD_UNGARRISON Table 3: Call to Power 2 Outgoing Messages Peer to the outgoing messages are the incoming messages. These messages are sent either in response to a query from TIELT or in response to a change in the game state in Call to Power 2. Similar to the outgoing messages, there will be some incoming messages listed that are used for handshaking when the program is started. The incoming messages are as follows:
Update: Attack Enemy City Message Name: UPD_ATTACK_CITY Description: Update to indicate success or failure of a unit you control (with ID of armyID) attacking city at location (x,y) Message Arguments: @bool success //set true if unit destroyed city, false if it died in the process @int armyID //ID of army that attacked the city @int x_pos //x-position of city that was attacked @int y_pos //y-position of city that was attacked Triggered By: ACT_ATTACK_CITY State update: If (success) Remove enemy city from enemy_city_locations array num_enemy_cities-Call: EnemyCityDestroyed observation model Update: Attack Enemy Army 64

Message Name: UPD_MOVEABLE Description: Update to indicate whether a unit can be moved to a certain tile Message Arguments: @bool success //set true if the unit in question can move to the tile passed in from the QU_MOVEABLE message @int armyID //ID of the unit that will move @int x_pos //x-location where the unit is @int y_pos //y-location where the unit is @int x_dest //x-location the unit will move to @int y_dest //y-location the unit will move to Triggered By: QU_MOVEABLE State update: Call: UnitMoveable observation model If (success) Call: ACT_MOVE outgoing message to move the unit there Update: Unit Buildable Message Name: UPD_UNIT_BUILDABLE Description: Update to indicate whether a unit can be built (ie: you are far enough in the tech tree to build it) Message Arguments: @bool success //set true if the unit type in question can be built @int cityID //city unit will be built in @int unit_type //type of unit to build Triggered By: QU_UNIT_BUILDABLE State update: Call: UnitBuildable observation model If (success) Call: ACT_PRODUCE outgoing message to make the unit Update: City Improvement Buildable Message Name: UPD_IMPROVEMENT_BUILDABLE Description: Update to indicate whether a city improvement can be built (ie: you are far enough in the tech tree to build it) Message Arguments: @bool success //set true if the improvement type in question can be built @int cityID //ID of city to build the improvement @int improvement_type //type of improvement to build 68
Triggered By: QU_IMPROVEMENT_BUILDABLE State update: Call: ImprovementBuildable observation model If (success) Call: ACT_IMPROVE outgoing message Update: Unit Garrisoning Message Name: UPD_GARRISON Description: Update to indicate whether a given unit can garrison its current location Message Arguments: @bool success //set true if the unit is garrisoning a city @int armyID //ID of the unit that is now garrisoning Triggered By: QU_GARRISON State update: -change garrisoning Boolean variable for armyID in my_army_locations array to true Call: Garrisoning observation model Update: Unit Stopped Garrisoning Message Name: UPD_UNGARRISON Description: Update to indicate whether a given unit can stop garrisoning its current location Message Arguments: @bool success //set true if the unit could stop garrisoning @int armyID //ID of the unit that is now ungarrisoned Triggered By: QU_UNGARRISON State update: -change garrisoning Boolean variable for armyID in my_army_locations array to false Call: StoppedGarrisoning observation model Update: City Attackable Message Name: UPD_CITY_ATTACKABLE Description: Update to indicate whether a given unit can attack a given city Message Arguments: @bool success //set true if you can attack the city @int armyID //ID of the unit that will attack @int x_pos //x-position of city that will be attacked @int y_pos //y-position of city that will be attacked Triggered By: 69

Game Won Message Name: GAME_WIN Description: Update to indicate a win Message Arguments: none Triggered By: -winning the game State update: Call: Win observation model Game Finished Message Name: GAME_DONE Description: Message to indicate completion of game Message Arguments: none Triggered By: -game complete State update: Call: GameOver observation model Program End Message Name: CTP2_END Description: Message to indicate end of CTP2 program Message Arguments: none Triggered By: - program ending State update: Call: Disconnected observation model Game Loaded Message Name: UPD_LOAD Description: Indicates success or failure of loading a game Message Arguments: @bool success //set true if game was loaded, false otherwise Triggered By: GAME_LOAD 73
State update: Call: GameLoaded observation model Game Saved Message Name: UPD_SAVE Description: Indicates success or failure of saving a game Message Arguments: @bool success //set true if game was saved, false otherwise Triggered By: GAME_SAVE State update: Call: GameSaved observation model Table 4: Call to Power 2 Incoming Messages
4.4 Communication Protocol
The communication protocol implemented by the TIELT Call to Power 2 system may not have been entirely apparent from the list of messages used above. This section will examine the protocol from a broader perspective. When Call to Power 2 is launched, it asks the user to begin the experiment in TIELT. When it detects a connection on the specified port, it sends a CTP2_START( ) message to TIELT. TIELT responds by sending HELLO( ). Once an individual scenario has begun, Call to Power sends the GAME_START( ) message. At this point, TIELT changes the internal state of the game to Playing. Then after the scenario is loaded, Call to Power 2 sends the GAME_MY_ID( ) message to inform TIELT of the ID of the player it is controlling. At this point the game may begin. At the start of any of the players turns, Call to Power 2 will send UPD_ARMY_XY( ) messages to indicate the positions of all the players units. After this state update, the GAME_MYTURN( ) message is sent to TIELT indicating that any desired actions can now be sent. As an example, to settle a city, TIELT would issue the 74
QU_CITY_BUILDABLE message for one of its Settlers. If the Settler can build a city on its current location, Call to Power 2 will respond by setting the first argument of UPD_CITY_BUILDABLE( ) to true and send this message to TIELT. TIELT sees that the action is possible and automatically responds with the ACT_SETTLE( ) message for this Settler. After the city has been built, Call to Power 2 responds with the UPD_SETTLED_CITY_ID( ) message to indicate the integer ID and location of the newly built city. Actions like this continue until the agent wishes to end the current turn, at which point it sends the END_TURN( ) message. Turns continue in this manner until a game is either won or lost. If, for example, the game is won, Call to Power 2 will send the GAME_WIN( ) message to TIELT. Then after the scenario is closed, it will send the GAME_DONE( ) message to TIELT, and TIELT will change the game state from Playing to NotPlaying. Finally, once the program is closed, the CTP2_END( ) message is sent to TIELT to terminate the experiment. The example just described is modeled below in Figure 23. The green box in Figure 23 indicates all the actions taken in a single turn.

Game AI for a Turn-based Strategy Game with Plan Adaptation and Ontology-based retrieval
Antonio S nchez-Ruiz Stephen Lee-Urban H ctor Munoz-Avila a e Bel n Daz-Agudo Pedro Gonz lez-Calero e a
Dep. Ingeniera del Software e Inteligencia Articial Universidad Complutense de Madrid, Spain {antsanch}@fdi.ucm.es, {belend,pedro}@sip.ucm.es Abstract
In this paper we present a novel approach for developing adaptive game AI by combining case based planning techniques and ontological knowledge from the game environment. The proposed architecture combines several components: a case-based hierarchical planner (Repair-SHOP), a bridge to connect and reason with Ontologies formalized in Description Logics (DLs) based languages (OntoBridge), a DLs reasoner (Pellet) and a framework to develop CaseBased Reasoning (CBR) systems (jCOLIBRI ). In our ongoing work we are applying this approach to a commercial Civilization clone turn-based strategy game (CTP2) where game AI is in charge of planning the strategies for automated players. Our goal is to demonstrate that ontology-based retrieval will result in the retrieval of strategies that are easier to adapt than those plans returned by other classical retrieval mechanisms traditionally used in case-based planning.
Dep. of Computer Science and Engineering Lehigh University, PA, USA {sml3, hem4}@lehigh.edu take turns controlling eachs empire or civilization. Controlling these civilizations involves issuing commands to units (e.g., to attack an enemy unit, to defend a location), allocating resources, and constructing new units. To win, various aspects of building a civilization must be taken into account including economy production, assigning resources to improve military and economy, deploying military forces, and using these forces in combat. In TBS games like Civilization or Call To Power hundreds of different kinds of units, buildings, technologies, civilizations, natural resources, terrain features, and weather conditions form an integral part of the game. Game AI must be able to reason with these objects while planning the strategies for the automated players. Currently, game AI is notoriously famous for cheating to provide an adequate challenge level. So for example, if a city is attacked, the game AI will spawn defenders to meet the challenge even though these defenders are not constructed following the rules of the game. This end up working acceptable in these games as the game AI includes ways to make sure it will not unduly challenge a player. However, cheating does detract from gameplay when the player realizes what is happening. Furthermore, as games are increasingly used as training environments (e.g., for military training or as epistemic games), cheating becomes unacceptable as the simulation environment is awed. We propose maintaining a library of known strategies (i.e., plans) in the game. This strategy library includes ontological information about the objects used in the strategies and the conditions under which these strategies where performed. We propose an ontology based retrieval to retrieve relevant strategies (e.g., strategies that are applicable to the current gaming situation) and plan adaptation techniques that use the retrieved strategies to adjust them to the current situation. Our goal is to demonstrate that ontologybased retrieval will result in the retrieval of strategies that are easier to adapt than other classical retrieval mechanisms traditionally used in case-based planning. Next, we describe the most relevant related work and the differences with our approach. The section following that provides an overview of the game and explains why we have chosen it. Then we describe the general architecture of our system and how the different modules are connected. Sub-

Introduction

Developing game AI, i.e. the algorithms that control Nonplayer Characters (NPCS) in a game, is well-known to be a difcult problem. Three outstanding challenges contribute to this difculty. First, game developers have little time allocated to develop game AI; other aspects of game development such as storyline, graphics, network connections usually take precedence. Second, the development of environments, called level design, is typically done independently of the development of the game AI. Yet, game AI will be controlling NPCs running in these environments. Third, games change over time. As games are tested, the games are tweaked to improve the gaming experience of the player. This makes constructing effective game AI a moving target. In this paper we propose a novel approach for developing adaptive game AI. At the core we propose the combination of plan adaptation techniques and ontological information relating objects in the game environment. Such ontological information is readily available in many of these games and is an integral part of their design. This is particularly the case for turn-based strategy (TBS) games. In these kinds of games, two or more opponents (some possibly automated)
Copyright c 2007, Association for the Advancement of Articial Intelligence (www.aaai.org). All rights reserved.
sequently, the next two sections provide a detailed description of the main components: the case-based planner and the advantages of an ontological representation of the domain. Finally, we summarize our work and propose future work.

Related work

One application of HTN planning in games is the work of (Hoang, Lee-Urban, & Mu oz-Avila 2005), wherein a team n of non-human players in a rst-person shooter game is controlled by dynamically generated plans from the orderedtask decomposition planner, JSHOP (Nau et al. 1999). This team of bots was shown to outperform teams composed of the same underlying bots that instead used hard-coded strategies. The domain encoding input to the HTN planner, however, was static (pre-encoded); no form of CBR was used. In our work, we intend to retrieve cases of HTN methods that are most suited to the current game state. Other researchers have applied CBR in games. In (Aha, Molineaux, & Ponsen 2005), cases consist of strategies applicable to specic situations in the real-time strategy game Stratagus. Using these strategies, they were able to beat opponents considered very hard, such as those that use a knights-rush. This work differs from our approach in that no form of HTN planning was used nor are retrieved plans adapted. Another use of case of CBR in games is the multi-layered architecture CARL (Sharma et al. 2007). CARL combines CBR and reinforcement learning to achieve a transferlearning goal in a real time strategy game. Unlike our work, their case retrieval does not use ontological information. Furthermore, case reuse is used to select a goal for the planner to achieve; no plan adaptation occurs. In (S nchez-Pelegrn, G mez-Martn, & Daz-Agudo a o 2005) the authors present a preliminary approach that also uses CBR in another clone of Civilization (C-EVO). The AImodule concentrates in a simple tactical problem concerning actions: the selection of a military unit behavior. However, this tactical problem has a big impact on the result of the game. It uses CBR to assign missions to control units based on a big case base of previously assigned missions. Learning and weighting case base features is a challenging problem in this domain because of the difculties inferring the impact of individual military unit behavior in the nal game result. While all of the above methods employ modern AI techniques in games, to our knowledge, there exists no published work that combines CBP with HTN planning in computer games. This is one of the primary contributions of our efforts. The planner used in our proposed architecture, RepairSHOP (Wareld et al. 2007), which is capable of performing both plan adaptation and plan repair, is strongly based on other work on plan adaptation, such as (Veloso 1994). Velosos work takes into account the paths explored by a rst-principles, state-space planner, and cases are used to store the failures along with the path that lead to a solution. A similar approach was later implemented for partial order planners (Mu oz-Avila & Weberskirch 1996). Plan adaptan tion of hierarchical plans has been proposed before ((Kambhampati & Hendler 1992); (Mu oz-Avila et al. 2001)). The n

RETSINA system (Paolucci et al. 1999) repairs hierarchical plans in the context of a multi-agent system, but it does not takes into account failed traces. Whereas these works either use solely the path that led to the solution, or failure traces for non-hierarchical planners, Repair-SHOP is distinguished in that it takes into account failure traces for HTN planning. Some research advocates separating planning from resource allocation (i.e., the information sources). Systems such as RealPLAN (Srivastava, Kambhampati, & Do 2001) and ParcPLAN (El-Kholy & Richards 1996) follow this approach. The separation of planning and resource allocation allows the systems to decompose the problems into parts for which a specialized reasoner is available. We will follow a similar principle of separating a problem into parts and use specialized reasoners for each part specically, by separating plan generation from execution.

Game description

Call to Power 2 (CTP2) is a turn-based strategy game (Civilization clone) that was originally developed by Activision and made open-source in 2003. This game is a good choice for our project because gameplay involves many decisions at varying levels of complexity: where to build cities, balancing exploration and expansion with defense, when and where to attack an opponent, which units to produce, which advances to research, etc. The huge amount of possibilities and factors involved in each decision make this environment a great challenge to test techniques like hierarchical planning, case-based planning, and ontological representation of knowledge. An example is the best way to get an intuitive feel for how CTP2 works. Figure 1 shows the initial state of the game. At this point, the player has two Settler units, which are nonmilitary units that can explore the map and build new cities. A majority of the map, which is a grid of tiles, is unexplored and therefore not visible. When considering a location to build a city, one must consider the type of terrain, amount of food and commerce provided by the map tile, and proximity of tradable goods (e.g. tobacco, beavers) in the vicinity of that tile. After a city has been built, the decision of number and type of units to produce must be made. In addition to building more settler units, it is possible to produce military units. Alternatively, the city can begin the construction of a City improvement, such as a granary. When built, city improvements give benets to the host city, such as increased commerce or food production, or additional defense against attacks. As the game progresses, another type of improvements, called Wonders, becomes available. Wonders (e.g., The Great Wall of China) take many turns to complete and provide special scientic, military or economic bonuses to the players empire once built. During the course of the game, enemy civilizations will eventually be encountered, and battles ensue. Combat involves each opposing unit simultaneously dealing damage to each other in turns until one is destroyed or retreats. Bonuses are given to a unit in a defensive stance within a city. For our purposes, game victory is only available through military conquest, which entails destroying all existing enemy units

Figure 1: Call to Power 2 (CTP2) is a turn-based strategy game similar to Civilization. and cities. However, the complete game provides two other means of victory, one through diplomacy through the forming of alliances, and the other through scientic advancement via building a special wonder. jCOLIBRI (Recio-Garca et al. 2005) is the component that nds the most suitable old plan by using ontological knowledge represented in a Description Logic formalism. Actually, jCOLIBRI is a framework for developing CBR Systems capable of managing ontological information using the OntoBridge library (Recio-Garca et al. 2006). Finally, there is a mediator between jCOLIBRI and the ontologies; the DL Reasoner Pellet(Sirin et al. 2007), is this mediator, and is responsible for keeping the consistency of the knowledge base and inferring new knowledge that was not explicitly asserted but can be deduced. Once the best old plan is retrieved by jCOLIBRI and adapted by Repair-SHOP, it must be executed by the Supervisor. The Supervisor communicates with the game and will both manage plan execution and determine when to begin a new plan retrieval, adaptation, and storage cycle. If the current plan has been accomplished, or is no longer suitable, the supervisor will ask the planner to generate a new plan. In the coming sections we provide a more detailed description of each part of the AI Engine. The Knowledge Base module keeps three different types of information: general knowledge about the domain, used to compute similarity between cases and adapt them, information about the current state of the game, and a collection of old plans indexed by their initial states and goals (cases). The main innovation is that we use ontologies to represent all this knowledge and DLs-like formalism to reason. The main advantages of this approach are discussed in a later section. As a product of the components of our architecture, the are two main sources of domain knowledge: the tasks, methods and operators used by the planner and stored in the for-

General Architecture

Figure 2 shows the three main modules of our architecture: Simulator, AI Engine and Knowledge base. The communication among these modules is done using well dened interfaces over a TCP/IP connection, so each module can be executed on different hosts. The Simulator, or game engine, is a modied version of the game CTP2, in which a Remote control API has been added to the original game. This Remote control API is described in (Gundevia 2006; Souto 2007) and allows a player to be controlled using a external program. The API is in charge of sending messages to the client about the events that take place in the game (CityBuilt, ArmyMoved, etc), and at the same time execute the commands that it receives (BuildImprovement, MoveArmyTo, etc). With this API only a subset of the game functionality is available: city development and improvement, unit production, and military control; however it is enough for our proposes. The AI Engine is the main module of our architecture and it combines several components. Repair-SHOP (Wareld et al. 2007) is a case-based planner based on SHOP (Nau et al. 1999), a hierarchical planner, and is responsible for generating new strategies. Like any other case-based planner, Repair-SHOP nds new plans by adapting old plans that were successfully used in the past to solve similar situations.

Figure 2: Architecture of our system and main modules malism of Repair-SHOP; and the knowledge about the different types of objects in the world and their relations that are stored using an ontology. In addition, the current state must be cloned in both formalisms because Repair-SHOP and jCOLIBRI use it in different ways: the planner must keep the current state to decide what methods and operators are applicable to adapt an old plan; and jCOLIBRI keeps the current state in an ontology to retrieve the most similar case using similarity metrics based on hierarchies and DLs. structure propagates changes in conditions to the appropriate task nodes; thus, SHOP can replan the affected sections through dependency-directed backtracking. Upon input of a case (T,S,GG) and a new problem (T,S), Repair-SHOP uses the cases GG relative to (T,S) in order to generate an HTN for the new problem. The same domain model is implicit in both the new problem and case. Dependencies are evaluated relative to (T,S) resulting in a partial HTN that is completed by using standard HTN planning techniques. The advantage of using the GG alongside SHOP is that GGs preserve information about the state of the plan for each task and subtask that SHOP attempts to solve. Leaves in the GG correspond to primitive tasks in the HTN. Internal nodes in the GG correspond to compound tasks in SHOP, culminating in the original compound task at the root of the GG. Repair-SHOPs operation is straightforward. When Repair-SHOP monitors a change in conditions, it propagates the result to the highest affected goal, and then checks for an alternate decision. If no alternate decision is available, the graph is navigated upwards towards the root until the rst alternate decision is found. If an alternate decision is eventually found, the stored SHOP state from that decision is restored and the SHOP planning algorithm restarted. If no plan can be found, Repair-SHOP searches upward in the GG for a new alternate decision. If nally successful, the new plan is saved and then spliced into the original plan beginning with the rst affected goal node. There are still areas in which Repair-SHOP could be improved. Specically, the system can only consider situations wherein conditions in the case are invalid. Clearly, it would be desirable to consider situations where new conditions are added (e.g., additional resources are made available).

Planner

In plan repair an existing plan must be modied because of changes in the world conditions (van der Krogt & de Weerdt 2005). Repair-SHOP, a planning system built on top of the HTN planner SHOP, is capable of performing plan adaptation and plan repair (Wareld et al. 2007). Among its distinguishing characteristics is the ability to take into account failed traces, which can result in improvements in running time performance. The HTN planner SHOP implements a variant of HTN planning called Ordered Task Decomposition. In this variant tasks are totally ordered and conditions are evaluated relative to the current state of the world, which is updated during planning. A case used in Repair-SHOP is dened as the tuple (T,S,GG): a collection of HTN tasks T, a state S, and a graph structure GG, called the goal graph. The goal graph GG represents the HTN generated when solving (T,S), augmented by other relations, and takes the form of a directed dependency graph with a one-to-one mapping between each goal in the graph and each task in SHOP. This graph represents relations between goals, operators and decisions (applied operators). The GG, which is an implementation of the REDUX architecture (Petrie 1991) with HTN planning in mind, maintains dependencies among SHOP task nodes, allowing SHOP to monitor changes in a tasks preconditions. This

Knowledge Base and Similarity
As we have already explained, CTP2 is a very complex game in which the player must manage several different types of resources: units, city improvements, technical advances, wonders, etc. Furthermore, each time a player uses his turn the game time will advance, so a normal game will cross different ages (stone age, ancient age, modern age, etc). In each age different features are available. Clearly, the complexity of this environment is substantial: there exist hundreds of features that interact in different ways depending upon the stage of gameplay. All this information can be intuitively described using taxonomies. Actually, the game user documentation includes several tables and graphs in which all these resources are classied. The use of these tables and graphs represent a suitable way to describe complex worlds and so this kind of documentation can be found in several strategy games. We chose to use ontologies, as a generalization of taxonomies, to represent not only the subclass relations but a more complete description of the domain. Ontologies are an expressive and standard mechanism to represent reusable knowledge that has been successfully used in several areas. It is evident that these ontologies keep knowledge, and our goal is to use this information in the retrieval and adaptation phases of our case-based planner to improve the performance and accuracy. This way, the planner is able to use two main knowledge sources: the cases, that represent concrete past experiences, and ontologies, that represent general knowledge about the domain. In this sense, our approach can be described as a knowledge-intensive case-based planner (KI-CBP). In gure 3 a small part of our ontology is presented (the current ontology uses more than 60 dened concepts and 400 instances to represent the world). Each entity of our world can be classied using different criteria. For instance, units are classied by the environment in which they operate (ground, water, air), the age they become available (ancient, renaissance, modern, etc) and by their military features. In the same way, the advances are classied by the age and the technological area (Construction, Economics, Cultural, Medicine, etc). We will use this ontology to compute similarities between different entities. Intuitively, two entities will be more similar the closer they are in the hierarchy and the more parent concepts they share. Let us remember the whole retrieve process of our casebased planner. Assume that Repair-SHOP needs to build a new plan to achieve some goals in the current state of the world. At this point, Repair-SHOP asks the jCOLIBRI component for the most similar case in the case base to achieve those goals in the current state. All the previous plans are stored in an ontology indexed by goals and initial states. Then, using the classication capabilities of DLs, a set of previous cases is retrieved using only some primary features. After that, the retrieved cases will be ordered using more accurate numerical similarity functions and the most similar case is returned to the planner for adaptation. These similarity metrics are discussed in next section. The process we describe is quite complex compared to the standard foot-printing similarity metric used in CBP, which

only counts the number of equivalent predicates in the states. However, we think that by using complex retrieval metrics we will get better cases that will be easier to adapt, reducing the adaptation time and improving the quality of the nal plan. We can measure the accuracy of the retrieval as the inverse of the plan adaptation effort.
DL and Ontology-Based Similarity
Description Logics (Baader et al. 2003) are a set formal languages (subsets of First Order Logic) that are typically used to formalize ontologies and reason with complex worlds. This formalism has been studied for several years and its features are well dened. An ontology is compound of a TBox (terminological information or concepts) and a ABox (asserted information or instances). The TBox contains the concepts, roles (relations between concepts) and their denitions, and the ABox contains the instances. For example, the concept Ancient Advance is dened as the intersection of the concepts Advance and Ancient Item. In the same way, an Ancient Item is dened as anything with a role hasAge with the value AG Ancient. Ancient Advance Advances Ancient Item Advances {AD Agriculture AD Chemistry.} Ancient Item hasAge.{AG Ancient} Ages {AG Ancient AG Renaissance.}. We use the TBox to represent the domain constraints, i.e. the domain information that will not change, and the ABox to represent the current state of the world. This way the concept City will represent the terminological denition of what is a city in our domain, and its instances will represent the current cities in an specic state of the game. The idea of using an ontology to represent the state in planning has been previously proposed in (Sirin 2006), for the Semantic Web Services domain. However, in that work they use a different approach than ours for the planning part. The main features of DLs are that they can automatically check the consistency of the ontology (if there exists at least one model for the ontology), and they can classify new concepts and instances. The consistency checking is useful when creating the ontology to check that there are no impossible denitions. The reader must take into account that we are modeling very complex worlds and it is very easy to make mistakes. The automatic classication of new concepts and instances classies the information about the new states and will make easier to compute similarities (Gonz lez-Calero, Daz-Agudo, & G mez-Albarr n 1999; a o a Salotti & Ventos 1998). The main two approaches to compute the similarity using ontologies are: Classication based retrieval using DL classication capabilities. A new concept is built with the common properties that we are looking for, then this concept is classied and its instances are retrieved. Another variation is to start with an instance, look for the most specic concepts of which this individual is an instance, and then retrieve all the instances of those concepts.

Figure 3: Small part of the ontology used to represent the domain in the game CTP2 Computational based retrieval. In this approach numerical similarity functions are used to assess and order the instances. The use of structured representations of the knowledge requires similarity metrics to compare two differently structured objects, in particular, objects belonging to different classes. Usually the similarity is determined recursively in a bottom up fashion (Bergmann & Stahl 1998), i.e., for each simple attribute, a local similarity measure determines the similarity between the two attribute values, and for each complex attribute a recursive call compares the two related sub-objects. Then the similarity values returned are aggregated (e.g., by a weighted sum) to obtain the global similarity between the initial objects. Different weights can be used to represent the varied importance of properties in the similarity measure. In general, the similarity computation between two structured cases can be divided into two components that are aggregated (Bergmann & Stahl 1998): the computation of a concept based similarity that depends on the location of the objects in the ontology (or intra-class similarity) and the computation of a slot-based similarity (or inter-class similarity) that depends on the llers of the common attributes between the compared objects. Figure 4 shows the intraclass similarities implemented in jCOLIBRI. In our system we will use both approaches. The classication based retrieval will retrieve a set of most similar cases to our current problem taken into account only the most important features, and then, numerical similarity functions will be used to order those retrieved cases using more accurate metrics. All this functionality will be provided by the framework jCOLIBRI that has already implemented all these similarity metrics. Here we propose a very trivial example in which the advantages of our approach in terms of quality are easy to check. Imagine that in the current state of the world we have 2 units: a warrior and a submarine, and our goal is to destroy an enemy city. In our case base there are only two cases with the same goal. In case 1 there is only one unit, a warrior. In case 2, there are two units: a knight and a destroyer. If the foot-print similarity is used for retrieval, then case 1 will be selected because there is 1 match (the warrior unit) against 0 matches with the second case. However, case 2 is in actuality more similar because a knight is similar to a warrior (both are from the ancient age and ground military units) and a submarine is similar to a destroyer (modern age and water military units). Using the ontological approach all of these similar qualities will be taken into account and case 2 will consequentially be selected.

Current Status and Future Work
In this paper we have presented our ongoing effort to integrate case-based planning techniques with knowledge intensive case-based reasoning using ontologies. In order to reduce the size of the search space, most approaches to planning represent the state of the world using propositional logic. In complex domains, such as real time strategy games, the expert may nd more natural ways to describe the world using object-oriented representations with inheritance. One of the main features of Repair-SHOP is its ability to accelerate the planning process. It does so by reusing previous plans that can be efciently adapted when some conditions required by the plan are not met in the current state. The ultimate goal of the work presented here is to determine whether using a rich representation of the domain for retrieval purposes may result in gains on speed and accuracy of the planning process. Speed ups may come from a more accurate retrieval that results in reduced adaptation effort and therefore reduce the time to obtain a plan, or from the reduction of the size of the case base resulting from a more expressive language to describe the cases. The accuracy of the case retrieval process will need to be measured in terms of the adaptation effort required along with the performance (i.e., game score) obtained by the resulting plans.

fdeep basic(i1 , i2 ) =

max(prof(LCS(i1 , i2 ))) max (prof(Ci ))

fdeep(i1 , i2 ) =

max(prof(LCS(i1 , i2 ))) max(prof(i1 ), prof(i2 ))
cosine(i1 , i2 ) = sim(t(i1 ), t(i2 )) =

di t(i1 )

(super(di , CN ))

di t(i2 )

(super(di , CN ))
detail(i1 , i2 ) = detail(t(i1 ), t(i2 )) = 1
CN super(c, C) LCS(i1 , i2 ) prof(c) t(i) prof(i)
is the set of all the concepts in the current knowledge base is the subset of concepts in C which are direct or indirect superconcepts of c is the set of the least common subsumer concepts of the two given individuals, i.e., the most specic concepts both individuals are instances of is the depth of concept c, i.e., the number of links in the longest path from c to the top concept following the concept-superconcept relation is the set of concepts in CN the individual i is instance of = max(prof(t(i))), where i is an individual
Figure 4: Concept based similarity functions in jCOLIBRI At this point we have successfully integrated in a single architecture the game CTP2 with Repair-SHOP and jCOLIBRI , demonstrating the technological feasibility of the approach. From this point, we are going to start building a case base large enough to run the experiments that would demonstrate the benets of the approach. Cases may be obtained by recording actual users playing the game and by using Repair-SHOP to generate plans by running it against human or articial oponents. based reasoning. In Lambrix, P.; Borgida, A.; Lenzerini, M.; M ller, R.; and Patel-Schneider, P. F., eds., Descripo tion Logics, volume 22 of CEUR Workshop Proceedings. CEUR-WS.org. Gundevia, U. 2006. Integrating war game simulations with ai testbeds: Integrating call to power 2 with tielt. Masters thesis, Lehigh University. Hoang, H.; Lee-Urban, S.; and Mu oz-Avila, H. 2005. Hin erarchical plan representations for encoding strategic game ai. In Young, R. M., and Laird, J. E., eds., AIIDE, 6368. AAAI Press. Kambhampati, S., and Hendler, J. A. 1992. A validationstructure-based theory of plan modication and reuse. Articial Intelligence 55(2-3):193258. Mu oz-Avila, H., and Weberskirch, F. 1996. Planning for n manufacturing workpieces by storing, indexing and replaying planning decisions. In AIPS, 150157. Mu oz-Avila, H.; Aha, D. W.; Nau, D. S.; Weber, R.; Bresn low, L.; and Yaman, F. 2001. Sin: Integrating case-based reasoning with task decomposition. In IJCAI, 9991004. Nau, D.; Cao, Y.; Lotem, A.; and Mu oz-Avila, H. 1999. n Shop: Simple hierarchical ordered planner. In Proceedings of the Sixteenth International Joint Conference on Articial Intelligence (IJCAI-99), 968973. Paolucci, M.; Shehory, O.; Sycara, K. P.; Kalp, D.; and Pannu, A. 1999. A planning component for RETSINA agents. In Agent Theories, Architectures, and Languages, 147161.

References

Aha, D. W.; Molineaux, M.; and Ponsen, M. J. V. 2005. Learning to win: Case-based plan selection in a real-time strategy game. In Mu oz-Avila, H., and Ricci, F., eds., ICn CBR, volume 3620 of Lecture Notes in Computer Science, 520. Springer. Baader, F.; Calvanese, D.; McGuinness, D. L.; Nardi, D.; and Patel-Schneider, P. F. 2003. The description logic handbook: theory, implementation, and applications. New York, NY, USA: Cambridge University Press. Bergmann, R., and Stahl, A. 1998. Similarity measures for object-oriented case representations. In EWCBR, 2536. El-Kholy, A., and Richards, B. 1996. Temporal and resource reasoning in planning: The parcPLAN approach. In Wahlster, W., ed., Proc. of the 12th European Conference on Articial Intelligence (ECAI-96), 614618. Wiley & Sons. Gonz lez-Calero, P. A.; Daz-Agudo, B.; and G meza o Albarr n, M. 1999. Applying DLs for retrieval in casea
Petrie, C. 1991. Planning and Replanning with Reason Maintenance. Ph.D. Dissertation, University of Texas at Austin, Computer Science Dept. Recio-Garca, J. A.; S nchez-Ruiz, A. A.; Daz-Agudo, a B.; and Gonz lez-Calero, P. A. 2005. jCOLIBRI 1.0 in a a nutshell. a software tool for designing CBR systems. In Petridis, M., ed., Proccedings of the 10th UK Workshop on Case Based Reasoning, 2028. CMS Press, University of Greenwich. Recio-Garca, J. A.; Daz-Agudo, B.; Gonz lez-Calero, a P. A.; and S nchez-Ruiz, A. A. 2006. Ontology based a CBR with jCOLIBRI. In Ellis, R.; Allen, T.; and Tuson, A., eds., Applications and Innovations in Intelligent Systems XIV, 149162. Springer-Verlag London. Salotti, S., and Ventos, V. 1998. Study and Formalization of a Case-Based Reasoning system using a Description Logic. In EWCBR, 286297. S nchez-Pelegrn, R.; G mez-Martn, M. A.; and Daza o Agudo, B. 2005. A CBR module for a strategy videogame. In Aha, D. W., and Wilson, D., eds., 1st Workshop on Computer Gaming and Simulation Environments, at 6th International Conference on Case-Based Reasoning (ICCBR), 217226. Sharma, M.; Holmes, M.; Santamaria, J.; ; Irani, A.; Isbell, C.; and Ram, A. 2007. Transfer learning in real-time strategy games using hybrid cbr/rl. In Proc. of the 20th International Joint Conference on Articial Intelligence (IJCAI07). Sirin, E.; Parsia, B.; Grau, B. C.; Kalyanpur, A.; and Katz, Y. 2007. Pellet: A practical OWL-DL reasoner. Journal of Web Semantics 5(2). Sirin, E. 2006. Combining Description Logic reasoning with ai planning for composition of web services. Ph.D. Dissertation, University of Maryland. Souto, J. 2007. A turn-based strategy game testbed for articial intelligence. Masters thesis, Lehigh University. Srivastava, B.; Kambhampati, S.; and Do, M. B. 2001. Planning the project management way: Efcient planning by effective integration of causal and resource reasoning in realplan. Articial Intelligence 131(1-2):73134. van der Krogt, R., and de Weerdt, M. 2005. Plan repair as an extension of planning. In Proceedings of the International Conference on Planning and Scheduling (ICAPS05), 161170. Veloso, M. M. 1994. Planning and Learning by Analogical Reasoning, volume 886 of Lecture Notes in Computer Science. Springer. Wareld, I.; Hogg, C.; Lee-Urban, S.; and Munoz-Avila, H. 2007. Adaptation of hierarchical task network plans. In Proceedings of the Twentieth International FLAIRS Conference (FLAIRS-07).