Starcraft Math: Modeling an Engagement

I've been wanting to use my math background to do a little theoretical analysis of Starcraft for a while now. I just finished my freshman year at UCSD, and as a biochem bio major I don't actually have to take any more math (I just finished the 20 series, for anyone who is curious about specifics), I've always really enjoyed math, and I'm considering minoring in math just for the hell of it. I'd like to start doing some applications with that math to see how well I know it, so I thought I'd start with what should be a relatively simple problem: modeling in general terms the engagement of two armies. Should be fun — and maybe we'll learn something about Starcraft.

We'll begin with a few assumptions:
+ Show Spoiler [Assumptions] +

What I want is a way to express mathematically how an engagement between two armies will go, who will win, and by how much. This is easiest in single unit vs. single unit calculations. These are simple and only tangentially related to the problem at hand, so I'll put them in a spoiler. If you have trouble following the equations, I apologize that I am writing everything out in a text format, with no subscripts, fraction bars, etc.
+ Show Spoiler [Single Unit vs. Single Unit] +

Army engagements are more complex. When two armies engage, not all of the units are necessarily firing; instead, they form arcs of units that oppose each other, and units in the front row of the arc are firing. Once a unit has approached the enemy closely enough to fire at the enemy they stop moving, so units behind them are stuck and cannot fire unless they run around the unit in front of them, thus widening the arc. The widest the unit arc can be is the width of the area they are engaging in. So if two armies engage in a narrow passage which is 5 wide, the largest the arc can be is 5. In calculations I will write arc length as AL.

Note that attack range begins at the edge of a unit's collision radius, not the center of the circle which they occupy.

In the case of units with equal range engaging each other, as for instance an engagement between two armies of marines, the front row and only the front row is firing. This means that if the arc lengths are equal, even if one army is bigger than the other, the trade will still be even. So if 20 marines engage 200 marines in a choke so that neither side has a bigger arc, then at the end of the battle both sides should have lost about 20 marines.

This is approximately the structure of marine vs. marine fights.

If one army has more range than the other, though, then that army can have more than just the front row of units firing while the opposing army only has the front row firing.

This would roughly represent, for instance, roaches firing at marines

The larger the range difference, the more it increases the number of units firing. It would seem from the pictures above that the range difference would have to be equal to 2 collision radii in order to increase the rows firing by one. In fact, this isn't quite accurate; while I did draw it this way, arranging units in rows and columns at right angles to each other is not the most tightly packed formation; the more accurate picture would have each row offset from the other one to take advantage of the space between circles, so the real spacing between rows is approximately sqrt(3) times the collision radius.

This is a more accurate representation of the arrangement of units in a clump.

From this, we can calculate an estimate of how many units will be firing in an engagement between two armies.
+ Show Spoiler [Calculations] +

The conclusion of our calculations was:
Number of units firing is proportional to arc length * range advantage / collision radius squared.

The number of units firing is important when considering how a certain type of unit "scales," or gets better in bigger numbers. If all your units are firing at once, you can do damage faster than an opponent that only has some of their units firing at once. So units scale better with range, and scale worse with collision radius squared. If your whole army isn't firing, you can help fix this by spreading them in a wider arc.

Now that we can calculate how many units are firing in each army, we can calculate the results of two homogeneous armies engaging one another. Let's do a concrete example: suppose 50 marines without stim or combat shield engage 25 roaches, with no upgrades on either side. As before, calculations will be in a spoiler. As before, I apologize for having to write down equations in text format, without fraction bars, subscripts, etc.
+ Show Spoiler [More Calculations] +

50 Marines

HP: 45
DPS: 5.81 (Ordinarily 6.97, but roaches start with 1 armor).
Range: 5
Collision Radius: 0.375

Total HP: 2250

25 Roaches

HP: 145
DPS: 8.00
Range: 4
Collision Radius: 0.625

