Hello everyone.
A month ago we developed a programming problem in the
CALICO contest at UC Berkeley that involved a bugfix of the Pokémon Showdown! damage calculator. Currently, the damage calculator does not handle multihit moves properly, as it gives a rough approximation, e.g. if Bullet Seed hits 4 times it is treated as a 100BP move instead of 4 different 25 BP moves. I will attach the original problem for those of you that are interested in reading it. You can even try to solve it in our
online judge.
This just gives a rough approximation, which can be really different from reality in the case of moves that hit a lot of times like Population Bomb (that's why the problem's name is Maushold, although in the problem Population Bomb hits up to 10¹² times lol). It also makes it hard to handle abilities like Multiscale or Weak Armor, or damage reducing berries or even Sitrus Berry procs.
I don't play Pokémon anymore and I'm not planning on getting involved with the project, but since I developed this problem I figured that I should give some indications on how to fix this. The fix is a bit complex to implement in the sense that a lot of the already written code should be modified, but if you put the time on this then more interesting features could be added to the calculator, such as calculating the odds of surviving multiple different attacks at the same time in an efficient (pseudo-polynomial) manner.
I have seen various implementations of the latter part and they always use trivial backtracking which is just a wrong approach on the problem since it has an exponential time complexity and it will make your machine "explode" if you try to combine 6 attacks. The workaround is using polynomials and polynomial multiplication (all details are in the Maushold-Editorial attached to this message). Note that FFT is a good approach but is not needed since most Pokémon have low HP (low means less than 1000). However, an FFT implementation could be nice if you take PokéRogue into consideration lmao. However, with just a trivial implementation of polynomial multiplication, given an Pokémon with M hit points and N moves, you can calculate (in an exact manner) the final damage rolls in O(M²N) operations (FFT reduces it to O(NMlogM)). Note that the editorial also gives some hints on how to solve some other questions, like taking Leftovers/Sitrus Berry/Damage reducing berries/Multiscale into account. Once you get the gist of it, any other "problem" (mechanic) will be solved similarly and it should be easy to come up with the solution.
If anyone from the project has questions regarding my approach to the damage calculation and how to implement it feel free to DM me here and I will try to respond as soon as possible.
Hope you find this helpful/interesting,
Gotheru