Fix to TacAI Decoys

[Saber Cherry]

Zen said:
Thanks SC.

You're welcome! It came out longer than I expected

Emelio Lizardo said:
Saber Cherry, you're going to get a reputation as the big "O".

I hope not... SC is better, because it (...not very often...) misleads people into thinking I'm some sort of 'super combattant'

Maybe add to your algorithm a case for "too close to own troops" or "in melee" that drops the target from the list or significantly lowers priority, observable scary features (higher priority), someone else is targeting it (lower priority or delete), etc. What order squads are doing should be considered to affect targeting so that there is some semblance of coordination in execution as presumably there was in planning.

For the Monte Carlo simulation, I rolled that into the 'evaluate' phase (7a). But thanks for pointing that out... the deterministic algorithm I specified does not include calculations for avoiding friendlies. My understanding is that Dominions II does this (to an unsatisfactory extent) while Dominions I did not.

So... in a deterministic method, avoiding friendlies would require something like this (where '3' refers to determinsitic phase 3):

3a: Sort enemy squads by proximity: O(n) (*n, including all friendly ranged squads)
3b: Determine predominant unit type. For example, should a group of 15 archers and 10 Xbows be treated as armor-piercing or not? Well... who knows. Anyway, simply calculating the most common unit type is O(x)=O(1) since squad size is limited. (*n, including all friendly ranged squads)
3c: For enemy all enemy squads, generate a value by multiplying number of units, relevance (Flier, Cavalry, etc), proximity, expected damage (of the predominant unit) versus attack type (of the predominant unit) (flaming arrows, armor piercing, damage versus protection, shield defense, etc): O(n)... or possibly O(n(log(n)) if Dominions II actually sorts each squad by unit-type quantity, which I doubt. (*n, including all friendly ranged squads)
3d: ... This is where it gets tough. I can't really think of a 'perfect' way to determine which friendly squads might be hit by friendly fire without iterating over every friendly squad, once for every friendly ranged squad, once per enemy squad... which is O(n^3). However, it is possible to approximate this by creating a list of friendly squads (sorted by proximity, protection, and cost) once per enemy squad, so that every firer can determine which friendly squad might be impacted without resorting all friendlies every time. This is heuristic, though. To do it perfectly requires O(n*n*n) time as far as I can tell, since every attacking squad might have a different projectile type (magical, cold, physical, banefire, flaming+poison, etc), which requires resorting all friendly squads every time any friendly firer targets any enemy squad. You also have to consider the friendly squad size and firer precision (i.e., spread) which firther customizes the targetting choices (meaning they have to be calculated anew for each firing squad, for good results). Tiling (dividing the battlefield into tiles, so that targetting a squad on tile[3][7] only considers other squads also on [3][7] or adjacent tiles) can reduce the problem to some extent... but only in practice, not in Big O notation, since 10000+ 1-unit squads might converge on the same set of 9 adjacent tiles, depending on how many units can fit on a tile.

So, in general, simulation may indeed be asymptotically less complex than any good deterministic (a.k.a. rule-based) system, since (good) rule-based systems must consider everything that might happen, while simulation only considers what does happen (a proper subset). But the constant multiplier for simulation will generally be way higher than that for rule-based systems, so in practice, deterministic algorithms are much better for small systems (like rolling dice) while simulation is much better for large systems (like fluid mechanics). Dominions is somewhere in the middle

In conclusion: It seems that I was wrong, and if a simple, deterministic AI considers all possible friendly-fire effects on a non-tiled battlefield (these traits describe my understanding of the Doms II tac AI), then the resultant algorithm will be O(n*n*n) compared to O(r*n*n*log(n)) for simulation... so the complexity of a deterministic system is acutally worse than simulation! However, bear in mind that a deterministic system COULD be statistically exact in O(n*n*n) time (though neither Illwinter nor anyone else in the world could actually create such an algorithm) while the quality of a simulation increases with log(r) [r = the number of runs] and never reaches unity.