Zerg Build Order optimizer.

Current Version: v0023

<0023 update>

Evolution Chamber Hwaiting! Und das uber Evolution Chamber!

That's right boys and girls, we have internationalization!

</0023 update>

It is out! http://code.google.com/p/evolutionchamber

Download Java and get it!

Yes, there will be a toss and terran version. We are in ~~the preliminary~~ advanced stages of making them.

For any non-code related feedback, please email fritley@gmail.com or (if you have a TL account) PM me.

Chat: irc.quakenet.org #EvolutionChamber

----------------

My career is in building learning systems and AI. One day I thought, huh, it looks like Starcraft 2 has a set vocabulary, and the game _is_ deterministic, to a certain point in the game. That means I can write a program that can learn how to perform a build order better, in order to make myself better.

I want to repeat this. I wrote a program that can learn how to optimize a build order.

So what I want to see if I can prove is if my program works, and get feedback on this.

The input is like so. I want to reach a certain point in the game. That point in the game may be 7 roaches. The build order optimizer tells you step by step instructions on how to get there, and then optimizes to become the fastest way to get there.

Here is the output for a 7 roach rush, a build I've used on the ladder to great effect. Note the following:

This is (potentially) the FASTEST way to get 7 roaches. Not to have a good economy and 7 roaches, or 7 roaches and a queen (though as you can see, it thinks a queen is useful), but just 7 roaches.

It is also naive. It uses averages and numbers, it doesn't actually run a drone to the mineral line, or think about how long it takes to run a drone to build a spawning pool. It is a simulator, and is not subject to gas steals, scouting, or anything of that sort.

The way to read this is:
@ -- This is at... so at 0 minutes and 0 seconds, you have
M: Minerals
G: Gas
L: Larvae
Supply: 6.0 of 10
Drone -- build a drone
@1fetc -- ignore. Just an address.

the +1 means the thing has popped at that time. So at 15 seconds, a larva spawned.

The Build Order for fast roaches.
+ Show Spoiler +

Poll: Do you ever think this should see the light of day?

Yes. (1783)

88%

No, and you've just ruined the metagame. (134)

7%

No. (100)

5%

2017 total votes

Your vote: Do you ever think this should see the light of day?

(Vote): Yes.
(Vote): No.
(Vote): No, and you've just ruined the metagame.

Poll: What flavor would you like to see the build order optimizer in?

Runnable Application. I want to use my awesome computer for personal gain! (1164)

62%

Web Application. I want it to be the easiest thing to use, don't care if it is slow. (461)

25%

Android Application. I want to do it at work. Discreetly. In the bathroom. (167)

9%

Distributed Program. I don't care if it takes a while to get out, I want community support! (73)

4%

1865 total votes

Your vote: What flavor would you like to see the build order optimizer in?

(Vote): Runnable Application. I want to use my awesome computer for personal gain!
(Vote): Web Application. I want it to be the easiest thing to use, don't care if it is slow.
(Vote): Distributed Program. I don't care if it takes a while to get out, I want community support!
(Vote): Android Application. I want to do it at work. Discreetly. In the bathroom.

Descriptions are here.

Last edit: 2010-12-15 12:28:15

iSTime October 13 2010 09:01. Posts 1574

Profile #

That's very interesting, though it'd be about 150x better if it could account for scouting on whatever number you scout on/required movement of workers.

www.infinityseven.net

Lomilar United States. October 13 2010 09:03. Posts 130

Profile #

I just use the digits provided by Liquipedia on their mineral/gas mining page. I could add arbitrary delays for things like moving a drone to build a building, but considering you can move a drone into position right within the time it takes to mine, that is mostly a moot point.

As for scouting, I thought about removing a drone at some scouting time, but eh. That's fine. If I make a real application out of this, it will definitely have the ability to do that.

I also don't have an option yet to pull workers out of gas, but again, that's not hard.

