Fractal Softworks Forum

Please login or register.

Login with username, password and session length
Advanced search  

News:

Starsector 0.97a is out! (02/02/24); New blog post: Simulator Enhancements (03/13/24)

Pages: 1 ... 8 9 [10] 11 12 ... 32

Author Topic: Optimizing the Conquest: a Mathematical Model of Space Combat  (Read 24625 times)

CapnHector

  • Admiral
  • *****
  • Posts: 1056
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #135 on: November 22, 2022, 05:04:09 AM »

Wow, my C++ code was pretty terrible it turns out, as indeed it should have an extra line for armor pooling too for the hit strength calculation and right now it's just comparing the total hit strength to one single cell's armor. Sorry about that. The extra lines should read

double armorpooled=0;
for(int x=0; x < 5; x++){
for(int y=0; y < 5; y++){
armorpooled = armorpooled + std::max(A((i-2)+x,y)/2, a_mod * a/2);
}
}
for(int x=0; x < 3; x++){
for(int y=0; y < 3; y++){
armorpooled = armorpooled + std::max(A((i-1)+x,y+1)/2, a_mod * a/2);
}
}
double adjusted_d = std::max(d*h/m/(armorpooled+h/m)*probmult, minimumdamageafterarmorreduction*d*probmult);   

for example.

Anyway, your code seems mostly right, however there is one extra thing which is that hit strength and damage must be two different things. This is because for beams we have hit strength = dps / 2 but damage = beam ticks(adjusted for chargeup/chargedown)*dps/beam tick. We get the adjusted beam ticks from the hit time series function for each second. And, I'm not an expert on armor, but I think Vanshilar said earlier that cells with 0 armor can contribute to minimum armor even if pooled armor is not yet at the minimum armor threshold so that affects the order of sum and max operations. Vanshilar, can you confirm if I have this right?

So anyway let's try that commenting thing again:

Code

/* NumericMatrix leads to the code modifying the matrix in the R global environment on lines 10 to 17. If this is not possible in Python, then the function should return the damaged matrix. The function should also return a double containing the hull damage that goes through. */
double damage(NumericMatrix A, NumericMatrix D, double a, double a_mod, double d, double h, double m){
  double hd = 0;
  int rows_A = A.nrow();
  int cols_A = A.ncol();
/* see above - we were passed the starting armor of the ship, and now we calculate the starting armor of an individual cell */
  a = a/15;
/* go through the armor matrix */
  for (int j = 0; j < cols_A; j++){
  for (int i = 0; i < rows_A; i++){
/* "armor" is the value we will use for the hit strength calculation. IF the armor matrix hp at (i,j) is greater than minimum armor (e.g a_mod=0.05, a=1500/15 (standard dominator) -> minimum armor is 0.05*100) THEN use armor matrix hp ELSE use the minimum armor value for the hit strength calculation */
    double armor = std::max(A(i,j), a_mod*a);
/* probmult refers to the fraction of damage we are assigning to the armor cell according to the probability distribution and it is given by the overall damage distribution matrix D (ie. the one stored in the lookup table, the one we calculate using the normal and uniform distributions) at (i,j) */
    double probmult = D(i,j);
/*now we must compute the pooled armor strength from adjacent cells for the hit strength calculation*/
    double armorpooled=0;
for(int x=0; x < 5; x++){
for(int y=0; y < 5; y++){
armorpooled = armorpooled + std::max(A((i-2)+x,y)/2, a_mod * a/2);
}
}
for(int x=0; x < 3; x++){
for(int y=0; y < 3; y++){
armorpooled = armorpooled + std::max(A((i-1)+x,y+1)/2, a_mod * a/2);
}
}

/* adjusted damage is: maximum of: damage assigned to cell (d = total damage times probmult = fraction of total damage assigned to cell), adjusted by hit strength / (armor + hit strength), or, if that were below it, the threshold armor can't reduce damage below times damage assigned to cell. In addition, because the modifiers are he = 0.5, kinetic = 2, frag = 4, then the correct adjustment for hit strength to hit armor is hit strength / modifier*/
double adjusted_d = std::max(d*h/m/(armorpooled+h/m)*probmult, minimumdamageafterarmorreduction*d*probmult);
/* if we are dealing less damage than either armor hp or minimum armor then we are not dealing hull damage */
    if (adjusted_d <= armor){
/* reduce armor hp by adjusted allocated damage */
      A(i,j) = A(i,j) - adjusted_d;
/* if armor went below 0 set armor to 0.0 since it is a double */
      A(i,j) = std::max(A(i,j), 0.0);
    }
/* if we are dealing more damage than either armor hp or minimum armor */
    if (adjusted_d > armor){
/* set armor cell hp to 0 */
      A(i,j) = 0.0;
/* now calculate the damage to hull. It is adjusted damage minus minimum armor or armor hp, re-scaled to hull. Due to the way we defined the modifier above, we can  re-scale the damage back to the appropriate modifier for hull by multiplying it by m (since all weapons deal 100% damage to hull) */
      adjusted_d = (adjusted_d - armor)*m;
/* this next line might just as well read hd = adjusted_d; */
      hd = hd + adjusted_d;
    }
  }
  }
  return hd;
}

