31–40 of 51 posts
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.
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.
Earlier quoted context omitted.
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…
[1] http://wiki.teamliquid.net/starcraft2/Mining_Minerals
[2] http://www.teamliquid.net/forum/sc2-strategy/140055-scientif...
Earlier quoted context omitted.
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…
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...
Earlier quoted context omitted.
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.
Earlier quoted context omitted.
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.)
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.
Earlier quoted context omitted.
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.
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…
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.
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…
Earlier quoted context omitted.
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.)
Earlier quoted context omitted.
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 pulle…
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.