Day 1: BOO with Genetic Algorithms

On October 13 2010 20:43 searcher wrote:
I hope you will have fun but I want to point out a rather annoying trend amongst computer scientists.

Instead actually trying to solve problems, too many computer scientists just shove their problems into some generic search algorithm, whether it is genetic algorithms or neural networks or whatnot. As a thinker trying to solve a problem you learn a lot less with this method, and furthermore in most cases there is no reason your solution should be easily found with your method. Many computer scientists like it simply because it always give an answer (and in the case of genetic algorithms, usually the local maxima).

For example in your case, why on earth would build orders "mate" well? There is very little reason why combining the better elements of different build orders will make a build order that is better. I think a naive search might actually yield better results. Finally, the process of optimizing build orders is very simple relative to things like even very simple game strategies. You could quite easily just run a search with some natural heuristics and solve the problem much easier and better.

On October 13 2010 21:26 Revilo wrote:


I agree wholy with your argument about the application of generic tools to problems in Computer Science. However, in this case "mating" actually makes a bit of sense since I will most likely be defining my buildorders as linear chromosomes. That means i can read off the build order by looking at the string of genes on my chromosomes. In this case, when we perform crossover, it is essentially giving the early game of one build order to another build order. In cases where suboptimal build orders are failing because of a few bad early decisions this may well allow a faster approach to some optima. I agree that this application would most likely only be very applicable to short term goals (for instance reaching 2 spine crawlers as soon as possible); but i hope to extend it so you can give a string of build order requirements. For example, if i want to first get 2 spine crawlers then get 10 zerglings, i would let the algorithm compute the (near to) optimal path to the 2 spine crawlers, then use that output as input for getting 10 zerglings as optimally as possible. In essence one would find that the overall buildorder for both may be suboptimal by far but it might be a constraint the user would like to implement because of some counter he needs to have at time X.

With respect to just performing a search, you will find that the search space explodes after about depth 3 or 4 for all the races. Once you get to the point where you want to make 10 marines as soon as possible, there are upwards of trillions of combinations reaching that target. Even using some kind of BFS takes some time. Of course I am not certain about this because I have not tested it, but I may implement that direct brute force approach in the future to compare.

For now this is going to simply educate me in the process of programming a genetic algorithm as well as hopefully give some interesting results about Build Orders. I really want to compare the algorithm against the so called "standard build orders" to see how well it fairs and whether there could be better ones!

Thanks for your input though, I value constructive criticism highly

On October 13 2010 22:30 NevilleS wrote:
It's admirable that you want to try this out, and I highly recommend learning coding languages and concepts by building something you are interested in, but... I think the problem with all these build order programs people keep talking about is that while, yes, the tech tree decisions are strictly defined and easily programmable, the income model is always going to be very coarse. To discretize a build into a genetic sequence that accounts for mining and producing workers, it seems to me that you would need to pick some reasonably small timescale (i.e. 100ms?) and then model resource income as some non-linear gain wrt worker count. Every possible action then needs to have a fairly complex dependency resolution function (enough money, requisite tech, requisite building, idle production queue).

IMO a genetic algorithm will spend most of the time rejecting invalid mutations that don't satisfy the dependencies. If you loosen the dependencies, you will get invalid builds. If your dependency model isn't accurate enough, you will also get bogus results. Therefore, the hard work is developing an accurate dependency model that can evaluate whether a particular "action" is valid given all previous actions through time...

On October 13 2010 22:52 Sleight wrote:


So while this is true, the nice thing about programming is that you aren't obligated to deal with all possible cases... just the relevant ones. Sure, in an ideal world, you could code a solution to any and every case, but we don't have to deal with that, we can rule out an absolute ton of those searches.
'
As a Terran, I can say you can only really save up to expand when producing off of 3 structures, 4 if you are super marine heavy, while you can go up to 4 if you aren't expanding. So we can code to eliminate possibilities that might conflict. We know that you can only really support 5 or 6 (if you are marine heavy) off of 2 bases. We can cut out conflicting ones of those. In fact, by looking at the practical constraints of a game, you truly can weed out the proverbial 'trees' to a handful of relevant decisions given the current game state, matchup, and map. Now, wiggle room has to be allowed for making current decisions with significant later ramifications, but I personally think that the correct approach is by doing what chess computers do and using GMs for their opening tables and relying on itself later on when it can just brute force a much more limited set of possibilities. The appropriate parallel is that we use practical human input for the reasonable decisions and only allow searches in situations humans might be forced to make a decision based on incomplete or imperfect information.

I foresee the program having a routine of preset initial openings with it allowed to improvise upon an established set of possible continuations that best orient towards a goal. The idea that any type of processing can optimize SC2 is silly... There are intangibles, *even in BOs*, that require human input to solve. It can create the most perfect 1 Tank push, but if 1 tank pushes aren't any good... I fail to see its significance.

On October 13 2010 21:26 Revilo wrote:


I agree wholy with your argument about the application of generic tools to problems in Computer Science. However, in this case "mating" actually makes a bit of sense since I will most likely be defining my buildorders as linear chromosomes. That means i can read off the build order by looking at the string of genes on my chromosomes. In this case, when we perform crossover, it is essentially giving the early game of one build order to another build order. In cases where suboptimal build orders are failing because of a few bad early decisions this may well allow a faster approach to some optima. I agree that this application would most likely only be very applicable to short term goals (for instance reaching 2 spine crawlers as soon as possible); but i hope to extend it so you can give a string of build order requirements. For example, if i want to first get 2 spine crawlers then get 10 zerglings, i would let the algorithm compute the (near to) optimal path to the 2 spine crawlers, then use that output as input for getting 10 zerglings as optimally as possible. In essence one would find that the overall buildorder for both may be suboptimal by far but it might be a constraint the user would like to implement because of some counter he needs to have at time X.

With respect to just performing a search, you will find that the search space explodes after about depth 3 or 4 for all the races. Once you get to the point where you want to make 10 marines as soon as possible, there are upwards of trillions of combinations reaching that target. Even using some kind of BFS takes some time. Of course I am not certain about this because I have not tested it, but I may implement that direct brute force approach in the future to compare.

For now this is going to simply educate me in the process of programming a genetic algorithm as well as hopefully give some interesting results about Build Orders. I really want to compare the algorithm against the so called "standard build orders" to see how well it fairs and whether there could be better ones!

Thanks for your input though, I value constructive criticism highly