AI -- the Thread

[LDiCesare]

(Edited because of mistake in my previous post about econ values)

The 1000 factor was wrong. I was too tired when I worked that out . I had forgotten a multiplier somewhere and I corrected the code that lets ai see other civs, now it works fine in Jericho. Jericho is way more fun now, though exploration is still lacking.
I'd still like to have a richness value of a square independant of population for strategic purposes, but that's not as urgent.

On a different topic, I checked the way CtP2 does exploration. They tag one square every 5 rows and 5 columns and make these the target squares. I could probably use something similar for exploration, though handling earth/sea transitions is a problem. I'd also probably pick 4 instead of 5 because units in clash see only at 1 square distance while explorers in CtP2 tend to see 2 squares.

[Mark_Everson]

Glad you found the problem Laurent. I played Jericho with the revised AI. It's definitely very much improved! However, it made me think of a few things that IMO are really needed.

First, a while ago I asked "How do you determine the value of a defensive plan vs an attacking one?" You answered that weights are given in the scenario file. What I wanted to know is how to you weigh the two in the Base case, before any scenario modifiers.

Here's a brainstorming idea that I think would vastly improve the AI -- adding an "oppotunity cost" term for each evaluation. If a plan results in big gains, but ties up your whole army for 20 turns, it is probably Not something you want to do since home can be easily conquered by someone in the meantime. This also ties back to the base evaluation of attack vs defense.

The importance of the opportunity cost is it would result in small units doing small-unit jobs, like exploration, or conquering single undefended squares, and big units doing defense or attacking big targets only. Right now big armies go exploring in Jericho and leave the homeland wide open sometimes. Division of labor is something big missing in the current AI.

I think it would be very beneficial to asap include modifiers for how long a plan ties up what number of troops. The opportunity cost minus should = factor*(turns to execute plan)*(cost of troops tied up) or alternatively factor2*(maint. cost of troops summed over time expected). Factor might = 5-10%, Factor2 might be 0.5-1.5.

In addition to merging, we also need the option to separate off one unit to do the little jobs. Basically when a big TF is examining opportunities, it should consider separate and then having one unit do something else. If the sum of benefits of the split TF is larger than the benefit of the whole TF, it should subdivide.

Anyway, those are my ideas at the moment. Whatcha' think?

[LDiCesare]

First, a while ago I asked "How do you determine the value of a defensive plan vs an attacking one?" You answered that weights are given in the scenario file. What I wanted to know is how to you weigh the two in the Base case, before any scenario modifiers.

There's no such thing as Base. You define an attitude in the scenario. That attitude defines weights for attack and defense. If the weights are both equal, only the economic value of target square is considered. If all units belong to the same attitude, they are likely to all behave in the same way, except for the smaller task forces which may stay in defense longer because they will be more successful at keeping their ground that anything else.

Here's a brainstorming idea that I think would vastly improve the AI -- adding an "oppotunity cost" term for each evaluation. If a plan results in big gains, but ties up your whole army for 20 turns, it is probably Not something you want to do since home can be easily conquered by someone in the meantime. This also ties back to the base evaluation of attack vs defense.

Since you're not telling how this opportunity cost can be computed, I don't know what I can do out of this. What I proposed in the earlier post is a way to provide for such opportunity costs, for evaluating attack/defense since going far from the capital would decrease the threat value in the capital for instance, but you didn't comment about that proposal.

I think it would be very beneficial to asap include modifiers for how long a plan ties up what number of troops.

