AI -- the Thread

[Mark_Everson]

Thanks for the update, Laurent. It sounds like you're making good progress. I think going to two simulations per combat should work ok for now. Eventually we can come up with a better way to do the sims. They don't have to be as accurate as real combat, and so there might be opportunties to make the sim combat much more efficient that we're not exploiting now.

Cya,

Mark

[LDiCesare]

I'd rather have simulations and real combat use the same model. It'll make less code if anything.
I found another thing which causes slowdowns: Some plans looks for the nearest unit, and these scan all the task forces every time. This means if the ai has 12 TFs and you have 10, it will compute distances between its own TFs 12*11 times, and between his and yours 12*10 times, for a total of 12 * 21 computations. Considering it doesn't see all of the player's units, it shouldn't do all the computations. Considering some units are in the same squares, it shouldn't compute paths to the same square several times. And it shouldn't compute path A-B once and then repeat with B-A. I'm not sure exactly how I'll fix that, but it looks like I can get rid of the quadratic, or at least most of it, if I can handle things correctly. This should hopefully speed the ai enough for me to work on something else.

[LDiCesare]

Mark said in a mail:
but an estimate of the troop loss cost to Take
the city should be included. (Not just troop losses in the first round.)
This should make Rome a very bad bargain for Hannibal. If the AI can't capture that, it will do a lot of boneheaded things that we should strive to avoid. I know you can't do everything at once, these are just comments for a future implementation.

I will have to multiply the cost of the troops loss according to the proportion of defenders that remain.

One problem with the ai is the pathfinding: It is generally OK, but it computes distances without acknowledging troops on the way. So if there are enemy troops on the way, the ai still considers teh path valid. This means that the ai picks targets based on time to reach the square, but will always be blocked by enemy troops on the way.

[LDiCesare]

I now allowed units to attack the next nearest square. This does allow Hannibal to attack southern Italy, but, as I mentionned, the pathfinding algorithm lacks provision for avoiding combat: Typically, the nearest square when you are north of Rome is Rome, and the next nearest is south of Rome (which requires you to cross Rome) because there is a road leading to it from Rome. The result is the ai will invade southern Italy, but do so only if it is able to "win" a fight in Rome (actually 1 tick, not necessarily 1 turn). I could provide a nearest neighbour square to avoid that? Otherwise, the whole pathfinding algorithm must take armies into consideration, which it should probably, but only armies the current TF is not able to beat, and even then, the fights would delay the army a bit... So in order for Hannibal to conquer Italy, you should help him and build a few roads around Rome.

[Mark_Everson]

Originally posted by LDiCesare
I now allowed units to attack the next nearest square.

Oh, I had no idea that the algorithm had such a small "sight" range, or maybe I'm misunderstanding what you are saying. Does it really only look at adjacent targets? There is currently no sense of "heading towards Rome" when the AI starts up?

This does allow Hannibal to attack southern Italy, but, as I mentionned, the pathfinding algorithm lacks provision for avoiding combat: Typically, the nearest square when you are north of Rome is Rome, and the next nearest is south of Rome (which requires you to cross Rome) because there is a road leading to it from Rome. The result is the ai will invade southern Italy, but do so only if it is able to "win" a fight in Rome (actually 1 tick, not necessarily 1 turn).

I hadn't forseen that problem. Probably the easiest long-term thing to do is to allow for pathfinding that has the cost increase for each square with enemies in it. However that may be difficult to do depending on the level of encapsulation of the pathfinding code. As I see it the best thing to do is to give the pathfinding algorithm a pointer to the moving TF (I think it has one already) and use that to set the scale for the seriousness of any opposition. In addition we may need to pass a parameter that indicates the tradeoff of speed vs opposition to the algorithm. Emphasising speed would reduce opposition costs.

In the present case, Rome would then show as a Very high-cost move, and the A* would look to move around Rome as the best path. What I suggest could be quite simple to implement, or a bit difficult, depending upon the exact nature of the pathfinding code.