The damage rate of the marines is equal to number of marines firing * DPS of marines. We'll assume the arc length of the roaches and marines is the same, so we don't need to specify it and can draw a general conclusion. We'll combine this with our other constants to make k, some constant that varies with arc length. Number of marine rows firing equals:

[R(marines) – R(roaches)] / sqrt(3) * CR (marines) = [5 – 4] / 1.732 * .375 = 1.54. Since we always round this number up, we get that 2 rows of marines are firing, while 1 row of roaches is firing.

The number of marines per row is equal to AL / 2 CR(marines) = 1.333 * AL. The number of roaches per row is equal to AL / 2 CR(roaches) = .8 * AL.

This means there are 2.66 * AL marines firing at once since there are two rows, while there are .8 * AL roaches firing from their one row.

Damage rate of marines = DPS(marines) * number of marines firing = 15.45 * AL.
Damage rate of roaches = DPS(roaches) * number of roaches firing = 6.4 * AL.

In other words, for every 45 damage the roaches do, the marines do 108 damage. for every marine that is killed, 3/4 of a roach is killed. Or for every 4 marines that are killed, 3 roaches are killed.

Remember that these calculations only work when both sides are in sufficient numbers that the maximum possible marines and roaches are firing at any given time. So this will apply until there aren't enough marines to fill 2 rows, or there aren't enough roaches to fill one row. This requires us to specify an arc length. Lets choose an arc length of around 3.5, since this is just enough to fit 9 marines or 5 roaches in a row. In this case when we reach 18 marines or 5 roaches, we no longer have enough to fill a row. This happens first to the roaches, at which point 20 roaches and about 27 marines have been killed.

Now we have a range of values. At one end, the Terran focus fires perfectly, reducing the damage rate of the Zerg. At the other end, the terran does the perfect anti-focus fire, the roaches all stay alive until the exact last moment, and then die simultaneously. In the latter scenario, the zerg maintains his prior attack rate until the end, and about 33 marines are dead at the end of the fight; 17 remain. In the former scenario, there are a few extra marines alive as a result of good focus fire from the Terran.

So when 50 unupgraded marines engage 25 unupgraded roaches, there should be at least 17 marines alive at the end. Better focus fire from the terran will raise this number, but not higher than 22 marines. A smaller arc length will aid the zerg, pushing the number closer to 17 marines. Of course, this calculation also doesn't account for overkill, to which roaches are prone. Overkill might leave the Terran with much more than 17 marines at the end of the day.

The result of the calculations: not accounting for overkill from the roaches, then at least 17 marines should be alive at the end of the fight. Engaging in smaller spaces in this case helps the Zerg.

From this analysis we can draw a few interesting conclusions, although they may not be especially new, and mostly are already well-known. I guess you could call this a tl;dr if you like.

Tl;dr:

-Getting big arcs is very important in getting strong engagements. In small armies where you haven't yet reached your maximum rate of units firing, this isn't so important, but as armies get bigger, large arc lengths become more important. Big arcs are more important for low-range units (thus why engaging in open spaces and against spread-out opponents is so important for zerglings, and for zerg in general).

-Knowing how units perform in a one-on-one engagement doesn't tell you how they perform in a 100-vs-100 engagement. In particular, one-one-one engagements don't emphasize range and collision radius as much as larger engagements do. Thus a zealot can beat a roach in a one-on-one fight (without micro, at least), but lots of zealots lose hard to lots of roaches.

-Range is a really, really important quantity on units. When the immortal went from range 5 to range 6, this was a much more massive change than it sounds like. Queen range jumping from 3 to 5 has all kinds of Terrans up in arms about balance. ~~Reaper range 7 in HotS doesn't sound that significant, but it really is potentially game-breaking and should be watched closely (especially considering their tiny collision radius of .38)~~. (Edit: I believe I was mistaken about reaper range being changed in HotS. In other HotS news, 22 range makes the Tempest a lot more effective than you think.)

