What model best suits optimizing for a real-time strategy game?

Question

An article has been making the rounds lately discussing the use of genetic algorithms to optimize "build orders" in StarCraft II.

http://lbrandy.com/blog/2010/11/using-genetic-algorithms-to-find-starcraft-2-build-orders/

The initial state of a StarCraft match is pre-determined and constant. And like chess, decisions made in this early stage of the match have long-standing consequences to a player's ability to perform in the mid and late game. So the various opening possibilities or "build orders" are under heavy study and scrutiny. Until the circulation of the above article, computer-assisted build order creation probably wasn't as popular as it has been recently.

My question is... Is a genetic algorithm really the best way to model optimizing build orders?

A build order is a sequence of actions. Some actions have prerequisites like, "You need building B before you can create building C, but you can have to build A at any time." So a chromosome may look like AABAC.

I'm wondering if a genetic algorithm really is the best way to tackle this problem. Although I'm not too familiar with the field, I'm having a difficult time shoe-horning the concept of genes into a data structure that is a sequence of actions. These aren't independent choices that can be mixed and matched like a head and a foot. So what value is there to things like reproduction and crossing?

I'm thinking whatever chess AIs use would be more appropriate since the array of choices at any given time could be viewed as tree-like in a way.

Answer 1

Yes, the genetic algorithm is the best way to model optimizing build order. The pros of using GA will be listed below:

In this case, what they did is solve a multi-objective optimization problem using a genetic algorithm. The goal is to optimize some metrics (time) with respect to some objective (building 8 units of this type) and 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.

In a GA, a population of individuals, creatures, or phenotypes to an optimization problem is evolved toward better solutions. Each solution(creatures in the population) has some properties like its chromosomes or genotype, which can be mutated and altered(can be changed); traditionally, solutions are represented in binary as strings 0s and 1s.