A better quick "how good am I fighting X"

[Yakk]

I think that this might run fast enough to be used in "get best defender".

Maybe it won't. But at least it should run much faster than the current binomial theorem based "chance to win" calculator.

It generates a fixed point answer to the question "what fraction of your HP would you expect to lose beating the target, and failing that, what fraction of their HP would you expect to chip away" in a quick, approximate way.

Higher values are better.

Someone else is in charge of generating "vs Melee" multipliers on the power of each combatant -- they are expected to be already factored in.

CombatChance and AttackPower must not be greater than MaxQuickCombatPower. (I should add checks...)

Note that MaxQuickCombatPower is 2^15, or about 32000. The limit on those two values is mainly if you want to scale them up for rounding purposes.

AttackPower is "damage you do per hit", scaled if you want. CombatChance is the number that is used to determine if you win a given combat round.

// this should take into account the changes to power
// due to the other side's unit type, and the terrain type
// you are on, etc.  It shouldn't take into account combat
// strength changes due to Health changes:
struct QuickCombatSide {
	int CombatChance; // assumes A/(A+B) chance to hit
	int AttackDamage; // damage done per attack
	int Health; // your current health
	int FirstStrikes; // # of first strikes
	int ChanceFirstStrikes; // # of first strike chances
};

// this first calculates "in a typical case, how much damage
// would an immortal version of myself take to kill the enemy".
// It then rescales that by this unit's Health, and up by 100,
// generating a sort of "what fraction of myself does it take
// to kill this target".


// Keeping the scales small enough that MaxQuickCombatScale squared
// isn't a problem
enum {
	QuickCombatScale = 1<<8, // 256
	MaxQuickCombatPower = 1<<7*QuickCombatScale, // 128
	MaxHealth = 100, // note, it is important that MaxQuickCombatPower >= MaxHealth
};

int DamageRatioScaled( QuickCombatSide you, QuickCombatSide other);

// This returns a fixed point value, where QuickCombatScale is 1.0
// 
int QuickCombatPower(
	QuickCombatSide you,
	QuickCombatSide other
)
{
	if (you.Health <= 0) { return 0; }
	if (other.Health <= 0) { return MaxQuickCombatPower; }
	if (you.Health > MaxHealth) { you.Health = MaxHealth; }
	if (other.Health > MaxHealth) { other.Health = MaxHealth; }

	// Expected damage from first strikes, scaled by QuickCombatScale
	int FirstStrikeDamageScaled = 0;
	{
		int FirstStrikesTimesTwo =
			you.FirstStrikes*2 + you.ChanceFirstStrikes -
			other.FirstStrikes*2 - other.ChanceFirstStrikes;
		if (FirstStrikesTimesTwo > 0) {
			int FirstStrikeHitsScaledPerRound = (you.CombatChance*QuickCombatScale)/(you.CombatChance+other.CombatChance);
			int FirstStrikeDamageScaledPerRound = FirstStrikeHitsPerRound * you.AttackDamage;
			FirstStrikeDamageScaled = (FirstStrikeDamageScaledPerRound * FirstStrikesTimesTwo+1) / 2;
		} else {
			int FirstStrikeHitsScaledPerRound = (other.CombatChance*QuickCombatScale)/(you.CombatChance+other.CombatChance);
			int FirstStrikeDamageScaledPerRound = FirstStrikeHitsPerRound * other.AttackDamage;
			FirstStrikeDamageScaled = (FirstStrikeDamageScaledPerRound * FirstStrikesTimesTwo+1) / 2;
		}
	}
	int otherFirstStrikeDamageScaled = 0;
	int yourFirstStrikeDamageScaled = 0;
	if (FirstStrikeDamageScaled > 0) {
		otherFirstStrikeWoundsScaled = +FirstStrikeDamageScaled;
	} else {
		yourFirstStrikeWoundsScaled = -FirstStrikeDamageScaled;
	}
	// the 100 here is because you.Health is a percentage
	int healthYouLostToFirstStrikesScaled = (you.Health*QuickCombatScale - yourHealthScaled)*100 / you.Health;
	// are you likely to lose in the first strikes?  Sucks to be you.
	if (you.Health*QuickCombatScale <= yourFirstStrikeWoundsScaled) return 0;
	// are you likely to win in the first strikes?  Rocks to be you
	if (other.Health*QuickCombatScale <= otherFirstStrikeWoundsScaled) return MaxQuickCombatPower;

	// Next, work out the damage ratio.  This is the ratio between the average damage
	// and the average damage they do to you, per round.
	// 1.0 means "every point you do, they do a point, you are even"
	// > 1.0 means you are ahead.
	int damageRatioScaled = DamageRatioScaled(you, other);

	if (damageRatioScaled <= 0) {
		// you aren't expected to do any damage.  This isn't good.
		// however, you might have done some damage in the earlier part.
		int fracHealthTheyLostToFirstStrikesScaled = otherFirstStrikeWoundsScaled / other.Health;
		// the 100 above here is because other.Health is a percentage
		if (fracHealthTheyLostToFirstStrikesScaled <= 0) {
			return 0;
		} else {
			return fracHealthTheyLostToFirstStrikesScaled;
		}
	}
	int expectedDamageTakenScaledPostFirstStrike = (other.Health*QuickCombatScale - otherFirstStrikeWoundsScaled)*QuickCombatScale / damageRatioScaled;

	int expectedDamageTakenToWinScaled = expectedDamageTakenScaledPostFirstStrike + yourFirstStrikeWoundsScaled;

	// if you aren't expected to take any damage...
	if (expectedDamageTakenScaled <= 0) {
		return MaxQuickCombatPower;
	}

	// smaller fractions of yous to win is better!
	int fractionOfYousToWinScaled = expectedDamageTakenToWinScaled*100 / you.Health;
	if (fractionOfYousToWinScaled <= 0) { return MaxQuickCombatPower; }

	// The return value, bigger is more powerful, hence better:
	int retvalScaled = QuickCombatScale * QuickCombatScale / fractionOfYousToWinScaled;
	if (retvalScaled > MaxQuickCombatPower) return MaxQuickCombatPower;
	return retvalScaled;
}

