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)."
Yes, I find the summary comprehensible and know what a genetic algorithm is. I don't know what an explanation of genetic algorithms is doing in the summary, though. Linking the Wikipedia page would be much more effective, since so many readers get nothing out of this explanation (either they already know what a GA is and, like me, are annoyed at the minor waste of time, or they don't and a brief explanation isn't enough).
Well, to be fair there's a lot more to SC2 than just build-orders. :-) Build orders are mainly concerned with the "macro" aspect of SC2 gameplay, which is base management and economy, and they're also relevant only in the opening. Everything past the 7 or 8-minute mark is beyond build orders. Good micro (unit-level manipulation of movement and actions), harassment of workers, and timed expansions all kick in after that point, and those become the difference between winning a game and losing a game.
Also, there is an element of "good practices" in SC2. Rushes, especially "all-in" rushes (referred to by TFA) are generally considered bad practice. Beating your opponent every time is cool, but this is usually indicative of a game imbalance that Blizzard will probably patch at some point down the line, at which point you'll rapidly fall in the leagues as you lose to high-level players clued in on countering that or who simply have the good practices to beat it (like early scouting, etc.).
The other (more important) factor is that a gamer specializing in an all-in rush deteriorates his/her gameplay, because he won't have the variety to compensate for a failure of that rush. A rush usually means a sacrifice of something or the other (the tight game-mechanics of an SC2 opening means there's always an opportunity cost; to get that extra army, your economy suffers, or to get those extra resource-collectors, your army will be smaller). All-in rushes, and rushes in general sacrifice some thing or the other which a good opponent can exploit if he/she manages to push back the rush. Someone over-playing one tactic will lack the skills to compensate for its failure, so varying one's game by mastering different build-orders and plays is the better way to do this (if slower).
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".
You have three choices (assuming the Total War series cannot be counted as viable Multi Player choices)
More Strategic: R.U.S.E (awesome visuals, very autonomous units, very indirect control)
More Direct: Supreme Commander - Forged Alliance (decent visuals, unprecedented scope of war and great control over your units)
More StarCrafty: Supreme Commander 2 (think ugly Starcraft with the ability to fully zoom out)
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.
No one just plays the dang game anymore. Its all about winning via pre-built key sequences.
Yes, and nowadays football games are all about winning using pre-planned passes, and chess is all about memorizing opening moves. /sacarsm
At your level when ppl are just learning how the game works, then, yes, a pre-planned built sequence can often win you the game. Much like a football team with well practiced passes can win low level games with little more than executing their practiced passes. Or beginning chess players can win games by playing from memorized opening moves.
However, once you reached a higher level, then if you cannot adapt your strategies to the situation at hand, you WILL lose against opponents who can.
This is the same with ANY competitive sports.
Yes, that involves a lot of practice and hard work. Seems like you just never reached that level. (Neither did I, BTW). But you can see it in the pro-level SC games in Korea. How the players respond to the unexpected is what differentiates good and not so good players.
Oliver.
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.
-1, Misinformed
The AI does not get double resources (although on Very Hard and Insane it does get an extra amount, but not double), and it does not do the absolute best it can. I guarantee you that if given the source code I could improve it, by simply exploiting the hell out of its APM advantage. The reason is that the AI has imperfections designed in; it is designed to respond somewhat superficially like a human opponent and not exploit godly micro tricks that a 2000+ APM computer could use. Here are a few things to get started: roach burrow micro; hidden queens in overlords microing transfuse, perhaps on dancing mutalisks; blink micro tricks; rotating damaged infantry in and out of bunkers; thorship micro.
Yes, making a proper strategic AI is very hard. But the included AI has a lot of room to improve in tactics, just by virtue of the ridiculous APM it can exploit.