Developing StarCraft 2 Build Orders With Genetic Algorithms 200
Jamie recommends a blog post from software engineer Louis Brandy explaining how using genetic algorithms to evaluate build orders in StarCraft 2 has led to some surprisingly powerful results. Quoting:
"One of the reasons build-order optimization is so important is that you can discover openings that 'hard-counter' other openings. If I can get an army of N size into your base when you do opening X, you will always lose. ... a genetic algorithm is a type of optimization algorithm that tries to find optimal solutions using a method analogous to biologic evolution (to be specific: descent with modification & natural selection). Put simply, you take a 'population' of initial build orders, evaluate them for fitness, and modify the population according to each element’s fitness. In other words, have the most successful reproduce. The program’s input is simply the desired game state. In practice, this means 'make N units' to determine some rush build order (but it also allows for other types of builds, like make N workers with some defensive structures and a small army)."
On the subject of games (Score:2, Interesting)
Still, it's nice to see geeks ruining games that can be dominated by simply knowing the best build order.
Re:This is why I hate the RTS genre (Score:3, Interesting)
I remember reading a review of one of the early RTS games that pointed out that they weren't so much strategy games as logistics games; the reviewer predicted the failure of the genre on the basis that everyone wants to play the general, they don't want to play the quartermaster. Obviously, he was wrong, and a lot of people do want to be the quartermaster; but he captured what I've always found so boring about RTSes.
Re:Does anyone else find the summary comprehensibl (Score:4, Interesting)
Re:On the subject of games (Score:5, Interesting)
Well, to be fair there's a lot more to SC2 than just build-orders. :-) Build orders are mainly concerned with the "macro" aspect of SC2 gameplay, which is base management and economy, and they're also relevant only in the opening. Everything past the 7 or 8-minute mark is beyond build orders. Good micro (unit-level manipulation of movement and actions), harassment of workers, and timed expansions all kick in after that point, and those become the difference between winning a game and losing a game.
Also, there is an element of "good practices" in SC2. Rushes, especially "all-in" rushes (referred to by TFA) are generally considered bad practice. Beating your opponent every time is cool, but this is usually indicative of a game imbalance that Blizzard will probably patch at some point down the line, at which point you'll rapidly fall in the leagues as you lose to high-level players clued in on countering that or who simply have the good practices to beat it (like early scouting, etc.).
The other (more important) factor is that a gamer specializing in an all-in rush deteriorates his/her gameplay, because he won't have the variety to compensate for a failure of that rush. A rush usually means a sacrifice of something or the other (the tight game-mechanics of an SC2 opening means there's always an opportunity cost; to get that extra army, your economy suffers, or to get those extra resource-collectors, your army will be smaller). All-in rushes, and rushes in general sacrifice some thing or the other which a good opponent can exploit if he/she manages to push back the rush. Someone over-playing one tactic will lack the skills to compensate for its failure, so varying one's game by mastering different build-orders and plays is the better way to do this (if slower).
Re:All your base are belong to humans... (Score:5, Interesting)
-1, Misinformed
The AI does not get double resources (although on Very Hard and Insane it does get an extra amount, but not double), and it does not do the absolute best it can. I guarantee you that if given the source code I could improve it, by simply exploiting the hell out of its APM advantage. The reason is that the AI has imperfections designed in; it is designed to respond somewhat superficially like a human opponent and not exploit godly micro tricks that a 2000+ APM computer could use. Here are a few things to get started: roach burrow micro; hidden queens in overlords microing transfuse, perhaps on dancing mutalisks; blink micro tricks; rotating damaged infantry in and out of bunkers; thorship micro.
Yes, making a proper strategic AI is very hard. But the included AI has a lot of room to improve in tactics, just by virtue of the ridiculous APM it can exploit.
Re:All your base are belong to humans... (Score:2, Interesting)
That is actually very interesting and I did not know that. I assumed that the lack of micro arises from the computers' lack of positional awareness of the game state. Ie. the sense in transfusing with queens or burrowing with roaches heavily depends on the composition of the opposing army and whether he is focus firing, does he have detection available.
In other words, the value of the micro tricks you mention is questionable in the sense, that could you build the AI to be able to routinely create situations where it would be able to exploit those heavily. The only one of your mentions, which I see being totally OP in actual combat situation is the ability to dodge incoming shots with blink stalkers.
Re:And this is why I stopped playing SC. (Score:2, Interesting)
There is a go proverb that states "Learning joseki loses two stones strength" which would apply. (Joseki are "are generally agreed-upon sequences of play resulting in what is considered a fair outcome for both players.") The basic idea is that you'll handicap yourself out of learning why and how to respond to your opponent if you focus too much on standard patterns. It's generally accepted that you shouldn't spend too much time on joseki until your understanding of the game is at a level where you can actually analyze the moves in a joseki, understanding as you go WHY each move is the best in the situation and HOW it depends on other factors.
http://senseis.xmp.net/?Joseki [xmp.net]
http://senseis.xmp.net/?LearningJosekiLosesTwoStonesStrength [xmp.net]
Re:All your base are belong to humans... (Score:4, Interesting)
I'd bet on human ingenuity vs generic build orders though. We learn build orders from each other and adapt far faster to disruptive tactics than any AI can at this point.
You bet wrong. Build orders only influence the first few minutes of the game, but they set the economic foundation for the entire early and mid game. A strong build order will give an otherwise average player a huge advantage over similar level players with weaker build orders. That's why the first thing you should do when trying to become competitive at an RTS is research build orders (even if you create your own, you still need to research standard build orders to give yourself a benchmark to work towards).
This reminds me of the old 'double hero rush' build that someone (madfrog?) came up with in Warcraft 3. By sacrificing a large portion of your early game economy you can buy your town hall upgrade much earlier than usual, leading to the ability to build two heroes very early in the game. Normally a build like that would be suicide but in the hands of a skilled player it became pretty strong.
Day Traders (Score:4, Interesting)
I've often watched my brother who is a multitasking jedi play WoW, SC2, etc and I've often asked him why he does not go into day trading. The skill sets of managing a quickly changing massive amount of information and evaluating probabilistic results for gain is EXACTLY what real time traders do.
Computer games, role playing games (with emphasis on the statistical portion), war games, RTS...
When it comes down to it, it's nothing more than statistical simulations.
If some game company can overlay something like WoW or SC over a real time stock trading system,...well...we will see what happens when a bunch of people who spend hours every day optimizing probabilistic statistical systems to their advantage has on world financial markets.
Probably would make a good Sci-Fi Novel if nothing else
Re:All your base are belong to humans... (Score:3, Interesting)
I'm literally coding the AI for a small game in my other window, and I'm doing just this. The AI has an advantage in stats - particularly, higher magic abilities. I had originally coded it to exploit that advantage until its mana ran out. It was difficult to beat, but also very boring to beat, because it kept spamming one attack. I added a small check, so it only exploits that advantage 50% of the time. Otherwise, it goes on down to less-than-optimal options. It's a lot more interesting this way.
Video games are designed to be fun, first and foremost. They will sacrifice realism, or difficulty, or almost anything, really, if it will the game more fun. If that means the AI can be beaten, so be it. The AI can't enjoy the game. The player can.
Re:On the subject of games (Score:3, Interesting)
If you read through some of the forum posts linked in the article you'll see that after not too long he encountered protoss players who easily countered his rush based on scouting and knowing what sorts of things to do. In this case the right thing to do is see that there are no zerglings out, so whack down a forge and at the last minute warp in some cannons behind a building wall. That pretty much stops the rush dead, at little cost to the protoss economy, while the rushing zerg has little left, with the cannons not arriving till he was committed to the rush and thus lost all his units. It will not be long before this sort of obvious counter becomes well known and the rush will become completely ineffective.
What RTS Genere? I only see RTT+E... (Score:3, Interesting)
Publius (or Gaius) Cornelius Tacitus brought us "tactics", and Strategos, plural strategoi Attic-Ionic (Greek: , pl. ; Doric Greek: , stratagos; literally meaning "army leader") brought us "strategy".
Strategic planning is _all_ about logistics. Your comment seems to infer a distinction that doesn't exist there.
Strategy is getting you units to the right places with the correct intelligence and provisioned and equipped for their task.
Tactics is executing your task in the best possible manner, with contingencies considered and ready for the fact that no plan survives contact with the enemy.
For instance, while people often (mis)describe Chess as strategic, it is mostly tactical. The only vaguely strategic element of chess is that there is a hierarchy of threat used as "support" for a piece. e.g. if you take my knight with your queen, the rook that covers it will get her. This is pure tactics.
Most "real time strategy" games actually fail utterly to be strategic in any form. They have economy and they have tactics, but they lack all forms of proper strategy. You don't ever have to "supply" your units, so you never have to have "supply lines". That means that you don't really have to control an area of the map in a proper sense.
Were I to make StarCraft actually strategic:
Zerg would only take orders if there were a sufficient number of overlords "close enough" to the units in question to pass those orders. There would also have to be a chain of overlords to bridge the distance between a hive and the directing overlord in question. Units not directly under control would drift, do random things, and possibly squabble. Unit groups under "insufficient control" would get sloppy. If an overlord becomes isolated from all hives it and its units will become defensive and put out a "distress call", and some hive will extend an overlord chain towards that position. Said chain would unreel from the base (closest overlord would advance to a controlling position, the ones behind it would move as well, and back near the base a new overlord would be dispatched to fill the trailing gap etc.) A set of units can be tied to a particular overlord and then given "standing orders" to guard or patrol, such a unit will persist in this action without further control (e.g. it can be isolated deliberately or accidentally) but its orders cannot be changed at all until a control conduit is restored.
The Terran forces would have (automagic) runner units that would resupply field units. There would be no build cost for these guys, and there would be a good number of them as they would appear on demand. But they would be destroyable. The player could assign particular supply depots to particular units if he would like, and drop routing flags that the runners would "want" to run between. Each supply depot would be able to generate a particular amount of supplies per minute, but they could charge like batteries and there would be an default "expected peak demand" based on proximity and or tuneables. It would therefore be useful to have supply depots near combat locations. As units run out of supplies their fire rates slow and eventually stop. A unit can be flagged "do not resupply" and will receive no runners (needed for ghosts etc so that the runners don't reveal the ghost) but when the unit goes hungry it will be useless until the flag is removed and a runner reaches it. "Priority supply target" can be set for the reverse condition so that a main defensive position can be maintained "at all costs" etc.
For the Protoss, any unit that leaves the field of a Pylon would gain a chain of lights (destroyable micro pylons) to power it. Isolated pylons would generate their fixed power. The first time a unit moves to an isolated pylon its chain of lights would span to that pylon, connecting it to the grid. Any unit that isn't "locked" to a pylon would automatically re-anchor its chain to the last pylon it was powered by. Units within one-light of the nearest pylon don't need the light (to reduce graphics loa
Re:All your base are belong to humans... (Score:3, Interesting)
I'm not disputing that excellent micro and strategy mid-game is often a decisive factor. I'm just saying that, all else (skill, strategic ability etc) being equal, a player with a good build order will have a strong advantage over a player with weak or no build order.
(Also, I must confess to being a bit of a Boxer fan. It's precisely his incredible micro and mid- to late-game strategy that make his games so interesting to me. Did you see that game where he took down half a dozen Carriers with about 20 stimmed marines?