|Programming||By Shamus||Jun 13, 2013||86 comments|
Hang on a second… A Starcraft post filed under “programming”? What sort of organizational shenanigans are going on here, Shamus? Is this some kind of trick? I’ll tell you: Last week I was pondering the mechanics of a Starcraft II rush. I wound up making the hilarious mistake of assuming it would be an easy thing to analyze with a bit of code.
A “rush” in Starcraft is where you forego building workers, constructing defenses, or expanding. Instead you begin the game by building as many of the most basic army unit as you can in the hopes of crushing your opponent before they have anything on the field. A rush is usually considered an “all in”, because if your initial attack fails then you’ll be at a massive disadvantage. You don’t have many workers, or defenses, or expansions. All you’ve got is this small handful of units. Your opponent will be far more wealthy than you, and will be able to out-spend you over the next five minutes or so.
It’s basically like a trick play in NFL. They’re rare because they’re risky, and the risk intensifies the more often you attempt them. It’s considered a lame, cheesy trick only used by the unskilled, the desperate, or (occasionally) the troll. There’s even a Sexy and I Know It parody song about it that makes fun of the notorious and meme-spawning Zerg rush:
Setting aside the jokes, the memes, the flame wars over game balance, and arguments over race: Just how much is the advantage of rushing, and how far behind will you be if you fail? What’s the damage, in a total numerical sense? How many units will you be ahead, and assuming there’s no game-ending engagement how long will it take for your opponent to pull ahead of you? I’m sure a pro player could intuit the answer just from the sheer volume of games they’ve played, but I wanted to see the breakdown on a chart where the rest of us mortals can visualize it. I so decided to write a little program to figure it out.
The cost of everything is right there in the game: The cost of the buildings, the time to construct them, the cost of the units, etc. It’s just like calculating compound interest, right? Just plug the numbers in and see what it gives you.
About twenty minutes into the project I realized I’d greatly oversimplified the complexity of the problem. About two hours later I realized that even my twenty-minute re-assessment had been overlooking important details. What was supposed to be a quick, slapdash problem wound up taking the better part of a day and at the end I have a very strange bit of code and a graph that may or may not be useful.
But before we look at the data, let’s look at how we get the data.
For the purposes of our test, we’re going to be looking at a series of hypothetical Terran players. Zerg have to worry about larvae spawn rates and Protoss have more expensive units. In the former I’d have an extra layer of complexity to worry about that might obscure the thing I was trying to observe, and in the latter it would give our chart less granularity. So what we’re doing is making a program to simulate a Terran player that will create some number of workers, construct appropriate supply depots, and then build one or more barracks structures that will begin pumping out marines as fast as possible. Also note that in the parlance of the game a barracks is often called a ‘racks. Because two syllable words are for people with too much free time.
Players identify early building strategies by how many workers you have when you begin building your production structures. So an 8-racks means you begin building your first racks once you have 8 workers on the field. (You actually need a supply depot first. I won’t get into it here, but for people familiar with the game I just want to note that I did take that into account.) A 10-racks means you build the barracks once you have 10 workers. You begin the game with six workers, so a 6-racks is the lowest you can go.
We keep the whole thing focused on simple barracks units. We ignore gas and we ignore expanding. This is complicated enough as it is.
The first thing I needed was some basic numbers on how fast you can acquire minerals with a worker. Like everything else in this project, this was less obvious than it seems. In the game, workers walk from the base to the minerals, spend a few seconds chipping away at them, and then walk back to base to deposit them in the “bank” where they can be spent. Repeat. This means that harvesting from nearby mineral patches is very slightly faster than harvesting from distant ones. If another worker is already harvesting from the desired mineral cluster, the worker will move to a free one. If there aren’t any free clusters available, it stands in line and waits its turn. This means that there’s some diminishing returns when you add more workers, and at some point more workers will do nothing to improve the yield.
This is really messy and involves way more complexity than I want in my program. I’m not interested in re-creating the precise movement mechanics of the game itself, and attempting to do so would run the risk of oversimulation. I just want a timer that counts seconds and minerals. I don’t want to have to simulate walking workers and worry about base layout and AI pathing.
Thankfully, someone else did the research for me. This post on Team Liquid gives us the breakdown on how fast the minerals come in. The yield between near and far minerals is narrow enough that we can just use the average. Without getting into the details (read the post if you want the full breakdown) the first 16 workers will each harvest 42 minerals a minute. The next 8 will only yield an additional 18 per minute each. Further workers do nothing but stand in line. So workers 6-16 make 42 MPM. Workers 17-24 make 18 MPM. Workers 25 and above will not speed up yield. (Although, they might still be useful. Workers are needed to make supply depots and barracks, and worker #25 could do that building so the other 24 can keep on mining. This would be a very small gain and would a take a while to pay for itself.)
The first question that seems obvious (but isn’t!) is: How many barracks do I build? If I’m doing a 9-racks, do I need to build one bunker? Or two? Three? If I build too few, then money will pile up and I won’t be as strong as possible. If I build too many, then they’ll sit idle most of the time and the resources spent on the barracks could have just been spent making more marines.
A barracks makes a marine every 25 seconds. Which means a single barracks produces 2.4 marines a minute. A marine costs 50 minerals. So it costs 120 minerals a minute to keep a barracks working at capacity. If I’m doing a 10-racks then I’ll have 10 workers who will bring in 420 minerals per minute. That’s enough to keep 3.5 barracks going. Hm. So what the AI (it does seem less like I’m writing numerical analysis and more like I’m writing AI at this point) will end up with is 4 total barracks. The first three will work continuously and the fourth one will be idle about half the time.
But wait! WHEN do we build these barracks? Let’s say I’ve got 3 racks pumping out marines. My bank has grown up to 150 minerals, which is enough for another racks. Do I build another racks right now? The other three racks are busy now, but what if – a single game tick from now – all three racks finish their current production and their marines all pop out? If I just spend my money on a racks, then marine production will stall for some period of time. Is it better to lose a little output now so I can have more capacity later, or should I focus on making marines and ONLY make additional barracks when I have enough cash that building the barracks won’t interfere with marines? Keep in mind that doing the later is actually really complicated. A barracks takes ages to make. I’d need to look at income, look at how soon the current barracks will complete. I’d need to take into account if this is the final barracks, because it might be worth losing production to get a barracks up UNLESS it’s that last odd barracks that’s going to be idle half the time anyway. And what about…
Wow. This question is more complicated than the original question I was trying to analyze. To keep this problem from getting away from me, I decide to simplify. I have it favor building barracks sooner at the risk of forgoing marine production in the short term. I don’t know if this is optimal, but finding the optimal strategy could take bloody ages and I don’t think I need to. As long as all of my tests use the same strategy we should have a pretty good apples-to-apples comparison.
This is a lot of code. I write a system to run a theoretical base, tracking income, counting off units, and building structures. Then I run into the next problem.
|This is what a 6-racks looks like. We’re two and a half minutes into the game and we’ve got our first marine on the field.|
As I mentioned before, supply is an important concept in the game. You need to build a supply depot for every 8 small units (workers or marines) on the field. A newbie player will forget to build depots until they run into the limit, at which point all production must halt until they can add a depot. It wouldn’t make for a good test if my program made this same mistake. So, when should you build a supply depot? Build it too soon, and you’ll tie up resources that should be spent on pumping out marines. Wait too long, and you’ll get supply blocked. Either way you can choke off production.
Players usually eyeball it at first, and as they master the game the supply depots become a natural part of the rhythm of their build order. But since we need to maximize production to make this test work, we need to build our depots at exactly the right time. It takes 30 seconds to build a depot, so we need to begin building one 30 seconds before we need it.
I don’t want to get too fancy with this, and this can get annoyingly cumbersome if I wanted to be precise. (If I have to start considering partially-built barracks and measuring the time left on current marines I could end up working on this for the next couple of days. It’s not hard code to write, but it’s murderously slow and fiddly to test and once again would complicate something I’m trying to keep as simple as possible.) Thankfully, the time to produce a marine (25) and the time to build a depot (30) are very close. I should be able to look at the number of barracks I have and throw down a supply depot when my supply is that many short of the limit. (Plus one, to give me a slight buffer. Building too soon is better than too late.) If the current supply limit is 19 and I have two racks going, then I should build the depot when (marines + workers + 1) >= 17.
This doesn’t actually work very well. In some cases, the 12-racks might out-perform (say) a 13-racks, both short and long term. That doesn’t make sense.
Eventually I realize that my program is still oversimplifying things. I see that in certain builds, the racks are spending a lot of time idle because the AI is broke. It’s built too many barracks and crippled its production.
It turns out that marines do not cost 50 minerals. Oh, that’s what they cost you up-front at the barracks, but in the long run you also need to account for the depots you’ll be building. A depot supports 8 marines, so each marine is 50 minerals plus 1/8 of a supply depot.
So how much does a depot cost? Well, up-front they cost 100 minerals to build, but remember that a worker must stop harvesting for 30 seconds to build it. (For the sake of my sanity, we’re going to ignore the time it takes the worker to walk over to the building site and walk back when it’s done.) So a depot costs 100 minerals plus it causes you to miss out on 24 units of mineral gathering. The total cost of a depot is 124, divided by 8 marines equals (rounding up) 16 minerals. So the cost of a marine is actually the base 50 plus this extra 16 of sunk costs for a total of 66.
Using this new value, I basically un-kink my production pipelines and all of the builds operate at near maximum capacity. I play a quick game of actual Starcraft 2, and the points of my 6-racks seem to roughly line up with the numbers I’m getting out of my program. As far as mineral values and marine counts, it’s all acceptably within bounds. I don’t guarantee my program is correct, but I’m reasonably sure the values make sense and the rules are being properly enforced. (It’s not spending itself into negative money or building units despite a supply block.) If there are flaws, they’re most likely inefficiencies in my AI and not in the simulation. The values we’re getting should be good enough for the purposes of our analysis.
I have the simulator run various builds and save the unit counts to a CSV file that I can load into Excel. Here is the build for a 6-racks compared to a player that aims for a more reasonable team of 16 workers.
This is the first ten minutes of the game. Our green player was aiming for 16 workers and red was going for a cheesy 6-racks. We see that red gets their first marine at around the 2:20 mark. Green doesn’t get their first marine until a full minute later. Note that it would be foolish for red to charge green’s base right when marine #1 pops out. Green has 13 workers at that point. Workers are terrible in combat, but 13 of them should be able to swarm and kill a single marine with minor losses.
But what if red waits another minute? By 3:20 red has four marines and green has zero. Right at this point in the game, green has finished one barracks and has a single marine in development. At the same time, green is building two more racks, one of which is nearly done and the other is only just started. Still, the rushing player has 4 marines, which should be able to mow down all the green workers. That’s a guaranteed win, right?
It would be, except for this:
It takes anywhere from 30 seconds to a minute to cross the average two-player map. The rushed army of four sets out from their base at 3:20. But by the time they arrive it’s 3:50 and green has 3 units on the field. 4 vs. 3 is still a win for the rushing player in an open fight, but red is likely fighting through a choke point and up a ramp to get into the base. When the fight is over red will have one or two injured marines, and the 16 workers should be able to mop them up. Red’s reinforcements are streaming in, but the rushing player doesn’t have the production capacity to sustain it. Red has two barracks and green has three, with number four on the way. Green has more income and more barracks. There will be minor skirmishes for the next minute or so, at which point the defender will begin to pull ahead and the rusher will never catch up.
You can think of production as a slider between aggression and greed. The sooner you attack, the more aggressive. The later you go, the more greedy you are. Greed will win over aggression in a long game. The trick is that you have to survive long enough for the greed to pay off.
Here is a chart showing a bunch of different builds:
|Click to expand to some kinda readable size.|
One final little bit of data is the chart below, which I generated for debugging purposes but might be kind of interesting to the reader. It shows the efficiency of the simulated builds.
|Build||Marine Count||Average Minerals||Supply Blocked||Production Wasted||Barracks Built|
|6 Workers||31||51||0:00||1:57||2 (2)|
|8 Workers||38||46||0:00||5:52||3 (3)|
|10 Workers||46||61||0:00||1:48||3 (3)|
|12 Workers||51||50||0:00||5:15||4 (4)|
|16 Workers||60||60||0:00||4:14||5 (5)|
|24 Workers||63||67||0:00||2:33||6 (6)|
- Marine count is how many marines the player had on the field after ten minutes.
- Average minerals is how much it had in the bank, on average.
- Time supply blocked. Not a problem now, but during testing I had a lot of trial-and-error figuring out how to avoid this.
- Production wasted is how many seconds the barracks were idle. If there are three barracks and they all sit idle for a single tick, that counts as three seconds of waste. This mostly happens in situations where the player has enough income to support 4.25 barracks and so barracks #5 spends 75% of its time idle.
- How many barracks it built. (How many barracks it planned to build.) These numbers really only apply in shorter tests.
Well, it was a lot of work and in the end we just confirmed what we already knew: Rushing only works because it’s used rarely.
In a real game, people that fall to rushes are usually people who got a little too greedy. Instead of getting out those first couple of marines (or other starter unit) they built upgrade facilities, expanded, and invested too much in technology and too little in defense.
Given that this project was not properly thought out ahead of time, the source for this is pretty rough. Still, the source code is available if you want to mess around with it. It’s a handful of class definitions all crammed into a single .cpp file, because I find it obnoxious when people hand out tiny and self-contained 500 line programs spread over three modules and header files. However, if this project was going to grow beyond this point the next order of business would be some kind of multi-file organization.