This is certainly not an optimal interpretation of what the code should do, but since you will be programming it in a different way, this should only act as a reference anyway.

Edit to add: for some reason this, however, seems to return far too high times to kill (e.g.

"72"   "Squall"   "Locust"   "Harpoon"   "Harpoon"   "Gauss"   ""   "Gauss"   "" when the previous simulation based method returned

"27"   "Squall"   "Locust"   "Harpoon"   "Harpoon"   "Gauss"   "Gauss"   ""   "")

So there is definitely something wrong with this fixed version. Was the previous one right all along? Unfortunately I simply can't put any more time into this just now as I have some calculus coursework where it's going to be less than ideal if I don't turn it in time. Anybody see where the error might be? Or is it lurking somewhere in the rest of the code?

Regardless, I'm confident in the structure of this thing even if there is a computational error somewhere.
« Last Edit: November 22, 2022, 06:17:27 AM by CapnHector »
Logged
5 ships vs 5 Ordos: Executor · Invictus · Paragon · Astral · Legion · Onslaught · Odyssey | Video LibraryHiruma Kai's Challenge

intrinsic_parity

  • Admiral
  • *****
  • Posts: 3071
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #136 on: November 22, 2022, 08:25:18 AM »

Anyway, your code seems mostly right, however there is one extra thing which is that hit strength and damage must be two different things. This is because for beams we have hit strength = dps / 2 but damage = beam ticks(adjusted for chargeup/chargedown)*dps/beam tick. We get the adjusted beam ticks from the hit time series function for each second. And, I'm not an expert on armor, but I think Vanshilar said earlier that cells with 0 armor can contribute to minimum armor even if pooled armor is not yet at the minimum armor threshold so that affects the order of sum and max operations. Vanshilar, can you confirm if I have this right?
Good point on the hit strength thing. I wasn't thinking about beams when I wrote the code, but it's easy enough to extend the dmg vector to include both values.

In terms of minimum armor, I'm trying to figure out how minimum armor per cell would work? You would need to multiply the overall minimum armor (based on the base armor) by 1/15 for inner cells and 1/30 for outer cells or something to make it reasonable. For instance, if your base armor is 1000, then each cell has 66.67 starting armor, but your minimum armor would be 50, so you would effectively prevent your armor from going below ~75%. Maybe that is why your code is giving strange results as well?

I also realized that when I cleaned up this function, I made a mistake. I shouldn't be doing the actual hull and armor updates inside the function when I'm handling the expected value case/probabilities because then I would be changing the armor values while iterating through the different possible shot locations. Instead the function should just return the expected damage values to hull/armor, and the outer code can appropriately reduce the armor/hull. In the probabilistic case, that would involve adding up the expected damage contributions from each possible hit location and then subtracting them from the total all at once.

edit: I'm pretty sure the way I was doing minimum armor is right, since I matched results with vanshilar in the last thread. Armor cells don't really 'contribute' to minimum armor. They contribute to pooled armor, and if pooled armor is too low, .05*base armor is used instead. So there is still minimum armor that way, even if all the cells are stripped.
« Last Edit: November 22, 2022, 08:56:07 AM by intrinsic_parity »
Logged

Liral

  • Admiral
  • *****
  • Posts: 717
  • Realistic Combat Mod Author
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #137 on: November 22, 2022, 08:34:35 AM »

I've posted a potential reference implementation in Java on the modding questions thread.

NuclearStudent

  • Ensign
  • *
  • Posts: 20
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #138 on: November 22, 2022, 11:01:12 AM »

Nick, the Detailed Combat Results guy, is updating his mod in the next few days to have callable methods to output sim data to log. He's open to any suggestions about information to log or features that'd make simming easier.

Link of comms: https://imgur.com/a/LY0fYeV
Link of example datadump: https://drive.google.com/file/d/14CvzqFJ5yHrXAVS1IcY1OoV6lPORaghJ/view?usp=share_link

Figured that you guys might get value from this to compare against a "real" simulation within SS itself, as with Vanshilar's work. I have no doubt that you guys would be better than I am at datascraping and analysis. I discussed this with Liral on the discord earlier this month, maybe we can collab about it in January-ish when I can fully devote my energy to this.
« Last Edit: November 22, 2022, 11:02:55 AM by NuclearStudent »
Logged

Liral

  • Admiral
  • *****
  • Posts: 717
  • Realistic Combat Mod Author
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #139 on: November 22, 2022, 07:28:55 PM »

I have now run the database code, found it did not quite work, modified it until it did, and ultimately discovered that the .csv or .ship files of some mods have caused bugs: namely Arma Armatura, Gundam Universal Century, and Scy.  Only Low Tech Armada and Practice Targets passed through cleanly.  I have created a duck-tape solution: a function that checks for the ids of these mods and hardcoded a constant tuple of those ids into the database code.

CapnHector

  • Admiral
  • *****
  • Posts: 1056
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #140 on: November 23, 2022, 04:07:07 AM »

