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

Using genetic algorithms to find Starcraft 2 build orders

lbrandy.com

Post reply on HN
Print view View original

51–60 of 79 posts

Re: Using genetic algorithms to find Starcraft 2 build orders

#51

Post by codexon »

henning wrote: post #50
codexon wrote: post #40

This is the type of non-obvious optimization that genetic algorithms excel at. This is not true. GA search is a hill climbing algorithm which is prone to finding local maxima. The less obvious a strategy is, the more likely it is that GA will miss it.

> GA search is a hill climbing algorithm which is prone to finding local maxima GAs are not pure hill climbers. Variation operators introduce new solutions into the population at random. As long as premature convergence is prevented, GAs will probably explore the search space well. There's always a tradeoff between exploration and exploitation. > The less obvious a strategy is, the more likely it is that GA will miss…

GAs are not pure hill climbers. Variation operators introduce new solutions into the population at random.

In searching for non-obvious solutions a GA is no better, probably even worse than an exhaustive search. You are essentially gambling to find the absolute maxima by increasing the mutation rate and population variance. GA is merely a heuristic to speed up searches by assuming the global solution is close to your randomly seeded population, something which is unlikely to be true in non-obvious solutions.

Let's say you increase the mutation rate to the point where you are guaranteed find the "non-obvious solution". Well then you've essentially just created an insanely inefficient exhaustive search.

This is a tautology that states "the harder a problem it is, the harder it is.

No. For example in an exhaustive search, the obviousness of a strategy has no bearing on whether or not it would more likely be found.

Re: Using genetic algorithms to find Starcraft 2 build orders

#52

Post by henning »

codexon wrote: post #51
henning wrote: post #50

Earlier quoted context omitted.

> GA search is a hill climbing algorithm which is prone to finding local maxima GAs are not pure hill climbers. Variation operators introduce new solutions into the population at random. As long as premature convergence is prevented, GAs will probably explore the search space well. There's always a tradeoff between exploration and exploitation. > The less obvious a strategy is, the more likely it is that GA will miss…

GAs are not pure hill climbers. Variation operators introduce new solutions into the population at random. In searching for non-obvious solutions a GA is no better, probably even worse than an exhaustive search. You are essentially gambling to find the absolute maxima by increasing the mutation rate and population variance. GA is merely a heuristic to speed up searches by assuming the global solution is close to your…

How convenient to ignore the fact that exhaustive search is completely computationally infeasible in most practical situations.

Genetic algorithms are heuristics, yes. There is no guarantee they will work. That doesn't mean they haven't been successfully applied in a very wide variety of domains. The facts of their successes clearly mean nothing to you, though. "Not guaranteed to work" is not the same as "not useful as evidenced by hundreds of papers describing real-world applications."

It takes a special kind of boorish ignorance to respond to a post where the guy comes up with a Starcraft 2 build that is "non-obvious" and pretty strong and whine about how a metaheuristic doesn't work/didn't work when you tried it.

Re: Using genetic algorithms to find Starcraft 2 build orders

#53

Post by jjwiseman »

bigmac wrote: post #18
StavrosK wrote: post #13

A GA sounds like exactly the wrong way to go about this. I think you could do much better with a heuristic algorithm than a GA in this case, and I think GAs (like neural networks) are very much overused just because they correlate well with natural processes. That said, I haven't played SC2, and I don't know what sort of complexity the building problem has.

I can't quite understand if you're saying GA's are neural networks, or just that both of them are overused. Either way, one of the big problems is that the heuristics for a heuristic algorithm must be designed by with human insights. In this case, and in many other cases where GA's have been applied successfully, a fundamental new insight is discovered by the algorithm. I do play some SC2. There are a bunch of built-…

"one of the big problems is that the heuristics for a heuristic algorithm must be designed by with human insights."

Note that this isn't really true--the point of Lenat's Eurisko system referenced upthread was to have it come up with new heuristics and measure how effective they were.

Re: Using genetic algorithms to find Starcraft 2 build orders

#54

Post by codexon »

henning wrote: post #52
codexon wrote: post #51

Earlier quoted context omitted.

GAs are not pure hill climbers. Variation operators introduce new solutions into the population at random. In searching for non-obvious solutions a GA is no better, probably even worse than an exhaustive search. You are essentially gambling to find the absolute maxima by increasing the mutation rate and population variance. GA is merely a heuristic to speed up searches by assuming the global solution is close to your…

How convenient to ignore the fact that exhaustive search is completely computationally infeasible in most practical situations. Genetic algorithms are heuristics, yes. There is no guarantee they will work. That doesn't mean they haven't been successfully applied in a very wide variety of domains. The facts of their successes clearly mean nothing to you, though. "Not guaranteed to work" is not the same as "not useful…

I find your tone very disturbing.

The point which keeps going over your head is that GA approaches a exhaustive search in which you randomly select cases to test until you've either tried them all (and wasted many cpu cycles along the way with repeated mutations) or luckily stumbled across the global maximum early (in which case you would never know if it was global).

The reason why people use it instead of exhaustive searches is because they don't care about a global maximum, or in this case "obviousness". But to say that non-obvious solutions are a strong suit of GA is wrong, and that is what I had an issue with. If you knew the solution was non-obvious, you'd have better luck randomly testing solutions without the overhead of cross-over and mutations.