Last edit: 2012-06-25 12:34:33

"Never attribute to malice that which is adequately explained by stupidity." -Robert J. Hanlon

Empyrean June 25 2012 12:17. Posts 16299

Profile Blog #

Not to be dismissive, but why wouldn't you try to model this as a set of differential equations?

EDIT: Cool blog, though.

Last edit: 2012-06-25 12:17:59

Probe1 United States. June 25 2012 12:17. Posts 16445

Profile Blog #

I enjoyed it reading this. Thank you.

.. I also didn't know reapers had 7 range. wut.

우정호 KT_VIOLET 1988 - 2012 While we are postponing, life speeds by

ChristianS United States. June 25 2012 12:27. Posts 371

Profile Blog #

Somehow I've always hated doing anything with differential equations unless I absolutely have to. I should probably get over that. But for now, I did this the same way I got through physics in high school, with a different equation for each value instead of differentiating everything.

A quick googling shows that reaper range 7 might have been a hoax. Now I'm not totally certain, I'll have to investigate a little more. It did seem awfully broken.

"Never attribute to malice that which is adequately explained by stupidity." -Robert J. Hanlon

d3_crescentia United States. June 25 2012 13:10. Posts 3669

Profile Blog #

Another promising young student ventures into math-modeling of SC concepts! But, modeling is nothing without testing and data, and data + conclusions would give mapmakers more concrete details to work with.

On June 25 2012 12:17 Empyrean wrote:
Not to be dismissive, but why wouldn't you try to model this as a set of differential equations?

EDIT: Cool blog, though.

Check out Lanchester's Laws of combat. A set of differential equations gives the result that, between two armies of size A and B that are otherwise indistinct in composition (no upgrades, identical single-unit composition), the winning army will be of size sqrt(A^2 - B^2), assuming of course that A > B. I spent little bit of time testing said law in SC2 a month ago, and it predicts engagements fairly well so long as all the units in the engagement are firing.

You can also factor in different DPS by introducing a constant (for upgrades, different single-unit compositions, etc.), and I started work on that a few months ago, but my math is super weak from being out of school for so long and I've since been sidetracked by other less-hard projects. Now that this thread is around, I'm trying to run the 50 marines vs 25 roaches scenario through the equation.

Since I keep getting 17 * i marines remaining, something is probably very wrong with my math and so it would be good to collect some data.

once, not long ago, there was a moon here

ChristianS United States. June 25 2012 13:37. Posts 371

Profile Blog #

Intuitively, I think the roaches should win the fight. I don't know where my math is wrong, although there's plenty of places for it to get messed up. Overkill seems like it would favor the marines even more, since marines fire quickly, do low damage, and hit instantaneously. But there's the fact that my estimation of rows of units isn't quite perfect; I assume that the units don't clip each other, but if we're being completely accurate they clip each other quite a bit, which could introduce quite a bit of error. Then there's the fact that when a unit in the front row is killed, it takes a few moments for another one to step into its spot. Since marines fire from two rows against roaches, no marine would step forward; instead, the roaches would kill the front row of marines, then walk forward. That would mean that the front row would only be full part of the time, and they would average at about 1.5 rows.

Let's see, in that case their damage rate would be 11.59 * AL. That means for every marine killed they'd do 82 damage, or kill about .56 roaches. By that they'd still come out ahead in the end, but they'd have something like 5 marines at the end; and of course, by then they stop filling their rows, and the roaches do better in small numbers, so the roaches might come out ahead. They should still kill most of the roaches, though, if not all of them.

"Never attribute to malice that which is adequately explained by stupidity." -Robert J. Hanlon

d3_crescentia United States. June 27 2012 19:26. Posts 3669

Profile Blog #