The time taken to reach target is already taken into account when computing the value of a plan, except for the capital (it could be, I'd have to do some more pathfinding). Removing the cost of big troops for exploration is a good idea. For conquest it is not unless you know that there are no enemies nearby and you can safely split. This knowledge requires a global evaluation of threat over the map as I outlined in my proposal.

Right now big armies go exploring in Jericho and leave the homeland wide open sometimes. Division of labor is something big missing in the current AI.

I beg to disagree. The jericho ai has been removed from jericho.xml some time ago and been replaced by attack 9 defense 1. This means roughly that 9 task forces out of 10 will be sent to attack the enemy and 1 left to defend. Since there's rarely 10 task forces, this plan defines that the ai should never defend. Division of labor would be better done by changing the scenario and telling attack 2 defense 1 rather than 9-1, for instance.

Splitting TFs is something that should indeed be done. First of all, instead of waiting for a new unit to be built, a high level attitude (e.g. defense) should be able to reclaim some units from the other attitude (attack in this case).

Checking how the TF could be split in order to get opportunity actions is ok, but how do I know that there's an opportunity somewhere?

I would much rather change the ai in order to get more strategy inside. What you propose looks to me to verge more on the tactical side, which I don't think is as important. For instance, I don't want to make many evaluations of opportunity costs when I could have a single measure that can tell me where units are most needed as I suggested in my post. Unless I have such a measure it will be very hard to compute such values.

[Mark_Everson]

Hi Laurent:

This post is meant to catch up with some comments that you have made over the last few days that I didn't really have time to respond to. I'll try to reply to most outstanding issues, although it may be a bit terse. I have also read some of the preceding posts in this thread going quite a ways back, and think my knowledge of how things work now is better because of it.

Originally posted by LDiCesare
Also, I realize that currently the value of a plan is evaluated in cash, but forgets a really important thing: population..

(This may be something I was supposed to ignore, if so, sorry!) don't really understand the need for your proposed solution that you made several posts ago. The value of population should already be included in the economic value of a square. If a square is heavily populated it should have very large value, where as in an unpopulated square only has value due to its potential if colonists are added (omitting strategic value for now).

Please let me know if this is still an issue for you, but I believe that adding population explicitly is going in the wrong direction. I still believe that cash equivalents are the best way to handle the evaluations. It may be that due to strategic factors that we don't have in there yet, the value of a unit may be modified from its base construction cost by some factor depending on whether we have armies that are too small or too large when looked at in a strategic sense.

I sent you the old demo 4 code so that you could look at what I had for evaluating strategic issues like army size, and fraction of the army with which a civilization could afford to attack. It is not really the type of strategic evaluation that I think you had in mind for this point, but it may be useful for this particular issue. I will also try and look that old stuff over soon to see if it really has value in our current context. It certainly should be useful as we move to a higher-level AI that determines whether the postures should be attacking or defending. We clearly need something better than the current approach for long-terms scenarios where diplomatic status with civilizations changes with time.

Originally posted by LDiCesare
Refining the above:
I could use a military threat value given to all units, and see what that threat value becomes when I move my units. If I move it into the enemy unit, I could destriy it, thereby reducing all its influence to 0, and thus increasing my own strategic value:

I read the whole post starting with the quote above. Influence mapping certainly could be useful here, but it also seems that this becomes very complicated if done over a large portion of the map and considering many possible actions. That said, it probably wouldn't take that long for you to try it in a small way , if you think this is a good direction to go in. As I said above :

Obviously the value of a military unit also depends on where it is. You could put in a modifying factor that takes into account that if in any unit is in our territory without opposing friendly units nearby (within one square?) Then its value gets a bonus of up to 100%. The maximum bonus would come from if it were near high-value economic squares, or a provincial or civ capital.

I had pictured something in terms of averaging enemy and friendly military and economic value over areas to determine this, but your influence approach seems like it could be used also if it included economic value information.

I'd still like to have a richness value of a square independant of population for strategic purposes, but that's not as urgent.

That is tough. We can go through the map AI exercise that I outlined years ago to determine strategic value of chokepoint etc. that might be a candidate for background processing, or even pre-processing while we are sticking with scenarios with pre-determined maps.

Since you're not telling how this opportunity cost can be computed, I don't know what I can do out of this.

??? I thought I told you exactly how it could be computed. It may be that you discounted my suggestion because you are thinking along different lines. Here is what I said:

“I think it would be very beneficial to asap include modifiers for how long a plan ties up what number of troops. The opportunity cost minus should = factor*(turns to execute plan)*(cost of troops tied up) or alternatively factor2*(maint. cost of troops summed over time expected). Factor might = 5-10%, Factor2 might be 0.5-1.5.”

It may be simpler than what you are thinking of , but it seems to me to be an explicit statement of how things can be computed...

What I proposed in the earlier post is a way to provide for such opportunity costs, for evaluating attack/defense since going far from the capital would decrease the threat value in the capital for instance, but you didn't comment about that proposal.

Perhaps your influence diagram proposal can be used for this. I am a bit skeptical, since to capture the entire opportunity cost you would need to redo the influence diagram at several points along a long trajectory, that would doubtless be influenced by unpredictable movements of enemy forces. I believe that the simple opportunity cost approach that I have outlined above would be just as good and a lot simpler. YMMV

The time taken to reach target is already taken into account when computing the value of a plan, except for the capital (it could be, I'd have to do some more pathfinding). Removing the cost of big troops for exploration is a good idea. For conquest it is not unless you know that there are no enemies nearby and you can safely split. This knowledge requires a global evaluation of threat over the map as I outlined in my proposal.

Over short distances I think you are correct. However, I worry about long-distant operations like going for an enemy capital.

Checking how the TF could be split in order to get opportunity actions is ok, but how do I know that there's an opportunity somewhere?

I was just envisioning a test where you say "let's pretend I had a unit here and am looking for something for it to do, what is its best action?" Like I said you would determine the value of action for an n-unit TF, and compare it to the actions for an n-1 unit TF and a single unit. If the splitting action gives noticeably better total value of evaluations , then you should split. Or you could recalculate and see if n-2 and 2 is the best choice.

I would much rather change the ai in order to get more strategy inside. What you propose looks to me to verge more on the tactical side, which I don't think is as important. For instance, I don't want to make many evaluations of opportunity costs when I could have a single measure that can tell me where units are most needed as I suggested in my post. Unless I have such a measure it will be very hard to compute such values.

For the level of thinking you are looking at, it does sound like the influence mapping strategy evaluation could be the way to go. However, I think it has the potential to be very time-consuming and require a lot of tweaking also. If I recall from my days of looking into this, there is a lot of material up on the web about influence mapping and its advantages and disadvantages. If you haven't already, you might want to take a look at some of that first. In any case, if you feel strongly that this is the way to go, you should try it out. It will certainly be fun seeing what can be accomplished in our context within influence map, and even if it doesn't work out for this case, I'm sure the code will be usable for something in the future anyway.

I've tried to answer all the outstanding big issues here. Please let me know what I have missed.

Bon Chance,

Mark

[LDiCesare]

If I understand correctly, your opportunity cost is just an adjustment to existing plans rather than creating a new opportunity plan, which is what I understood at first.

Population tkane into account as far as squares are considered but is not part of the cost of a unit. The unit costs cash plsu population, and that population is not counted as part of the cost of the unit.

We differ on the evaluation of the cost of the different approaches. I think a per tf approach will cost lots of small bits which will end up costing a lot while an influence map will cost once a big chunk. I think the big chunk will be less expensive than many small because it will be reused. We won't know for sure until we have tried.

QUOTE]"let's pretend I had a unit here and am looking for something for it to do, what is its best action?" Like I said you would determine the value of action for an n-unit TF, and compare it to the actions for an n-1 unit TF and a single unit.[/QUOTE]
This means the time taken by the ai would be roughly multiplied by 3. 1 evaluation of n, one for 1, one for n-1. Or at least two if I keep the same plan for n-1 as for n. I'd need to know beforehand whether it's interesting to think of splitting in order to avoid doing too many computations. Do you have ideas for that or is it probably irrelevant?

I'll be checking the D4 code.

[alms66]

While you're doing AI, Laurent, could you whip something up to let the AI colonize squares?

Also, when I tested the tech test scenario after adding the barbarians, the whole time I was thinking it would be really great if the AI would harass the player, rather than try to conquer him. The AI would come in and raid, that is destroy infrastructure and steal population, a square or two, then return home. Rinse and Repeat. To that end, I'm thinking a 'raid' plan could accomplish this. This plan would make the AI not attack to control, but attack to pillage and enslave (steal population). We might want to give the player a 'raid' order button as well.

I'd suggest that when raid is used, it works like the move button, but only allows raiding in adjacent squares. The amount of infrastructure destroyed and population stolen should be relatively small (maybe 10% at most?). The enslaved population should work like settlers, except they are automatically added on the raid command, and can only be dropped into a square you own (not used to colonize new squares). Also, when you "move" into the square to 'raid' (after selecting the raid button and selecting the target square), after hitting end turn, your unit ends up in the same square it was on before the raid (thus the unit has moved in and moved out of the tile after the raid, but on the same turn).

Unfortunately, this would present a whole new slew of problems you may not want to deal with right now, so I'd understand if you didn't want to do this. Also, though I've written a bit here, I haven't really given this much thought, so there could be some big holes. Anyhow, do with it what you will.

[LDiCesare]

alms,
In order to colonize squares, I'd have to do a bit of work to decide whether it's worth doing so. Currently the ai automatically expands but won't settle provinces far away (and won't settle down if it has settlers attached). I think it's a big thing to do, so I'd rather leave it for later. I think I've got a correct exploration code now, but settling is something that requires more strategic thinking than I have got now.
Raiding is a whole new functionality to code, again I'm too busy to start on that now. It could be achieved by moving, stealing pop and moving back, and in that sense a raid order for the ai could work, and later be refined if we include a raid order different from the move one.