Okay so I got my statistics and calculus and so on homework done (if you good folks have never looked at Lebesgue integrals, please do, it is fascinating) and found a bug. Another one is lurking somewhere. Anyway, the C++ code I wrote only applied the modifier vs. armor to hit strength and not damage, when it should be applied to both! Doh! See "d/m*h/m/(armorpooled+h/m)" in the fixed code below.

This gives a shorter time but still 52 seconds to kill the Dominator with Squall - Squall - Harpoon - Harpoon - Gauss - Gauss so something else is still off in the new code. Maybe in the new hit distribution, since I wasn't able to find it in the damage function?

Edit2: I found two more bugs. One was a small one affecting the final cell of the hit distribution which didn't really matter here. But here's the crux of it: we are either NOT supposed to pool armor here, or must apply a modifier later.

Explanation: we are computing damage by cell. Let's make some definitions
h hit strength (of shot)
d damage
d_adj damage adjusted for hit strength
a armor (of ship)
A_ij armor value of cell
A_ij_next next armor value of cell after this shot
m modifier (using the definition that damage to armor is d/m)
x_ij distribution factor of ship armor or damage to cell

Now assume all the max(0,...) etc. junk is correctly applied here so the presentation is relatively clean. We want to compute how much armor is damaged by the hit ie. A_ij_next. Now first let's see what happens when we pool the armor: We take d_adj = d*h/m/(h/m+a). That's what we know to be correct. Then the proportion of damage that hits the cell is d_adj*x_ij and A_ij_next = A_ij - d_adj*x_ij/m. Now let's see what happens when we compute cell by cell: we take d_adj = d*x_ij*h/m*x_ij/(h/m*x_ij+A_ij))%u2020 = d*x_ij*h/m*x_ij/(h/m*x_ij+a*x_ij)=d*x_ij*h/m/(h/m+a). And then A_ij_next = A_ij - d_adj.

So if we were to pool the armor and use a instead of A_ij at %u2020 then we would get the incorrect result. And the way I wrote the damage distribution D (as D(i,j) in the function) is that it includes the distribution factor both for cells and for probability.

Anyway that is why the previous method was right and pooling the armor here was incorrect. Fixed code:
Code
'double damage(NumericMatrix A, NumericMatrix D, double a, double a_mod, double d, double h, double m, double minimumdamageafterarmorreduction){
  double hd = 0;
  int rows_A = A.nrow();
  int cols_A = A.ncol();
  a = a/15;
  for (int j = 0; j < cols_A; j++){
  for (int i = 0; i < rows_A; i++){
    double armor = std::max(A(i,j), a_mod*a);
    double probmult = D(i,j);
    double adjusted_d = std::max(d/m*h/m/(armor+h/m)*probmult, minimumdamageafterarmorreduction*d/m*probmult);
if( adjusted_d <= armor){
      A(i,j) = A(i,j) - adjusted_d;
      A(i,j) = std::max(A(i,j), 0.0);
    }
    if (adjusted_d > armor){
      A(i,j) = 0.0;
      adjusted_d = (adjusted_d - armor)*m;
      hd = hd + adjusted_d;
    }
  }
  }
  return hd;
}
'

Hit distribution:

Code

# this function generates the shot distribution (a bhattacharjee distribution for the
#non-trivial case)

hit_distribution <- function(upperbounds, standard_deviation, spread){
  vector <- vector(mode="double", length = length(upperbounds)+1)
  if (standard_deviation == 0){
    if (spread == 0){
      vector[1] <- 0
      for (j in 2:(length(upperbounds))) {
        #if both spread and standard deviation are 0 then all shots hit 1 cell. this should be so even if
        #the ship has an even number of cells to prevent ships with even no. cells appearing tougher which is not
        #the case in the real game most likely
        if ((upperbounds[j] >= 0) & (upperbounds[j-1] < 0)) vector[j] <- 1
      }
      #return part of a box
    } else {
      vector[1] <- min(1,max(0,(upperbounds[1]+spread))/(2*spread))
      for (j in 2:(length(upperbounds))) vector[j] <- min(1,max(0,(upperbounds[j]+spread))/(2*spread)) - min(1,max(0,(upperbounds[j-1]+spread))/(2*spread))
      vector[length(upperbounds)+1] <- 1-min(1,max(0,(upperbounds[length(upperbounds)]+spread))/(2*spread))
    }
  } else {
    if (spread != 0){
      vector[1] <- hit_probability_coord_lessthan_x(upperbounds[1], standard_deviation, spread)
      for (j in 2:(length(upperbounds))) vector[j] <- (hit_probability_coord_lessthan_x(upperbounds[j], standard_deviation, spread)-hit_probability_coord_lessthan_x(upperbounds[j-1], standard_deviation, spread))
      vector[length(upperbounds)+1] <- (1-hit_probability_coord_lessthan_x(upperbounds[length(upperbounds)], standard_deviation, spread))
    } else {
      #if spread is 0 but standard deviation is not 0 we have a normal distribution
      vector[1] <- pnorm(upperbounds[1],0,standard_deviation)
      for (j in 2:(length(upperbounds))) vector[j] <- pnorm(upperbounds[j],0,standard_deviation) - pnorm(upperbounds[j-1], mean=0, sd=standard_deviation)
      vector[length(upperbounds)+1] <- 1-pnorm(upperbounds[length(upperbounds)], mean=0, sd=standard_deviation)
    }
   
  }
  return(vector)
}