On June 25 2012 13:37 ChristianS wrote:
Intuitively, I think the roaches should win the fight. I don't know where my math is wrong, although there's plenty of places for it to get messed up. Overkill seems like it would favor the marines even more, since marines fire quickly, do low damage, and hit instantaneously. But there's the fact that my estimation of rows of units isn't quite perfect; I assume that the units don't clip each other, but if we're being completely accurate they clip each other quite a bit, which could introduce quite a bit of error. Then there's the fact that when a unit in the front row is killed, it takes a few moments for another one to step into its spot. Since marines fire from two rows against roaches, no marine would step forward; instead, the roaches would kill the front row of marines, then walk forward. That would mean that the front row would only be full part of the time, and they would average at about 1.5 rows.

Let's see, in that case their damage rate would be 11.59 * AL. That means for every marine killed they'd do 82 damage, or kill about .56 roaches. By that they'd still come out ahead in the end, but they'd have something like 5 marines at the end; and of course, by then they stop filling their rows, and the roaches do better in small numbers, so the roaches might come out ahead. They should still kill most of the roaches, though, if not all of them.

intuitively the marines should win the fight because superior numbers trumps superior efficiency

based on some preliminary tests I conducted (done in a generic unit test map) 17 marines *may* be a good prediction - results were generally in the 15-20 range, but it'd be better to create a specific testing map so we can recreate the scenario you described and run a couple hundred iterations. I also have to figure out if I'm defining my efficacy coefficients correctly...

once, not long ago, there was a moon here

ChristianS United States. June 28 2012 07:44. Posts 371

Profile Blog #

In general numbers trumps efficiency, but I chose 25 roaches against 50 marines in the first place because they're approximately equal on resources (50 marines = 2500 minerals, 25 roaches = 1875 minerals, 625 gas), unupgraded marines are widely believed to be terrible, and roaches are in general considered pretty good against marines. A lot of people would estimate that fight by knowing that 1 roach consistently beats 2 marines (The roach kills 1 marine in 3 hits, or 6 seconds, and kills the second after 12 seconds; the first marine does ~35 damage in its 6 seconds of life, while the second does ~70 damage in its 12 seconds of life, so the roach ends the fight with ~40 health), and assuming that both sides scale equally. Obviously marines scale more effectively, but that change is quite dramatic.

Predictions
-50 marines vs 25 roaches should end with 17-22 marines.
-40 marines vs 20 roaches should end with 15-18 marines.
-30 marines vs 15 roaches should end with 5-8 marines.
-20 marines vs 10 roaches should end with 0-5 marines remaining (in the extreme focus fire case, I believe the zerg ends with a roach at half life).
-10 marines vs 5 roaches should end with about 1 roach left alive.
-2 marines vs 1 roach should end with 1 roach at about 40 HP.

These calculations were done with an assumed arc length of 3.5, which is approximately the width of a small ramp (not a base ramp, which is only 3 roaches wide). In several of these cases, the roaches would benefit significantly from engaging in a more open area.

"Never attribute to malice that which is adequately explained by stupidity." -Robert J. Hanlon

uikos United States. June 29 2012 23:32. Posts 121

Profile Blog #

