The hard part of the problem isn't to state that build order optimization can be reduced to a TSP problem (which can be solved by existing libraries). The hard part is to define the reduction of, let's say the StarCraft rules, to a TSP problem! And when the rules change or when you want to apply it to a different game, what then? Rewrite the whole thing?
And if you want to expand the rule set to allow complex goal statements with AND/OR statements, locations or dynamic events the whole model will blow up in your face ;-)

Myself I wrote a generic rule processor that deals with any type of strategy game, combined with a fast job scheduler based on evolutionary algorithms, I bet that this is the best approach

We will see when I'm finished.

Ualaa

Canada2 Posts

May 22 2011 08:41 GMT

#1123

A big thank you to the team working on this.

I am wondering if I am using Waypoints correctly.

First I run, a Final: 4 Zergling + 2 Bases + 2 Spine Crawlers.
It finds a 3m 45s build, almost immediately.

Then I run a Final: As above, but add in 2 Queens.
Again, in 10sec or less it finds a solution that is just under 5 minutes.

I set the Waypoint 0 to 4.0 minutes.
With 4 Zergling, 2 Bases and 2 Spine Crawlers.

I set the Final to 5.0 minutes.
With 4 Zerglings, 2 Bases, 2 Spine Crawlers and 2 Queens.

It has been running for over 30 minutes.
The stats show just over 36 million games.
But it cannot meet the Waypoint of 4 minutes, so has no solutions.
This for a waypoint which was done in 3:45, in my first run which took under 15 seconds to find.

Am I using Waypoints correctly?

MaxwellE

England229 Posts

May 22 2011 08:49 GMT

#1124

Might be that there is simply no solution to that. Getting both of these requires more time than getting them individually. Try setting the 2 queen waypoint to something like 5:30, or you can run the 4ling/2base/2spine/2queens and see at what time approximately your lings bases and spines finish so you can see a proper waypoint.

E: I just tried it and lings finish slightly after 4 minutes and spines finish at 4:30, your waypoints are impossible.

Ualaa

Canada2 Posts

May 22 2011 08:56 GMT

#1125

Thanks, I will try that.
Had not thought of it like that before.

Just because it can have 4/2/2/0 at 3:45.
And 4/2/2/2 at 4:49.

Does not mean it can meet the requirement of 4/2/2/2 in 5 minutes, with the added requirement of 4/2/2/0 at the 4 minute mark of the same game.

As I type this...
Giving it 6 minutes for the final build, resulted in a 5m19s solution within 3 seconds of running.

cpu

102 Posts

May 22 2011 09:39 GMT

#1126

Hi,

Sorry if this has already been answered I am new to this thread.

Is there any way to account for larva inject ?

cpu

102 Posts

May 22 2011 09:41 GMT

#1127

Sorry again for dbl posting can you account for removing drones from gas after a certain point ?

FreejaN

Slovakia26 Posts

July 02 2011 17:24 GMT

#1128

Are you going to make a new one for HotS too? I really broke the metagame in my division :D (Master 1500) want to continue

MrAverage

19 Posts

July 08 2011 05:21 GMT

#1129

Is this being as silly as I think it is?

@1:00 M:80 G:0 L:2 S

/10 Extractor Trick
@1:00 M:55 G:0 L:2 S:8/10 Build Drone
@1:02 Spawned: Extractor Trick Finished, Drone Restored
@1:02 Spawned: @Hatchery #1 Larva +1

Looks to me like it's extractor tricking at 9 supply instead of 10?

Shouldn't it only consider an extractor trick if supply blocked?

Shiladie

Canada1631 Posts

August 09 2011 18:30 GMT

#1130

On July 08 2011 14:21 MrAverage wrote:
Is this being as silly as I think it is?

@1:00 M:80 G:0 L:2 S

I was having a problem where it extractor tricked 4 times in a row without actually taking advantage from it. I ended up just unchecking use extractor trick to get it past that.

KoiKe-

Canada24 Posts

August 09 2011 20:00 GMT

#1131

Thanks a lot for this

i can now look for build order and test them while at work

Inters

Canada29 Posts

August 10 2011 07:41 GMT

#1132

i checked the "minimum pool supply" as 11 but it starts testing with a 7 pool... is there a reason for this?

VRage

Belgium13 Posts

August 23 2011 12:30 GMT

#1133

So I play Zerg and usually go with a heavy Roach into Muta style unless scouting gives me cause to build lings.

