Developing StarCraft 2 Build Orders With Genetic Algorithms 200
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)."
Re:Does anyone else find the summary comprehensibl (Score:3, Informative)
The entire summary is devoted to explaining what a genetic algorithm is, though I'm not convinced this is a particularly "genetic" genetic algorithm.
I've known this technique to be used frequently in game development. It sounds like someone is using it to find good opening gambits in Starcraft. I say "good", because generational algorithms can frequently find "local" optimal solutions, whereas there may be better solutions further away from your breeding start point. You're just never sure you've found the best solution.
The actual interesting points come in the details of the strategies the program found, but those are only really of interest to Starcraft nerds.
Re:Does anyone else find the summary comprehensibl (Score:1, Informative)
Nah, mutations, multiple iterations and choosing good stop conditions will avoid getting caught in local minmums. This isn't hill climbing.
Re:On the subject of games (Score:4, Informative)
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)
Re:On the subject of games (Score:3, Informative)
A recent game like that is called Globulation 2 (Linux, not sure about other platforms). Instead of telling unit X to do task Y, you say "I want task Y done, with as close to N units working on it as possible." and the AI for your team does its best to fulfill your requests. If you ask for impossible things (say, building 20 buildings, each with 10 units, while you only have 100 units), it instead prioritizes as well as it can based on available resources and location of units. You can also script your own AI if you like, they have a large group of people that work hard on making the AI as strong as possible by trying to script their own winning strategies. It's sort of a modern extension of the ancient game "Simant" where you could put down smells and the ants would respond accordingly without individual control. You paint areas you want scouted (or not), and the scouts go and check it out. You paint areas where you want defenders, and your defenders are allocated as well as possible.
My primary complaint was the lack of diversity in the game. Only three unit types, which could be upgraded along only a single path, and maybe a half dozen or a dozen building types. It was really entertaining until I solved the game to my satisfaction, and I haven't really played since. A fork with more types of units might be a serious contender for best game on Linux.
Re:The problem is... (Score:4, Informative)
Re:This is why I hate the RTS genre (Score:5, Informative)
To (not literally) quote Sean 'day[9]' Plott [day9tv.blip.tv]: 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.
Re:All your base are belong to humans... (Score:2, Informative)
In the developer commentary that comes with the Collector's Edition, the primary developer of the AI (and also Blizzard's primary engine developer) says that the only difference between the difficulty levels is how many queued "actions" are allowed to be executed per second. As the AI plays, it queues up orders it wants to perform and weights them accordingly. The AI does not cheat at all, and you can verify this by watching a replay of a game against a computer opponent.
Re:Does anyone else find the summary comprehensibl (Score:4, Informative)
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.
Re:This is why, if I get SC2 (Score:4, Informative)
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".
Re:This is why, if I get SC2 (Score:4, Informative)
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.
Re:All your base are belong to humans... (Score:2, Informative)
http://games.slashdot.org/article.pl?sid=10/10/15/1411228 [slashdot.org]