Last edit: 2010-10-13 09:04:44

Broodlings United States. October 13 2010 09:05. Posts 148

Profile Blog #

I don't understand whats so wrong about this. And just because you don't release it eventually someone will, if it is effective as you say it is.

There is no Karont3 icon???? what is this madness?

Lomilar United States. October 13 2010 09:07. Posts 130

Profile #

Part of 'playing the game' over the long term is figuring out build orders. If I want 20 roaches and 10 hydras, this can give me a definitive answer as to the best way to get that, so I don't have to play 30 or so games, working and smoothing out the build order.

That's the danger. It is a significant advantage.

Goobus Hong Kong. October 13 2010 09:07. Posts 581

Profile #

I don't see where the "moral problem" is here. This is merely a tool, it's not like it can play the game for you. With this kind of program SC2 can advance so much quicker than it has in the past, without the need to test build orders. For example, nobody would've guessed that an overpool/15 extractor would be the fastest way to get 7 roaches out.

EDIT: Is there a way to input multiple "goals" for the program? (i.e. get 7 Roaches and 1 set of Zerglings)

Last edit: 2010-10-13 09:09:19

Crazypyro1 United States. October 13 2010 09:09. Posts 418

Profile #

Can the program understand the advantages of a fast expo, if so, how much is that "worth"? And is there a certain number of drones you must maynard for the build order to work with the estimated worth of the expo?

Lomilar United States. October 13 2010 09:11. Posts 130

Profile #

Yes. It can tell you when to expo.

Right now, it assumes the available number of mineral patches is based on the number of hatcheries you have, same with gas, and that the workers are distributed evenly. A flaw right now is that it assumes the workers are maynarded over instantly, with no mineral time lost. That is going on the list of things to fix.

And how much is it worth? Well, it depends what your goal is. The bigger the goal (50 roaches, or just 20 zerglings) the longer it takes to achieve, so it accounts for building an expo in the former, but not the latter, because it is faster to do the latter with just a queen.

You can require it also to build an expo. So 7 roach fast expand could be a possible build for it to crunch.

I can also chain these builds together. So 7 roach to fast muta, find the best way to do that.

Last edit: 2010-10-13 09:14:20

flowandebb Canada. October 13 2010 09:14. Posts 155

Profile #

10 pool isn't even THAT much of an economic disadvantage.

Edit: It seems to have a problem with overlords in my opinion. Always gets them when it is supply capped. I don't think thats optimal?

Last edit: 2010-10-13 09:19:23

Dromar United States. October 13 2010 09:17. Posts 1777

Profile Blog #

On October 13 2010 08:58 Lomilar wrote:
It is a simulator, and is not subject to gas steals, scouting, or anything of that sort.

