Algo for Re-writing Casualty Selection

[DanVanAtta]

The algorithm for default casualty selectoin does not take into account movement, has a very questionable level of caching, and is really complex (650+ lines)

I'm thinking to fix it, we need to back up, simplify and re-write it.

Proposed Algorithm

I'm thinking the logic should instead be as follows:

• for each casualty
• apply all combat modifiers that do not depend on other units
• calculate the power of each unit, any support should be summed to the unit providing the support
• sort first by power, then by cost, then by movement
• select the least of the sort
• repeat until all casualties selected.

Examples

So for example, if selecting 1 casualty from 2 arty and 2 inf, we would have:

arty 1 -> 3 power, 4 cost
arty 2 -> 3 power 4 cost
inf 1 -> 1 power, 3 cost
inf 2 -> 1 power, 3 cost

In this case we select one of the infantry.

Selecting another casualty, we would have:

arty 1 -> 3 power, 4 cost
arty 2 -> 2 power 4 cost
inf 1 -> 1 power, 3 cost

Again we would choose an infantry if selecting 1 casualty.

If we had an amphiboius assaulting marine with an infantry and 2 arty, selecting 1 casualty:

marine 1-> (2+1) power 4 cost // +1 for amphib assault
arty 1 -> (2+1) power, 4 cost  // +1 for support to marine
arty 2 -> (2+1) power, 4 cost
inf 1 -> 1 power, 3 cost

We would choose inf 1.

For the next casualty:

marine 1-> (2+1) power 4 cost // +1 for amphib assault
arty 1 -> (2+1) power, 4 cost  // +1 for support to marine
arty 2 -> (2) power, 4 cost

We would select arty 2.

Selecting a 3rd casualty:

marine 1-> (2+1) power 4 cost // +1 for amphib assault
arty 1 -> (2+1) power, 4 cost  // +1 for support to marine

