Slashdot Mirror
Developing StarCraft 2 Build Orders With Genetic Algorithms
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)."
I'd like to see a game that isn't a click-fest, but still would offer some action and nice visuals. Something with the gameplay involving giving orders to partially autonomous troops. After giving orders, you could watch and see how they fare and perhaps give some further orders, maybe with some possible penalty incurred for breaking radio silence. Or in the setting of a Total War type of game, there could be a limited number messengers who would take time to reach the troops and even have a chance to fail in delivering your orders.
;)
Still, it's nice to see geeks ruining games that can be dominated by simply knowing the best build order.
The entire summary is devoted to explaining what a genetic algorithm is, though I'm not convinced this is a particularly "genetic" genetic algorithm.
I've known this technique to be used frequently in game development. It sounds like someone is using it to find good opening gambits in Starcraft. I say "good", because generational algorithms can frequently find "local" optimal solutions, whereas there may be better solutions further away from your breeding start point. You're just never sure you've found the best solution.
The actual interesting points come in the details of the strategies the program found, but those are only really of interest to Starcraft nerds.
The ______ Agenda
Traditional RTSes are all about memorizing the optimal build order (which apparently can now be calculated via an algorithm, removing the player almost entirely) and then being able to click really fast, and this is why I think it's a terrible genre. Hand-eye coordination should not even come into play in a game that calls itself a "strategy" game.
There are exceptions--those that aren't traditional RTSes, but are more real-time tactical games that focus on maneuver, flanking, suppression, and other actual military tactics instead of gathering resources and base-building.
The problem is that strategy is not inherently real-time and that too many people confuse tactics with strategy. The only games I've played that effectively combine the two are those that keep them completely separate, like the Total War series.
No one just plays the dang game anymore. Its all about winning via pre-built key sequences.
"Have you ever thought about just turning off the TV, sitting down with your kids, and hitting them?"
Yes, I find the summary comprehensible and know what a genetic algorithm is. I don't know what an explanation of genetic algorithms is doing in the summary, though. Linking the Wikipedia page would be much more effective, since so many readers get nothing out of this explanation (either they already know what a GA is and, like me, are annoyed at the minor waste of time, or they don't and a brief explanation isn't enough).
Exactly. An AI could win by exhibiting super-human micromanagement by engaging enemeies in several locations at once, diverting the attention of the human player. Unlike Chess, which is a turn-based game, Starcraft 2 is a real-time game. This gives people who can manage multiple conflicts at once while still pumping out units and maintaining their economy will prevail. An advanced AI would roflstomp a human. Blizzard's "Insane" AI for multiplayer still follows the rules of human skill. An AI bot designed to crush a human opponent would not limit itself like that.
TFA's method is designed to optimize rush builds, where the goal (ex. 7 roaches ASAP) is specified by the human. It wouldn't work at all for longer games where you have to respond to your opponent, since then your goals depend on what they do. At best, I'd say this method (1) provides strong but inconclusive support for the quality of various opening builds; (2) might find better opening builds that are not commonly known to humans. (2) seems much less likely than (1). I wonder if a brute-force all-branches approach is actually possible or even better than a genetic algorithm. For the first few minutes of SC(2) you don't have many options, so the branches wouldn't become horrifically numerous until several minutes in.
In any case, this method depends on humans to specify its goals and doesn't work in larger situations. I don't think there should be any concern about this type of AI beating "human ingenuity".
If I get SC2 I'll play the single player campaign only.
I'm really not interested in being pwned by someone who has a bunch of rush tactics memorised, let alone someone who's used genetic algorithms to optimise their deployment/build strategy.
If you read TFA, the fitness function defined as distance (in time and resources) from having a desired set of units. The example provided is having 7 roaches. The GA isn't scoped to fight battles or develop a strategy; the programmer defines the desired end-state, and the GA finds an optimum path to get there. It's a tool for developing build-orders, not an AI to play the game for you.
-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.
In the developer commentary that comes with the Collector's Edition, the primary developer of the AI (and also Blizzard's primary engine developer) says that the only difference between the difficulty levels is how many queued "actions" are allowed to be executed per second. As the AI plays, it queues up orders it wants to perform and weights them accordingly. The AI does not cheat at all, and you can verify this by watching a replay of a game against a computer opponent.
It's completely different. The whole point of evolutionary algorithms is that you start from a population of initial builds (the "previously entered"), and, at each iteration, it creates new builds by altering the existing ones at random.
Given enough builds, a lot of those alterations perform a bit worse than their original, and eventually gets removed, while others perform a bit better, and thus gets used as a base for other variations.
If your performance space is relatively smooth, that kind of approach is extremely powerful at finding minimas in the performance space. If it's very crinkled, it leads to chaos, but I don't think it's the case in this problem.
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.
Nothing, because the only way to win is not to play.
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
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.
Rampant carbon sequestration destroyed the Dinosaurs' tropical paradise. I'm here to help repair the damage.
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
Very accurate, but I have a point to add. Game designers program the AI to act "fun". Sure, they could make it a devastatingly overpowered, mind-reading unstoppable juggernaut, but that's no fun. Quite often, the AI is deliberately programmed to make poor choices (often documented in comments as "artificial stupidity"), or to make less-than-optimum choices at least some of the time.
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.
There was a story on Starcraft AI competions, they could defeat some people but not the pros.
http://games.slashdot.org/article.pl?sid=10/10/15/1411228
Video games are designed to be fun
For whom? What do people consider fun? Do all people consider the same kinds of things fun?
I think the answer is no. In the case of Magic: The Gathering (the card game), Mark Rosewater (lead designer) thinks the answer is no---his three psychographic profiles Timmy, Johnny and Spike want different things. See http://www.wizards.com/Magic/Magazine/Article.aspx?x=mtgcom/daily/mr11 and http://www.wizards.com/Magic/Magazine/Article.aspx?x=mtgcom/daily/mr220a
I think these apply reasonably well to Starcraft (and RTSes in general). Let me describe them briefly, in terms of Starcraft 1:
Timmy wants to make a splash; he wants to build big units and cause a splash; he likes tanks, nukes and carriers.
Johnny likes quirky and underused combos; he plays the oddball strategy to see if it might just work---"I have to try statis-fielding my own units to trap the opponent on one side of the ramp", or "Can I reliably win using only melee attacks?"
(Johnny also likes to make quirky RPG builds, in the style of MongoJerry's pacifist Diablo II necromancer, see http://www.lurkerlounge.com/forums/thread-10277.html)
Spike plays to win, and will play whatever is effective. Do you 9-pool or overpool on a 128x128 map? Does the answer change on 128x192 maps? How do you react when the opponent goes for +1 attack _before_ +1 defense vs. after? How good are our relative zergling micro---do I win mirror battles?
These aren't hard-line categorizations; they're attributes you can have more or less of. (I'm a multiclass Johnny/Spike, FWIW.)
They will sacrifice [anything] if it will the game more fun. If that means the AI can be beaten, so be it.
For Spike, if you nerf the AI, you make the game less fun. If godlike micro lets Spike defeat human opponents, he wants an AI to help him hone his godlike micro skills (yes, they _will_ be godlike).
He will want an AI with human-like micro skills, so that he can simulate the real deal closely; he'll also want a different AI that will let him train specific skills---say, a macrobot AI vs. him self-imposing a macrobot playing style; or a custom scenario where you have to multi-task between microing a unit being chased and building your base to defend against the "5 minutes no rush" rush.
Thats what Spike wants. That's what's fun to him. Especially if he's Korean :-)
I don't think you get to tell him he's wrong (it's a chocolate vs. vanilla thing). I think you, if you're the right person in the right job, gets to decide that you want to make a game that appeals more to Timmy and Johnny. I don't think you get to decide that there are more Timmys and Johnnys in the world; that's an empirical question. You do get to comission a survey, though, and base your product development decisions on that survey.
(Based on recent developments in popular games, as I see them mostly from the outside, Timmy is the hot new market segment.)
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
Innocent people shouldn't be forced to pay for inferior software development.
--"Code Complete" Microsoft Press
I would contend that the early game in Starcraft is far more important than the early game in Chess. An early rush, if successful, practically guarantees a win.
:) )
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?
Rampant carbon sequestration destroyed the Dinosaurs' tropical paradise. I'm here to help repair the damage.