Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Liral]

Well, for the time being all distributions are, in fact, symmetrical, unless we want to start adding asymmetrical distributions. It's possible of course, just doesn't exist now.

If you wanna optimize the Conquest, you're gonna need asymmetrical distributions to account for the limited turret traverse because it can't fire both broadsides at once.

That reminds me: hardpoints should be added. I never considered them due to only studying conquest. They should have half spread.

 Even then, the pooling/distribution matrices only have 2 real rows that are formatted like this:
R1
R2
R2
R2
R1

So this must also be the case for the rows of the armor matrix at all times since one thing we are not doing AFAIK is adding more complicated armor shapes. Of course we could, if we wanted to. It would just be a case of figuring out the projection of the armor shape to the circle (or tangent, to be crude) at the range and then using the points corresponding to cell edges with the prob dist function for the hit probabilities for cells, and either a map of how the cells pool armor when the matrix is projected to a linear shape, or a padded matrix of several rows corresponding to the armor shape. Anyway.

Then pooling armor could be done just like: 3x pool cells of R2, 2x pool cells of R1. Distribution should be the exact same as it is now except only 2 rows. And hull damage the same as now except multiplied by 2 for R1 and 1 for R2.

That's what I did, and it was about as fast if not a little slower.

I do not understand how it could be slower to compute a sum of 2 rows over a sum of 5 rows? But I guess I don't know a lot about computers.

I have no clue either.  Maybe NumPy doesn't like that shape. 

By matrices I meant that it is quite easily possible to formulate these in any number of ways using vectors, matrices etc. For example we could compute damage to a cell as the elementwise product of vectors, like I did before (ie damage to 1 cell from 1 shot is shot damage times pooling row/15 dot (elementwise product of (sub-vector of adrs and sub-vector of probabilities))) or as a matrix multiplication operation using diagonal matrices. And I was thinking I could look at tensor products and such. But can switching to such operations make it faster, or will it make it slower?

I wish you could understand the NumPy code because you would have seen that the pooling weights are already a 5x5 matrix and that it is multiplied by a 5x5 slice of the armor grid, which is also a matrix; it even has a second 5x5 damage distribution matrix that has already baked the 1/15 factor in.  We might need other libraries to speed this code up further.

I mean for a human calculating by hand it would be a terrible choice to define armor damage using matrix multiplication rather than sums, much less something like a Kronecker product but since I really don't know about computers they could have special parts or algorithms for dealing with such things for all I know.

You could try profiling

                  [ a1  a2  a3  a4  a5 ]  [ 1/2 ]
                  [ a6  a7  a8  a9  a10]  [ 1   ]
[ 1/2 1 1 1 1/2 ] [ a11 a12 a13 a14 a15]  [ 1   ] - mean(a1,a5,a21,a25)
                  [ a16 a17 a18 a19 a20]  [ 1   ]
                  [ a21 a22 a23 a24 a25]  [ 1/2 ]

to see if it's faster than the sum operation (note: mean because 4 values multiplied by 1/4, but I assume it is more optimized than 1/4*sum. if not so, replace with 0.25*sum(a1,a5,a21,a25))

I have tried it now, and it is about ten times worse than the weighted approach because selecting those odd numbers requires python coding.  NumPy is so much faster than Python that brute force but idiomatic approaches can beat smart but custom ones.

If you were to use vector operations then you could loop over cells only once for dealing damage (instead of dealing damage to it 3 to 5 times separately) so I wonder if that could speed things up?

How would I do that?

To handle the entire calculation using matrix multiplication, which I should imagine would be the most optimized thing due to its importance, and no sub-vectors, which I imagine are costly, define

Two kinds of optimization exist in a tight NumPy loop: reducing the work that NumPy must do and reducing the amount of Python code involved.

Say that the ship has n hittable cells ("ship cells"). Then define

