Algorithms Discover Build Order From Hell

By Quintin Smith on November 2nd, 2010 at 1:04 pm.

Humans: Still a pathetic creatures of meat and bone.

This is mad. Over on StarCraft 2 forum Teamliquid, a poster who goes by Lomilar has been talking about a program he’s coded called EvolutionChamber. It uses genetic algorithms to find powerful build orders, meaning his program takes a population of build orders, kills off the useless ones, and has the most successful ones reproduce asexually to create a new population, which tests itself again, and so on. I’m taking all this from this blog post by programmer Louis Brandy, wherein he breaks down what Lomilar’s done so that lay folk can understand it.

EvolutionChamber’s already come up with one ludicrous build order, which I’ve posted beneath the jump.

10 extractor-trick to 11
11 overlord
11 spawning pool
15 extractor
16 queen (stop drones here)
18 overlord
18 roach warren
17 overlord (yes, two)
spawn-larva on queen when she pops
roach x7

Which will get you a 7 roach rush in less time than anybody thought possible. “Extractor-trick” refers to telling a drone to build an extractor, building a drone, then cancelling the extractor’s construction to get the drone back, making your population of drones 11 out of a maximum of 10.

To summarise Louis’ blog post, this is interesting because:

(1) This is such a devastating build order that for a while the discussion on Battle.net centred around whether Protoss could survive it even if they knew it was coming. Turns out they can, but only with very specific counter-strategies or if the person they’re playing fails to fulfil the potential of the build order.

(2) Despite its effectiveness, this build order wasn’t known to the SC2 community. It’s quickly become labelled as a “cheese build,” though, meaning… well, it works.

(3) The extractor trick used by the program has been tested by real players, and was thought to be “economically inferior” compared to just buying an overlord and increasing your population cap. However, using this trick the program created a build order that made 7 roaches in less time than the standard roach rush strategy produces 5.

(4) …and yet while the strategy neglects to buy an overlord to begin with, it later produces two at once, far overshooting the population cap the strategy requires but allowing it to squeeze those 2 extra roaches into the rush. It’s all counter-intuitive, but the result is inarguable. Louis says that “This is the type of non-obvious optimization that genetic algorithms excel at.”

Truly, we are living in the future. Here’s a tutorial on how to do the 7 roach rush.

__________________

« | »

, .

