Computing chance of winning when dealing with fuzzy numbers

Question

Computing chance of winning in a one player and one enemy battle when using fixed numbers is quite easy; for example if we have these numbers:

Player : Attack : 5 - Health : 30 - Attack Interval : 2s
Enemy : Attack : 10 - Health : 20 - Attack Interval : 5s

When both player and enemy start battling together at the same time you can say for 100% the player will win this battle because it takes the player 8 seconds to kill enemy but enemy needs 15 seconds to win, so it is certain the player would win this battle.

Now considering using not fixed numbers (Attack and Attack Interval are fuzzy), for example for these numbers:

Player : Attack : (5>10)10% - Health : 30 - Attack Interval : (2s>5s)50%
Enemy : Attack : (10>15)20% - Health : 20 - Attack Interval : (5s>7s)10%

Note: (5>10)10% means for 90% of times when a player attacks it would have 5 hit points and for 10% of times it randomly can be from 5 to 10 point.

Note: (2s>5s)50% means for 50% of times player attack interval is 2s and for 50% of times it randomly can be from 2 to 5 second.

Now this changes choosing the winner for some numbers; either the player or the enemy can win the battle. How can we compute the chance of winning? For example, concluding that the player has 34% of winning in this battle, etc.

---

UPDATE : I'm creating probability tree for player and enemy for my example with a little change in numbers to get rounded numbers. example is this :

Player : Attack : (5>10)10% - Health : 30 - Attack Interval : (2s>5s)70%
Enemy : Attack : (10>15)20% - Health : 20 - Attack Interval : (5s>7s)10%

now i achieve two probablity/winTimeNeeded chart like these :

Now how can i get player overall win probability with these chart and numbers?

---

Update : with @realUser404 solution i can say player have exactly 82.0028% of winning in this example (if player and enemy have exactly the same time we consider this a lost.)
still if some one have better solution I'll be happy hear about it I'll wait til the end of bounty.

Answer 1

If you do not wish to compute all the solutions, maybe the following can get you a good approximation :

Choose fixed stats for the Enemy : Enemy : Attack : 10 - Health : 20 - Attack Interval : 5s for example. This gives you the time the enemy needs to kill you.

With that information, it is pretty easy to get the probability that you kill him first, with your fuzzy stats.

You can then calculate the same for different values of the enemy's stats, and then ponderate according to the probabilities you defined for your enemy --> This will give you your final probability of winning.

It is only an approximation, but it can be a pretty good one depending on how you do the settings, and can improve the performances by a lot.

With your Edits :

Okay, so now with your edit it became pretty simple to calculate the player's winning probability : Just calculate the probability of winning if you do 4 secs, then 6 secs, then 8... up to 20s. Then ponderate by the probability of doing yourself that time, and add everything up.

A few examples : if you kill your opponent in 6 seconds, you have 100% chances of winning. So you can add to your total probability 4.40 * 100% = 4.40%. As your opponent cannot kill you before 10 seconds, you already know you have at least a 1.40 + 4.40 + 64.60 +0.60 +0.20 = 71.20% chances of killing him.

For 12 seconds, you have 96.20% chances of killing your opponent (100 - 3.60 - 0.20), so you can add to the total probability 96.20 * 9.80% (percentage of chances to kill the opponent in 12 seconds).

Do This for all the times, add everything, and you should get something around 85% in your example.

Answer 2

Run a batch of randomized simulations (aka Monte Carlo experiments) & collect the desired statistics. This technique is especially useful if you have hard to quantize combat factors, such as freeze effects, to randomized hit modifiers, variable chance to crit, etc. It's also a nice way to capture other info like the quickest victory, least damaging, most damaging, etc. I've seen this approach used in Brogue for instance.

In terms of draw backs, this technique general requires loosely coupled game logic &/or games with easily restored logical state. It is not good for situations where your combat is tightly coupled to your graphics / animations.

I usually automate the process of finding a good # of trials for this sort of thing. This let's me experiment with a potentially wide variety of different combat mechanics & I can easily adjust my estimate finder without doing a bunch of testing by hand.

Answer 3

This is written in python 2.7.11 if you want to test it out for yourself before you start working it out in the language you're using if you decide to use it. There are no special requirements, just make sure to use python 2.7 and remember to import math.

