> Programming
If you use a system that computes the best combination of items (chips and weapons) to deal damage to your opponent, you probably have your own way of estimating the damage of the combination you are studying: if you are pessimistic, you might take the sum of each item's minimum damage; if you are more neutral, maybe the sum of the average damage, and so on.
The goal of this page is to give you some notions of probability so you can study the probability distribution of the damage of such a "combo" in finer detail.
Warning: this article requires some math. At least high-school integral calculus, and preferably some basic probability too.
> 1. Motivation >2. Random draw when using a chip or a weapon >3. Direct approach >4. Continuous approach > 4.1. Principles > 4.2. Probability density of an item > 4.3. Convolution > 4.3.1 Introduction: the discrete case > 4.3.2 The continuous case > 4.3.3 A few properties > 4.4. Practical computation in LeekScript > 4.4.1 Combos in Leek Wars: simplifications from the context > 4.4.2 Symbolic computation: polynomials > 4.4.3 Piecewise-defined functions > 4.4.4 Convolution > 4.4.5 Critical hits: sum of two boxes >5. Handling absolute shields and fixed-damage items: mixed distributions > 5.1. Absolute shield: an atom at 0 > 5.1.1 Mixed distributions > 5.1.2 Dirac delta at 0 > 5.2. Fixed-damage items and critical hits: atoms elsewhere > 5.2.1 Critical hits and atoms > 5.2.2 Dirac delta at any point > 5.3. Computation in LeekScript >6. Cumulative distribution function and probability tools > 6.1 Definition and computation > 6.2 Usage >7. Remarks
Getting the average damage of a combo isn't very hard. However, you may want something more precise than the average: if you are trying to guarantee a minimum amount of damage (for example to have a good chance of killing), the average won't help you much.
Let's take an example: your opponent has only 430 life points left and 155 absolute shield, and you have 400 strength and no agility (so no chance of landing a critical hit). You have picked two combos that can kill the opponent: using your Rhino three times, or using your Rifle twice.
Indeed, the maximum damage dealt by three uses of the Rhino is: 3 * (64 * (1 + 400/100) - 155) = 495 and the maximum damage dealt by two uses of the Rifle is: 2 * (79 * (1 + 400/100) - 155) = 480 which is above 430 in both cases, for a similar TP cost (let's assume you have 15, with the Rhino already in hand).
Computing the average damage, which works the same way, gives 450 for the Rhino as well as for the Rifle. All the average tells us is that both the Rhino and the Rifle have more than a 50% chance of killing the opponent. But that doesn't help us pick the combo most likely to be lethal.
So if we want to maximize our chances of killing the opponent, we need more precise information.
> Spoiler: here, the Rifle has the better chance, with a 94.4% chance of killing, against 90.4% for the Rhino.
This fairly simple case may seem of little interest, and perhaps rather intuitive. The tools presented below let you handle more varied combos, as well as the chance of critical hits, whose effect on damage probabilities is sometimes less obvious.
Finally, note that this probability study can have other uses (healing, for example: you can look for the best healing combo under conditions such as "don't heal more than the number of missing life points"). I'm only presenting the tool here; it's up to you to use it as you see fit.
Each time a weapon or a chip is used, the game makes one and only one random draw (between 0 and 1) for all its effects. The value of each effect is then given by: value = min_value + draw * (max_value - min_value) where draw is the number between 0 and 1 that was drawn.
This random draw picks a float between 0 and 1 with a uniform probability: no float is more likely to come up than any other.
When you use an item, you can compute the probability of each possible result: after all, since the draw is uniform, every result (except the extreme ones, which actually have half the probability of the others) is equally likely. Indeed, each value k comes up if the result before rounding is between k-0.5 and k+0.5, except for the minimum (the draw can't give a lower value, so only half as many floats round to the minimum: those between k and k+0.5) and the maximum (this time the draw can't give a higher value; same reasoning).
So, using the Spark chip with 400 strength, you can deal between 40 and 80 damage, and each integer between these values has a probability of 1/40 = 0.025 (except 40 and 80, whose probability is 0.0125).
And if you want to chain several items, you can in theory compute the probability of each possible result. For example, with no strength, no agility and no shield on the target, for a combo made of two uses of the Pistol, the probability of dealing 33 damage can be computed by finding every possible way to get 33 and adding up the probabilities of each of these ways. The computation would look like this:
p = 0.02 + 0.04 + 0.04 + 0.02 = 0.12 (a 12% chance).As you can guess, even though there are faster ways to go about it, this method is going to be tedious. Indeed, I picked two items with a fairly small damage range and gave my leek no strength so as not to have too many cases to handle. Imagine (or compute!) the number of possible values when hitting with the Axe with 500 strength!
So this method is tricky to use in practice. It can be done algorithmically, but the cost is likely to be high as soon as you have many items or fairly wide damage ranges.
One way to handle such a large number of possible values is to act as if the random draw could take any real value between 0 and 1, not just floats. This is technically wrong, but the difference between the two is quite small given the huge number of possible floats between 0 and 1 (which is necessarily finite because of the encoding used, but still very large).
The tool we are going to use is called a density function: it is a function that describes the behavior of a random quantity taking values in the set of real numbers (or a subset of it, here an interval).
> Note for nitpicky mathematicians: OK, OK, a few conditions would be needed... I'll talk about distributions with atoms later on, and I won't talk at all about singular distributions, but hey... it's hardly relevant here.
Right... A bit of math to introduce the concepts.
A probability density is a function f that is always nonnegative and whose integral is 1. It represents the behavior of a random variable X (here, the damage of a combo) as follows:
> The probability that X takes a value between two numbers a and b is given by the integral of f between a and b. In other words, !defDensity
Example (with the density of the combo of two Sparks with no characteristics):
Note that the function f is indeed nonnegative and that its integral between the two ends is indeed 1.
Computing the integral between 19.5 and 25.5 tells us that the combo has a probability of 0.574... (i.e. 57.4%) of dealing between 19.5 and 25.5 damage, so, after rounding, between 20 and 25 damage.
The conditions on the function are explained as follows:
If we have a way to represent such a function for a combo (which is what the rest of this article is about), we can then deduce quite a lot of information from it, for example:
d is the integral of the density function between d-0.5 and d+0.5, since all the numbers between these two values round to d:
d damage is the integral between d-0.5 and the maximum:So the idea is to represent a probability distribution not by every possible value and its probability, which is cumbersome to handle, but by a function from which we can extract that information. And in the case of Leek Wars probabilities, these functions turn out to be fairly simple to handle (see the practical part below).
OK, that's all very nice, but how do we find the density functions in the cases we care about (i.e. damage probabilities in the game)?
Let's start with a single item, without taking the leeks' characteristics (agility, strength, shields) into account for now.
Since every float (or at least every float that can come up...) in the item's damage range has the same probability, we'll use box-shaped density functions for items:
Notice that the height and the width of the box are linked: since the integral must be 1, the height of the box is given by the item's damage values: height = 1/(max_value - min_value) which, for Spark with no strength or agility and no shield on the target, gives 1 / (16 - 8) = 1/8 = 0.125, as you can see on the graph above.
Taking strength into account is then no big deal: you just compute the range of possible damage and build the matching box. So, still for Spark but with 400 strength, the minimum damage is 40 and the maximum 80, which gives a box from 40 to 80 with a height of 1/40 = 0.025:
To handle such objects in LeekScript, you would need to store two values (for example the minimum and maximum values, since the height of the box can be deduced from them). However, it will turn out to be useful later on to handle a somewhat more general class of functions. So I'll discuss implementation ideas in LS a bit further down.
Note that an item with fixed damage can't be represented by a box. If you have no chance of a critical hit, no problem: the damage is fixed, you can just handle it separately. The case of fixed damage with a chance of a critical hit is covered further down.
The "Convolution" article on Wikipedia
The problem is then the following: if I chain several items, how can I compute the matching density function from the densities of each item?
As an example, let's go back to the discrete case, using the combo of two Pistol shots (with no strength, agility or shield) from earlier.
If I plot the probabilities of the different values for one shot, I get this:
(Careful: I've temporarily gone back to representing probabilities value by value; this is not a density function.)
The probability of getting 33 damage is then, as we saw earlier, the sum of the probabilities of getting the pairs of values (15, 18), (16, 17), (17, 16) and (18, 15).
We can then lay out the computation graphically as follows:
The first graph shows the probability of each value of the first shot, with the values too high for the sum to reach 33 shown in black. The second one shows the probability of the values of (33 - result of the second shot): so, if the draws make the first shot deal 15 and the second one 18, the matching values on my two graphs are vertically aligned (at x = 15).
To do the computation, we can then take the sum of the products of aligned values:
The first graph was built directly, but what about the second one? It is obtained geometrically as follows: if we want a sum S (here 33), we reflect the first graph across the y-axis, then shift the resulting graph S units to the right.
And what about probability densities? The same method will answer our problem. We just need to describe it for densities rather than for discrete distributions, but the principle stays the same.
Given two random variables X and Y, with density functions f and g, and a number s, to find the probability that X+Y takes the value s, we proceed as follows:
For example, with the two density functions shown below, and s = 7:
Of course, the result depends on the desired sum s. The convolution (or convolution product) of f and g is then the function f * g that maps a number s to the result of the computation above.
We can give a formula for it: !ConvolutionFormula but in practice it's mostly the construction that we'll use.
So far we have only shown how to compute the value of f * g at a point s. If we want to use f * g as the density function of the sum of the two random variables, we need an expression of this function that holds for every s.
Depending on what the functions look like, this step can be more or less hard. Here, the functions we'll have to handle stay fairly simple, but they have the particularity of being piecewise-defined. In the previous example, we can proceed as follows:
The crucial property here (I've more or less said it already, but now it's explicit):
> Let X and Y be two independent real random variables, with densities f and g respectively. Then the sum S = X + Y is a random variable with a density, and its density is f * g. (This can be extended to mixed distributions by using generalized functions, also called distributions, see further down, but densities are what we mainly care about here.)
The convolution product has a few properties that can come in handy.
> It is commutative: f * g = g * f.
So you can do the convolution in whatever order you like; it doesn't matter.
> It behaves well with addition: f * (g+h) = (f * g) + (f * h).
So you can split functions into sums of several simple pieces, convolve with each piece, and add up the results.
> It behaves well with multiplication by constants: f * (a x g) = a x (f * g).
So you can "pull" multiplicative constants out of the product.
> It is associative: (f * g) * h = f * (g * h).
Thanks to associativity and commutativity, you can do a series of convolutions one at a time in any order you like (in our case, this means that the damage probabilities of a combo don't depend on the order in which the items are used, which is true as long as you don't use any buffs in between, of course).
Let's start with a crucial remark (since it greatly simplifies the computations): each of our items has a box function as its probability density, and the convolution of several such functions is necessarily a piecewise-defined function in which every piece is polynomial.
More precisely, the convolution of k boxes is always made of polynomial pieces of degree at most k-1.
Moreover, as we gradually add items to our combo, we are computing convolutions with boxes, which conveniently is fairly simple: in the construction of the product shown earlier, we can "move" the box according to the desired sum s, so the integrals to compute are only ever integrals of the density already computed between two bounds that depend on s, multiplied by the height of the box:
Example here with g the density function obtained for two Sparks with no strength, and the box for a third use of the same chip.
So, for Leek Wars, we will need to:
I'll present the main principles here, not a ready-made implementation. You can adapt this however you like (create a Polynomial class if you want to do OOP, work directly with arrays otherwise, or any other approach you find relevant).
To represent a polynomial function f(x) = a_n * x**n + ... + a_1 * x + a_0, you just need to store its coefficients. So you can represent f by the array [a_0, a_1, ..., a_n].
From there, the useful math operations aren't very hard to implement:
f(x) = a_n * xn + ... + a_1 * x + a_0 and g(x) = b_p * xp + ... + b_1 * x + b_0, you just add their coefficients (careful, f and g don't necessarily have the same degree):f + g is represented by an array of the form [a_0 + b_0, ..., a_p + b_p, a_(p+1), ..., a_n] (here I took `p
The functions we get when computing convolutions are defined piecewise: so we need to represent such functions in LS. To do this, you can store a list of the pieces (which are polynomials in our case) along with the lower and upper bounds of the domains where they apply. Again, there are several ways to do this (OOP, arrays directly, ...); I'll just present the operations you'll need to be able to perform:
Finally, and this is the hard part, you need to be able to compute the convolution of such a function with a box.
If you've coded everything above, a good chunk of the work is done. The difficulty in computing the convolution of a piecewise polynomial function with a box mainly lies in finding the breakpoints of the resulting function.
Let's go through an example computation (well, the start of it...) in a case that is still simple: we have the probability density g for two uses of Spark and we add one Pistol shot (with no strength), whose density is a box f. Let's compute, step by step, the new density g * f (or f * g, it's the same) of the combo 2 Sparks + 1 Pistol:
Critical hits aren't really a problem. Indeed, the probability density of an item that can land a critical hit is made of two boxes.
More precisely: consider an item with a probability p of landing a critical hit. Let f be the box function of this item with no chance of a critical hit, with a minimum a and a maximum b. Then the density with critical hits is given by (1-p)f + pg, where g is the box with minimum CRITICAL_FACTOR * a and maximum CRITICAL_FACTOR * b.
Then the convolution with a density function h can be written: !critFormula so you can get by with two convolutions of h with boxes, then a sum of two piecewise-defined functions.
So far, I haven't talked about what happens if the opponent has shields. The relative shield is no problem at all: it just applies a multiplier to the damage, like strength, and is handled the same way (the boxes will just be closer to 0 and narrower, that's all). The absolute shield, on the other hand, is a real problem.
Indeed, it forces us to deal with probabilities where an exact number has a nonzero probability of coming up. For those who aren't used to it: yes, it's a bit strange at first, but with probability densities, a precise number always has a probability of... zero. When I introduced the tool, I said that to get the probability that the combo deals between a and b damage, we use the integral of the density from a to b. And in our case, we could take as the probability that the combo deals s damage after rounding the integral between s - 0.5 and s + 0.5. But before rounding, the probability of landing on a precise sum is the integral... between s and s, which is always 0.
To give an analogy: if I give you a plank, a saw and a tape measure and ask you to cut a length of 50 cm, you'll end up with a plank that is (unless you're really clumsy) about 50 cm long. But with a more precise measuring tool, does your plank stand any chance of being exactly 50 cm? To the millimeter? To the micron? Unless I've come across a saw virtuoso, if I measure finely enough, I'll always find a small difference. The same idea applies here: I can have a nonzero probability of landing on a value once rounded, but without rounding, no chance.
And yet the absolute shield has the annoying property of giving a precise value, 0, a nonzero probability of coming up: if I use a Spark (with no strength) on an opponent protected by a Helmet (with no resistance), I'll most likely deal 0 damage. To deal (nonzero) damage, the game's random draw would indeed have to give me damage between 15.5 and 16, which is rounded to 16 and, once the shield is taken into account, brought down to 16 - 15 = 1. For every other draw, the damage is 0.
So we'll have to deal with these nonzero probabilities of dealing 0 damage, and for that, densities alone offer no solution: there is no density function whose integral between 0 and 0 is nonzero.
> Note for mathematicians and physicists: yes, I'm going to talk about the Dirac delta, but it isn't a function.
So we'll need to handle probability distributions given by a density function plus probabilities attached to certain values (zero in particular, because of the shield, but we'll see that fixed-damage weapons cause the same kind of phenomenon).
> A probability distribution is said to have an atom at a point a if the probability of a is nonzero.
In general, a probability distribution can be decomposed (I'm skipping the few assumptions to check... no problem here) into several parts: a discrete part, a part described by a density, and a weird part that doesn't concern us here. If you're up for it... see the Radon–Nikodym theorem (this gets into somewhat complicated math, but understanding this theorem is completely unnecessary for what follows; I'm just mentioning it in passing).
From now on, I may say "density" for a function whose integral isn't 1. That's an abuse of language! But the idea stays the same: representing the (absolutely) continuous part of a distribution by a function.
Right, without going into the complicated details... Here, on top of a density describing the probabilities outside the atoms, we'll need to keep the atoms and their probabilities. And propagate that information when we add an item to the combo.
For example, take the case of two Sparks with 400 strength, against an opponent with 60 absolute shield (and 0 relative shield). Without a shield, a Spark would deal between 40 and 80 damage, represented by the box !1Spark400Strength
However, with the 60 absolute shield, the damage is reduced by 60, so the box is shifted 60 to the left. But damage can't be negative: the left half of the box therefore gets "squashed" onto the value 0. So we get a probability represented by two things:
f:Let's add the second Spark. We'll need to distinguish several cases:
0.5 * 0.5 = 0.25;We then keep the following information:
Note that the resulting function isn't continuous. Unlike the case without atoms, where the function got smoother as items were added, this is no longer guaranteed!
Mathematically, this object can be represented with a strange tool: the *Dirac delta* at 0, written δ, which is an object (it can't be a function...) that is 0 everywhere except at 0, and whose integral is 1. I won't formalize this here, but this "distribution" would give a more complete formalism to this notion of a probability of dealing 0: we can say that the probability is represented by 0.25δ + g (where g is the function plotted above).
The Dirac delta conveniently has a very useful property for convolutions: for any function h, we always have δ * h = h * δ = h.
The four previous cases can then be summed up in a single formula: !ConvoDiracs We do find the 0.25 probability of dealing 0, and we get a simple formula to compute the function for the remaining cases.
Note that when you compute the damage probabilities of a combo, the probability of dealing 0 damage disappears as soon as you add an item that can't deal 0 (makes sense, right?). So you only have a δ term until you add such an item; after that, you only have a true density (with integral 1).
Another case can give a nonzero probability to a precise value: fixed-damage items (Katana, Illicit Grenade Launcher, Devil Strike and Punishment at the time of writing).
Without any chance of a critical hit, a fairly simple approach would work: compute the fixed damage of the combo being studied and shift the density function obtained with the other items by that amount. The chance of a critical hit, however, breaks this approach, since the "fixed" damage isn't really fixed anymore (two possible values)... We then end up with two atoms.
One way to go about it is, for each fixed-damage item added, to distinguish two cases:
and we take the sum of the two probability distributions obtained this way, weighted by the probability of a critical hit.
So we need to handle the sum of two distributions that may have atoms: the resulting distribution has atoms at every point where either distribution had an atom.
An example to make this clearer: the combo Spark + Katana, with 400 strength, 400 agility (so a 0.4 probability of a critical hit), and 50 absolute shield on the target leek.
So the probability distribution of this combo has two atoms. If we add a third item, we'll therefore have to handle three cases:
Again, this can be formalized mathematically with well-placed Dirac deltas: an atom located at a point a with probability p_a is represented by a Dirac spike at a, weighted by the probability p_a, written p_a δ_a.
The previous computation can then be laid out as follows:
So, for the distribution of the combo, we get: !SparkKatanaCritASCalc
And the convolution with a Dirac spike located at a point a amounts to a shift to the right by a. So we do get back the probability distribution computed earlier.
The hardest part should already be done if you've coded the convolution. You'll just need to add an extra layer here: a probability distribution is no longer represented only by a piecewise polynomial function, but by a set of atoms with their probabilities on top of such a function.
So all you'll need to code is a way to keep track of these atoms, and a convolution function that takes them into account by separating several cases (atom * atom, atom * density, density * atom, density * density), then adds up the resulting distributions.
So you should manage with the tools you've already coded: translating a function by a given vector, convolving two densities, adding piecewise-defined polynomial functions.
So we have a way to compute the probability distribution of a random variable (representing the damage dealt) as a set of atoms plus a "density" function (not quite: its integral is 1 minus the probabilities of the atoms; it would be more accurate to say it's a linear combination of a distribution with a density and a discrete distribution... never mind).
From there, we can extract various pieces of information. We said that with a density, the probability of dealing damage between a and b was given by the integral of the density between a and b. Here, with atoms, we'll instead take the sum of the integral of the "density" between a and b and of the probabilities of the atoms located between a and b.
Rather than computing integrals over and over, it can be useful to compute what is called the cumulative distribution function (CDF) of the distribution.
> The cumulative distribution function of the probability distribution on R of a random variable X is the function that maps a number x to the probability that the variable X takes a value less than x, or equal to x. In other words: !CDFDefinition
If a probability distribution is given by a density D, the CDF is then simply the antiderivative of D whose limit at -infinity is 0. > For nitpicky mathematicians: well... OK, not an antiderivative in the strict sense. If the density is a box, the CDF isn't differentiable on all of R, so it isn't an antiderivative...
For a probability distribution with a "density" and atoms, you'll have to go step by step:
For example, with the Spark + Katana combo from the previous example, we had a function D: !SparkKatanaCritAs and two atoms, one at 335 with probability 0.09 and the other at 450.5 with probability 0.06. So the CDF is built by taking:
From the CDF, it's fairly easy to compute probabilities that may be relevant. If F is the CDF of a probability distribution, then: !ProbabilitiesFromCDF
Computing this function symbolically therefore saves you from computing integrals every time you need a probability.
It is needlessly complicated to compute the expected value of the damage dealt from the distribution obtained: the expected damage of the whole combo is simply the sum of the expected values of the items taken one by one.
Likewise, since the successive rolls when using items are independent, the standard deviation can be computed directly from the standard deviations s1, s2, ... of the different items with the formula s = sqrt(s12 + s22 + ...)
So the point of having the distribution doesn't lie in computing these indicators.
___ ___ Note: the illustrations were made with the GeoGebra software. ___ References:
Philippe Barbe and Michel Ledoux, Probabilité, EDP Sciences (2007) (in French)
For those who already have a good level in math, a classic reference on measure theory (be warned, it's a tough read): Walter Rudin, Analyse réelle et complexe (French translation), published by Masson (1975, 1977) or Dunod (1998) or in English: Walter Rudin, *Real and Complex Analysis*, McGraw-Hill (1987)
Impossible de charger les données du jeu.
Vérifiez votre connexion et réessayez.