P is a diagonal matrix of dimensions n+4 x n+4, where element p[i+2,i+2] = probability to hit ship cell i and all others are 0
ADR a diagonal matrix of dimensions n+4 x n+4, where element adr[i+2,i+2] = armor damage reduction at ship cell i and all others are 0
D is the matrix multiplication product P ADR
w_i is a vector 1 row, n+4 column matrix that has 1 at indices from i-1 to i+1, 1/2 at i-2 and i+2, and 0 otherwise, and these vectors correspond to ship cells i  (or -1 to 0 or n+1 to n+2 for padding) (special case: at the edges only consider indices that are defined for the above definition)
damage_edge_i is a 1 column, n+4  matrix with values 0 1/30 1/30 1/30 0
at indices i-2 to i+2 and 0 otherwise , special case likewise, with i corresponding to ship cell (or -1 to 0 or n+1 to n+2 for padding)

damage_center_i is a 1 column, n+4row matrix with values 1/30 1/15 1/15 1/15 1/30 at indices i-2 to i+2 and 0 otherwise, special case likewise, with i corresponding to ship cell. (or -1 to 0 or n+1 to n+2 for padding)

Then unless I am badly mistaken (I typed this on mobile while walking somewhere, will be away from keyboard for a while, maybe few days except intermittently) we can compute damage for edge cells as, letting d=damage(scalar)

d(w_i D damage_edge_i), referring to matrix multiplication, where i is the ship cell index (or -1 to 0 or n+1 to n+2 for padding)

and for the central cells it is

d(w_i D damage_center_i), i likewise.

While seemingly laborious all the matrices except D are constant and depend only on ship size so only computed once (or even pre-defined).
 So I was thinking even though it is 2 matrices for each cell, maybe it's faster for the computer due to fewer loops? Since using this you would compute the matrix D first, then loop over all armor cells doing above calculation at each cell once to determine incoming damage. By contrast distributing damage from each middle cell separately leads to 1 cell calculating damage 5 times. Additionally you could use the w_i for pooling: pooled armor at central cell i should be w_i A w_i^t - mean(a_(1,i-2),a_(1,i+2),a_(5,i-2),a_(5,i+2)) where A is the ship's armor matrix and ^t is transposition and a_ij is the armor cell at i,j.

I don't quite understand.

Also note that you can again just compute 1 edge row and 1 central row and when you are done, set the other rows to equal them as appropriate, so you really loop over only 2/5th of the armor (1/5th if you do the half ship thing)

This can also, of course, be implemented by referencing - compute adrs at each of the central cells, then loop over the 2/5th of armor and compute damage*(adr_at_i-2*weight _i-2*probability_i-2 + adr_at_i-1*weight _i-1*probability_i-1+...+adr_at_i+2*weight _i+2*probability_i+2). Again loop over 2 rows and compute rest with equals operations.

(Edit: i edited the wi definition to permit pooling).

Edit: 1 more idea. Let armor be a complex number. then you can pool armor with

                  [ a1  a2  a3  a4  a5 ]  [ i/2 ]
                  [ a6  a7  a8  a9  a10]  [ 1   ]
[ 1/2 1 1 1 i/2 ] [ a11 a12 a13 a14 a15]  [ 1   ]
                  [ a16 a17 a18 a19 a20]  [ 1   ]
                  [ a21 a22 a23 a24 a25]  [ i/2 ]

without any need for referencing or manipulating the elements, so long as at the end you count the pooled armor as sum of both the imaginary part and the real part of the sum.

Logic: the first multiplication turns the top edge into a real with half the value and bottom edge into an imaginary number with half the value (while summing the columns, of course). Then the second multiplication turns the left edge and right edges into imaginary numbers with half the value, except the corner cells at the bottom which are turned into real numbers with a negative value of one quarter of the original and subtracted from the armor (while summing the row). The corner cells on the top edge on the other hand are turned into imaginary numbers with a quarter of the original value. Because top and bottom edges are symmetrical, this cancels out the corners exactly while summing the rest with the appropriate weight, so long as at the end you compute pooled armor = Re(sum)+Im(sum).

Tried it now, and it is 50% slower than the usual.

[Thaago]

When you have code where you are happy/confident that it is outputting correct values, I can do an optimization pass as I have some experience in that with python. Send me a DM please as I'm only checking in here every once in a while!

[Liral]

We have been working with an armor grid that is essentially just a line of hittable cells with padding, but real ships aren't like that. They have corners and weird geometry which would ruin all this symmetry. We definitely don't want to bake in that really basic armor grid model and preclude actual ship models.