I started by getting the range of time that each individual has the opportunity defeat the other. The starting value represents the soonest possible time that one person can possibly defeat the other and the end value represents the latest. Each value rounds up, accounting for a user not taking a "non-integer" amount of turns since we don't need to deal the exact damage required to defeat their opponent.

This range is important because we want to figure out how long one person has until the other has a chance of defeating them. We then calculate the odds of that person defeating the other during this time. For the remainder of this post, I will refer this person (the person who has the opportunity to defeat the other first) as Sub_A and the other Sub_B. Just so I don't have to describe it every time :)

example: there is a 40% chance that the player(Sub_A) will defeat the enemy(Sub_B) before the enemy has a chance of defeating the player. That leaves a 60% chance of both users having an opportunity to defeat one another afterward.

The rest of the equation is acquiring the odds of the player defeating the enemy during the remaining time using their approximate damage per second. This is then multiplied by the odds of Sub_A NOT DEFEATING Sub_B and added to the odds of Sub_A DEFEATING Sub_B.

continued example: There is a 20% chance of the enemy(Sub_B) defeating the player(Sub_A) and a 60% chance of the player defeating the enemy. We then divide each percentage by the sum of both ( 20 / (60 + 20) and 60 / (60 + 20) ). This gives us 25% and 75% for a total of 100%. There is a 100% chance that one of them will defeat the other during this time. Those values are then multiplied by the 60% from earlier to get 15% and 45%. We then know that the player has approximately a (40 + 45) = 85% chance of defeating their enemy.

Hopefully this does the job! I tried to put in some helpful comments, but ultimately it just takes a some figuring out. Please let me know if I made any mistakes or if anyone has any improvements/changes. I would love to know!

def main():
    import math

def lerp(mn, mx, amt):
    # calculate the value between min and max at a certain percentage
    return mn + (mx - mn) * amt

def average_amt(mn, mx, odds):
    # takes the average random value between (min amount) and the (average of the range between min and max)
    # this takes into account the odds of getting the min amount
    return lerp(mn, lerp(mn, mx, .5), odds)

class Fighter:
    def __init__(self, min_dmg, max_dmg, dmg_chance, hp, min_time, max_time, time_chance):
        self.min_dmg = min_dmg
        self.max_dmg = max_dmg
        self.dmg_chance = dmg_chance
        self.hp = hp
        self.min_time = min_time
        self.max_time = max_time
        self.time_chance = time_chance

    def time_range(self, dmg):
        # returns the range of time needed to deal a certain amount of damage
        # value is based on how many turns it will take
        # example: if it takes 4.2 turns to deal the requires amount of damage, it will round up to 5
        mini = math.ceil(dmg / self.max_dmg) * self.min_time
        maxi = math.ceil(dmg / self.min_dmg) * self.max_time
        return mini, maxi

    def get_dps(self):
        # returns the average amount of damage dealt per second
        ave_dmg = average_amt(self.min_dmg, self.max_dmg, self.dmg_chance)
        ave_time = average_amt(self.min_time, self.max_time, self.time_chance)
        return ave_dmg / ave_time

    def approx_percent(self, time, dmg):
        # returns an approximate percent chance of winning at any given time based on average damage per second
        time_range = self.time_range(dmg)
        if time <= time_range[0]:
            # it is not technically possible to win at this point in time,
            # but would still return a value if not explicitly told not to
            return 0
        else:
            return self.get_dps() * time / dmg

    def odds(self, enemy):
        # returns the odds of winning a battle against an enemy
        my_range = self.time_range(enemy.hp)
        enemy_range = enemy.time_range(self.hp)

        if my_range[0] > enemy_range[1]:

            # enemy will win before the player has a chance to
            return 0

        elif my_range[1] < enemy_range[0]:

            # player will win before the enemy will have a chance to
            return 1

        else:
            overlap_start = max(my_range[0], enemy_range[0])
            overlap_end = min(my_range[1], enemy_range[1])
            if my_range[0] < enemy_range[0]:
                # the player has an earlier possibility of defeating the enemy

                # win_odds are the odds of the player defeating the player before the enemy has a chance
                win_odds = self.approx_percent(overlap_start, enemy.hp) / 2

                # enemy/player odds are the odds of the enemy and player winning while the possibilities overlap
                player_odds = self.approx_percent(overlap_end, enemy.hp) / 2 - win_odds
                enemy_odds = enemy.approx_percent(overlap_end, self.hp) / 2

                # return the total odds in relation to the player
                return win_odds + player_odds / (player_odds + enemy_odds) * (1 - win_odds)
            else:
                # the enemy has an earlier possibility of defeating the player

                # win_odds are the average odds of the enemy defeating the player before the player has a chance
                win_odds = enemy.approx_percent(overlap_start, self.hp) / 2

                # enemy/player odds are the odds of the enemy and player winning while the possibilities overlap
                enemy_odds = (enemy.approx_percent(overlap_end, enemy.hp) - win_odds) / 2
                player_odds = self.approx_percent(overlap_end, enemy.hp) / 2

                # return the total odds in relation to the player
                return player_odds / (enemy_odds + player_odds) * (1 - win_odds)

