Fix to TacAI Decoys
 

I got involved in a chat yesterday about dom2 in the irc room. The subject of decoys came up - someone suggested a post about it, so here it is.

Decoys are an abuse of the tac targetting ai. Setting a screen of 1 unit squads seriously reduces the ability for archers and mages to cause the amount of damage they should, as well as seriously delaying melee units (this effect is much more pronounced in the small scale combat regularly seen in early multiplayer fights/blitz games - where the 3-4 turns of protection from archers and mages can have a profound effect).

My suggestion to a fix for this is pretty simple (but would probably be too large a change for patch -- maybe dom3 though):

All unit types have a minimum unit size. For example, militia have a minimum unit size of 5. If militia are placed in squads smaller than 5, they'll rout automatically. Of course more powerful units should have smaller minimum sizes.

But setting a minimum size would force you to at the very least invest some cost when employing decoys - while at the same time giving ranged weapons a better chance of routing or killing those decoys effectively (a mage casting falling fire on a group of 5 has a much greater chance of hitting a couple of them - and therefore routing them).

Anyway - this might not be the perfect solution - for some things it might not be thematic to enforce minimum sizes (vinemen spring to mind) - but you can make a case that most weaker summons need to be used in groups for mages to properly control them (weak undead for instance).

Maybe some food for thought at least.

Re: Fix to TacAI Decoys
 

I love this idea! (I was the one who insisted halfzware post it).

Re: Fix to TacAI Decoys
 

Agreed, min squad size sounds pretty good. Although dynamic regrouping might be nice too. For example, if two groups of 5 light infantry advance and one group loses a soldier, the understrength squad could merge (on the battlefield) with the other one, and subsequently all 9 soldiers would be a single squad.

If I were a brave, proud, nationalistic soldier and 90% of my squad was annihilated, leaving me alone... I'd probably try to join another squad during the battle, rather than routing or fighting alone.

As I understand it, your solution is to force-rout tiny squads once combat occurs. However... allowing the player to form single-member "squads" of very weak units in the first place is rather silly. No soldier would take their leader seriously if he said "Bob, you stand alone at the front, while everyone else is in a dense wedge formation 200m behind you." The only real problem I see with preventing this on the user-side is that when you have only 4 militias in a province (perhaps they retreated there) you can't get them out easily, since you can't form a squad of 4 weak units. And adding more rules to allow formation of small squads in situation X but not situation Y would cause problems and confusion.

The main problem I see with your proposed version of squad-size control, even if dynamic regrouping were added, is that it might be problematic for tiny armies. For example, what if you buy 3 points of province defense, enough to prevent an enemy scout from singlehandedly stealing a province? Your PD will generally rout... forcing their leader to rout... and giving an automatic loss. Also, as you mentioned, auto-routing cannot solve the problem of mindless AI decoys, since they can't rout. Yet enforcing squad size limits on the user-side brings other problems, as I mentioned.

So... it seems like more thinking needs to be done to address the corner-cases, as there is no obvious, universal answer that is clean and simple. But I think it's a very good approach to eliminating the tactical decoy problem (and adding some realism to battlefield deployment), if those niggling details can be addressed. This forum is full of smart people; I'm sure someone will have an idea. http://forum.shrapnelgames.com/images/smilies/happy.gif

Re: Fix to TacAI Decoys
 

Dynamic squad regrouping I'm not so sure about - as I think the code for this could be tricky. I would like to see some kind of rally system though, for instance if you have guys on their way off the screen but the entire enemy army routs it'd be nice for your guys to stop running off.

I think preventing you from forming the groups in the first place is not a good solution.

Perhaps a simple addition to the ui would be best - like a moral number visible on the unit formation screen. If a squad has below "squad minimum" they will have 0 squad moral. Once it goes to minimum they'll have 10 moral, and so on using some multiplier like ( base moral * ( squad size - minimum squad size ) ) / minimum squad size.

But yeah - basically being able to put together units however you want should be possible - what happens when you're on the field with the fire flying is another thing.

Re: Fix to TacAI Decoys
 

I think you got it all the wrong way. The best fix might be the one that sounds most complicated at first: Fixing the targeting algorithm.

If a squad's target is set to anything else than "Large Monster", squads with only 1 single unit in it should be ignored, unless there is no other target at all.

