7 ms·

Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

208 points by AndyBaker 13y ago

wingi 13y ago
This "news" is from 2010.
- daken 13y ago
  And no longer applies with all the refactoring done in 4 years...
  - andrewchoi 13y ago
    Perhaps a more appropriate word is "rebalancing"; I'm sure that the code has been refactored to some extent, but the balance issues are what are salient to this article.
remon 13y ago
I'm not sure if you hav enough fingers on two hands to count the number of SC2 balance patches since November 2010. This news is a tad dated no?
- SixSigma 13y ago
  2^10=1024
  - thaumasiotes 13y ago
    This assumes e.g. that I can extend my ring finger without also extending the adjacent middle finger. ;)
    - pliny 13y ago
      2^8 = 256
    - traviscj 13y ago
      It just takes practice! https://vimeo.com/89914687 https://vimeo.com/89914687
    - kibwen 13y ago
      Rather than extending extending and retracting fingers, you can achieve this by placing your hands on a table and lifting a finger off the table in order to indicate a 1 on that digit. http://en.wikipedia.org/wiki/Finger_binary http://en.wikipedia.org/wiki/Finger_binary
  - remon 13y ago
    Haha, touche..
thomasahle 13y ago
I remember reading this and thinking "That would be so much simpler to do with a breadth first search". Sure 'genetic' sounds cool, but when the search space is as limited as it is in a build order optimization like this, you should use the right tools for the task.
- ryanator 13y ago
  I don't think breadth first search would have been the right approach. The search space is actually quite huge for this. Also, the algorithm wasn't built to create a build that wins the fitness was simply how fast they could produce the army the user inputs. What stands out is if you had asked anyone even a professional player to build this exact army composition (7 roaches) they would almost certainly not have pulled it off as fast as the method this algorithm discovered. The algorithm was able to do it by doing a few tricks that normally aren't intuitive but, work out so your resources match up perfectly to make the build happen. Also, I can confirm as a mediocre Starcraft player the build was quite powerful.
  - vladimirralev 13y ago
    The search space is not that big. It depends on the granularity of the decisions, but in SC2 most algorithms will work on the supply scale (with resources as constraint). Meaning you only have 3-5 decisions to make at any supply count. In this case considering the extractor cancel is a nice touch and I assume it was a special case because it's a known trick which makes no sense to consider for any other buildings.
    - veemjeem 13y ago
      Maybe the search space is limited in the first few minutes of the game when your opponent has also has a limited set of moves, but as the game goes on, the complexity increases exponentially. The 7 roach rush could be calculated here because the algorithm essentially completes when it reaches 7 roaches, but longer more complicated builds would be significantly harder -- like a 2-base blink all-in.
