EPTSummary:
+ Show Spoiler +
This post examines StarCraft economy from a static perspective. How much units can be produced given some income in minerals and gas? This is important, because it limits the solution space. The post concludes with a formula to calculate all possible combinations for Terran. It does not take into account time.
Introduction:
Before any attempt is made at creating a good StarCraft bot, we must thoroughly understand the mechanics of the game. Here, I discuss the mechanisms defining what a player can produce given his available resources. To draw an analogy between chess and StarCraft: In chess there are a total of 32 pieces. You start out with 16 pieces each and the number of pieces on the board can only decrease. It is quite easy to teach this knowledge to an AI. But in StarCraft, it is a problem on its own. Units can be produced. Furthermore, what can be produced depends on what has been produced in the past.
In Economics, there is a concept called the “Production Possibilities Frontier”. It defines what a given economy is maximally able to produce in terms of a combination of different goods. Typically, it is illustrated using a two-goods economy and it is assumed that there is a marginal cost per unit because of the law of diminishing returns. That is, each additional unit is worth less than the previous one (if you’re hungry, you might pay 5$ for your first slice of pizza. But probably won’t even want to pay 1$ for the 10th slice, because you are too full). This leads to production possibilities frontiers looking like this:
![[image loading]](http://i.imgur.com/NTFEEJL.jpg)
As can be seen, the depicted economy can either produce 10 computers or 100 books or any combination within the area defined by the border line. If the combination is on the border line it is a maximal production. Examples: 40 books and 6 computers is not maximal, but 60 books and 8 computers is. I both economics and StarCraft we want to be on the border line = on the production possibilities frontier. This translates to having few resources in the bank and producing as many units as possible.
But StarCraft is a bit more complicated than this.
1. There is not one single currency, but two (minerals and gas – there is no way to trade one for the other).
2. There are not two goods, but between 12 and 14, depending on race (counting producible units in Brood War).
3. there is no direct marginal cost. At least not as long as we ignore time.
4. the income we are allowed to spend is not constant, but it 1) increases over time and 2) depends on what we produce (workers increase income, all other units don’t).
As pointed out in part 0 of this series, my approach is to simplify, simplify, simplify. Point 4 is really complicated and probably requires differential equations to solve, so I leave it out for now. furthermore, it is often useful and simpler to focus on the upper bound of economies. An upper bound does not define what you can produce, but it guarantees that it is impossible to produce more than the upper bound.
I start really easy by examining one currency and one unit, no buildings, or supply cost: Just SCVs.
Just SCVs
1. “Given x minerals, how many SCVs can I produce?”
OK, this is really quite easy. An SCV costs 50 minerals. Up to 49 minerals the answer is zero, from 50 to 99 it is one, and so on. Mathematically: round(x / 50). Note that just x / 50 (without rounding) also represents an upper bound, albeit a less precise one.
Anyways, let’s raise the bar just a little bit:
SCVs and vultures
2. “Given x minerals, how many SCVs and / or vultures can I produce?”
The chart for an income of 1000 minerals looks like this:
![[image loading]](http://i.imgur.com/CP0Posp.jpg)
We can produce any combination between 20 SCVs and 13 vultures, as long as we stay on the blue line (i.e. we don’t spend more than 1000 minerals). The reason it looks a bit like a stair is because a vulture costs 1.5x as much as a SCV. It therefore doesn’t matter whether we produce 11 or just 10 SCVs, we still can only produce 6 vultures with the remaining minerals.
Mathematically, we solve x * 50 + y * 75 <= 1000. x = number of SCVs, y = number of vultures
Economically speaking, we can trade 1 vulture for 7/5 SCVs, or the other way around, we can trade 1 SCV for 5/7 vultures.
Still too easy for you? Let’s look at all 13 units then.
All 13 units
Now, it’s not really feasible to plot a graph anymore, since the production space is 13-dimensional. However, fortunately the mathematical equation is still simple:
x1*c1 + x2*c2 + x3*c3 + x4*c4 + x5*c5 + x6*c6 + x7*c7 + x8*c8 + x9*c9 + x10*c10 + x11*c11 + x12*c12 + x13*c13 <= Income
where xi denotes the amount of unit i and ci the cost of the unit i. Income = available minerals.
The result is a valid upper bound that actually applies to the game. However, it is imprecise. The reasons:
- We did not account for production buildings and supply depots
- We did not consider gas cost
So let’s do gas cost first. This simply turns cost and income into a 2-dimensional variable. Instead of cost = 50 we now write cost = (50,0) indicating 50 minerals and 0 gas. Instead of Income = 1000 minerals we now write Income = (m, g).
The constraint above: x1*c1 + … x14 * c14 <= Income must now be written twice. Once for minerals and once for gas.
1) x1*cm1 + … x14 * cm14 <= minerals income
2) x1*cg1 + … x14 * cg14 <= gas income
Now, let’s account for production buildings and supply depots.
a) Production buildings
Production buildings are easy. In economics terms, they just represent a fixed cost, as opposed to the variable cost of the unit. So instead of stating “total cost = number of units * cost of unit” the equation now states “total cost = number of units * cost of unit + fixed cost”
I briefly list the equation for all Terran units considering their technology tree, to not lose touch with StarCraft
Note that I list the cost of a required building on the tech tree only once (lazy...).
List of variable and fixed cost for each Brood War Terran unit, accounting for tech tree requirements:
+ Show Spoiler +
Cost of SCVs = x * (50,0)
Cost of marines = x * (50,0) + (150,0)
requirements: barracks (150,0)
Cost of firebats = x * (50,25) + (300,0)
requirements: barracks, academy (150,0)
Cost of medics = x * (50,25) + (300,0)
requirements: barracks, academy
Cost of ghosts = x * (25,75) + (800,400)
requirements: barracks, factory, starport, academy, science facility, covert ops (50,50)
Cost of Vulture = x * (75,0) + (350,100)
requirements: barracks, factory (200,100)
Cost of Siege tank = x * (150,100) + (400,150)
requirements: barracks, factory, machine shop (50,50)
Cost of Goliath = x * (100,50) + (450,150)
requirements: barracks, factory, armory (100,50)
Cost of Wraith = x * (150,100) + (500,200)
requirements: barracks, factory, starport (150,100)
Cost of Dropship = x * (100,100) + (550,250)
requirements: barracks, factory, starport, control tower (50,50)
Cost of Science Vessel = x * (100,225) + (650,400)
requirements: barracks, factory, starport, control tower, science facility (100,150)
Cost of Battlecruiser = x * (400,300) + (650,400)
requirements: barracks, factory, starport, science facility, physics lab (50,50)
Cost of Valkyrie = x * (250,125) + (650,300)
requirements: barracks, factory, starport, control tower, armory
This list does not account for synergies. The total cost of 1 marine is 200 minerals, the total cost of 1 vulture is 425 minerals and 100 gas. However, the total cost of 1 marine + 1 vulture is 475 minerals and 100 gas, because only 1 barracks is needed.
Cost of marines = x * (50,0) + (150,0)
requirements: barracks (150,0)
Cost of firebats = x * (50,25) + (300,0)
requirements: barracks, academy (150,0)
Cost of medics = x * (50,25) + (300,0)
requirements: barracks, academy
Cost of ghosts = x * (25,75) + (800,400)
requirements: barracks, factory, starport, academy, science facility, covert ops (50,50)
Cost of Vulture = x * (75,0) + (350,100)
requirements: barracks, factory (200,100)
Cost of Siege tank = x * (150,100) + (400,150)
requirements: barracks, factory, machine shop (50,50)
Cost of Goliath = x * (100,50) + (450,150)
requirements: barracks, factory, armory (100,50)
Cost of Wraith = x * (150,100) + (500,200)
requirements: barracks, factory, starport (150,100)
Cost of Dropship = x * (100,100) + (550,250)
requirements: barracks, factory, starport, control tower (50,50)
Cost of Science Vessel = x * (100,225) + (650,400)
requirements: barracks, factory, starport, control tower, science facility (100,150)
Cost of Battlecruiser = x * (400,300) + (650,400)
requirements: barracks, factory, starport, science facility, physics lab (50,50)
Cost of Valkyrie = x * (250,125) + (650,300)
requirements: barracks, factory, starport, control tower, armory
This list does not account for synergies. The total cost of 1 marine is 200 minerals, the total cost of 1 vulture is 425 minerals and 100 gas. However, the total cost of 1 marine + 1 vulture is 475 minerals and 100 gas, because only 1 barracks is needed.
Let's account for supply cost:
b) Supply depots
Supply makes matters worse. Not only do we have to factor in an additional 100 minerals every 8 supply, but now we also have to introduce further constraints and account for supply cost of all units. The mineral cost of supply is supply * 12.5 (supply / 8 depots, costing 100 minerals each).
The additional constraints therefore are:
1) x1*s1 + … x14 * s14 <= max supply, where si is the supply cost of unit i
2) x1*c1 + … x14 * c14 <= income – (x1*s1 + … x14 * s14)*12.5
Note that 2) can be written as x1*(c1+S1*12.5) + … + x14*(c14+S14*12.5) <= income
Let’s wrap it up by stating the final equation for an upper bound of the PPF, considering mineral cost, gas cost, supply cost, and technology tree for Terran units:
Income(minerals,gas) >=
#SCVs * (50+12.5,0) + #marines * (50+12.5,0) + #firebats * (50+12.5,25) + #medics * (50+12.5,25) + #ghosts * (25+12.5,75) + #vultures * (75+25,0) + #siegetanks * (150+25,100) + #goliaths * (100+25,50) + #wraiths * (150+25,100) + #dropships * (100+25,100) + #science vessels * (100+25,225) + #battle cruisers * (400+75,300) + #valkyries * (250+37.5,125) + (1050,600)
Supply constraint:
200 = #SCVs * 1 + #marines * 1 + #firebats * 1 + #medics * 1 + #ghosts * 1 + #vultures * 2 + #siegetanks * 2 + #goliaths * 2 + #wraiths * 2 + #battlecruisers * 6 + #valkyries * 3
Conclusion:
The real challenge in StarCraft economy is the fact, that income increases over time and depends on what has been produced in the past (If I made more SCVs in the past, I will have a larger income now). This post examined the static view only. However, it is a necessary preliminary work for the next post to come, which will examine income over time.
Both concepts together will then allow us to provide a reasonable upper bound of what each player can possible have produced at any given time in the game.
Disclaimer: I double checked numbers, but did calculations manually – there might be some typos
Data was retrieved from http://wiki.teamliquid.net/starcraft/Technology_tree and http://wiki.teamliquid.net/starcraft/Units
