Thesis First Draft

Here is my first draft.

Thesis Progress Report 2/24: BARC Updates Complete

Earlier today I finished adding in XML loading/saving in BARC.  I used XStream to save the building state list, and then reinitialize the list from the the XML file.  I implemented the Logger, and then fixed the performance updating at the end of the game.

The BARC framework is complete, but the real tactics need to be added in (Right now it is just a dummy comment).  I plan on trying to communicate with the authors of Learning To Win to get the tactics they used, but in the mean time I will be working on developing some simple tactics to be used.

The remaining steps are:
1. Explore Wargus APIs
2. Tell Wargus to use scripts produced by BARC
3. Find a way to get Wargus to send BARC the game information
4. Find a way to automate the games, recording game information.

Thesis Progress Report 2/18: Retrieval Complete

I have begun implementation of BARC, and I have successfully implemented the retrieval section of it.  It will enter exploration mode at the appropriate times, generate new cases, and select the best matching case given a game description.

Currently the BARC will start up from a text file with a description of the states and starting tactics.  It is able to retrieve cases and add new cases, along with printing out a .lua file.

The next steps in developing BARC are:

1. Add case performance evaluation
2. Add saving/loading case base from xml file
3. Add logger file to aid in debugging
4. Create and add actual tactics instead of placeholders which are currently used.
5. Write up documentation for interfacing with BARC

The next steps outside of BARC development are:
1. Explore Wargus APIs
2. Find a way to have Wargus send game state information to BARC
3. Find a way to have Wargus use lua script provided by BARC
4. Find a way to automate games

Extended Abstract

To view the extended abstract for my thesis, click here.

Thesis Progress Report 2/11: Switching to Custom CBR

After examining the Case-Based Reasoner (CBR) described in the "Learning to Win" article (David Aha et al.), I realized that the jCOLIBRI system would not be able to accomplish everything that I needed it to, and if it could it would take more time figuring out how to implement it than creating a new CBR system would actually take.

The Case-Based Reasoner described in Learning to Win is slightly different than others.  It is built around the idea that the game can be in 20 states.  These states are defined by what buildings have been constructed.  These states are organized in a lattice network based on what states can follow from a previous state.  The following figure is the lattice as shown in the Learning to Win article:

Each state has associated with it a set of tactics to be used in that state.  In the paper, there are 8 different tactics included in this (as indicated by a-h in the figure), each designed to counteract a specific opponent strategy.  I will be starting out with the same number of tactics as there are states which follow from the current state; so for instance state one will have 3 different tactics.  Implementing the other tactics is a later project goal, and I hope to be able to receive these tactics from the original authors.

The CBR has the responsibility of selecting which tactic to use while the game is in the current state.  Only one tactic will be used per state per play through.  Upon entering the state, the CBR must evaluate the current state of the game, and decide which tactic it will use while in the state.  Once it decides, the tactic does not change until it enters the next state.  

When the CBR first begins playing, it will be in an 'exploration mode'.  This means that during this time it will choose each tactic x amount of times to get an idea of how each one performs.  Once the exploration mode has finished, it will begin evaluating each state normally.

The normal workflow of the CBR selecting a tactic for a state is as follows:

1. The CBR enters a new lattice state.
2. The CBR receives information about the current state of the game (such as number of workers, combat units, etc.)
3. The CBR uses the the current game state to query its database of cases associated with the current lattice state, and returns a set of the k closest matches using a k-nearest neighbor algorithm.  It does this by using the information about the game state as an 8 dimensional coordinate, and then checks it against the previous game state cases that were used by using the distance formula.
4. The CBR selects the case with the highest performance rating.
5. The CBR implements the tactic in the case.
6. The CBR moves on to other cases.
7. At the end of the game, the CBR saves the cases it used by either creating new cases if the exact cases did not exist, or updating the performance of the cases if they did exist.

If in step 4 the CBR finds that none of the nearest neighbors have a performance rating of above .5, the CBR will enter exploration mode for this step and try one of the least used tactics.

The jCOLIBRI CBR was not set up to handle cases in this way, and thus the idea for BARC (Barton CBR) was born.  BARC was designed to fit these criteria:

1. Organize tactics and cases by state
2. Save cases for later use
3. Update the performance of a case when it has been selected
4. Have an 'exploration mode' for when the CBR first starts.
5. Enter 'exploration mode' when a none of the retrieved cases have a performance above .5.
6. Create new cases.
7. Retrieve k-closest cases from the knowledge base
8. Select case with best performance from the k-closest cases.
9. Send selected tactic to game.
10. Select 1 case per state.