- 13y ago
pyduan 13y ago
It's unfortunate that the only other comments so far are about the fact this article is a few years old. Clearly what's interesting here is the method itself, not its immediate impact on the StarCraft II metagame. Real-time strategy games have recently stimulated a lot of great research [1] because they exhibit several interesting subproblems such as resource allocation optimization, strategy selection, or plan optimization (like here). It also has the nice side effect that it makes it easy to evaluate the quality of the resulting plan in a real-world setting and see how it fares when certain assumptions are relaxed (non-static opponents, effect of imperfect strategy execution, etc.). In this case what they did is solve a multi-objective optimization problem [2] using a genetic algorithm (a popular way to do so). The goal is to optimize some metric (e.g. time) with respect to some objective (e.g. "build 8 units of this type") and some constraints (resource requirements, unit trees). Of course you could perform some form of search in the solution space, but this space can become pretty big pretty fast and for complex games it's fairly easy to be stuck in a local optimum because the net effect of some choices can be hard to assess (some can be bad in the short term but be a nice set-up in the medium term, and two bad tactics can interact to be a good strategy). In contrast, a genetic algorithm can help find the global optimum. While it's not as big as the article makes it sound (it's not a "winning build" per se -- more like a method to find the fastest way to achieve a known opening), if you combined plan selection methods (e.g. [3]) with plan-optimization techniques like this one, you could come up with an IA that is able to come-up with both near-optimal tactics (how to achieve an objective) and strategies (which objectives to pursue). Pretty interesting stuff overall, and applicable to more than just real-time strategy games. [1] http://scholar.google.com/scholar?q=%22real-time+strategy+game%22%2Balgorithm http://scholar.google.com/scholar?q=%22real-time+strategy+ga... [2] http://en.wikipedia.org/wiki/Multi-objective_optimization http://en.wikipedia.org/wiki/Multi-objective_optimization [3] http://link.springer.com/chapter/10.1007/11536406_4 http://link.springer.com/chapter/10.1007/11536406_4
- TrainedMonkey 13y ago
  Great tutorial on genetic algorithms here: http://www.ai-junkie.com/ http://www.ai-junkie.com/
  - 13y ago
malanj 13y ago
I used that strategy a few times when it came out. I found it interesting to see how fast humans could responded and nullify the advantage. I think after 3-4 wins with the strategy I started getting countered effectively. So it took a few days and all the players at my level knew about it and could handle it easily. It's hard to beat a general purpose strong AI in the long run!
- gamegoblin 13y ago
  I used this as my main build for quite a while, and got pretty good at transitioning out of it. Kept me in platinum league pretty solidly. Not sure if you were diamond or masters, though.
  - rfrank 13y ago
    7rr specifically was pretty easy to counter, just get cannons out when you scout the early roach warren. The program from that article was pretty fun though, used it to make some absolutely ridiculous blink builds that didn't really work but were fun to try.
    - malanj 13y ago
      Yeah - I found that you had to be pretty good at moving off that build asap if you were scouted and the other player realised what you were up to.
lbrandy 13y ago
Ha. I wrote the blog post mentioned in this article that started this. As pointed out, this is an old repost(1), but perhaps interestingly (at least at a meta level) is that this is all actually HN's fault. When I first saw this thread on teamliquid, I thought "Oh man, proggit and HN will love this" so I wrote it up. And sure enough, it was near the top of both, for a day. Next came the random news articles (like this one). And here several years later is an HN repost of a blog article that only exists because HN and proggit upvoted the original blog post. You guys created the article that's being reposted :) [1] https://news.ycombinator.com/item?id=1856390 https://news.ycombinator.com/item?id=1856390 From the last time around, the most common criticisms were: 1. Without any form of crossover, it's just hill-climbing/gradient-descent, it's not really a "genetic algorithm". 2. BFS would work better (maybe. IIRC people tried BFS and there's a bunch of subtle things that make the BFS search space huge (e.g. putting workers on and off gas at certain times). Of course since we have a goal state, something like A* might win the day).
thinkbohemian 13y ago
I'm not a java programmer and currently eclipse is telling me that it's going to take 60 minutes to download. How does the program itself work? Is there some SC2 API they are using for this or did they just write down all the values and are "simulating" a SC2 build.
- maytsch 13y ago
  It's a simulation - if you ignore your opponent and assume perfect execution, the result of build orders is deterministic within pretty close bounds. There are a number of tools around to do this, here is an online version showing the build order mentioned in the article: http://www.sc2planner.com/#Zaaaap8oDaCoDjp3oFaaaaaoDaahcjoHjflllllll http://www.sc2planner.com/#Zaaaap8oDaCoDjp3oFaaaaaoDaahcjoHj... And just for fun, a more optimized version using a 13 pool in place of the 11 overpool to get the seventh roach 4 seconds earlier: http://www.sc2planner.com/#ZaaajaaaaoFaaaoDaacjhoHjflllllll http://www.sc2planner.com/#ZaaajaaaaoFaaaoDaacjhoHjflllllll If you're looking for a current GA build order optimizer, SCFusion is probably the best one: https://github.com/Carbon-12/SCFusion https://github.com/Carbon-12/SCFusion
  - Strom 13y ago
    SCFusion is nowhere near as good & maintained as WizardOfWin [1], which I've built. Although SCFusion is open-source, which may be a bonus point for some. [1] http://www.wizardofwin.com http://www.wizardofwin.com
    - maytsch 13y ago
      So how's your version better? Any new ideas to implement cross-over or make solutions more robust? Being open source is certainly an advance if you're mainly interested in the technical underpinnings...
- Strom 13y ago
  Having built a quite advanced GA based build order calculator myself, I can say that it involved a lot of analyzing the game, followed by recreating parts of the game engine that touch construction/advancement/worker movement.