With these we get the exact same result as from the simulation based method for Squall-Squall-Harpoon-Harpoon-Gauss-Gauss vs. Dominator (technically 26 vs 27 seconds according to my graph, but we might expect it to be a little faster since we are now also accounting for shield radius).



But honestly, you might want to write this whole thing differently using the "whole-armor" definitions and applying the modifier later as there is a high risk of confusion here. If individual cells can't contribute minimum armor when the pooled armor is not below threshold then there is literally no difference.

E3: alright that was confused and confusing even for me, since we are not strictly doing that and the definition of x_ij is not consistent (it is not correct to just insert Dij into hit strength in the algorithm). Here is some scaffolding for a more formal look at this. To be continued.


(In your mind please remove the as from D as they are just a result of copy paste and hurry. The damage distribution is then dD where d is shot damage. Then once again ignoring all the inelegant junk like max() and modifiers:

If you imagine that we are looking at the expected value of the hit strength at cell vs. expected value of armor at cell, and h is total hit strength, then you have hDij hit strength vs armor strength aijDij, so hDij/(hDij+aijDij) = h/(h+Aij) as the multiplier for damage and damage dealt is d*Dij*(h/(h+Aij)). Which is exactly what we are doing in the non-pooling function above. And its wrong to look at hit strength hDij vs armor strength sum(5x5 area in the way the game does it))

If it's confusing for even me who wrote it based on this intuitive imagining of ghost armor cells and probability waves, though, then that's probably a good reason to rewrite it with easier formalism but for the time being it does work.
« Last Edit: November 23, 2022, 10:02:03 AM by CapnHector »
Logged
5 ships vs 5 Ordos: Executor · Invictus · Paragon · Astral · Legion · Onslaught · Odyssey | Video LibraryHiruma Kai's Challenge

intrinsic_parity

  • Admiral
  • *****
  • Posts: 3071
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #141 on: November 23, 2022, 10:17:56 AM »

I think your problem is that you're trying to do the armor damage reduction for each armor cell individually. That's either wrong or done in an unnecessary way.

You do the damage reduction once to the full shot damage using the pooled armor value, and then divide the adjusted damage amongst the cells using the 1/15 and 1/30 factors. The whole (d/(armor +d)) adjustment should not happen cell-wise.

Edit: maybe I misinterpreted code, not 100% sure what is being done outside of the loop/code snippet being shown, so I think it could theoretically be mathematically correct, but you definitely should not need to do that armor reduction calculation inside a loop over armor cells ever. At the very least, that should be moved outside of any loops over armor cells.
« Last Edit: November 23, 2022, 10:33:46 AM by intrinsic_parity »
Logged

CapnHector

  • Admiral
  • *****
  • Posts: 1056
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #142 on: November 23, 2022, 10:46:38 AM »

Well, it seems to work. I'm having a little bit of trouble imagining the "whole-ship" formalism now that I got the idea, but I can't seem to get it together without coming back to cell by cell computations because of the probability. Because the problem is of course probability, not damage distribution. Could you tell me how you would account for probability to hit a given cell, when doing it in bulk as you describe? What is the proportion of expected damage to a cell when you also have a probability distribution? It would certainly be much better to have simpler math for this as it's pretty confusing.

The main issue is that you have overlapping hits as it were. So how do you pool cells to get the total armor to compare to? Especially given they could have in principle arbitrary armor hp due to previous weapon hits.

Please show the problems in the matrix version of the above if you see some and I'll try to fix. Ie: looking at the matrices I posted above (and removing the a_ijs from D) then E(damage to cell) = Dij*damage, and 'If you imagine that we are looking at the expected value of the hit strength at cell vs. expected value of armor at cell, and h is total hit strength, then you have hDij hit strength vs armor strength aijDij, so hDij/(hDij+aijDij) = h/(h+Aij) as the multiplier for damage and damage dealt is d*Dij*(h/(h+Aij)). Which is exactly what we are doing in the non-pooling function above. And its wrong to look at hit strength hDij vs armor strength sum(5x5 area in the way the game does it))'

Now we had a discussion about whether cell by cell produces the corrected expected value in the last thread and at the very least Vanshilar found by simulating it that the error is at the most small IIRC, although the matter was finally left unsettled.
« Last Edit: November 23, 2022, 11:10:55 AM by CapnHector »
Logged
5 ships vs 5 Ordos: Executor · Invictus · Paragon · Astral · Legion · Onslaught · Odyssey | Video LibraryHiruma Kai's Challenge

Liral

  • Admiral
  • *****
  • Posts: 717
  • Realistic Combat Mod Author
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #143 on: November 23, 2022, 12:27:16 PM »

Well, it seems to work. I'm having a little bit of trouble imagining the "whole-ship" formalism now that I got the idea, but I can't seem to get it together without coming back to cell by cell computations because of the probability. Because the problem is of course probability, not damage distribution. Could you tell me how you would account for probability to hit a given cell, when doing it in bulk as you describe? What is the proportion of expected damage to a cell when you also have a probability distribution? It would certainly be much better to have simpler math for this as it's pretty confusing.

