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)."
Especially of the ones who frigging *know* what genetic algorithms are all about, as I expect a better half of /.?
Paul B.
P.S. Or was it auto-generated by a genetic algorithm? :)
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. Of course we can't watch 15 flash points at once...
For in politics, as in religion, it is equally absurd to aim at making proselytes by fire and sword. - Publius
Makes sense to me... do you know Starcraft or RTS's in general?
Make sure everyone's vote counts: Verified Voting
If this continues, SkyNet will rise and take domination of all multi-player strategy games. What are we going to play then?
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
All work and no play makes Jack a dull boy.
Lighten up.
Who knows, with the help of this kind of technology, maybe I can play against Koreans without BEING HORRIBLY MURDERED! (Until they start doing it, at which point we're all proper-fucked.)
Friend: "The NIC is misconfigured..." Me: "No prob, I'll just telnet in and fix it." *Silence*
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.
I would love to have a tool like this to solidify the "Theorycraft" behind build orders in SC2 :) I mean, I've got my build orders down pretty good now, but that doesn't mean a genetic algorithm isn't ready to punch my face :)
Nah, mutations, multiple iterations and choosing good stop conditions will avoid getting caught in local minmums. This isn't hill climbing.
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).
You mean an algorithm designed to compute the best possible path to achieve a result given known variables can ACTUALLY compute the best possible path to achieve a result given known variables? How amazing!
Made sense to me. Granted lines from it are fail:
In other words, have the most successful reproduce.
Need help treating your acne? Come here!
This isn't very surprising, given that similar things existed for StarCraft 1. Namely, "Evolution Forge". It is the first successful implementation for SC2 that I've heard of, though.
However, through exploring SC1 build orders with Evolution Forge, I found that the mass of players manage to replicate the best build orders. I think this will likely be the case for SC2 as well - many man-years (or perhaps even man-centuries) have already gone into tweaking SC2 build orders, and human-tweaked schemes can be optimized for both speed and adaptability.
From what I gather, it's equivalent to a computer brute forcing its way to play chess. Only, unlike chess where it literally would go through all potential moves, SC2 only allows to those build orders previously entered into the program.
So it can't really decide new build orders, it just tells you which build order of those inputted are the most likely to succeed. And I guess does them?
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.
So are particle swarms, and many other types of optimization algorithms.
Think of an application, even a trivial one, like something that generates visuals based on the genotype.
Enjoy!
I doubt you can find a global optimum.
The performance of GA is impressive, and you can quite easily find solutions that are suboptimal mathematically, but surpasses the capabilities of humans. Such solutions are called partially solved problems, because it cannot be proven that they are the optimal solution, before the global optimum is found. And the global optimum can only be found by mathematical proof, which for most problems is currently impossible because of our limited computing power.
The algorithm is sound by the way. It's just standard GA with their own selection strategy which is apparently suited for Starcraft.
(And what do you mean not genetic? It evolves chromosomes; that is by definition genetic! And each chromosome is a )
How would you evaluate for fitness?
If you create X units of type Y - and the opponent has created units specifically to counter them, then its going to be 'unfit' - even though that it might have worked under other circumstances.
I think that the fitness function changes too rapidly during the game in order to be properly used. Also since GA take lots of time to properly function (which may include a lot of garbage) - I don't see this reacting fast enough to changes in tactics either.
So its an awesome idea - but I don't think a GA is the best tool for the job.
What do you mean "genetic-genetic"? The only thing that I can see that might be missing is a reference to "sexual reproduction" or "mating" in TFA, but I don't think that's strictly necessary for a GA. I especially liked the potential for "junk DNA" to build up. In my own simulations, chromosomes did either something or nothing consistently; perhaps it's just the domain that he's working in, but it certainly lends itself to "situational" expression of a chromosome.
It's certainly no Evolvable Hardware, but it's still a pretty neat idea.
a bunch of build orders are made randomly. they enter into a starcraft tournament and compete against each other. The build orders that win exchange parts of their build orders with parts of other winning build orders better build orders are created, bad build orders deleted... keep going for a while and keep some tourney stats and you will know what the best build orders are and what build orders counter others.
GA do tend to get interesting results.
Pretty much a shortcut to checking all possibilities of build orders.
Comment removed based on user account deletion
Thanks for responding to Jack and getting a Score of 2.
Thanks to you, I read Jack's post, and I found it hilarious.
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.
http://xkcd.com/54/
Yes, but it's painfully obvious. Even if I hadn't heard of it before, how can it not be obvious what a genetic algorithm is?
Also, they did not mention the problem of local maxima.
Choose my build order. Rock, paper, or scissor?
Yeah... this sounds like so much fun. I remember why I don't play RTS games anymore.
There is a war going on for your mind.
I suppose crossovers could be beneficial, as well as preserving some of the "bad" build orders to avoid local optima like you said, I'm just not familiar enough with the starcraft build order to tell. But even if it's only randomly mutating build orders and selecting the best ones, I'd still say it's a genetic algorithm.
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
that this can be more efficiently calculated using simple linear programming. Solutions are then even sure to be optimal, in contrast to when using GAs.
>have the most successful reproduce
This is why humans are the most successful reproducing species on the planet....not only do we reproduce like rabbits, but we also mame all other species in our areas (by building over their habitats) thereby giving us no real competitors for our resources.
If we were to encounter an alien race, I wonder if we would really be the top on the food chain....
Many people that have discussed my love for animals think I am over exaggerating my point of view sometimes...some even argued that because man was intelligent (and that dogs were not) men had more right to live then dogs.... I tend to disagree, I believe it is the one with the least negative impact on its environment that has more right to live, and unfortunately , this would make us first in line
to die as a species.
It's not a matter of intimidation or fear of losing. Memorizing sequences requires memorization skills and the desire to use them, nothing more. If I choose not to memorize, for whatever reason, playing against one who does becomes unsatisfying. If I out-think their canned routine, what satisfaction do I get? If I slip and their canned routine runs over me, what have I learned? The other player wasn't really responding to my moves. I would learn as much from studying a book. Why am I playing this person if they are going to act like a machine? They are not personally engaged in what we are doing. It's like going for a walk on a fine sunny day and meeting people who are plugged into their music systems. We are in two different worlds; they don't hear the birds I hear nor can they adequately respond to a greeting.
What the algorithm can't take into effect is micro and positioning in battles. Just because you have a more powerful army doesn't mean you will win the battle.
In a "crinkled" search area you are more likely to find local min/max and have to plan for that but that isn't the same as chaos. I could be misunderstanding your meaning though.
Sounds all very sensible to me! Don't understand a fucking word of it but it sounds all very sensible.
A closed mouth gathers no foot.
Using GAs is a fun concept, but in this case, it's just a (broken) crutch. Starcraft takes a lot of technical skill to even be able to pull off an opening correctly, so there's that. But more importantly, even if you are technically skilled, the idea of a "hard counter" is misleading. Yes, if I go pure tanks and you go pure banshees, you're going to win in a straight out fight, but there's almost always something you can do to use your resources to do something useful. For instance, suicide-attacking the other base with the tanks to try to buy enough time to get anti-air up. This might not work that great, but there's a chance, even in this theoretically obviously imbalanced situation. Hard counters only exist in boundary cases that will rarely occur in a real game. They're a mostly useless concept. If you're losing because of it, it's probably either you simply lack the technical skill to carry out what you're doing efficiently enough, or you're doing something insanely stupid without scouting and just hoping it'll somehow work. In that case, GAs aren't going to save you.
At higher level play, there's a lot of openings that simply don't have hard counters that instead rely on technical skill, adaptability, good strategy, and occasionally fancy micro. Some openings will work better against them, but none will curb-stomp them, and they are easily adaptable to any given situation once you are aware of that situation. This is why these openings are considered standard - they work against everything and aren't about gambling. Even if you try to use something that is better against a particular opening, an opponent may still scout it out in time to adapt, not by rote, but using their knowledge of the fundamental principles behind their opening.
Build orders are an important component to a skilled game. *Rush* build orders are a good way to win against beginners or throw a hail mary against someone significantly better than you. They're a lousy way to try to win consistently.
This is not necessarily original. Douglas Lenat used EURISKO (http://en.wikipedia.org/wiki/Eurisko) to win the Traveler RPG (http://en.wikipedia.org/wiki/Traveller_(role-playing_game) "Trillion Credit Squadron" championship in the early 1980's. Lenat got the attention of DARPA and later formed the company CyCorp (http://www.cyc.com/).
In the game community there are many circulating hand-perfected, opportunistic build orders:
If you could beat them, you'd be famous.
Voila, problem solved.
But the whole point of using evolutionary algorithms as a metaphor for what's happening with SC2 is that it works.
Instead of DNA being the carrier of information between lifeforms you have the brain carrying the information between games.
The evolution is in the data retained in the DNA/Brain.. no?
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.)
I haven't lost in almost a month, it's also pretty easy to do.
I just don't play the game anymore...
I don't have an intelligent phone, so I need to be.
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
Insane's build queues are all 50% time. And time is sort of the biggest resource in the game ;)
You better watch out, there may be dogs about . .
The main weakness is when you score prematurely as "fit" or "unfit". A line derived from adequate but lower-scoring stock in a certain generation may actually prove to be very high scoring after a few more generations.
Always choosing just the "most fit" or "highest scoring" from a particular generation isn't really optimal and isn't really how genetics work, either. Taking all of the top half of each generation and intermingling their offspring later would be more realistic genetically. It may also produce better final offspring after some number of generations.
The major drawback to using many more inputs per generation is you end up with vastly more runtime and memory involved to compare them at every generation. You may or may not see better final candidates for it.
Yes, I remember X-COM 3 attempted something like this. Very, very nearly a great game.
And such a scheme won't work with 3+ players, and only with 2 if you can synchronise slow down eg units automatically see each other at the same time.
I think that using genetic algorithms for such simple things like game opening is a huge overkill. I would consider using DECISION TREEs for finding the best opening, based on the fact that at a given time of the game (especially at the start), the number of distinct operations that make sense is very limited, mostly because of resource (mineral and vespene gas) is very limited at this game. Building the whole decision tree for a limited period of game time should not be a problem, because it cannot contain more than thousand nodes, and evaluating all possible routes in the tree should not be hard either. This way, every possible combination is tested and the best algorithm (based only on some basic assumptions about game logic) cannot be missed, as it could be in the case of genetic algorithms. For more information about Decision Trees, click this link: http://tinyurl.com/37sh5zn
I wonder if there's a way to apply this research to make it easier to win web-based RTS games like the awesome Lacuna Expanse? Check it out, it's totally awesome. Like a cross between Tradewars and Star Control.
- In Soviet Korea, only old people loose all their bases to Natalie Portman's petrified hot grits overlords.