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)."
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)
If you read TFA, the fitness function defined as distance (in time and resources) from having a desired set of units. The example provided is having 7 roaches. The GA isn't scoped to fight battles or develop a strategy; the programmer defines the desired end-state, and the GA finds an optimum path to get there. It's a tool for developing build-orders, not an AI to play the game for you.
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.
It's completely different. The whole point of evolutionary algorithms is that you start from a population of initial builds (the "previously entered"), and, at each iteration, it creates new builds by altering the existing ones at random.
Given enough builds, a lot of those alterations perform a bit worse than their original, and eventually gets removed, while others perform a bit better, and thus gets used as a base for other variations.
If your performance space is relatively smooth, that kind of approach is extremely powerful at finding minimas in the performance space. If it's very crinkled, it leads to chaos, but I don't think it's the case in this problem.
Actually, only a handful of people complain about this, and mostly those that haven't even played the game. On forums visited by actual players, nobody complains about this at all.
Sure, there are a bazillion complaints about other trivial things :), but people are generally interested in figuring out how to beat each other, as there certainly isn't a "one build order to win them all".
Never underestimate the bandwidth of a 747 filled with CD-ROMs.
The matchmaking system in SC2 is very good at matching you against someone with the same skill. In fact, it's almost too good.
In SC1, 1 or 2 out of 10 games would be close. The other 8 would be a blowout by one player or the other. In SC2, 9 out of 10 games are close. It can be very exhausting.
I wish they would put a little wander in the matchmaker giving you a wider variety of games (some easy, some hard, some close). You can learn a lot by watching a replay where you get destroyed by a higher level player.
Kiteboarding Gear Mention slashdot and get 10% off!