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