251 Comments »

  1. Mman says:

    “In an RTS, I like basic infantry, and I like tanks. Any winning strategy that doesn’t utilize hordes of infantry and tanks is not going to be fun for me, and being forced to either use said strategy or fail is not a rewarding experience for me.”

    Marines+Marauders (and medivacs along with whatever backup you want) is one of the most powerful basic unit compositions in the game, so you can do just that.

  2. GHudston says:

    Opinions on Starcraft 2 aside (I rather enjoyed it, but I’ve sort of moved on from it now.) I LOVE stuff like this.

    Genetic algorithms (and genetics/evolution in general) are utterly fascinating to me. To see it applied to something like a Starcraft 2 build order is just brilliant and I can’t believe it’s taken this long for someone to come up with it.

    Very interesting!

  3. pipman3000 says:

    wow who knew aspergers could be so fun!

  4. Koldunas says:

    stop comparing chess to starcraft! please! I know how you love the idea that your favourite RTS could be like one of the oldest games of all time (please don’t nitpick), which is still has mesmerizing depth, BUT it’s not. Chess is perfect information and pure strategy, starcraft is imperfect information and a lot of frantic mouse clicking keyboard mashing (a.k.a. skill). Please remember I’m not having a go at Starcraft, it’s a really good RTS (even though it may not be everyone’s cup of tea), but it’s just not chess. Stop the bollocks.

    • mrmud says:

      Your right
      Starcraft has a vastly greater number of combinatorial outcomes than chess does.

    • Koldunas says:

      I feel you were trying to be cocky and completely missed my point, but yes. In a way, you are right. SC II (just like any rts game) has an insane number of combinatorial outcomes (even though, as I stressed in my post, they are executed in real-time).This is one of their strengths, but it also takes away (as I have said before) from perfect information/pure strategy. So, again, it is not ‘like chess’.

    • GHudston says:

      I don’t think anyone is saying that Starcraft is “like chess” in the way that you think they are. But you are blind if you cannot see that build orders are akin to the opening moves seen in chess. The games themselves play out much, much differently of course (real time vs turn based, as just one example.); but the similarity is very much there.

  5. pimorte says:

    One of the biggest problems in this discussion is that people still try and call Starcraft and its sequel strategy games.
    They’re not. They’re games of memorisation and reflexes. A game of Starcraft has much more in common with a game of Diablo than a game of chess. I would call it a top-down multi-character action game.

    This problem also leads to another problem – people come into Starcraft with the expectation that they will have an large space of strategies to play with. They don’t. This is what leads to many people’s disappointment. The selection of possible build orders and reactions to opponents moves is minute in comparison to the possible selection of build orders and reactions.

    This is not to say Starcraft cannot be a fun game – plenty of people do enjoy the challenge of subsecond-level timing and reactions going to a set script. Someone up above compared it piano, and another “Guitar Hero for obsessive-compulsive psychopaths”. Sure! There’s a lot of people who like playing music for recitals, even though it’s just playing the same thing over and over and over again, trying to get the sub-second timings down.

    • pkt-zer0 says:

      This is the kind of post that prompts the “you just don’t know what the hell you’re talking about” type responses. I mean, Diablo…? Seriously?

      Care to link to your SC2 profile? Just to make it clear what experience you’re basing your opinions on.

    • RaveTurned says:

      I kind of see pimorte’s point. The RTS label is often a misnomer since the real-time element necessarily reduces the scope for strategic play compared to turn based games, so they tend to end up focussed at a more tactical, reactionary level. I wouldn’t say this is a disappointment for that many people though, it’s just a trait of the genre.

    • pkt-zer0 says:

      I’m not sure even that is true. That strategy happens outside of the game doesn’t necessarily mean it’s reduced in scope.

      The comparison to Diablo is still incomprehensible, though.

    • b0rsuk says:

      I couldn’t have said it better. Have a cookie.

      pkt-zer0:

      You do realize your response is a personal attack ? You don’t adress the points he’s made.

      As for your later statement that the strategy happens outside the game – that’s pretty damning. It makes it even more like piano, and yes, Diablo ! You just make his point even stronger. Very few people can improvise while playing piano and produce something of value. Your statement makes Starcraft similar to Magic: The Gathering, too. It too could be defended by saying “strategy happens outside the game”. But the point is, in M:tg deck building is VASTLY more important than actual playing skill. Even the best player won’t win with a poor deck. And when it comes to playing, a lot is defined by the single card you draw every turn. Other card or board games have better mechanics, like letting you draw up to, say, 5 cards. So first you draw more cards and have more choices, and second you choose how many cards to keep for later and how many to trash.

      I can (with some effort) accept that there are people who like Starcraft, and it’s a good game in that sense but calling it a strategy game is wrong. It has elements of strategy, just like Diablo has elements of RPG, but at its core the first is an arcade game, while the second is a collectible game. (For an action RPG that has proper action and very interesting multiplayer, see Nox)

    • pkt-zer0 says:

      @borsuk: I didn’t address the points he made for the same reason I wouldn’t argue “the sky is not blue”, but would first ask if he’s ever looked up at the sky.

      And no, it’s not a personal attack, it’s a perfectly valid inquiry. His entire argument hinges on whether he’s qualified to make the objective statements he did or not. There was no reasoning given.

      Same goes for you here, obviously. SC2 profile please, or any sort of indication that you’re not just talking out of your ass.

      But the point is, in M:tg deck building is VASTLY more important than actual playing skill. Even the best player won’t win with a poor deck.

      Because in SC, you can win even if you only build workers in the first thirty minutes (a laughably bad strategy, in case you were wondering), as long as you’re a good enough player? Is that what you’re saying?

    • b0rsuk says:

      pkt-zer0:

      “What you’re doing here is called ignoring the point. It’s a also know as a straw man.”

      I’m very happy to educate the ignorant like you. Straw man – it’s intentionally substituting opponent’s argument for another, superficially similar but easier to refute. It’s intentionally misrepresenting someone’s opinion. I do nothing of this sort :P. I pointed out the truth – you waved away his argument as useless without using any argumentation.

      “Nowhere was it implied that first-hand experience is the only form of experience, the point simply was that you shouldn’t start arguing about a subject if you don’t have a bloody clue.”

      You’re contradicting yourself. You just waved his arguments away saying he doesn’t have a clue, but you can’t even say why. The simplest explanation is you simply [i]can’t refute what he said.[/i] Your attempt at argumentation suggests his SC profile, or more speficially win/loss ratio is more important that what he said. I pity you, and hope you get better.

      “The same goes for you”

      Still too good to offer an explanation or counterargument ?

    • b0rsuk says:

      pkt-zer0:

      Okay, my replies apear out of order.

      You say that talking without showing a SC profile is “talking out of ass”. If that’s not a personal attack instead of argumentation, I don’t know what it is. Again, no attempt at backing anything up. The guy has beaten you fair and square.

      I’m happy and proud to say I don’t have a SC profile. I don’t want one. I don’t have to be a shoemaker to know good or bad shoes. There are other sources of knowledge, for example sc2 replays are common and easy to find. Multiplying anything said by someone’s battle.net profile is just a personal attack, and very typical for battle.net natives. That’s why I believe you own the game.

    • pkt-zer0 says:

      @b0rsuk: Your attempt at argumentation suggests his SC profile, or more speficially win/loss ratio is more important that what he said.

      Hey, look, another straw man. See this part?

      SC2 profile please, or any sort of indication that you’re not just talking out of your ass.

      Notice the lack of reference to a win-loss ratio, and the bolded part specifically stating that all I require is for people to have a clue before they just flat-out claim the game has no strategy without any sort of reasoning backing it up.

      There are other sources of knowledge, for example sc2 replays are common and easy to find.

      Indeed. There’s a minor detail you seem to have “accidentally” omitted: have you actually watched (and understood) any of them? Or the Day[9] daily? Because I find it hard to believe you’d just dismiss all of that as a bunch of baloney.

      Still too good to offer an explanation or counterargument ?

      The problem is you’re looking for an argument, rather than any sort of understanding. My explanation has been clear enough: the potential for strategy in the game should be obvious to anyone somewhat familiar with the game. I don’t see much of a reason to go further than that if you insist on arguing from a position of ignorance. As I’ve said before, you really should just look up before claiming the sky is, in fact, not blue.

  6. Koldunas says:

    I’m getting a really bad impression about the current SC community. All well-argumented discussions about the nature of competitive RTSs (not even criticisms) getting these pathetic “what’s your win percentage, n00b?” responses.

    • RogB says:

      same here. Didnt expect it from a RPS thread tbh.

      must be because i’ve never played SC2 online. OMG NOOB.

    • pkt-zer0 says:

      “All well-argumented discussions about the nature of competitive RTSs (not even criticisms) getting these pathetic “what’s your win percentage, n00b?” responses.”

      The well-argumented ones? Not really, no.
      Or maybe I’ve just become desensitized to such responses, or whatever.

    • Neut says:

      They’re not asking “what’s your win percentage”, they’re asking people what their experience with the game is. It feels like a lot of people are making statements of fact about the game (it’s just guitar hero button mashing, it’s purely a game of reflexes, there’s no strategy) from positions of ignorance.

      It’s not a matter of comparing e-penis or “pssh noobs”. If you don’t enjoy the game that’s fair enough, but if you’re going to qualify that by objectively stating it lacks strategy, it’s just about reflexes or you’re just carrying out the motions like a robot, you better back that up by demonstrating you know what the hell you’re talking about.

      I’m a shit player myself – don’t play 1v1, bronze 2v2, gold 3v3, but even then to me it was blatantly obvious some of the comments here are pure nonsense.

  7. rebb says:

    The whole cookbook-recipe-ness ( oooh i must build this at the exact moment, then add a grain of salt ) that StarCraft became always bothered me, it didn’t feel like there was actual Strategy going on, just following a list of items to do, maybe jumping to a different list of items if one has more information on the enemy.

    • pkt-zer0 says:

      Wouldn’t an implementation of any strategy be a “list of things you have to do”?

    • Luke says:

      I’m not very good at SC2, or many multi player rts’es, much as I love them. But I can appreciate the depth and strategic possiiblity of people who are betetr than me nonetheless, without having to reason that fastest clicker wins.

      It does make me wonder at these people who scorn Starcraft 2 for it’s limited strategic scope, yet they can’t grasp the simple complexities, or problems, if you will, of a fairly straight forward argument.

  8. Malibu Stacey says:

    ITT: People who don’t understand competition trying to comment on competitive strategy.

    Note: I don’t play Starcraft 2 or any RTS competitively (unless you count AI War) but the I’ve seen the same rhetoric many times in various communities for HL1 mods & Source Engine games/mods over the last decade. As it was in Natural Selection, as it is in Team Fortress 2, as it will be.

    • CMaster says:

      That said, the competitive players in NS had some crazy ideas, despite me agreeing with you in regards to some of the comments here.

    • b0rsuk says:

      What you’re doing here is called poisoning the well. It’s a pre-emptive personal attack. By your logic I should never comment on abortion until I’m born as a woman and give birth.

      Try focusing on argumentation and responding to points, please.

    • pkt-zer0 says:

      @b0rsuk: What you’re doing here is called ignoring the point. It’s a also known as a straw man.
      Nowhere was it implied that first-hand experience is the only form of experience, the point simply was that you shouldn’t start arguing about a subject if you don’t have a bloody clue.

      Try focusing on argumentation and responding to points, please.

      The same goes for you, too.

      (correcting reply fail)

    • b0rsuk says:

      …and back to Magic: The Gathering.

      No, I was trying to say that just like in M:tg, whatever in SC2 is left of strategy happens outside the game. A player building 30 drones won’t win even if he’s a good one. An extremely formulaic, cookbook game.

      Do you know the quote “No plan survives contact with the enemy” ? I think it’s a very good indication if a game is a strategy or not. It was said by a field marshal, so I think he knew what he was talking about. Can you say with a straight face that it applies to SC2 ? Hardly. There are some choices later on, but provided that first you play strictly according to a script, to have any chance of survival. If you don’t, there’s no late game for you.

      Back to the article. I think this is just the the beginning. I think we can in near future see StarCraft AI good enough to beat 99% of regular players. The early game is so limited that the AI doesn’t have to be good at later stages, it won’t let players to survive that long.

    • pkt-zer0 says:

      Do you know the quote “No plan survives contact with the enemy” ? I think it’s a very good indication if a game is a strategy or not. It was said by a field marshal, so I think he knew what he was talking about.

      Do you know the quote “Great in-game decision making is the hallmark of an expert player”? It was said by a guy who has played Starcraft for 11 years, so I think he knew what he was talking about.

      So yeah, if that’s your criteria for strategy, SC2 easily qualifies.

      There are some choices later on, but provided that first you play strictly according to a script, to have any chance of survival.

      Fending of early rushes is mostly a matter of scouting and micro, and as such probably the least scripted part of the game. So what exactly are you talking about, here?

  9. Virgins for LIFE says:

    +1 virgins for LIFE

  10. Hothgadt says:

    @Hidden_7

    While you know a lot, you get a lot things wrong too.

    First of all, chess will not be solved. The number of possible situations on a chess board is larger than the number of atoms in the universe, so you cannot ever write that book down (or keep it all in your brain, since that too depends on cells, neurons, short: matter)

    Secondly: Off corse Starcraft is a turn based game. The turns are only very very rapid and the game doesnt wait for you to give a command in each one. The main difference between computer chess and computer Starcraft is not the lack of turn-based-ness, but rather (a) incomplete information and (b) the number of possible “moves”

    b is the killer thing that prevents you from writing minmax- or alpha-beta-algorithms to make AI players. While in chess you might have 30 or 40 legal moves at any point in time, in starcraft you can basically tell any of a hundered units to attack move to any of 200*200 locations, which is 4 million attack move orders to single units alone. Also the end of the game is several thousand “moves” in the future… Therefore the game tree you would have to search is a little large to handle :-))

    I enjoy both, playing challenging games at ahigh level, and also writing computer programs that do, the important thing is not to confuse the two. While a game might be “easy” for computers, or “fun” to write an AI for, it isn’t necesarrily easy for humans or fun to play … and vice versa.

    Cool things happen, when human professional players, like in Chess or Backgammon today, start learning things about the game from their AI sparring partners.

  11. ManusDei says:

    I’m confused why so many anti-Starcraft people are commenting on this thread/build. If you don’t like SC, why are you even here?

    And yes, there are valid reasons not to enjoy it. But complaining that you don’t want to put the thought or effort into a game to get better is an unfortunate circumstance that you’re passing on to us in the form of whining. And quite honestly, we don’t care for it. Go enjoy your simple, thoughtless games and let us enjoy our Starcraft.

  12. pkt-zer0 says:

    @borsuk: What you’re doing here is called ignoring the point. It’s a also know as a straw man.
    Nowhere was it implied that first-hand experience is the only form of experience, the point simply was that you shouldn’t start arguing about a subject if you don’t have a bloody clue.

    Try focusing on argumentation and responding to points, please.

    The same goes for you, too.

  13. spawnmoreoverlords says:

    Zerg player here, this makes me very happy.
    Going to play around against ai few times to see if I can transition of this starter into later game.

  14. lamellama says:

    I’d expect nothing less from the future saviour of the human race. John Connor

  15. James T says:

    Hey, James T.

    I get it. I comprehend it completely.

    I don’t like it.

    Perhaps you don’t comprehend that.

    The way you describe fighting games is nothing like how they are played.

  16. oizeaurar says:

    We have already some BO and replays sc2 to counter this strategy at http://www.makozfriends.com

Comment on this story

XHTML: Allowed code: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>