Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

This "news" is from 2010.

2^10=1024

It's unfortunate that the only other comments so far are about the fact this article is a few years old. Clearly what's interesting here is the method itself, not its immediate impact on the StarCraft II metagame.

Real-time strategy games have recently stimulated a lot of great research [1] because they exhibit several interesting subproblems such as resource allocation optimization, strategy selection, or plan optimization (like here). It also has the nice side effect that it makes it easy to evaluate the quality of the resulting plan in a real-world setting and see how it fares when certain assumptions are relaxed (non-static opponents, effect of imperfect strategy execution, etc.).

In this case what they did is solve a multi-objective optimization problem [2] using a genetic algorithm (a popular way to do so). The goal is to optimize some metric (e.g. time) with respect to some objective (e.g. "build 8 units of this type") and some constraints (resource requirements, unit trees). Of course you could perform some form of search in the solution space, but this space can become pretty big pretty fast and for complex games it's fairly easy to be stuck in a local optimum because the net effect of some choices can be hard to assess (some can be bad in the short term but be a nice set-up in the medium term, and two bad tactics can interact to be a good strategy). In contrast, a genetic algorithm can help find the global optimum.

While it's not as big as the article makes it sound (it's not a "winning build" per se -- more like a method to find the fastest way to achieve a known opening), if you combined plan selection methods (e.g. [3]) with plan-optimization techniques like this one, you could come up with an IA that is able to come-up with both near-optimal tactics (how to achieve an objective) and strategies (which objectives to pursue). Pretty interesting stuff overall, and applicable to more than just real-time strategy games.

[1] http://scholar.google.com/scholar?q=%22real-time+strategy+ga...

[2] http://en.wikipedia.org/wiki/Multi-objective_optimization

[3] http://link.springer.com/chapter/10.1007/11536406_4

I used that strategy a few times when it came out. I found it interesting to see how fast humans could responded and nullify the advantage. I think after 3-4 wins with the strategy I started getting countered effectively.

So it took a few days and all the players at my level knew about it and could handle it easily.

It's hard to beat a general purpose strong AI in the long run!

I don't think breadth first search would have been the right approach. The search space is actually quite huge for this. Also, the algorithm wasn't built to create a build that wins the fitness was simply how fast they could produce the army the user inputs.

What stands out is if you had asked anyone even a professional player to build this exact army composition (7 roaches) they would almost certainly not have pulled it off as fast as the method this algorithm discovered. The algorithm was able to do it by doing a few tricks that normally aren't intuitive but, work out so your resources match up perfectly to make the build happen.

Also, I can confirm as a mediocre Starcraft player the build was quite powerful.