Fix to TacAI Decoys

[Wick]

Another problem with this is bodyguards.

[PrinzMegaherz]

halfzware said:

This is more problematic than it seems. The obvious for instance would be single pretenders, or other SCs. But even smaller for instances would be other strong single units. A blessed hydra for instance. If you don't like that example, how about a blessed jotun, a black hunter, or even a knight. These single units do need to be targetted and differentiation would require tagging all the units appropriate for individual targetting - this would be essentially the same work as setting minimum unit sizes only the result would be less desirable.

Those examples you gave (most pretenders, Jotuns, Hydras, even knights) are considered to be "large monster", as long as there is nothing bigger around (and usually, the pretender, hydra is the biggest thing in your army - even the knight is larger than his footman cousins).

[Emelio Lizardo]

It would be wrong to place limits on unit size to cure one problem. The cost of the cure doesn't equal the benefit, if any. It also doesn't really cure the problem, as a squad can be reduced to a size of one low value critter by battle and still draw ALL of the enemy fire and melee units.

Basically what we are calling an 'exploit' here is a situation that is not believeable to us because we appreciate relative target values, as opposed to 'units' that simply do as their limited programming instructs. There is no 'awareness' of the general situation or even local circumstances.

There will always be some limitation to AI algorithms that can be exploited, but as long as it is universal (ie both sides can use it) it is simply a feature of battle. Admittedly not a believable feature, but then there are a LOT of features of this battle simulation that are less than acceptable. Target selection, unit orders and the algorithm for hitting the target square need dire improvements.

As example, a enemy commander insisted on running into my squad of 60 archers to commit honorable suicide. As he plunged into the group, did they oblige him? No, every archer who offered a knife for him to fall on was shot on spot by his fellows. I swear one archer shot himself rather than stab the commander. Finally, they ran out of arrows and had no choice but dirty their daggers on the poor fellow. In another variation of this theme, ineveitbably, as the enemy routs, my calvary hord takes its most casualties as it chases down the last remaining kobold and is slaughtered by my own archers who also happen to be targeting that same vary kobold. Basically, there are lots of times when archers or spell chuckers should refrain from tossing a load, or at least NOT targeting the front line, especially when the front line is, let's say, in the middle of a friendly formation.

Units that geefully follow hydras (and other icky-pods) just to suck fumes from their tailpipes, leap into magma pools, ignore high value targets to go beating on kobolds, queue up ten deep to wait their turn to fight in stead of swarming around or retargeting. The volume of problems is impressive. Well, that is if you compare the Dom II simulator to any comparable simulator as of 15 years ago. But if viewed as a source of comedy, it has great potential.

One problem is that area of effect for dropping a spell and throwing an arrow appear to be the same. Arrows have vector, so the should tend to drop short or long rather than randomly from a point. And this needs to be tightened up more, as the safest place on the battle field is usually the targeted square. It should be MUCH more probable that an arrow arrive at the target square than anywhere else. In compensation, I would allow units with shields to use their full defense value against the attack.

As for targeting lone kobolds by an entire squad, or even the entire army, this also represents a flaw in the limitation of orders. I should have an option to order my units to target large formations. It would then be a long time then before a single kobold becomes interesting to shoot at. A conditional order to allow fragmented targeting would also be useful.

Sadly, I also feel the need for an order that my ranged weapon units NOT target my own troops.

[Endoperez]

Great idea there:
Fire at big groups

alternatively,
Fire, aim carefully (do not fire if x% chance of hitting own unit)

[halfzware]

Basically what we are calling an 'exploit' here is a situation that is not believeable to us because we appreciate relative target values, as opposed to 'units' that simply do as their limited programming instructs. There is no 'awareness' of the general situation or even local circumstances.

Incorrect. We're calling it an exploit because in smaller scale games clever use of decoys results in benifit that so far outweigh their cost as to be considered exploitative.

Changing the AI to avoid targetting small groups would fix the problem, but I think its more likely that having the tac ai not target certain groups would just open the game up to other (potentially greater) abuse:

Get a n4+ blessing on any small sacred troop type you want. Sure they have 4 protection, but if you use them in squads of one unit - no mages or archers will target them. Then just put 10 squads of two guys there - they'll never rout (berserk), they'll never be targetted by mages or archers. Perfect units.

This is just one example of how to abuse this kind of tac ai logic, there are many - it'll just take some time and prodding to find them. Making harsh exceptions like "the ai should completely ignore individual units" is just asking for more exploits.

Frankly I don't understand the resistance to minimum group size - my guess is most people are just uncomfortable w/ the idea of any change in the mechanics of the game. Even if it would be a very clean fix.

[shovah]