Mark,
I checked the D4 code. It's not that much different from what I envisionned: It checks for enemy armies in neighbouring squares (around vital squares or frontline squares only, I haven't had time to check it entirely), which is very much like what I had in mind, except I thought of propagating the power of a tf outwards but dividing (roughly) by time to go there. That is a factor which is then put on top of the econ value of the square.
The evaluation of military strengths depends a lot on knowledge of the opponent. I'd like to provide threat ratios to unexplored squares so that the player gains something (minimizes threats) when exploring.
I checked a bit influence mapping. The only real drawback it has is it needs some resources, but map knowledge needs that.
I'll try to add the distance factor in the attack capital plans and fix the current problems vefore I go further.

[Mark_Everson]

Hi Laurent:

Originally posted by LDiCesare
Population tkane into account as far as squares are considered but is not part of the cost of a unit. The unit costs cash plsu population, and that population is not counted as part of the cost of the unit.

You are right, we should have a cost for population removed. I can make an estimate of that, and have put it on my to-do list.

This means the time taken by the ai would be roughly multiplied by 3. 1 evaluation of n, one for 1, one for n-1. Or at least two if I keep the same plan for n-1 as for n. I'd need to know beforehand whether it's interesting to think of splitting in order to avoid doing too many computations. Do you have ideas for that or is it probably irrelevant?

