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.