just do what endo said and have extra targetting orders, not perfect but it helps

[curtadams]

One way to fix the targeting issue is to have units target based on a hypothetical "dry run" of the effects of their attack. The basic idea is that if the squad had decent commanders the commanders would know about what damage could be expected from an attack and would plan the squad's attack appropriately. The "dry run" simulates the commander's knowledge.

You plan the attacks for a multiunit stack one at a time. Figure out who unit #1 will target and then execute his attack in the hypothetical run. Then figure unit #2's attack based on the situation after unit #1's dry run attack, so if the target is dead, #2 shoots at a different target. Continue through all the units and you have a list of attack orders for each unit in the squad. THEN have the units execute those orders in the "real" battle.

You could optimize by averaging multiple "dry runs" or changing the level of damage that justifies switching to a new target (morale break, serious injury, or death are all reasonable candidates). The programming is not particularly difficult. Although the computer demands are fairly high (at least doubling the time for each battle) in Dom's batched turn-processing mode that's not a serious concern.

[Saber Cherry]

curtadams said:
You could optimize by averaging multiple "dry runs" or changing the level of damage that justifies switching to a new target (morale break, serious injury, or death are all reasonable candidates). The programming is not particularly difficult. Although the computer demands are fairly high (at least doubling the time for each battle) in Dom�s batched turn-processing mode that's not a serious concern.

No, no, no... the computational demands are O(n/(log(n))) (relative to a deterministic method) no matter how many runs you choose... and therefore identical

Seriously, though, I've considered this before, and wholly endorse it. I'd love to have turn generation take 10x as long if my generals would be 10% less stupid. But, it is not done at present...

[Note: if you are unfamiliar with "Big O" notation, please skip to the VERY bottom.]


...from where did I pull O(n^2/(log(n)))? Keep in mind when reading this that constants are ignored in Big O math, so curtadams's claim of "at least double time" is quite correct in the real world. That said, if n is the number of squads per side (or total; it does not affect the Big O math, as there are 2 (a constant number of) sides per battle):