I would do the "normal" evaluation and pick a target. When the fight is evaluated you will know if there are excess units. (FE if our losses are none or small in the battle if any then there is probably excess power). In that case you probably only need to evaluate the single-unit case since you already know that the other n-1 case is safe. Does that sound like a low-cost compromise?

We differ on the evaluation of the cost of the different approaches. I think a per tf approach will cost lots of small bits which will end up costing a lot while an influence map will cost once a big chunk. I think the big chunk will be less expensive than many small because it will be reused. We won't know for sure until we have tried.

The evaluation of military strengths depends a lot on knowledge of the opponent. I'd like to provide threat ratios to unexplored squares so that the player gains something (minimizes threats) when exploring.
I checked a bit influence mapping. The only real drawback it has is it needs some resources, but map knowledge needs that.
I'll try to add the distance factor in the attack capital plans and fix the current problems vefore I go further.

Sure, sounds like a decent plan, go for it!

Threat evaluation will get a lot more interesting when espionage and other inputs are available to give info on how many troops the enemy has, and some guesses as to where they are within the fog.


Alms:

I'm with Laurent. These things will take time, and probably aren't the most important thing to do now concerning costs and benefits. I do like the raiding idea in the long term, and clearly AI colonization is needed too.

[LDiCesare]

I added a split plan for task forces.
It works as follows (could be made better but I'm too lazy):
When a TF is in a square with not too many separate task forces, if that task force is not awaiting reinforcements in order to do something, then:
I add a split plan. This plan is executed if any order that involves combat (i.e. all plans at the moment) has low casualties (roughly: casualties of opponent must be 2.5 times superior to own casualties - casualties is the proportion of casualties taken). This plan will replace the favored plan (90% of the time since there are times when the best plan is bypassed - I may decrease that to 80% or lower in order to provide less predictability).
When the task force is split, the first unit of the tf is left where the tf was while the other part moves on. Again, this is subject to tweaking.
This solution allows to split task forces and is not too intensive on CPU (though there's an assumption that the split plan is evaluated last).

[Mark_Everson]

Sounds great Laurent.

Your recent improvements have made a big difference in Jericho. I've been Annhilated the last few times I've tried it. I do ok for a while and expand northwards, but after conquering one or two civs big TFs from one of the other guys start showing up around turn 100 at different points of my civ and slowly take it apart! (I'm not using cheats like population grabs that would make it easier, or I'd do much better.)

It looks like both the exploration and attack parts of the AI are working well. I'm sure there are problems at a low level, but at least it can do a decent job with the advantages it had in Jericho.

[alms66]

Laurent,

I'd like to make a suggestion for you. Load up the Tech Test scenario and watch the AI play it (you'll need to add a build order to Ugaria for Light Spearmen at about 25-30 or so). I did this last night, and the AI playing Ugaria did some really odd things.

At one point it only had two units and moved them endlessly back and from between the hill and desert barbarians. Something eventually broke the loop, I suspect it was the arrival of more barbarians.

At the beginning, the AI of Ugaria also never attacked to retake their lands, even though enemies were nowhere near. And by nowhere I mean they had already made it back to their respective cities.

There were lots of other weird choices by the AI. I'm sure you do this with other scenarios, just wanted to point out the particularly odd behavior here.

[LDiCesare]

Adam,

The ai is indeed doing funny things. It's mostly spending its time splitting and mergeing. It tends to merge attackers with defenders etc. so I need something more clever for splitting.
This mergeing and splitting also ensures that all the resources always go to the same plan (in my case stonewall), so the ai doesn't move much or at all. If it's stonewall, it won't ever try to move into enemy territory.
I'll change merge so it doesn't merge with a tf that is of a different attitude, and split so it stops splitting units that don't want to move in the first place (and that would therefore probably merge on the following turn).

[Mark_Everson]

From Commit #139by LDiCesare
Adjusted Merge plan in order to merge only with armies having the same attitude.
Modified MergeOrder so that a tf with a target will merge with that target rather than with everyone.

I'll check it out soon!

Some thoughts (before playing the changes):

The second change seems a bit restrictive. Perhaps you could use an objective value test as you did for the splitting. FE if bigger TF of the two has an attack order and its odds are less than 2.5:1 or are unknown then do the merge, otherwise skip it. Of course for a correct evaluation you need to consider what the single unit could accomplish alone.

[LDiCesare]

The second change is actually the most important and is really needed. I also thought of not splitting if one didn't move but that doesn't seem necessary.
I'm back to work now so updates will be weekly for a while.
The "target" means the tf has decided some time ago to merge and with whom. The way it was done, everyone in the square ended up merged which was not the objective.

[Mark_Everson]

Thanks for the clarification. Sorry to hear about your return to work. I need to go back tomorrow too.

Bon Chance!

-Mark

[LDiCesare]

I am working a bit on the ai to allow it to evaluate correctly the map. I moved the MapView class into a MapAI class (in game.ai) and started putting things into it. The map ai will keep, one for each civ, data about seen squares, explored squares, squares with a city, economic value of the square as it was when last seen. I'll add the military units somehow too.
The main point with this change is that I have to change all the map display so that we draw what the player knows rather than let teh squares draw themselves (in particular things like cities, roads, fortifications...).
I could also put a color on the map so it still shows the ownership of the squares you explored but don't see.
The ai will use this to keep knowledge of who's where. I'll have to also put some information like "Task Force XXX was seen in square YYY at turn ZZZ". This will help getting better ai and map evaluation.

[Mark_Everson]

Sounds great Laurent!

I'll check it out as soon as I get the chance. (Heavy RL schedule this weekend.)

[LDiCesare]

From the Demo 8.1 thread:

AI for naval units including loading and unloading land units (0%)

I think naval units don't decide to load land units, but land units want to reach squares and going by sea is the fastest, safest, or only way to get there.
So if I want to include loading units on ships, I have to consider loading units in the pathfinding. But there is the problem of transport ships being available to carry the units.
I can also make a special plan called "attack coasts" and manage loading/unloading with that plan, but I'm not sure about it.
I can probably use influence mapping to find out where naval units should go giving a bonus to squares near one's own coasts so you know more or less who "controls" which sea square.
It's quite clear to me that, when you control all the harbours, you can use only transport ships, so there is some change of attitude involved when you feel safe about your seas.

All in all, I would welcome ideas about how to manage naval units.

[alms66]

I would think the best method to handle this would be a new plan, so that both the naval units and the ground units involved in the plan would be 'on the same page' when it comes to what needs to be done. If the ground units were to request the presence of naval units, I could see situations where as the naval units got closer to the first request, a second request might pull them away from the first. That could be corrected with simple queuing, but my instinct still tells me that a new plan will handle the situation best.

As for the name of the plan, "amphibious assault"?

[LDiCesare]

If the ground units were to request the presence of naval units, I could see situations where as the naval units got closer to the first request, a second request might pull them away from the first.

Not really. When a taskforce requests reinforcements, the reinforcements don't do anything else and refuse other reinforcement requests until they reached their target. The problem is that said target might move away from the coast in the meantime.
My main problem is how to evaluate it correctly adn find targets for it. Islands are clear targets, but it requires a lot of map knowledge to find out where to attack in the sea, for instance landing near the capital on an island so you have time to disembark.

[alms66]

Originally posted by LDiCesare
Not really. When a taskforce requests reinforcements, the reinforcements don't do anything else and refuse other reinforcement requests until they reached their target. The problem is that said target might move away from the coast in the meantime.

I see, I didn't know further requests were automatically refused. Regarding targets moving, that is precisely one of the reasons why I think the plan approach would work better, because it would be a matter of syncronizing the timing from the plans initial state, vs a TF requesting the naval units at the coast and having to wait for the navy to arrive. Then again, you could always request to meet at x,y on turn z, rather than wait until reaching the coast.

Originally posted by LDiCesare
My main problem is how to evaluate it correctly adn find targets for it. Islands are clear targets, but it requires a lot of map knowledge to find out where to attack in the sea, for instance landing near the capital on an island so you have time to disembark.

Assuming you have enough troops to take it, it would be better to land on the island capital rather than near it.

As for targeting, it seems that any tile owned by the enemy would be a target, with the economic value of the tile raising the priority of the target, capitals raising priority and high military presence lowering the priority. Proximity would, of course, also play a role in raising or lowering priority - not only the proximity of the target tile to land already owned, but also the proximity of an available army to the target tile. But, it seems to me, you probably already know this. As for evaluating, I'm not sure what the problem is there.

[LDiCesare]

Assuming you have enough troops to take it, it would be better to land on the island capital rather than near it.

Not the way the model works now: You must first disembark your troops in order for them to fight. If they are on-board, they don't fight and will get sunk by the defenders.

Evaluation and targeting are the same thing: Evaluation is the way I pick the target and is done pretty much the way you described. The problem is distance: Computing time to reach or simple distance to target takes a lot of time when it's done for every task force, but that's something I should be able to handle.

[alms66]

Originally posted by LDiCesare
Not the way the model works now: You must first disembark your troops in order for them to fight. If they are on-board, they don't fight and will get sunk by the defenders.

I was under the impression that you could move the transports in, then disembark on the same turn, hit 'end turn', and then the combat occurs. If that's not the case then, I was wrong. I haven't played delenda much, so I don't know for sure. I'll assume you've got it right, unless I happen to find out otherwise later.

[alms66]

I went ahead an checked to be sure, and you're correct, you cannot land and fight in the same turn, which is odd, IMO. If you move into a battle like that, it seems that the defender might get a tick or two of attacks against your lowered combat values, but the troops would still be able to unload and fight a land battle (though they would loose a tick or two in the unloading process as stated above). If there are naval units in the tile in question, that's a different story as there would have to be naval combat before the land combat.

That's more of a military matter though...

[Mark_Everson]

Well, I thought a little bit about this, but don't have anything all that intelligent to say. Ideally I think that in the planning that considers thing like taking province capitals naval transport should be explicitly considered. When comparing a plan that involves naval action to a pure land plan the following things would be considered (pretty obvious, but I'm stating them anyway!.):
1. naval power using an influence map as Laurent suggested. There is no point in going very far in the planning if the enemy completely owns the seas.
2. Available naval transport and a guess at the timing and riskiness of same from the influence map.
Once these two factors are considered, then land plans and naval delivery of troops can be considered on roughly the same footing. How this works in detail in terms of reinforcement request queuing and other factors is I think best left to the expert, Laurent.