In terms of performance, matrix multiplication is an implicit inner loop over the elements of the matrix, so I don't think you are reducing the theoretical number of calculations by re-formulating in that way, just hiding them in a different operation. However, in python, it could very well be faster to do it that way because the linear algebra library is likely implemented very efficiently in a lower level language, while a high level loop in python is not. It's hard to say what will be best just looking at equations on paper.

There's lots of other fine details to speed in programming. For instance, memory is not free. It takes time to allocate and access memory, and sometimes, longer than to just do some extra calculations. Eliminating or pre-allocating temporary/intermediate variables is often a big performance booster.

Another non-intuitive one is that when dealing with multi-dimensional arrays, iterating over columns vs rows can result in different performance. This is because the data is actually stored in linear memory, so elements adjacent in the array are not necessarily adjacent in memory https://en.wikipedia.org/wiki/Row-_and_column-major_order. It's even more fun when you find out it is language dependent which way the data is stored. I'm pretty sure our arrays are going to be small enough for it to not make a huge difference though.

In my opinion, the best way to optimize code is to first write code that does what you want, then profile it to see what parts/functions/lines etc. are taking the most time, then find ways to improve those things.

Yeah, I would agree, though while we're working directly with the bottom of the code, we might as well see about squashing it down.  Here's hoping that we find other ways to save time.

[Liral]

When you have code where you are happy/confident that it is outputting correct values, I can do an optimization pass as I have some experience in that with python. Send me a DM please as I'm only checking in here every once in a while!

Wooooooo! 

[intrinsic_parity]

