|
Hey guys,
I've been wanting to do this for a while now, 'this' being make a blog about mathematical analysis of certain StarCraft phenomenon.
This edition will be looking at the following situation:
Problem: Mirror match, 10 Zerglings vs 8 Zerglings. How many Zerglings will survive on the 10 side once the 8 side is completely dead?
Obviously this takes many, MANY unrealistic assumptions into account. For one, 'no micro' (or perfect micro) is involved, because that would introduce references to chaos dynamics which are near impossible to deal with >_>. Second, I'm going to approximate damage and the life of the army as continuous functions. This has a larger percentage margin of error with such small numbers, but better approximates asymptotic results near infinity. However, I still think the end result is somewhat interesting, so just bare with me.
Note: to everyone in the future who wants to comment about how unrealistic and imperfect starcraft battles are, I completely agree. This blog is mostly meant to tackle abstractions and related ideas in math, for any type of real battle outcome expectation, I would suggest playing around with it yourself in the campaign editor.
Denote functions F and G as life/time for the two armies. That is, when we solve for x_0 when G[x_0] = 0, and then F[x_0] will be our answer.
Some things we know:
F[0] = 10
G[0] = 8
Also importantly, the rate of change of F is directly proportional to the size of G. (the more Zerglings the other guy has, the faster yours will die.) We can represent this with differential equations:
F' [x] = -kG[x] (1)
Similarly,
G' [x] = -kF[x] (2)
(Where k is the damage per second of 1 unit of F, i.e. 1 Zergling. )
Taking the derivative of (1) and subbing in (2) yields:
F'' [x] = -kG[x] = -k(-kF[x]) = (k^2)F[x] (and the same result for G'' [x])
Now we begin to think about the possible functions to represent such an equation. Immediately e^kx comes to mind, and possibly a trigonometric function. However with something like cos[kx], F'' [x] = (-k^2)cos[kx], which is not equal to the right side. The other less obvious solution to this equation is e^-kx, and thus functions F and G are actually linear combinations of e^kx and e^-kx.
Note: For the remainder of these calculations, we will disregard this 'k-factor', since intuitively, if Zerglings did half or twice as much damage, the battle would finish slower or faster, but the end result would be the same. So,
Answer: 6. If 10 Zerglings engaged 8 Zerglings in a perfect world, math says 6 Zerglings would survive.
Of course, the natural followup question is, how can we generalize this equation to starting armies of size a,b for any values with a>b. Since this blog is getting kind of long, I’ll leave this final problem to spoilers:
+ Show Spoiler +Ok assuming F[0] = a and G[0] = b. We know that a = C1+C2 and b = C2-C1. Solving this yields: C1 = (a-b)/2 and C2 = (a+b)/2 Now we once again find the root of G[x], and sub the result into F[x]: So as we can see, if an army of ‘a’ Zerglings engages an army of ‘b’ Zerglings with a>b, the remaining number is speculated at sqrt(a^2-b^2), which I found very interesting because it maps out the sides of a right angled triangle (Pythagorean Triples). Some interesting applications include: 5 vs 4, 3 survive 13 vs 12, 5 survive 17 vs 15, 8 survive
This concludes my first blog post. I'm new at this, so please let me know what you think. I'm currently a first year math major in university, so I'm not infallible in the subject. Anything would be helpful, challenging my logic, suggestions for communication, layout, organization, or ideas in StarCraft that you would like analyzed.
Thanks again,
ShinyGerbil.
 