int DamageRatioScaled( QuickCombatSide you, QuickCombatSide other)
{
	// catch blowthrough:
	if (you.AttackDamage > other.Health) you.AttackDamage = other.Health;
	if (other.AttackDamage > you.Health) other.AttackDamage = you.Health;

	if (other.CombatChance <= 0) return MaxQuickCombatPower;
	int HitRatioScaled = you.CombatChance * QuickCombatScale / other.CombatChance;
	if (HitRatioScaled > MaxQuickCombatPower) HitRatioScaled = MaxQuickCombatPower;
	if (other.AttackDamage <= 0) return MaxQuickCombatPower;
	int DamageRatioScaled = you.AttackDamage * QuickCombatScale / other.AttackDamage;
	if (DamageRatioScaled > MaxQuickCombatPower) DamageRatioScaled = MaxQuickCombatPower;

	int retvalScaled = HitRatioScaled * DamageRatioScaled / QuickCombatScale;

	if (retvalScaled > MaxQuickCombatPower) return MaxQuickCombatPower;

	return retvalScaled;
}

This code has not been compiled nor tested, it was just written as-is. Some work was put into making sure that the fixed point values don't break the 2^31-1 barrier of ints.

Math was done in fixed point out of an irrational, and probably unwarranted, fear of doubles. Probably doing it in floating point would be a better idea. Then again, who knows what the civ (graphics) engine has done to the FPU precision!

 

[notque]

Is that going to make it into Better AI, When does it get tested?

When I do it myself?

 

[Yakk]

Was actually having some other thoughts.

Rather than a hack-ass (and the above is hack-ass) attempt at a fast approximation to the combat odds...

Calculating "blows until combat over" isn't hard -- for Withdraw/Retreat/Victory/Loss.

FS/FSC and per-round odds can then be mapped to your victory chance.

Can we build a table that is sufficiently fine grained and small that we can generate approx. victory chance by a mere table lookup?

Ignoring FS for now (which is a big thing to ignore):
PerRoundChance x Blows to Dead/Retreat x Blows to Victory/Withdraw -> Chance
is a map we could cache. At 50 PerRoundChances (all >= .5, we can use symmetry for the other half), 20 different Blow counts (don't have to be contiguous), that's

50*20*20 = a 20 k entry table

FS and FS chances, sadly, cause a blow up. How bad?

Well, with W+?X one one side and Y+?Z on the other, there are X+Z different distributions of number of total first strikes the fight has. We have to look it up in a max X * max Z size table if we want it to be fast and not have to calculate the binomial coefficients.

This could fit in a max X * max Z * max (X+Z) size table.

Set max first strike chances at 10, and that's a 2000 size table, with each entry being a delta-first-strike and a probability -- quite doable.

This reduces it to # of first strikes on each side. Let's say we cap the total first strike edge at 20. First Strike Edge x Hit Chance x Number of Hits -> Probability of that many hits is a table of 20*20*50 = 10,000 entries.

Then we can convolve the chance table with the number of FS hits table in at most 20*20 operations (but that is bounded by the number of actual FS and FS chances the units have, so will actually almost always be very small), to generate a list of at most 20 lookups in the first table mentioned.

The result:
Hits until dead calcuation on both sides
Hit chance calculation on both sides
<= 400 fractional multiplications and 21 table lookups for FS mathematics.
32,000 table entries containing a rational value (or floating point value) in each.
Some work to approximate the blows until dead/hit chance for table lookup (manual pseudo-rounding).
<= 20 table lookups to map FS distribution -> victory chance
Some math to deal with withdraw chance.

That might be fast enough, and gives us an 'approximate combat odds calculator' that is based on the actual in-game mechanics. We can even fill it dynamically (store a flag for 'has been calculated', and then calculate it on-demand), so there is no start up costs.

But this is harder than the first attempt.

 

[PieceOfMind]

I'm not very familiar with how the bestdefender code works exactly, but I have gotten the impression from game experience that it works pretty well except in the presence of first strikes (as demonstrated in the other thread). I reckon if we thought up a better way to include first strikes into the current code it might be a lot more accurate.

But whatever the case, one could argue that this sort of change is effectively a gameplay change rather than an AI change. Is this ok? I'm wondering whether it can be shown with certainty that the bestdefender code was actually meant (intended) to pick the defender with the best odds. At the moment, for example, siege units are treated differently when they are valued and units which have some other asset value (like transports) are weighted differently. From the limited amount of the code I've seen it seems pretty obfuscated and it's going to be pretty hard to change it to something just based on best odds or best approximation to best odds.