More specific design and implementation notes on BARC will follow in the coming posts.

3 Page Abstract

Here is my original 3 page abstract for my thesis.  Many things have changed over the past few weeks, and these will be updated shortly. To view the original PDF, click here.

Using Case-Based Reasoning to Improve Real-Time Strategy Game AI

Abstract

In recent years using real-time strategy (RTS) games as a test bed for Artificial Intelligence techniques has become increasingly popular.  RTS games allow an environment that is complex enough to present the AI with a sufficiently challenging situation. These games also allow an easy way to evaluate the effectiveness of the technique.  In this paper, I will build on the work of Aha et all, who in [1] used a custom built Case-Based Reasoner to govern an AI in Wargus: an open source RTS engine, that learns to play better as it plays more games.  I will be replicating their experiment with a different Case-Based Reasoner.  I will be working with jCOLIBRI, a freely available Case-Based Reasoner.
Problem Definition
My work will be on addressing four of the problems in RTS game AI: adversarial real-time planning, decision making under uncertainty, spatial and temporal reasoning, and resource management.  These can all be thought of as higher level decisions made by the AI.  My work will not deal with lower level AI, or individual unit AI (troop pathfinding, worker reaction to being attacked, etc).  Instead it will focus on the high level decisions regarding strategy. One of the largest problems with addressing the decision making of the AI is that the decision space, or number of possible actions, grows exponentially with the number of workers and troops.  The decision space can be defined with the following equation [1, p5]:

O(2^W*(A*P) + 2^T*(D+S) + B*(R+C))
Where: 
W = current number of workers 
A = assignments workers can perform 
P = average number of workplaces 
T = number of troops (fighters plus workers) 
D = average number of directions that a unit can move 
S = choice of troop's stance 
B = number of buildings 
R = average choice of research objectives at a building 
C = average choice of units to create at a building 

Shortly into a game, the amount of moves grows too large to even consider all options.  One of the first pieces of the problem of developing a high level AI is limiting the decision space.  

When the decision space is limited, the problem becomes choosing the best option given the current situation. The best option will be defined as the one that will increase the likelihood of AI attaining victory.  Case-Based Reasoning will be used to determine which option is the best at the time by pulling from a knowledge base of other situations faced by the AI.  

In solving the problem of which solution is best the AI would also solve the four problems mentioned above.  It would solve adversarial real-time planning by changing the AI's plan depending on the changing environment because as the game situation changes the AI may choose a different solution.  Decision making under uncertainty would be solved because by selecting a best solution at the time, the AI would be making a decision under uncertainty.  Selecting the best solution also solves spatial and temporal reasoning by learning when the best times to attack are, and what building patterns work best.  Resource management is also taken care of because the AI will select the option that is the best use of it's money at the time.  Thus, the important problem is what is the best decision for the AI to make at this time to put itself in a position to win the game?
Procedure
I will be using the jCOLIBRI Case-Based Reasoner as the system to govern the AI.  This system will be responsible for retrieving cases based on the current game state, proposing a solution, modifying the solution, applying the solution, evaluating the solution, and saving the case for future use.  Most of this will be handled by the built in system, but I will have to write how the cases are retrieved, what how they will be indexed, and what information should be stored.  For much of this, particularly the indexes, I will be referring to the work in [1].  
I will be using Wargus as the game to test my AI.  Wargus is an open source RTS game based on the Stratagus engine.  It is based on the game Warcraft II, and is what was used in [1].  The game is scripted in Lua, and since jCOLIBRI is written in Java, I will be using the LuaJava libraries to communicate between the two.
In [1], the TIELT system was used to communicate between the CBR and the game engine.  This system was able to plug in a game and AI module, and then evaluate it.  The TIELT system is no longer under development, and currently has issues running on my system, so I will be unable to use this.  Instead, I will need to write the interface between jCOLIBRI and Wargus so that Wargus can send state information to jCOLIBRI, and jCOLIBRI can send AI commands to Wargus.  Additionally, I will need a way to automate tests and record the results.
Bibliography
[1] David W. Aha, Matthew Molineaux, Marc Ponsen.  Learning to Win: Case-Based Plan Selection in a Real-Time Strategy Game. 2005.