I also doubt that an exhaustive search to find this 7 roach build is infeasible when today's chess engines are able to brute-force 10 steps in a matter of minutes on standard hardware. I also never "whine"d about how GA didn't work for me, so I don't know what to say about that except that it is now obvious you are trolling.

Re: Using genetic algorithms to find Starcraft 2 build orders

#55

Post by waterhouse »

NyxWulf wrote: post #45
3pt14159 wrote: post #39

Earlier quoted context omitted.

Are you sure you are timing it correctly, using it on the right map, and microing ok? It should decimate most Protoss players unless they scout, discover, forge up, delay possible cannons until last min, dual exp, and quick air or go all in sentries.

> It should decimate most Protoss players unless they scout.. It should (annhilate|destroy|overwhelm| ) most Protoss players unless they scout... FTFY That usage of decimate is as grating to me as it is common. :/ I don't blame you, I'm just shaking my fists at the heavens in impotent rage.

I sympathize and agree. For those who don't know, the word "decimate" comes from a practice of the Roman army in which they would kill one out of every ten soldiers as a punishment for mutiny.

http://en.wikipedia.org/wiki/Decimation_(Roman_army)

Re: Using genetic algorithms to find Starcraft 2 build orders

#56

Post by weavejester »

Artagra wrote: post #41
alnayyir wrote: post #37

Earlier quoted context omitted.

Yeah I was going to say, I'm a silver level and this strat does not work that well even in that tier.

I just played 17 games using this strat, in the Gold League 1v1 and Bronze league 2v2. And some of the 1v1's where against Diamond league players. 12 wins, 5 losses. Trust me, it works. 1. Against Toss it's almost always a win, especially if you go all in (attack using queen and half your drones). Unless he's got a closed wall with cannons, he can't stop you. In my experience, no-one does this in just about any leagu…

As an aside, I find it interesting that you're Gold 1v1 and Bronze 2v2. I'm Silver 1v1 and Gold 2v2. I'm not convinced the ranking system for 2v2 and above works very well.

Re: Using genetic algorithms to find Starcraft 2 build orders

#57

Post by StavrosK »

ewjordan wrote: post #38
StavrosK wrote: post #27

Earlier quoted context omitted.

I can't tell you if it's "right", as I haven't worked on this particular problem, and ML is hardly black-and-white. GAs might give good results, it's just that there is usually another algorithm that will give better results faster. Again, it might work very well, I just think that some sort of tree-based approach might be faster and more efficient.

Again, it might work very well, I just think that some sort of tree-based approach might be faster and more efficient. While this is true in general, sometimes the nice thing about genetic methods is that pretty much all you have to do is write the fitness function, cross your fingers that the problem is a good fit for the method and go do some real work on another computer for a while. Oftentimes other methods requi…

Yep, exactly right. I'm just going by the fact that they probably need to optimize for running time first of all, as this will need to run in real time (or so I assume). GAs would make this very hard, even if the results are good enough.

Re: Using genetic algorithms to find Starcraft 2 build orders

#58

Post by seles »

I'm not going to say that this program is useless, but the example shown (7 roach) would have been near trivial to find by a mere human. Tricks like premaking the overlord, using extractor trick, etc. Have been around for over 10 years since the early days of Starcraft 1. Any person could come up with this build, the question is where did the idea to rush for 7 roaches come from? It sounds like that was manually set as the target goal by the creator.

I have yet to see a programs which is better than human at finding optimal builds. But what programs do excel at is simulating a build so you can see how the timings work out, allowing you to find your own build by experimentation and tweaking. Sure a program can help automate some very minor fine tuning details (which would be easy to find but perhaps tedious).

Re: Using genetic algorithms to find Starcraft 2 build orders

#59

Post by andreyf »

CoryOndrejka wrote: post #2

This echoes the story of Eurisko, a genetic AI written by Stanford's Douglas Lenat to build Traveller "Trillion Credit Fleets." Eurisko destroyed the competition at the national championship 2 years in row. http://aliciapatterson.org/APF0704/Johnson/Johnson.html In both cases, using the GA allowed a player to more comprehensively search the opportunity space created by the game designers than the designers did during…

This has been happening over the centuries with games like chess: after enough people spent time on them, openings began to develop. Now we've got iPhone apps to teach use SC2 openings: http://itunes.apple.com/us/app/build-calculator-for-starcraf...

How long before there's an app to develop them in real-time, by optimizing for certain constraints?

Re: Using genetic algorithms to find Starcraft 2 build orders

#60

Post by colanderman »

StavrosK wrote: post #19
bigmac wrote: post #18

Earlier quoted context omitted.

I can't quite understand if you're saying GA's are neural networks, or just that both of them are overused. Either way, one of the big problems is that the heuristics for a heuristic algorithm must be designed by with human insights. In this case, and in many other cases where GA's have been applied successfully, a fundamental new insight is discovered by the algorithm. I do play some SC2. There are a bunch of built-…

> I can't quite understand if you're saying GA's are neural networks, or just that both of them are overused. I was saying that both are overused. > one of the big problems is that the heuristics for a heuristic algorithm must be designed by with human insights By "heuristics" I don't strictly mean "rule-based", but you can do a good job in reducing the search space by a large amount if you program in some common sen…

This AI isn't intended to play the game however; by analogy with chess, this is intended to determine the best opening to use, when you have no knowledge of your opponent's moves. Hence min-max trees make no sense (since there are no "turns"), and we can't use precalculated moves, since those are what we're trying to figure out.
Post reply on HN