Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

rockpapershotgun.com

Post reply on HN
Print view View original

41–50 of 51 posts

Re: Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

#41

Post by jules »

Xcelerate wrote: post #38
jules wrote: post #36

Earlier quoted context omitted.

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…

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.

I suppose you're talking about genetic programming? That is wildly optimistic. Genetic programming can't find anything except the most trivial programs.

Re: Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

#42

Post by marcosdumay »

TrainedMonkey wrote: post #21
pyduan wrote: post #6

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 optim…

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

Re: Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

#43

Post by marcosdumay »

jules wrote: post #36
Houshalter wrote: post #25

Earlier quoted context omitted.

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…

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.

Re: Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

#44

Post by jules »

marcosdumay wrote: post #43
jules wrote: post #36

Earlier quoted context omitted.

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…

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

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.

Re: Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

#45

Post by maytsch »

Strom wrote: post #27
maytsch wrote: post #26

Earlier quoted context omitted.

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 overp…

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

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

Re: Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

#46

Post by lomnakkus »

marcosdumay wrote: post #42
TrainedMonkey wrote: post #21

Earlier quoted context omitted.

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

I think you have a rather unfortunate misspelling in your post. It's "asexual" not "assexual".

Re: Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

#47

Post by Houshalter »

Xcelerate wrote: post #38
jules wrote: post #36

Earlier quoted context omitted.

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…

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.

Re: Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

#48

Post by Houshalter »

jules wrote: post #37
comicjk wrote: post #32

Earlier quoted context omitted.

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, whil…

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 essentia…

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.

Re: Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

#49

Post by tripzilch »

jules wrote: post #23
kriro wrote: post #22

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 so…

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

Re: Genetic Algorithms Produce Winning StarCraft II Build Order (2010)

#50

Post by marcosdumay »

jules wrote: post #44
marcosdumay wrote: post #43

Earlier quoted context omitted.

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

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.

Post reply on HN