|
Towards a good StarCraft bot - Part 1 - "Economy (2/2)"
Summary:
+ Show Spoiler +We examine StarCraft economy from a dynamic perspective: how does the income curve over time look like? This is important because it determines the Production Possibilities Frontier discussed in the previous post. The post concludes with a formula to calculate maximum available income at any time in the game for one base.
Previously, we examined the Production Possibilities Frontier statically, given Income = (mineral, gas). Now we add time to the equation. The question we want to answer is: “What is the maximum amount of minerals mined possible at any given time?”
Again, we will start as simple as possible and gradually work towards a complete model.
only SCVs on one base, unlimited supply, assuming a constant mining rate of 1 mineral per second per SCV
The graph below shows the maximum amount of minerals possible for the first two minutes of the game. The general behavior is as follows: 1 additional SCV lowers the income by 50 at the time it is produced. The increased mining rate then kicks in 15 seconds later, leading to a steeper curve for the rest of the time.
![[image loading]](http://i.imgur.com/4NEmwj5.jpg)
As can be observed, to obtain the maximum income up to the 65 seconds mark, the best strategy is not to produce any additional SCVs apart from the first 4. This is because it takes 15 seconds for a worker to be trained and an additional 50 seconds for it to recuperate its own investment.
General formula for n SCVs:
Income_t = 250 – n * 50 + t * 4 + (t-15) + (t-30) + … + (t-(n-4)*15)
Even more general:
Income_t = Income_0 – n * c + t * a + (t-b) + (t-2*b)+…+(t-(n-a)*b)
Which can be written as:
Income_t = Income_0 – nc + ta + ∑_x=a..n [ t-(x-a)b ]
Where:
Income_0: Income at start of the game (50 minerals, or 250 minerals - 200 for the 4 SCVs)
c: mineral cost of SCV
b: build time of SCV
a: SCVs at time 0 (4 starting SCVs)
In real games, supply is not unlimited but has a cost. But since exact timings of supply depots are crucial we must first obtain a better estimation of minerals mined per second as a function of number of workers.
Only SCVs on one base, accounting for supply, more precise constant rate of return
In a simple model supply cost can be modelled as follows: Every 8th SCV costs 150 minerals instead of 50. However, this turns out to be too simplistic, because it does not account for lost mining time. A supply depot takes 40 seconds to build. Furthermore, the SCV needs to travel to the construction site.
Approximation: The first SCV needs 6 seconds to travel back and forth. Every additional depot adds 0.25 seconds to that travel time, such that the 24th depot (max supply) requires 12 seconds of travel time.
Whether this approximation is in any way realistic we will verify at a later time.
For the first 10 supply the graph will look exactly like the graph above. The 11th SCV however introduces various changes, because an extra supply depot has to be built. The total mineral cost of this depot is: 100 + (40+6), still assuming constant mineral mining rate of 1 mineral per second per SCV.
This supply depot can be built anywhere from before the first SCV is built to after the 10th SCV is built. Therefore, we need to introduce a first concept of build order.
Generally speaking, due to the nature of the income curve, we want to build the supply depot as late as possible while SCV production is interrupted as little as possible. Thus, we only have to examine building a supply depot at t-40 or later, where t is the time we run out of supply. This translates to building a supply depot at 7, 8, 9, or 10 supply.
The graph below displays income over time for four different build orders. Constructing a supply depot at 7, 8, 9, or 10 supply while producing SCVs with as little interruption as possible up to 11 SCVs. The “no depot” case is shown as reference and stops at 10 SCVs.
![[image loading]](http://i.imgur.com/34nGHTl.jpg)
It turns out that there is hardly any difference between depot at 8 and depot at 9. Depot at 10 is clearly inferior while depot at 7 delays the 8th SCV too much.
The formula, now accounting for supply depots, is extended to:
Income_t = Income_0 - n*cs - n/8(cd+(bd+d)r) + ta + ∑_(x=a..n) [ t-(x-a)bs) r]
Where:
r: mineral mining rate per second per SCV
cs: cost of SCV
cd: cost of depot
bd: time to build depot
bs: time to build SCV
d: travel time required to build depot
Subsequent supply depots are easier to calculate, because we will have a big enough mineral surplus such that we can build them whenever necessary without interrupting SCV production. However, past the 10th SCV another phenomenon comes into play: the rate of returned minerals diminishes for larger number of SCVs.
Only SCVs on one base, accounting for supply, diminishing rate of return
In the above formula, r was a constant factor. Now, we only have to let r depend on n. I will spare you the details, but based on some numbers I pulled from a TL post combined with some magic it just so happens that r = -0.018*n+1.05 gives a decent approximation
+ Show Spoiler +
I guess the final question is: “that’s a lot of theory, but is it any good??”
The answer is: yes, definitely! The chart below displays total gathered minerals using a simple mineral mining algorithm in an actual game (blue) compared to the calculation (orange) for up to 18 workers on one base, as well as the corresponding net mineral values. I would say mission accomplished 
![[image loading]](http://i.imgur.com/xjsO8HV.jpg)
Conclusion:
This post provides the second part necessary to calculate possible army compositions over time, by adding the dynamic view to the static PPF calculation of part 1. It is absolutely necessary to tune different parameters depending on the map, base location, number of mineral patches at base, etc.
A short note on gas: I did not consider gas here, because it should be rather easy to model.
Basically, any gas income comes at a fixed cost (building refinery), then mineral miners can be traded for gas miners for up to 3 workers.
In the next post we will put everything together and predict maximum enemy army size over time. In order to do that, at least two more factors must be considered: expansions, and cost of army as a function of production time (parallel production with multiple production facilities).
Disclaimer:
I had to reformat the formulas manually for the TL post format.
Limitations:
Obviously the most important limitation is the restriction to 1 base.
Furthermore, the calculations are valid only for the map Fighting Spirit, at a spawning location, since it does not account for different number of mineral patches, etc.
A minor issue, easy to solve: when calculating lost mining time due to depot construction, r is held constant. It should actually be calculated dynamically.
The calculations are done for up to 30 SCVs only. It is assumed that the income curve flattens considerably and r can be modeled such that an additional SCV adds almost no value.
Credit:
I cross-checked several numbers with calculations from LetaBot. His data was also used to calculate the approximation for r.
I used http://www.analyzemath.com/parabola/three_points_para_calc.html to calculate the function of r
Edit: simplified r and adjusted coefficient s.t. it hold for up to 30 SCVs
Edit: added sources for calculation of r
|
very cool, looking forward to the next steps!
|
Hello, imp42.
I'm not a fan of your model. First of all, assuming a constant mineral mining rate per SCV is to assume that the mineral patches are spread in a circle about the Command Center. Secondly, the number of mineral patches in the main on FS (and most other competitive maps) is 9. Once the 10th SCV starts to mine, you have to consider the wandering (SCV goes to another mineral patch when another SCV is mining it) and dawdle (two SCVs arrive to a patch at the same time and one mines while the other waits) effects. These will decrease the income rate per added SCV over time, eventually going to 0 as maximum saturation is reached. The graph of mineral mining rate vs. number of SCV's should look like an S. Therefore, your linear model of the diminishing income rate is not justified, especially for 30 SCV's. I'm not sure from what data you concluded that from or why it should be in the shape of a parabola.
Generally speaking, due to the nature of the income curve, we want to build the supply depot as late as possible while SCV production is interrupted as little as possible.
This is quite easy to answer. The first Supply Depot ideally finishes when the 10th SCV is produced because otherwise SCV production is halted. I timed the build times for an SCV and a Supply Depot, and I measured them to be 12.9 seconds and 26.2 seconds, respectively, on the fastest game setting. I'm not sure how you got 15 seconds and 40 seconds, respectively. If these numbers were true, you would see people building the Depot at 7/10 supply The 10th SCV is the 6th produced SCV from the Command Center, so the Depot should be built at about 6(12.9) - 26.2 = 51.2 seconds.
Only SCVs on one base, accounting for supply, diminishing rate of returnIn the above formula, r was a constant factor. Now, we only have to let r depend on n. I will spare you the details, but based on some numbers I pulled from a TL post combined with some magic it just so happens that r = -0.018*n+1.05 gives a decent approximation + Show Spoiler +Ok, actually what I did here was to calculate a parabolic curve through three points of empirically observed rate of returns. Then I simplified away the quadratic term into the linear coefficient
This is completely unacceptable. You weren't shy earlier when you were giving us formulas for the income graph. Why are you getting cold feet now? Rather than giving us some random expression for r, why don't you show us the empirical data you collected? That is, show us in a table how the rate changes for every SCV you send to mine. Why not also give a link to the TL post you referred to?
I guess the final question is: “that’s a lot of theory, but is it any good??”The answer is: yes, definitely! The chart below displays total gathered minerals using a simple mineral mining algorithm (blue) compared to the calculation (orange) for up to 18 workers on one base, as well as the corresponding net mineral values. I would say mission accomplished
What simple mineral mining algorithm are you talking about? Isn't the point of a model to approximate the real mineral mining phenomenon? Why are you comparing it with another model? Compare it with real data.
-Shalashaska_123
|
Shalashaska_123 you made some good points. But I think there also have been some misunderstandings.
Let me address your concerns one by one. But let's get this out of the way first:
The comparison I posted is real data. When I said "simple mining algorithm" I meant a simple implementation for a bot. I actually measured the real mining rates of the bot in a game. My calculations are very very close to the real behavior.
First of all, assuming a constant mineral mining rate per SCV is to assume that the mineral patches are spread in a circle
I do not assume constant mineral mining rate. I just started with a constant rate to make things easier at the beginning. Later I switched to a variable mining rate depending on the number of SCVs.
Secondly, the number of mineral patches in the main on FS (and most other competitive maps) is 9. Once the 10th SCV starts to mine, you have to consider the wandering (SCV goes to another mineral patch when another SCV is mining it) and dawdle (two SCVs arrive to a patch at the same time and one mines while the other waits) effects
yes, this is why r is modeled to represent diminishing rates of return.
I timed the build times for an SCV and a Supply Depot, and I measured them to be 12.9 seconds and 26.2 seconds, respectively, on the fastest game setting. I'm not sure how you got 15 seconds and 40 seconds, respectively.
I referenced my data source in part 1. I got my data from TL wiki.
http://wiki.teamliquid.net/starcraft/Supply_Depot
http://wiki.teamliquid.net/starcraft/SCV
http://wiki.teamliquid.net/starcraft/Game_Speed#Build_Time
What I failed to mention is a small penalty for every produced SCV because of the initial travel time from where it pops to the mineral patches. Also, the build time for the SCV was adjusted on the Wiki during my work. Quite a coincidence that somebody adjusted the value for an 18 years old game just 5 days ago. I will look into this...
This is completely unacceptable. You weren't shy earlier when you were giving us formulas for the income graph. Why are you getting cold feet now? Rather than giving us some random expression for r, why don't you show us the empirical data you collected? That is, show us in a table how the rate changes for every SCV you send to mine. Why not also give a link to the TL post you referred to?
you are right, I somehow thought it was not that important. But I did reference LetaBot and his Excel in the credits.
The post is: http://www.teamliquid.net/forum/brood-war/484849-improving-mineral-gathering-rate-in-brood-war
and the Excel is: http://imgur.com/h9O6wv5
I took three points from the built-in behavior from the Excel to calculate r.
What simple mineral mining algorithm are you talking about? Isn't the point of a model to approximate the real mineral mining phenomenon? Why are you comparing it with another model? Compare it with real data.
As stated at the beginning, the lines labeled as "empirical" (blue and grey line) are real data. That's what "empirical" means. The simple algorithm I used for the bot works as follows:
A new SCV takes into account all mineral patches at the base that have the least amount of workers assigned and then takes the closest.
I hope these additional explanations make the calculations more comprehensible. Else, please get back to me. It could well be that I blundered somewhere. What made me confident was the close correlation with real data.
|
As promised to Shalashaska_123 I looked into the issue with different build times.
I timed the build times for an SCV and a Supply Depot, and I measured them to be 12.9 seconds and 26.2 seconds, respectively, on the fastest game setting
It turns out the SCV build time is approximately 15 seconds on faster and the supply depot takes 40 seconds on normal.
In its current state, TL wiki has inconsistent data.
While the curves for total minerals mined are close to identical, the net curves are a bit off. Wrong build timings might actually be the cause.
As a consequence, I will change all timings to frames rather than seconds and use BWAPI (via bwmirror) as source.
The build time of the SCV in BWAPI is given as 300 frames.
|
On September 10 2016 22:52 imp42 wrote:As promised to Shalashaska_123 I looked into the issue with different build times. Show nested quote +I timed the build times for an SCV and a Supply Depot, and I measured them to be 12.9 seconds and 26.2 seconds, respectively, on the fastest game setting It turns out the SCV build time is approximately 15 seconds on faster and the supply depot takes 40 seconds on normal. In its current state, TL wiki has inconsistent data. While the curves for total minerals mined are close to identical, the net curves are a bit off. Wrong build timings might actually be the cause. As a consequence, I will change all timings to frames rather than seconds and use BWAPI (via bwmirror) as source. The build time of the SCV in BWAPI is given as 300 frames.
Good call on using frames instead, it removes any lag type issues from the equation.
Personally I don't see the issue Shala was having with most of his points. At the end of the day, the objective of a model is to simplify reality and give accurate predictions, which your model demonstrated. That said, on your graphs, a percent error vs time graph would be a lot more useful, since especially in the income graph, your two values are close together, but even a 2-5% difference can make a big impact on certain timings.
As neat as it is mathematically, I don't think it's the right way of going about solving this optimization problem. In your current post you addressed a relatively simple issue, asking when is the best time to build a supply depot. Now I'm not sure how you'll treat problems like ideal time to build an expansion, but I think a more appropriate way to deal with this issue would be Monte Carlo simulations (and defining ranges for values like first depot build time, command center build time, refinery, etc)... Imo it will be difficult for you to treat multiple changing variables, particularly when 1 isn't better than the other in 100% of cases (building a depot at 9 is clearly better than at 10, since at every point in the game, minus some 15-20 second window it's superior).
Anyway, I'm looking forward to seeing your next post, and how you'll treat some of the more complex things. I appreciate your rigorous method, and you are not making assumptions that you're not letting us know about.
|
FiWiFaKi, thanks for your input
on your graphs, a percent error vs time graph would be a lot more useful
what matters to me at the moment is the gross curve. The net curve will show greater error, but that does not matter as long as it does not diverge (which it won't because it's just gross minus minerals spent on buildings and SCVs). The goal atm still is to calculate a reasonable upper bound of enemy army size. A 5% error at the 2 minutes mark is equivalent to the estimate being off by one marine. Up to 30 SCVs / 6.5 minutes the estimate is never off by more than one marine.
Nevertheless, including the percentage and absolute error is definitely a good idea, I will keep it in mind for the future.
As neat as it is mathematically, I don't think it's the right way of going about solving this optimization problem. In your current post you addressed a relatively simple issue, asking when is the best time to build a supply depot. Now I'm not sure how you'll treat problems like ideal time to build an expansion
Here is a hint on how I plan to do it:
the upper bound for expansion time in a real game is infinite (never expand).
the lower bound for expansion time is the earliest possible command center. Since a command center requires 400 minerals, we can simply solve the presented economy equations for 400 minerals and will arrive at @6 (both 5 SCVs and 7 SCVs will take longer to accumulate 400 net minerals).
Once we know the lower bound we can calculate the time the expansion has paid itself off.
This again allows us to formulate a better, more general upper bound depending on the army size goal specified as "army composition at time t".
I need to solve a couple of problems first, like:
- optimal transfer of workers from main to natural
- general formula for parallel army unit production (I already have a nice graph showing cost of x marines depending on production time, if you want them faster it's more expensive due to additionally required barracks)
- calculation of delays introduced by diverging from the maximum mining strategy (sacrificing economy for earlier army)
details will follow!
PS: regarding monte carlo: probably a main advantage of the calculations are that they are so generic. For example, it is quite easy to (statically) calculate optimal SCV to mineral patch assignment for any number of command centers, any number of mineral patches, and any distances between patches and command centers. By "statically" I mean ignoring current positions of SCVs and initial travel time to their assigned patch. Just answering the question "given x SCVs, y command centers at locations l_ci and z patches at locations l_pi, where should each SCV mine?"
|
Hello again, imp42.
Thank you for replying.
Now you know why referencing wiki pages is frowned upon in academia.
I'm still not convinced. I don't know which three points you chose or how you went about calculating r. As far as I'm concerned, your linear model r(n) = 1.05 - 0.018n is bogus and has no evidence to support it. Since I'm curious about this myself, I'll go ahead and do the calculations for everyone to see.
According to LetaBot's post, he produced SCV's from the start of his experiment, built a Depot to continue production to 18 SCV's, and then let them mine until 8000 frames passed. As you said, it's given that 300 frames is the time required to build an SCV (12.9 seconds if I measured it correctly).
Here in this notebook, I create a set of points corresponding to LetaBot's first and second columns in his spreadsheet, (frames, built-in minerals). I stop the data set at 4500 frames because that's when SCV production stops.
![[image loading]](http://i.imgur.com/kZLXaGl.jpg)
![[image loading]](http://i.imgur.com/qxZeSi6.jpg)
Fitting a quadratic curve to this data works out very nicely. I see now why you decided to do this. Now that we have this function, we can use it to calculate r, the mineral mining rate per second per SCV, at any frame. It has a different expression depending on the number of SCV's mining obviously.
![[image loading]](http://i.imgur.com/ox34A0s.jpg)
![[image loading]](http://i.imgur.com/vbN4uPS.jpg)
At the start of the game there are 4 SCV's. In the 300 frames before the 5th SCV spawns, the initial 4 SCV's bring in a total of f[300] - f[0] minerals. We divide this quantity by 12.9 seconds and by 4 to get the units of minerals per SCV per second. When the 5th SCV spawns, there are not enough minerals to build a 6th SCV right away. In fact, it takes about 2 seconds to resume continuous SCV production from here. To convert this to frames, multiply it by the conversion factor, 300/12.9. Therefore, the amount of minerals that the 5 SCV's mine before the 6th one comes out is f[600 + 2*300/12.9] - f[300]. We divide it by (12.9 + 2) seconds and by 5. The 6 SCV's mine f[900 + 2*300/12.9] - f[600 + 2*300/12.9] minerals before the 7th SCV comes out in 12.9 seconds. 7 SCV's will mine for 600 frames or 12.9*2 seconds because the 8th SCV that spawns has to build a Supply Depot. Once the 10th SCV spawns, the Depot will complete and the constructing SCV returns to mine so that there are 10 miners. Computing these expressions, we get
![[image loading]](http://i.imgur.com/JhwMQTU.jpg)
Plotting the mineral rate per second per SCV vs. the SCV count gives
![[image loading]](http://i.imgur.com/YyRxMBL.jpg)
Fitting a linear function to this data gives
![[image loading]](http://i.imgur.com/PbA8EMD.jpg)
Plotting this function with the data
![[image loading]](http://i.imgur.com/TtF1R7m.jpg)
We can calculate the percent error for each n using the formula (|r(n) - g(n)|/g(n)) * 100%, where |x| denotes the absolute value of x. I'm sure I could've done this more cleanly, but this does the job
![[image loading]](http://i.imgur.com/kAJvJ0J.jpg)
![[image loading]](http://i.imgur.com/rzGuI2l.jpg)
Computing these expressions gives the percent error at each n.
![[image loading]](http://i.imgur.com/x6QbDQe.jpg)
If we take a moment to compare your linear model to my calculations, we see that it is off significantly.
![[image loading]](http://i.imgur.com/MgT1nQ7.jpg)
Considering also that you included incorrect Supply Depot and SCV build times into your model, I'm very skeptical that it would give such accurate results as indicated in your graph.
Something else that you haven't explained is the difference between gross income and net income and total income. Gross and net are synonymous to me, so could you please define them?
In your limitations section you say your model works for up to 30 SCV's, but LetaBot's experiment does not support this. In his experiment's description he said he only went up to 18 supply, i.e. 18 SCV's. So how do you know your model is valid for up to n = 30?
Lastly, if I made a mistake somewhere, please let me know. Thanks for reading.
Shalashaska_123
|
First of all, thank you very much for your effort!
As far as I'm concerned, your linear model r(n) = 1.05 - 0.018n is bogus and has no evidence to support it
your own approximation based on the empirical data gives you
9.7 + 0.18x + 0.00005x^2
You will notice the two formulas are quite similar. As mentioned in the OP I simplified away the quadratic term because even for 30 SCVs it only grows to 0.045. While I just ignored it you went ahead and calculated the precise linear fit as 1.17 - 0.023n
The mining rate is initially assumed to be 1 mineral per second. The initial 4 SCVs will mine pretty much perfectly, so r is initially really close to 1 (my formula says 0.978, yours says 1.14).
So for all practical purposes we can say that our formulas differ in the offset. My mining is consistently less efficient than yours. One possible reason could be that I picked just 3 values out of the experimental data to compute the quadratic function. And IIRC I picked them not randomly but at the lower end of the table, in order to more accurately pick up the flattening of the curve (you will notice your first 4 data points do seem a bit off).
I'm very skeptical that it would give such accurate results as indicated in your graph
I looked into that. My own experimental data shows clearly less efficient mining than LetaBots data. This must be due to the chosen map and spawning location. You find my experimental data in the spoiler below.
Something else that you haven't explained is the difference between gross income and net income and total income. Gross and net are synonymous to me, so could you please define them?
"gross" = total income = total minerals mined
"net" = total income - expenditure
expenditure = #SCVs * 50 + #Depots * 100
So how do you know your model is valid for up to n = 30?
I did my own experiment. Here is the data:
+ Show Spoiler +0 0
100 50
200 58
300 82
400 106
500 122
600 154
700 162
800 194
900 202
1000 242
1100 258
1200 290
1300 314
1400 354
1500 370
1600 402
1700 434
1800 466
1900 506
2000 514
2100 570
2200 594
2300 658
2400 682
2500 730
2600 778
2700 826
2800 882
2900 922
3000 970
3100 1026
3200 1074
3300 1122
3400 1170
3500 1218
3600 1258
3700 1322
3800 1370
3900 1434
4000 1482
4100 1546
4200 1602
4300 1642
4400 1698
4500 1754
4600 1818
4700 1866
4800 1922
4900 1986
5000 2034
5100 2114
5200 2178
5300 2250
5400 2306
5500 2378
5600 2450
5700 2506
5800 2578
5900 2642
6000 2706
6100 2770
6200 2842
6300 2898
6400 2970
6500 3026
6600 3106
6700 3162
6800 3250
6900 3298
7000 3378
7100 3426
7200 3506
7300 3570
7400 3642
7500 3706
7600 3778
7700 3850
7800 3922
7900 3994
However:
Even before your accurate calculations, I started to feel uneasy about r, because it's just not sufficient anymore when calculating optimal expansion time including moving workers to the natural. You now gave hard evidence to support that feeling. The best solution is probably to replace r with an actual calculation. This is what I have in mind (and partially implemented):
calculate optimal number of assigned SCVs per patch as: (traveldistance / travelspeed + miningtime) / miningtime
rounding this value down means the mineral patch will be unoccupied for some time
rounding this value up means an SCV will have to wait for the mineral patch to become unoccupied
- traveldistance / travelspeed will have to account for acceleration and slowing down of the SCV.
- mining time is given as 80 frames (this time citing a report rather than a wiki: http://projekter.aau.dk/projekter/files/42685711/report.pdf)
Given a mining algorithm that lets SCVs actually wait at the mineral patch rather than wander this should allow us to eliminate r and replace it with a more accurate calculation.
|
The mining rate is initially assumed to be 1 mineral per second. The initial 4 SCVs will mine pretty much perfectly, so r is initially really close to 1 (my formula says 0.978, yours says 1.14).
So for all practical purposes we can say that our formulas differ in the offset. My mining is consistently less efficient than yours. One possible reason could be that I picked just 3 values out of the experimental data to compute the quadratic function. And IIRC I picked them not randomly but at the lower end of the table, in order to more accurately pick up the flattening of the curve (you will notice your first 4 data points do seem a bit off).
For as long as the mineral field is not oversaturated, the SCV's will mine efficiently, gathering 8 minerals every 7 seconds roughly (mining time plus traveling time). 8/7 is roughly 1.14, so this should be regarded as the correct mineral mining rate for n less than or equal to the number of patches. I assume that the SCV's are rallied straight from the spawn to an available patch, so that could be a reason for the discrepancy observed in LetaBot's data. It's closer to 8 minerals every 8 seconds, or 1 mineral per second as you postulated. I imagine there's a delay before it is sent to mine. My first 5 values for r are fine.
In using a quadratic function to model the function over all n, I disregarded the wandering and dawdle effects that occur in oversaturation. A better model would use a piecewise function for the mineral mining rate--one function to model n less than or equal to M and another to model n greater than M (M being the number of patches in the mineral field).
I did my own experiment. Here is the data:
How did you do the experiment? If you're building 30 SCV's, then your data should go for at least 9000 frames, right?
However:
Even before your accurate calculations, I started to feel uneasy about r, because it's just not sufficient anymore when calculating optimal expansion time including moving workers to the natural. You now gave hard evidence to support that feeling. The best solution is probably to replace r with an actual calculation.
By actual calculation, do you mean a theoretical expression for r? Also, if you watch Terran players do a fast expand build on FS, you'll see they transfer 6 SCV's usually, which leaves about 11 SCV's mining in the main. This makes it so that when 3 SCV's are sent to mine gas, the SCV density (the ratio of SCV's to the number of mineral patches) at each mineral field is equal. As we see from my plot of r vs. n, r drops to about 0.88 when n = 10. It makes sense then that the expansion completes to keep r greater than 1 for as long as possible.
calculate optimal number of assigned SCVs per patch as: (traveldistance / travelspeed + miningtime) / miningtime
This makes sense. In Fastest Possible Maps, where the mineral patch is right next to the Command Center, the travel distance is 0. So only one SCV is needed per patch. And when the time to travel from the mineral patch to the Command Center and back equals the amount of time it takes to mine, then 2 SCV's can mine a patch. Therefore, for mineral patches on competitive maps the value is between 1 and 2.
- traveldistance / travelspeed will have to account for acceleration and slowing down of the SCV.
Hehe, the formula t = x/v only holds for constant speed, i.e. no acceleration. Even if you were to use the Co-Op pathing that LetaBot talked about to do this, you'd still have to measure the distance. I suggest you directly measure the time it takes for SCV's to travel to each mineral patch. This way you won't have to worry about obscure details like acceleration. I wonder if that BWTA add-on that Christensen et al. mentioned in his paper on page 10 could help out with this.
If you take out traveldistance / travelspeed and substitute it with traveltime, you'll have a very useful expression. Computing it for each mineral patch would tell you how far away it is from the Command Center (I would say they'd be in the range of 1.3 to 1.5 on average). Thus, the lower-value patches should be mined first and the higher-value patches mined later.
Which page?
Given a mining algorithm that lets SCVs actually wait at the mineral patch rather than wander this should allow us to eliminate r and replace it with a more accurate calculation.
The r we calculated was for the built-in, default mining AI. Obviously if you want to consider some other mining dynamic, the model will be different. Using a combination of mining algorithms as LetaBot indicated shows that a computer will have more and more minerals vs. a human opponent the longer the game goes on. For what computers lack in decision-making, they make up for in macromanagement ability. It's quite exciting to think about how build orders and army compositions will be affected.
Shalashaska_123
|
My first 5 values for r are fine.
They are correct, yes. What I meant when I said there a bit "off": if you calculate the best fit linear function over only 18 SCVs then those 5 values have a too heavy weight (28%). SCVs 19 through 30 will extrapolate the curve given by SCVs 10 through 18.
I disregarded the wandering and dawdle effects that occur in oversaturation. A better model would use a piecewise function for the mineral mining rate--one function to model n less than or equal to M and another to model n greater than M (M being the number of patches in the mineral field).
I think it's perfectly fine to disregard these effects if we just assume a slightly better mining algorithm than built-in. Which would be something reasonable to do anyways for a bot. This would eliminate the need for a piecewise function. By the way: Another nice side effect of letting M be the patches in the game rather than patches at the main is that it gives a very decent default behavior for distance mining.
By actual calculation, do you mean a theoretical expression for r?
yes
How did you do the experiment? If you're building 30 SCV's, then your data should go for at least 9000 frames, right?
I am training only 26. I provide SCV count as total count, including the starting 4.
I wonder if that BWTA add-on that Christensen et al. mentioned in his paper on page 10 could help out with this.
I rely heavily on BWTA, using BWTA.getGroundDistance(commandCenter, field.mineralField) to compute distances for all patches in the game. Every time a command center finishes I just update with new closest distances.
Hehe, the formula t = x/v only holds for constant speed, i.e. no acceleration
Of course. Should be easy to account for acceleration, I just still don't know the de-acceleration.
Which page?
Chapter 3, page 23 (PDF page 29)
It's quite exciting to think about how build orders and army compositions will be affected.
absolutely!
Btw.: By now we have so many different sub-topics to discuss, any chance we could take this to IRC #BWAPI on freenode?
|
Show nested quote +I disregarded the wandering and dawdle effects that occur in oversaturation. A better model would use a piecewise function for the mineral mining rate--one function to model n less than or equal to M and another to model n greater than M (M being the number of patches in the mineral field). I think it's perfectly fine to disregard these effects if we just assume a slightly better mining algorithm than built-in. Which would be something reasonable to do anyways for a bot. This would eliminate the need for a piecewise function. By the way: Another nice side effect of letting M be the patches in the game rather than patches at the main is that it gives a very decent default behavior for distance mining. yes
Yes, I agree. However, it's important to model the built-in behavior to have a standard to compare any proposed mining algorithm with. In order to do that, the oversaturation phenomena have to be taken into account.
Show nested quote +I wonder if that BWTA add-on that Christensen et al. mentioned in his paper on page 10 could help out with this. I rely heavily on BWTA, using BWTA.getGroundDistance(commandCenter, field.mineralField) to compute distances for all patches in the game. Every time a command center finishes I just update with new closest distances. Show nested quote +Hehe, the formula t = x/v only holds for constant speed, i.e. no acceleration Of course. Should be easy to account for acceleration, I just still don't know the de-acceleration.
Because there are only so many directions a unit on the ground can face, the SCV's will have different accelerations depending on a mineral patch's position relative to the Command Center. Therefore, just because a mineral patch is closer to a Command Center doesn't mean it will result in a faster mining rate (edit: usually this is true, though). For example, if you consider the mineral patch on the bottom of the top left base of Fighting Spirit, an SCV will maintain its maximum speed as it deposits the mineral and heads back to mine. This is not the only mineral patch on the map that does this. At the 6 o' clock position, there's a patch with the same position relative to the Command Center, and the SCV behaves similarly.
Rather than trying to measure distances and figuring out a patch's position relative to the CC to determine an SCV's travel time, I think it would be easier to just measure the time directly with a stopwatch for each patch.
Show nested quote +How did you do the experiment? If you're building 30 SCV's, then your data should go for at least 9000 frames, right? I am training only 26. I provide SCV count as total count, including the starting 4.
How many patches are in the mineral field? And would it be okay to assume the SCV's build the Depots close by so they return to mining right away?
Btw.: By now we have so many different sub-topics to discuss, any chance we could take this to IRC #BWAPI on freenode?
Thanks for the offer. I appreciate it. But right now I want to focus on developing a mathematical model for the mineral mining rate of the built-in mining behavior (a theoretical expression for r). Once it's understood how the mineral mining rate changes when the mineral field becomes oversaturated, we can answer a lot more interesting questions. I don't know how long it'll take me, but I'll let you know when I do. Thanks for inspiring me. And thank you for taking the time to answer my questions and provide references.
Sincerely,
Shalashaska_123
|
|
|
LetaBot, thanks a lot for your source.
It's quite amazing how similar our code looks, from the enumeration for SCV state to the Mineral struct to starting with perfect split, then queuing... Yours is still way more advanced though
BUT: you use "mineralTrick" and "posTrick" (path finding trick). I assume what you do with GetTrickPath is to target a move command behind the mineral in order to get there without slowing down.
I also do that but then I lose 10 frames when issuing the gather command. I just can't explain why? How did you solve this? (I'm using BWAPI 4 with bwmirror 2.5, does that make any difference?)
Edit:
I might have misunderstood how the pathing trick works. In order to touch the mineral patch at full speed and switch right to mining without losing time the SCV has to be able to actually move past the mineral patch. Else it slows down in my tests. So positions 1,2, and 4 in the image below work, because the SCV can move past the patch in the areas indicated by the green circle. But patch 3 does not have such an area, therefore the SCV slows down.
![[image loading]](http://i.imgur.com/acUol5O.jpg)
Is that in line with your observations?
I haven't checked all of your 1912 loc. Do you use your own custom path to move the SCV back to the cc to minimize turns?
|
|
|
|
|
|
EPT
