likelihood – The right way to calculate Likelihood of Success in a turn-based battle with probability to hit and harm roll + harm modifier?

I began on the lookout for a extra deterministic approach to compute this, with out counting on Monte Carlo simulation, gathering statistics of a pattern of randomized battles.

It’s kind of of an extended street displaying how I derived this, so scroll to the underside in the event you simply need the tl;dr.

To start out, I requested “What’s the likelihood that the enemy has precisely $x$ HP after $n$ turns?” Let’s name the operate that solutions this query $P_{textual content{enemy HP}}(x, n)$

I am additionally going to make an odd simplification, which is to imagine the HP worth $x$ can go to zero or unfavorable and the battle retains going anyway. This avoids special-casing zero, though it offers us an unrealistic reply for some instances. That is tremendous: we’ll use this unrealistic reply as a constructing block to work towards a realistically helpful derived reply.

The bottom case $P_{textual content{enemy HP}}(x, 0)$ is simple to calculate, since that is the state earlier than anybody has made a transfer:

$$P_{textual content{enemy HP}}(x, 0) = start{instances}
1, & textual content{if $x$ = Enemy Beginning HP}
0, & textual content{in any other case}
finish{instances}$$

We will compute the values for flip $n$ from flip $n-1$ by summing two instances:

• If the participant misses, then the prospect the enemy has $x$ HP after this spherical is similar as the prospect that they had $x$ HP on the finish of the spherical earlier than. So that offers us a $(1 – textual content{Participant Hit %}) cdot P_{textual content{enemy HP}}(x, n-1)$ time period.

• If the participant hits, then the prospect the enemy has $x$ HP after this spherical is a sum. For every worth $i$ from $(textual content{Participant Modifier} + 1)$ to $(textual content{Participant Modifier} + textual content{Participant CP})$ (ie. their min to max harm), we add up $ frac 1 {textual content{Participant CP}}P_{textual content{enemy HP}}(x+i, n – 1)$ (ie. the prospect the enemy had precisely $i$ extra HP final spherical, and the participant rolled precisely $i$ harm). That provides us a time period like this:

$$frac {textual content{Participant Hit %}} {textual content{Participant CP}} cdot sum_{i = textual content{Participant Modifier} + 1}^{textual content{Participant Modifier} + textual content{Participant CP}}P_{textual content{enemy HP}}(x + i, n – 1)$$

Now we are able to recursively calculate $P_{textual content{enemy HP}}(x, n)$ for any $n geq 0$.

I carried out this in Google Sheets for a spread of HP from -100 to +100, and as much as 63 turns – see the “Battle Sim” tab.

We will sum the values for all cells with HP > 0 in a row to get the likelihood the enemy survives $n$ turns.

The difficulty is, we needed to do a metric crapton of calculations to get this quantity! Sufficient in order that doing many rounds of Monte Carlo sims might be simply as quick, and has the benefit of being a lot easier to motive about.

However we’re not completed – I did this to determine a floor reality knowledge set that we are able to use to derive an in depth approximation that is simpler to compute, and confirm the accuracy of that worth.

This calculation is successfully a convolution filter utilized to the discrete likelihood distribution of enemy HP at every flip. You possibly can see with every passing flip, the distribution will get increasingly more smeared-out – and, because of the central restrict theorem, increasingly more usually distributed. We will exploit that, to see if we are able to usefully approximate HP as a bell curve with a imply and customary deviation.

Calculating the imply and customary deviation of this distribution at every flip is a bit tough – as soon as the left tail of the distribution goes previous the bottom unfavorable HP I am simulating, the imply and SD values we compute are not reliable (although the entire likelihood of being alive continues to be correct). To stave that off so long as doable, let’s give the enemy a number of HP, say 100, and shrink the participant’s harm output, say we preserve CP = 10 and decrease Mod = 6. That provides us 13 rows of reliable knowledge factors to test our work.

The very first thing we discover is that the imply decreases linearly: precisely the identical delta in each reliable row. That is to be anticipated, given we’ve the identical likelihood distribution of harm dealt each flip. So we are able to compute the imply HP after $n$ turns utilizing the participant’s anticipated harm dealt, $E_text{participant harm}$:

$$
textual content{Imply}_{textual content{enemy HP}}(n) = textual content{Enemy Beginning HP} – n cdot E_text{participant harm}
textual content{the place}
E_text{participant harm} = left( textual content{Participant Hit %} proper) left( textual content{Participant Modifier} + frac {1 + textual content{Participant CP}} 2right)
$$

The usual deviation follows the curve of a sq. root operate (which means linearly growing variance – once more, perhaps anticipated since we’re making use of the identical convolution every flip). We will compute that operate like so:

$$
textual content{SD}_{textual content{enemy HP}} = sqrt {n cdot Delta sigma ^2}
textual content{the place}start{align}
Delta sigma^2 = &sum_{i = textual content{Participant Modifier} + 1}^{textual content{Participant Modifier} + textual content{Participant CP}}
left(textual content{Enemy Beginning HP} – i – textual content{Imply}_{textual content{enemy HP}}(1)proper)^2 frac {textual content{Participant Hit %}} {textual content{Participant CP}} &+ left(textual content{Enemy Beginning HP} – textual content{Imply}_{textual content{enemy HP}}(1)proper)^2 cdot (1 – textual content{Participant Hit %})\
= &sum_{i = textual content{Participant Modifier} + 1}^{textual content{Participant Modifier} + textual content{Participant CP}}
left(E_{textual content{participant harm} – i}proper)^2 frac {textual content{Participant Hit %}} {textual content{Participant CP}} &+ left(E_{textual content{participant harm}}proper)^2 cdot (1 – textual content{Participant Hit %})
finish{align}$$