# Player : Attack : (5>10)10% - Health : 30 - Attack Interval : (2s>5s)50%
#  Enemy : Attack : (10>15)20% - Health : 20 - Attack Interval : (5s>7s)10%

# this is the equivalent to your example in code
PLAYER = Fighter(5.0, 10.0, .10, 30.0, 2.0, 5.0, .50)
ENEMY = Fighter(10.0, 15.0, .20, 20.0, 5.0, 7.0, .10)

odds = PLAYER.odds(ENEMY)
print '{}%'.format(odds * 100)

# 69.1689008043%

PLAYER = Fighter(10.0, 15.0, .2, 20.0, 5.0, 7.0, .1)
ENEMY = Fighter(10.0, 15.0, .2, 20.0, 5.0, 7.0, .1)

odds = PLAYER.odds(ENEMY)
print '{}%'.format(odds * 100)

# 50.0%


main()

Answer 4

With discrete random events like your example, the easiest method to understand would be the probability tree. Map out all the possible outcomes in a tree, note the probabilities of each outcome "branch", and sum the probabilities in the end.

Since there could be many attacks before the first player/enemy dies, this tree could have many levels of branches, so you may need to write a short program to perform the calculation.

Answer 5

This problem looks small enough that you could just do a brute force exhaustion over all possible random choices, as described in this answer.

---

The biggest optimization you can probably do here is to study the two actors independently. i.e. for the player, you tabulate the probability distribution on the amount of time it takes to deal 20 damage, and for the enemy you tabulate the probability distribution on the amount of time it takes to do 30 damage.

Then using those tables, you can then compute the probabilities of the player doing 30 damage before, at the same time as, or after the enemy.

You can even do that last calculation in time linear in the table size with the right algorithm.

---

You can also optimize the exhaustion over all random choices.

Rather than iterate through the possible states — e.g. pairs consisting of "the time the actor can attack next" and "damage previously done done" — you can iterate through them in a topological ordering (e.g. increasing time). Using a hash table, you can detect when a game state is duplicated, and merge the probabilities of arriving at that state, so as to avoid duplicating work.

Approaches like this are surprisingly effective if you've never seen them before; they can very quickly do exhaustive calculations that you might have thought completely infeasible if you've never seen things like them before.

---

Also, claim that analyzing the two actors separately is actually an optimization an educated guess — depending on the sorts of actual problems you have, it may actually be better to do the exhaust over all of the possible states of actual combat.

Answer 6

Intro
I'm going to specifically answer how to use the probability tree to get win/loss ratios.

For starters, your math becomes very ridiculous to hand-design a flowchart. I didn't even finish the first player attack and got this:

Simplify
So, let's change your numbers a bit so the drawing gets done today. Now, both player and npc have 15 health, player has a 50% crit chance, npc has a 25% crit chance, both player and npc do 5 damage, and all crits do double damage. Also, they each attack once per turn regardless, and I'll assume the player wins a tie (i.e., both player and enemy would hit 0 health or less on the same round).

This means that each round there are 4 possible outcomes for damage. PHit/EHit, PHit/ECrit, PCrit/ECrit, PCrit/EHit, with probabilities of 50% x 75% = 37.5%, 50% x 25% = 12.5%, 50% x 25% = 12.5%, 50% x 75% = 37.5%.

Now we get this:

In each box, the first number represents the probability of that box occurring if the preceding box happened. Then PxD gives the player's damage, ExD is the enemy's damage, PxH is the player's remaining health, and ExH is the enemy's remaining health. The final percentage is the cumulative chance of getting to that box, calculated by multiplying each conditional chance in the chain (and rounded a bit, so the final totals won't be exactly 100%). Orange text means the player killed the enemy, red text means the enemy killed the player.

Specific Numbers
For a specific example, let's take the left-most branch each turn. 37.5% of the time, both player and npc roll normal hits, doing 5 damage each, leaving them at 10 health. After that happens, there's a 37.5% chance they each roll normal hits again, doing another 5 damage each, leaving them at 5 health. Finally, there's another 37.5% chance they each roll normal hits a third time, doing a final 5 damage and killing each other. Since we said the player wins a tie, this counts as a win for the player. The total probability of the fight ending this specific way is 37.5% x 37.5% x 37.5% = 5.2734375% ≈ 5.3%.

Results
So the player loses on the second round 11% of the time, wins on the second round 74% of the time, and wins on the third round 14% of the time. Total odds are that the player wins 88% of the time and loses 11% of the time.

Applying to your Numbers
Using your example numbers, you'd need to have a lot more branches, including the fact that many branches include no damage when no attack occurs on that particular round. Which means you'd likely want to automate the process instead of doing it by hand.

I'm not exactly sure how you got your charts, but I think you can convert it to similar numbers by multiplying each of the player percentages by the percentage of player wins, then the same for the enemy chart. So, for example, if the player wins 80% of the time, the first number on the chart becomes 80% x 1.4% = 1.12%. Then the first number on the enemy chart becomes 20% x 3.6% = 0.72%. Etc.

My gut feeling is you can't do what your edit says to get 82%. Each chart sums to 100%, which means each number isn't a percentage of the total, so you can't just add the percentages. You can add the percentages say that 71% of all player wins occur in the first 9 seconds. But you don't know how often the player wins, so you can't say there's a 71% chance the player wins by 9 seconds.

Your chart says there's a 71% chance the player wins by 9 seconds. Then it gets complicated. There's a 29% chance the player doesn't win by 10 seconds. 0.2% of that remaining 29% chance involves the player killing the enemy on the 10th second. But this is 0.2% / 29% ≈ 6.90% chance assuming that we got to 10 seconds. Then we have to break that into four parts. Because we could have neither player nor enemy wins, both win, player wins, enemy wins. There's a 3.6% / 100% = 3.6% chance the enemy wins on this turn, with final results of:

In about 89.7% of the cases, nobody wins, so we go to the next step. In about 3.4% of cases, the enemy wins (so the player loses). In about 6.7% of cases, the player wins. And in about 0.25% of cases, both win (so it's a tie). But the total odds are the 29% chance we even got this far times the individual odds of any specific branch happening. For example, there's a 29% x 0.25% = 0.0725% chance of getting a tie on round 10.

So we repeat the same stuff for the next round. Nobody kills anyone on round 11 (100% chance of nothing, 0% chance of other stuff), so we skip to round 12. There's a 29% chance we made it to 10, then an 89.7% chance we went from 10 to 12, so there's a total of 29% x 89.7% = 26.013% chance we get to round 12 at all. The player chance remaining is 28.8%, and the enemy chance remaining is 96.4%. So the odds the player wins this round, given we got here, are 9.8% / 28.8% ≈ 34.0%. The odds the enemy wins this round, given we got here, are 0.2% / 96.4% ≈ 0.21%. Again, there are four possibilities, just like above. Each block is calculated as tie = (e x p), player wins = (1-e) x (p), enemy wins = (e) x (1-p), and neither wins = (1-e) x (1-p), where e and p are the odds of the enemy and player winning given above, 0.21% and 34.0%.

Then we repeat that for every step of the way. Each round will have four options: tie, player wins, enemy wins, and nothing happens (which leads to the next round). In some cases, there will be a 100% chance nothing happens, so we just skip ahead. The final case will have a 0% chance nothing happens. Add up all the numbers for tie + player wins + enemy wins, and you should get 100%. Add up all the player wins to get total odds of the player winning, etc. Assign tie wherever you want, or treat it separately, your choice.