User:Bcbrown

Building a Monte Carlo Markov Chain for Damage Simulation

I'd like to demonstrate all the steps required to build a Monte Carlo Markov Chain for damage simulation. I will be building one to simulate damage while charm kiting, but I'll build it as generally as possible to make it easy to apply to as many problems as possible. Let's start by defining some terms.

Monte Carlo

A Monte Carlo method is using repeated simulations of some process to answer mathematical questions that are too hard to solve directly. For example, say you wanted to calculate the odds of getting a straight flush in a five-card poker hand, and you didn't know how to calculate that directly. You could simulate dealing a thousand hands and just count up how many of them are straight flushes. We're going to repeatedly run a Monte Carlo process and calculate the average remaining health of a mob after breaking charm, and how frequently the mob dies before charm breaks.

Markov Chain

A Markov Chain is just a flow-chart with loops. You have a bunch of different possible states, and you have arrows, or transitions, between them. For example we can build a simple markov chain for hitting a mob with a weapon. There's only one state, with current health of the mob. There's two possible transitions: 1) if the last swing killed the mob, combat is over; 2) if the mob survived the last swing, swing again.

Implementing the Damage Simulation

This is going to use a very simple damage simulation using actual data derived from a log file of charm fights. I took the last 1000 hits of gator v gator charming in Cazic Thule and processes it into a file with two columns, damage and number of hits, called histogram. I then wrote a Python method to load it.

This method has to do several things. First, we're going to be thinking of damage in terms of a percentage of the mobs total health, not the raw damage done. Second, we're going to convert raw numbers of hits into frequencies. So the output of this will be something like:

8% 11.5%
7% 15.0%
6% 19.4%
5% 9.8%
4% 8.7%
3% 7.9%
2% 9.2%
1% 8.4%
0% 10.1%

The second part of damage simulation is using that data to roll some random numbers to determine the damage each round. I counted a 57.7% hit rate, or a 42.3% miss rate, so first we'll use that to see if the swing is a hit or a miss. If it's a hit, we'll compare a second random number to determine how much damage it does.

   from collections import defaultdict
   from random import random
   
   def build_histogram(filename='histogram'):
       with open('histogram') as f:
           max_damage = 62
           max_percent = 8
           scale_factor = max_percent / max_damage
           counts = defaultdict(int)
           total_hits = 0
           for line in f:
               damage, count = line.strip().split(' ')
               damage = int(damage)
               count = int(count)
               damage_percent = int(damage * scale_factor)
               counts[damage_percent] += count
               total_hits += count
           histogram = {}
           for damage, count in counts.items():
               percent = count / total_hits
               histogram[damage] = percent
       return histogram
   
   class Combat:
       def __init__(self):
           self.histogram = build_histogram()
           self.miss_percent = 1 - .577
       def hit(self):
           hit_roll = random()
           return hit_roll > self.miss_percent
       def damage(self):
           damage_roll = random()
           accumulator = 0
           for damage, percent in self.histogram.items():
               accumulator += percent
               if accumulator > damage_roll:
                   return damage
           return damage
       def swing(self):
           if not self.hit():
               return 0
           return self.damage()

Implementing the Markov Chains

As discussed earlier, a Markov Chain consists of states and transitions. We'll implement this by having each state be an object, and if you tell it the current mob health and the damage from the last combat round it'll tell you the next state to transition to. For an instant cast charm break like the Goblin Gazhugi Ring this is very simple. There's a single state. As soon as the mob health drops below some threshold, you click the ring, charm breaks, and the simulation is over.

The implementation for the Ring of Stealthy Travel is only slightly more complicated. First there's a waiting state that just transistions back to itself. As soon as the mob health drops below some threshold, you click the ring and move to a Casting state. Then, determined by the damage in the last combat round and the new mob health, you either duck and recast (transitioning back to the Casting state), or you let the cast go through and the simulation is over.

