Zerg Build Order optimizer.

This is what high level players do already. If you sat a high level player down and said: 'get 7 roaches into your opponent's base as fast as you can,' in a few hours they'd have the optimum build. I see this as being much more useful for new players who probably don't have super-efficient builds,and is not a game breaker in any way.

This is rarely what pro gamers are after anyways. As I understand it the goal is usually to make the leanest possible build that can deal with what the opponent is doing, and to invest remaining resources in macro. That requires in-game testing to figure out and this program wouldn't be so useful for that.

So to answer your question I don't think you have to worry about breaking SC2!

Adeny Norway. October 13 2010 11:44. Posts 1230

Profile Blog #

Concept is cool, build is useless. They just get a forge when they see your warren and win automatically, maybe with 4 range but I doubt it...

Rybka United States. October 13 2010 11:49. Posts 468

Profile #

What people are missing in the potential of a program like this is, well...

http://en.wikipedia.org/wiki/Rybka

What this program would seem to be best-suited to is highly detailed replay analysis. You can't plan a perfect game out from beginning to end, but what you can do is go through the game and take notes about critical decision points. In situations where you did something wrong, or simply not fast enough, you could run the program to tell you how long it would take to perfectly execute the proper decision... whatever that decision might be. If it's 7 corrupters or 8 marines or whatever, you could find the optimal time those units could be built in and whether or not your "position" was truly lost.

Groundwork for some very, very cool stuff in SC2 and definitely not amoral IMO. With enough effort and programing it could really evolve the game.

"Leoric is one of the most heroes around." -Qbek

ZodiakLucien United States. October 13 2010 11:54. Posts 14

Profile #

On October 13 2010 11:26 Lomilar wrote:
Psst, its ovi*2 at 18.

fixed

Lobotomist United States. October 13 2010 11:57. Posts 1229

Profile #

Wow man, that is awesome! Very impressive coding.

Could you give it a goal like, "Build 8 roaches and 8 mutas. Must have 3 roaches before spire starts building."?

Teching to hive too quickly isn't just a risk: it's an ultrarisk

DragonDefonce United States. October 13 2010 12:00. Posts 782

Profile Blog #

Would this program be able to optimize something like 30 workers, 2 hatcheries, 10 zerglings, 2 spine crawlers? Then this could be used to optimize all sorts of build orders, allins and economical alike.

FLuE United States. October 13 2010 12:02. Posts 809

Profile #

Concept is cool, build is useless. They just get a forge when they see your warren and win automatically, maybe with 4 range but I doubt it...

A - I think he was just using this build as an example. If he posted the optimal build to make 6 lings nobody would have cared, if he posted the optimal build for 10 mutas it would have been 10 pages long.

B - The build isn't useless. I've already tried it and it is very fast, and effective. So for a side note, it is actually a nice opener. I've only done it in some 2v2 RT games, so not sure how it would do in 1s but in a 2v2 it is a nice little build.

C - What league are you in that the response to a roach warren on 18 is forge and cannons? And if they do that, then just expand while they turtle behind cannons? Actually cool thing with this build is it looks like a 10 pool if you get just a quick scout...and your economy isn't really horrible after the roaches come out either.

Almania October 13 2010 12:07. Posts 145

Profile #

On October 13 2010 09:29 FrostedMiniWeet wrote:
I was actually considering writing a similar program.

I was actually underway writing such a program a couple of weeks back before.. like most of my impromptu unpaid programming tasks I got bored and moved on =p.

Now it's piqued my interest again and I want to get back to it...

Props to the OP, nice work.

BladeRunner United States. October 13 2010 12:09. Posts 407

Profile Blog #

I have a friend who's a genius at CS, worked on the AI they put in robots sent to the moon, and I've had many interesting conversations with him about Machine Learning (a topic he is quite interested in). I, being a meer CS bachelor's degree holder was of course familiar with genetic algorithms, but I learned by talking to him that they're widely considered suboptimal to experts in the field.. They tend to get stuck on local maxima/minima.

According to him (and unfortunately I can't really back this up as I'm not an expert), support vector regression is better in almost every case.

From my experience, genetic algorithms are cool for finding unsuspected solutions to a problem, and many various solutions... not exactly the best way to find the BEST solution reliably. I think you could take advantage of this with your tool is to look at a longer target and the result would be a handful of optimal solutions that the player could choose between in the early-game based on scouting, etc.

StimCraft United States. October 13 2010 12:22. Posts 136

Profile #

Would be MUCH more effective for toss or terran. Otherwise, nice job.

Last edit: 2010-10-13 12:22:51

kidcrash89 October 13 2010 12:22. Posts 198

Profile #

As other have said, you've pretty much built it before I have. These models are theoretical at best and have errors in applicability. If anything, releasing the program will add more depth to the game because players would be thinking at much more complicated levels. Theory does not consider every possible map, nor does it scout for you or protect you from harass. If anything, releasing the program will allow more players to think of starcraft truly as a game of strategy, and could lead to great balance changes in the future. Ultimately, getting 7 roaches as fast as you can is great and all, but it doesn't help you if the other player knows how to counter that. Also, this method could easily be exploited by figuring out when the exact time you need to scout the build is. If people started doing this, then you start having people trying to find builds which won't reveal too much too soon. Seems pretty cool to me. To be honest, I'm more interested in learning from your code than anything else as I hope to go to grad school to study algorithms.