This one is a toss-up (in which case we would sort by movement, but they have the same movement, so it's a toss-up).

[RoiEXLab]

@DanVanAtta We need to consider the case where only certain units are able to capture land. For example: Let's say we're attacking with

• 1 fighter
• 1 armor

In this case I'd choose the fighter if I really need to capture the land and it isn't sufficient to just defeat everyone in it. However same scenario with

• 1 fighter
• 1 infantry

is a lot trickier. The infantry not only has lower attack values, but is also cheaper so in this case you maybe value your fighter over a real victory and you choose the infantry instead.

Not sure where this line should be drawn tbh

[tvleavitt]

This only becomes more extreme with, say, bombers in place of fighters.

Or sea battles with carriers, where sacrificing the carrier, even though it is more expensive, may make sense at some point in favor of other units... or, you may want to preserve the carrier, because losing it means your fighters have no place to land, etc.

Thomas

On Thu, Apr 16, 2020 at 1:39 AM RoiEX notifications@github.com wrote:

@DanVanAtta https://github.com/DanVanAtta We need to consider the case where only certain units are able to capture land. For example: Let's say we're attacking with

• 1 fighter
• 1 armor

In this case I'd choose the fighter if I really need to capture the land and it isn't sufficient to just defeat everyone in it. However same scenario with

• 1 fighter
• 1 infantry

is a lot trickier. The infantry not only has lower attack values, but is also cheaper so in this case you maybe value your fighter over a real victory and you choose the infantry instead.

Not sure where this line should be drawn tbh

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/triplea-game/triplea/issues/6268#issuecomment-614502512, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABB5HAMQVTP7MOSPBFNU4HLRM272LANCNFSM4MJJG74Q .

-- Thomas Leavitt Internet enabled since 1990

[DanVanAtta]

The algorithm in question is the default OOL selection. If a user defines a custom OOL then that would have precedence. This is the algorithm that is responsible for selecting bombers first on defense even though that is something not the wisest move. In essence the algo should strive to maintain max combat power so that if you select all of the default options you maximize the odds of winning the battle. For example, some units have very long range, but very low attack power and high cost. Those units should be selected first before other units with higher attack powers even if that is more costly in terms of TUV.

The existing algo is really complicated and does an absurd amount of caching. To do a simple update to say "select equivalent units that have less movement before those with more movement" is frighteningly complex.

In the end the algo maximizing combat power is about as best we can do and is on-par with the current one.

Strategy Decisions - cannot be decided by this algo, we are maximizing for overall combat odds

Territory Capture

We will not be able to decide this for a user. The question of whether to sacrifice an expensive high powered attack unit in order to save a land unit and get a capture is too difficult for us to answer programmatically. It is a strategic decision.

For example, sometimes you only want one unit to capture and prevent placement. Sometimes you want to sacrifice all air to maximize the chance to hold the territory. Other times the territory is not worth that much and you do not want to capture at all.

We can't make this decision programmatically for a user, it depends on circumstance and players strategy.

Bomber vs Fighter Casualty

This again goes to strategy. Sometimes fighters will be selected just because a bomber is so valuable that a player is willing to try and defend on a one for the sake of keeping the bomber. Sometimes it's clear that the attack is just strafing, and sometimes there could be another country that can follow-up (ie: germany + italy combined strafing to kill both a fighter and bomber, in that case you may want to lose the bomber first).

[Cernelius]

Interestingly enough, that seems wrong. If you have 2 artillery with 2 infantry, both infantry would be better selected as casualties first before selecting any artillery unless an artillery gave a bonus to infantry that was greater than the attack power of another artillery.

@DanVanAtta I believe you are reading it wrong (but I don't believe it is very clear). That is not referring to any units of any particular games, but just to two unit types having the same "attack" value, and one supporting the other. In your case, just take your regular "artillery" and "infantry", but lower the attack value of the "artillery" to 1, rest remaining the same.

[Cernelius]

  /**
   * The purpose of this is to return a list in the PERFECT order of which units should be selected
   * to die first, And that means that certain units MUST BE INTERLEAVED. This list assumes that you
   * have already taken any extra hit points away from any 2 hitpoint units. Example: You have a 1
   * attack Artillery unit that supports, and a 1 attack infantry unit that can receive support. The
   * best selection of units to die is first to take whichever unit has excess, then cut that down
   * til they are both the same size, then to take 1 artillery followed by 1 infantry, followed by 1
   * artillery, then 1 inf, etc, until everyone is dead. If you just return all infantry followed by
   * all artillery, or the other way around, you will be missing out on some important support
   * provided. (Veqryn)
   */

For a practical example of this, you can take the "archers" and "spearInfantry" of "Lord of the Rings: Middle Earth".

[DanVanAtta]

You're right cernel, but I do think we are getting beyond the point. The key thing here is the algorithm. Is it missing anything, will it be correct? There are examples written in the OP.

On Thu, Apr 16, 2020, 2:41 PM Cernelius notifications@github.com wrote:

/**

• The purpose of this is to return a list in the PERFECT order of which units should be selected
• to die first, And that means that certain units MUST BE INTERLEAVED. This list assumes that you
• have already taken any extra hit points away from any 2 hitpoint units. Example: You have a 1
• attack Artillery unit that supports, and a 1 attack infantry unit that can receive support. The
• best selection of units to die is first to take whichever unit has excess, then cut that down
• til they are both the same size, then to take 1 artillery followed by 1 infantry, followed by 1
• artillery, then 1 inf, etc, until everyone is dead. If you just return all infantry followed by
• all artillery, or the other way around, you will be missing out on some important support
• provided. (Veqryn) */

For a practical example of this, you can take the "archers" and "spearInfantry" of "Lord of the Rings: Middle Earth".

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/triplea-game/triplea/issues/6268#issuecomment-614911821, or unsubscribe https://github.com/notifications/unsubscribe-auth/AC6SZOMEBAUEZFCMBIHHQD3RM53R7ANCNFSM4MJJG74Q .

[Cernelius]

I recall the algorithm was mostly made by @ron-murhammer and, as long as we have only positive supports to the same side, I have never seen it failing to maximize remaining power. However, I don't know much about the reliability of the recently added ability of giving multiple supports of the same type to a same unit (currently available only for the prerelease).

I vaguely recall some problems when giving negative supports to the opposite side.

[Cernelius]

Not sure if I'm being off topic, but my main issue with the Casualty Selection Algorithm is that it ignores AA attacks completely (relevant if they last for more than 1 round of combat).

[DanVanAtta]

@Cernelius there is history available line-by-line to determine who wrote when, it is not pertinent nor am I looking for feedback from the original author per-say (it does not matter as its being re-written after having seen/observed what is there and what is being taken into account).

I updated the OP to more clear. The problem is that it's a mess, the caching is questionable, and it's not going to be trivial to take into account unit movement. 650 lines is way more than is needed.

Not sure if I'm being off topic, but my main issue with the Casualty Selection Algorithm is that it ignores AA attacks completely (relevant if they last for more than 1 round of combat).

AA attacks are computed in a completely different section of code (which regrettably is also a mess).

[Cernelius]

any support should be summed to the unit providing the support

I'd rather say the support bonus should be summed to the one in the shortest supply between the giver and the receiver (as long as you select as casualty 1 unit every time, then recalculate it, before selecting the next one).

Basically the question would be whether, for that support type, we have more units that can receive support than the available support bonuses to be given or the other way round. If exactly the same, it doesn't matter taking one or the other.

[Cernelius]

AA attacks are computed in a completely different section of code (which regrettably is also a mess).

Do you believe this should be the case? AA attacks lasting infinite rounds are not much different than (and may be exactly the same as) first strike attacks (say, submarines).

[DanVanAtta]

@Cernelius the algo does state:

for each casualty

So we are looking at it each casualty at a time. The summation to the supporter is the number of support attack power it is providing. That is demonstrated in an example where one of the artilleries goes from a calculated power of 3 to 2 after it no longer is providing support.

[DanVanAtta]

Do you believe this should be the case? AA attacks lasting infinite rounds are not much different than (and may be exactly the same as) first strike attacks (say, submarines).

1. Combining selection of AA casualties is out of scope here, merging that selection is a different update than what is being proposed. It would also probably make this update impossible as we would we be trying to solve too many problems at the same time. It's better to solve this first, then see if that makes sense. It's akin to trying to clean your garage, attic, kitchen all at the same time and not completing until all three are done rather than doing one at a time.

2. No, it actually does not make sense. It does not matter how casualties are created, the algo here is "given X hits, which order should those casualties be chosen". We are talking about the default order of loss algorithm for standard combat rounds where remaining units are not all of the same type.

[ron-murhammer]

So I didn't write the original algorithm but did make enhancements to it around supportattachments and performance. You are welcome to take a shot at either re-writing or improving it but I would highly recommend waiting til after the 2.0 release as it is pretty complex and will require a lot of testing.

Here are the known limitations that are not handled well currently (just off the top of my head):

• AA attack/defense
• Negative support values
• Multi-HP units which change into weaker units when damaged (ex. TWW battleships shouldn't take the first hit as default casualty if there are weak sea units like subs/destroyers)

The default casualty selection should do at least the following prioritization:

1. Provide the optimal casualty selection to maximize the chance to win the battle considering all factors (AA and negative support can make this very complex) - essentially losing which unit leaves my side with the most strength and ideally the enemy with the least strength
2. Check for certain battle influencing attributes (sub, destroyer, etc)
3. Take cheaper units before more expensive ones
4. Take lower remaining move units

@DanVanAtta What you've laid out so far, I don't believe would be sufficient and result in worse casualty selection than we have today. You need to consider receiving and giving support essentially equally. Take a look at Napoleonic Empires for example where you have 2 equal units where one provides support and the other gives it, say on attack you have just fusiliers/howitzers and took all your fusiliers before all the howitzers as casualties.

[Cernelius]

Right, then I confirm that I believe support should not be generally summed to the unit providing the support, but to the one in shortest supply. I guess you can assign it randomly on a 50% in case the available support bonuses are exactly the same number as the receivers. For example, in "Lord of the Rings: Middle Earth", if you have as many attacking "archers" as "spearInfantry", and no other attacking units, and have 1 casualty to take, you can throw a coin to decide if to take 1 "archers" or 1 "spearInfantry" (here meaning summing the support to one or the other on an equal chance for either).

[DanVanAtta]

@ron-murhammer could you walk through a similar example as given in the OP and point out how an incorrect decision would be made? Support is accounted for, the third example demonstrates it.

Timing is immaterial as this is a planning task and it is hard to say when this will happen.

[DanVanAtta]

Multi-HP units which change into weaker units when damaged (ex. TWW battleships shouldn't take the first hit as default casualty if there are weak sea units like subs/destroyers)

That is handled as a post-processing step which would be out of scope from the algo. We need to only create a list of units to choose, and in which order, all units are actually assumed to be single hit and multi-hit is considered later. It wouldn't be bad to expand the re-write to loop that in, but we're then talking about 900~1200 lines of code rather than rewriting 700 lines.

[DanVanAtta]

I don't believe would be sufficient and result in worse casualty selection than we have today.

Please expound on such comments and provide more concrete examples. I'm finding this to be completely not helpful. Such an example is already provided in the OP how the scenario is accounted for, please note where it is different and how, kindly being specific so that we can have direction and specific problems to solve.

Would be nice to even suggest updates/edits to the algorithm.

[ron-murhammer]

@DanVanAtta Well I'm talking about the default casualty selection as a whole. How you want to chunk it up and design it is another discussion. You can consider multi-HP out of scope for the rewrite if you'd like.

In terms of your examples, they work fine but you need to consider examples with more variation in support and attack/defense values. So here is the example I describe:

howitzer 1 -> 2 (1+1) power, 4 cost
howitzer 2 -> 2 (1+1) power, 4 cost
fusilier 1 -> 1 power, 4 cost
fusilier 2 -> 1 power 4 cost

Select fusilier 2. Which is fine (could choose fusilier or howitzer here).

howitzer 1 -> 2 (1+1) power, 4 cost
howitzer 2 -> 1 power, 4 cost
fusilier 1 -> 1 power, 4 cost

Select fusilier 1 or howitzer 2? Must choose howitzer here otherwise you then have to supporting units with no units to provide support to. As 1 of each is 3 total power, where 2 howitzers is only 2 total power.

This gets even more complex when you start considering units that provide support to multiple other units or having different types of support units which provide varying levels of support to other units.

[DanVanAtta]

I think I see the gap, thank you. In more general, one can have this situation:

Unit A: attack 2
Unit B: attack 1, provides support of +2

In this case Unit B is better to take as casualty first, if either unit is alone then you want Unit A. If there is another Unit A available to receive the support, then it's Unit A that is better removed.

Is this solved by "adding equally support" to both units? Or is it more complicated? Initially that perhaps looks like it could work:

Unit A: 4 (2+2) // +2 for receiving support
Unit B: 3 (1+2) // +2 for providing support
Unit A: 2   // not receiving support

[DanVanAtta]

For multi-support case:

Unit B: 5 (1+2+2) // +1 base, +2 support to first unit, +2 support to next unit
Unit A: 4 (2+2 ) // + 2 for support
Unit A: 4 (2+2) // + 2 support

At this iteration one would choose Unit A, not B.

[DanVanAtta]

How you want to chunk it up and design it is another discussion

@ron-murhammer The contract of the method in question is pretty specific. I'm not looking to re-write the entire class here.

[DanVanAtta]

Any updates should get a test harness around it so we'll be pretty sure it works at least as well as what is there. From a context perspective, the code history and sleuthing through it for about 4 hours yesterday was quite a bit, came to the conclusion we are at a BBOM state and can go for a lot simpler.

---

Thinking about this convo, there are some updates which I think might work well. First, the existing algo calculates the ideal order of all units regardless of number of casualties. If we cap that to just the number of casaulties we should see a good improvement.

I'm thinking this for an updated algo:

• for each casualty
• for each unit type
• calculate the new firepower of the group with one less of that unit type
• remember the unit types with the max values
• break ties using cost and movement

[DanVanAtta]

Please excuse my hubris @ron-murhammer , @Cernelius . I'm interested to know more about the AA casualty selection problems that you are aware of.

[Cernelius]

Haven't said anything because I assumed was off topic, but I actually believe there might have been a misunderstanding. I was talking about AA-able units in general and, in particular, mostly about the issue of selecting as casualties of normal attacks units that are able to make AA attacks (for more than one round) not just, or even primarily, about the casualties selection of units targeted by AA attacks. For example, if you have a unit that has normal attack 0 but has some strong AA offensive attack, the engine will see it as an attack 0 unit (like a Classic transport) and select it as casualty before other units that are actually absolutely weaker (think about if that unit has an attack AA value of 1 or more that can target all enemy units currently in the battle and lasts for infinite rounds (then, it is substantially the same as a first strike unit (submarine) with the same regular attack value, thus absolutely superior to any units with a normal attack value of 1, yet the engine just sees it as an attack 0 unit, thus preselects it first)). Now that also regular attacks can target a selection of units (something before limited to a few cases, like submarines able to target any units but air units), the difference between a unit with AA attacks for infinite rounds and a unit with first strike and target options is easily nothing (maybe they should be somehow merged, but that's obviously off topic, and likely not feasible).

[DanVanAtta]

@Cernelius sounds like AA attacks should be a summation of all the air unit it is shooting at. Even then though, attacking multiple units gives greater possibility to do more damage in case multiple ones are rolled. It seems it would be difficult for the engine to know when it's better to lose an AA vs a stronger unit. For some of these rules we could add an options menu into the battle/casualty dialog to "prefer losing AA last"; hard to say if it's enough of a problem or common enough to be worth it.

[DanVanAtta]

I think the current algorithm just gave a bad result:

On Big World, amphib marines attack at a 3, with artillery they attack at a 4. Attacking with both artillery and marines, you want to keep all marines first as they are attacking at 3 even unsupported while artillery attack at a 2. In the above screenshot, after the first two artillery were selected, the engine selected a marine (seems incorrect)

[DanVanAtta]

Loading up Napoleonic Empires, the scenario you described @ron-murhammer worked properly. The game engine did prefer to remove 2 howitzers first from the 4 units, but if you remove a fusilier first dropping down to 3 units (1 fusilier and 1 howitzer), then it will recommend to remove a howitzer next. Maybe though that still not the most demonstrative as it appears the engine wants to just remove howitzer's first anyways. It would be nice to contrive up a scenario where we would see an interleaving of losing artillery then infantry.

[ron-murhammer]

So at the highest level check they would have equal total power as 2 marines + 1 art and 3 marines both equal 9. So as long as it took the art before the last marine then it would be mathematically alright for optimizing the battle's win chance.

But I think keeping individual power (base att/def, isMarine, etc) over support power should then be a tie breaker (better to take the art before any marines in this case). I'm not sure what all the tie breakers are currently without looking through the code. My guess is its probably comparing base att/def and not including active isMarine bonus.

[Cernelius]

I think the current algorithm just gave a bad result:

On Big World, amphib marines attack at a 3, with artillery they attack at a 4. Attacking with both artillery and marines, you want to keep all marines first as they are attacking at 3 even unsupported while artillery attack at a 2. In the above screenshot, after the first two artillery were selected, the engine selected a marine (seems incorrect)

No, this is fine. The artillery is in the shortest supply, thus it adds a total of 3 power, just like the marine. So, here, for taking 1 unit out, we are in a coin throw situation: taking the artillery or the marine is just as good.

you want to keep all marines first as they are attacking at 3 even unsupported while artillery attack at a 2.

This is a way to maximize power, but, once left with 1 artillery remaining, taking up to 2 marines first, then the artillery, then the remaining marines is the generally best practice (of which your case is a subset).

Starting with 3 artillery and 3 offloaded marines, these are all the possible combinations of causualties, taken in sequence, to maximize power: 3 artillery, 3 marine 2 artillery, 1 marine, 1 artillery, 2 marine 2 artillery, 2 marine, 1 artillery, 1 marine 1 artillery, 1 marine, 2 artillery, 2 marine 1 artillery, 1 marine, 1 artillery, 1 marine, 1 artillery, 1 marine

[Cernelius]

I think, when selecting casualties amongst attackers, in basic rules games, the tie breaker should be first the defence then the cost, if also the defence is the same, normally (for example, in WAW this would mean that, having the same number of elite and artillery and no other units, you take elite first, since artillery costs more).

For example, in Napoleonic Empires, if you have the same number of fusiliers and howitzers attacking alone, you maximize power by, either, taking 1 fusilier then 1 howitzer or 1 howitzer then 1 fusilier, repeating over and over again. In this case, the way to go would be taking the howitzer first, since it has the lowest defence.

Also, likely, an attack value boosted by the marine bonus should be deprioritized, on tie-breaking, with respect to the same normal power (for example, in Napoleonic Empires you have only offloaded marines and grenadiers in attack, alone, you take all marines first, even though they are both attack 3). On the other hand, if the marine bonus is a negative, then the marines should be taken last on tie.

Finally, when you have a unit that attacks at 2 normally and another one that attacks at 2 because of being positively supported, it makes sense to go with taking the supported one first.

If to make a hierarchy, it may be advisable following this order, on tie breaking, when the currently removed power is the same (meaning what to remove first): 1- lower cost 2- higher total support bonus. 3- higher total territory effect bonus. 4- higher marine bonus. 5- lower basic attack value if attacking or lower basic defence value if defending. 6- lower basic defence value if attacking or lower basic attack value if defending. 7- unit list order or random.

EDIT: Moved lower cost at first place, actually, since the next thing you want to maximize is probably the TUV swing, also for the battlecalculator.

[Cernelius]

@DanVanAtta Applying the above to your previous example, I substantially agree with taking first the 3 artillery, then the 3 marine. This in keeping with what I previously said that the support bonus should be assigned to the unit in the shortest supply between the giver and the receiver (in this case, it is the artillery, after you take out the first artillery).

[Cernelius]

@Cernelius sounds like AA attacks should be a summation of all the air unit it is shooting at.

I think we are still not on the same page. While, mostly out of mere legacy, the default targets are all air units only (which is not a good default, as it would be better the default being any units), I was not thinking in those terms at all. I was actually mostly thinking to the case the AA attacks were able to target whatever enemy units in the battle (which would make them possibly substantially the same as the submarine first strikes when there are only sea units in the battle (since these, instead, target all units but air units)).

[DanVanAtta]

@Cernelius you're right. It sounds like it's a question of how to properly compute attack power for a unit that otherwise has an attack power of zero, but an effective attack power that is non-zero.

@ron-murhammer good point on both summing to 9;

I would like for us to now focus on the updated algo and we can then iterate and hash out how to do resolution of ties and proper attack power accounting. For now so long as we have something that computes the same results, we are effectively on the right path.

Previously, the effective attack power of all units was computed and then we are choosing units based on the lowest attack power. This is difficult as attack powers are dependent on other units, there is a fundamental complexity to this. For example, you can't just say an artillery attacks at a 2, it is adding support, and same for units that are supported.

Proposed: for each unit type, we compute what the new total attack power of the whole group would if we subtract one of that unit type. We then select the unit type that results in the highest attack power.

I think the proposed algorithm is essentially the right one and what we are fundamentally doing. EG:

3 marines and 2 artillery. What's the attack power if we had 2 marines and 2 artillery, and what's the attack power if we had 3 marines and 1 artillery. The difference in that answer tells you which one to remove. A trivial case is non-supported units in which case you just remove the lowest attack power. I think we might have gotten to our current algorithm to account to support offsets by trying to keep the strategy of choosing the lowest attack power and added in a fudge factor to account for support.

[DanVanAtta]

Crud, I'm not sure if that was clear.

The big difference is in how we score units. For example, currently we do a per unit attack power, eg:

Marine : 4 (amphib & supported)
Artillery 1: 3  (providing support)
Artillery 2: 2 (base attack)

We take the lowest on the list, then we recompute and keep taking the lowest on the list until we've gone through all units.

The proposed update computes the score across the group and we would take the max, eg:

Marine: 4  (removing a marine results in 2 artilleries remaining)
Artillery 1: 6  (removing an artillery results in 1 marine on amphib assault supported by on artillery, 4+2)

In the above you choose artillery, the resulting attack power of the group is maximized after that removal.

It's just a slightly different way to compute the per unit scores, and one important point is that we'd be computing it by unit type rather than unit-by-unit.

[ron-murhammer]

@DanVanAtta I believe it has some logic to only check each unit type once and the caching is done using unit types as well.

[DanVanAtta]

The cache logic will precompute everything. Though the cache is by player, by attack/defense, by territory, and by units. A cached computation will run in about 2-5 microseconds. The non-cache case iteratively computes attack (or defense) values for every unit participating in the offense or defense and typically runs in about 20-50 microseconds.

Ultimately we would be going for simpler code, more maintainable and places us in a position for more fundamental optimizations. Currently we're in a BBOM state and change is unlikely and risky.

The runtime is a consideration for sure, but if we have a runtime that is 2x-10x slower, it perhaps will not matter as we would be talking about an increase in execution time for AI over a game phase of milliseconds. To another extent, it's kinda unfortunate there is any AI dependency on this code at all, that probably should not exist and worst case we fork the logic to the AI. The AI does need to make strategic decisions, I think we're potentially seeing inappropriate re-use of logic. IF there were no AI dependency then the efficiency could be reduced 1,000x and it would still would be below the threshold for human perception of a difference in time.

[ron-murhammer]

@DanVanAtta Actually last time I did performance testing casualty selection and route finding were the 2 most critical performance areas in the engine. One thing to remember is you can have battles with 100s of units with 20 different unit types on each side. And these have simulation counts in the battle calc of at least 100s if not 1000s. I believe this is also by far the slowest portion of the battle calc. Try running a large battle in the BC on WaW or TWW with lots of various units on each side and you'll see it takes seconds and I believe most of that time is spend in the casualty selection.

Any changes here should be closely performance tested. And actually the AI isn't even the limiting factor. If you increase the time this method takes by even 2-3x then it makes a significant impact on human players using the battle calc.

[Cernelius]

One thing to remember is you can have battles with 100s of units with 20 different unit types on each side. And these have simulation counts in the battle calc of at least 100s if not 1000s. I believe this is also by far the slowest portion of the battle calc.

@ron-murhammer You could have such an enormous xml full of every kind of triggers and conditions that would take such a long time to load on the battlecalculator that would dwarf anything else, comprising the time needed to run the simulations. This is now actually a rather easy "achievement", with the new "variableList" feature.

For example, I'm close releasing a game that, on my system, has the battlecalculator taking 5 seconds to "copy data", which is a bigger time that what it takes to run most simulations, at my default of 1000 run count (on the other hand, except rare multi-power defences, there are never more than 9 types of units per side and even the biggest stacks tend to be of only a few tens of units, in this game).

Of course, you are right for possibly each and every game currently in the repository, instead.

[DanVanAtta]

2 micros * 1000 -> 1 millisecond, could be 10x slower and we'd be at 10ms, well below human perception. That is the data we have so far though, would need to see more. We're getting premature to really discuss at that level. For at least a game round of AI we can tolerate as much as 5x slower, if not 20x (I turned off the cache and noticed the 10x-20x in measurements, but it was not significant from an overall timing).

It's:

• working
• simple
• fast

In that order. We missed the second step. Battle-calc I think is still dominated by the game data copy. A large, late game WaW takes 5-7s to copy game data, that is time before the battle calc can do anything. It's immaterial if we shave 1s and fail to see the bigger picture.

If you increase the time this method takes by even 2-3x then it makes a significant impact on human players using the battle calc.

So I don't think that is a statement we can make at this point. We should look at overall timing, but increases of 100ms to battle calc (imply a 3 order of magnitude slow-down) are still well within tolerance.

[Cernelius]

@DanVanAtta Ah right, forgot. Even maps with a very small xml (next to no triggers at all), like WAW, may become quite heavy, because of the history, after many rounds.

[ron-murhammer]

@DanVanAtta Please provide some test data before making those assumptions. In particular, showing how long the BC takes for a large battle in WaW and how much of that time is in casualty selection. As well as doing the same for the AI.

[DanVanAtta]

The data I measured with the 2micro's and 20micros without cache was for AI.

For WaW, I raised the perf issue before. The scaling of the data copy is poor and makes late game WaW difficult to play. I am not planning on checking that as it does not matter.

I did not make assumptions, perhaps you have misread. If an something is taking 20micros and we execute it 1000 times, we are at 20,000 micros, which is 20 ms. A 10x increase gets us to 2ms. We would want to be sure that the 1000x is the actual scaling factor.

The current algorithm iterates through collections quite a lot, it's not linear. The battle calc is currently not computing isMarine properly, and it looks like the OOL cache does not get updated in case territory effects are ever changed. The OOL cache issue is a problem that could be addressed here.

[DanVanAtta]

For WaW, I raised the perf issue before. The scaling of the data copy is poor and makes late game WaW difficult to play. I am not planning on checking that as it does not matter.

The problem is the data copy before any thing else happens. Hence it does not matter for this discussion as it's not pertinent. The point though is that we may be losing the forest through the trees.

[ron-murhammer]

Let's just put it this way. Let's ensure the battle calc and AI performance are as good or better after any changes to this.

[DanVanAtta]

There is memory consumption to consider, and there is significant thresholds. Are we going to reject a change due to a 1% increase, say that being 0.1 seconds slower on a large calc?

I don't know if there is a long running disagreement here but I do stand by: "It's better to optimize correct code than to correct optimized code"

Performance gains are also generally gained through simplicity and design, not clever algorithms or optimizations to complex areas of code. If we have optimized a BBOM and can no longer ever make changes, we are sacrificing all forward progress to maintain an expensive status-quo.

[DanVanAtta]

We'll also need to weight benefits of any potential fixes. It does not look the OOL cache is invalidated with:

• technology, artillery supporting 2 units would not be taken into account
• terrain effects changing, I'm not aware of such a scenario but if terrain modifiers were to change post-caching they would not be applied.

There are a number of considerations and unknowns to all this. Regardless, we are in a sub-optimal state currently (BBOM land).

[DanVanAtta]

To document one more problem.. If there is a marine and infantry and artillery, total world war for example where marine and infantry attack at the same power, support is not applied to the more expensive of the two units. In testing I observed the marine being selected first because the support was applied to the infantry, a less expensive unit.

[DanVanAtta]

Alright, a very interesting case where the engine surprised me and also a case where the number of casualties is an input to which selections you want to make.

Scenario:

• improved arty
• 2 marines
• 1 tank
• 1 arty

If you have to take 3 casualties, the best choice is to keep the tank. If you have to take fewer than you want to kill the tank.

EG:

marine @ 4
marine @ 4
arty @ 2 (and providing +2, effective of a +4)
tank @ 3

So one by one, the order would be: { tank, artillery|marine, artillery|marine, marine }

But, if you lose three units, then your best attack is either a marine (@3) or a tank (@3), in which case the tank is the best choice.

The really odd thing, currently the engine does provide the right answer. I think this only might be because the arty support is not distributed correctly. If the artillery is not improved, then the order would be: {artillery|marine, artillery|marine, marine, tank}

All indications is the current algo does compute casualties one at a time, which gives weight that the engine is not properly computing improved artillery.

[Cernelius]

Alright, a very interesting case where the engine surprised me and also a case where the number of casualties is an input to which selections you want to make. Scenario:

improved arty 2 marines 1 tank 1 arty

If you have to take 3 casualties, the best choice is to keep the tank. If you have to take fewer than you want to kill the tank. EG: marine @ 4 marine @ 4 arty @ 2 (and providing +2, effective of a +4) tank @ 3

Not really. This would be correct if you get only 1 casualty. However, if you get 2 casualties, keeping the tank is still the best choice, as you would want to take out 1 marine and 1 artillery.

If you remove 1 tank, that is a -3, and removing 1 other unit is a -4, for total -7.

If you remove 1 marine, that is a -4, then removing 1 artillery is a -3, for total -7.

So, taking out the tank is the single best choice when getting 1 hit, but it is not the single best choice when getting 2 or 3 hits.

I'm assuming here that you would want to save the tank as a higher cost tie breaker (since I understand that 1 tank or 1 marine alone have the same attack value), since, power wise, taking the tank first is always equal or better than any other choices, no matter how many hits.

So one by one, the order would be: { tank, artillery|marine, artillery|marine, marine }

Yes, which means only:

1: tank, artillery, marine, marine 2: tank, marine, artillery, marine

But, if you lose three units, then your best attack is either a marine (@3) or a tank (@3), in which case the tank is the best choice.

Yes, if you define a tie breaker that says so.

The really odd thing, currently the engine does provide the right answer. I think this only might be because the arty support is not distributed correctly. If the artillery is not improved, then the order would be: {artillery|marine, artillery|marine, marine, tank} All indications is the current algo does compute casualties one at a time, which gives weight that the engine is not properly computing improved artillery.

Yeah, this example is good to demonstrate that, if you use cost as a tie breaker, then you should be doing it by assigning all hits taken, as it may get sub-optimal doing it 1 hit at a time. Good catch.

As long as this:

If you have to take 3 casualties, the best choice is to keep the tank. If you have to take fewer than you want to kill the tank.

Is changed to "If you have to take 2 or 3 casualties, the best choice is to keep the tank. If you have to take 1, then you want to kill the tank.", then, I agree.