Sample Page Title

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

It’s a little bit of an extended highway displaying how I derived this, so scroll to the underside when you simply need the tl;dr.

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

I’m additionally going to make a wierd 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, regardless that it offers us an unrealistic reply for some circumstances. That’s superb: we’ll use this unrealistic reply as a constructing block to work towards a realistically helpful derived reply.

The base 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{circumstances}
1, & textual content{if $x$ = Enemy Starting HP}
0, & textual content{in any other case}
finish{circumstances}$$

We can compute the values for flip $n$ from flip $n-1$ by summing two circumstances:

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

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

$$frac {textual content{Player Hit %}} {textual content{Player CP}} cdot sum_{i = textual content{Player Modifier} + 1}^{textual content{Player Modifier} + textual content{Player 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 variety of HP from -100 to +100, and as much as 63 turns – see the “Battle Sim” tab.

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

The bother is, we needed to do a metric crapton of calculations to get this quantity! Enough 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.

But we’re not executed – I did this to ascertain a floor fact information set that we are able to use to derive a detailed approximation that is simpler to compute, and confirm the accuracy of that worth.

This calculation is successfully a convolution filter utilized to the discrete chance distribution of enemy HP at every flip. You can see with every passing flip, the distribution will get an increasing number of smeared-out – and, due to the central restrict theorem, an increasing number of usually distributed. We’re going to use 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’m simulating, the imply and SD values we compute are now not reliable (although the full chance of being alive remains to be correct). To stave that off so long as potential, let’s give the enemy plenty of HP, say 100, and shrink the participant’s harm output, say we maintain CP = 10 and decrease Mod = 6. That offers us a very good 13 rows of reliable information 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’s to be anticipated, given we’ve the identical chance 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{Mean}_{textual content{enemy HP}}(n) = textual content{Enemy Starting HP} – n cdot E_text{participant harm}
textual content{the place}
E_text{participant harm} = left( textual content{Player Hit %} proper) left( textual content{Player Modifier} + frac {1 + textual content{Player CP}} 2right)
$$

The customary deviation follows the curve of a sq. root perform (that means linearly rising variance – once more, perhaps anticipated since we’re making use of the identical convolution every flip). We can compute that perform 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{Player Modifier} + 1}^{textual content{Player Modifier} + textual content{Player CP}}
left(textual content{Enemy Starting HP} – i – textual content{Mean}_{textual content{enemy HP}}(1)proper)^2 frac {textual content{Player Hit %}} {textual content{Player CP}} &+ left(textual content{Enemy Starting HP} – textual content{Mean}_{textual content{enemy HP}}(1)proper)^2 cdot (1 – textual content{Player Hit %})\
= &sum_{i = textual content{Player Modifier} + 1}^{textual content{Player Modifier} + textual content{Player CP}}
left(E_{textual content{participant harm} – i}proper)^2 frac {textual content{Player Hit %}} {textual content{Player CP}} &+ left(E_{textual content{participant harm}}proper)^2 cdot (1 – textual content{Player 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 features:

$$start{align}
textual content{Mean}_{textual content{enemy HP}}(n) &= textual content{Enemy Starting 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 chance that the enemy is useless by the point $n$ turns have handed, utilizing the cumulative distribution perform 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 Function – this cannot be expressed by way of elementary features, however an ordinary statistics library ought to include an implementation you should use.

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

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

But this nonetheless is not fairly the reply we’re searching 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 chance that the enemy dies earlier than the participant character does. But we are able to use this $P_text{enemy useless}(n)$ perform to get that.

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

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

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

Then a way to compute the chance 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 pPlayerUseless = playerDeath.ChanceToBeDeadAfter(turnsCounted);
        double pEnemyUseless = enemyDeath.ChanceToBeDeadAfter(turnsCounted);

        double pPlayerDiesThisFlip = pPlayerUseless - pPlayerAlreadyDead;
        double pEnemyDiesThisFlip = pEnemyUseless - pEnemyAlreadyDead;

        pPlayerWins += (1 - playerAlreadyDead) * pEnemyDiesThisFlip;
              
  
        pEnemyWins += (1 - pEnemyUseless) * pPlayerDiesThisFlip;

        pPlayerAlreadyDead = pPlayerUseless;
        pEnemyAlreadyDead = pEnemyUseless;

        double pStillGoing =  1 - pPlayerWins - pEnemyWins

        expectedTurnCount += (pBattleOngoing - pStillGoing) * turnsCounted;

        pBattleOngoing = pStillGoing;
    }

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

Couldn’t fully escape iteration in the long run, however now our computation is proportional to the anticipated period of the battle (in all probability within the dozens of turns).

All this being mentioned, myself, I’d in all probability nonetheless implement this the Monte Carlo method (and have, once I wanted battle predictions previously). I simply did this as a result of I used to be nerd sniped and needed to show it could possibly be executed.

The motive I might not advocate implementing it this fashion is that the majority of what I’ve executed above is non-obvious, making it onerous to identify an error if I’ve made one (I in all probability have!), and brittle: it solely works for precisely the battle mechanics you have described. If you later resolve to alter your mechanics, add a brand new particular skill, and so on., then you must re-do this entire derivation to account for the brand new impact.

With the Monte Carlo strategy, when you architect it proper, you should use precisely the identical code for each regular battle decision and the prediction loop: so any change you make to your battle mechanics routinely updates your predictions too! That’s an enormous win, and doubtless price even a number of milliseconds of additional computation. (Especially 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)