UC Berkeley StarCraft Class, Week 4
Friday, February 20, 2009 at 2:55PM I was not able to attend the week 3 class, but here's the summary of week 4.
Professor Feng started with an analogy of the game Battleship (you know, that game where you say "H2," then the other guy says "You sunk my battleship!") What if you played a game of Battleship where the number of attacks you get per turn is equal to the number of ships you have left, he asked. Feng is pointing out the essential slippery slope nature of the game, that your ability to attack is reduced as you start fall behind (as opposed to many games where your ability to attack is unaffected by falling behind--I wrote about this here).
Perfect Micro
Then we explored the math behind this idea. To make it easier, we considered the damage done between two packs of marines assuming all marines are within range of each other in an idealized situation. One player has N1 marines versus the other player's N2 marines. Assume the first player has perfect micromanagement while the other player has the worst micromanagement possible. In perfect micromanagement, as many of your units as possible deal damage for as long as possible. In other words, you focus fire on a single enemy marine and kill him as soon as possible so that the enemy's damage output is reduced. You then immediately switch to a new marine, focus fire on him to kill, switch targets, and so on. Meanwhile, your opponent is attacking in the worst way possible: he spreads out his damage evenly amongst your marines, not killing any of them (thus allowing you to keep your overall damage per second high while his declines).
If each marine deals D damage per shot, then after volley 1, player 1 dealt N1D damage while player 2 dealt N2D damage. Player 1 killed N1D/K marines where K = the hit points of a marine. Player 2 killed 0 marines though.
After a second volley, player 1 still deals N1D damage and again kills N1D/K marines. Player 2 only has N2 - (N1D/K) marines left though, so he deals (N2 - (N1D/K)D damage and kills 0 marines again.
After m volleys of this, how many marines are left on each side? Player 1 will have the same number of marines he started with (N1) for a long time, then they will all suddenly die at about the same time. This is because the opponent is attacking in the least efficient way possible here, basically keeping player 1's marines alive as long as possible. Calculating player 2's remaining marines is more tricky though. Player 2 will deal this much damage after m volleys:
Summation from 1 to m of (N2 - N1D/Km)D. This solves to mD(N2 - N1(m+1)/2K).
Why does this matter? Perfect macro is not quite possible and even the built-in AI will probably not use the most inefficient attack possible. The point is to see how big the gap is between perfect and worst macro, so we know what kind of relationship we're dealing with. The answer is that the difference in damage dealt is proportional to the SQUARE of m, the number of volleys. You can also think about this as being proportional to the square of the time the battle takes. So the better micro player doesn't get a linear advantage here, he gets the much bigger "squared" advantage. Relationships in the economy of StarCraft have even bigger effects (exponential), but that's for another class.
Population Dynamics
Professor Feng then represented the problem in a simpler(??) way by ignoring the specifics of perfect micro. Instead, imagine we have two groups of units, A and B, and we know the two variables alpha and beta that are the death rates. Alpha is the rate at which A dies because of B and beta is the rate at which B dies because of A. We don't care about exactly every detail of alpha. It might involve micro, or shield regeneration, or distances/ranges, or terrain, and so on. We can actually determine alpha experimentally for specific situations by setting up tests in the game itself.
How much of A is left after time t is a function we'll call A(t). We'll call the initial value of A (at time 0) A0.
A(t) = A0 - integral of (alpha * (B(t))dt. Likewise...
B(t) = B0 - integral of (beta *A(t))dt.
What followed was a bunch of math involving double integrals and such, and I'll omit it here partly because it's too much trouble for me to present math equations here in a readable form, and partly because my notes on the derivation aren't perfect and if there's the tiniest error, I'll have to read a hundred comments about it, even though this isn't my math in the first place. I wish professor Feng had gone through this part more slowly. Even though I'm adept at calculus, it was hard to follow every step in quick, small writing on a whiteboard.
Anyway, the real point is the result of the calculation. A(t) = A0 - alpha*B0 + an integral. That integral is kind of a correction factor. If the battle ends very quickly, then the integral hardly matters at all. If the battle lasts a long time, then the correction factor dominates. Notably, that correction factor has a term of e ^ sqrt(alpha*beta*t). If this math stuff is hurting your head, Feng is trying to demonstrate here exactly how much population dynamics matter on different time scales.
On a time scale of 1 or 2 seconds, they don't really matter at all. The integral might as well not be there.
On a time scale of 10 or 15 seconds, the importance of the death rate (from micro, terrain, etc) is much higher.
On a time scale of 40 seconds (a long battle), it's extremely important. The correction factor is huge and dominates the calculation.
Examples
Feng then showed us two gameplay examples. In the first example, both Protoss players had large armies and started a battle. One player used his Arbiters' statis abilities to take many enemy units out of the battle temporarily (this included the enemy Arbiters, nice). The victim's death rate was now reduced a lot. There were a lot of units involved here, so the time scale of the battle was large. We saw how big of an effect this was, as the victim's remaining units got cut to shreds, then when the smaller force of statis'd units recovered, they got cut to shreds as well.
In another example from that same game, both players again had a lot of units on the verge of a battle. Here, one player was moving his units and the other attacking during this troop movement. The effect was that the player on the move had too many units that were too far away from the action and so his death rate (his ability to deal actual damage in a battle) was pretty low. The point here is that even when your troops show up after a few seconds, you're already sunk. Those were too many seconds where you took lots of damage without dealing enough back, which puts you behind, which spirals out of control. The longer the battle (because it involves more units), the bigger the disaster is.
Flux
This brings us to the concept of flux, the measure of how much your forces are actually able to deal damage. In English, it's the ratio of your "usefully attacking guys" to "all your guys" in a battle. For example, if you send 48 zerglings to attack a choke point that is blocked by 3 zealots, your flux is very low. You have a few few zerglings in front dealing damage while forty-something zerglings behind run around uselessly.
Another simple example is to imagine the enemy has a ranged units in a broad horizontal line formation, waiting for you. Your forces are above, and you move them directly down, single file, to meet this line. Your flux is terrible because your guys probably die one by one as they come in contact with many simultaneous hits from the enemy formation (it has much better flux).
Then Lore, a player who trained Professor Feng earlier in his gaming carreer took over the lecture for a while. He plays Zerg and talked about the mobility of Zerg. He said that if you look at the APM (actions per minute) of a match, and break down where all those actions are going, the Zerg use more actions on moving than the other races. Lore says this is partly because their units are weak and die relatively quickly, so that makes positioning them that much more important. Also, because Zerg have many (weak) units, it means that they are often getting in each other's way, so that requires more attention on movement. Finally, because Zerg units are so numerous, it's possible to split them up and attack on multiple fronts (more movement).
Lore then showed us a replay of a game he played last week, his Zerg vs. Terran. This replay had many examples of flux. The Zerg player often tried to flank the Terrans so that he could have multiple packs of hydralisks coming from different angles. The idea is that this maximizes the flux because the hydras are all suddenly in attack range, rather than stumbling around behind each other. That said, he often failed to pull of his flanks, but he at least showed us where he tried, and sometimes succeeded.
He had great success in stopping a huge Terran attack using burrow. He burrowed a pack of Hydralisks near his base and unburrowed them when the Terran's huge force was right there. This means that the hydras didn't have to take damage (and die) as they wandered into range. He basically had 100% flux right here, with all the hydras immediately dealing damage. he also happened to get the seige tanks to deal a lot of splash damage to each other because of this positioning.
Another technique he used (in combination with burrow!) was to send 3 overlords full of units on top of the tanks and drop them. This was yet another way to get good flux. His units went from out of combat to suddenly in combat in such a way that every single Zerg unit could immediately attack usefully.
Another instructor then talked about winning with Terran. He emphasized that Seige Tanks are crazily good because they have the longest range in the game. If you "keep the enemy off your tanks, you'll be fine." He also emphasized that Vultures are ridiculously good. He said they are the fastest units in the game, and their 20 damage shot isn't bad, while their ability to lay 3 mines each is amazing. He showed a replay of a game where the Terran player has a ton of tanks and vultures and when a battle happens, he doesn't even use the vultures to attack. Instead he just drives them around in front of the tanks for protection, so the tanks have enough time to kill whatever the threat is.
He also talked a lot about the "big ball" technique. Terrans want to keep their units together in a big ball of death that outranges and kills everything. Tanks + vultures was one example. He also stressed that this takes a while to setup, so before you roll around the map with your big ball, you need to harass the enemy, not to kill him, but to slow him down so that your big ball won't have to fight as much stuff later. Vultures are great at this harassment and you can also use them as part of the big ball itself later, as he showed in the video.
The instructors then joked that we have no time to cover Protoss, "but they are too easy to play anyway."
Conclusion
Professor Feng then closed by saying that the best things to attack as those that don't attack back. Population dynamics and slippery slope are so large, that you would do well to attack things that don't hurt you, so that your remaining force will be overwhelming later. Examples are attacking peons when possible, or supply depots that are out of range of Terran defenses. Zerg are often able to fly Mutalisks around the map, looking for anything that's not defended, and attacking that. Attacking units on the move also qualifies because if you have a large enough force or a large enough advantage in flux, it's possible to kill an enemy group without even losing anything. Just to make up fake numbers, your force of 20 against their force of 5 might not result in you having 15 left. The advantage is so large here that you could end up with 19 or all 20 of your units after killing those 5, so they basically qualify as "attacking something that can't hurt you."
Much of Sun Tzu's advice about when to attack and when not to has to do with these same concept of population dynamics and flux. If have either of those advantages, press them. If you don't, avoid fighting because you'll only lose everything if you do.
Reader Comments (15)
great write up. The zerg instructor who went over that Zerg vs Terran replay in class was me.
This post brought back some memories for me. When I was toying around with the idea of transposing the essential elements of a RTS into a turn-based game, I did a lot of the same math that you mentioned here. I eventually gave up when I realized how valuable a game engine was for simulating these sorts of things, and that requiring players keep up with a bunch of numbers and how to use them wasn't a good idea.
http://www.youtube.com/watch?v=Az27FNRUzBQ
is where you can find the stasis.
Economy in StarCraft is not exponential. Well, obviously it depends on how one plays, e.g. if one never bulids any new workers, the mineral intake (the amount of minerals mined from the beginning up to a point in time) is linear.
But, if one has one base and (as Terran or Protoss) produces workers as fast as possible, the increase in workers (and increase in mineral intake) is constant. That means that the amount of workers grow linearly, and because that is essentially the derivative of the mineral intake, one can conclude that the mineral intake grows quadratically.
The derivative of an exponential function is exponential. Which means that if the economy (mineral intake) really did grow exponentially, the worker production would have to grow exponentially too, which it doesn't.
Of course one can bulid more bases. But that doesn't mean the mineral intake is exponential because that would mean that one would have to increase the number of bases so quickly as to allow for an exponential growth of worker production.
Anyways, saying something about the economy in the long run in a game of StarCraft is hard because matches can be so different.
Also, worker production and expanding cause discontinuities in the real functions that describe the economy, which mean that polynomial or exponential function will just be approximations anyway.
My point is just that one can approximate the mineral intake better with a quadratic or qubic function than with an exponential function. Especially in the (quite common) case of one base and constantly building workers.
Ooops, the increase in workers and increase in mineral intake (second paragraph) is not the same thing, if mineral intake is what I said it was.
The reason they keep saying the growth is exponential is because you start with one base, which builds a second base. Each of those bases can gather the resource of a new base; now you have four bases. Each of those bases builds a base; now there are 8 bases. The number of bases you have is 2^X, where X is the amount of time it takes for one base to gather the resources needed to construct a 2nd base. Granted, this greatly simplifies the construction process of new bases, but the theory is there.
The production of workers at one base is linear, as the amount of workers/minerals you have does not impact how quickly a base can construct new workers. Once you start building more bases (command centers, etc) you get into exponential growth. The total amount of minerals mined by workers at one base is quadratic, but we are dealing with potentially more than one base.
You don't see the exponential growth so often because that plan doesn't survive contact with the enemy -- if the opponent decided to invest in army rather than continuing exponential growth, then you usually have to do the same or get squashed. But sometimes the game does progress in a way that you see it.
For example, the very bad thing about cannon-backed early expand with protoss against zerg is that you advertise your intention not to pressure your opponent -- and the savvy opponent will respond by expanding two or three (or more!) more times, giving you a chance to see just how fast an economy can grow!
A more amusing example was a zerg vs zerg game I once played where we were able to scout each other with our overlords in the first thirty seconds. Both of us knew that 9 pool was a bad idea: the opponent would just 11 hatch 12 pool, giving him maybe two more larvae (thus pulling ahead either in economy or in army), and could still deflect any rush without trouble.
So, both of us expanded to our natural with 11 hatch -- and we had our overlords in place to know that. Both of us knew that 12 pool 14 hatch was a bad idea, because the opponent could 13 hatch 14 pool, and come out with quite a few more larvae, and the ability to deflect any rush.
And so forth; we both played a game of chicken, and as time went on, the penalty for blinking became more and more severe. In the end, he built his spawning pool after the fourth hatchery, at which point the penalty was to be an entire hatchery behind; and he was utterly crushed by my 5 hatch 'ling vs his 4 hatch 'ling.
But after about 3-4 bases worker poduction stops, so this exponential approximation doesn't last very long. And up until then, the rate of increase in workers is much higher than the increase of bases. It makes a quadratic approximation more accurate, I believe.
And one seldom has more than 4-5 expansions with minerals left. That means that if we tried increasing the number of bases in the way you said, Missingno, that would not work beacuse the minerals at each expansion will run out.
Anyway, thank you for pointing out why people say it's exponential. But I still believe a quadratic or cubic function is more accurate, given that the player is not stopped in some way by his opponent. If he is stopped is some way, then both polynomial and exponential approximations will be totally inaccurate. That's one reason why I think the one base example is relevant---that actually happens often. After that (longer into the game) games can look very different.
Well it's clear that your economy can grow at several different rates....
Linearly by not expanding your workers at all (no change in economic growth)
Logarithmically by expanding too many workers at one base (you get diminishing returns if any return at all)
Quadratic/Cubic by increasing your workers at a liner rate (1 expo at a time and only 1 producing workers)
Exponentially by building multiple workers from multiple bases and/or expanding to multiple locations at once.
What rate an economy is growing at any particular moment is going to depend on the gameplay situation. Since the maximum possible growth is exponential it's safe to say that if you give your opponent too much time to expand/eco he's going to expand at an exponential rate for a little while.
It's not enough to just look at the rate of growth in terms of mineral intake, you also need to look at the impact that having sustained mineral intake has on the overall game.
Even a few seconds of having all your peons pulled off the mineral nodes is pretty devastating to your econ, and the effect of that disruption is disproportionate to the amount of time it went on. If you're a bit behind on econ that disparity grows the longer the game goes on as well. It's similar to the correction factor in the A(t) function really, just with a different magnitude.
And it also impacts the A(t) function directly as well, by altering values for A0, alpha and beta. More units, better upgrades, etc, etc. so it has a very large impact on other factors well in excess of the actual change in levels of minerals or gas.
Man i know he was joking, but saying Toss is easy to play is kind of a dumb joke. My main example is TvP. In most games, if Terran win, its like a quick 10-15 minute game that had some vulture harass followed by a siege tank contain outside the toss base.
If toss wins against Terran, it's USUALLY a 30+ minute game. Protoss need more bases to compete with terran, forcing them to expand. Also, it requires obnoxious amounts of harrassment from usually Reavers or high templars, amazing zealot bomb shuttle usage, amazing sense of when to attack the terran ball and when not to, delay from spider mine hunting, useful stasising, perfect storming, etc.
Pretty much what I'm getting at is, for Terran to win, harass early, siege tank contain, GG. For toss to win, harass, tech, expand, zealot bomb, good fight or flight judgment, necessity to stop contains, spider mine hunting, perfect shuttle usage, good arbiter usage. It's almost unfair. Terran are the easiest and best race, and if you don't believe me, look at Boxer, Iloveoov, and Nada. They have by far the most medals of anyone. Bisu is the first Toss to win 4 individual titles, and this happened in 2009. Boxer, Nada and Iloveoov all won 4 titles at around 2004-2005 era. Bullshit, toss isn't easy.
Uh... Protoss IS the easyest to play race (but not the strongest).
Zerg and Terran just need a shitload more APM than toss.
Protoss vs Terran on mid/lower Skill-Level is so hard for the Terran, it's not even funny. And if the Toss really does not want to lose... Proxygate into GG :p.
IMO protoss is the easiest race to pick up and start playing with but at high levels ie pro-gaming each race is equally hard to play as. craNk, Terran and Zerg do NOT need a shit load more apm than protoss does.
Bisu has an average APM higher than 300 while sAviOr even at his prime was never over 300. It all depends on the player and style they play. Not the race.
I'm a nub terran but it doesnt seem harder than any other race really... wall up keep your macro up harass when possible...ball of death :)
@ChoboOv
Uhm... You did not get what i meant.
YOu can play every race very *good* with apm over 150-250..
NOW... Try playing Protoss with 80 APM, then try play Terran or Zerg.... There you will notice a very big diffrence. Protoss is way easyer to controll (less Units, less fragile Units, less abilitys to use/not as micro heavy units (if you don't go reaver).
At progamer level this is not erally an issue anymore, no argument there ^^.