Starcraft Genetic Programming
I was keeping track of these on their own webpage but I figure I might as well move as much as I can over here. Here’s a few posts about the project I did developing Starcraft AI with genetic programming.
Update 12/21/2009
Here’s the end of the semester update. I polished the project in its current state and gave a presentation on it. I think I’ll keep working as there are some definite improvements to be made and it has potential. The newest (still ugly) version of the code is available on github.
Here’s a link to the slides from my presentation. Check out a video of a decent run against the default A.I after the break. You can see some interesting behaviors that have evolved.
Update 12/10/2009
Well, I finally got things up and running in an evolutionary-y style. Since the last update my strategy has changed a bit. Here’s the outline:
The framework now raises events that each unit can respond to. The events are modeled after what a human player would react to. They are mostly of the style ‘is an enemy near?’, ‘is a friend near?’, ‘is my health low?’. Each part of the chromsome, an actor for each Zealot, chooses a set of actions to respond to an event with. The actions are of the style ‘move to x,y’, ‘move to unit’, ‘attack unit’. An initial set of chromosomes is generated and then the simulation begins running.
Each run of the simulation takes between 4 and 8 seconds (not trivial when we’re talking about thousands of runs). At the end of a run, the chromosome’s fitness is evaluated based on the number of enemy units killed and the number of friendly units left. I may tweak this some in the future as necessary.
At the end of a population, both crossover and mutation are performed. The selection process is elitist – the top 25% of the previous population are passed through as is. Then another 25% of the population are mutated randomly and added to the new population. Finally, a group of 50% of the population, 25% from the top and 25% from the bottom, are crossed over and added to the new population. This new population is then run as well and the process starts over again.
I’m serializing and storing the top portion of each population so that future runs can be seeded from some less random chromosomes
The next step is to run this for a while and see how it goes. Both the mutation and crossover will probably need some tweaking and other holes may be exposed too. Hopefully I’ll learn something interesting and useful though to improve it. Oh, and the new version of the code is up on the github project page. It’s not the prettiest thing in the world right now though.
Update 12/2/2009
Update: I submitted the basic restart support to the project as patches – hopefully it’ll be integrated soon.
As is par for the course things took a bit longer than expected. All known bugs are now out of the framework again. If you’re curious about the restarting modifications here’s the gist:
In ClientModule.cpp add at the beginning of the handleCommand() function (~line 470) this bit.
if (command == 42) {
Broodwar->sendText("Restarting game");
Broodwar->restartGame();
return;
}
Yes, it should be added to the case statement but the whole thing is kind of hacky so this isn’t doing much damage.
Then in starcraftbot.proxybot.command.CommandQueue.java add this function:
public void restart() {
doCommand(StarCraftCommand.restart, 0, 0, 0, 0);
}
and add restart to the end of the enum in starcraftbot.proxybot.command.Command.java:
public enum StarCraftCommand {
none,
...
gameSpeed,
restart,
}
The modifications are in the version of the proxybot in my git repository. Now you can call game.getCommandQueue().restart() to restart the game.
The next step is to make the proxybot rerun itself, otherwise the game would restart but the AI would just keep going. To do this, change the main() function in ProxyBot.java to this:
public static void main(String[] args)
{
while (true)
{
new ProxyBot().start();
}
}
Then modify runGame()’s update loop like this:
long startTime = System.currentTimeMillis();
boolean running = true;
while (running)
{
...
long elapsedTime = System.currentTimeMillis() - startTime;
if (elapsedTime >= 10000) //Run for 10 seconds
{
System.out.println("Restarting");
game.getCommandQueue().restart();
botThread.stop();
running = false;
}
...
}
runGame() will now return when running is false and go back to the loop in main, restarting the AI. In this code the game runs for 10 seconds and is then restarted – you could end on any condition though. Again, this code is in the git repository.
Next up is nailing down stuff that works in the behavior trees. My next update should have information on that as well as some initial crossover and mutation operators.
Update 11/30/2009
BWAPI and the Java proxy bot have gotten some updates since the last post which greatly help with some things. Unfortunately they have also been restructured which, in turn, required restructuring on my part.
I’ve modified the Java Proxy and the in-process module so that I can easily run many iterations of the game. This was essential to actually getting anywhere with genetic programming, obviously.
I’m now in the process of updating everything to work with the new API. A new version should be pushed to github tonight and I’ll also update with some information about my game restarting modifications on the off chance they’ll be helpful to somebody.
Update 11/24/2009
I now have all of the framework code up and running. The chromosome structure is defined and it’s a basic tree – I’ll put up a formal description soon. I can generate and run random trees within starcraft and see the (usually comical) results. For now each “chromosome” is a set of 9 behavior trees where each unit runs its own behavior tree. This will lend itself well to some interesting crossover and mutation operators. The next step is to get fitness evaluation up and running in such a way that I will be able to continually run new generations. At this point I’ll be able to implement the genetic operators and we’ll see where it goes from there.