kriro 13y ago
I enjoy genetic algorithms conceptually and they were one of my biggest "lightbulb moment" during university...a little silly thinking back but the order of classes was lined up in a way where I didn't really know much about algorithms and had just learned JAVA basics and naively assumed "computers are powerful...I can brute force everything" and then took a class called "soft computing" (iirc) and we had to solve some problem and implemented some naive brute force and let it run for a couple of days (lol!) until the next lecture where GA were introduced. I was totally floored that such a simple idea could speed up stuff so much. That being said there's usually better local/heuristic search methods (eventhough they are also often quite a bit harder to understand unless you just want to use them).
- jules 13y ago
  Hill climbing is far simpler and virtually always works better. In fact I've yet to see a practical case where GAs work better than simple randomized hill climbing.
  - Houshalter 13y ago
    Hill climbing by it's very nature is going to be faster (unless you can parallelize the GA) because you are only evaluating 1 solution at a time rather than a whole population. The problem is it's "greedy" and prone to getting stuck in local optima. GAs explore around a wide territory before converging and so generally get a better result (especially with crossover which the one from this post didn't use.)
    - jules 13y ago
      That's what people always say but it's false. You do hill climbing until you reach a local maximum, then you restart to a random state and repeat. The difference between hill climbing an GAs is that in GAs you do crossover. So in order to argue that GAs do better you have to show that crossover is beneficial. In all the cases that I have tested, GAs actually do worse because unlike with randomized hill climbing, GAs waste a lot of resources because the population usually isn't 100% diverse. There is also a paper by the co authored by the inventor of genetic algorithms, where they try to come up with a toy problem where GAs beat hill climbing. They start off with a toy problem that is designed to be an example where GAs shine, but they show that hill climbing actually works (far) better. Then they modify the toy problem in several steps, yet they only succeed barely in coming up with a toy problem where GAs beat hill climbing. Keep in mind that this is an extremely contrived toy problem. Suffice it to say that if coming up with a toy problem is that hard, it's unlikely that you will see a real world problem where GAs do better. Every field has its dark areas, like chemistry has had alchemists and their quest to create gold. GAs are one of the dark areas of computer science, where a lot of papers have been published but it ultimately turned out to be all bullshit.

208 points by AndyBaker 13y ago

wingi 13y ago

This "news" is from 2010.

daken 13y ago
And no longer applies with all the refactoring done in 4 years...
- andrewchoi 13y ago
  Perhaps a more appropriate word is "rebalancing"; I'm sure that the code has been refactored to some extent, but the balance issues are what are salient to this article.

remon 13y ago

I'm not sure if you hav enough fingers on two hands to count the number of SC2 balance patches since November 2010. This news is a tad dated no?

SixSigma 13y ago
2^10=1024
- thaumasiotes 13y ago
  This assumes e.g. that I can extend my ring finger without also extending the adjacent middle finger. ;)
  - pliny 13y ago
    2^8 = 256
  - traviscj 13y ago
    It just takes practice! https://vimeo.com/89914687 https://vimeo.com/89914687
  - kibwen 13y ago
    Rather than extending extending and retracting fingers, you can achieve this by placing your hands on a table and lifting a finger off the table in order to indicate a 1 on that digit. http://en.wikipedia.org/wiki/Finger_binary http://en.wikipedia.org/wiki/Finger_binary
- remon 13y ago
  Haha, touche..

thomasahle 13y ago

I remember reading this and thinking "That would be so much simpler to do with a breadth first search". Sure 'genetic' sounds cool, but when the search space is as limited as it is in a build order optimization like this, you should use the right tools for the task.

ryanator 13y ago
I don't think breadth first search would have been the right approach. The search space is actually quite huge for this. Also, the algorithm wasn't built to create a build that wins the fitness was simply how fast they could produce the army the user inputs. What stands out is if you had asked anyone even a professional player to build this exact army composition (7 roaches) they would almost certainly not have pulled it off as fast as the method this algorithm discovered. The algorithm was able to do it by doing a few tricks that normally aren't intuitive but, work out so your resources match up perfectly to make the build happen. Also, I can confirm as a mediocre Starcraft player the build was quite powerful.
- vladimirralev 13y ago
  The search space is not that big. It depends on the granularity of the decisions, but in SC2 most algorithms will work on the supply scale (with resources as constraint). Meaning you only have 3-5 decisions to make at any supply count. In this case considering the extractor cancel is a nice touch and I assume it was a special case because it's a known trick which makes no sense to consider for any other buildings.
  - veemjeem 13y ago
    Maybe the search space is limited in the first few minutes of the game when your opponent has also has a limited set of moves, but as the game goes on, the complexity increases exponentially. The 7 roach rush could be calculated here because the algorithm essentially completes when it reaches 7 roaches, but longer more complicated builds would be significantly harder -- like a 2-base blink all-in.