Finally, the end state when you break charm is called the Terminal state, and doesn't have to do anything. You can see those states below.

   Terminal = object()
   
   class BreakInstant:
       
       This is the only state for the GGR. As soon as the mob health hits the 
       threshold, break instantly and end
       
       def __init__(self, threshold):
           self.threshold = threshold
           self.next_state = Terminal
       def transition(self, mob_health, last_damage):
           if mob_health <= self.threshold:
               return self.next_state
           else:
               return self
       def reset(self):
           pass
   
   class Waiting:
        
       This is the initial state for the RoST. As soon as the mob health hits the
       threshold, cast invis and wait to see the outcome of the next round before
       deciding whether or not to duck
       
       def __init__(self, threshold, next_state):
           self.threshold = threshold
           self.next_state = next_state
       def transition(self, mob_health, last_damage):
           if mob_health <= self.threshold:
               return self.next_state
           else:
               return self
       def reset(self):
           self.next_state.reset()
   
   class Casting:
        
       This is the state where we've cast the RoST. Depending on the outcome of
       the next combat round we'll either duck the cast or let it go through
       
       def __init__(self, threshold):
           self.threshold = threshold
           self.num_ducks = 0 
       def transition(self, mob_health, last_damage):
           if mob_health <= self.threshold:
               # mob's injured enough, let the cast go through
               return Terminal
           else:
               # duck
               self.num_ducks += 1
               self.current_ducks += 1
               if self.current_ducks > self.max_ducks:
                   self.max_ducks = self.current_ducks
               return self
       def reset(self):
           self.all_ducks[self.current_ducks] += 1
           self.current_ducks = 0

Implementing the Monte Carlo simulation

There's two methods in this implementation, first to run the simulation for a single charm fight, second to repeat it thousands of times and calculate the results.

To run a single simulation you repeat a small loop. First you simulate a combat round and update the mob's health with the damage done. If the mob dies, you end the simulation. Otherwise you transition to the next state in the Markov chain, to allow the user to choose whether to start casting, duck and recast, or allow a spell to finish. Repeat until the cast finishes and charm breaks or the mob dies.

   import markov
   import combat
   DeadMob = object()
   engine = combat.Combat()
   def run_once(state):
       mob_health = 100 
       while state is not markov.Terminal:
           damage = engine.swing()
           mob_health -= damage
           if mob_health < 0:
               return DeadMob
           state = state.transition(mob_health, damage)
       return mob_health

The other method runs the simulation as many times as requested. It tracks the outcome of each simulation: whether the mob dies before charm is broken, and if charm is broken, what percentage of health the mob is left at. Then after running all the simulations it computes the percentage of lost mobs and the average health remaining.

   def run_loop(starting_state, num_loops):
       mob_deaths = 0 
       final_healths = []
       for i in range(num_loops):
           result = run_once(starting_state)
           if result is DeadMob:
               mob_deaths += 1
           else:
               final_healths.append(result)
       mob_death_percentage = 100 * mob_deaths / num_loops
       print("Percentage of lost mobs: " + str(mob_death_percentage) + "%")
       average_health_remaining = sum(final_healths) / num_loops
       print("Average health percentage remaining: " + str(average_health_remaining))

The final section launches the simulation of each approach and also calculates the average number of ducks when using the RoST:

   def count_ducks(all_ducks, threshold):
       ducks_over_10 = 0
       for k, v in all_ducks.items():
           if k >= threshold:
               ducks_over_10 += v
       print("Frequency of {}++ ducks: {}".format(threshold, str(100 * ducks_over_10/num_loops)))
   
   if __name__ == '__main__':
       num_loops = 10 * 1000
       print("Running simulation for GGR")
       starting_state = markov.BreakInstant(9)
       run_loop(starting_state, num_loops)
       
       print("Running simulation for RoST")
       casting_state = markov.Casting(9)
       starting_state = markov.Waiting(18, casting_state)
       run_loop(starting_state, num_loops)
       
       print("Average number of ducks: " + str(casting_state.num_ducks / num_loops))
       print("Max ducks: " + str(casting_state.max_ducks))
       
       all_ducks = casting_state.all_ducks
       count_ducks(all_ducks, 5)
       count_ducks(all_ducks, 10)