Using genetic algorithms to find Starcraft 2 build orders
lbrandy.com
lbrandy.com
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 design and play testing.
Really awesome stuff, though it sets up an intriguing arm's race between the game designers who can patch and Nerf elements to eliminate unbalanced strategies and the players who then explore the new rule set.
How long before there's an app to develop them in real-time, by optimizing for certain constraints?
It might be super-duper, but the fact that he wouldn't let anyone else use it, and that those amazing feats have not been reproduced by others despite huge advances - might just mean that there's more myth to truth in the stories about Eurisko.
"Eurisko, however, had judged that defense was more important than offense, that many cheap, invulnerable ships would outlast fleets consisting of a few high-priced, sophisticated vessels. There were ninety-six ships in Eurisko’s fleet, most of which were slow and clumsy because of their heavy armor" - 1984 article
"astronomical number of small ships like P.T. boats, with powerful weapons but absolutely no defense and no mobility, Lenat said. They just sat there. Basically, if they were hit once they would sink." - 2009 article
I would be more interested in searching the space for hard counters to build orders with certain match ups. Certainly it gets way more complex (and starcraft is).
It should (annhilate|destroy|overwhelm|<etc>) 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.
Are you suggesting people should only and exclusively adhere to original meanings and "trve" origins of words?
Knowing where a word came from can certainly help us understand more but let's face it, languages are very alive and change a lot.
Forging up, and dual expoing (correct me if I misread you when you said dual exp) into "quick" air is not a viable strategy.
A reliable strategy would be to hold off the initial push and securing your natural. You should be in an economic lead since he sacrificed 7 larvae early on in the game for the attack. From there the game should transfer into a standard ZvP with the protoss being slightly ahead due to a higher probe count.
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 league.
2. Against Terran, it's very succesful, if not quite as succesful as against Protoss. If they put up a bunker with marauders, or they micro 2 or 3 marauders behind a wall, you need to fall back. But in general, it works amazingly.
3. Against Zerg it works very well, as long as they don't six pool - if they do six pool and you haven't scouted it then you are in trouble. But in general, it worked well.
Bottom line? Although it seems like it's similar to the traditional zerg rushes, it's actually a very impressive rush. I would say that well executed it's got a 90% success rate on maps with short to medium rush distances. So definitely give it a try :)
In 1v1, a variation on this strat is to go all-in - send your queen after you spawn larvae, and then when the second 4 come out send most of your drones. With 7 roaches + drones + queen, it doesn't matter if he gets out the Immortal, or infact what he goes for. Only thing I've seen is a hard cannon wall, which then commits him to a single base Void rush - which is easily countered.
So yes, this strategy is very unbalanced. Played 22 games tonight, 7 losses. 2 of those losses where on 2v2. Last 10 games I played? 9 wins, 1 loss.
I hope Blizzard fixes this soon :( it's going to make Terran and Toss very susceptable early game.
But I do agree that ranking for larger teams is poor - for example, I'm 3v3 Platinum, and I'm definitely out of my league - I think I ranked their as a result of being lucky in terms of getting good team mates.
The two points about the build that the article mentions as counter-intuitive don't seem that strange to me since it is a rush (all-in) build. The extractor trick is well known and I would believe that it sacrifices economy long term but it gives you an extra drone (= more money) early on which is good for a rush.
The double overlord is there to support the seven roaches that you build almost all at once. At the beginning of the game, you can only afford to build one unit at a time so you can also replenish supply one overlord at a time. As the game progresses and you start pumping out large number of units at a time, you have to also be producing multiple overlords simultaneously to keep up with supply. Although this is very early, the all-in rush to produce 7 roaches requires a fast increase in supply.
To give an idea of how fast this is, the build ends at around 31 supply, about half of which is the attacking roach units. Max supply is 200 and mid-game is probably somewhere around 50-70 supply.
I specify this being useful in 4v4 against Protoss/Zerg as Terran traditionally wall and the few seconds it takes to burst through the wall may give their teammates time to mobilize.
Note- I wrote this under the impression that your mentioning "all-in rushes" didn't include sending your drones in to act as meat shields. In a 4v4 that would be suicide and invalidate my point.
Tester deftly deflected cheese attempts from Hyperdub and NexFreeSaga before crushing the remains of their army in season 1. On the other hand, fan favorite TLO was eliminated by some proxy barracks from the cheese-loving Hyperdub and GSL season 1 winner aFruitDealer showed that he wasn't above a cheese game or two with a ballsy six-pool on a four spawn map against Inca.
Cheese fails every time if it's spotted against a high-level player, which is why it's cheese. These guys have definitely practiced against 6-pool, proxy gate, proxy rax, 7 roach rush a thousand times. There's no way they would take a cheesy loss with $80,000 on the line or give up the easy counter and auto-win.
edit: GSL, not ESL.
But if you're a known player playing against other known players, or if you're playing best-of-N matches, it's valuable to have demonstrated flexibility in your play and a willingness to perform individually suboptimal strategies like early all-ins. If your opponent believes that you're capable of many different things, they will feel compelled to scout earlier and more carefully, and their options will be restricted slightly until they feel they can pin down exactly what you're up to.
It's always seemed like more of an economic strategy game than an actual "fronts of battle" kind of strategy.
There are two ways to look at economic production in SC2. You can spend your time and money producing items that will do damage (e.g. units), or you can spend money on things that will increase your production rate (e.g. more barracks, hatcheries, etc).
Then there is a tech tree to factor in, how far up the tech tree should you go. It's all about understanding how far up the tech tree you need to go.
Say you are facing an opponent that is going to rush with level 1 units, if you know this, you can build defenses at choke points that will cost you much less than his units will cost to break through. At the same time you are rapidly climbing the tech tree to get more powerful units and spending less on the lower tier units.
On the other hand, if he has just enough units to bust through your defenses, it's game over.
That's how strategy comes into play in SC2. Often part of your early game strategy is figuring out how to disrupt the opponents supply chain (particularly along their critical path) while continuing to increase your own production capacity.
Long post - but in general your economic curves are not necessarily the same. Early expand, versus more units and pushing, etc.
And more specifically, it's not about maximizing your rate of production, its about maximizing the difference between youres and your opponents (this is both RTS and real life war).
That's the basis of rush tactics. You actually stunt your own rate of growth in the hopes of stunting your opponents even more.
As for the tactics or "logistics" -- if that means clicking 500 times/minute, then i really don't see the appeal :)
1) There are several opportunities in each game to sacrifice your rate of growth to obtain a temporary advantage in present value (ie. cutting workers to rush).
2) Because present value is multidimensional (you can't measure the value of a Zergling directly against that a Mutalisk), you can sacrifice your rate of growth or your present value in order to obtain a temporary advantage in what kind of value you have (ie. cutting units or workers to tech).
3) Information asymmetry. While trying to gain these mathematical advantages, one has to act on information that is increasingly out of date. One can not usually predict the opponent's exact present value and rate of change, but can only estimate ever-widening bounds on their values.
That said, I haven't played SC2, and I don't know what sort of complexity the building problem has.
I do play some SC2. There are a bunch of built-in AIs that use heuristic algorithms, yet they are all easily defeated. The GA in this case is really about searching through an immense space to find good candidates.
To give you a feel for the complexity of the building problem, consider this. There are custom maps where are all you do is practice your initial build order, with absolutely no opponent. It is pretty well accepted within the SC2 community that you should use these practice maps in order to get better. Another way to think about it is that this build order will probably cause Blizzard to tweak the game due to how fast the roaches come out. This game has been in development for 10 years, yet there are interactions of the building process that are not understood by the developers themselves.
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 sense that will discard obviously bad moves.
It would be surprising if the devs did understand all the interactions, as it would mean that the search space is trivial. SC2 is not that much different from chess, and, to my knowledge, the best chess-playing AIs don't use genetics. They get much further with trees and precalculated start- and endgame moves.
As a comparison, look at the recent progress made in computer Go that employs Monte Carlo simulations. (And Genetic Algorithms are closer to Monte Carlo than to tree searches.)
I believe that the fitness function used for evaluating build orders does this. It is very difficult to accurately evaluate how good a specific strategy is at a specific point in time, especially when you have imperfect information about your enemy. The code used to decide which build orders survive almost certainly used heuristics.
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.
The Starcraft build order as defined here is a planning problem, that is a problem whose goal is to find a sequence of action to get to a desired state. There are algorithms more suited than GA because they take advantage of the logical structure of the problem.
Do I get that right?
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 require more in the way of setup or planning, not the least of which is actually picking an appropriate method and mapping its implementation onto the problem space.
Some of the nastiest problems I've ever worked on have gotten that way because I went with a domain specific approach that was "optimized for the problem"; while the end results are usually very good (and, to be fair, run on the computer from zero-to-solved in no time flat), in a couple cases I've gone back and tried the "brute force" genetic programming approach, and though it took quite a bit more computer time, the programming effort was substantially smaller to end up with similarly good results.
The real problem, though, is that many of the problems people apply GA/GP to aren't well suited to the genetic approach, usually because the problem itself doesn't lend itself to incrementally improving solutions (problems like function regression can be tricky, because getting close to the correct functional form symbolically usually leaves you very far away from the correct form numerically, and sometimes the correct result is actually surrounded by a "wall" of completely and utterly unfit solutions that's very hard to break through). Genetic methods work well when the fitness landscape has lots of solutions that work fairly well, and quite a few that work great, not when there's literally one needle in some super-multi-dimensional haystack.
To be fair, the Starcraft optimization problem is probably somewhere in the middle, there are probably many good solutions to the problem, and many of these will be minor variations on other good solutions, so it's pretty likely that a GA will get to some good ones. But the search space is small enough that you're probably right, a heuristic-guided direct search would be more likely to pick out the best solutions faster.
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.
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 it.
This is a tautology that states "the harder a problem it is, the harder it is."
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.
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.
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.
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).
For the record, though, I've played against the 7-roach build a couple of weeks ago, and iirc that was a few days before EvolutionChamber was announced. So some people knew about it, maybe they found out about it from the creator, or played against him, who knows.
[1] http://wiki.teamliquid.net/starcraft2/5_Roach_Rush_%28vs._Te...
If this build is truly unstoppable in most cases, then Blizzard's balance team will simply nerf some aspect of Zerg to make it harder to abuse. For example, when the balance team determined that Reapers were too strong in early game, they made the tech required for them take longer to get.