AI -- the Thread

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