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.
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.
I've been looking for material about Eurisko. Other than this championship, there appears to be no credible documentation of any of Eurisko's reported achievements.
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.
Adding to the mystery, I read the newyorker article (2009) linked from wikipedia on Eurisko, and it seems Lenat forgot the winning strategy Eurisko developed, or the first article is wrong.
"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
IIRC they didn't ban him - rather, they told him that if he kept competing they'd just cancel the competition. This was not out of spite, but because he was so dominant that it was discouraging the other players from even trying.
Probably, yes. Somewhat closed gaming groups can have fun with an imperfect game if everyone agrees not to abuse the holes in the rules. (After all, rules abuse does not necessarily lead to a more fun game.)
I am a diamond level terran on ladder and have faced this rush build order before. To be honest it is a very strong build but most players will scout this very early.
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).
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 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 :)
Usually when the first three arrive, they don't have a sentry yet (The first three are about 15 to 20 seconds ahead of the next 4). If they do have a sentry, and they block, then you fall back and then attack with all 7. If they don't use it, you can usually use those three to start killing their units, and the next 4 come in and finish the job. If they are rushing an immortal (high level players often do this vs Zerg) then you can usually snipe the pylon. If there is more than one pylon powering the building, then it's tougher.
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.
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.
Well, I'm 2v2 Bronze in a specific team with a friend (we ranked a few months back and haven't played much together.) On 2v2 Random, I'm also Gold.
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.
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.
I reasonable protoss player will scout. This build cuts out a lot of zerglings and unless you can deny a probe scout it will be very transparent that you're going for a 7RR. A zerg who does not take an expansion quickly or lets at least a few lings to scout / deny scouting is very suspicious. Additionally protoss have access to the sentry and zealots will kill a roach in a 1v1 battle. They key is to force the roaches halfway up your ramp then cutting them off in half. Ideally 3 on top of your ramp and 4 below. A few stalkers should be able to hold them off.
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.
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.
That is the origin of the word, but I don't see why there is anything wrong with using it as the original poster did: "to cause great destruction or harm to" is a perfectly valid meaning of the word.
This is pretty cool to see programs "solving" video games. Although, for the most part I don't think this will affect play much. All-in strategies like this tend to only work if the other player is unprepared. Granted, this is a very fast rush and perhaps still very difficult to scout and notice early enough to counter, but the Starcraft community does tend to go back and forth finding and countering new builds (Perhaps the next step is to use a program to find a counter to this).
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 haven't looked into SC2 as much, but in the BW version of the the extractor trick, the cost-benefit tips at some point within the timespan of 'rushes'. That is, it'll be wonderful for very very fast rushes, but more 'patient' rushes are harmed by it. And at least for BW rushes, the trend seemed to be in the last bit before SC2 came out to trend towards more patient rushes. People weren't even looking for the win off the rushes anymore, but rather some sort of fast econ harrass to early map control. That mind set, where fast extractor tricks were optimal probably carried over a bit into the SC2 build making process.
Yes, most high level play isn't really looking to do all-in rushes like this. The goal is more to "fast econ harrass to early map control" giving you an early advantage and allowing you to eventually win.
Well, that's true and not true. On the ladder, where every game is (sort of) a one-off, you want to have a solid game, and it doesn't matter so much if it's a predictable "standard" game as long as you play better than your opponent.
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.
I'd have to disagree regarding rushes in high level play. I most enjoy 4v4 random and a key move is decimating one opponent's economy to the point that they become a non-factor in the game. With this build order in a 4v4 one player can neutralize a Protoss or Zerg player and then pivot to mutas or continue with roach/hydra. Since your economy isn't in shambles like a traditional 6 pool zergling rush, even if you fail with the roaches you are still left in acceptable shape to assist your teammates.
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.
By 'High-level play' he is most likely referring to tournaments and the e-sports scene, which is almost entirely 1v1 and plays very differently from 4v4.
I see. In that case it applies even more. It might be considered a cheese rush but an all-in with your drones would be very hard to counter unless they were able to hold the choke. It would have a good chance of ending the game in under 8 minutes versus drawing it out another 5-7 minutes.
It seems like cheese has failed more often than not so far in the GSL. At best it's a 50-50 proposition.
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.
This is half true. Indeed, currently European/NA players play quite "standard" at tournaments, avoiding rushes and "all-in" strategies. The Koreans, however, at GSL have shown that they're neither afraid nor hesitant to do so.
In the GSL (the largest SC2 tournament) there have been quite a few all-in rushes. Usually one player doesn't like his chances on the map, race matchup, or he feels he is inferior to the other player so he all-ins in an attempt to pick up an unlikely victory.
Starcraft has always struck me as a game of compound interest, and the optimal early builds always seem to be just that: maximizing an instantaneous rate-of-production, which will correlate to maximizing your instantaneous rates-of-doing-damage
It's always seemed like more of an economic strategy game than an actual "fronts of battle" kind of strategy.
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.
StarCraft 2 has tastefully upgraded the UI so that you can do lots of things with less clicks than before in SC 1. (Of course, that means at the higher end, people will just do more now than they did. But it's quite a nice feeling on the beginner level, too. E.g. you can get a worker to work right after it's build. And there's also a button for finding idle workers.)
Honestly, the graphics may be better, there may be new units, and balance may have improved or whatever else, but the UI improvements are the thing I love the most.
Starcraft isn't about clicking fast, it's about doing a lot of things at the same time. As you think about the game better you'll do more things faster, not the other way around.
It certainly is a game of compound interest! On top of that the system has three features that interact to give it its depth:
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.
I've had that happen more times than I can count. It's hard, because all the terran has to do is hit stim on his MMM ball and A-move. As zerg you have to pull off some Robert E. Lee shit to have a chance.
My biggest problem is pushing into an army backed up by a planetary fortress. I think I need to wait for the Terran to push out more and then destroy his army in the field or drop into his main. Pushing the front of a Terran base is suicide.
if you see that go hard into broodlords. A PF in a home base is a giant waste of money if not used, especially considering the additional building armor upgrade and range upgrade he spent on it and the lost time-income of no mules. You will easily out macro him.
Normally it's at his natural, like the open forward expansion on Delta Quadrant. I lost a game just today where I had a huge macro advantage over the Terran because of that PF. I even had Broodlords but I wasn't good enough to micro them against the SCVs repairing the fortress. I ended up destroying it with banelings, but by that point it had eaten up many thousands of minerals worth of my army.
That's true, but if you're evenly matched with your opponent, your initial economic curves will be identical, and then strategy and tactics come into play. Obviously it can be more valuable to strike the opponent's miners and factories than to engage his main army -- but real war is no different.
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.
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-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 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 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.
Indeed. Though the crucial difference is, that chess is a game of complete information, while StarCraft hides your enemy. It's much harder to do tree search without complete information.
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 it's only harder when you want to optimise for the outcome (winning), since it's hard to know what your opponent will do if you can't see them. However, if you optimise for total offensive/defensive power, I think you can do quite well with trees!
> 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.
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.
Yes, but that's the fitness function you want to maximise (i.e. the end result you will get with each "individual"). I'm saying that you might want to use heuristics in maximising that, rather than a GA.
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.
"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.
That's what I was thinking too but my AI knowledge is a bit rusty.
A genetic algorithm serves as a search algorithm that is finding a solution among a set of candidates. For example finding an answer to a sudoku.
A GA can also be used to perform optimization. For example arranging the structure of a bridge to maximize the load it can support.
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.
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 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.
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.
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 it.
This is a tautology that states "the harder a problem it is, the harder it is."
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.
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.
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.
GAs are less likely than other learning techniques to get stuck at a local maxima because mutations and crossover can cause to them to search entirely new areas in the space (unlike ANNs for example).
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).
Yet nobody found it. The closest thing to a roach rush people found was the 5-roach build [1], which is slower and it suffers a lot economically if the rush fails.
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.
Only because they never looked for it. Did this program decide to look for it on its own (having some idea of strategy, that would be impressive)? Or did the creator tell it to find fastest 7 roach build?
I'd imagine you would assign each unit some kind of relative value to each other and then factor in a time weighing making earlier builds more desirable even if there unit score is lower.
Another unmentioned aspect of this is Blizzard's involvement.
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.
I'm sure Blizzard will Nerf this. Early reapers, well executed, had about a 70% success rate. This has a 80% success rate at least, and is much harder to counter.
This was a very interesting read in that it gives a solid example on how designing a system can be outperformed by a natural selection approach. Us humans are inclined to design things and it is very easy to dismiss a random trial and error approach to achieve best results.
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.