Thanks, interesting stuff! This is an area where I have relatively little to contribute unfortunately. But now that we basically have / are very close to having the code in Python, but with limitations in performance (see Liral's post - hence hunting for optimizations), do you have ideas about how to improve the strategy for testing, say, ship variants against each other, or a very large number of weapons versus a set of ships in order to rank them by some attribute?

I have ideas about ways of running numerical optimization on loadouts using some sort of combat model, but I think we are still quite far from having a simulation that is actually useful for that purpose.

In terms of performance, I think the issues are a little overstated. On my laptop (2019 Intel MacBook Pro, 2.3 GHz I9), my MATLAB code (which is not super optimized) takes about ~7 seconds to run the armor damage calculations 1000000 times (without any parallelization). My laptop has relatively unimpressive clock speed and 8 cores, so I would expect 3-6x reduction in time with parallelization based on personal experience. I would expect comparable performance (or better with good optimization) in python.

Based on my experience, most combat simulations take a few hundred shots for a kill, so that 1000000 armor damage calculations probably corresponds to 1-2 thousand combat simulations. I think that speed should be sufficient to run optimization code in a reasonable amount of time (several minutes). Obviously any improvements would be great though. Brute force searching all possible combinations of weapons/loadouts for a ship is still probably out of the question though just due to the combinatorics of how many possible ways there are to create a loadout. Obviously this is all very ‘back of the napkin’ approximations.

Here is my assessment of where we are and what we still need to do:

Current state (feel free to add anything I am missing):
in python:
- armor damage calculations (given hit strength and armor grid)
- expected armor damage (given shot distribution, hit strength and armor grid)
- some shot distribution calculations (given range, armor grid dimensions)
in R:
- more complex weapon mechanics (beams, charge up/charge down, burst weapons)
- some rudimentary AI for shield management
- a basic simulation

The remaining non-translated R code is mostly part of the broader simulation rather than the damage calculations. We still need to build out all the simulation code in python that calls the damage calculations.

In order to do numerical optimization, what we need is a function which takes all of the parameters to be optimized (loadout, hopefully including all weapons, hullmods, caps/vents), as well as the simulation parameters (ships, skills, opponent loadout etc.) and runs the simulation to return the value of the metric that we are trying to improve for that specific case. We will also likely need to write some constraint functions, but we can worry about that later.

What I think we need to do:
- translate remaining R code for weapon mechanics and stuff to python
    - this might require to some reformulation depending on how the simulation is implemented in python
- create a simulation structure in python
    - need to handle flux dynamics, including soft/hard flux from both firing weapons and shield damage
    - need to figure out time steps to handle all the different types of weapons (beams, burst weapons etc.)
    - IMO we need to handle variable range as well (will talk about this later)
- create a programatic system for getting appropriate weapons and ship data
    - I know Liral was trying to do this for weapons stats from the CSV file already
    - ship stats should be similar (parsing a CSV file), unless we try to handle actual ship geometry for the armor grid, and need to pull that data (which is not in a file format I am familiar with)
- choose a metric to optimize and create a function that utilizes the simulation to calculate that metric
- wrap this in the optimization code (probably from a generic optimization package, I can handle this)

Handling range is something I’ve been think about. Obviously, the big issue is that the shot distribution depends on range, and we don’t want to be recalculating that constantly, but I have some ideas when we get there. We would also need some rudimentary AI to manage range for each ship.

Also, I think we are definitely getting to the point where a GitHub would be very helpful for collaboration. I think the method of copy/pasting code from the forum will get very inefficient very fast. I am happy to write some code.

[Liral]

I have ideas about ways of running numerical optimization on loadouts using some sort of combat model, but I think we are still quite far from having a simulation that is actually useful for that purpose.

In terms of performance, I think the issues are a little overstated. On my laptop (2019 Intel MacBook Pro, 2.3 GHz I9), my MATLAB code (which is not super optimized) takes about ~7 seconds to run the armor damage calculations 1000000 times (without any parallelization). My laptop has relatively unimpressive clock speed and 8 cores, so I would expect 3-6x reduction in time with parallelization based on personal experience. I would expect comparable performance (or better with good optimization) in python.

Glad to read more confirmation that a potato can handle it.

Based on my experience, most combat simulations take a few hundred shots for a kill, so that 1000000 armor damage calculations probably corresponds to 1-2 thousand combat simulations. I think that speed should be sufficient to run optimization code in a reasonable amount of time (several minutes). Obviously any improvements would be great though. Brute force searching all possible combinations of weapons/loadouts for a ship is still probably out of the question though just due to the combinatorics of how many possible ways there are to create a loadout. Obviously this is all very ‘back of the napkin’ approximations.

Your calculations match the ones I did earlier.

Here is my assessment of where we are and what we still need to do:

Current state (feel free to add anything I am missing):
in python:
- armor damage calculations (given hit strength and armor grid)
- expected armor damage (given shot distribution, hit strength and armor grid)
- some shot distribution calculations (given range, armor grid dimensions)
in R:
- more complex weapon mechanics (beams, charge up/charge down, burst weapons)
- some rudimentary AI for shield management
- a basic simulation

The remaining non-translated R code is mostly part of the broader simulation rather than the damage calculations. We still need to build out all the simulation code in python that calls the damage calculations.

In order to do numerical optimization, what we need is a function which takes all of the parameters to be optimized (loadout, hopefully including all weapons, hullmods, caps/vents), as well as the simulation parameters (ships, skills, opponent loadout etc.) and runs the simulation to return the value of the metric that we are trying to improve for that specific case. We will also likely need to write some constraint functions, but we can worry about that later.

What I think we need to do:
- translate remaining R code for weapon mechanics and stuff to python
    - this might require to some reformulation depending on how the simulation is implemented in python
- create a simulation structure in python
    - need to handle flux dynamics, including soft/hard flux from both firing weapons and shield damage
    - need to figure out time steps to handle all the different types of weapons (beams, burst weapons etc.)
    - IMO we need to handle variable range as well (will talk about this later)
- create a programatic system for getting appropriate weapons and ship data
    - I know Liral was trying to do this for weapons stats from the CSV file already
    - ship stats should be similar (parsing a CSV file), unless we try to handle actual ship geometry for the armor grid, and need to pull that data (which is not in a file format I am familiar with)

The database is good-enough for general-purpose use but could be made more convenient.  The database can read CSVs and .ship files from vanilla and some mods, returning nested dictionaries for each source, ship_data.csv row, weapon_data.csv row, and .ship file.  I could make it transform the data types of the 'bottom' dictionary elements from strings into directly-usable floats, decimals, and integers, and I could even write accessor methods to allow searching by weapon_id and ship_id directly.

- choose a metric to optimize and create a function that utilizes the simulation to calculate that metric
- wrap this in the optimization code (probably from a generic optimization package, I can handle this)

Handling range is something I’ve been think about. Obviously, the big issue is that the shot distribution depends on range, and we don’t want to be recalculating that constantly, but I have some ideas when we get there. We would also need some rudimentary AI to manage range for each ship.

Let's just let the user set one or several engagement ranges before we start talking AI.

Also, I think we are definitely getting to the point where a GitHub would be very helpful for collaboration. I think the method of copy/pasting code from the forum will get very inefficient very fast. I am happy to write some code.

CapnHector, what do you think?

[CapnHector]

I think definitely start a github now. The discussion is excellent. Also, my ability to contribute as a person who is profiled 100% for theory rather than programming is getting quite limited. Feel free to proceed from here as you see fit.

I do have an idea about asymmetrical weapon arcs. Essentially it's this: if the target is at the edge of the weapon arc then this results in a shifted uniform distribution for the firing angle. So a shifted version of the convolved normal dlst. Then when you have multiple weapons with different limited arcs the ship should calculate the optimal position for dealing damage to the target and assume that position. This is a matter of maximizing damage*area under curve of probability distribution from ship edge to ship edge for all weapons. And that should be just a function of damages, shifts and coordinates. Using calculus we already have an integral of the PDF so auc is just F(highercoord)-F(lowercoord), but we probably don't even need calculus because in our reality the distribution is discretized and can be formulated using sums. I'll get to working out the details when I have a chance.

I won't develop the matrix theory further since you did find it to be slower in the most basic function, although let me know if you think it would still be useful.

[Liral]

I think definitely start a github now. The discussion is excellent.

I agree.

Also, my ability to contribute as a person who is profiled 100% for theory rather than programming is getting quite limited. Feel free to proceed from here as you see fit.

I feel sad because learning how to code could open many doors for you in academia, work, and hobbies, and I hope you learn soon because you could do it and would enjoy it.  I would even teach you, answer your questions, etc.! 

I do have an idea about asymmetrical weapon arcs. Essentially it's this: if the target is at the edge of the weapon arc then this results in a shifted uniform distribution for the firing angle. So a shifted version of the convolved normal dlst. Then when you have multiple weapons with different limited arcs the ship should calculate the optimal position for dealing damage to the target and assume that position. This is a matter of maximizing damage*area under curve of probability distribution from ship edge to ship edge for all weapons. And that should be just a function of damages, shifts and coordinates. Using calculus we already have an integral of the PDF so auc is just F(highercoord)-F(lowercoord), but we probably don't even need calculus because in our reality the distribution is discretized and can be formulated using sums. I'll get to working out the details when I have a chance.

Sweeeeeet!

[CapnHector]

Oh don't worry, I definitely have been inspired to learn, when I have an opening in my schedule. This project is currently in my hobby slot and it's been fun and educational. I've even found a professional idea about theoretical statistics I'd like to spend some time researching at some point, but we'll see.

[intrinsic_parity]

Dealing with weapon arcs also requires dealing with the rotational state of the ships, which once again might require some rudimentary AI.

Also, when I say rudimentary AI, I mean some basic conditional rules, not like a whole complicated attempt to imitate the game. It could be as simple as 'fly forward if xyz flux conditions met, else fly backward' for range. I guess there's nothing wrong with also being able to handle fixed range, but IMO it's a pretty integral part of combat.

Rotations seem harder to deal with. I guess you could again choose a specific rotational state, but it seems quite complicated to make that user friendly.

[CapnHector]

Here is what I think we're solving illustrated professionally in MSPaint

(of course in reality there are an arbitrary number of weapons and a minimum and maximum angle for each based on how you rotate the ship towards enemy ie. select target angle, of which either the minimum or maximum is used based on whether the target is higher or lower in angle)

Now here's the thing that the computation does become recursive if we want to find the optimum angle for the whole combat, because then we'd want to know which weapons have the highest dps vs hull, armor and shields on average vs. the target, but since shields regenerate we'd need to know how long the combat lasts in the first place to know how much we should weight shield dps. There are at least three solutions:
1) guess the value (say, based on how long the average combat lasts vs that ship, or alternatively a naive non-matrix based calculation of how long it might last)
2) allow the ship to rotate during combat, so that it rotates to maximize armor damage when enemy flux is max, and only consider dps vs. the component you are targeting currently.
3) use fixed values based on ship stats to determine how to weight damage vs. shields, damage vs. armor and damage vs. hull.
Of course there is also the "correct" solution that you pick some reasonable starting point, run the combat, then improve your optimum target angle estimates based on that, then re-run the combat until you find the optimal angle. But I don't think we want to do that. I think basically we'd want the rotation version where the optimum angle changes once shields are down, since that is the realistic thing to do anyway.

