|
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.
|
Wow I love this blog. 5/5
I like the experimentation by d3_crescentia, suits perfectly to my engineering mind, haha.
Maybe someone should try the thing with zealots, yes, more protoss love please~
|
Thanks for the feedback, everyone! I really appreciate all the comments and suggestions. Specifically StRyKeR, it makes perfect sense to use a floor or ceiling function to make steps. However, as said before, making differential relationships between functions like that is terribly difficult (and at the very least super messy).
@ d3_crescentia, wow it's awesome that you went though all the trouble to get those results. I think it's really cool to have an experimental aspect to these ideas, to compliment the theory. Many thanks!
|
FINAL UPDATE:
I ended up taking data for 13v12 and some other instances. Have some graphs:
A short explanation: since it's difficult to evenly spawn the two symmetric parallel lines of zerglings since one is odd and the other is even, the 13th zergling was added to either the top or the bottom of the line. I tried these instances with both Linear2 and 3 line separation distances (refer to my earlier attempts for a better idea). Looking at the graph of Linear3.1 specifically it's here where we start to realize that 100 trials is definitely not enough to give us accurate data. Still, it seems to suggest a peak at either 4 or 5, which is close, given the imperfect nature of the experiment.
To see if anything interesting would happen, I added the results from Linear2.1 and 2.2, and 3.1 and 3.2 together and plotted them, though this would compound the experimental error significantly if I was doing this seriously (for that matter, if I was doing this seriously, I wouldn't be using Excel). Again, suggestion of a peak at 4-5, but we need more trials to be accurate.
Lastly, some other trials for people that are interested. These are runs of 101 trials of Linear2 setup (with the exception of 18v15) - enough to suggest peaks, but we're starting to get to the point where 100 trials is not enough. We have a predicted peak for 17v15 at 8 and an actual at 9-10. For 20v16, this is simply a multiple of 10v8, which should give a peak at 12, but more trials are necessary to see if it does indeed occur there. It could also be that the mathematical model fails at larger numbers of zerglings for whatever reason.
*The run of 18v15 was entirely a mistake - I set my triggers to spawn an extra zergling in the 17v15 run. By the time I had noticed, it was already >70% completed. Truth be told, this data doesn't look too bad, as the peak should be at about 10 (root(99) to be exact), but again - more trials to be sure.
+ Show Spoiler [Speculation] +Discounting the points at zero, it seems that the distribution climbs more gradually before the peak and falls more steeply after the peak. Having been trained as a physicist, I've only encountered such a graph once before. If we reverse the x-axis and define it in terms of zerglings lost for player 1 (with the surviving zerglings simply being added to the 'lost' count), then we can get something that looks like: The Maxwell-Boltzmann distribution for particle speeds in gases. Of course, more trials may end up telling us that this is not entirely the case, and I can't discount the fact that I'm just pulling things out of my ass right now. But, if there's a connection between the two (as unlikely as it is), I'll see if I can't find it.
I also tried experimenting with different concave formations in the 10v8 scenario to see if the 8 could win, but none of them turned out very well.
Some conclusions/possible improvements:
- Probably a good mathematical model for 1-2 control groups of lings under ideal circumstances.
- The next possible avenues of inquiry involve different zergling formations (clumps, perpendicular lines, concave) or with larger groups of lings and more trials.
- Zergling AI, while not as bad as Dragoon AI, can still be pretty bad.
- Possible UMS improvement - having an internal counter of each trial, as I double-checked the leaderboard after every engagement (not difficult, just tedious). This is rather difficult/boring with StarEdit alone, but I don't think it will be too much better with SCMDraft.
This was a lot of fun - I miss doing scientific-ish things, so it was refreshing and entertaining to do it for SC. It was also nice to work on a UMS map again, especially since I have a tendency to set projects too big for me to finish quickly. If you come up with other things to experiment, let me know and I'll see if I can give it a shot testing it.
|
Thank you for this thread, and I hope you continue with deeper math analysis of Starcraft. For example, it's interesting to investigate how acceleration affects gameplay with various speed caps.
On January 10 2010 20:22 ShinyGerbil wrote: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 Indeed, due to fragmentation of armies most calculations are based on L2-normed space (or Pythagorean metric), adjusted to include standard deviation, due to non-deterministic randomness. The volatility factor is quite high, so this makes the outcomes of most evenly matched battles fairly unpredictable. Therefore, people shouldn't be too quick to conclude anything from the outcome of a Starcraft battle.
|
You probably have to get into difeq
|
Hmm, it'd be interesting to put together a BWAPI "perfect micro" bot to see exactly what the results are, although it'd be pretty difficult - what do we consider "perfect" to be
If anyone can give me a clear rules of what perfect micro is, I could try it (and probably fail, but that's besides the point).
|
My thoughts on perfect micro.
+ Show Spoiler +For individual controls, I'd guess that they should retreat before dying (with 1 hit left on them, waiting for their health to return), as well as retreat from 1v1 battles where they will lose (ie, they have less health than the enemy unit). They should run from 2(+)v1 battles (unless they will win them), and attempt to engage in 2(+)v1 battles (unless they will take any casualties). Target priority should go to the enemy units with the least health left. Attempt to prevent overkill somehow as well.....
After that, you'll have to incorporate multi-unit positioning into it, to form concaves, and trap running enemies. That will be much, much trickier.....
And then, there are times where taking some damage gets multiple units into better positions, allowing the combined group to do much more damage than if the individual followed the set rules..... There will also be times where one needs to retreat, to give another room to retreat to prevent it from dying..... this part will be next to impossible to code, if not impossible.....
Of course, if you were to do this with the group with less lings, and have normal micro on the group with more, I would fully expect them to win without taking any casualties (assuming a large space to work with, and more than 1 ling is involved for them).....
If it was done right, I doubt Jaedong could win with 2X the lings..... It might be powerful enough that it could eventually defeat hundreds of lings under his control with only 2 under perfect micro.
|
let this guy go to berkeley...
|
the US has stolen enough of our doctors, scientists and engineers, they don't need to steal our SC players, thank you very much.
|
|
|
looking forward to part 2
|
It is possible to derive the same thing without actually solving the differential equations. Basically you want to show F^2-G^2 is invariant. Differentiating
2F.F' - 2G.G'=2F.(-kG) - 2G.(-kF) = 0
gives you that F^2-G^2 is constant and the rest follows.
|
On June 01 2010 10:59 Megaman703 wrote:
the US has stolen enough of our doctors, scientists and engineers, they don't need to steal our SC players, thank you very much.
We steal those from Third World countries...
|
United States10328 Posts
oh rofl my roommate and I did a math modeling project on this like last november, and then a bunch of people modeled these small unit battles for our modeling with differential equations class just yesterday... let's see if we can obtain copies of those to put up here ;o
|
On June 01 2010 10:26 illu wrote:
let this guy go to berkeley...
Edit: I was mistaken...
Also... I love this theoretical gaming stuff. I was working with my game theory prof to do some simplistic starcraft analogies a little while ago.
|
|
|
|
|
|
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)
![[image loading]](http://img.photobucket.com/albums/v312/vdraconis/zerglings5-1.jpg)
![[image loading]](http://img.photobucket.com/albums/v312/vdraconis/zerglings6.jpg)
![[image loading]](http://img.photobucket.com/albums/v312/vdraconis/zerglings8.jpg)
![[image loading]](http://upload.wikimedia.org/wikipedia/en/5/5d/Maxwell-Boltzmann_distributionPDF.png)
