4 ms·

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 i

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.
Houshalter 13y ago
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.
- OlivierLi 13y ago
  Maybe backtracking would be used to reduce the search space.
- thomasahle 13y ago
  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*.
otikik 13y ago
Go for it, tiger :)

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.

Houshalter 13y ago

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.

OlivierLi 13y ago
Maybe backtracking would be used to reduce the search space.
thomasahle 13y ago
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*.

otikik 13y ago

Go for it, tiger :)