The main issue is that you have overlapping hits as it were. So how do you pool cells to get the total armor to compare to? Especially given they could have in principle arbitrary armor hp due to previous weapon hits.

Please show the problems in the matrix version of the above if you see some and I'll try to fix. Ie: looking at the matrices I posted above (and removing the a_ijs from D) then E(damage to cell) = Dij*damage, and 'If you imagine that we are looking at the expected value of the hit strength at cell vs. expected value of armor at cell, and h is total hit strength, then you have hDij hit strength vs armor strength aijDij, so hDij/(hDij+aijDij) = h/(h+Aij) as the multiplier for damage and damage dealt is d*Dij*(h/(h+Aij)). Which is exactly what we are doing in the non-pooling function above. And its wrong to look at hit strength hDij vs armor strength sum(5x5 area in the way the game does it))'

Now we had a discussion about whether cell by cell produces the corrected expected value in the last thread and at the very least Vanshilar found by simulating it that the error is at the most small IIRC, although the matter was finally left unsettled.

I want to know if I understand what we're doing, so here's my best understanding.  We have a horizontal row of armor cells A across which we want to compute the probable damage of one shot from some weapon.  First, pad this row with three ghost armor cells above, below, and to the left and right to form an armor grid G.  Next, for the ith cell from the left of A, ai, generate such a separate grid of ghost armor cells as follows:

111
12221
12221
12221
 111


Calculate and distribute the damage of one hit from the weapon in question across each grid and save the resulting hull damage in a corresponding row H.  Then, for each grid, for each cell, multiply the difference of the cell value from that of the corresponding cell in G by the probability of hitting ai and subtract the product from the cell in G.

Do I understand correctly?

intrinsic_parity

  • Admiral
  • *****
  • Posts: 3071
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #144 on: November 23, 2022, 01:08:41 PM »

You have a set of possible events (locations the shot can land) along with the damage that occurs (over multiple cells) if the shot lands there (a function of the shot location). The expected value of a function of a discrete random variable is just  E[f(x)] = sum(f(x) * p(x)) over all values of x. So in this case x is the shot location, and if you consider the armor cell the shot landed on as the random variable, then it is a discrete random variable. Then f(x) is just the normal damage calculations. The hard part is figuring out the probability distribution of that random variable p(x) based on the underlying distribution of possible shot angles, but I think we already did that.

Then on a high level the code should be:

loop over possible shot locations

calculate damage to the entire armor array and hull given that the shot landed in that particular location (damage|location) and store the values

end loop

expected_damage = sum(damage|location*p(location)) (again both hull and armor cell values)

I guess you could do the probability multiplication inside the loop and sum as you go to get the total expected damage, and then subtract the total expected damage off of the armor values and hull value at the end of the loop. It's very important to not subtract the armor damage from the armor values mid loop though, because you need to use the pre-shot armor values for the entire loop.

Edit, maybe the confusion is that inside that f(x) function, there is another loop through armor cells? That is the loop that should not contain the (d/(d+a)) expression. The outer loop (over shot locations, which is also a loop over armor cells) obviously has to contain all the damage calculations. Maybe you were trying to do it all in a single loop? I'm not sure if that is possible.
« Last Edit: November 23, 2022, 02:05:50 PM by intrinsic_parity »
Logged

Liral

  • Admiral
  • *****
  • Posts: 717
  • Realistic Combat Mod Author
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #145 on: November 23, 2022, 05:23:51 PM »

You have a set of possible events (locations the shot can land) along with the damage that occurs (over multiple cells) if the shot lands there (a function of the shot location). The expected value of a function of a discrete random variable is just  E[f(x)] = sum(f(x) * p(x)) over all values of x. So in this case x is the shot location, and if you consider the armor cell the shot landed on as the random variable, then it is a discrete random variable. Then f(x) is just the normal damage calculations. The hard part is figuring out the probability distribution of that random variable p(x) based on the underlying distribution of possible shot angles, but I think we already did that.

Then on a high level the code should be:

loop over possible shot locations

calculate damage to the entire armor array and hull given that the shot landed in that particular location (damage|location) and store the values

end loop

expected_damage = sum(damage|location*p(location)) (again both hull and armor cell values)

I guess you could do the probability multiplication inside the loop and sum as you go to get the total expected damage, and then subtract the total expected damage off of the armor values and hull value at the end of the loop. It's very important to not subtract the armor damage from the armor values mid loop though, because you need to use the pre-shot armor values for the entire loop.

Edit, maybe the confusion is that inside that f(x) function, there is another loop through armor cells? That is the loop that should not contain the (d/(d+a)) expression. The outer loop (over shot locations, which is also a loop over armor cells) obviously has to contain all the damage calculations. Maybe you were trying to do it all in a single loop? I'm not sure if that is possible.

I think we agree and must now vectorize the necessary operations for NumPy to execute quickly.   I want to show you an example of what we have to work with.  This code initializes the armor cell row, encompassing armor grid, and virtual armor grid corresponding to each cell on the armor cell row.

