4
\$\begingroup\$

I'm coding a choice-driven role-playing game and I want to give the player a percentage of his success chance in winning a battle before he chooses to start it. However, I have no clue how to make this calculation. I'd really appreciate any guidance you can provide!

The battle system is a simplified version of D&D battles:

  1. Battles are turn-based and always 1vs1 (Player vs Enemy).
  2. Both have HP, CP, DP (Health, Combat and Defense Points) and a Weapon Modifier.
  3. Before an attack, the attacker has to roll a Hit Roll (1d20). The result + his Modifier is compared against the target's DP. If the value is equal or higher, the attack will hit.
  4. Then I calculate the Damage inflicted with a Weapon Roll, which uses the weapon die (the die is equivalent to the CP value, so if CP = 10, the die is 1d10) + the Modifier.

I need to calculate the chance the Player will be able to land enough hits to kill the Enemy before he kills him. I can calculate the Chance to hit by using this formula provided by the D&D community, but I also need to take into account the rest of the variables:

Chance to hit = ((21-(Target’s DP-(Attacker's Modifier))) / 20) * 100

*21 because: 20 = always hit, 1 = always miss

Here's an example:

Player Enemy
DP 10 20
CP 10 8
HP 80 60
Modifier 8 5
Chance to hit 45% 80%
Avg. damage 9 7

The final result should be a single percentage. For example: Battle success chance = 47%


Edit:

I simulated 100 battles as @Zibelas suggested to get the result. However, I'd still prefer to find a single formula to get the succes percentage, for efficiency reasons...

enter image description here

\$\endgroup\$
5
  • 2
    \$\begingroup\$ The lazy way when you are stuck and can't figure out the math is to simulate 100 battles and just display the win rate. That amount of battles won't even be noticeable for the player and you can use the real dmg as well instead of average \$\endgroup\$
    – Zibelas
    Sep 10, 2022 at 8:47
  • \$\begingroup\$ I thought it would be resource inneficient to simulate 100 battles in-game, specially since I want to recalculate the value after each turn. But I coded it and it just takes 1 ms to do 100 battles, so I'm going to use this method unless someone suggests a formula! Thank you! \$\endgroup\$
    – ireth92
    Sep 10, 2022 at 12:57
  • 1
    \$\begingroup\$ @Zibelas or ireth92, I'd say that's worth posting as an answer. This method of just simulating many randomized runs and gathering statistics about the outcomes is called a Monte Carlo approach. \$\endgroup\$
    – DMGregory
    Sep 10, 2022 at 13:01
  • \$\begingroup\$ One clarification: is damage dealt simultaneously, or does one character or the other go first, and have a chance to kill their opponent before taking damage that turn? (This matters for whether I need to compute the probability of mutual destruction) And if there's turn taking, is the order constant, or randomized each turn (like a D&D initiative roll), or randomized at the start of battle (eg. normal battle = player first, ambush = enemy first)? \$\endgroup\$
    – DMGregory
    Sep 10, 2022 at 22:52
  • \$\begingroup\$ The damage is dealt in turns, so it does matter who attacks first. I pass an "ambush" bool at the start. The same order is maintained throughout the entire battle. \$\endgroup\$
    – ireth92
    Sep 11, 2022 at 15:24

2 Answers 2

3
\$\begingroup\$

I ended up calculating it as @Zibelas suggested: simulating 500 battles and then getting the percentage with this formula:

$$\text{Probability} = \frac{\text{Favorable Outcomes}}{\text{Total Number of Outcomes}}$$

In case anyone is curious, the battle simulation process goes like this:

  1. Run a for loop 500 times.
  2. Inside the loop, calculate how many turns it will take the Player and the Enemy to die, taking into account their current health (while there is HP, continue taking damage, and count iterations). If the enemy dies first, return true.
  3. Count how many true values we've got (Favorable Outcomes).
  4. Calculate the probability and multiply it by 100 to get a percentage.

I found simulating 500 battles gave an accurate enough probability. And overall the entire script runs in less than 2 ms.

\$\endgroup\$
0
2
\$\begingroup\$

I started looking for a more deterministic way to compute this, without relying on Monte Carlo simulation, gathering statistics of a sample of randomized battles.

It's a bit of a long road showing how I derived this, so scroll to the bottom if you just want the tl;dr.


To start, I asked "What is the probability that the enemy has exactly \$x\$ HP after \$n\$ turns?" Let's call the function that answers this question \$P_{\text{enemy HP}}(x, n)\$

I'm also going to make a strange simplification, which is to assume the HP value \$x\$ can go to zero or negative and the battle keeps going anyway. This avoids special-casing zero, even though it gives us an unrealistic answer for some cases. That's fine: we'll use this unrealistic answer as a building block to work toward a realistically useful derived answer.

The base case \$P_{\text{enemy HP}}(x, 0)\$ is easy to calculate, since this is the state before anyone has made a move:

$$P_{\text{enemy HP}}(x, 0) = \begin{cases} 1, & \text{if $x$ = Enemy Starting HP}\\ 0, & \text{otherwise} \end{cases}$$

We can compute the values for turn \$n\$ from turn \$n-1\$ by summing two cases:

  • If the player misses, then the chance the enemy has \$x\$ HP after this round is the same as the chance they had \$x\$ HP at the end of the round before. So that gives us a \$(1 - \text{Player Hit %}) \cdot P_{\text{enemy HP}}(x, n-1)\$ term.

  • If the player hits, then the chance the enemy has \$x\$ HP after this round is a sum. For each value \$i\$ from \$(\text{Player Modifier} + 1)\$ to \$(\text{Player Modifier} + \text{Player CP})\$ (ie. their min to max damage), we add up \$ \frac 1 {\text{Player CP}}P_{\text{enemy HP}}(x+i, n - 1)\$ (ie. the chance the enemy had exactly \$i\$ more HP last round, and the player rolled exactly \$i\$ damage). That gives us a term like this:

$$\frac {\text{Player Hit %}} {\text{Player CP}} \cdot \sum_{i = \text{Player Modifier} + 1}^{\text{Player Modifier} + \text{Player CP}}P_{\text{enemy HP}}(x + i, n - 1)$$

Now we can recursively calculate \$P_{\text{enemy HP}}(x, n)\$ for any \$n \geq 0\$.

I implemented this in Google Sheets for a range of HP from -100 to +100, and up to 63 turns - see the "Battle Sim" tab.

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

The trouble is, we had to do a metric crapton of calculations to get this number! Enough so that doing many rounds of Monte Carlo sims is probably just as fast, and has the advantage of being much simpler to reason about.

But we're not done - I did this to establish a ground truth data set that we can use to derive a close approximation that's easier to compute, and verify the accuracy of that value.

This calculation is effectively a convolution filter applied to the discrete probability distribution of enemy HP at each turn. You can see with each passing turn, the distribution gets more and more smeared-out - and, thanks to the central limit theorem, more and more normally distributed. We're going to exploit that, to see if we can usefully approximate HP as a bell curve with a mean and standard deviation.

Calculating the mean and standard deviation of this distribution at each turn is a bit tricky - once the left tail of the distribution goes past the lowest negative HP I'm simulating, the mean and SD values we compute are no longer trustworthy (though the total probability of being alive is still accurate). To stave that off as long as possible, let's give the enemy a lot of HP, say 100, and shrink the player's damage output, say we keep CP = 10 and lower Mod = 6. That gives us a good 13 rows of trustworthy data points to check our work.

The first thing we notice is that the mean decreases linearly: exactly the same delta in every trustworthy row. That's to be expected, given we have the same probability distribution of damage dealt every turn. So we can compute the mean HP after \$n\$ turns using the player's expected damage dealt, \$E_\text{player damage}\$:

$$ \text{Mean}_{\text{enemy HP}}(n) = \text{Enemy Starting HP} - n \cdot E_\text{player damage}\\ \text{where}\\ E_\text{player damage} = \left( \text{Player Hit %} \right) \left( \text{Player Modifier} + \frac {1 + \text{Player CP}} 2\right) $$

The standard deviation follows the curve of a square root function (meaning linearly increasing variance - again, maybe expected since we're applying the same convolution each turn). We can compute that function like so:

$$ \text{SD}_{\text{enemy HP}} = \sqrt {n \cdot \Delta \sigma ^2}\\ \text{where}\\\begin{align}\\ \Delta \sigma^2 = &\sum_{i = \text{Player Modifier} + 1}^{\text{Player Modifier} + \text{Player CP}} \left(\text{Enemy Starting HP} - i - \text{Mean}_{\text{enemy HP}}(1)\right)^2 \frac {\text{Player Hit %}} {\text{Player CP}} \\&+ \left(\text{Enemy Starting HP} - \text{Mean}_{\text{enemy HP}}(1)\right)^2 \cdot (1 - \text{Player Hit %})\\\\\\ = &\sum_{i = \text{Player Modifier} + 1}^{\text{Player Modifier} + \text{Player CP}} \left(E_{\text{player damage} - i}\right)^2 \frac {\text{Player Hit %}} {\text{Player CP}} \\&+ \left(E_{\text{player damage}}\right)^2 \cdot (1 - \text{Player Hit %}) \end{align}$$

So once we calculate the constants \$E_\text{player damage}\$ and \$\Delta \sigma^2\$, we can compute the mean and standard deviation of our HP distribution on any turn \$n\$ with very simple functions:

$$\begin{align} \text{Mean}_{\text{enemy HP}}(n) &= \text{Enemy Starting HP} - n \cdot E_\text{player damage}\\\\ \text{SD}_{\text{enemy HP}} &= \sqrt {n \cdot \Delta \sigma ^2}\\ \end{align}$$

That lets us estimate the probability that the enemy is dead by the time \$n\$ turns have passed, using the cumulative distribution function of the normal distribution:

$$P_\text{enemy dead}(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]$$

...where \$\text{erf}\$ is the Error Function - this can't be expressed in terms of elementary functions, but a standard statistics library should contain an implementation you can use.

In the Google Sheets example, the probability of enemy death calculated this way very closely matches the one we computed exhaustively - differing by less than 1% at worst (ie. it underestimates the chance of dying by the end of 16 as 9.12% in this example, when the true value to within the accuracy of our double precision floating point math is 9.98%)

Graph of error values

So, I'd say that gives us a very good approximation of the true chance of being dead. Note that since we're lumping together the whole part of the distribution <= 0, the unrealism I called out earlier of pretending the enemy could have negative HP values gets erased.

But this still isn't quite the answer we're looking for, because it assumes the player character is immortal and has no chance to die and stop dealing damage. What we really want is the probability that the enemy dies before the player character does. But we can use this \$P_\text{enemy dead}(n)\$ function to get that.

Let's assume we've built a data structure with a constructor like:

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

This will compute and cache the constants we need, and expose a double DeathPredictor.ChanceToBeDeadAfter(int turnNumber) method that implements the probability function discussed above.

Then a method to compute the probability of victory might look something like this (assuming the player character acts first each turn):

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

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

    int turnsCounted = 0;

    double pPlayerWins = 0;
    double pEnemyWins = 0;

    while(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));
}

Couldn't entirely escape iteration in the end, but now our computation is proportional to the expected duration of the battle (probably in the dozens of turns).

All this being said, myself, I'd probably still implement this the Monte Carlo way (and have, when I needed battle predictions in the past). I just did this because I was nerd sniped and wanted to prove it could be done.

The reason I would not recommend implementing it this way is that most of what I've done above is non-obvious, making it hard to spot an error if I've made one (I probably have!), and brittle: it only works for exactly the battle mechanics you've described. If you later decide to change your mechanics, add a new special ability, etc., then you have to re-do this whole derivation to account for the new effect.

With the Monte Carlo approach, if you architect it right, you can use exactly the same code for both normal battle resolution and the prediction loop: so any change you make to your battle mechanics automatically updates your predictions too! That's a huge win, and probably worth even several milliseconds of extra computation. (Especially if you can do this on a background thread and hide the latency with a UI animation, so the player doesn't notice even the slightest hitch when a new battle prediction is being computed)

\$\endgroup\$
6
  • \$\begingroup\$ OMG! 😂 I can see you had fun solving this... Actually, the player doesn't always attack first. That's a variable I haven't taken into account and it shows (I'm thinking I'll just substract a turn from the player, in those cases). As you suggest, I'll continue using the Monte Carlo approach, mainly because I need to be able to understand what I'm calculating, and I'm having a hard time with your formula... cries And there may very well be new variables added in the future. \$\endgroup\$
    – ireth92
    Sep 11, 2022 at 15:20
  • \$\begingroup\$ I posted the same question in the Mathematics Exchange a few days ago, I think your answer will be most useful there. link \$\endgroup\$
    – ireth92
    Sep 11, 2022 at 15:21
  • \$\begingroup\$ We can modify the code above to work with different attack orders - I just need clarification in your question about what sequence (or simultaneous action result) is expected under your rules. \$\endgroup\$
    – DMGregory
    Sep 11, 2022 at 15:24
  • \$\begingroup\$ There are no simultaneous actions. Depending on the battle, either the player or the enemy begins their attack. Since I recalculate the chances of victory after every turn, I will be passing a "whose turn is it" variable into each simulation. \$\endgroup\$
    – ireth92
    Sep 11, 2022 at 19:08
  • 1
    \$\begingroup\$ You can use that to basically exchange the roles of enemy and player in the code above then, as needed. \$\endgroup\$
    – DMGregory
    Sep 11, 2022 at 19:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .