Genetic Algorithms Produce Winning StarCraft II Build Order (2010)(rockpapershotgun.com)
rockpapershotgun.com
Genetic Algorithms Produce Winning StarCraft II Build Order (2010)
http://www.rockpapershotgun.com/2010/11/02/genetic-algorithms-find-build-order-from-hell/
8 comments
Great tutorial on genetic algorithms here: http://www.ai-junkie.com/
An all flash site.
Well, just to add, the algorithm used in the article was "evolution with assexual reproduction". Genetic algorithms rely on sexual reproduction, to the point that the assexual algorithm has a completely different name (and origin), it's called "simulated anealing".
Well, just to add, the algorithm used in the article was "evolution with assexual reproduction". Genetic algorithms rely on sexual reproduction, to the point that the assexual algorithm has a completely different name (and origin), it's called "simulated anealing".
I think you have a rather unfortunate misspelling in your post. It's "asexual" not "assexual".
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
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).
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
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).
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!
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!
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.
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.
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.
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.
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.
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.
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.
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.
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.
They also didn't use crossover which I thought was the main advantage of genetic algorithms.
How would a breadth first search work better? The search space is huge.
How would a breadth first search work better? The search space is huge.
Well, you only care about what actions to do and what order.
If your edges are 'building things' and your nodes are records of some type (current time, number of stuff, stuff currently building), then you can calculate when you will be able to build what next, and generate the descendent states.
Given we are interested in four types of buildings and three types of units, that's maximum 7 descendents per node. Getting to 7 roaches doesn't require more than 20-30 actions. That's 7^30 and too much, but a lot of states are easy to prune, e.g. don't build 2 zergling dens, and on top of that you can add some goal searching heuristics, like a*.
If your edges are 'building things' and your nodes are records of some type (current time, number of stuff, stuff currently building), then you can calculate when you will be able to build what next, and generate the descendent states.
Given we are interested in four types of buildings and three types of units, that's maximum 7 descendents per node. Getting to 7 roaches doesn't require more than 20-30 actions. That's 7^30 and too much, but a lot of states are easy to prune, e.g. don't build 2 zergling dens, and on top of that you can add some goal searching heuristics, like a*.
Maybe backtracking would be used to reduce the search space.
Go for it, tiger :)
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).
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).
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.
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.)
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.
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.
What if you GA the algorithm itself? Such that GA converges on hill climbing (or something better, if it exists) as the best technique to use.
That's been tried before. It's theoretically possible, but unless you have a ton of computing power and example problems to work on, it'd probably just overfit to the specific problems you train it on.
And as the other comment pointed out, genetic programming is far too weak to achieve anything this complex. You need to simplify the problem tremendously by hand and then have the computer optimize the last few bits. Though seeding existing metaheuristics to start with might work.
And as the other comment pointed out, genetic programming is far too weak to achieve anything this complex. You need to simplify the problem tremendously by hand and then have the computer optimize the last few bits. Though seeding existing metaheuristics to start with might work.
I suppose you're talking about genetic programming? That is wildly optimistic. Genetic programming can't find anything except the most trivial programs.
Well, crossover is extremely powerfull and makes genetic algorithms very genereic. You are right that it's probably overkill for most problems we solve with computers, but only because we solve very simple problems nowadays.
Anyway, my experience with automatic programming is completely oposite to yours, and in line with comicjk. I've always had better results with GA than with hill climbing* or simulated annealing. I have the same experience for resource scheduling. Of course, your experience will vary a lot depending on the data you want to fit/schedule.
Also, nothing is stopping you from including hill climbing as a kind of mutation...
* Last time I used it, I didn't even have a well behaved gradient to climb, it was zero at a huge number of places, and I knew it beforehand. Automatic programming applies to all kinds of crazy domains.
Anyway, my experience with automatic programming is completely oposite to yours, and in line with comicjk. I've always had better results with GA than with hill climbing* or simulated annealing. I have the same experience for resource scheduling. Of course, your experience will vary a lot depending on the data you want to fit/schedule.
Also, nothing is stopping you from including hill climbing as a kind of mutation...
* Last time I used it, I didn't even have a well behaved gradient to climb, it was zero at a huge number of places, and I knew it beforehand. Automatic programming applies to all kinds of crazy domains.
You should publish a paper on the problem you solved with GA. It will be a huge breakthrough, since so far here is only 1 problem known to work better with GAs than hill climbing, and it's a toy problem specifically crafted for this purpose.
I'm not very inclined to share it.
I was trying to fit a potential field, that I knew consisted of a map of 12 dimensions into 1. I could approximate it pointwise, but only with a very slow procedure, and needed both a faster one and a derivative.
I was trying to fit a potential field, that I knew consisted of a map of 12 dimensions into 1. I could approximate it pointwise, but only with a very slow procedure, and needed both a faster one and a derivative.
Many stochastic methods get around the local optima problem with various techniques. The simplest one is just to pick another random place to start climbing.
Have you tried automatic programming? For one heuristic optimization project, I automatically derived arithmetic expressions to match an unknown function, using a wide variety of methods including hill-climbing. Many methods started out more efficient than genetic algorithms - at one hundred thousand evaluations or so, simulated annealing was doing best. But by one million, all other contenders had levelled out, while the genetic algorithm was still doggedly finding better answers. The fact that it maintains a population and exchanges working code between its members turns out to be extremely effective for hard problems.
Yes, I have tried automatic programming in the past, but my results were the opposite. Hill climbing universally does better. Of course you need to be reasonable and restart the search once it gets stuck in a local maximum. If you don't do that then GAs obviously do better since they start off with a whole population rather than one candidate. So the reason GAs do better has nothing whatsoever to do with its essential difference to hill climbing (the crossover). In fact if you just take an ordinary GA and disable crossover, and you let each individual in the population have exactly 1 offspring, it will usually work better! This is because crossover & the breeding rules of GA tend to remove diversity in the population.
By the way, in my automatic programming programming experiments hill climbing hardly did better than just brute force search. It fails for all but the smallest examples. So that's another one of those things that doesn't really work in practice.
By the way, in my automatic programming programming experiments hill climbing hardly did better than just brute force search. It fails for all but the smallest examples. So that's another one of those things that doesn't really work in practice.
My reading of genetic programming disagrees with you. In fact many have found that mutation doesn't actually help. Pure crossover with a random population seemed to work just fine (for genetic programming.)
The biggest problem is that the search space isn't smooth and even crossover is very mutative on discrete, arbitrary graphs.
The biggest problem is that the search space isn't smooth and even crossover is very mutative on discrete, arbitrary graphs.
> 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.
Thank you for saying this.
Realizing this is sort of similar to the time when I first learned about how standard error-backprop neural networks really work, and I realized that they're "just" a stochastic optimization algo and not really actually "smart like a brain" that can learn everything (I was young :) ).
About, a "practical case" where GAs work better, I'm going to go with (generative/digital) art projects. The fact that a GA is sort of based on a simulation of a biological process lends extra flavour to an art piece that is somehow crafted using a GA, more so than if it had used hill-climbing or brute force. It'll help ask questions like "who is the artist here?" and "what is creativity" and "can a computer be alive?" etc etc.
Thank you for saying this.
Realizing this is sort of similar to the time when I first learned about how standard error-backprop neural networks really work, and I realized that they're "just" a stochastic optimization algo and not really actually "smart like a brain" that can learn everything (I was young :) ).
About, a "practical case" where GAs work better, I'm going to go with (generative/digital) art projects. The fact that a GA is sort of based on a simulation of a biological process lends extra flavour to an art piece that is somehow crafted using a GA, more so than if it had used hill-climbing or brute force. It'll help ask questions like "who is the artist here?" and "what is creativity" and "can a computer be alive?" etc etc.
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.
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/#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
If you're looking for a current GA build order optimizer, SCFusion is probably the best one: https://github.com/Carbon-12/SCFusion
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
If you're looking for a current GA build order optimizer, SCFusion is probably the best one: https://github.com/Carbon-12/SCFusion
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
[1] http://www.wizardofwin.com
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...
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.
I figured this was how it worked. What ways did you use to get an accurate model of the rules? Did you just use wikis and a stopwatch to figure out how long builds take, what can be built when, etc. or did you actually memory watch or decompile the game itself to figure out the algorithms and loops used?
I made a Tic-Tac-Toe GA in undergrad as my senior project. It was horribly stupid, but I didn't reduce the problem space down, and I could have easily implemented rotation and flip mapping to reduce the search space by a significant amount (just over 7% of the nieve search space), but the algorithm still worked pretty well and served as a great learning experience.
The genetic part is ridiculously simple, IMO. The hard part is figuring out how to define the rules of the game, break them out, and figure out what maps to the genome and how it maps. Evolution from that point is simply modifying the genome in different ways.
I made a Tic-Tac-Toe GA in undergrad as my senior project. It was horribly stupid, but I didn't reduce the problem space down, and I could have easily implemented rotation and flip mapping to reduce the search space by a significant amount (just over 7% of the nieve search space), but the algorithm still worked pretty well and served as a great learning experience.
The genetic part is ridiculously simple, IMO. The hard part is figuring out how to define the rules of the game, break them out, and figure out what maps to the genome and how it maps. Evolution from that point is simply modifying the genome in different ways.
No decompiling, just observing the game with a timer. I used a lot of community wiki/forum information as well. There has been some really amazing research done by the community [1][2], to figure out optimal resource harvesting strategies, and I used quite a bit of data from that.
[1] http://wiki.teamliquid.net/starcraft2/Mining_Minerals
[2] http://www.teamliquid.net/forum/sc2-strategy/140055-scientif...
[1] http://wiki.teamliquid.net/starcraft2/Mining_Minerals
[2] http://www.teamliquid.net/forum/sc2-strategy/140055-scientif...
Thanks for the info! It really helps knowing how others have solved problems like that. I am interested to know if there is an open source finite state machine for building in SC2.
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?
2^10=1024
This assumes e.g. that I can extend my ring finger without also extending the adjacent middle finger. ;)
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
It just takes practice! https://vimeo.com/89914687
2^8 = 256
Haha, touche..
This "news" is from 2010.
And no longer applies with all the refactoring done in 4 years...
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.
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+ga...
[2] http://en.wikipedia.org/wiki/Multi-objective_optimization
[3] http://link.springer.com/chapter/10.1007/11536406_4