import numpy as np

armor_per_cell = 100
armor_row_width = 10
armor_row = np.full(armor_row_width, armor_per_cell)
print("armor row")
print(armor_row, "\n")

padding = 2
armor_grid_width = armor_row_width + 2 * padding
armor_grid_height = 1 + 2 * padding
armor_cell_ids = np.arange(armor_grid_width * armor_grid_height)
armor_grid = np.reshape(armor_cell_ids, (armor_grid_width, armor_grid_height))
print("armor grid")
print(armor_grid, "\n")

virtual_armor_grids = np.array(
    [armor_grid[i - padding - 1 : i + padding] for i in
    range(padding + 1, armor_row_width + padding + 1)]
)
print("virtual armor grids")
print(virtual_armor_grids)
output
armor row
[100 100 100 100 100 100 100 100 100 100]

armor grid
[[ 0  1  2  3  4]
 [ 5  6  7  8  9]
 [10 11 12 13 14]
 [15 16 17 18 19]
 [20 21 22 23 24]
 [25 26 27 28 29]
 [30 31 32 33 34]
 [35 36 37 38 39]
 [40 41 42 43 44]
 [45 46 47 48 49]
 [50 51 52 53 54]
 [55 56 57 58 59]
 [60 61 62 63 64]
 [65 66 67 68 69]]

virtual armor grids
[[[ 0  1  2  3  4]
  [ 5  6  7  8  9]
  [10 11 12 13 14]
  [15 16 17 18 19]
  [20 21 22 23 24]]

 [[ 5  6  7  8  9]
  [10 11 12 13 14]
  [15 16 17 18 19]
  [20 21 22 23 24]
  [25 26 27 28 29]]

 [[10 11 12 13 14]
  [15 16 17 18 19]
  [20 21 22 23 24]
  [25 26 27 28 29]
  [30 31 32 33 34]]

 [[15 16 17 18 19]
  [20 21 22 23 24]
  [25 26 27 28 29]
  [30 31 32 33 34]
  [35 36 37 38 39]]

 [[20 21 22 23 24]
  [25 26 27 28 29]
  [30 31 32 33 34]
  [35 36 37 38 39]
  [40 41 42 43 44]]

 [[25 26 27 28 29]
  [30 31 32 33 34]
  [35 36 37 38 39]
  [40 41 42 43 44]
  [45 46 47 48 49]]

 [[30 31 32 33 34]
  [35 36 37 38 39]
  [40 41 42 43 44]
  [45 46 47 48 49]
  [50 51 52 53 54]]

 [[35 36 37 38 39]
  [40 41 42 43 44]
  [45 46 47 48 49]
  [50 51 52 53 54]
  [55 56 57 58 59]]

 [[40 41 42 43 44]
  [45 46 47 48 49]
  [50 51 52 53 54]
  [55 56 57 58 59]
  [60 61 62 63 64]]

 [[45 46 47 48 49]
  [50 51 52 53 54]
  [55 56 57 58 59]
  [60 61 62 63 64]
  [65 66 67 68 69]]]
« Last Edit: November 23, 2022, 06:12:49 PM by Liral »
Logged

CapnHector

  • Admiral
  • *****
  • Posts: 1056
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #146 on: November 23, 2022, 08:34:14 PM »

Well, it seems to work. I'm having a little bit of trouble imagining the "whole-ship" formalism now that I got the idea, but I can't seem to get it together without coming back to cell by cell computations because of the probability. Because the problem is of course probability, not damage distribution. Could you tell me how you would account for probability to hit a given cell, when doing it in bulk as you describe? What is the proportion of expected damage to a cell when you also have a probability distribution? It would certainly be much better to have simpler math for this as it's pretty confusing.

The main issue is that you have overlapping hits as it were. So how do you pool cells to get the total armor to compare to? Especially given they could have in principle arbitrary armor hp due to previous weapon hits.

Please show the problems in the matrix version of the above if you see some and I'll try to fix. Ie: looking at the matrices I posted above (and removing the a_ijs from D) then E(damage to cell) = Dij*damage, and 'If you imagine that we are looking at the expected value of the hit strength at cell vs. expected value of armor at cell, and h is total hit strength, then you have hDij hit strength vs armor strength aijDij, so hDij/(hDij+aijDij) = h/(h+Aij) as the multiplier for damage and damage dealt is d*Dij*(h/(h+Aij)). Which is exactly what we are doing in the non-pooling function above. And its wrong to look at hit strength hDij vs armor strength sum(5x5 area in the way the game does it))'

Now we had a discussion about whether cell by cell produces the corrected expected value in the last thread and at the very least Vanshilar found by simulating it that the error is at the most small IIRC, although the matter was finally left unsettled.

I want to know if I understand what we're doing, so here's my best understanding.  We have a horizontal row of armor cells A across which we want to compute the probable damage of one shot from some weapon.  First, pad this row with three ghost armor cells above, below, and to the left and right to form an armor grid G.  Next, for the ith cell from the left of A, ai, generate such a separate grid of ghost armor cells as follows:

111
12221
12221
12221
 111


Calculate and distribute the damage of one hit from the weapon in question across each grid and save the resulting hull damage in a corresponding row H.  Then, for each grid, for each cell, multiply the difference of the cell value from that of the corresponding cell in G by the probability of hitting ai and subtract the product from the cell in G.

Do I understand correctly?

Pretty much but here's the beef of it, I'll try to be as informal as possible:

Let's say that we have a line of n armor cells. Then, for each of the n armor cells, compute probability to hit that cell. Call this p_k.

Now, create a new matrix that is of width k and padded with 2 cells above, below, left and right. Since armor is pooled this way in Starsector that we even have virtual cells outside hittable cells, this represents the armor matrix the shots see. For the first iteration set each cell to starting armor/15, then later keep it as whatever it is after armor takes damage.

Now, how does this armor take damage?

If we were to it through loops we must calculate, for each cell, at the topmost cells, 1/30th of the damage FOR each of the up to three shots that can damage the cell multiplied by the probability of each of those hits separately (e.g. for a middle cell k for the top and bottom row, 1/30p_(k-1)+1/30p_k+1/30p_(k+1).). For the middle rows, 1/15 damage for each of the up to three shots where this cell can be a middle cell and 1/30 damage for each of the up to two shots where this cell can be an edge cell, multiplied by probability of each hit separately. Then loop over armor.

What my code does instead is pre-compute the probability and damage distribution for each weapon into the damage distribution matrix D (the one we store in the lookup table for each weapon at each timepoint) so the loop is just damage multiplied by damage distribution matrix for each cell.

Now the other consideration is hit strength and if we are doing it using this method then you do not pool the armor but use the matrix D also (the expected value of hit strength to that cell) and the armor at that cell (times D_cell for the expected value of the armor that the shot is "seeing"). Specifically 1/15 the hit strength for each of the up to three shots where the cell can be a central cell times the probability of those shots plus 1/30 the hit strength for each of the up to three shots where the cell can be a peripheral cell times probability versus armor of 1/15 for each of the up to three shots where the cell can be a central cell times the probability of those shots plus 1/30 the hit strength for each of the up to three shots where the cell can be a peripheral cell times probability as this is how the armor would be pooled to meet the shot.

Doing the hit strength calc in aggregate is what the game does. But then using the probabilistic method and not doing shots one by one, the question is what is the armor for the hit strength calculation so that the damage distribution calculation remains accurate, if we were to do that? Because each cell is hit up to 5 times with different fractions of a shot rather than once but we only have 1 step where we distribute the damage. I don't have an answer at this time and seems non trivial, you may want to pen and paper this out.

For a very easily imaginable example of the problem with aggregate hit strength calculations when we have probabilistic shots, a shot with very narrow spread is going to "see" different cells than one with very wide spread, so how do you account for that in the hit strength calculation when the armor is damaged and is not uniform, if doing it in aggregate? In this example for example it would be wrong to use whole ship armor for both shots for the hit strength calculation without any adjustment - if you doubt this, then consider that for a gun, hit strength and damage are equal, but were you to do this then they would be spread differently. It is also not correct to calculate hit strength for each middle cells and subtract damage immediately as then we have order of operations affecting damage (the previous subtraction reduces armor for the next hit strength calculation). It should be correct to calculate it for each middle cell pooling the surroundings, saving the value somewhere else, then distributing all the damage according to the D matrix in one step (ie. 1/30 of the damage for peripheral hits and 1/15 for central hits times probability of each hit separately). But then you are doing the exact same thing as the cell by cell, just in a more complicated order. Doing it cell by cell removes this issue.

I've got a hunch that pooling the armor to account for the problem above is going to involve the same matrix as distributing the hit strength and it's going to make no difference, because this is what imagining things the shot sees tells me, but haven't done the pen and paper math.
« Last Edit: November 23, 2022, 09:41:34 PM by CapnHector »
Logged
5 ships vs 5 Ordos: Executor · Invictus · Paragon · Astral · Legion · Onslaught · Odyssey | Video LibraryHiruma Kai's Challenge

intrinsic_parity

  • Admiral
  • *****
  • Posts: 3071
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #147 on: November 23, 2022, 09:49:48 PM »

I think, you're making this way harder than it has to be. I really don't understand what's wrong with looping over shot locations. It works fine.


I ported my code into python, and verified it produces the same results as my MATLAB code. It probably could be optimized but it's reasonably fast. A quick test found that calculating the expected damage of one shot took ~.00064 seconds (averaged over 10000 trials) on my laptop (2.3 GHz i9).

Code
import numpy as np


def getArmorIndexes(location, armor_grid):

    inner_cells = np.full(armor_grid.shape, False)
    outer_cells = np.full(armor_grid.shape, False)

    if any(np.less_equal(location, 1)) | location[0] > armor_grid.shape[0] - 3 | location[1] > armor_grid.shape[1] - 3:
        raise Exception("hit location must not be on the edge of the grid")

    inner_cells[location[0] - 1: location[0] + 2, location[1] - 1: location[1] + 2] = True

    outer_cells[location[0] - 2, location[1] - 1: location[1] + 2] = True
    outer_cells[location[0] + 2, location[1] - 1: location[1] + 2] = True
    outer_cells[location[0] - 1: location[0] + 2, location[1] - 2] = True
    outer_cells[location[0] - 1: location[0] + 2, location[1] + 2] = True
   
    return inner_cells, outer_cells