|
If you're interested in this sort of thing, you might want to google the Starcraft course that took place at Berkeley at the start of last year, which had a roughly game-theoretic approach - video of a few of the lectures are available on Youtube.
|
Hong Kong20321 Posts
x_0 looks like a face :D:D
interesting but unfortunately i'm totally not a maths person 
welcome to TL!
|
you need to include that a damaged zerg heals and thus constantly will get more health. yes math like this is hard.
|
By using calculus you use a continuous solution to solve the problem. I'm not entirely sure the assumption is valid with only 8 zerglings. It is probably not far off but with 8-10 zerglings being off by one is a margin of error that sort of makes it a bit pointless. Also, unless you use Pythagorean triples like you have, you'll get non-integer results which are also not very useful. Furthermore it is unlikely you'll be able to build upon this solution, greater accuracy would require a discrete solution which would probably be a lot of tedious and difficult work into the simulation of zergling combat.
So you've probably done the best possible without writing a 10 page thesis and it was interesting. Thanks!
|
You can actually make it very useful in game but its usefulness depends on how close it is to perfect equation, meaning how close it is into including all possible factors. Still the experience based knowledge usually means learning the discernment faster for most people, so they don`t need maths at all to differ whether its worth for them to engage or not. In 95 % situations its not worth to engage with inferior number anyways so .....
Still - one who would understand the subtle difference between 95 % and 5 % situations - he would be able to use it, form new or modifyed strategies that would make use of this factor and what he would learn from that would let him gain even more knowledge about this and become even better player so - in the end this subtle difference would skyrocket his skills to lvls even unimaginable for those who ignore this 'little' things, to say he would be absolutely unbeatable
Actually this isn`t even crazy assumption nor is it exaggeration - its the reality.
There is a tremendous amount of usable knowledge even behind such seemingly vague concept. 10 lings vs 8 lings , if you understand this situation in and out and use it to full potential - then 8 lings can win vs 10 lings even if both players are good. Yes it is that useful.
|
This is absolutely interesting and I just created a UMS map which will test this theory. I'm going to leave it running for the next few hours so I can get some nice data. Will post sometime later this afternoon!
|
Nice work!
As it stands, it underestimates the damage output of a unit, because in reality, a damaged unit does not do any less damage than a fully healed unit.
In order to compensate, you could let F(x), G(x) be the total hp of the armies and work out the equations
F' [x] = -k * CEILING(G[x] / 35.0)
Similarly,
G' [x] = -k * CEILING(F[x] / 35.0)
35.0 is the HP for a zergling. I don't think there is a closed form solution. It's probably close to the sum of exponentials solutions you got, but you never know -- discretization might have a bigger effect. It would be interesting to have a numerical solver output the solution curves (or steps, I guess).
Also the benefit of using hp is that it assumes the armies are "smart". As in, the damage being dealt will ALWAYS focus fire to kill off one unit at a time. For example, once G(x), the sum of all HPs, falls by 35, it assumes that a Zergling has been killed.
Of course, since Zerglings don't have range, even with the best micro, 20 Zerglings cannot simultaneously deal damage to one Zergling at a time. I will think of something for later.
|
I think perhaps the best way to assign damage dealt would be to assume the larger army engages one on one first and then two on one with the extras.
For melee units, especially.
|
Well a more pressing realistic issue is that you're having 10 zerglings surrounding 1 zergling while 7 other zerglings surrounding one the the 10. They are all happily hammering away. With no micro at all, 10 zerglings in a line would lose just one or two zerglings against a line of 8. With perfect micro (in which zerglings attempt to attack in 2v1 and 1v1 situations), you might realistically lose around 7 or 8.
|
Your analysis might be reasonable for 100 zerglings vs 60 zerglings, but treating the hp and damage as continuous functions is not realistic enough to give meaningful results with only 6 or 10. Also, you need to use probability with such low numbers as well. It really depends on which side attacks first, because once one zergling dies (the one who attacked second), then the remaining zergling may only have 1 hp, but now you have 2 zerglings attacking 1 zergling. This is not a continuous math problem, its a discrete problem (not surprising since this is a computer program...).
On January 10 2010 22:01 d3_crescentia wrote:
This is absolutely interesting and I just created a UMS map which will test this theory. I'm going to leave it running for the next few hours so I can get some nice data. Will post sometime later this afternoon!
What would be really interesting is if you could keep increasing the number and see if you can converge with his result. Make a map with 6 vs 10, 12 vs 20, 24 vs 40, etc.
|
Why only zerglings? Wheres the protoss love? ^_^
|
I think it's hard to predict the outcome with equations alone. The best way to approach this is through empirical experimentation, i.e. running a scenario on a UMS a hundred times.
Ha, Engineering vs. Math 
|
Ehh ~_~_~ in a perfect world the 8 lings would be sitting on the ramp in a concave formation.
|
You should reallllly use a step function rather than a continuous function. The math is not much harder... i.e. taking the integral is actually much easier.
|
i skipped most of the math but i think it'll be interesting to compare your results with crescentia's UMS map testing to see how it works out.
|
A few images of 10v8 runs I tried earlier this morning, and a short explanation of the process:
+ Show Spoiler +First attempt. Second attempt. Third attempt.
The two ling groups are unallied from each other and are left to acquire their own targets for attack until one side emerges victorious. The remaining lings are counted and then ordered to move out of the way and killed, for the next set of lings to spawn. This was repeated for 101 trials for each attempt - which by no means is definitive, but it should give an idea of how accurate the mathematical model is.
The varying distances of each run were attempts to simulate what I feel is the ideal situation, where two parallel lines of zerglings are engaging combat. Commenting on that, the first run wasn't a very good simulation. The second and third were better, with (I believe) the second faring significantly better than the third - in the third the ling formation to bulge more often than the 2nd, perhaps due to the targeting AI.
After recording how many zerglings survived for 101 runs per attempt, we get the following distribution:
![[image loading]](http://img.photobucket.com/albums/v312/vdraconis/zerglings5.jpg)
Something I threw together in Excel.
The number of surviving zerglings is counted for the first player, who started out with 10 zerglings. The number of instances of the number survived was counted and plotted in the above graph. In these trials there were no instances was the second player victorious. Based on the data, it does seem that the most probable outcome is either 6 or 7 surviving zerglings if they engage in two parallel lines relying on only the computer AI to acquire targets for attacking. I may end up trying to do some error analysis later to figure out the uncertainty, but I do find it interesting that it does seem to suggest that the math sort-of predicts the most likely outcome, even if the approach still has some kinks to be worked out. Perhaps later this evening I'll run the next case; 13v12.
Again, I'd like to state that I am not a statistician and that this study was done for exploratory purposes (and entertainment, to a small degree), and so my results may not be 100% accurate, though I made painstaking efforts into getting good data. If you have a little knowledge of UMS mapmaking, feel free to reproduce my trials on your own by modifying the map below. Also, I do not profess to be an excellent mapmaker, though I was glad to see that I haven't forgotten everything about UMS mapmaking these past 6 or so years.
Link to map: http://www.mediafire.com/?wybxdo3iyoi
Lastly, I'd like to say that while this might not have any significant application to 1v1 BW as we know it, it was a lot of fun doing this, and I'll keep you guys updated with anything else I end up doing with this.
|
On January 10 2010 21:05 searcher wrote:
By using calculus you use a continuous solution to solve the problem. I'm not entirely sure the assumption is valid with only 8 zerglings. It is probably not far off but with 8-10 zerglings being off by one is a margin of error that sort of makes it a bit pointless. Also, unless you use Pythagorean triples like you have, you'll get non-integer results which are also not very useful. Furthermore it is unlikely you'll be able to build upon this solution, greater accuracy would require a discrete solution which would probably be a lot of tedious and difficult work into the simulation of zergling combat.
So you've probably done the best possible without writing a 10 page thesis and it was interesting. Thanks!
I thought so too, but then I realised that there would still be problems with a large number of zerglings. He makes the assumptions that the rate of change your zerglings is proportional to the number of enemy zerglings, but this is only true if all zerglings are in engagement, something that doesn't happen with large numbers.
|
United States4796 Posts
This is seriously some of the most awesome math ever!
|
Might I make a request for an excel spreadsheet calculating whether it'd be better to upgrade or to build more units to increase your damage output? The spreadsheet should have all the required constants I need to change eg: base damage, damage/upgrade, cost/unit, armor etc...
This could be useful in defence games like sunken D.
|
|
|
|
|
|
EPT![[image loading]](http://i21.photobucket.com/albums/b274/joe_the_shmo/latex1.jpg)
![[image loading]](http://i21.photobucket.com/albums/b274/joe_the_shmo/latex2.jpg)
![[image loading]](http://img.photobucket.com/albums/v312/vdraconis/zerglings.jpg)
![[image loading]](http://img.photobucket.com/albums/v312/vdraconis/zerglings2.jpg)
![[image loading]](http://img.photobucket.com/albums/v312/vdraconis/zerglings3.jpg)