Mages obviously must be handled a bit different. But they already choose their spells dependent on how much damage they do to the target. So it's simply a matter of giving them better chances to actually do some damage at all: Atm, bolt spells are mostly useless against single targets, as they usually hit the right square only 30% of the time. And then can still fall on an unoccupied slot, or be blocked by a shield. If low-level bolt spells would have way higher accuracy, the IMHO the mages would use them automatically to fry any decoys in range. And as the spells have low path requirements, fatigue gain would be small.

Btw., IMHO this fix has the biggest chances to get implemented: One of the devs said once it's much more fun to fiddle with the AI than to alter the Ui or code new battle mechanics http://forum.shrapnelgames.com/images/smilies/wink.gif

Re: Fix to TacAI Decoys
 

The auto routing of small squads wouldnt fix the problem. Archers would still target the single troops set in front even if they immediately retreat...

Re: Fix to TacAI Decoys
 

Not quite true:

Targeting happens at the very beginning of each combat turn, as well as Re-targeting when the original target routs.

So in the first turn, the archers would target the decoys.
In the second turn, the decoys would be routing and the archers would switch to another, non-routed target, prefering those not in direct (base-to-base) contact with friendly troops.

Re: Fix to TacAI Decoys
 

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.

This again opens itself to potential abuse - even if bolt spells were more accurate a group of two militas could still eat up 2 turns of spell casting in order to rout/kill them.

The routing system isn't perfect - even handling minimum groupings of 5 militia can be abused. The point though is increasing the costs involved when deploying 'gamey' tactics. The hidden value in minimum unit sizes isn't just in its initial cost - 5 milita is only 15 gold in CB. The real value is that constant renewal of your decoy groups is more difficult and more costly (each time you use a decoy, they'll probably die or rout - meaning you have to constantly renew them - in groups of 5 instead of individual soldiers). This is especially important in early game fights where the tactic is most abusive and where every unit counts.

Re: Fix to TacAI Decoys
 

Nah, minimum group size is not the way to go. It might seem good on the face of it, but it breaks down. Think about mixing up unit types - how could you possibly even guess what the min group size for it would be?

Arralen is right that the correct fix is to repair the targetting ai. Archers need to look at how much of thier volley in each turn is "wasted". So like 20 archers firing at 1 militia results in massive waste. But 20 archers firing at 50 militia will mean that probably every single arrow will hit and perhaps kill a unit.

This said tho: whether or not any changes are made to the targetting AI, there will always be loopholes if the algorithm is static.

Re: Fix to TacAI Decoys
 

for each unit in squad
add element unit size to squad moral total
divide squad moral total by number of units

Also known as averaging, if averaging isn't to your liking there are other tools that can be used simply. Standard deviation, etc. Code is very good at handling this kind of thing - and methods for aggregating numbers are many and well known.

I agree that having a targetting AI that behaves as a human controlling it would want it to behave is the best answer. But as you say, the most likely scenario is that people will find methods to abuse the targetting logic here also. There will always be loopholes, which is why its better to prevent worst case abuse at the onset. Minimum unit size is a simple - I dare say elegant way to achieve this.

Re: Fix to TacAI Decoys
 

Another problem with this is bodyguards.

Re: Fix to TacAI Decoys
 

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).

Re: Fix to TacAI Decoys
 

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.

Re: Fix to TacAI Decoys
 

Great idea there:
Fire at big groups

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

Re: Fix to TacAI Decoys
 

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.

Re: Fix to TacAI Decoys
 

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

Re: Fix to TacAI Decoys
 

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.

Re: Fix to TacAI Decoys
 

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 http://forum.shrapnelgames.com/images/smilies/happy.gif

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.

Re: Fix to TacAI Decoys
 

Thanks SC.

Re: Fix to TacAI Decoys
 

"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.

Re: Fix to TacAI Decoys
 

You're welcome! It came out longer than I expected http://forum.shrapnelgames.com/images/smilies/happy.gif

I hope not... SC is better, because it (...not very often...) misleads people into thinking I'm some sort of 'super combattant' http://forum.shrapnelgames.com/images/smilies/happy.gif

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 http://forum.shrapnelgames.com/images/smilies/happy.gif

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.