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)."
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).
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).
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.
You have three choices (assuming the Total War series cannot be counted as viable Multi Player choices)
More Strategic: R.U.S.E (awesome visuals, very autonomous units, very indirect control)
More Direct: Supreme Commander - Forged Alliance (decent visuals, unprecedented scope of war and great control over your units)
More StarCrafty: Supreme Commander 2 (think ugly Starcraft with the ability to fully zoom out)
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.
What we call "strategy" in in fact mostly a matter of logistics - having a perfect tactical plan is worthless if you can't keep your troops supplied during the course of it. RTS games are generally just a simplified/idealized version of how things work in the real world.
Amateurs study tactics, professionals study logistics
(attributed to Gen. Omar Bradley)
It sounds like what *you* want is a large-scale RTT (Real-time tactical) game, where all you have to worry about is deciding on which units to move and where to move them. Personally, I would consider *that* boring, as it removes a lot of the complexity that makes a good RTS challenging.
Don't tell me to get a life. I had one once. It sucked.
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.
No one just plays the dang game anymore. Its all about winning via pre-built key sequences.
Yes, and nowadays football games are all about winning using pre-planned passes, and chess is all about memorizing opening moves. /sacarsm
At your level when ppl are just learning how the game works, then, yes, a pre-planned built sequence can often win you the game. Much like a football team with well practiced passes can win low level games with little more than executing their practiced passes. Or beginning chess players can win games by playing from memorized opening moves.
However, once you reached a higher level, then if you cannot adapt your strategies to the situation at hand, you WILL lose against opponents who can.
This is the same with ANY competitive sports.
Yes, that involves a lot of practice and hard work. Seems like you just never reached that level. (Neither did I, BTW). But you can see it in the pro-level SC games in Korea. How the players respond to the unexpected is what differentiates good and not so good players.
Oliver.
The fast and coordinated clicking stuff is only the first part of learning SC (II). Strategy comes after that.
To (not literally) quote Sean 'day[9]' Plott: If you are interested in american football and want to play various tactics on the playfield, you first need to train your body. I.E. if you are a scrawny guy, with no muscles and stamina whatsoever, you can think about football tactics all you want, but you simply won't be able to execute them for lack of the basic requirements.
Same goes for SC (II) and every (balanced) RTS in general. The *real* strategy part only comes into play, after the player mastered the basic mechanics of gameplay.
-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.
I think the point of your post is clear and correct. I'm not arguing that at all, but...
Or beginning chess players can win games by playing from memorized opening moves.
I don't actually play chess, but I know a few people who do. I think you actually have this backwards. You can get by playing the game at the low levels, but if you want to get advanced you need a really big library (of actual books) so you can memorize things. You have to get to the very very top to get back to playing.
I'm not saying there isn't a lot of thinking and analysis going on, but it appears to me (from the outside and from comments from "expert" level players) that memorization is key to winning chess at the higher levels.
Then again, I'm told (by an expert level player who hates this) that it can be hilarious to memorize archaic openings that nobody bothers with and using those as your opening, so you can hopefully get to a middle game that isn't memorized.
Imagine if you weren't allowed to use roads because a bus company complained about your driving 3 times. --skunkpussy
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.
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
it's been that way since war2 and before. I remember learning build orders from cases ladder players on war2+kali. Oh how fun that was, smashing face with bloodlusted ogres then dragons. Such a simple strategy, it normally lost to good micro of someone doing almost exactly the same thing (or worse, quick upgrade grunt rushing.)
Star Craft build order discussion became a bit of a national past time in South Korea before the release of SC2, now that's the primary focus.
I loved it in war2 when someone came at me with dragons. Dragons took forever to build. cost of a ton of gold, and were easy to kill. Took a little bit of micro but I was awful at micro and I managed to do it... a mage to slow them, a blizzard, and a couple of archers and they were dead.
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.)