EPTSummary:
+ Show Spoiler +
The earliest possible time to expand is calculated as an intermediate step.
A more precise calculation of the mineral rate r_n for n SCVs at a base location is given.
Then the optimal expansion timing is calculated, based on a given income goal. The actual example uses the income goal "max. minerals long-term (large time t)", which gives a somewhat trivial result. But the calculation holds for actually interesting applications with real income goals. It can be extended to account for delays because of enemy intervention.
“When is the right time to expand?”
The answer to this question depends on our army goal. We can state such a goal as “army composition at time t”. At the moment, we are not concerned with what constitutes a good army goal. Let’s just assume some higher-level decision maker tells us: “I want composition x by time t!” and we are in charge of gathering the necessary resources.
Side note: The price of an army depends on how early it needs to be ready:+ Show Spoiler +
It is noteworthy that the price of an army composition depends on t. This is because lower t requires more parallel production. Parallel production requires additional buildings, which have a cost. I will dedicate a separate post to answer the question “what is the cost of army composition x at time t?”. Here, we consider this question answered and therefore arrive at a simple requirement to produce a certain income by time t, described as Income_t = (minerals, gas)
The following graph illustrates the problem using cc@6 vs 1-base as an example. The yellow and grey curve indicate total minerals mined while the green and blue curve show the net income = total income – expenditure (cost of produced SCVs, depots, command centers).
![[image loading]](http://i.imgur.com/2nompXc.jpg)
The nature of the income curve for one base (gross: grey and net: dark blue) has been examined in a previous post. We only have to consider expanding if the requirement “Income_t” cannot be satisfied on one base. In the above example, this is the case for any income requirements above the blue line. In the above graph, the breakeven of cc@6 compared to 1-base is achieved at the 12400 frame mark. So the question becomes: “at what earliest time is the combined income curve of main and natural higher than the income curve of the main alone?” (gross: intersection of grey and yellow, net: intersection of blue and green).
The answer lies somewhere between the earliest possible expansion and never expanding.
When is the earliest possible time one can expand?
A simple answer would be “by the earliest time we can gather the 400 minerals required to build a command center”. This can be calculated easily with the formula from the previous post and turns out to be @6 supply. So the build order would be “SCV, SCV, CC”.
However, more optimized builds will have an SCV ready at the construction site exactly by the time they hit 400 minerals. This makes things a little more complicated. In particular, we have to account for the distance to the construction site at the natural and the lost mining time during travel.
![[image loading]](http://i.imgur.com/pE65AaS.jpg)
Let’s say we have n SCVs mining at rate r_n each. If we pull an SCV off to send to the construction site, by the time it arrives the remaining n-1 will have gathered (n-1)*(travel time) * r_n-1 minerals. Note that the rate is not the same (r_n != r_n-1) because efficiency decreases with increasing number of SCVs.
Let d be the distance between the main command center and the construction site at the natural (In a real implementation we would probably want to use the SCV closest to the construction site, so d might vary…).
Travel time t_travel = d / V_scv with max(V_scv) = 4.92
A note on SCV speed:+ Show Spoiler +
4.92 is the top speed, but SCVs accelerate, slow down, and lose time when turning. Some empirically measured average should be used or mathematically account for start, stop, and at least two turns.
Let t(y) be the time we have gathered y minerals and choose y such that:
y + (mining during travel) = y + (n-1)( t_travel)r_n-1 = 400.
y = 400 – (n-1)( t_travel)r_n-1 (=the amount of minerals we want before sending SCV to expand)
y = f(t, n) (f being the function for income over time and SCVs from the previous post)
we want to solve f(t, n) = 400 – (n-1)(t_travel)r_n-1
A note on "r" (previously only approximated by a simple function):+ Show Spoiler +
![[image loading]](http://i.imgur.com/K4h80ma.jpg)
Let’s examine some cases:
a) 1 SCV, m = 2, d(p1) = 2*180, d(p2) = 2*230:
t(p1) = 73 frames, saturation(p1) = 1.91, as(p1) = 1, rate(p1) = 1*8 / (73+80) = 0.052 minerals / frame
t(p2) = 93 frames, saturation(p2) = 2.16, as(p2) = 1, rate(p2) = 1*8 / (93+80) = 0.046 minerals / frame
the SCV would mine from patch p1
b) 2 SCVs
assigned(p1) = 2, rate changes to rate(p1) = 1*8 / (80) = 0.1 minerals / frame because assigned(p1) > saturation(p1)
t(p2) remains the same
the second SCV would also mine from patch p1 even though it has to wait for a bit before the mineral patch becomes available. Because: efficiency(p1) = 0.05 while efficiency(p2) = 0.046
c) 3 SCVs
efficiency(p1) changes to 0.034
t(p2) remains the same
the third SCV would mine from patch p2 because efficiency 0.046 > 0.034
and so on…
Let us have a look at expanding @4, @5, @6, @7, assuming 400 frames of travel time (measured on 9 o’clock Lost Temple, where t_travel = 400 frames):
![[image loading]](http://i.imgur.com/onEBgrk.jpg)
Note: The higher “r” at column “5” denotes the mining rate of the 5 SCVs to accumulate 320+50 total minerals (50 minerals were spent on the 5th SCV). The lower “r” denotes the mining rate of the remaining 4 SCVs while one of the 5 was sent to construct the natural.
As can be seen in the table, the earliest possible time to expand, given a travel time to the natural of about 400 frames, is at frame 2054. Unfortunately, this comes at the very high cost of interrupting SCV production for 2054 – (2*300) + 215 = 1669 frames (we stopped at frame 600 and can resume only after having gathered another 50 minerals after command center construction has started, which takes approximately 215 frames given the rate of the remaining 5 workers mining). This is equal to sacrificing about 5.5 SCVs.
What are the total opportunity costs of a natural?
The true cost of expanding to the natural is: cost of command center + lost mining during travel and construction. Lost mining = (400 + 1800) frames at rate 0.045 = 98 minerals. Therefore: 498 minerals.
Furthermore, depending on when the command center is constructed, SCV production at the main is interrupted. We can therefore model the opportunity cost of a command center over time as:
op_cost(Command Center at t) = (mineral cost + lost mining cost) + interruptedScvProduction(t)
What is the benefit of having a natural?
There are two benefits: maximum speed of SCV production is doubled and the mining rate “r” is increased. For example, 30 SCVs in the main can mine about 0.71 minerals / frame. A 15/15 split between main and natural can yield about 2 * 0.65 = 1.3 minerals / frame. Splitting 15/15 comes at a cost of sending 15 SCVs to the natural, which equals to 15*400 frames of lost mining at a rate of r_30 - r_15. Therefore: 6000 * (0.71-0.65) = 360 minerals, which are recuperated within 360/(2*r_15 - r_30) = 610 frames after transfer.
More generally: Splitting n workers into j + k brings a benefit of:
Benefit(splitting into j+k at time t) = t * (r_j + r_k_nat) – t * (r_n) - t_travel * k * (r_n – r_j)
achieving the break even at: t = t_travel * k * (r_n – r_j) / (r_j + r_k_nat - r_n)
Nicer formatting:
+ Show Spoiler +
![[image loading]](http://i.imgur.com/jjGhjDG.jpg)
Note that r_k_nat != r_k_main because r depends on the number and distances of the mineral patches.
It is “comparatively” easy to calculate optimal j and k, given t. If there is no further SCV production and t is infinite, then we can just pick j and k such that (r_j + r_k_nat) is maximized. If we continue to pump out SCVs at both command centers, then we have to account for the fact that we reach max saturation earlier. That is, the advantage diminishes over time due to diminishing rate of return per SCV and reaches 0 once the natural would have reached max saturation without the SCV split.
For practical purposes maximizing (r_j + r_k_nat) should be sufficient, maybe accounting for the fact that we might pull of workers for gas or to construct buildings in the main in the near future.
A quick note on the additional SCV production: a natural that is operational 300 frames earlier yields one additional SCV.
profit(Command Center at t) = benefitSplitting(t) + additionalScvProduction(t)
What is the optimal time to expand?
Simply put:
at the earliest time t such that profit(Command Center at t) > op_cost(Command Center at t)
Maybe it is worthwhile to briefly elaborate why the fastest possible expansion is not the optimal one. Firstly, benefitSplitting(t) is almost negligible when splitting 6 workers into 3 and 3. We’re talking about an advantage of 0.034 minerals / frame and a breakeven of 4200 frames to make up for the lost mining time during travel alone. But more importantly, if the additional SCV production does not make up for the sacrificed SCV production, then it is not worth it. That is, for every SCV sacrificed the command center should be constructed 300 frames earlier to make it profitable.
Let’s look at op_cost(Command Center at t) for SCV 6 through 13, this time calculated, not measured (11-13 SCVs have to produce a supply depot as well):
![[image loading]](http://i.imgur.com/Y52638F.jpg)
I marked two interesting cells yellow. For CC@11 for the first time we will have more than 400 minerals when arriving at the construction site, because the 11th SCV is the limiting factor. The other one: CC@13 is the earliest CC that does not interrupt SCV production anymore.
The curves for profit(Command Center at t) all look similar, except they are shifted to the right for higher t, therefore, no earlier build will ever be able to catch up on a later one, once behind. Hence, the important conclusion is the following: long-term, an earlier command center is only worth it, if it can produce more workers than a later command center. This the case for the first time @13. All earlier command centers are not able to make up for their delayed SCV production before a later command center also starts SCV production. For example: Let’s compare CC@9 and CC@10. CC@10 produces the first SCV after the CC at 2326 frames, which is 137 frames later than CC@9. However, CC@9 interrupts SCV production for 163 more frames than CC@10. So CC@9 will always be behind in SCV production and can never catch up to CC@10.
The final answer: The optimal time to expand on Lost Temple 9 o’clock position, given a large enough time horizon for return on investment, is at 13 supply. A quick cross check with http://wiki.teamliquid.net/starcraft2/CC_First shows that the optimal build for command center first is considered to be cc@14, which is in line with our calculation when accounting for the scouting probe, which is pulled off from mining.
Further expansions:
About further expansions beyond the just the natural: The 3rd expansion behaves in a similar way to the natural expansion. Except for practical purposes we don’t need the same level of detail. A very simple way to approach the problem, probably sufficient for all practical scenarios: Expand to a third if the given income requirement cannot be satisfied on two bases.
Quick refresher: Why do all the complicated calculations when you can just measure / ask a pro player?
The calculations replace expert knowledge and allow an AI to reason. Instead of hard-coding a cc-first build order with cc@13 (which is considered “expert knowledge”: some higher instance just knows it is optimal and tells us so) we can query our system to fulfill a given income requirement the fastest possible way for any map and any mineral patch distances. In a more extreme case, the system could easily deal with a situation where the cost for a command center is increased from 400 to 500 minerals.
Disclaimer:
I had to reformat formulas manually for the TL post format. There might be inconsistencies with the included images.
The calculation for "r" is more exact than the previous approximation, but it systematically calculates more income than measured empirically. This is most likely due to unpredictable SCV movement between main and mineral patch containing unnecessary turns (the measure was done with only 1 SCV in the test).
This means that the calculated earliest time frames may not actually be reached in a real game, nevertheless the calculations remain the same, even if coefficients in the algorithm for "r" will be adjusted in the future.
Limitations:
The empirical tests are naturally done only on one map and must be performed for every map, every location.
The calculation for "r" is much more precise than the previous approximation, but requires exact travel times for SCVs to each mineral patch. These travel times are very hard to calculate because of the somewhat unpredictable behavior of SCVs and the path they choose. As Shalashaska_123 suggested, it is probably better to measure travel time rather than calculating it. I did measure it for Lost Temple 9 o'clock main and natural.
Of course all of this is only accurate as long as there is no enemy intervening with our mining. If an incoming enemy harass is scouted, then we must formulate a very short-term goal to produce defending units. Only when successfully defended we can go back to formulate a more long-term goal and consider expanding. How to account for such delays will be the topic of a future post.
Credit:
Shalashaska_123 for good input on calculation of "r"
Liquipedia for the "CC first" BO
