Forgot your password?
typodupeerror
Programming Real Time Strategy (Games) Games

Developing StarCraft 2 Build Orders With Genetic Algorithms 200

Posted by Soulskill
from the nerd-intersection dept.
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)."
This discussion has been archived. No new comments can be posted.

Developing StarCraft 2 Build Orders With Genetic Algorithms

Comments Filter:
  • by cgenman (325138) on Tuesday November 02, 2010 @02:42AM (#34098490) Homepage

    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.

  • by Anonymous Coward on Tuesday November 02, 2010 @02:51AM (#34098524)

    Nah, mutations, multiple iterations and choosing good stop conditions will avoid getting caught in local minmums. This isn't hill climbing.

  • by thygrrr (765730) on Tuesday November 02, 2010 @03:50AM (#34098700)

    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)

  • by Gibbs-Duhem (1058152) on Tuesday November 02, 2010 @04:02AM (#34098736)

    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)

    by Ruke (857276) on Tuesday November 02, 2010 @04:07AM (#34098758)
    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.
  • by moenoel (1897920) on Tuesday November 02, 2010 @04:47AM (#34098854)
    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 [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.
  • by Anonymous Coward on Tuesday November 02, 2010 @05:34AM (#34098972)

    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.

  • by varcher (156670) on Tuesday November 02, 2010 @06:01AM (#34099056)

    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.

  • by Pulzar (81031) on Tuesday November 02, 2010 @06:44AM (#34099174)

    A lot of people seem to complain about this and especially about the realtime requirement in strategy

    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".

  • by Fahrvergnuugen (700293) on Tuesday November 02, 2010 @09:09AM (#34099822) Homepage

    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.

  • by JTsyo (1338447) on Tuesday November 02, 2010 @10:01AM (#34100280) Journal
    There was a story on Starcraft AI competions, they could defeat some people but not the pros.
    http://games.slashdot.org/article.pl?sid=10/10/15/1411228 [slashdot.org]

Given its constituency, the only thing I expect to be "open" about [the Open Software Foundation] is its mouth. -- John Gilmore

Working...