EVE: Combinations and probabilities.

[sobrique]

I have a bit of a puzzle that I'm trying to figure out.
It's EVE related, but a little more ... annoying.

The problem is this.
When building a starbase, one deploys sentry guns as defenses.
You have a choice of small, medium or large (in a mix if necessary).
A small gun does 1 point of damage, a medium 2, and a large 4.
Each gun uses a certain amount of power. A small uses 1, a medium 2, a large 4.

The problem is this. An attacking ship requires at least 5 points damage to destroy it. (It might be more, but a single large gun cannot do the job). (Otherwise it can run away and repair, come back and repeat).

Against a single ship, there's no difference at all in damage dealt. However, when one is faced by an attacking fleet of 10, 20, 30, 40 or 50, is having 40 small guns doing 1 point each, better than 10 large doing 4 each.

Each gun selects a target entirely at random.

Now, the first stage, is figuring out how many different 'sets' there are. Which is fairly easy, it's number of ships to the power of the number of guns. Easy enough really.

The thing I'm having trouble figuring out is how many 'sets' the same ship is picked multiple times.

I started on permutations (N!/(N!-K!)) in the hopes of excluding all the permutations where multiple aren't picked, however that doesn't really help when I'm trying to fit the cases where '3 or more the same' are picked.

To take the simple case, with 3 guns, and 3 ships, and 2 on the same target needed to destroy:

1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

Bolds are ones that 'count' as successes. Now, I figured that you could probably pick the permutations here (3P2 is 6) since by excluding 'legitimate permutations' you end up with only the ones where there's some repetition. But that falls down if you say want 3 'hits' (where only 3 successes occur).

And my brain is melting now. I shall ponder some more.


The purpose of the puzzle, is to figure out if a starbase populated entirely with 'small' guns is 'better' than a starbase populated with 'large' guns. (Intuitively I'm thinking yes, because 'efficiency' of distribution is better, but if more guns will probably lead to evening out of damage, and I need 'spikes' to destroy ships)

Comments

[paulw.livejournal.com]

If you have 40 points I would go with something like 2 large, 8 med and 16 small.

Its a mix which would give you those spikes and well, I just like those numbers. ;)

[mister-jack.livejournal.com]

I suspect one populated with medium guns will be best.

My thinking is like this: the more guns you have, the more even the distribution will be and you need clustering to destroy ships, and larger cluster to do it with smaller guns. However, an all large gun setup will 'waste' a lot of power as the granularity is high so when hitting a 5 pt to kill ship with 8 pts you waste 3 points. The medium gun offers a position intermediary between the two and will therefore probably be best.

[mister-jack.livejournal.com]

Now you're just complicating matters ;)

[sobrique.livejournal.com]

I'm less worried about wasting the damage as I am about failing to kill a ship, it warping out and returning again.

However that still doesn't help me with the root of the problem. Figuring out what relative probabilities are of 8 small guns out of 40 picking the same target, vs. 2 out of 10 large guns, with a 40 ship fleet visiting :).

[mister-jack.livejournal.com]

Sum (a = 8 to a = 40) of 40*(40!/(a!*(40-a)!))*40^(40-a) ways of doing it for the small guns I think. That's all over 40^40.

[sobrique.livejournal.com]

Does that account for the fact that I don't mind which ship they choose, and which 8 it is that chooses?

Ugh. Confusing

[mister-jack.livejournal.com]

Yes.

Although thinking about it, it's wrong anyway since I haven't accounted for more than one 8 set being acheived in a given permutation.

You know what I'd do? I'd write a little program to solve it.

[sobrique.livejournal.com]

Well, I was thinking in terms of just doing lots and lots of 'random(40)' type calls, and summing and stuff.

But that'd be cheating.

[apostle13.livejournal.com]

I'm not familiar with EVE, but going on raw statistics and running a Monte Carlo simulation using the details given, I can tell you that 40 small guns are pretty much twice as effective as 10 large guns (given the uniformly random targeting system). This is across fleet sizes from 10-50, and will probably be even more effective for larger fleets. 20 medium guns have, predictably, intermediate effectiveness.
As far as I can see, there is no obvious scenario favouring large guns (not even if the ships can take more damage before being toasted), so unless there is some counter-balancing issue (cost or other resources), lots of small guns will always outperform a few big guns.
The Monte Carlo simulation was admittedly very "rough and ready", but I would say a factor of 2 difference in efficiency is *fairly* accurate across most scenarios.

[sobrique.livejournal.com]

Could I get you to give me a link, so I can proceed to grok monte-carlo?

[apostle13.livejournal.com]

The Monte Carlo method/approach is a bit of an umbrella term for a set of stochastic techniques.
I hastily knocked together a not-too-comprehensive bit of fortran code for your EVE scenario and then fiddled with it a bit to arrive at my analysis. The efficiency difference is less pronounced for ships which can take a lot of damage, but I didn't find *any* obvious scenarios where the big guns were better!
Basically, Monte Carlo is ideally suited to computational techniques, useful when the analysis is either impossible or, like me, you just can't be bothered with calculating the exact probabilities etc.

There are undoubtedly plenty of academic papers utilising Monte Carlo methods, but a good lucid introduction to the sort of technique involved, in my opinion, is the determination of pi. Try this link:

http://www.chem.unl.edu/zeng/joy/mclab/mcintro.html

[queex.livejournal.com]

In summary, bigger guns take longer to clean all the ships away, but the number of ships falls more steeply initially. To stop ships warping out, bigger guns are probably the way forwards.

I have R-code, if you're interested.

[queex.livejournal.com]