Also, will this consider the option of early expanding? In other words, suppose this were a terran/marine simulator, could it instruct you to make additional barracks? Funny how looking at this from Zerg's perspective actually seems (I could be wrong) to make things LESS complicated, while a problem I approached regarding how many workers are needed to sustain any certain build showed that Zerg's methodology was more complicated.

Last edit: 2010-10-13 12:41:13

kevmo United States. October 13 2010 12:36. Posts 38

Profile #

On October 13 2010 12:09 BladeRunner wrote:
I have a friend who's a genius at CS, worked on the AI they put in robots sent to the moon, and I've had many interesting conversations with him about Machine Learning (a topic he is quite interested in). I, being a meer CS bachelor's degree holder was of course familiar with genetic algorithms, but I learned by talking to him that they're widely considered suboptimal to experts in the field.. They tend to get stuck on local maxima/minima.

According to him (and unfortunately I can't really back this up as I'm not an expert), support vector regression is better in almost every case.

From my experience, genetic algorithms are cool for finding unsuspected solutions to a problem, and many various solutions... not exactly the best way to find the BEST solution reliably. I think you could take advantage of this with your tool is to look at a longer target and the result would be a handful of optimal solutions that the player could choose between in the early-game based on scouting, etc.

Support vector machines are used for classification problems (given an input and a set of data, produce a function which most reliably predicts that data). Genetic algorithms are used for search problems (given a solution space, find the "best" solution for some definition of best).

That said, genetic algorithms usually are not the best solution for a given search problem. The advantage lies in the ease of implementation, as well as general applicability. Essentially, I consider genetic algorithm the go to algorithm when you don't really know a better way to solve a search problem. Often in complicated problems (such as build order optimization) genetic algorithms are a good way to get something working.

I obviously don't know the details of the OP's implementation, but there are possibly optimizations to be done even with genetic algorithms. For instance, you can prune solutions early that don't meet certain easily calculable metrics. The easiest are required buildings/units for a given set of goals. In the 7 roach example, you know that you will need at the LEAST a spawning pool, roach warren, extractor, 1 overlord (because 6 drones - 3 for buildings + 14 supply of roaches = 17 supply), and 7 roaches in the build. Any build that does not contain these items simply is not valid, and does not need to be considered as a solution. Furthermore, you can probably speed up evaluation with some simple formulas based on required minerals. For example, you know you need a certain amount of minerals and gas to get all the required buildings and units, and there are easy heuristics for computing payoff time for building workers. Using these numbers, it should be easy to prune off say, a 6 pool as being clearly inferior to a 7 pool, etc.

In terms of implementation, the latter optimization can be thought of as keeping track of the best builds you have seen so far, and immediately rejecting anything that is slower by a certain margin using simple heuristics (e.g. I have seen 7 roaches in 5:00 so starting my spawning pool at 4:30 is clearly not going to be any better). This would involve finding any critical paths and resource requirements for a given goal, but that can be precomputed once and then used over and over again as you evaluate solutions.

voss Australia. October 13 2010 12:36. Posts 144

Profile Blog #

Question for you Lomilar: Is it possible to input multiple requirements? Or is it just limited to X number of Y units in fastest possible?

example: I want to get out 10 roaches, 4 zerglings, 2 infestors and a hatchery in the shortest time possible. Is this a valid input to your optimizer?

Lomilar United States. October 13 2010 12:40. Posts 130

Profile #

On October 13 2010 12:36 voss wrote:
Question for you Lomilar: Is it possible to input multiple requirements? Or is it just limited to X number of Y units in fastest possible?

example: I want to get out 10 roaches, 4 zerglings, 2 infestors and a hatchery in the shortest time possible. Is this a valid input to your optimizer?

Yes.

OwlFeet October 13 2010 12:45. Posts 75

Profile Blog #

I bet Blizzard already does this to check for obvious rush problems

voss Australia. October 13 2010 12:49. Posts 144

Profile Blog #

On October 13 2010 12:40 Lomilar wrote:

Show nested quote +

Yes.

Impressive.

In order to maintain a decent economy, can you specify a number of drones? - how does this incorperate with this current amount of drones? Will it factor in the increased resources that come with these drones? Does it factor in oversaturation (pretty hard to do I guess)

example: I want to get out 10 roaches, 4 zerglings, 2 infestors, a hatchery, and 30 drones.

Will these 30 drones be factored in to the income rate? Will it add 30 drones to the amount of drones in the previous example (10 roaches, 4 zerglings, 2 infestors and a hatchery)? Or will it count the amount of drones from before (if this makes sense)?

1 More question: is it possible to put a higher priority on certain units: - using the previous example; obviously getting the 30 drones out first would result in the fastest time, but it would be unrealistically unsafe. So could you put priority (or something) on the 10 roaches some how?

evanthebouncy! United States. October 13 2010 12:51. Posts 10736

Profile Blog #

sure go for it. :D

Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!

BishopXIV United States. October 13 2010 12:59. Posts 19

Profile #

this is cool 7 roaches in 4:40 hmmm.....

Please enter the above text in the field to prove you are not a robot. You can refresh the image if it's too hard to read. - teamliquid.net/mytlnet/register.php