After two weeks of attempting the build I got the closest I have managed to this time of 4:40 with 4:47 (Slightly different build order - but I also have lair underway for muta switch) - I used as a basis for my build develpoment and have to say it was a great starting point. Also great to know how far off "optimal"an opening is. (For the added long game potential of my minor adjustment I am happy to lose the 7 seconds)

Knowing a build order does not guarentee delivery of the build by the said time - that implementation still takes some skill especially if scouting also.

I doubt many players could hit the 4:40 on the nose - id like to know if anyone managed it

anarkandi

Sweden48 Posts

August 23 2011 12:43 GMT

#1134

Consider trying to add the extractor trick into the equation, it might actually make a big difference.

Belial88

United States5217 Posts

February 16 2012 01:10 GMT

#1135

Hey, so I was interested in using this to figure out when to best take a fast third (like 3 base vs FFE, is it best to make 3rd at 30 supply? 20 supply? 35 supply?)

How do I tell the system "I want the most drones possible at 8:00, with 3 bases"?

I'm also a bit confused on the overlords too.

Belial88

United States5217 Posts

February 23 2012 22:03 GMT

#1136

No help?

meadbert

United States681 Posts

February 23 2012 22:11 GMT

#1137

I have a program that does that and I am running it right now.
I am not restricting it to 3 hatcheries though as that is silly.
I am just telling it to maximize drones at 8 mins.

Preliminary "low quality" mode says 3rd Hatch at 26 supply.

Specifically it says:
10 Overlord
15 Hatch
18 Overlord
25 Pool (LOL)
24 Overlord
26 Hatch

There is a build order optimizer elsewhere online where you can have certain checkpoints, so you can tell it that you need to have 4 lings at a certain time and metabolic at a certain time and X number of Roaches ready by 8 mins etc.

EDIT:

High quality mode finished and found a way to make 109 drones by 8 minutes.

9 Overlord
15 Hatchery
17 Overlord
25 Hatchery
25 Overlord
33 Spawning Pool

I will not go into detail from there because this is sort of silly, but basically you end up with 5 Hatcheries, 5 Queens and 109 Drones at 8 minutes.

Belial88

United States5217 Posts

February 24 2012 02:41 GMT

#1138

^ You can tell it to limit it to 3 hatches, and that a spawning pool must be done by 3:00 (14 pool). I think you can tell it to make a 9 overlord in some way too... leave out extractor tricking, for one.

How do you tell it to 'make most drones' though?

You can add 7:00 evo, 7:30 roach warren, too though.

NightElfik

Czech Republic3 Posts

March 17 2012 12:37 GMT

#1139

What i am doing wrong if I am getting nearly always some silly build starts like extractor trick @9 supply:
+ Show Spoiler +

@0:43 M: 79 G:0 L:2 S: 9/10 Extractor Trick
@0:43 M:54 G:0 L:2 S:8/10 Build Drone
@0:45 Spawned: Drone+1
@0:45 Spawned: Extractor Trick Finished, Drone Restored
@0:47 Spawned: @Hatchery #1 Larva +1
@0:52 M: 75 G:0 L:2 S:10/10 Extractor Trick
@0:52 M:50 G:0 L:2 S: 9/10 Build Drone
@0:54 Spawned: Extractor Trick Finished, Drone Restored

or 6 overlord:
+ Show Spoiler +

@0:17 M:102 G:0 L:3 S:6/10 Build Overlord
@0:29 M:50 G:0 L:2 S:6/10 Build Drone
@0:32 Spawned: @Hatchery #1 Larva +1
@0:42 Spawned: Overlord+1

even after very long processing time (hundreds of millions games played)? My goal was just 50 speedlings & nydus.

Belial88

United States5217 Posts

April 13 2012 05:17 GMT

#1140

I still don't exactly understand how to use this.

How do you ask it "I want the most possible X"? Like, I get you can say "i want 7 roaches at 8:00", but what if 8, 9, or 10 is possible? Do you just have to retest it over and over with 7, 8, 9, + until it stops finding a build order, to find a max?

Is there a way to set in a certain build order? Like "most drones possible, but you HAVE to go 9 overlord 14 pool?"?

I know 14 pool is down at 2:00. Can't get it to learn 2:00+65 though for 3:05 finish time, mostly because it confuses 9 overlord. I guess i could just test for hours and let it figure it out on it's own but...