The results of this type of thing should also feed into the high-level military decisions that the civ makes. For example if all the juicy easy targets are available only after naval transport, and no transport is available, building some should get high priority. At a higher level, if the naval influence is not in the civ favor, then it should consider contesting the other side's naval supremacy.

Getting back to matters of orders and plans... Of course new types of plans for naval units to attempt to control the seas are also relevant here. That could wait a while, but if it's not too difficult to do, having naval units looking for ways to destroy competing fleets would add a new dimension. The AI should be roughly similar to that for land. A patrol/attack order would also be useful to have naval units attempt to protect coasts.

After the discussion on when units get unloaded, I think it would also be useful to have two versions of naval transport orders. One option would be the current one, where when transport is done unloading must occur manually. The other would be a "transport and unload" plan that would automatically unload all units on the destination square.

I know getting this stuff going is a pain, but once it is most of the way there, I think delenda will become a really exciting scenario to play.

[LDiCesare]

One point which is problematic is to choose a good harbour. If f.e. you control the Adriatic but the enemy has a fleet near Corsica, even though it takes longer, it would be worth considering a trip through the Adriatic, which may still be faster/safer than a land trip. The combination of sea path+land path requires using the threat map to find an optimal path. If I can chart an optimal path which goes through sea, then I can check if I need resources like ships to transport the troops, estimate when they become available, and adjust the plan value accordingly. The "when they become available" part is pretty hard since right now I don't have any idea about that.