def armorUpdate(dmg, location, armor_grid, minimum_armor):
    # dmg is a vector with elements:
    # [shield_damage, armor_damage, hull_damage, shield_hit_strength, armor_hit_strength, hull_hit_strength]
    # location is a tuple of the coordinates in the armor grid where the shot lands
    # armor_grid is an array with each element corresponding to an armor cell
    # minimum armor is the smallest armor value the pooled armor is allowed to take. Typically .05*max_armor

    inner_cells, outer_cells = getArmorIndexes(location, armor_grid)

    armor_pooled = np.maximum(np.sum(armor_grid[inner_cells]) + 1 / 2 * np.sum(armor_grid[outer_cells]), minimum_armor)

    armor_damage_reduction = np.maximum(dmg[4] / (dmg[4] + armor_pooled), .15)

    damage_armor = (1 / 15 * inner_cells + 1 / 30 * outer_cells) * armor_damage_reduction * dmg[1]

    damage_hull = np.maximum(damage_armor - armor_grid, 0) * dmg[2] / dmg[1]

    damage_hull_total = np.sum(damage_hull)

    return damage_armor, damage_hull_total


def expectedArmorDamage(locations, location_probabilities, dmg, armor_grid, minimum_armor):

    damage_armor_expected = np.zeros(armor_grid.shape)
    damage_hull_expected = 0

    for i, location in enumerate(locations):
        damage_armor, damage_hull = armorUpdate(dmg, location, armor_grid, minimum_armor)
        damage_armor_expected += damage_armor * location_probabilities[i]
        damage_hull_expected += damage_hull * location_probabilities[i]

    return damage_armor_expected, damage_hull_expected


Lmao, as soon as I looked at my code, I noticed optimizations I could do. For instance, I pass in the entire armor_grid array to the getArmorIndexes function when I only need to pass in the size of the array. There's also quite a few unnecessary intermediate variables, but I kinda like the improved readability.

Also, just to summarize what the code does. The first function (getArmorIndexes) takes shot location coordinates and the armor grid (should just be the size of the armor grid) and returns boolean arrays of the same size as the armor grid with all the inner cells or outer cells set to 'true' and all others set to false. That's super convenient for doing calculations.

The second function (armorUpdate) takes the initial armor grid, the damage of the shot, the location the shot lands, and the minimum armor value, and returns the damage dealt to each armor cells as well as the total hull damage dealt.

The last function expectedArmorDamage takes all the arguments of armorUpdate, except the shot location is replaced by the set of possible shot locations and the associate probabilities. It returns the expected damage to each armor cell and the expected hull damage.
« Last Edit: November 23, 2022, 10:03:48 PM by intrinsic_parity »
Logged

CapnHector

  • Admiral
  • *****
  • Posts: 1056
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #148 on: November 23, 2022, 10:27:40 PM »

Well, here's a better look at this:



I can't read that code very easily, so I think the easiest way to show that it is correct is that you apply your code to calculate times to kill vs ships and show that it produces reasonable results in practice. Because it's honestly not very easy to see when you are falling into the trap of applying the incorrect (non-probability-adjusted) armor strength for the hit strength calculation even when it's your own code, at least for me.

If it's still hard to see where the danger lies basically just imagine that you have 1 weapon (weapon A) that repeatedly hits the center of the armor and 1 weapon (weapon B) that hits uniformly over the armor. Now if you are applying the whole armor for the damage reduction then you will get correct results for weapon B but incorrect results for weapon A after shot 1, because weapon A doesn't "see" the peripheral cells ever so you are reducing its damage too much. Weapon A doesn't "see" the cells right outside of the cells it damages either so when you are applying damage to outermost cells that weapon A damages then you still are not allowed to include armor values from outside weapon A's "vision" in the hit strength calculation.

I mean if you avoid that trap and have a simple way of computing it that's great but I certainly fell right into that trap when I just naively applied pooling and then got obviously incorrect results when I tried to use that for the time to kill.
« Last Edit: November 23, 2022, 10:45:39 PM by CapnHector »
Logged
5 ships vs 5 Ordos: Executor · Invictus · Paragon · Astral · Legion · Onslaught · Odyssey | Video LibraryHiruma Kai's Challenge

intrinsic_parity

  • Admiral
  • *****
  • Posts: 3071
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #149 on: November 23, 2022, 10:43:09 PM »

I already verified that my MATLAB code matched the TTKs from vanshilars excel speed sheet way back when we started all of this (in the other thread when we discussing movement based inaccuracy and distributions). I also verified that the EVs from my MATLAB code were reasonably close to the averaged damage values from large numbers of deterministic trials. All I did today was port the code into python and verify that it produces the same results as the MATLAB code.
Logged
Pages: 1 ... 8 9 [10] 11 12 ... 32