I could provide a nearest neighbour square to avoid that? Otherwise, the whole pathfinding algorithm must take armies into consideration, which it should probably, but only armies the current TF is not able to beat, and even then, the fights would delay the army a bit... So in order for Hannibal to conquer Italy, you should help him and build a few roads around Rome.

I favor doing it right over a kludge of the NN (nearest neighbor) sort. But if doing it right will take a very long time, perhaps a quick fix is in order.

[LDiCesare]

Does it really only look at adjacent targets? There is currently no sense of "heading towards Rome" when the AI starts up?

No.
Here's the algorithm:
Look at nearest known enemy (may be 10 squares away). Simulate if it's worth fighting them.
I added the next nearest enemy too.
If you look at the militaryattitude file, you can see the various things the ai considers. When looking for opponents, it looks for the two nearest ones, near in terms of pathfinding (including roads, not looking at neighbour squares). It does the same for cities. Capital is more straightforward.

What I suggest could be quite simple to implement, or a bit difficult, depending upon the exact nature of the pathfinding code.

Yes, I'll look into this. Since pathfinding may be used with different functions (path for roads, path for different units who don't share the same movement costs across different terrain), I hope it won't be too hard.

[Mark_Everson]

Thanks for the description of the algorithm, Laurent. Now it's a lot more clear to me why the new AI does what it does. I think in the fullness of time we can come up with good ways to increase the scope of what it's doing. But that is probably properly the function of the higher-level AIs that you don't have fleshed out yet.

I have one suggestion for the current AI that might be worthwhile. Sometimes a big TF wastes time moving around taking single low-value squares. Presumably that is because these turn out to be more valuable than taking distant cites or attacking distant armies. But if the big TF were to move toward those more sizeable objectives it would take roughly similar low-value squares anyway. Is there a way to emphasize high-value targets if a TF is 'big'? The operational definintion of big might be tied to TF Power / Total Military Power for the AI civ.

This may be too complicated to do right now, but I thought I would throw the idea out while I was thinking about it.

[LDiCesare]