As for units getting unloaded, I miss the point of not unloading them systematically. If you go on shore, you can't add other units unless they are incorporated to the carried taskforce. So if we want to allow automatic unloading, then it should be systematic imo. Of course, a naval battle could take place prior to unloading if the defender has ships. But then again, one may not be able to land at all (that's what protected Constantinople for centuries: there was nowhere to land to attack the city).

[alms66]

If there is the possibility of a naval battle, there should be a 'scouting' phase to see if the defender has time to move against the attacker. If so, have a naval battle, and if the attacker wins, he can land his troops to fight the land battle, if he looses, he looses his troops (assuming he was destroyed, of course). Regarding Constantinople, just because there is no place to land the troops doesn't mean it can't be done. It's a matter of transferring to smaller craft that can make the landing, or landing a few miles away and marching to the city/battlesite. At Clash scale, I think we're safe in allowing it.

[LDiCesare]

I have re thought about naval ai. Here are the notes I wrote, open for comments.
I tend to consider that the best option for a fleet is to be grouped together rather than dispersed (read that in some American strategist's writings but I can't remember his name) in general.
I'm afraid it's a bit chaotic and maybe inconsistent, but these are the various steps I used to reacha possible algorithm:

Naval and amphibious warfare:

Objectives/Plans for the navy:
Carry land (or air) units.
Protect carriers/transports (normally through taskforce composition and regular reinforcement code).
Destroy enemy sea units.
Patrol in order to avoid enemy sea units from landing.
Bombard shore.
Explore.