Of course, there may be wrinkles. If the ships can destroy the sentry guns, you'd need a more comprehensive approach. If all the targets are selected together, rather than one by one as the guns fire, then small guns lose much of their efficiency advantage over large ones.

[sobrique.livejournal.com]

I've just tried running it assuming 50 ships, 10 large guns, 4 pts of damage and a 'per ship' soak of 6, and it takes 36 iterations (30-40) to deplete the pool (removing if their cumulative damage exceeds 6, resetting otherwise).

With small guns, it's in the 1000-2000 range... Of course, I may be looking at something dubious here.

[queex.livejournal.com]

If you assume that ships repair fully after each pass big guns are so much better it's ridiculous. The reality is probably somewhere between gull repair and no repair.

[crashbarrier.livejournal.com]

In the past I have found that covering something, Porcupine style, with faster reacting guns tends to work well. but not so well against armada.s. as you can't punch armour fast enough, even with the number of guns in play.

What I found was have many smaller guns, and intersperse them witht he bigger heavier weaponry, the smaller guns then back up the heavier weaponry through their reaction time.

now if your guns all fire at the same speed and you can affoard it, go for covering your starbase with heavy weaponry and armour.

If the guns have differing rates of fire then mix em.. the interspersal gives you a better over all rate of fire and better covarage and if you get hit by an armada you can make it very expensive for them before you go...

(think Babylon 5 )

[the-g-man.livejournal.com]

Hmmm... I suspect the answers depends on exactly how many hits ships take to destroy. If 5 hits is the norm then you probably want a mixture. If 8 hits is the norm then big guns are the way. Generally using a higher granularity is better if you want peaks. Reducing granularity (smaller guns) is going to result in a more even distribution.

[sobrique.livejournal.com]

Targets are selected at a 30s 'cycle'. Multiple can select the same thing, even if it's overkill.
Guns are destroyable, but only in certain situations (which won't be applicable here).

[sobrique.livejournal.com]

Probably, it is. Each pass is hot on the heels of the last, however it 'lasts' 30 seconds, so gives a ship that's under fire and in trouble an opportunity to bug out.

[queex.livejournal.com]

Well, with that information, big guns are still a go. They look to be about thirty times more effective at cleaning house (with full repair), and slightly less effective than small guns with out repair.
Enemy ships decay more steeply are the outset in both cases.

[apostle13.livejournal.com]

OK, the factor of 2 is incorrect since I just calculated a kind of pure damage spread accumulation (no this isn't a technical term, it's mindless waffle) i.e. I did not correct for target depletion. Hell, they use a uniformly random targeting strategy, so I didn't assume *any* intelligence to their approach ;-)
Now I am presuming toasted ships are no longer viable targets, so the efficiency difference is reduced, but the small guns still seem to have a *slight* edge, particularly when the fleet is large (although I have a suspicion there may be a latent bug in my code/compiler, specifically the pseudo-random number generator intrinsic function). However, your factor of 1000 difference sounds a *little* odd too, but you may be considering game factors that I have neglected(?).
On-the-fly repairs and retreats are going to complicate matters, but you could presumably set up a "retreat" threshold value or something similar. It's often interesting to see when the "all or nothing" approach pays off, and when it does not!

[darkgodfred.livejournal.com]

You're not the only person who's been thinking about this. I've got two things to add, the first is easy, the second is hard. 1st, to insta-kill a BS is not 5 points, it's more like 25.

Second, a number of guns tagging a single target can be expressed as the birthday problem, ie how many people do I need for a 50% chance of two people sharing one. Re-expressed, how many guns do I need for a 50% chance of hitting one target of a blob twice. And I have a formula to approximate it, unfortunatly it's evil for anything more than doubletaps.

Now for double taps, given n = number of guns, d = number of ships then for a 50% chance of a double tap n = 1.2 * sqroot(d) or for a 95% chance then n = 2.5 * sqroot(d).

Now, to generalise. k = number of guns hitting the same target, p = probabilty. We can approximate using the formula

http://mathworld.wolfram.com/images/equations/BirthdayProblem/equation6.gif

Doesn't that look fun. Of course it also doesn't account for different gun sizes.

Anyway, the pages I found when looking into this are http://mathworld.wolfram.com/BirthdayProblem.html and http://mathworld.wolfram.com/images/equations/BirthdayProblem/equation6.gif

[sobrique.livejournal.com]

25 points? Well, I can re-run on that basis. I suspect that'll favour large guns even more though. (5 was the 'best case' for small guns, in that it took 2 larges, or only 5 smalls).

Lessee, arbitrary ship with 6k shield, 6k armour, 6k hull. (Is that reasonable?) a large arty loaded with DU does 5400, but split across Kin/therm/explosive. If we cheat and pretend average resistances (pretend 30%) because I'm thinking of distributing damage evenly we get 3780.

Hrm, I see your point. That's about 20 'points'.

I'm now scared, it's frighteningly easy to kill off a starbase with hit and fade attacks.

[jambon-gris.livejournal.com]

The traditional solution on battleships and so on is a mixture of big and small

eg North Carolina 9 16" guns 20 5" guns, pretty much the same for all ww2
american battleships

bismark 8 15" guns 12 6" guns and 16 4" guns (this seems wrong not sure I trust the web site)

vangaurd 8 15" guns 16 5.25" guns

What about range and ROF do big guns fire further and small guns fire faster/hit more often

personally I would forget medium guns unless you dont plan to mount any heavy or light. This may be solution if there is no range/rof issues

[sobrique.livejournal.com]

The stats of the different gun sizes are identical in terms of range and rate of fire.
The difference is that smaller guns are better able to hit. I'm still factoring that bit in to what I'm trying to figure out :)