So as soon as we calculate the constants $E_text{participant harm}$ and $Delta sigma^2$, we are able to compute the imply and customary deviation of our HP distribution on any flip $n$ with quite simple capabilities:

$$start{align}
textual content{Imply}_{textual content{enemy HP}}(n) &= textual content{Enemy Beginning HP} – n cdot E_text{participant harm}\
textual content{SD}_{textual content{enemy HP}} &= sqrt {n cdot Delta sigma ^2}
finish{align}$$

That lets us estimate the likelihood that the enemy is useless by the point $n$ turns have handed, utilizing the cumulative distribution operate of the traditional distribution:

$$P_text{enemy useless}(n) = frac 1 2 left[
1 + text{erf}left(
frac {0 – text{Mean}_text{enemy HP}(n)}
{ text{SD}_text{enemy HP}(n) sqrt 2}
right)
right]$$

…the place $textual content{erf}$ is the Error Perform – this cannot be expressed by way of elementary capabilities, however an ordinary statistics library ought to comprise an implementation you should utilize.

Within the Google Sheets instance, the likelihood of enemy loss of life calculated this manner very carefully matches the one we computed exhaustively – differing by lower than 1% at worst (ie. it underestimates the prospect of dying by the tip of 16 as 9.12% on this instance, when the true worth to throughout the accuracy of our double precision floating level math is 9.98%)

So, I would say that offers us an excellent approximation of the true probability of being useless. Observe that since we’re lumping collectively the entire a part of the distribution <= 0, the unrealism I referred to as out earlier of pretending the enemy may have unfavorable HP values will get erased.

However this nonetheless is not fairly the reply we’re on the lookout for, as a result of it assumes the participant character is immortal and has no probability to die and cease dealing harm. What we actually need is the likelihood that the enemy dies earlier than the participant character does. However we are able to use this $P_text{enemy useless}(n)$ operate to get that.

Let’s assume we have constructed an information construction with a constructor like:

DeathPredictor(int hp, int dp, int opponentCP, int opponentMod)

This may compute and cache the constants we want, and expose a double DeathPredictor.ChanceToBeDeadAfter(int turnNumber) technique that implements the likelihood operate mentioned above.

Then a way to compute the likelihood of victory would possibly look one thing like this (assuming the participant character acts first every flip):

float ChanceOfPlayerWin(Character participant, Character enemy, out double expectedTurnCount) {
    var playerDeath = new DeathPredictor(participant.hp, participant.dp, enemy.cp, enemy.weaponModifier);
    var enemyDeath = new DeathPredictor(enemy.hp, enemy.dp, participant.cp, participant.weaponModifier);

    double pPlayerAlreadyDead = 0;
    double pEnemyAlreadyDead = 0;
    double pBattleOngoing = 1;

    int turnsCounted = 0;

    double pPlayerWins = 0;
    double pEnemyWins = 0;

    whereas(pBattleOngoing > CHANCE_THRESHOLD && turnsCounted < TURN_LIMIT) {
        turnsCounted++;

        double pPlayerDead = playerDeath.ChanceToBeDeadAfter(turnsCounted);
        double pEnemyDead = enemyDeath.ChanceToBeDeadAfter(turnsCounted);

        double pPlayerDiesThisTurn = pPlayerDead - pPlayerAlreadyDead;
        double pEnemyDiesThisTurn = pEnemyDead - pEnemyAlreadyDead;

        pPlayerWins += (1 - playerAlreadyDead) * pEnemyDiesThisTurn;
              
  
        pEnemyWins += (1 - pEnemyDead) * pPlayerDiesThisTurn;

        pPlayerAlreadyDead = pPlayerDead;
        pEnemyAlreadyDead = pEnemyDead;

        double pStillGoing =  1 - pPlayerWins - pEnemyWins

        expectedTurnCount += (pBattleOngoing - pStillGoing) * turnsCounted;

        pBattleOngoing = pStillGoing;
    }

    return (float)(pPlayerWins / (pPlayerWins + pEnemyWins));
}

Could not completely escape iteration ultimately, however now our computation is proportional to the anticipated length of the battle (most likely within the dozens of turns).

All this being stated, myself, I would most likely nonetheless implement this the Monte Carlo method (and have, after I wanted battle predictions up to now). I simply did this as a result of I used to be nerd sniped and wished to show it might be completed.

The rationale I’d not suggest implementing it this manner is that the majority of what I’ve completed above is non-obvious, making it laborious to identify an error if I’ve made one (I most likely have!), and brittle: it solely works for precisely the battle mechanics you’ve got described. When you later determine to vary your mechanics, add a brand new particular capacity, and so on., then it’s important to re-do this complete derivation to account for the brand new impact.

With the Monte Carlo method, in the event you architect it proper, you should utilize precisely the identical code for each regular battle decision and the prediction loop: so any change you make to your battle mechanics mechanically updates your predictions too! That is an enormous win, and doubtless value even a number of milliseconds of additional computation. (Particularly if you are able to do this on a background thread and conceal the latency with a UI animation, so the participant does not discover even the slightest hitch when a brand new battle prediction is being computed)