1. Hello!

    First of all, welcome to MapleLegends! You are currently viewing the forums as a guest, so you can only view the first post of every topic. We highly recommend registering so you can be part of our community.

    By registering to our forums you can introduce yourself and make your first friends, talk in the shoutbox, contribute, and much more!

    This process only takes a few minutes and you can always decide to lurk even after!

    - MapleLegends Administration-
  2. Experiencing crashes with 'Unknown Error'? Make sure you are on the latest MapleLegends version. The current latest version is found by clicking here.
    Dismiss Notice

Average Hits Calculator

Discussion in 'General Discussion' started by Truth Seeker, Mar 7, 2021.

  1. Truth Seeker
    Offline

    Truth Seeker Blue Snail

    2
    0
    10
    Oct 12, 2019
    Male
    7:55 PM
    DegreenLife
    Warrior
    27
    Active
    Hey guys, I started developing this average hits calculator back when OSM was still functional. It uses OSM's monster library, so some monster stats are a little off. I used the formulae from the infamous 2009 post regarding how damage is dealt on the ayumilove website. Ultimately, i think that this program is a cool way to see exactly which monster is the most efficient to kill given your character's stats.

    Check out my vid on the math behind it! https://www.youtube.com/watch?v=KiMbwhViDMo&ab_channel=GameCrux

    Download link: https://www.mediafire.com/file/3mnh9g1ne8baxfm/ManyWorlds.rar/file
    To use, simply extract the .rar file somewhere and click on "ManyWorlds.exe". Use the "ReadMe.txt" file to determine which fields need to be filled in. Calculations will take a while if you're high-leveled or have a large attack range. If you would like to contribute to the project, please check out the associated repository on Github: https://github.com/GameCrux/ManyWorlds .

    Example:
    many worlds noob example.png
     
    • Great Work Great Work x 2
  2. Tate
    Offline

    Tate Capt. Latanica

    351
    228
    278
    Apr 16, 2020
    New Zealand
    1:55 PM
    Potayto
    Shadower
    175
    Beaters
    Oooh this sounds promising.
     
  3. geospiza
    Offline

    geospiza Web Developer Staff Member Web Developer

    208
    440
    215
    Apr 16, 2020
    4:55 PM
    geospiza
    Dark Knight
    146
    Funk
    Gotta love combinatorial explosion; I like the precision of the formula. Your video is also intuitive and easy to follow along.

    One resource to check out is Nise's Formula Compilation, which refers to Ayumilove's Formula Compilation. Two small things to consider are the effects of monster defense and player accuracy. The former is just a modifier on how damage is calculated, depending on the monster. The latter probably makes the exact method intractable, but it does factor into the average number of hits to kill if you were to rank all monsters for a player. Concrete example: I remember trying to figure out if it was worth killing CDs at a certain level because of how often I was missing.

    It would be interesting to calculate the average hits using both constraint solver and statistical model. You mentioned the knapsack problem, which can be solved using off-the-shelf constraint solvers. A constraint solver can result in concise code because it's declarative, i.e., find all combinations of damage that sum up a monster's hp and compute the weighted average. A statistical model could be computationally cheaper with approximate results. From my limited understanding of stats, you can sample random walks across the many worlds and compute an average based on those samples (their length and frequency). It's easier to model things like crits and accuracy into the final result because they're just random variables.

    In any case, great food thought! Thanks for sharing.
     
  4. geospiza
    Offline

    geospiza Web Developer Staff Member Web Developer

    208
    440
    215
    Apr 16, 2020
    4:55 PM
    geospiza
    Dark Knight
    146
    Funk
    I was curious, and put together a script that does both the exact solution (via constraint solver) and an approximate solution (via rejection sampling). It doesn't handle any of the modifiers, just the average number of hits given a damage range and hp. I noticed that you did handle monster defense and accuracy when I reviewed your code.

    I reproduced the numbers in your video for the blue snail with the scripts. In the first row, there's an array containing the number of possible ways to kill a monster in that many hits (counting from 0). In the second row, there are the parameters (algorithm, min range, max range, hp) and the average number of hits (naive, algorithm). So the average number of hits to kill a blue snail with 15 hp with an attack range of [4, 6] on is 3.37. The naive solution is to divide hp by the average range (which is very cheap to compute).

    Code:
    [0, 0, 0, 17, 30]
    exact 4 6 15 => 3.0 3.37
    
    The constraint solver finds every solution over the possible number of hits to kill a monster. The library I use does this via backtracking, but there are more sophisticated solvers out there. This definitely doesn't scale when the attack range is in the 1000s and the number of hits to kill is greater than 3 or 4, because the number of solutions is exponential. It takes a good 10+ seconds for range [40, 120] at 150 hp.

    I tried an approximate solution that runs in linear time using rejection sampling (not the random walk that I was thinking about before, I don't think it's applicable here). For each possible number of hits to kill a monster, generate a fixed number of samples (a line of damage). Count it as valid if it kills the monster in exactly the number of hits. Then find the probability that you kill a monster in that number of hits. The average is then the weighted average across all possible number of hits.

    Here the first row is the weight for the number of hits (e.g. there's a 62% chance you kill a snail in 3 hits). The second row is the same format as the previous one.

    Code:
    [0, 0, 0, 0.619, 0.391]
    approx 4 6 15 => 3.0 3.39
    
    This answer is within 1% error of the original, which I think is pretty good. It's also straightforward to implement.

    Here are a few problems that will choke the exact counting algorithm, even if it's very optimized.

    Code:
    [0, 0, 0, 0, 0, 0.0, 0.094, 0.671, 0.248, 0.008, 0.0]
    approx 1500 3000 15000 => 6.667 7.167
    
    [0, 0, 0, 0.0, 0.176, 0.533, 0.284, 0.039, 0.003, 0.0, 0.0]
    approx 1500 5000 15000 => 4.615 5.188
    
    [0, 0, 0.015, 0.404, 0.41, 0.124, 0.019, 0.0, 0.0, 0.0, 0.0]
    approx 1500 8000 15000 => 3.158 3.720
    
    One benefit of sampling is that you can also show the entire distribution. You can see how a wider range leads to a wider distribution on the number of hits to kill.

    upload_2021-3-11_0-38-32.png

    I think sampling is the way to go to calculate the average. Thank you again for the clear video, it spurred my curiosity and helped me think through an efficient way to calculate the number.

    gist: https://gist.github.com/geospiza-fortis/3122d62852c2023f79a79bdd74cd1561
     

Share This Page