Casualty Selection Algorithm Re-write

[trevan]

I've been recently looking at the casualty selection algorithm in CasualtyOrderOfLosses. I've gone over the last discussion in #6268 and #6376.

Based on those discussions and what I've seen, I think there might be a better way to select casualties.

Just to ensure everyone is on the same page, here is how the current algorithm works:

1. Sort all of the units by their "main power" (using offensive power if they are offensive units and vice versa), then by cost, then by their "opposite power" (using defensive power if they are offensive units), then by some "tie breakers", and finally by their remaining movement.  All of this logic is in [UnitBattleComparator](https://github.com/triplea-game/triplea/blob/master/game-core/src/main/java/games/strategy/triplea/delegate/battle/UnitBattleComparator.java#L74).
  a. The "tie breakers" are: sub/destroyer gets +4 power, multi hp units that can repair get +1 power, transporting units get +1 power, air units get +1 power, carrier units get +1 power, and transports (that aren't transporting) get +1.  These "tie breakers" are also used in the "main power" and "opposite power" calculations.
  b.  The power includes technology effects and technology effects.  It doesn't include support from other units.
2. Add support from other units to the sorted list and remember which units gave support.
3. Reverse the sort so that the weakest unit is first
4. Loop through all of the units
  a. For each unit, loop through all of the unit types of all the units (including the unit type of the current unit)
    i. For each unit type, take one of the units of that type and add to its "supported power" (this is the power that includes technology, territory, and support from other units) the amount of support that it gives to other units.  I'm going to call this new value the "totalCombatValue".
    ii. Compare the totalCombatValue against the weakest known totalCombatValue
    iii.  If the totalCombatValue is lower, then this unit becomes the weakest unit
    iv.  If the totalCombatValue is equal, then it compares the current weakest unit against this unit using the same comparison in the first sort, except it doesn't use the "main power" part.  It only uses the cost, "opposite power", "tie breakers", and movement.
  b. Add the weakest unit found to the casualty list, remove it from the main list, and remove any support it has received from the other units.

So, basically, it checks the "main power", cost, "opposite power", certain "tie breakers", and movement.

But there are problems with the algorithm.

One problem is that if the units have multiple owners (such as on defending). If one of the players has better technology that increases their units power, this might be included or not in the algorithm. This is because when it is looping over the unitTypes (4.a.i), it grabs the unit type of the first unit of that type. So, if the first unit is from the stronger player, then it see the weaker unit and it will not be removed until much later.

Another problem is when there are more supporting units than units that can receive the support. When it is building the "totalCombatValue", it uses the amount of support that the unitType gives. In certain cases, it might see the unit giving the support which inflates the "totalCombatValue" for the units not giving support. In other cases, it does the opposite. An example would be:

2 UnitTypeAs - Attack 2, Gives +2 support to UnitTypeB
1 UnitTypeB - Attack 1

In this situation, you want the order of loss to be:

UnitTypeA
UnitTypeB
UnitTypeA

That is because the first UnitTypeA isn't supporting UnitTypeB so it can be removed while still allowing UnitTypeB to have an attack of 3 because of the other UnitTypeA. The current algorithm incorrectly selects UnitTypeB first because it sees that UnitTypeA is giving +2 support and so it should stay around.

---

Now that I've explained the current algorithms and some issues with it, this is what I'm proposing:

1. Loop through all of the units and create a UnitSet for each UnitType and GamePlayer
2. In each UnitSet
  a. Calculate the base power (using main power and territory effects)
  b. Calculate Greatest Fully Received Support (GFRS)
     i. The greatest amount of support that ALL of the units in the unitsets will receive.  So if B and C support A, and there are 2 A, 1 B, and 3 C, then the support from B is not counted as not all As get the support, but the support from C is counted.
  c. Calculate the Greatest Fully Given Support (GFGS)
     i. The greatest amount of support that ALL of the units in the unitsets will give.  So if A supports B and C, and there are 2 A, 1 B, and 3 C, then the support given to B will be counted since all Bs are supported but the support given to C is not counted.
3. For each unit
  a. Sort the UnitSets by the sum of base power, GFRS, and GFGS (as well as possible other tie breakers that the old algorithm use)
  b. Grab the unit from the lowest UnitSet
  c. Recalculate GFRS and GFGS

With that algorithm, I'm able to handle the following example correctly:

UnitTypeA - Attack 1, supports UnitTypeB + 1
UnitTypeB - Attack 1, supports UnitTypeA + 1
UnitTypeC - Attack 2, supports UnitTypeA + 1
UnitTypeD - Attack 1, supports UnitTypeC + 1

2 UnitTypeA, 2 UnitTypeB, 2 UnitTypeC, 2UnitTypeD

Initial attack power: 18
Remove UnitTypeD - attack power is now 16
Remove UnitTypeD - attack power is now 14
Remove UnitTypeB - attack power is now 11
Remove UnitTypeA - attack power is now 9
Remove UnitTypeC - attack power is now 7
Remove UnitTypeB - attack power is now 4
Remove UnitTypeA - attack power is now 2
Remove UnitTypeC - attack power is now 0

The existing algorithm comes up with:

Remove UnitTypeD - attack power is now 16
Remove UnitTypeD - attack power is now 14
Remove UnitTypeB - attack power is now 11
Remove UnitTypeB - attack power is now 8
Remove UnitTypeA - attack power is now 6
Remove UnitTypeA - attack power is now 4
Remove UnitTypeC - attack power is now 2
Remove UnitTypeC - attack power is now 0

You'll notice that the middle part, the new algorithm gives better total attack power than the existing algorithm.

I've opened a PR with my current work in progress: #8170. I still have to implement support stacking and there's a lot of performance improvements that I have in mind. But it is mostly working and I've built tests to ensure that items are ordering correctly.

I'm wondering if people see any issues with this algorithm and if you do, can you describe the units, their stats, and what support they are giving/receiving. I can put those in as tests and figure out how to fit it in.

[DanVanAtta]

@trevan could you compare contrast your proposal with the previous proposal we had for a rewrite?

In essence the previous was:

• for each unit type, remove one of that unit type, calculate total power (including support)
• choose the unit type that results in the greatest remaining power
• for tie breakers, define a way to do tie breaking (either defensive power, PU, etc.)

In theory we should already have a 'total power' function, we need that to know in LL situations what total power we are working with.

What I also like about the above is that there is no need to sort units and it can be extended to a 'n' case where you can determine how many units can be removed from a given unit type until supports changed. For example, the algorithm could say, "remove the next 3 infantry", and that would remove 3 iterations of the OOL.

[DanVanAtta]

@trevan are you accounting for negative support from enemy units, does that change anything?

[DanVanAtta]

What happens when units support multiple unit types? For example, artillery supports both marines and infantry, does that mess up the GFRS calculation? There are a number of scenarios here as well where the supporting unit has greater, or lower attack power and that can determine whether they are a better or worse choice if summing up, per unit, support given.

The item I like about computing the total attack power of a group is that it's quite a bit simpler. You can create a module to compute the total power, test that, then given that module, you can use that module to do the OOL simulations. Furthermore, there is no complexity in adding/subtracing supports, you just apply supports and that goes into the total computation. You also don't have any issues with choosing whether strongest or weakest units get support, or cases where you have to worry about units providing multiple other units with supports and how that computes calculations. For example, improved artillery, it can be a headache if you are summing that up and then it matters if there is an odd or even number of units that can be supported. It's also a headache when you have multiple supporting units (say for example there were to exist an 'artillery' and 'heavy artillery'. A naive calculation could double count, for example an artillery, one infantry, and a heavy artillery, one one of the artilleries is providing support.)

[trevan]

@DanVanAtta , the "calculate total power and choose the unit that results in the greatest remaining power" is when I realized that the other algorithm had a minor flaw. Take my example I gave above:

UnitTypeA - Attack 1, supports UnitTypeB + 1
UnitTypeB - Attack 1, supports UnitTypeA + 1
UnitTypeC - Attack 2, supports UnitTypeA + 1
UnitTypeD - Attack 1, supports UnitTypeC + 1

2 UnitTypeA, 2 UnitTypeB, 2 UnitTypeC, 2UnitTypeD

Initial attack power: 18
Step 1. Remove UnitTypeD - attack power is now 16
Step 2. Remove UnitTypeD - attack power is now 14
Step 3. Remove UnitTypeB - attack power is now 11
Step 4. Remove UnitTypeA - attack power is now 9
Step 5. Remove UnitTypeC - attack power is now 7
Step 6. Remove UnitTypeB - attack power is now 4
Step 7. Remove UnitTypeA - attack power is now 2
Step 8. Remove UnitTypeC - attack power is now 0

At step 3, removing UnitTypeB or UnitTypeC ends up with an attack power of 11. But if you remove UnitTypeC, the next removal will give you a power of 8. So you want to remove UnitTypeB and then UnitTypeA to get a power of 9.

It was while looking at this situation that I came up with the CGFS and CGRS. The reason why it is better to remove UnitTypeB is that it is receiving support from UnitTypeA and when you remove UnitTypeB, now you have a UnitTypeA that isn't giving any support. So the CGFS of UnitTypeB is higher than UnitTypeC which breaks their tie.

I also noticed that the CGFS and CGRS calculations were similar to the other algorithm's "getWeakestUnit". In there, it appeared to figure out the greatest least amount of buffs that could be given to the unit which is what the CGRS calculates as well.

What I also like about the above is that there is no need to sort units and it can be extended to a 'n' case where you can determine how many units can be removed from a given unit type until supports changed. For example, the algorithm could say, "remove the next 3 infantry", and that would remove 3 iterations of the OOL.

This algorithm can do the same optimization. I haven't done that yet as I'm wanting to make sure everything works correctly but it is possible.

are you accounting for negative support from enemy units, does that change anything?

It should be able to account for negative support from allies or enemies. I'll be working on tests to check that out.

What happens when units support multiple unit types? For example, artillery supports both marines and infantry, does that mess up the GFRS calculation? There are a number of scenarios here as well where the supporting unit has greater, or lower attack power and that can determine whether they are a better or worse choice if summing up, per unit, support given.

It should handle that as well. I've done several tests by hand to check different situations. If you have a specific case in mind, please let me know.

[DanVanAtta]

Is there a typo in your example?

UnitTypeA - Attack 1, supports UnitTypeB + 1
UnitTypeB - Attack 1, supports UnitTypeA + 1
UnitTypeC - Attack 2, supports UnitTypeA + 1
UnitTypeD - Attack 1, supports UnitTypeC + 1

Should that be (?):

UnitTypeC - Attack2, support unitTypeD +1

[trevan]

No, UnitTypeC supports UnitTypeA with a +1. Both UnitTypeB and UnitTypeC support UnitTypeA with a +1. Nothing supports UnitTypeD.

[DanVanAtta]

Units can only receive one support for power, and only one support for rolls.

*edit only one 'friendly' support for power, and one friendly support for rolls.

[DanVanAtta]

To be sure, the algorithm described to choose the best remaining power is a 3rd option that only appeared in the closed PR branch of some time ago. That's a really simple algorithm as well which is of a lot of benefit, particularly when the dice-roll and battle logic are overly complex. I would be surprised if that ever found a sub-optimal choice since by definition you are choosing the optimal choice per round.

[DanVanAtta]

Say for example if you had:

• infantry attacking at 1
• light artillery attacking at 2 and giving infantry a + 2
• heavy artillery attacking at 3 and giving infantry a +2

If there were on one of each unit type the initial power would be 8 and choosing the light artillery leaves a remainder power of 6, the best you can do.

[trevan]

Units can only receive one support for power, and only one support for rolls.

*edit only one 'friendly' support for power, and one friendly support for rolls.

If the "bonus type" of the supports are different, then they stack. See https://github.com/triplea-game/triplea/blob/master/game-core/src/test/java/games/strategy/triplea/delegate/power/calculator/AvailableSupportsTest.java#L379. Also, Pact of Steel 2 says "the name of the bonus, any string. Any bonus with the same name will not stack unless a count of how many can stack is specified, any bonus with a different name will stack."

[trevan]

To be sure, the algorithm described to choose the best remaining power is a 3rd option that only appeared in the closed PR branch of some time ago. That's a really simple algorithm as well which is of a lot of benefit, particularly when the dice-roll and battle logic are overly complex. I would be surprised if that ever found a sub-optimal choice since by definition you are choosing the optimal choice per round.

I gave an example where it can find a sub-optimal choice. Maybe this is because you weren't aware that support rules can stack.

[DanVanAtta]

The algo I described did not state how to break a tie, though you also get a tie in that case as well (therefore I don't see how it is sub-optimal), the algo does the same:

• remove unit D
• remove unit D
• tie between unit B & unit C

This gist has the math behind that: https://gist.github.com/DanVanAtta/46b0517b6e772e6bfff8ddf5bbdb7574

[DanVanAtta]

I'm curious if there is something i'm not seeing. It seems like the 'choose best remaining' algorithm would become similar when it goes to break a tie as you have to consider support received and given to choose best tie breaker.

The aspect i like the most about "choose best remaining" is that the code to compute the total power is something we need to have (and do have somewhere), we can modularize that and test it really well. Then we can re-use that for the biggest parts of the OOL algorithm. Then the tie break becomes it's own algorithm, which again can be readily tested. This pairs I think something that is simple and modular (which gives us the best chance of getting it right).

[DanVanAtta]

Last, I like the 'choose best' because it is more generic. It takes into account tech, territory effects, amphib bonus - everything that we must account for to compute a correct total power. Having a different way to compute OOL needs to have all of these components built into them, which means we'll fundamentally have that logic duplicated when we compute the total power of LL, and again when we are computing OOL.

[DanVanAtta]

@trevan Are you sure that the proposed algorithm would work with multiple supports per unit as well (for example, improved artillery?)

I'll toot the horn of the 'choose best' algorithm one more time as it's guaranteed to give you the best result for the next round (that is how you choose, you are simulating removing one unit and then computing the best power, if you are removing one unit, therefore you must be choosing the unit that results in the best remaining power).

[trevan]

The algo I described did not state how to break a tie, though you also get a tie in that case as well (therefore I don't see how it is sub-optimal), the algo does the same:

* remove unit D

* remove unit D

* tie between unit B & unit C

This gist has the math behind that: https://gist.github.com/DanVanAtta/46b0517b6e772e6bfff8ddf5bbdb7574

There is at tie between unit B & unit C. But if you take unit B, you'll then get a suboptimal result on the next round. Taking unit A, B, or C after you take unit B gives you a total power of 8. But if you take unit C and then take unit A, you get a total power of 9. So even though unit B & unit C has a tie, you need to take unit C to get the better result.

[trevan]

Last, I like the 'choose best' because it is more generic. It takes into account tech, territory effects, amphib bonus - everything that we must account for to compute a correct total power. Having a different way to compute OOL needs to have all of these components built into them, which means we'll fundamentally have that logic duplicated when we compute the total power of LL, and again when we are computing OOL.

OOL uses the same code that is used to calculate total power for LL. I don't see why it needs to be duplicated.

[trevan]

@trevan Are you sure that the proposed algorithm would work with multiple supports per unit as well (for example, improved artillery?)

I'll toot the horn of the 'choose best' algorithm one more time as it's guaranteed to give you the best result for the next round (that is how you choose, you are simulating removing one unit and then computing the best power, if you are removing one unit, therefore you must be choosing the unit that results in the best remaining power).

Yes, I've just done a test for improved artillery. I've also done tests for stacking from multiple rules. I haven't yet done stacking in a single bonus type but I don't expect that to be much different.

[DanVanAtta]

The choose best algorithm has given a tie between B & C. At that point you need another algorithm, a tie-break algorithm, but that was not specified. The result is not sub-optimal. The fact one of the units within the tie was the best choice shows the result of the choose-best is good.

[trevan]

The choose best algorithm has given a tie between B & C. At that point you need another algorithm, a tie-break algorithm, but that was not specified. The result is not sub-optimal. The fact one of the units within the tie shows the result of the choose-best is good.

Per your gist:

## Step 3
Remove UnitTypeB: 11

2x UnitTypeA => (2*1) + 3 = 5
1x UnitTypeB => (1*1) + 1 = 2
2x UnitTypeC => (2*2) + 0 = 4

Remove UnitTypeC: 11

2x UnitTypeA => (2*1) + 3 = 5
2x UnitTypeB => (2*1) + 2 = 4
1x UnitTypeC => (1*2) + 0 = 2

If we continue:

## After Removing UnitTypeB in Step 3
### Step 4
Remove UnitTypeA: 9
1x UnitTypeA => (1*1) + 2 = 3
1x UnitTypeB => (1*1) + 1 = 2
2x UnitTypeC => (2*2) + 0 = 4

Remove UnitTypeB: 8
2x UnitTypeA => (2*1) + 2 = 4
0x UnitTypeB => 0 = 0
2x UnitTypeC => (2*2) + 0 = 4

Remove UnitTypeC: 8
2x UnitTypeA => (2*1) + 2 = 4
1x UnitTypeB => (1*1) + 1 = 2
1x UnitTypeC => (1*2) + 0 = 2

## After Removing UnitTypeC in Step 3
### Step 4
Remove UnitTypeA: 8
1x UnitTypeA => (1*1) + 2 = 3
2x UnitTypeB => (2*1) + 1 = 3
1x UnitTypeC => (1*2) + 0 = 2

Remove UnitTypeB: 8
2x UnitTypeA => (2*1) + 2 = 4
1x UnitTypeB => (1*1) + 1 = 2
1x UnitTypeC => (1*2) + 0 = 2

Remove UnitTypeC: 8
2x UnitTypeA => (2*1) + 2 = 4
2x UnitTypeB => (2*1) + 2 = 4
0x UnitTypeC => 0 = 0

So, the optimal choice is to choose UnitTypeB. Because then you can choose UnitTypeA and get a power of 9. If you choose UnitTypeC, then you can't get a power of 9. The best you can get is 8.

This algorithm does basically the same thing as "choose best" but it also includes the information needed to make this type of optimal choice as well.

[DanVanAtta]

TBH, I thought the algo you are proposing has been our current and then the offset values were only for deciding a tie. A clean version of that will be better, I suspect the original algorithm is a result of 'throwing code at it' until it was maybe right (and then performance optimized). I believe I saw an example where the OOL code is invoked twice per battle round, once without the cache, again without. I mention this to emphasize how the complexity of what was written has lead to some really bad tangles, and it was performance optimized to further tighten the knots.

I like choose best as it's simple and sub-divides the needed algorithms that are both readily tested. You can test tie-break on its own, and you can test overall choice on its own, you don't have to test it all in one-go. I like your proposal as a tie-break algorithm.

Though, I think what you are implying is that what I would use for tie-break criteria, can be computed over the original units to give enough information to choose the best casualty in the first place.

As far as test cases, we have to handle it all - but I would focus on same-type supports personally as that is far more common (I'm not aware of any maps that have different type supports, but they could be out there. There are a couple of maps that do have enemy negative supports).

Enemy negative supports need a careful look as those could apply to multiple units, and sometimes applies to rolls and/or to power as well. I think that is where a simple "compute the total power given these units" keeps it simple.

I think I would like to see your algorithm written out in a similar way I did in the gist to give the summed values for the second and third step.

[DanVanAtta]

Sorry to pile on, the cases for OOL are subtle but become complex.

Drilling into same type support, one also needs to consider multiple units that support multiple other units. Napoleonic is an example. There are different kinds of artillery, and they all support different kinds of infantry. The infantry can only be supported by one artillery at a time (and so the support bonus amount needs to be applied correctly). I think the detail then comes into how do you determine that a unit is actually giving support? That is where the majority of the complexity comes in.

For performance and otherwise to approach the algorithm, changing the data structure to be unit type with unit count I do think is the way to go. That then immediately makes the algorithms O(m) where m = number of unit types vs O(n) where n = number of units.

[DanVanAtta]

@trevan , just saw your response: https://github.com/triplea-game/triplea/issues/8171#issuecomment-727511382

Choose best does not continue when it sees a tie. It instead invokes a completely different tie break function to determine which to choose. EG: Unit tieBreak(Collection<Unit> tiedUnits). The result of step 3 is the result of that function. I'm implying that function would look at supports, and unit costs to determine the tie break, and presumably it would choose unitC.

[DanVanAtta]

In short, what I'm not sure about:

• if CGFS CGRS is used to do a tie break for 'choose best', is it just as well to compute 'CGFS and CGRS' in the first place?
• is it easier to understand choose best and then have a modular tie-break algorithm that does CGFS and CGRS? Or is it just simpler to have CGFS and CGRS and then an even simpler tie-break algorithm?
• Does CGFS and CGRS lend itself well to bulk computation? I think it probably would. What I mean here is if we are looking at the unit group, or the unit-type & unit-count combination to do the computations. This ultimately should give us the right asymptotic complexity characteristics of a good algorithm before we then start doing any further optimizations. Specifically, having an algorithm be O(number of unit types) is much better than O(number of units). Granted, for small battles, the number of units and the number of unit types are often the same, but for larger battles we'll have exponentially more units than types.

[trevan]

GFRS is basically the same thing as "choose best". It calculates, for a set of units, the The greatest amount of support that ALL of the units in the unitsets will receive. So if B and C support A, and there are 2 A, 1 B, and 3 C, then the support from B is not counted as not all As get the support, but the support from C is counted. Add this to the power of one of the units (which should all be the same since they have the same player and unit type), and you get the total power that "choose best" uses. Then, the GFGS also tells you if the unit is giving support to others so it is kind of the tie break.

Both GFGS and GFRS are calculated at the unitset level. They also don't need to change every time a unit is removed. The current code calculates them for all unitsets each time but that's just a quick and dirty solution.

[DanVanAtta]

How to proceed?

I'd recommend:

• enhance the test cases and try to get as comprehensive as possible. You may find more bugs in the existing algorithm by doing this. Really the crux is if you have enough test cases, and we can say "if these test cases pass, then the algorithm is correct", then you'll have a lot of freedom.
• if you can have an algorithm that approaches the existing performance to within about 25%, that will be acceptable.
• try to unify as much code as you can, and be as modular as is reasonable. I would like to see there be a modular way to compute unit powers and ideally that be shared to compute LL power, ec - and done in just one way.

When I did this exercise, without caching I found the updated algorithm was much faster than the existing code. Though, the existing code, in the cache cases, was on average (which really says something when a no-cache algorithm is almost as good as something that uses a very large cache). When looking at it in more detail, I found the biggest performance hit was to constantly copy units into unit groups on every battle round. If the battle data structure was able to keep track of the unit groups, then it seemed like the no-cache updated algorithm would have been straight up faster in all cases (and then there was more opportunity beyond that to make it even faster).

[trevan]

Adding more test cases and handling the different situations is what I'm doing. One of the reasons for submitting this issue was to see if there are other known sets of units that might cause problems. I've been working through the sets of units that were mentioned in the other issue and others that I've found.

The power computation is already been modularized. It is in the CombatValue code that I previously worked on. I plan on just reusing those components here so that the same code is shared.

[DanVanAtta]

GFRS should change when a unit is removed, right? If you remove a unit giving support, then the amount of support being received changes.

At the unitset level, I do like that if you have 3 infantry, 5 artillery, then you know you can remove 2 artillery before any of the support changes and therefore can then skip the next OOL iteration. At each iteration level the data structure returned should probably be a tuple, the unit type that can be removed and how many of them can be removed before you need to start running OOL again.

I was thinking another optimization would be to only compute 'n' iterations as well. For example, 50 units losing 5 units, you only need to get the best 5, we do not need to compute all 50 to then compute the first 5.

[DanVanAtta]

@trevan , in short, I'm going to leave the final code and algorithm up to you. The test cases were added largely as part of this exercise in trying to re-write OOL and include most of the curve-balls we could think of.

You need to be sure you account for:

• tech (for example, british jet fighters defending with american fighters)
• support, both friendly and enemy (additive and non, single unit & multiple, strength support bonus & roll bonuses)
• amphib and any other territory or battle bonus, territory effects in particular

Finally, for now, the performance is significant and we cannot tolerate much of a regression as the AI runs the OOL code repeatedly. The really slow pull on AI battle calc's is doing a full copy of the game data, if we can fix that then the AI should be incredibly fast. If we were to fix that, then there would be more flexibility in OOL for performance. Until then we are tied into a bit of a knot and need OOL to be fast.

[DanVanAtta]

A mention about test cases @trevan , I'm pretty sure they are lacking a few things:

• enemy support tests
• tie break tests. For example, choosing a Destroyer (defense of 2, movement 2) over a patrol boat (defense of 2, movement 1). Even if the PT boat had a movement of 1, the special ability is worth more than a unit that has no special ability. I don't think we need to try and be perfect right now about how to weight the special abilities.

I think this then brings in an AI tie-in. The AI code should somewhere have its own OOL algorithm. It's kinda nasty how they are intertwined. It's an option even to copy/paste all of the existing OOL code and use that only in AI, and do something simple and not-cached for non-AI battles.

Anyways, my point is it could become an AI implementation of exactly how to deal with ties, we probably could drive ourselves nuts trying to do things like (favor keeping subs until there is exactly 1 destroyer left, etc..).

[trevan]

I think I would like to see your algorithm written out in a similar way I did in the gist to give the summed values for the second and third step.

Here's a gist based on your gist showing this algorithm: https://gist.github.com/trevan/6300b24962eb35e26e93885e707b995b

[trevan]

A mention about test cases @trevan , I'm pretty sure they are lacking a few things:

* enemy support tests

* tie break tests. For example, choosing a Destroyer (defense of 2, movement 2) over a patrol boat (defense of 2, movement 1). Even if the PT boat had a movement of 1, the special ability is worth more than a unit that has no special ability. I don't think we need to try and be perfect right now about how to weight the special abilities.

I'm planning on keeping the existing tie breaks: cost, opposite power, sub/destroyer, transporting, air/carrier/transport. I'll use the same values that the existing algorithm uses for those tie breaks.

[trevan]

GFRS should change when a unit is removed, right? If you remove a unit giving support, then the amount of support being received changes.

It could. It depends on if the unitset has more support available to give. If you have 5 artillery and 2 infantry, then removing 1 artillery won't change the GFRS since you only need 2 artillery to get the full support. So, as an optimization, I could keep track of how much "overage" each unit set has and then as units are removed, decrease the overage.

[DanVanAtta]

It can get complicated, for example:

• 5 infantry, 2 light artillery, 2 heavy artillery
• 2 infantry, 3 light artillery, 3 heavy artillery

I'd recommend to ensure the tie break can stay modular. I think it's been a mistake historically in the code for the way AI to calculate it to have been coupled with the generic algorithm. Personally I'd be happy using something really simple and very predictable, after-all OOL is used to present options to humans and I think something easier to predict is better than something that is overly optimized. I've argued that it gets into a strategy decision when to keep a sub vs a destroyer, which is something the AI must decide, but for a generic OOL it's questionable for us to be making that decision for players.

Calculating support is very complicated. That is the reason why the support 'calculator' was extracted to its own class so it could then be isolated and iterated on independently. I think a big key to getting all of the code to be reasonable will be to create good APIs and abstractions. A 'unitGroup' for example and being able to determine support given sets of unit groups, etc..

[trevan]

Can you define what is an "infantry", "light artillery", and "heavy artillery"? What are their attacks, defense, supports? I'm trying to not use terms like that because they mean different things depending on the game/map/person.

[DanVanAtta]

@trevan it does not matter too much, the point is more that both artilleries support the infantry. Napoleonic is a good example of such a map where there are multiple artilleries, support multiple infantry types, and the supports do not stack.

In the example, infantry probably attacks at 1 or 2, light artillery at 1, and heavy artillery at 2, and both artillery give a +1 to the infantry. Varying the attack power of the infantry creates different results and it all needs to be accounted for and work.

For example, infantry attacking at 2, light at 1, heavy at 2, would give these powers:

infantry 2+1 => 3
light 1 => 1
heavy 2 = > 2

The OOL in that case is light, infantry, heavy (just assuming the heavy artillery costs more PU)

OTOH, if you had infantry at 1, and you had something like this:

3x infantry, 1 light artillery, 3x heavy artillery

Then the OOL would be 1 light artillery, then infantry then heavy artillery.

If you had infantry attacking at a 2, and heavy artillery at a 2, then it's likely the OOL would interleave removing infantry then heavy.

The point really is that for units that give support, you need to account for the case where there are no units to receive that support, and sometimes there is overlapping options where there units to receive the support but they are already receiving support and hence no support is given.

[trevan]

Let me try and reword the calculations.

The "GFRS" is basically the "strongest weakest" unit in the unit set. So in an example of 2 infantry (+1 attack) and 1 artillery (+1 attack, +1 support to infantry), the GFRS of the infantry is only 1 (+1 from the base attack). That is because the 1 artillery can't support both the infantry. So one of the infantry will not have any support. If the artillery was improved, then the gfrs would be 2 (+1 from the base attack, +1 from the support). If there were four artillery, the gfrs would still be 2 since the support doesn't stack from a single support rule.

So when it sorts the two unit sets (infantry and artillery), the infantry unit set will be the lowest as it only has a GFRS of 1 while the artillery would have a GFRS of 1 as well as a GFGS of 1 (since it is actively supporting one of the infantry). The first infantry would be removed, it would then recognize that the GFRS of the infantry goes up to 2 (since now all of the infantry are supported by the artillery), and the resort would put the artillery at the bottom since its GFRS is still 1.

[tvleavitt]

As a side note, I'd suggest that the "Twelve Clans" map would be a great sanity check for how generic the algorithm is, as it includes a bunch of different units with special powers and supporting effects, including "leaders". As I recall from my play through, the current algorithm did an o.k. but not perfect job of accounting for the varying capabilities.

On Sun, Nov 15, 2020 at 11:32 AM trevan notifications@github.com wrote:

Let me try and reword the calculations.

The "GFRS" is basically the "strongest weakest" unit in the unit set. So in an example of 2 infantry (+1 attack) and 1 artillery (+1 attack, +1 support to infantry), the GFRS of the infantry is only 1 (+1 from the base attack). That is because the 1 artillery can't support both the infantry. So one of the infantry will not have any support. If the artillery was improved, then the gfrs would be 2 (+1 from the base attack, +1 from the support). If there were four artillery, the gfrs would still be 2 since the support doesn't stack from a single support rule.

So when it sorts the two unit sets (infantry and artillery), the infantry unit set will be the lowest as it only has a GFRS of 1 while the artillery would have a GFRS of 1 as well as a GFGS of 1 (since it is actively supporting one of the infantry). The first infantry would be removed, it would then recognize that the GFRS of the infantry goes up to 2 (since now all of the infantry are supported by the artillery), and the resort would put the artillery at the bottom since its GFRS is still 1.

— 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/8171#issuecomment-727623815, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABB5HANDV5NOHCQRWYRS4XLSQAUGVANCNFSM4TV3FSCQ .

-- Thomas Leavitt Internet enabled since 1990

[DanVanAtta]

I'll emphasize one more time, I think we could be losing sight of requirements and should not make all of the strategy decisions for players. If we try to be perfect, we're doing something the AI should be doing. Humans want something that is more predictable, telling them exactly the optimal OOL order is arguably too much computer aid and is dictating strategy.

It would be reasonable to use something very simple and predictable for the OOL suggestion to humans, and to have something more involved for the AI OOL. We should consider this option as well. I think this more speaks to how tie-breaks are decided. When working on OOL re-write previously, my intent was to have tie-breaking be a strategy object and allow for different AI injections. For example one AI might favor to always keep airplanes over land units, or it might favor to keep subs when no offensive destroyer were present. Regardless, we should try to strive for the OOL algorithm and/or the tie-breaking algorithm to be strategy injections and not tightly coupled to the battle logic. It's certainly a question of how many iterations it would take to get there, there's a lot of work to do to untangle the knots in this code.

[trevan]

I'm making it possible to pass in a custom Comparable. This is where custom tie-breaking logic would be done.

[DanVanAtta]

A Comparable I see two issues:

1. We need to be sure it is transitive. It might be difficult to know that it is. We do have error reports of AI doing sorts and we see errors due to the comparable not maintaining transitive property. A complex sort like this could very well not be transitive.
2. It could get very ackward, a two hit bship would be at the front of the list, but then a single hit bship is at the end of the list. Implementations could be much easier if they can early terminate when they find the next best unit rather than having to compare every unit possible (ie: a comparable has to be able to compare every unit in a given collection, whereas an API like UnitGroup breakTie(Collection<UnitGroup>) only needs to find the one best unit to break the tie.)

[DanVanAtta]

To expound, the transitive property could be very difficult for something like destroyers or anything else that gets a conditional weight. Support units are another example since some units will get lower priority when they are providing support vs when they are not.

[trevan]

I don't see how the UnitGroup breakTie<Collection<UnitGroup>) is any better. It still has to be transitive and it has to go through the entire list. Otherwise, you'll not be able to move units around as you want (such as a two-hit battleship in front of another unit) because the two-hit battleship might not be passed into the breakTie.

[DanVanAtta]

I'm thinking:

• first pass goes through and computes scores of each unit group. Things like two hit bships are given their own unit group, supporting units, supported units, and non-supporting and non-supported also get their own groups.
• given a set of scores we choose the set of unit groups with the max score (or min score, whichever as appropriate)
• if there is one unit group with a max score, that is selected
• if there are multiple with a tied score, then we run the tie-break function and return the unit from the tie break function

The tie-break function would take in the collection of all unit groups that are in the tie and return the one unit group that is to be selected. In the above, there is no sorting and no need for a Comparator function. Therefore the tie-break does not need to be transitive.

[DanVanAtta]

The AI will want to know the full set of all units, in the general case we perhaps don't need to care. This is where I feel really conflicted and feel like the general case should be predictable and simple and it is really the AI that needs to be concerned with making an optimal choice.

Regardless, the API needed will probably need to be more like:

UnitGroup breakTie(Collection<UnitGroup> tiedUnits, Collection<UnitGroup> allAlliedUnits, Collection<UnitGroup> enemyUnits)

The enemyUnits might be better replaced with a datastructure that has the enemy supports in it instead to keep it simpler.

[trevan]

But, say you wanted a two-hit battleship to be taken before a destroyer. The unit group construction and scoring of each unit group would have to be customizable so that you can then ensure that the two-hit battleship is either lower than the destroyer or tied to the destroyer. And all of that customization, plus the tie breaking code, is basically a comparable broken up into pieces.

[DanVanAtta]

If unit groups are constructed such that they are distinct per:

• number of hit points
• supported (Per support type, whether enemy or friendly)
• unsupported
• providing support
• not providing support

Then the API UnitGroup breakTie(Collection<UnitGroup>) should work, right?

The fact we've gotten really hard to debug error messages about sort not being transitive in AI code has me really concerned that we'll get it wrong in a subtle and hard to fix way. If that is basically a comparator, then how does a comparator help us if it has more likely problems? I'm also unsure if the comparator API is really what we want, that is a unary operator depending on one unit group vs another. What we have is a set operation that needs to account for all units in a tie and only needs to choose one (once we've found a clear choice, we don't need to keep looking at other unit groups. This is a rules-based prioritization problem IMO, not a sorting problem)

[DanVanAtta]

In short: " And all of that customization, plus the tie breaking code, is basically a comparable broken up into pieces." That is what makes me concerned a comparator for tie-break won't always be transitive and would then cause errors.

[trevan]

If unit groups are constructed such that they are distinct per:

* number of hit points

* supported (Per support type, whether enemy or friendly)

* unsupported

* providing support

* not providing support

Then the API UnitGroup breakTie(Collection<UnitGroup>) should work, right?

The fact we've gotten really hard to debug error messages about sort not being transitive in AI code has me really concerned that we'll get it wrong in a subtle and hard to fix way. If that is basically a comparator, then how does a comparator help us if it has more likely problems? I'm also unsure if the comparator API is really what we want, that is a unary operator depending on one unit group vs another. What we have is a set operation that needs to account for all units in a tie and only needs to choose one (once we've found a clear choice, we don't need to keep looking at other unit groups. This is a rules-based prioritization problem IMO, not a sorting problem)

I don't think the tie is the problem that this api needs to work on. Because a two-hit battleship will probably never tie a destroyer. So, if the AI wants a two-hit battleship to be taken before a destroyer, it has to somehow make the battleship tie a destroyer or be valued less than a destroyer. So, if you take a set of UnitGroups, you'll want to find the "lowest" unitgroup using some sort of comparison. And that comparison will need to make a two-hit battleship lower than a destroyer. Even if you don't use a Comparator api, you'll still be writing a comparator.

[trevan]

I think maybe I'm not having a problem with using the Comparator is because I'm only using it to find the lowest UnitGroup. Once it finds the lowest UnitGroup, it takes off 1 to N units and then resorts the list again to get the lowest item. So, I could change that to just a findWeakestUnitGroup(Set<UnitGroup>) and it should have the same functionality.