--On Land units carrying:
-- Strategic:
-- Needs to commission transports in the right place.
-- Needs to realise there are target objectives reachable only by sea and commission a dedicated aphibious task force to tackle these. The task force should be able to reuse existing idle units.
-- Tactical:
-- A land unit deciding to move to target square should decide whether it's too slow and check if it would be faster to go there by boat. If so, ask for transport.

How to decide of land/sea units cooperation:
Option 1) Land units decide, and sea units are just a part of the pathfinding. Drawback: Sea units would have to get to given point in time, complexifies pathfinding.
Option 2) Sea units decide of a target (amphibious assault being one of their possible plans). If they ask for an amphibious plan, land units will come in as usual reinforcements while the sea units stay at port or do something else. Drawback: Sea units may be moving one by one in an uncoordinated way.
Option 3) A higher level ai decides that an amphibious assault should be made and decides a task fore must be assembled. Drawback:The ai mustn't decide of amphibious assaults out of the blues, Will it know what to do with idle sea units?

Possible algorithm (option 2 vergeing on 3):
Sea task forces evaluate each possible plan:
-AmphibiousAssault
-Merge (if not deemed strong enough?)
-Split (if too big, with reference to what?)
-AttackSeaUnit
-NavalSuperiority
-Explore
(-Bombard)
The first goal of the ai should be naval superiority, without which an amphibious assault is out of question.
Merge, split and attack are just means to reach that superiority.
Thus I need an OVERALL Naval Military Influence. The goal is that:
- Near friendly coasts, Military Influence should be positive. This means patrolling into the unknown in order to reduce a negative effect from unknown squares. It also means moving ships towards place of negative influence in order to kill enemy ships there. If enemy ships are too strong, then order to build more ships and try to consolidate the maximum influence in friendly coasts (optimize positive influence, do not count negative one). Harassing the enemy is an option.
- If a weaker enemy ship is in range: Attack ship if moving there won't reduce military influence in any of our coasts to a null or negative value, and if there is not a big enemy military just behind.
- If Military Influence is positive near one's coasts, check all coasts where the influence is positive:
-- If there are enemy squares there, consider them as possible targets.
-- If there are no enemy squares, consider Exploration. Exploration is actually the same as NavalSuperiority except it reaches farther and attack of enemy ships should be systematic.


THE ALGORITHM:

A ship will first check for nearby enemies and engage them if it doesn't lower influence dangerously.

Determining which mode the naval ai is in:

-When in AugmentInfluence mode, own coast influence is then computed.
Note that friendly influence should be lowered where friendly transport ships are, in order to make sure that ships escort their transports.
If not positive, the Fleet ai is set to AugmentInfluence, otherwise it is set to Aggressive.