[Liral]

For now, why not just let the user specify an angle for each ship in a separate file, as we do for range?

[CapnHector]

Well, for now I say ignore this whole issue since we don't even support weapon arcs of fire. First should get the utility put together as is, with all weapons firable directly at the target. This will work fine for testing the balance of weapons, though not of ships. That should take some time so good time to figure this out. The priority now should be integrating the code, putting together a complete fight against a ship and creating functions to print out graphs of it and optimizing in my opinion. I'm just thinking about this since I can't really help with that.

As is, I don't think adding a rotation parameter is very useful right now since it does nothing unless the whole structure with ship rotation and turret arcs are implemented. It would be a complete pain for the user to specify a rotation for each ship to be tested manually, not to mention quite unrealistic to test all possible rotations of a number of ships, so I don't think that's a good option, rather implement a coherent way for the program to handle the whole thing or skip entirely for the time being (like for the Conquests I only included the  missiles and one broadside).

This should eventually amount to a change to the hit distribution based on weapon arcs and ship rotation so nothing that can't be added later or that would interfere with the damage calculations. Well, other than it breaks horizontal symmetry, so the code must not assume that. Vertical symmetry on the other hand would only be broken by a deeper than 1 row amor grid.

In the meantime, users can test rotation much more intuitively by specifying which weapon slots are available. Want to test Conquest broadside? 2x LM, 2x medium missile, 2x large gun,  2x medium. Want to test frontal firepower at medium range? 2x large missile, 2x medium energy. Etc. Not saying this is optimal, just that nothing need be added for now until the complete package is figured out.  But it's already publishable without it for weapon and weapon combinations testing and that can even be a later upgrade.