Deterministic (current) method:
1) Make a list of enemy squads: O(n)
2) Copy this list and give it to a friendly squad: O(n)
3) Assign each enemy squad a priority based on a function of size, relevance to the friendly squad's orders (e.g. "Fire Large Monsters"), etc: O(n)
4) Calculate distance to each enemy squad on the list, and divide its priority by its distance: O(n)
5) Sort (descending) resultant list: O(n(log(n)))
6) Target element 0: O(1)
7) Fire: O(x) [once per member, but members per squad is limited, so assumed constant, or O(1)]
8) Repeat for each ranged squad: multiply by n [in practice it will be less than n]
Result: (O(n)+O(n)+O(n)+O(n)+O(n(log(n))+O(1)+O(1))*n=n*n* log(n)

Dry-Run-Simulation (Monte-Carlo) method:
1) Make a list of enemy squads: O(n)
2) Copy this list and give it to a friendly squad: O(n)
3) Sort (ascending) by distance: O(n(log(n))) [note: 3 and 4 do not change the big O complexity, but drastically reduce real-world complexity]
4) Eliminate out-of-range targets: O(log(n)), using binary search
5) Assign each enemy squad a priority based on a function of size, relevance to the friendly squad's orders (e.g. "Fire Large Monsters"), distance, etc: O(n)
6) Sort (descending) by priority: O(n(log(n))) [again, this does not alter theoretical complexity]
7) run Monte Carlo simulation ('dry run'): O(r*x*n), where x is squad size, which is limited by game mechanics to around 25-50, and thus can be abstracted as a constant. "r" is the number of runs, so the ultimate complexity is O(r*n*n) .
7a) calculate value of each simulation: O(x), where x is the number of firing troops. Each squad, of course, has a finite number of units due to commander leadership limits, as mentioned before... so this becomes O(1).
7b) sort (ascending) by cumulative simulated value: O(n(log(n)))
7c) cull worst targets, so they are not included in the next simulation: O(n) [the way I would do it; though O(log(n)) is also possible]
8) Target element 0: O(1)
9) Fire: O(1) [see 7a for reason]
10) Repeat for each ranged squad: multiply by n [in practice it will be less than n]
Result: (O(n)+O(n)+O(n(log(n))+O(log(n))+O(n)+O(n(log(n))+ O(r*n)*O(1)+O(n(log(n))+O(1)+O(1))*n=r*n*n*log(n)

However, it is important to note that (depending on the heuristic employed in steps 7.x) the computational complexity can be reduced

So, (r*n*n*log(n))/(n*n*log(n))=r. But assuming r (the number of simulations) is finite and bounded, it becomes a constant, yielding a differential of O(1). In other words... on an infinite battlefield in Dominions II, with an arbitrarily large number of squads, the relative complexity of simulation versus deterministic, rule-based target-choosing asymptotically converges on 1. In other words, the amount of time it takes to calculate the result of a huge battle (with n squads) is (if calculated as efficiently as possible, and if I did not make any mistakes) directly proportional to (n^2)*(log(n)). Were the suggested dry run (Monte Carlo) simulation to be added, the amount of time would be directly proportional to r*(n^2)*(log(n)), the number of simulations. If 'r' was a constant, then the asymptotic complexity would remain unchanged when moving to the more accurate Monte Carlo simulation method... so every battle would take 'r' times longer to compute, and quadrupling the number of units in a battle would generally increase the calculation time by a factor of 32 in either system. Therefore, the quality of tactical battle AI can vastly increased [by roughly a factor of log(r), where "r" is the time multiplier; which I will not prove this here, but is known a property of statistical simulations] without changing the relationship between speed and battle size.

Please note that these calculations are for RANGED UNITS ONLY, not melee, which cannot be 'squadded' since they do their targeting individually (to some extent).






*** Big O Notation Briefing ***

Also known as "Asymptotic Complexity". Consider the function y=a+b*x+c*x^2+d*x^3. At x=0, the only relevant factor is 'a', since everything else is zero. Now consider the situation where a=-4096, b=1024, b=-128, c=1. At x=0, y=-4096; it is dominated by term 1 (-4096) since the other terms are all zero. But at x=32, it is dominated by term 2 (-128*32^2) since (term 1 = -4096), (term 2 = 32768) < (term 3 = -131072) > (term 4 = 32768). And when x>128, term 3 has a greater magnitude than other two terms, so it dominates. In any case, no matter how large the multiplier is on other terms, only one will dominate when x (the relevant input) reaches sufficient size, and it is always the one with the highest exponent (in a polynomial expression).

Big O notation uses this fact to ignore all factors that will become irrelevant at very large values of "x" or "n" (the normal term for the input-size variable). Since the worst case is most important to the developer (e.g., it is better to have 10 battles of 10 seconds each than 9 battles of .01 seconds each and one battle that takes 5 hours), Big O notation is utterly critical to software design, even though it discards information that seems relevant.

[Zen]

Thanks SC.

[Emelio Lizardo]

"Incorrect. We're calling it an exploit because in smaller scale games clever use of decoys results in benefit that so far outweigh their cost as to be considered exploitative."

Hummm, I'll somewhat disagree. It's like saying that it is an exploit of war that is so easy to shoot someone instead of fighting them by hand. A ten dollar archer can kill a infinately more valuable mage any day. A fully buffed knight swarmmed by a few no cost kobolds dies. Some cheap tinfoil chaff on some even cheaper Korean balistic missile can decoy the expensively stupid American ABDS any day. A seriously perverse exploit which I'm sure they will be happy to use. Exploit/abuse or tactic, it seems very subjective.

There will ALWAYS be something that can be "abused". As long as everyone can abuse it, I don't see it as being a big ethical problem. As opposed to, say, someone who hacked the game. But when it isn't believable this detracts from the game experience, and/or generates humor.

I think we can agree that the AI needs a serious retune as it often fails to make use of the possibilities available to it. It would be more fun play against a smarter AI, when the is one.

It's not that the AI should avoid small units, it just needs more than ALL or NOTHING programming. Closer squads of any size can begin to have a higher targeting value than more distant squads, but it shouldn't be absolute.

Be nice to have the option to direct fire based on TARGET VALUE, using priorities that i can set, including a deliniated tolerance for friendly fire.

Saber Cherry, you're going to get a reputation as the big "O". Nice informative explanation. ooh, felt a neuron grow a new psudopod.

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 scarry features (higher priority), someone else is targeting it (lower priority or delete), etc. What orher squads are doing should be considered to affect targeting so that there is some semblenc of coordination in execution as presumably there was in planning.

How would you fragment squad targeting when the enemy is "skirmished", so that the WHOLE squad/army doesn't unload on our kobold while ignoring other dangers? While something big, scarry and close should draw a lot more fire, as should some brightly colored hand waver in the back row (ie, consider multiple factors on critter priority targeting).

As you may observe, I'm rather unhappy with the algorithm for where the projectile ordinance (mundane & magical effect) drops (usually on friendlies.) Any thoughts about projectile endpoint?

One special case I'd like to see, banish should be divinely directed and hit only occupied squares. If there aren't enough occupied squares it can hit some multiple times. Priests are pretty wimpy to begin with and the sheer volume of the undead hordes justifies this. Talk about exploits, the undead have the biggest one built right into the game.