Slashdot Mirror
Developing StarCraft 2 Build Orders With Genetic Algorithms
Jamie recommends a blog post from software engineer Louis Brandy explaining how using genetic algorithms to evaluate build orders in StarCraft 2 has led to some surprisingly powerful results. Quoting:
"One of the reasons build-order optimization is so important is that you can discover openings that 'hard-counter' other openings. If I can get an army of N size into your base when you do opening X, you will always lose. ... a genetic algorithm is a type of optimization algorithm that tries to find optimal solutions using a method analogous to biologic evolution (to be specific: descent with modification & natural selection). Put simply, you take a 'population' of initial build orders, evaluate them for fitness, and modify the population according to each element’s fitness. In other words, have the most successful reproduce. The program’s input is simply the desired game state. In practice, this means 'make N units' to determine some rush build order (but it also allows for other types of builds, like make N workers with some defensive structures and a small army)."
TFA's method is designed to optimize rush builds, where the goal (ex. 7 roaches ASAP) is specified by the human. It wouldn't work at all for longer games where you have to respond to your opponent, since then your goals depend on what they do. At best, I'd say this method (1) provides strong but inconclusive support for the quality of various opening builds; (2) might find better opening builds that are not commonly known to humans. (2) seems much less likely than (1). I wonder if a brute-force all-branches approach is actually possible or even better than a genetic algorithm. For the first few minutes of SC(2) you don't have many options, so the branches wouldn't become horrifically numerous until several minutes in.
In any case, this method depends on humans to specify its goals and doesn't work in larger situations. I don't think there should be any concern about this type of AI beating "human ingenuity".
A lot of people seem to complain about this and especially about the realtime requirement in strategy, but the truth is that in addition to the kind of economically suboptimal rush build orders you seem to hate, there are strategies designed to securely carry you into the midgame, where the opponent no longer benefits from memorized build orders.
Moreover, the whole gripe seems misplaced, as I doubt that the same players are against people memorizing openings in chess, board states in go or probabilities in poker. It's simply being intimidated by people better in the game than you - being afraid of losing. You must realize that a video gaming company the size of Blizzard is very aware of this, and the whole mentality is precisely why Starcraft has a very friendly ladder system, which tries to match you against people of your own skill level.
The fast and coordinated clicking stuff is only the first part of learning SC (II). Strategy comes after that.
To (not literally) quote Sean 'day[9]' Plott: If you are interested in american football and want to play various tactics on the playfield, you first need to train your body. I.E. if you are a scrawny guy, with no muscles and stamina whatsoever, you can think about football tactics all you want, but you simply won't be able to execute them for lack of the basic requirements.
Same goes for SC (II) and every (balanced) RTS in general. The *real* strategy part only comes into play, after the player mastered the basic mechanics of gameplay.