By the way, here are some more initial thoughts on the turret rotation issue. Don't know when have a chance to really sit down with it but I keep  thinking about it occasionally. Say that angle 0 is the angle exactly to the right of the ship's facing. Then we can give each turret a maximum and minimum angle. Let's say that a turret's maximum angle and minimum angle in these coordinates are m and n. Then it should be the case that the maximum mean point for the turret's hit distribution is m-spread/2 (see mspaint above) and minimum is n+spread/2. Call these points a and b respectively.

Now to target the enemy ship, let's say the enemy ship is at angle t in these coordinates. We can freely rotate so can freely choose t. Then for each gun the midpoint of the probability distribution is a, when t>a, t, when a>t>b, b< t>b.

Then to calculate AUC we should calculate  F(x2)-F(x1) where x2 and x1 are the enemy ship's edge angles and F(x) is the CDF of probability (determined fully by the mean point, spread and sd). Now given that it's also the case that x1=t-width/2 and x2=t+width/2 then this should actually lead to a differentiable expression for AUC as a function of t, especially when we use the differentiable approximation x/(1+e^-x) for max(x,0).

[intrinsic_parity]

FWIW, rotation state also changes the locations of armor cells, and changes which cells are visible, and the AI rotates the ship with this in mind as well. It's definitely pretty complicated. I think range is much simpler to handle.

If we are picking a fixed angle, we should just check which weapons can fire forward in the selected orientation and use those, rather than assuming all weapons can fire.

[CapnHector]

I'm still not necessarily sold on adding returning fire or enemy ship rotation. I guess it's a matter of what the goals of the program are. If the goal is a quick, rough search of potentially overpowered weapons or problematic layouts then it does not necessarily serve our interests to add a lot of complexity and assumptions. Not only does it increase processing time but also adds more sources of potential errors in code or in our assumptions or model.

On the other hand, if the goal is a fully realistic test then it absolutely must be added. The question is, is that a realistic goal for the program? Will it ever be fully realistic? Will people rather not use the sim especially if the program takes very long? Will our recreation of combat be credible?

In my opinion the first use case is more justifiable since a player could never do such a wide search as this model can in the sim and that is where this is irreplaceable.

Ultimately if the final code is developed together it's a matter of time and discussion to see what features come about ofc.