-When in Aggressive mode:
If an amphibious attack plan is being launched, stay in Aggressive mode.
If some coastal squares become negative and stay thus for more than N (3? 4? 5?) turns, then cancel Aggressive mode and switch to AugmentInfluence mode.
If there is an amphibious attack plan (see below) is in its buildup phase, stay Aggressive. If the target square is conquered, go to Consolidate mode.
If there is no amphibious plan, check coast influence and decide as in AugmentInfluence mode.

-When in Consolidate mode: If all land squares neighbour of the target square are conquered, check as in AugmentInfluence mode. Otherwise, if Consolidate mode lasted 5(? should be random but around that or another heuristic value about twice the time taken to carry troops there) turns, then check as in AugmentInfluence mode.

-If AugmentInfluence: Ships try to optimize positive influence near their coasts.
-If Aggressive:
---Enough ships to maintain positive influence on every owned coast will more or less remain in place as they maximize influence. The rest of the ships are flagged as "offensive ships".
---If there are offensive ships: Pick all possible land squares.
----If none: Explore submode.
Each offensive ship explores the nearest unexplored sea square (fogged squares should just radiate negative influence). If an enemy ship is sighted, all offensive ships are given an order to "regroup and attack". Regrouping should be limited to ships in one ot at most 2 turns range, otherwise the enemy ship may get lost.
If no enemy ships have been sighted for more than N (3,4,5?) turns, ships are allowed to split so they can explroe individually.
----If one or more: Enter Amphibious submode.
Compute expected economic value. Multiply by the naval military influence on the coast minus the enemy land military influence (times some factor?). If all are negative, pick a random one, or the one with the weakest enemy military, or the nearest one, or the one with highest economic value.Create an AmphibiousAssaultPlan object. Tag this square as "Amphibious Assault Target" as part of that plan. Here, also take in consideration own coast squares with negative land military influence (send reinforcements by sea to areas under attack by land).
Estimate necessary land strength to land there (at the very least twice or thrice the opposing strength in that square).
The new plan tracks the units assigned to it (and their strength) and can askForReinforcements() as other plans do..
If it is not possible to get enough existing taskforces (or new taskforces through reinforcement requests) after 2? 3? turns, then cancel plan and switch to explore submodeinstead.
Make sure land units are aware of a new plan, JoinAmphibiousAssault, which is ok when the unit has reached a target harbor, and whose value is evaluated as (amphibious target square value -minus/divided by- time to reach harbor).
The overall plan should not take too much time to complete, as it would be blocking units in harbour for too long.
NOTA: It would be possible to compute one such AmphibiousAssault plan for every harbor the civ has, particularly if the civ has several landmasses, or there are several seas (Mediterranean and Pacific for instance).
Sea units go to the harbor, and make sure (askForReinforcements) they can carry the land units there (and protect the transports? normally achieved by higher militaryinfluence at sea).
When all the transports, escorts and land units are there, the assault is launched.
-If Consolidate:
---Enough ships to maintain positive influence on every owned coast will more or less remain in place as they maximize influence. The rest of the ships are flagged as "offensive ships".
Offensive ships are used to bring reinforcements to the square target of the previous AmphibiousAttackPlan. Amount of reinforcement is to be determined by the land units there.

REMARKS:
This algorithm doesn't really allow to land troops on a friendly part of a continent which is also controlled by an enemy. This should be a legal target for AmpphibiousAssault. The ai when going into Aggressive mode could ask for any Land Plans in need of reinforcement and decide to help them for instance.

[Mark_Everson]

Hi Laurent:

This looks very good to me. I'm sure that there are defects, and additional factors, but they'll probably only become apparent as you get things coded and we get some playtesting in.

Which part do you want to try first? My guess is keeping it purely naval and just seeing how the sea fight goes is a tough enough first goal. Though perhaps it would be more exciting in terms of playing if naval combat and influence were left for later, and just amphibious assaults were turned on.

I think that we'll also soon need automatic patrol and intercept orders. Without them true coastal defence will be impossible. Do you agree? I'm not trying to give you extra work, but ships move so fast across the map that without automatic interception by "sentry" ships it will be impossible to prevent landings even if you have naval supremacy.

[LDiCesare]

I'm first getting the purely naval part done. Asking for land troops and amphibious assaults will come second.
In my first draft, I also don't make very good optimisations of placement, but I plan to iterate and converge suing whatever optimisation mechanism works best (gradient, annealing, genetic algos) depending on result and speed.
Automatic intercept orders are indeed a must, but won't be in the first code released.