13y ago

pyduan 13y ago

It's unfortunate that the only other comments so far are about the fact this article is a few years old. Clearly what's interesting here is the method itself, not its immediate impact on the StarCraft II metagame. Real-time strategy games have recently stimulated a lot of great research [1] because they exhibit several interesting subproblems such as resource allocation optimization, strategy selection, or plan optimization (like here). It also has the nice side effect that it makes it easy to evaluate the quality of the resulting plan in a real-world setting and see how it fares when certain assumptions are relaxed (non-static opponents, effect of imperfect strategy execution, etc.). In this case what they did is solve a multi-objective optimization problem [2] using a genetic algorithm (a popular way to do so). The goal is to optimize some metric (e.g. time) with respect to some objective (e.g. "build 8 units of this type") and some constraints (resource requirements, unit trees). Of course you could perform some form of search in the solution space, but this space can become pretty big pretty fast and for complex games it's fairly easy to be stuck in a local optimum because the net effect of some choices can be hard to assess (some can be bad in the short term but be a nice set-up in the medium term, and two bad tactics can interact to be a good strategy). In contrast, a genetic algorithm can help find the global optimum. While it's not as big as the article makes it sound (it's not a "winning build" per se -- more like a method to find the fastest way to achieve a known opening), if you combined plan selection methods (e.g. [3]) with plan-optimization techniques like this one, you could come up with an IA that is able to come-up with both near-optimal tactics (how to achieve an objective) and strategies (which objectives to pursue). Pretty interesting stuff overall, and applicable to more than just real-time strategy games. [1] http://scholar.google.com/scholar?q=%22real-time+strategy+game%22%2Balgorithm http://scholar.google.com/scholar?q=%22real-time+strategy+ga... [2] http://en.wikipedia.org/wiki/Multi-objective_optimization http://en.wikipedia.org/wiki/Multi-objective_optimization [3] http://link.springer.com/chapter/10.1007/11536406_4 http://link.springer.com/chapter/10.1007/11536406_4

TrainedMonkey 13y ago
Great tutorial on genetic algorithms here: http://www.ai-junkie.com/ http://www.ai-junkie.com/
- 13y ago

malanj 13y ago

I used that strategy a few times when it came out. I found it interesting to see how fast humans could responded and nullify the advantage. I think after 3-4 wins with the strategy I started getting countered effectively. So it took a few days and all the players at my level knew about it and could handle it easily. It's hard to beat a general purpose strong AI in the long run!

gamegoblin 13y ago
I used this as my main build for quite a while, and got pretty good at transitioning out of it. Kept me in platinum league pretty solidly. Not sure if you were diamond or masters, though.
- rfrank 13y ago
  7rr specifically was pretty easy to counter, just get cannons out when you scout the early roach warren. The program from that article was pretty fun though, used it to make some absolutely ridiculous blink builds that didn't really work but were fun to try.
  - malanj 13y ago
    Yeah - I found that you had to be pretty good at moving off that build asap if you were scouted and the other player realised what you were up to.

lbrandy 13y ago

Ha. I wrote the blog post mentioned in this article that started this. As pointed out, this is an old repost(1), but perhaps interestingly (at least at a meta level) is that this is all actually HN's fault. When I first saw this thread on teamliquid, I thought "Oh man, proggit and HN will love this" so I wrote it up. And sure enough, it was near the top of both, for a day. Next came the random news articles (like this one). And here several years later is an HN repost of a blog article that only exists because HN and proggit upvoted the original blog post. You guys created the article that's being reposted :) [1] https://news.ycombinator.com/item?id=1856390 https://news.ycombinator.com/item?id=1856390 From the last time around, the most common criticisms were: 1. Without any form of crossover, it's just hill-climbing/gradient-descent, it's not really a "genetic algorithm". 2. BFS would work better (maybe. IIRC people tried BFS and there's a bunch of subtle things that make the BFS search space huge (e.g. putting workers on and off gas at certain times). Of course since we have a goal state, something like A* might win the day).