Mark, your suggestion falls under higher level strategy IMHO. Sometimes you want all resources you may need so spending some time on nearby squares will be important, sometimes not, because fights should always be reisky (they aren't enough now). Anyway, I'd just change the militaryattitude of TFs past a certain power. I don't think I'm ready for that now.

I coded the pathfinding so the units will avoid big strong enemies. This works more or less correctly. My problems are that I find the pathfinding to be slow as it was, and now it needs even more data and computation. I used a very rough heuristics to augment the square tick cost when enemies are there (based on attack strength, *2 if walled - not a simulation, so inaccurate but much faster to compute too). I think that the new pathfinding is much slower than the previous, too (didn't play enough to make measures or anything, though).

I also wonder how much time is spent mapping units to squares. Currently, squares don't know what taskforces are there, but TFs know which square they are in. There is a data structure that does the inverse mapping, but I feel it is a bit complex. I reduced some of the overhead (and concurrent modification exceptions) therein, but I am unsure that having TFs out of squares gives us anything. Gary might tell me why it was done that way. I know he thinks performance shouldn't compromise design, but I miss the design rationale here.

[Richard Bruns]

Does militaryattitude.xml still do anything? I know it used to be the a list of things the AI would do at random, and the odds for each, but now the AI seems to be far beyind that.

[LDiCesare]

militaryattitude.xml is still used, but its role changed a bit.
Before, you had several 'plans' (take square, take capital...), each had a weight, and the chance of choosing that plan was a simle proportion of weight ofr that plan divided by sum of weights.
Now, the weight is a factor by which we multiply the economic value of the square in order to get a number of points in case the plan succeeds.
If the plan is not a total success (f.e. you win the fight but there are defenders left, or you take the square but suffer lots of casualties), the amount is reduced (certain constants are in the xml file too, under AIConstants, some may still be hardcoded).
Each plan has a target square, which is chosen (nearest, second nearest enemy square, nearest seen enemy unit, nearest city, enemy capital, plus others which are anecdotic). Once all squares are determined, the maximum value of each plan is computed (militaryattitude value of the plan times economic value of the square). A computation is run. If the result is higher than the current maximum, it is kept 90% of the times (I don't remember the exact figure, nor if this is in the xml files). This allows for some unpredictability. Each plan is simulated in order until we reach plans whose value is too low to beat the current best plan (typically all plans witha weight of 0).
There are also tweaks, like grouping taskforces together when there are more than a given number in a square. This is needed both because it prevents the ai to move around too many single units and because it helps performance quite a bit. (btw the pathfinding is not slower now I made the tests, but the overall program is still too slow to my taste). The last tweak is that a command that meets an (unexpected) army will cancel its orders and ask for new ones.
And then there is reinforcement stuff: If a TF realizes it can win a battle if it gets reinforcements, it will ask for some. This can result in building siege weapons for instance (it works in the Reinforcement test scenario, but I can't seem to get Carthage build the *** catapults for some reason). Note that, because of the way I coded the stuff (multiplications), all units would be better off having a non zero value in both attack and defense. When a reinforcement is expected, the task force no longer considers plans which require reinforcements, and the reinforcing units move towards their target in order to merge with them. The position is not recomputed every turn or tick, so it may produce werid results if the first taskforce starts moving a lot. I think I added a multiplier to the wait order for the case units are waiting for reinforcements, so they move a bit less than others.

So the militaryattitude file remains very important.
In the future, I should code something even more complex with a breakdown of different attitudes (typically one defensive and one offensive) for each ai, with units sent to either of these in order to get a specified proportion of each attitude.

[LDiCesare]

Mark, thinking a bit more about your point:

I could have plans compute their value over N turns or including the path: If I take path XXX to reach square xy, then I conquer all the XXX squares and thus the plan has a higher value:
Value of a plan = (value of target square) + (value of conquered squares in the path). But then I must divide that by the time taken to reach the objective.

[Mark_Everson]

Hi Laurent:

What you said is basically what I was thinking of. Nothing too complicated. It seems it would be beneficial to do this if it isn't too much additional work. It's your call as to whether it is worthwhile to do now.

Does the algorithm now account for time taken to achieve the objective? It probably should if it doesn't.

[LDiCesare]

The algorithm doesn't take time into account for the moment. I'm currently struggling with the pathfinding to allow the units to avoid other units not only when planning an attack but also when doing the actual moves. It means I need 2 costs for movements: Actual cost and cost + heuristics to avoid enemies. The actual cost is used to actually move, while the other cost is used to plan the moves. Both notions are blurred in a single class right now.
I am afraid of computing the time needed to get to the target square. Normally, I have the path stored somewhere when I found the square, but I'm not yet done with those path objects.
Additionnally, I've been sick (unable to talk) for more than a week, which gets on my nerves and doesn't help my coding.

[Mark_Everson]

Hi Laurent, thanks for the response. Sorry to hear about your illness. I just had to reload the OS on my comp, so I am still digging out from it. That, combined with a small flood in the basement and numerous other irritations have me feeling like I must have a virtual "kick me" sign affixed to my back!

Good luck getting better!

-Mark

[LDiCesare]

Taking time needed into account causes weird behaviours. In particular, since units tend to get created near one another, they can merge quickly, so they spend a lot of time moving to where a new unit has been created. This results in slowing the ai a lot.
Also, the result of the division by time needed results in the ai going around squares that are not important when it could instead head to the capital. The value of the capital could be increased vastly to take this into account, though, so I think it may all be tuned by changing figures in the xml file.

There is one thing however that bothers me: I did't have to compute a path to reach the capital of an enemy, but if I want to take time into account, I will have to, and pathfinding is slow, particularly over long distances. Any idea on improving pathfinding would be welcome. My problem is that time needed to reach a place is highly variable (depends on units present in the taskforce, their movement valu may depend on techs, there may be roads in between...) so I can't see how I could avoid recomputing everytime. And I'd rather put nothing than a (false) heuristic.