Beta

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Developing StarCraft 2 Build Orders With Genetic Algorithms

Soulskill posted more than 3 years ago | from the nerd-intersection dept.

Programming 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)."

cancel ×

200 comments

Sorry! There are no comments related to the filter you selected.

Does anyone else find the summary comprehensible? (1)

PaulBu (473180) | more than 3 years ago | (#34098400)

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? :)

Re:Does anyone else find the summary comprehensibl (1)

rsborg (111459) | more than 3 years ago | (#34098444)

Makes sense to me... do you know Starcraft or RTS's in general?

Re:Does anyone else find the summary comprehensibl (2, Informative)

cgenman (325138) | more than 3 years ago | (#34098490)

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.

Re:Does anyone else find the summary comprehensibl (1, Informative)

Anonymous Coward | more than 3 years ago | (#34098524)

Nah, mutations, multiple iterations and choosing good stop conditions will avoid getting caught in local minmums. This isn't hill climbing.

Re:Does anyone else find the summary comprehensibl (0)

Anonymous Coward | more than 3 years ago | (#34098660)

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 )

Re:Does anyone else find the summary comprehensibl (1)

Ruke (857276) | more than 3 years ago | (#34098786)

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 [damninteresting.com] Hardware [ucf.edu] , but it's still a pretty neat idea.

Re:Does anyone else find the summary comprehensibl (0)

Anonymous Coward | more than 3 years ago | (#34099410)

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.

Re:Does anyone else find the summary comprehensibl (4, Interesting)

FrootLoops (1817694) | more than 3 years ago | (#34098550)

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 [wikipedia.org] 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).

Re:Does anyone else find the summary comprehensibl (1)

Com2Kid (142006) | more than 3 years ago | (#34098572)

Made sense to me. Granted lines from it are fail:

In other words, have the most successful reproduce.

Re:Does anyone else find the summary comprehensibl (0)

Anonymous Coward | more than 3 years ago | (#34098624)

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?

Re:Does anyone else find the summary comprehensibl (3, Informative)

varcher (156670) | more than 3 years ago | (#34099056)

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.

Re:Does anyone else find the summary comprehensibl (0)

Anonymous Coward | more than 3 years ago | (#34098880)

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.

Yes, but... (1)

RichiH (749257) | more than 3 years ago | (#34099192)

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.

All your base are belong to humans... (1)

BenJCarter (902199) | more than 3 years ago | (#34098434)

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...

Re:All your base are belong to humans... (2, Insightful)

cigawoot (1242378) | more than 3 years ago | (#34098584)

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.

Re:All your base are belong to humans... (1)

Warma (1220342) | more than 3 years ago | (#34098666)

This is misinformed. I also find it depressing that you think it would be possible to make an AI bot that would be able to crush a human opponent on equal footing.

The AI in the game is extremely stupid, like every AI in every game ever made with the exception of chess. It is not designed to "follow human skill" or give a handicap. It simply does the absolute best it can, while also cheating like hell and getting double resources.

The fact that even this is not nearly enough to beat a good human player is simply an indicator of the game's complexity and scope and the difficulty of building a proper AI in general.

Re:All your base are belong to humans... (4, Interesting)

Entropius (188861) | more than 3 years ago | (#34098870)

-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... (2, Informative)

Anonymous Coward | more than 3 years ago | (#34098972)

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.

Re:All your base are belong to humans... (0)

Anonymous Coward | more than 3 years ago | (#34099286)

Have you tried this though? The insane AI gets extra resources per worker return - try playing an insane AI and watch the resource collection rate graph by the end of it.

Re:All your base are belong to humans... (2, Interesting)

Warma (1220342) | more than 3 years ago | (#34099104)

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:All your base are belong to humans... (2, Interesting)

gman003 (1693318) | more than 3 years ago | (#34099988)

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.

Re:All your base are belong to humans... (1)

PopeRatzo (965947) | more than 3 years ago | (#34100022)

This is misinformed. I also find it depressing that you think it would be possible to make an AI bot that would be able to crush a human opponent on equal footing.

They do it in chess all the time. But of course, the number of "pieces" and "spaces" in chess is not as great as in Starcraft.

Re:All your base are belong to humans... (5, Insightful)

FrootLoops (1817694) | more than 3 years ago | (#34098612)

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".

Re:All your base are belong to humans... (3, Interesting)

fractoid (1076465) | more than 3 years ago | (#34099388)

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.

This is the road to doom (0)

Arancaytar (966377) | more than 3 years ago | (#34098446)

If this continues, SkyNet will rise and take domination of all multi-player strategy games. What are we going to play then?

Re:This is the road to doom (1)

Denihil (1208200) | more than 3 years ago | (#34098462)

"insane" difficulty bots, i would imagine.

Re:This is the road to doom (3, Funny)

Hognoxious (631665) | more than 3 years ago | (#34099346)

Nothing, because the only way to win is not to play.

Re:This is the road to doom (1)

fractoid (1076465) | more than 3 years ago | (#34099406)

Nothing, because the only way to win is not to play.

Unlike Blizzard's other popular game, where the only way to play is not to work...

Does anyone find Slashdot usefull anymore? (-1, Offtopic)

Anonymous Coward | more than 3 years ago | (#34098476)

SO many times have I responded with Industry insight, and I've been modded into oblivion by Editors and Moderators for initially sounding Draconian. For instance, a new moderation system was introduced whereas I can no longer read comments at -1 just so I catch other commentary that might not be trollish. I find this absolutely a failure of Slashdot as a Nerd Icon. I full-well recognize with my own eyes those Commentaries that have fraudulent content and meritless facts and I don't need someone's moderative pre-suppositions trying to hide that from me.

FIX SLASHDOT. Remove the Moderation SYSTEM.

Besides this, StarCraft has no class: it's like a College-student's class about Game Programming. They don't need to be efficient to capture the imagination of someone because with limitless performance it has all fruited into an inefficient scripting-language to move smoke and mirrors around on behalf of the magician to wherever the psychologists think will entertain the young audiences the most for highest yield of recurring billing.

Re:Does anyone find Slashdot usefull anymore? (1)

Shikaku (1129753) | more than 3 years ago | (#34098492)

All work and no play makes Jack a dull boy.

Lighten up.

Re:Does anyone find Slashdot usefull anymore? (0)

Anonymous Coward | more than 3 years ago | (#34098976)

Thanks for responding to Jack and getting a Score of 2.

Thanks to you, I read Jack's post, and I found it hilarious.

Re:Does anyone find Slashdot usefull anymore? (-1, Offtopic)

Anonymous Coward | more than 3 years ago | (#34099030)

Thanks for your support, Jeebs. You sure are a swell guy! I'm a...little short...tonight. How about some unmoderation on my original post huh? Thanks, you're a swell guy! Excuse me, I have to get to the men's room.

>>Thanks for responding to Jack and getting a Score of 2.

>>Thanks to you, I read Jack's post, and I found it hilarious.

On the subject of games (2, Interesting)

contra_mundi (1362297) | more than 3 years ago | (#34098478)

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. ;)

Re:On the subject of games (0)

Anonymous Coward | more than 3 years ago | (#34098520)

"can be dominated by simply knowing the best build order"

If you think that's the case for StarCraft 2, you'll get worked at your ideal game as well. Also fruitdealer attempted the "optimal" build as found in this program and it gave no advantage vs his particular opponent.

Re:On the subject of games (4, Interesting)

Iftekhar25 (802052) | more than 3 years ago | (#34098556)

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:On the subject of games (1)

Warma (1220342) | more than 3 years ago | (#34098698)

There actually is games like that, and has been for quite a while. Oldie strategy games like VGA Planets, which did not have a realtime component at all, had autonomously fought, crudely simulated battles. More modern Play-By-E-Mail -strategy games like Dominions also do this, but include more simulation and a lot more complexity.

Gratuitous Space Battles, on the other hand, is a yet more recent game consisting of nothing but pre-programmed battles on custom-built space ships. Haven't played that, though.

http://www.shrapnelgames.com/Illwinter/DOM3/DOM3_page.html [shrapnelgames.com]
http://www.positech.co.uk/gratuitousspacebattles/ [positech.co.uk]

Re:On the subject of games (4, Informative)

thygrrr (765730) | more than 3 years ago | (#34098700)

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)

Re:On the subject of games (1)

contra_mundi (1362297) | more than 3 years ago | (#34099182)

I've tried Supreme Commander before and it certainly catered more to my interests than StarCraft 2. R.US.E seems interesting, I'll be looking at that one later.

Obviosly I can't reply to every suggestion, and many of them are new and interesting, so I'll just do this once: Thanks everyone!

Re:On the subject of games (1)

Xentan (1089097) | more than 3 years ago | (#34098702)

Like chess is ruined by people learning the best openings and their counters?

Re:On the subject of games (1)

JohnFluxx (413620) | more than 3 years ago | (#34099208)

I don't know if you're being sarcastic, but it is for me.

This is true even for the game Go, where it's dominated up to 1st Dan by memorising as many opening and counters as possible.

Re:On the subject of games (0)

Anonymous Coward | more than 3 years ago | (#34100036)

This seems unlikely to be true for go. If rote memorization was all that's required for shodan then it would be trivial to produce a shodan player AI. As it stands that does not appear to be the case. I play at around the 10k level and a frequently play ranked bots on KGS. As it stands there aren't many above 4k.

Re:On the subject of games (2, Informative)

Gibbs-Duhem (1058152) | more than 3 years ago | (#34098736)

A recent game like that is called Globulation 2 (Linux, not sure about other platforms). Instead of telling unit X to do task Y, you say "I want task Y done, with as close to N units working on it as possible." and the AI for your team does its best to fulfill your requests. If you ask for impossible things (say, building 20 buildings, each with 10 units, while you only have 100 units), it instead prioritizes as well as it can based on available resources and location of units. You can also script your own AI if you like, they have a large group of people that work hard on making the AI as strong as possible by trying to script their own winning strategies. It's sort of a modern extension of the ancient game "Simant" where you could put down smells and the ants would respond accordingly without individual control. You paint areas you want scouted (or not), and the scouts go and check it out. You paint areas where you want defenders, and your defenders are allocated as well as possible.

My primary complaint was the lack of diversity in the game. Only three unit types, which could be upgraded along only a single path, and maybe a half dozen or a dozen building types. It was really entertaining until I solved the game to my satisfaction, and I haven't really played since. A fork with more types of units might be a serious contender for best game on Linux.

Re:On the subject of games (1)

Redlazer (786403) | more than 3 years ago | (#34098876)

Supreme Commander 2 is this for me.

Re:On the subject of games (1)

Seumas (6865) | more than 3 years ago | (#34098878)

I couldn't agree more. I've been looking forward to StarCraft 2. I pre-ordered it and installed it and played through most of the single player. I figured I'd be living on the multiplayer for years. In truth, I have yet to play a single game online. Perhaps part of it is just that I'm getting older (thirties, now) . . . but I suddenly find the whole "game ends in three minutes and you can tell who is going to lose, often, in the first ten seconds". It's not just Star Craft, though. There are a lot of games that I also find off-putting, because they devolve into exactly what this article describes. The knowledge that there is one perfect chain of actions you should take and the entire point of the game is to take those actions faster than the other guy. It takes the fun of discovery, surprise, variety out of it.

Re:On the subject of games (1)

TheKidWho (705796) | more than 3 years ago | (#34099582)

Must just be you, I get into plenty of 30+ minute long games. (In diamond league for 1v1-4v4)

Re:On the subject of games (1)

404 Clue Not Found (763556) | more than 3 years ago | (#34098890)

You might be interested in Gratuitous Space Battles [positech.co.uk] , a pretty space strategy game where you design a fleet, deploy ships, and issue orders all BEFORE the battle begins... then sit back and watch the fireworks. A very different kind of fun.

Re:On the subject of games (1)

Terrasque (796014) | more than 3 years ago | (#34098922)

The indie game AI War [arcengames.com] might be similar to what you're looking for. At least it focus a lot more on strategy than clicking.

Try the demo, see if it's something you like :)

Re:On the subject of games (1)

mrtonic (1229970) | more than 3 years ago | (#34099074)

Just a warning though, the AI in this game will quite happily shaft you if you give it the chance. Its brutal, especially at higher levels.

Re:On the subject of games (1)

Pinckney (1098477) | more than 3 years ago | (#34098992)

Try Combat Mission, though the troops can require a lot of manual pathfinding. Simultaneous turns (RT optional in the latest).

Re:On the subject of games (1)

gmueckl (950314) | more than 3 years ago | (#34099088)

Then you might be interested in Majesty and Majesty 2, strategy games in which your units are totally autonomous. You control them by giving them monetary incentives and sometimes helping them out with magic (which also costs money). Each type of unit also has its own character in addition to strengths and weaknesses, so they react differently to your incentives. It's quite fun to play actually and not that high on actions per minute.

Re:On the subject of games (1)

azaris (699901) | more than 3 years ago | (#34099146)

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.

Scourge of War: Gettysburg [scourgeofwar.com] and its predecessors Take Command: 2nd Manassas and Take Command: Bull Run pretty much work that way. The graphics are dated (think Medieval: TW quality) but functional enough, the gameplay fairly slow and meticulous. Most battles start with 5-20 minutes of maneuvering into attack positions, after which you order your divisions/brigades their set targets and watch them march into the fray. If and when things start looking bad you start to micromanage individual batteries and regiments. That's when it gets really hectic and interesting. Or you can play Empire: TW and watch the beautifully rendered but historically ridiculously inaccruate soldiers run up and down mountains on a tiny battlefield while being bombarded by overpowered artillery.

Maybe, just maybe... (1, Insightful)

John Pfeiffer (454131) | more than 3 years ago | (#34098498)

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.)

Re:Maybe, just maybe... (1)

bonch (38532) | more than 3 years ago | (#34098604)

If you want to beat Koreans, you need to sit in front of your computer 10 hours a day doing nothing else but playing Starcraft, like in the professional Korean burnout camps. After you beat them, you'll finally get to play!

Re:Maybe, just maybe... (1)

John Pfeiffer (454131) | more than 3 years ago | (#34098900)

Aaaaaand this is why I stick to things I can actually play...like FPSs and 20 year old arcade fighting games...

This is why I hate the RTS genre (2, Insightful)

Anonymous Coward | more than 3 years ago | (#34098504)

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.

Re:This is why I hate the RTS genre (2, Interesting)

Homburg (213427) | more than 3 years ago | (#34098542)

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:This is why I hate the RTS genre (3, Insightful)

Lloyd_Bryant (73136) | more than 3 years ago | (#34098742)

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.

Re:This is why I hate the RTS genre (1)

DNS-and-BIND (461968) | more than 3 years ago | (#34099152)

What General Bradley did in WWII could hardly be described as "fun". The very word "amateur" means one who does it for the love of the task, while conversely "professional" means someone who does it for money. Logistics is a lot of hard work, and nobody does it without a full staff to assist. Indeed, logistics is well-known for its dryness and it is not something that anyone would do as recreation. It's essentially the same thing as keeping the shelves stocked in a grocery store.

I played Starcraft, and don't remember any supply rules, other than the unit limit. Maybe they added beans & bullets tracking to SC2, I'll never know. I know a few freaks who like logistics games, and they say honestly their favorite game is Microsoft Excel.

Re:This is why I hate the RTS genre (5, Informative)

moenoel (1897920) | more than 3 years ago | (#34098854)

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 [day9tv.blip.tv] : 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.

Re:This is why I hate the RTS genre (1)

LordNacho (1909280) | more than 3 years ago | (#34099790)

You're right about there being too much micro-management. Perhaps what is needed is a higher-level interface where you can pre-program some of your build/movement orders. That might make the game a bit less frantic. It could also make it a higher level of franticness...

Avid SC2 Player... WANT (1)

DoomSprinkles (1933266) | more than 3 years ago | (#34098506)

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 :)

And this is why I stopped playing SC. (2, Insightful)

Kenja (541830) | more than 3 years ago | (#34098534)

No one just plays the dang game anymore. Its all about winning via pre-built key sequences.

Re:And this is why I stopped playing SC. (1)

rax313 (1923570) | more than 3 years ago | (#34098614)

So SC2 or probably other RTS will be like chess now? with your choice of "building"/"opening" scenarios?

Re:And this is why I stopped playing SC. (0)

Anonymous Coward | more than 3 years ago | (#34098704)

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.

Re:And this is why I stopped playing SC. (3, Insightful)

murdocj (543661) | more than 3 years ago | (#34099502)

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.

Re:And this is why I stopped playing SC. (4, Insightful)

khchung (462899) | more than 3 years ago | (#34098768)

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.

Re:And this is why I stopped playing SC. (3, Insightful)

spottedkangaroo (451692) | more than 3 years ago | (#34098960)

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.

Re:And this is why I stopped playing SC. (1)

khchung (462899) | more than 3 years ago | (#34099740)

I think you another the other poster misunderstood my point. The OP's point (as I understand) was memorizing build orders is the only way and sure way to win. My point is that while it helps at low level, it is not enough at high level play.

Of course, it doesn't mean you don't memorize build orders at high level, it means that, like football passes and chess openings, the memorized build orders became part of your toolbox that you can use as the situation calls for it, and more importantly, recognize it when your opponent uses it.

For example, if you are unfamiliar with the build orders your opponent's race, then the information you gained from scouting may be wasted, as you simply cannot understand what he is doing even though you see what buildings he has.

So, in summary, build orders is something you need to remember to play at high level, and gives you great advantage at low level. But it is by no means "all there is" in SC/SC2 game play.

Re:And this is why I stopped playing SC. (0)

Anonymous Coward | more than 3 years ago | (#34099076)

Yes, and nowadays football games are all about winning using pre-planned passes, and chess is all about memorizing opening moves. /sacarsm

Sarcasm? You're right. And of course, you're also totally missing the GP's point, which was that playing games used to be about having fun. Sure, there's always an element of competition, but can't you tell the difference between a friendly chess game between friends and tournament-style, perhaps even professional play?

Or take Scrabble. There are "serious" players who will learn the official Scrabble dictionaries by heart, and there's players like my mum, who merely meets up with her friends once a week and plays a game or two as part of their coffee klatsch routine, for no other reason than that they enjoy it. There's still a winner there, too, but can't you see how it's different?

Your entire post shows that you have totally missed this point. Reaching higher levels? Competitive sports? Hard work? Pro-level SC games? That is exactly what the GP is saying isn't fun anymore - for him, but also for many others. Don't let the fact that you'll typically only hear about chess players like Fischer and Kasparov and Kramnik fool you into thinking that no others exist, or that the vast majority of chess games is played by these pros.

Re:And this is why I stopped playing SC. (2, Interesting)

StDoodle (1041630) | more than 3 years ago | (#34099212)

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:And this is why I stopped playing SC. (1)

brunes69 (86786) | more than 3 years ago | (#34099232)

The OP doesn't want to play SC as a "competitive sport". He wants to play it for fun. The difference is a backyard neighborhood weekly pick-up game vs. the NFL - it is night and day.

The OP's PROBLEM is it is impossible to find that kind of game online anymore.

This is why I stopped playing FPS's online. Games to me are a way to unwind for an hour or two a week. I don't consider myself any kind of champion and have no desire to be, I just want to have some fun.

When everyone takes things too seriously it sucks the fun out of it for those who don't.

Re:And this is why I stopped playing SC. (0)

Anonymous Coward | more than 3 years ago | (#34098792)

Apparently you and everyone with mod points has never actually played SC2. There is a reason that KeyPressBot 5000 is not the top player in the world.

Re:And this is why I stopped playing SC. (1)

Missing.Matter (1845576) | more than 3 years ago | (#34099250)

Even games old games were subject to this kind of scrutiny. I remember my grandmother telling me how she came up with a path in pac-man which if followed would maximize her points (she would get every ghost and every fruit for every level), since the behavior of the ghosts is deterministic. Honestly I feel going through that process takes what little fun there is to be had in pac-man.

Incredible! (0)

Anonymous Coward | more than 3 years ago | (#34098564)

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!

Re:Incredible! (0)

Anonymous Coward | more than 3 years ago | (#34098648)

Too jaded you are. If more people are introduced to the exciting world of multivariable optimization, that's good news!

Similar to Evolution Forge for SC1 (1)

nickersonm (1646933) | more than 3 years ago | (#34098574)

This isn't very surprising, given that similar things existed for StarCraft 1. Namely, "Evolution Forge" [clawsoftware.com] . 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.

This is why, if I get SC2 (3, Insightful)

Nursie (632944) | more than 3 years ago | (#34098628)

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.

Re:This is why, if I get SC2 (5, Insightful)

Warma (1220342) | more than 3 years ago | (#34098732)

A lot of people seem to complain about this and especially about the realtime requirement in strategy, but the truth is that in addition to the kind of economically suboptimal rush build orders you seem to hate, there are strategies designed to securely carry you into the midgame, where the opponent no longer benefits from memorized build orders.

Moreover, the whole gripe seems misplaced, as I doubt that the same players are against people memorizing openings in chess, board states in go or probabilities in poker. It's simply being intimidated by people better in the game than you - being afraid of losing. You must realize that a video gaming company the size of Blizzard is very aware of this, and the whole mentality is precisely why Starcraft has a very friendly ladder system, which tries to match you against people of your own skill level.

Re:This is why, if I get SC2 (1)

Nursie (632944) | more than 3 years ago | (#34098766)

It's not quite the same as chess, go or poker, in that timing does not have the same factor.

Either way, it takes something away from the game, IMHO.

Also never really cared for chess or Go.

Re:This is why, if I get SC2 (1)

khallow (566160) | more than 3 years ago | (#34099750)

It's not quite the same as chess, go or poker, in that timing does not have the same factor.

Either way, it takes something away from the game, IMHO.

It's a problem with any game where you might be able to win shortly into the game through an aggressive gamble. Your opening needs to be good enough to keep you from losing to an opponent's aggressive opening. In old Starcraft a common approach is the "no-rush" rule where players don't attack for the first X minutes of the game.

Re:This is why, if I get SC2 (3, Informative)

Pulzar (81031) | more than 3 years ago | (#34099174)

A lot of people seem to complain about this and especially about the realtime requirement in strategy

Actually, only a handful of people complain about this, and mostly those that haven't even played the game. On forums visited by actual players, nobody complains about this at all.

Sure, there are a bazillion complaints about other trivial things :), but people are generally interested in figuring out how to beat each other, as there certainly isn't a "one build order to win them all".

disconnecting from the moment (1)

Tristfardd (626597) | more than 3 years ago | (#34099736)

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.

Re:This is why, if I get SC2 (0)

Anonymous Coward | more than 3 years ago | (#34099040)

This is why the matchmaking service pits you against someone roughly your own skill level (after a series of placement matches). If you look at players in the higher leagues, they average around a 1:1 win:loss ratio. The matchmaking is pretty good and all but guarantees a challenging game.

Re:This is why, if I get SC2 (3, Informative)

Fahrvergnuugen (700293) | more than 3 years ago | (#34099822)

The matchmaking system in SC2 is very good at matching you against someone with the same skill. In fact, it's almost too good.

In SC1, 1 or 2 out of 10 games would be close. The other 8 would be a blowout by one player or the other. In SC2, 9 out of 10 games are close. It can be very exhausting.

I wish they would put a little wander in the matchmaker giving you a wider variety of games (some easy, some hard, some close). You can learn a lot by watching a replay where you get destroyed by a higher level player.

GAs are fun. (0)

Anonymous Coward | more than 3 years ago | (#34098642)

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!

The problem is... (1)

Haedrian (1676506) | more than 3 years ago | (#34098662)

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.

Re:The problem is... (3, Informative)

Ruke (857276) | more than 3 years ago | (#34098758)

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.

Re:The problem is... (1)

wierd_w (1375923) | more than 3 years ago | (#34098810)

The optimization might come up with a solution to this problem, through exploiting resource consumption rates and build times, so that even if you started building the counter units immediately, you would not be able to resource and construct them quickly enough to avoid being overwhelmed.

EG, it calculates how quickly (maxiumum) you can develop your harvesters, evaluates the maximum rate of resource accumulation, and determines the optimum attack strategy by choosing units that are quick to produce, cheap, and require expensive countermeasures that you could never possibly create enough of, fast enough to prevent your destruction.

Re:The problem is... (0)

Anonymous Coward | more than 3 years ago | (#34098882)

The history of GAs can be summed up that way: "awesome idea, but a GA isn't the best tool for the job".

It's never Lupus.

Re:The problem is... (1)

Beezlebub33 (1220368) | more than 3 years ago | (#34099020)

Well, that's generally true. You use a GA when you don't know the correct solution. It's just a stochastic search mechanism, and frankly one where you have to worry about a lot of the important factors, such as solution representation and fitness function. Lots of research ideas, and potential paths, but when faced with a real problem, there's usually a better tool for the job.

Okay, genetic algorithm. (1)

ihavnoid (749312) | more than 3 years ago | (#34099256)

Choose my build order. Rock, paper, or scissor?

Re:Okay, genetic algorithm. (0)

Anonymous Coward | more than 3 years ago | (#34099318)

Rock!

Good ol' rock. Nuthin' beats that!

Uh yeah... (0, Troll)

Jaysyn (203771) | more than 3 years ago | (#34099356)

Yeah... this sounds like so much fun. I remember why I don't play RTS games anymore.

Day Traders (3, Interesting)

Danathar (267989) | more than 3 years ago | (#34099420)

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:Day Traders (1)

LordNacho (1909280) | more than 3 years ago | (#34099820)

The reason this might not work is that in a game, it doesn't cost anything to explore all the different paths you can take. Which sword is better? What strategy for build order? Keep playing, and you'll come across everything. The game will act the same, and it won't cost you anything to learn.

In the market, there's no easy way to try out stuff without putting money on the line. Furthermore, the rules change, and the market doesn't necessarily act the same the next time a given event happens. It has memory.

Re:Day Traders (1)

Dekar (754945) | more than 3 years ago | (#34099984)

Bots perform a ton better at day trading, and in the stocks market in general, than they currently do at games like Starcraft or poker. I'd say it's an entirely different set of skills.

Besides, day trading really doesn't contribute more to society than playing SC2 does, it might actually be the other way around. The only change would be his personal wealth and overall happiness, which are in no way proportional.

I submit (1)

TranceThrust (1391831) | more than 3 years ago | (#34099506)

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.

Mass reproduction (0, Offtopic)

hesaigo999ca (786966) | more than 3 years ago | (#34099612)

>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.

Micro Matters (1)

Billkamm (322282) | more than 3 years ago | (#34099928)

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.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?
or Connect with...

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>