thinkbohemian 13y ago

I'm not a java programmer and currently eclipse is telling me that it's going to take 60 minutes to download. How does the program itself work? Is there some SC2 API they are using for this or did they just write down all the values and are "simulating" a SC2 build.

maytsch 13y ago
It's a simulation - if you ignore your opponent and assume perfect execution, the result of build orders is deterministic within pretty close bounds. There are a number of tools around to do this, here is an online version showing the build order mentioned in the article: http://www.sc2planner.com/#Zaaaap8oDaCoDjp3oFaaaaaoDaahcjoHjflllllll http://www.sc2planner.com/#Zaaaap8oDaCoDjp3oFaaaaaoDaahcjoHj... And just for fun, a more optimized version using a 13 pool in place of the 11 overpool to get the seventh roach 4 seconds earlier: http://www.sc2planner.com/#ZaaajaaaaoFaaaoDaacjhoHjflllllll http://www.sc2planner.com/#ZaaajaaaaoFaaaoDaacjhoHjflllllll If you're looking for a current GA build order optimizer, SCFusion is probably the best one: https://github.com/Carbon-12/SCFusion https://github.com/Carbon-12/SCFusion
- Strom 13y ago
  SCFusion is nowhere near as good & maintained as WizardOfWin [1], which I've built. Although SCFusion is open-source, which may be a bonus point for some. [1] http://www.wizardofwin.com http://www.wizardofwin.com
  - maytsch 13y ago
    So how's your version better? Any new ideas to implement cross-over or make solutions more robust? Being open source is certainly an advance if you're mainly interested in the technical underpinnings...
Strom 13y ago
Having built a quite advanced GA based build order calculator myself, I can say that it involved a lot of analyzing the game, followed by recreating parts of the game engine that touch construction/advancement/worker movement.

kriro 13y ago

I enjoy genetic algorithms conceptually and they were one of my biggest "lightbulb moment" during university...a little silly thinking back but the order of classes was lined up in a way where I didn't really know much about algorithms and had just learned JAVA basics and naively assumed "computers are powerful...I can brute force everything" and then took a class called "soft computing" (iirc) and we had to solve some problem and implemented some naive brute force and let it run for a couple of days (lol!) until the next lecture where GA were introduced. I was totally floored that such a simple idea could speed up stuff so much. That being said there's usually better local/heuristic search methods (eventhough they are also often quite a bit harder to understand unless you just want to use them).

jules 13y ago
Hill climbing is far simpler and virtually always works better. In fact I've yet to see a practical case where GAs work better than simple randomized hill climbing.
- Houshalter 13y ago
  Hill climbing by it's very nature is going to be faster (unless you can parallelize the GA) because you are only evaluating 1 solution at a time rather than a whole population. The problem is it's "greedy" and prone to getting stuck in local optima. GAs explore around a wide territory before converging and so generally get a better result (especially with crossover which the one from this post didn't use.)
  - jules 13y ago
    That's what people always say but it's false. You do hill climbing until you reach a local maximum, then you restart to a random state and repeat. The difference between hill climbing an GAs is that in GAs you do crossover. So in order to argue that GAs do better you have to show that crossover is beneficial. In all the cases that I have tested, GAs actually do worse because unlike with randomized hill climbing, GAs waste a lot of resources because the population usually isn't 100% diverse. There is also a paper by the co authored by the inventor of genetic algorithms, where they try to come up with a toy problem where GAs beat hill climbing. They start off with a toy problem that is designed to be an example where GAs shine, but they show that hill climbing actually works (far) better. Then they modify the toy problem in several steps, yet they only succeed barely in coming up with a toy problem where GAs beat hill climbing. Keep in mind that this is an extremely contrived toy problem. Suffice it to say that if coming up with a toy problem is that hard, it's unlikely that you will see a real world problem where GAs do better. Every field has its dark areas, like chemistry has had alchemists and their quest to create gold. GAs are one of the dark areas of computer science, where a lot of papers have been published but it ultimately turned out to be all bullshit.