Sounds cool, but it sounds like it only computes the fastest way to do something you already know you want to do (which btw isn't even the best way necessarily). As long as the above is true, I don't think you need to worry about any moral dilemma.

gamecreator United States. October 13 2010 09:21. Posts 24

Profile #

It sounds like it's blind and deaf but smart otherwise. In other words, it'll get you the fastest Mutalisk but it won't care that the enemy is attacking you with Marines and you need Zerglings now.

But yeah, feel free to release it. And make one for Protoss and Terran when you can. I'm impressed it considers expansions as well. If this program was somehow combined with the map analyzer, it would be that much more powerful.

Last edit: 2010-10-13 09:23:13

RifleCow Canada. October 13 2010 09:21. Posts 553

Profile #

I think in order for this to work beyond cheese you would have to input a few things. Like tell it to get up another hatchery, 35 drones, 2 spines, 4 zerglings, and 2 roaches then lair. Oh yea, and the zerglings and the roaches have to come out before the first hellion harrass. Knowing the fastest way to do this would be something useful. Can you program this?

hohoho

Fa1nT United States. October 13 2010 09:22. Posts 3423

Profile #

The fastest way to do something is still the fastest way to do something.

If you are following this, but say a probe kills a drone, you will be behind a few seconds, but it still is probably the most efficient way.

Lomilar United States. October 13 2010 09:23. Posts 130

Profile #

On October 13 2010 09:14 flowandebb wrote:
...
Edit: It seems to have a problem with overlords in my opinion. Always gets them when it is supply capped. I don't think thats optimal?

I didn't think that was optimal either, but if you think about it, an overpool means you start the pool while waiting for the overlord to pop, maximizing the number of minerals from 10 drones instead of 9 (and pretty early too, necessary for fast roaches), and the 2 overlords while waiting for the roach warren to pop also makes sense, since you want the supply right when you build the 7 roaches from when the queen larva pop.

PLEASE! If you can post a replay of you getting close to this time or beating it with a build order, I want to know.

But yes, a lot of things seem counter-intuitive, but run the build a few times, and it starts to make more sense.

Last edit: 2010-10-13 09:24:21

Qzy Denmark. October 13 2010 09:24. Posts 1121

Profile Blog #

Easy to make

so just release it. It's a constraint problem, easily solved by a simple search - not like most programmers can't do it.

The problem is not "how fast can i make 10 battlecruisers!" The problem is: How can i sustain a good economy, and yet being able to fend off his army...

The algorithm can't solve that.

Last edit: 2010-10-13 09:29:25

TG Sambo... Intel classic! Life of lively to live to life of full life thx to shield battery

tsuxiit October 13 2010 09:24. Posts 1274

Profile #

...I somehow doubt this program is as impressive as you claim.

Say you told it you wanted to make 50 hydralisks. There are an extreme number of variables in that equation; when do larva start to appear at a new expansion? When can a queen get there? Should you expand 3 times as soon as possible or delay them? If so, by how much? I mean, how does your program possibly determine and optimize hundreds of precise timings? Does your claim that it 'learns' just mean that it gives you limited information as to how to 'optimize' a build once you already execute it?

Last edit: 2010-10-13 09:24:48

Redunzl October 13 2010 09:26. Posts 861

Profile Blog #

Release the hounds....

Lomilar United States. October 13 2010 09:28. Posts 130

Profile #

On October 13 2010 09:24 tsuxiit wrote:
...I somehow doubt this program is as impressive as you claim.

Say you told it you wanted to make 50 hydralisks. There are an extreme number of variables in that equation; when do larva start to appear at a new expansion? When can a queen get there? Should you expand 3 times as soon as possible or delay them? If so, by how much? I mean, how does your program possibly determine and optimize hundreds of precise timings? Does your claim that it 'learns' just mean that it gives you limited information as to how to 'optimize' a build once you already execute it?

Give me a desired build. Something like, the fastest way to some mutalisks, or something like that.

There are indeed an extreme number of variables in that equation. I have programmed some tricks in there, such as waiting for a building to pop before doing anything more. I haven't done others, like building a second queen at your main while waiting for your expo.

My claim is, you give me a desired destination (10 lings, 5 roaches, 7 mutalisks), and within an hour or two, or maybe less, I will give you a build like the above, telling you how to do it very quickly.

VelRa_G Canada. October 13 2010 09:28. Posts 265

Profile Blog #

I don't think by any means that this would be a detriment to the SC2 community. No one plays like a robot, and unexpected things happen in games because each game is emergent and dynamic.This just allows players to skip the hardest part of advancing the metagame, figuring out correct timings to optimize their builds! This program could very well be the death of many strategies and the birth of many more fruitful ones.

Nuda Veritas

FrostedMiniWeet United States. October 13 2010 09:29. Posts 636

Profile #

I was actually considering writing a similar program. This won't change much in the gaming scene however, as the game gets too dynamic as it goes on, but it may provide some clever builds. I'm curious what function you used to determine the effectiveness of drone mining, as there is diminishing returns for each drone as you approach 3 drones per patch.