(I'll preface this by saying I'm not a math-guru by any means, but I've "theoretically" thought of a topic similar to this but never really sat down and tried to actually do it. Kudos to you for your first attempt! :D)

I'll agree that the Lanchester's laws (found on wiki) were quite informative and hit on a point that you're missing. (I never heard of these laws until right now.) But unless I'm mistaken, you don't account for units dying. Obviously when a unit dies, it can't attack anymore, but I don't see any account for that in your calculations.

That would be why differential equations would be much more useful because you can then really capture the notion that damage is dealt more like in a stream (a rate) rather than in rounds. This is even more tricky when you realize you can only deal with integers (there's no "half a marine").

If you manage to get over that hike (modeling everything in differential equations), one of the things I think is academically rewarding is figuring out the "tipping point." (Assuming no micro, what is the least number of marines you need to kill off a roach army of X roaches.) A lot of players (at the very least, me) can kind of "guess" which army will win, but often times we're wrong. And as with any theory-applied-to-real-life paper, you could then actually test your theory. Obviously micro will make a big difference, and then you can start to tweak your model to make claims about how "effective" microing/positioning will help your army.

Other good questions to tackle are "why are MMM so good in small numbers" and "why is mass-roaches a bad idea after a certain point of the game." Us starcraft players of course have an intuitive answer to these questions, but we have no "solid calculation" to back them up.

I really liked your introduction of the arc-length :D I'm not entirely sure if it's correct (simply because you're treating it like a line as opposed to an actual arc), but I like the direction you're going with that.

I don't think you need to worry about overkill because most people A-move, and if I'm not mistaken, the starcraft AI doesn't have units overkill when A-moving unless you manually tell units to attack a specific enemy unit.

Nice writeup and good job!

I'm in love with Hero~

ChristianS United States. June 30 2012 08:11. Posts 371

Profile Blog #

On June 29 2012 23:32 uikos wrote:
(I'll preface this by saying I'm not a math-guru by any means, but I've "theoretically" thought of a topic similar to this but never really sat down and tried to actually do it. Kudos to you for your first attempt! :D)

I'll agree that the Lanchester's laws (found on wiki) were quite informative and hit on a point that you're missing. (I never heard of these laws until right now.) But unless I'm mistaken, you don't account for units dying. Obviously when a unit dies, it can't attack anymore, but I don't see any account for that in your calculations.

For my calculations, I assume an instantaneous replacement rate. That is, when a unit in the row dies, One of the units from behind that was too far away to fire steps into its place. Obviously this takes time, but I have no way to quantify that time, nor can I calculate when these deaths will occur, since they depend either on micro or on which units the attack-move AI randomly decides to target. This would introduce some error, but not a lot; and since both sides need to replace dead units, the error on each side would approximately equal out. So the battle would take longer than expected, but I think the outcome should be roughly the same.

For units that have enough range to fire from multiple rows this might function a little differently. If 2 rows of marines are firing on one row of roaches, and some of the front line of marines die, none of the marines from behind the second row can find a way to move forward. So the front row doesn't get replaced; instead, the roaches kill off the rest of the front row, and they have to walk forward to fight again, at which point the next row of marines is now in range to fire. Thus the effective number of rows firing would depend on the random choice of the AI; if it focus-fired perfectly, then the front row would start at full and lose a marine at consistent intervals, so the row would average at being half full. If it anti-focus-fired perfectly, the front row would remain full until all the marines in the front row died at the same instant. Then the row would maintain its full firing rate until it died and the next row behind could start firing.

Where I suspect Lanchester's laws would come in handy is modeling the engagement after one or both sides don't have enough units to replace the front lines. At that point there's no reinforcements to "replace" the dead units, so the rate is permanently changed with every death.

That would be why differential equations would be much more useful because you can then really capture the notion that damage is dealt more like in a stream (a rate) rather than in rounds. This is even more tricky when you realize you can only deal with integers (there's no "half a marine").

As a matter of fact, differential equations do model everything as a rate, but so did the equations I used. I just find it easier to use dimensional analysis to find the equations, and then multiply or divide by time to change between rates and accumulations of those rates.

What's unfortunate is that while rates are mathematically easier to work with, damage isn't actually dealt in a stream; it comes in discrete attacks, which do in a sense come in "rounds." Even using DPS to describe damage being dealt isn't entirely accurate; a roach doesn't do 8 damage continuously over the course of a second, it does 16 damage in a burst after 2 seconds. These are approximations that will introduce some error in calculations, but probably a negligible amount.

If you manage to get over that hike (modeling everything in differential equations), one of the things I think is academically rewarding is figuring out the "tipping point." (Assuming no micro, what is the least number of marines you need to kill off a roach army of X roaches.) A lot of players (at the very least, me) can kind of "guess" which army will win, but often times we're wrong. And as with any theory-applied-to-real-life paper, you could then actually test your theory. Obviously micro will make a big difference, and then you can start to tweak your model to make claims about how "effective" microing/positioning will help your army.

Other good questions to tackle are "why are MMM so good in small numbers" and "why is mass-roaches a bad idea after a certain point of the game." Us starcraft players of course have an intuitive answer to these questions, but we have no "solid calculation" to back them up.

I think once I have an effective way to model the engagement after one or both sides don't have enough units to reinforce the front lines, I could begin to answer some of these questions. The other tool that would help answer some of them would be making a custom map that allows me to specify arc length, what units on each side, and how many of them. I'm not especially experienced with the map editor, but I could probably manage something like that with a little research. I just need to find the time to do it.

I really liked your introduction of the arc-length :D I'm not entirely sure if it's correct (simply because you're treating it like a line as opposed to an actual arc), but I like the direction you're going with that.

Arcs are obviously not always straight lines, but their length is still a linear quantity, and the number of units in each arc is still determined by the arc length divided by the collision radius. Instead of looking linear as shown above, it could look like this:

[image loading]

Here the arc is curved rather than straight, but it still has a length, and that length is still a linear quantity. If we approximate that curve as a circle with a more sharply curved arc corresponding to a shorter radius, then the length of the arc can be calculated by radius * theta, with theta being the portion of the circle in radians that is occupied by the arc. So if your units are in a complete circle around the enemy, theta is 2 * pi, if your units are units form a half circle around the enemy, theta is pi, etc.

If the arcs are curved it's usually because one army is wrapping around a little wider than the other army, which means that they'll be part of concentric circles, and they'll occupy the same theta. You can find the center point of those circles by drawing a straight line through the edges of each arc until they intersect at some point beyond of the smaller arc.

[image loading]

Since the thetas are the same, you can compare the arc lengths by judging how far each one is from the center. So if the smaller arc is about halfway between the center point and the outside arc, then one arc is proportional to r * theta, while the other is proportional to (1/2) r * theta. That means that the smaller arc length is approximately half as big as the other one (you can see this scenario pictured above). If the smaller arc is about 80% of the way from the center point to the outside arc, then its arc is about 80% as big, etc. This is a good quick way to judge arc length relative to your opponent. Note that this analysis is assuming both sides are only firing from a single row, so I don't know how this transfers to situations where one side significantly outranges the other, so more rows are firing.

I don't think you need to worry about overkill because most people A-move, and if I'm not mistaken, the starcraft AI doesn't have units overkill when A-moving unless you manually tell units to attack a specific enemy unit.

While the starcraft AI doesn't generate boatloads of overkill, there's still some. First of all, some overkill just comes from the fact that a unit has to be hit by an integer number of attacks. If a marine with 45 HP gets hit by 3 roach attacks, the first two each do their full 16 damage, but the last one only does 13. Of the 48 damage in roach attacks, 3 is wasted killing by killing a marine with 13 HP using a 16 damage attack.

As for several units attacking the same one generating a lot of overkill, this happens for attacks that do not impact instantaneously. Marines hit instantaneously, so no overkill. Roaches do not hit instantaneously, so if a roach attacks a 13-HP marine, there is a brief delay in which another roach can attack that same marine. If it does so, its attack is wasted.

Nice writeup and good job!

Thanks for reading! And thanks for the feedback! And sorry for the wall of text in response. I'm planning to do more with these calculations. I'll either post another blog, or edit this one. In either case, you're welcome to check back and see what I've done with it.

"Never attribute to malice that which is adequately explained by stupidity." -Robert J. Hanlon

Xyik Canada. June 30 2012 08:36. Posts 606

Profile Blog #

Cool, would be good to see how accurate your model is to gameplay results. Maybe compare in some sort of unit tester?

Please log in or register to reply.