AI -- the Thread

[LDiCesare]

I implemented a division by time needed and found out that staying where you are is highly valuable in these conditions, so I changed the divider to (number of ticks per turn + ticks needed). This allows distance to be taken into consideration, but not too much. Without adding the value of intermediary squares, I don't see any change in the ai so I'm not really keen to do more coding on that topic until I have a scenario where we can see an effect of the code.
I also finally implemented the possibility to have different military attitudes for a single ai. Thus Carthago spends 5 task forces on attack and 1 on defense.
The implementation is rough (I commit a number of task forces, but don't care about their actual strength), but should do for now. What this means is essentially that orders of wait, owncity can be removed from offensive attitudes, and the ai will commit units to various attitudes, alwas leaving defenders thanks to those taskforces with stonewall attitude for example.

I will flesh out this a bit more (I must allow a taskforce to specify its attitude through xml so Hannibal always "attacks"). After that, I think it should be worth checking whether to continue on the ai now or to code something else (like saves).

[Mark_Everson]

Hi Laurent, sounds like good progress!

I'll be out of town for a while, and very busy for the next week. In a few weeks, if you're ready, we can put out a new version of the testbed based upon your recent improvements.

Cya,

Mark

[alms66]

What follows is compiled from several notes I found on the AI for EIT (I’m still unpacking…). I post it here for any helpful hints or suggestions that it may provide.

Meet the AIs

CivManagerAI: CivManager is the highest level of AI associated with every player. It makes all decisions as any human player would, though it leaves most implementation to ProvinceManager and TheaterManager, which human players can do as well. CivManager is not present in any human controlled empires.
C++ Note: CivilizationAI is an extension of the Civilization class that adds CivManagerAI.

ProvinceManagerAI: ProvinceManager is the second level of AI associated with every player. It is created for every province in the civ’s empire. It takes commands from and sends reports to CivManager. It has nothing to do with TheaterManager.

TheaterManagerAI: TheaterManager is not a single AI. It is created for every theater that CivManager creates. It is essentially a small part of ProvinceManager (the DefenseManager) added to OffenseManager. It takes commands from and sends reports to CivManager and has nothing to do with ProvinceManager.

Notes:
1. I’m going to show one level down into these ‘managers’ but no further. If I were to get that detailed this would span more pages and take up more time than I’m willing to use. If requested, I can elaborate further, but I’ll only do so then.
2. The only ‘unit-level’ (or TF-level) AI that exists is path-finding and other assorted necessities.
3. The three AIs above, as well as many below, are of the Project AI sort (http://www.gamedev.net/reference/art...article545.asp), while the overall design is of the Hierarchal sort (http://www.gamedev.net/reference/art...article199.asp)

CivManagerAI Detailed

Here’s a detailed look at the internal structure of CivManager:

ForeignManagerAI: ForeignManager handles communication and interaction with other empires, except for the military side of things. When the situation gets hairy here, ForeignManager calls up MilitaryManager and tells him to bring out the guns. ForeignManager also handles espionage and covert actions.

DomesticManagerAI: DomesticManager is a workhorse. It makes decisions regarding all domestic policies. It has no interests other than it’s own lands. It does, however, request resources from ForeignManager, if they can’t be acquired through ProvinceManager, from time to time. If ForeignManager cannot meet the needs peacefully, it will look for ‘other’ ways of meeting the needs, including declaring war.

MilitaryManagerAI: MilitaryManager does not make the decision to declare war, though it can request that ForeignManager do so, it merely creates TheaterManager AIs and manages the military resources, upgrades units,

Notes:
1. I seem to remember adding one here…though I can’t recall what it was if I did.

ProvinceManagerAI Detailed

Here’s a detailed look at the internal structure of ProvinceManager:

InfrastructureManagerAI: InfrastructureManager handles large infrastructure projects, such as aqueducts and irrigation systems, which require many tiles of coordination. It also sets guidelines for the tiles in the province, though these are very weak guidelines.

TradeManagerAI: TradeManager collects all surplus commodities and takes orders for deficits from all the tiles. It redistributes the surplus to those tiles that have a deficit to fill, and if there are still deficits attempts to trade any surplus for needed commodities, as well as trade away any excess.

DefenseManagerAI: DefenseManager, with the resources given to it by ProvinceManager (given to it by CivManager), seeks to keep invaders out and keep rebels down.

TileManagerAI: TileManager handles all the drudgery at the tile level, such as general infrastructure (housing, schools, roads, etc.),

Notes:
1. EIT had both Resources (natural – labor to extract) and Goods (manufactured – resourses+labor to produce – these were of a higher price due to double labor involved). ‘Commodities’ is a term used to refer to both Resources and Goods. I’d really like to do this with Clash.

TheaterManagerAI Detailed

First thing is a definition and description of the concept of a theater. A theater is a rectangle encompassing an area of military activity. The theater also has a list of exclusion squares for when ProvinceManager’s territory overlaps with TheaterManager’s territory. The theater will be an empire that is being invaded, a section of water known to have enemy craft, or an ally’s empire we are attempting to defend, so these rectangles can get quite large, theoretically a theater could be the entire map, though CivManager places limits on the size of a theater. TheaterManager communicates with any adjacent TheaterManagers as well

For example, let’s use this as a sample map (the ‘a’ tiles represent the invasion territory while ‘b’ tiles represent the invader’s territory – some of it.):
o|o|o|o|o|o|o|o|o|o|b|b|b|b|b
o|o|o|o|o|o|o|o|a|c|b|b|b|b|b
o|o|o|o|a|a|a|a|a|c|c|b|b|b|o
o|o|o|a|a|a|a|a|a|a|c|c|c|c|o
o|a|a|a|a|a|a|a|a|a|a|o|o|o|o
o|o|o|o|o|o|a|a|a|o|o|o|o|o|o
o|o|o|o|o|o|o|o|o|o|o|o|o|o|o
You can see that the theater encompasses an area just larger than the empire to be invaded. It does not include ‘b’ tiles (they are on the exclusion list) because those are defended by ProvinceManager’s DefenseManager. TheaterManager’s DefenseManager only defends territory that’s been occupied. Meanwhile, the ‘c’ tiles are those that OffenseManager would seek to control, in order to secure the border and then proceed to achieve the original objectives of the war.

Here’s a detailed look at the internal structure of TheaterManager:

OffenseManagerAI: OffenseManager handles conquering…

DefenseManagerAI: DefenseManager handles keeping it conquered…

Notes:
1. Not much to add here…

[Mark_Everson]

Thanks for putting this up Alms. I don't really see much here that we don't already have (or have planned). Am I missing something? The exception is the detail on the theater manager map. We haven't yet gotten down AFAIK to subdividing the civ-level military AI into fronts, theaters or whatever. That is probably still a bit off in time.

[alms66]

No, you're not missing anything. As I said, I just found the notes and thought they could be useful to Clash, so I posted them... that's all.

[LDiCesare]

Cross-posted from Demo 8.1 Planning Thread: alms said:

The two main gripes on the AI's boneheaded decisions at this time are that it fails to go for the kill when it's got the upper hand and it very often does absolutely nothing, when it should be doing something.

Just last night I ran Jericho on computer only, and about 50 turns in all the AI's sent their units home and stopped attacking each other. What's that about? Did they get bored?

Failing to go for the kill: The ai currently has very tactical goals and not an overall strategy. This explains why it may wander around about useless squares instead of finishing off by attacking a capital for instance.
Doing nothing in Jericho is because
1) It no longer cheats by knowing everyone's territory.
2) It doesn't explore the map intelligently. I added some exploration goals, but these are still far from useful. They currently just add some random movement.

The ai would be much better if it had a high level planning that decided whether subplans should be explore and defend, attack and defend, attack explore and defend, and what in what proportion.

The ai also needs to figure out fronts. That should probably be done at the same level (figure out which enemy to attack and where).

The ai also needs to handle sieges and reinforcements better than it currently does.

[LDiCesare]

A question about evaluating the interest of plans of different types:
I recoded the attack nearest enemy order. Doing this, I have to know what the value of that plan is. It used to be the value of the square that enemy was in. I now use a combination of value of the square and value fo the unit. This is multiplied by the weight of "attack nearest enemy" order (all intrinsic plan values are multiplied by a factor defined in the militaryattitude file). The value of the square is 0 when uninhabited. This means that, for settled squares, things are relatively ok, but when squares are not settled, the value of the plan drops. The big problem is that the cost of a unit wert the value of a square is something of a totally different nature. Putting a mulitplier somewhere wouldn't work very well since this multiplier would be correct for a given combination of population/square value and unit cost.
I'm thus looking for a way to compare plans that have something to do with taking a square, others that have with destroying armies, and others (joinign armies, exploring unknown lands).
This would require a utility function to which I would convert the various values of each plan (square economic value, number of tiles uncovered or unfogged by exploration, economic or military value of enemy units...).
Any idea of how to design such a function in a way that will adapt smoothly to different scenarios, resource files and eras?

[Mark_Everson]

Hi Laurent:

Wow, that is a tough question! To do it right at almost requires a discussion thread all its own. My mom is flying in shortly, so I will just give an answer covering what I think we may need for the near future.

To keep it simple, I think I would make the utility function for now simply a weighted sum of all of the contributions that you mention (unit value, square value, exploration value, etc.). I believe for now you should have the weights for this function be global variables modifiable through the military attitude file. That way play testers can explore the values and see which sets turn out to be better for a robust AI. Also, in the short term, it might be useful to override these globals in a given scenario file just to fine-tune the AI. I would start with them having a value of one, and then move them up or down from there. Once it gets a bit more sophisticated however, I believe that this approach will fulfill your desire to have something that will retain relevance over different technological eras.

Here are some suggestions for placing all these different things on the same scale. I will use cash equivalents, because that strikes me as the easiest way to go about it.

1. Military Unit Value - build cost pro rated for unit strength. For enemy units destroyed, I would use something like .5x (replacement cost). Using this metric if we attack at 2:1 odds, destroying the enemy, while taking expected 20% casualties it would be credited as approximately 30% x original strength build cost success 30% = 50% enemy killed – 20% our strength lost. 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.

2. Captured economy value - economic value to the civilization of over some time period. I don't know what you are using right now for economic value. Can you tell me what the function call is that you do to determine a square's value? The economic value to the civilization in a single turn is tax rate x gross economy value. Since we should assume that we will conquer the square and hold it, there should be multiplied by some factor. Something like twenty seems correct for first guess. For right now the province capital should have a special effect in that it ends up flipping much of the province. As above we need special circumstances modifiers eventually to cover instances like chances we will not be able to hold the square, either due to military action or revolt, etc.

(BTW I think that provinces should not flip when the province capital is captured unless the enemy has at least a 2:1 military power superiority in the province. This simple rule would prevent a lot of silly things from happening...)

3. Value for merging with other TFs is even more situationally dependent than the items above. Do it right you need a two-step process where you say, if I were to merge TFs what is the incremental value of the plans that they might be able to execute over plans that they would execute separately. One obvious case is that a big stack that would like to besiege a fortified city should pull any siege engine units into it. Another metric to suggest is that if our biggest TF is already significantly larger than the enemy's largest TF, then separate smaller TFs should be formed to attack province capitals in an opportunistic fashion. Unfortunately I can't suggest any good math to back this up beyond my suggestion of a two-step evaluation up at the top of this paragraph. I don't know how practical such an evaluation is with the current code.

4. Exploration - assume for a start at the value of exposing a square is about 10% of the value that it would have if you conquered it. Since we don't know what the black squares are before hand, estimated their value by taking an average of a group of squares that we can see that are in that direction. That is, the economic value on the "front" of exploration.

BTW, settled squares do have economic value that can be calculated. In the migration code there is a way to estimate the economic value of a square if we were to plunk settlers down on it. If you take some small fraction of that value, that could be used as the unsettled potential value of the square.

Please let me know what else you need, in terms of specifications or specific function calls from the economics code, and I'll do what I can.

-Mark

[LDiCesare]

The code that is currently used to evaluate value of a square:
target.square.getEconomicValue());
What I use for exploration (I know it's bad):
targetSquare.getPotentialEconomicValue(civilizatio n) - I added that method to get an estimation, it's based on the average population of the civ and what the value would be in this case. One problem is the kapital brought. I then multiply that value by the number of squares which would be uncovered + those which would be unfogged. That's good imo but the way I choose the target square is not.

I add targetUnit.getCost() to the square cost in a PursueUnit plan. There needs to be a factor between them. I wish I could find a way to do so without putting figures in the xml files.

Multiplying the value of a square by 20 is rather pointless since it's a constant. Anyhow, if we do that, then we must also subtract the cost of holding this square, probably the cost of one or more military units.

I think we need a general unit <-> square equivalence from which we can build on. For instance, I may want to say ideally I want as many units as I can maintain with X% of my income. X being 10, 50, or whatever is historically correct, and then would be adapted based on what the opponents do (if they have a bigger military, I need a bigger one). (100 being the maximum is also a nice value because it would allow us to remove the arbitrary value, leaving for militaryattitude to correct that number by lowering the weight multipliers for plans that attack units instead of squares if needed).

So I think the value of a square would be the number of units it allows to maintain, and thus the value of a unit is the value of enough squares needed to pay its upkeep cost. So given that Square.getEconomicValue() is 20 * economy.getEconomicInfo(Economy.ESTIMATED_TAX_REVE NUES);
+ economy.getEconomicInfo(Economy.PRODUCTION_TAX_BAS E);
the revenue is about 1/20th of that ? So I should multiply the upkeep cost of the unit by 20 to compare these values correctly?

[Mark_Everson]

Originally posted by LDiCesare
What I use for exploration (I know it's bad):
targetSquare.getPotentialEconomicValue(civilizatio n)

I'll try to fix up that method to be more like what you intended.

I add targetUnit.getCost() to the square cost in a PursueUnit plan. There needs to be a factor between them. I wish I could find a way to do so without putting figures in the xml files.
(snip)
Multiplying the value of a square by 20 is rather pointless since it's a constant.

A way to bring unit and conquest on the same scale is the whole point of what I was trying to get at in my post above. I think that my additive function value = 1 (unit) + 2 (square) contribution in the post above is a good way to put the results of plans involving unit elimination and conquest on the same scale. (Then factors 3 and 4 can be added in when relevant.) Alternatively you could use target.square.getEconomicValue() instead of the 20x the one-turn value since they are fairly similar (see your formulae above).

So I think the value of a square would be the number of units it allows to maintain, and thus the value of a unit is the value of enough squares needed to pay its upkeep cost.

I think the value of a military unit for equivalent puposes should be more than maintenance. Essentially maintenance only covers steady state, but the cost to generate the unit in the first place should enter the calculation. It should be value = maintenance + (cost to build) / factor. Factor is TBD but is probably in the range 5-50.

So given that Square.getEconomicValue() is 20 * economy.getEconomicInfo(Economy.ESTIMATED_TAX_REVE NUES);
+ economy.getEconomicInfo(Economy.PRODUCTION_TAX_BAS E);
the revenue is about 1/20th of that ? So I should multiply the upkeep cost of the unit by 20 to compare these values correctly?

Revenue is just the first term. I don't know why the second term is in there. I think Gary put it in there. For a tax rate of 10% the first term is about 2x the importance of the 2nd. I think you have a decent idea, but it will need tweaking. And you haven't mentioned it, but I assume you also accout for the expectation of lost units and count those in the cost metric I have above. (I missed maintenance in my 1-4 cost elements above, it should have been included in the unit cost of an operation as well as any replacement cost.)

I think that my approach above (if modified for maint.) and yours will actually result in similar comparisons for my factors 1&2. We just argued using different methods. Let me know what you think.

Hope this helps!

[LDiCesare]

Both look like mostly the same yes. I'll do something like building cost + 20 times maintenance cost which would be the same as the square formula. (As usual, I'll tweak until I get something which looks like it works.)
The lost units are taken into account too, but at a different place:
The ai plan has a maxValue() function which is the best one can hope (with no loss or casualty). Then, if this maxValue is higher than what you currently got (i.e. this plan might be better than the other plans you already checked) you simulate it, and will subtract a value for the losses you suffer.

[Mark_Everson]

Sounds reasonable for a first refininement. How is the time to execute a plan handled in terms of cost? That seems like perhaps a more natural place for maintenance costs to me. How do you determine the value of a defensive plan vs an attacking one? this is a critical one to have balanced properly.

[LDiCesare]

Time to execute is not important. I mean it should be but we are far from this being important enough for it to be taken into account now. See the problems I have below. These must be addressed first. (A better way to say this might be: Time is of tactical concern, but I have strategic problems to solve before choosing the tactics.) Anyway it's a divider to the value of the plan if I remember well, but that alue itself is not accurate right now.

Attack vs. defense is right now precised by hand in the scenario file (note: there may be a problem nowwhen merging units which belong to different attitudes). The problem is the same as evaluation of attack / defense / explore. Except I need defense when I know I have enemies, and I would have to evaluate what the enemies would do in order to determine the defense I need. We're not yet there either. But see below.

Now, I have a big problem with the attack nearest enemy unit plan.
When I evaluate (army cost + square cost) I get values like 70 + 120,000 (in Jericho). The difference in magnitudes is about 1000, but that would be scenario dependant, and, worse, could very well be dependant on the tech level too (if I build unit which cost 20 times as much but my econ is only 2 or 3 times stronger, the factor is only 100). Multiplying one term by this factor (or, slightly better, dividing the other) doesn't give any good result as we are still comparing apples to oranges. The value of a military unit shouldn't be its cost but its military power.

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

We could use something more composite, like population * cash * military value, since all these are different and you can't really say that 1 unit of military is worth X units of cash, and the same for population.
Separating these is intersting because it would let me answer the question "Do I need some military?":
If I have 1000 cash, 1000 population, and I wonder whether I can build a military unit costing 200 cash and 100 population, worth military power of 1. If I convert the unit to cash, I am unable to answer, as the resulting cash is still 1000. If I say I go from 1000*1000*0 to 800*900*1, I see I increase overall. Building a second unit then becomes a question whether 800*900*1 < 600*800*2? and I can decide that the best value is to have 2 military units because the product is optimal for that number of unit (3 reduces to 400*700 *3 which is less than the value for 2 units).
Doing things that way, attacking an enemy unit becomes the following equation:
(pop of the square + pop of attacked unit) * richness of the square (independant of population) * (military value of enemy unit + military value of the square).
(Exploration would use potential population instead of actual in order to determine the value of the lands explored).
In order to evaluate defense, I could consider that a unit expands its military power outward and decide that my military power must be superior to that of my enemies/neighbours inside my territory.

I still have to figure out value of a square versus value of a unit ( ) but at least it's purely strategic. If I can express the value of a unit as its ability to take a square, and the value of a square as its ability to allow taking of another square (typically a square is worth what its neighbours are worth + map ai value for chokepoints etc. so it has an "influence"), I'd have the same unit of measure, which would help me a lot. By default 1 square is worth 1 strategically, and 1 unit is worth something only in comparison with other units, so it's probably a ratio: 1 unit stronger than another is worth 1, the weaker is worth 0. Since the winner will suffer losses and can win with only a given probability, its value is probably only 0.8 so the loser is worth 0.2. This value depends on the opponent, so it's very interesting to attack a weak enemy because my military value won't fall, while attacking a strong one is suicide and it's shown by a 0 or almost 0 strategic value... (needs refining)

(It's taken me more than one hour to write this rant and it's quite late here, I hope it makes sense).

[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:
Suppose I have 1 tf with power of 10, opponent has one with power of 1. Map is (m = mine, h= his):

mmm
hhh

And both armies are in the middle square of their own territory.
My threat value would be something like using power/1 + distance):

5 10 5
4 5  4

The opponent has:

0.4 0.5 0.4
0.5 1  0.5

The overall for me is thus:

4.6 9.5 4.6
3.5 4 3.5

for a total of 29.7. If I killed the enemy unit, let's say my power would fall to 9 and the opponent to 0, the map would be something like:

3.6 4.5 3.6
4.5 9 4.5

(my army has moved to the south).
worth 29.7 too, but I'd conquer some of its territory, so the strategic value would increase as instead of having 5+10+5 = 20 I'd have 3.6 + 4.5 + 3.6 + 9 = 20.7.
If I consider not only my value but the enemy's, I could also subtract the enemy's strategic value to know where I am. I would have gone from 20 vs 2 (18) to 20.7 vs 0 (20.7).

This could be used to make strategic decisions based on rough power projection figures, leaving combat simulations to evaluate the feasibility of a plan and to assess properly the threat function.

This might even be used to decide whether to go to war: Consider the move attack civ C at square X. If I do that, I'll go from a strat value of 100 to 95 and them from 20 to 10. If I'm at war with them, it's worth doing it, because I hurt them more than I am hurt. If I am not at war, then it's just weakening myself and thus not worth the risk. This also lends itself to computations for wars against more than one enemy: If suddenly B enters war, then I must consider that my move will reduce C's power but since B's would increase as a result, then I should not do that.

[Mark_Everson]

Originally posted by LDiCesare
Now, I have a big problem with the attack nearest enemy unit plan.
When I evaluate (army cost + square cost) I get values like 70 + 120,000 (in Jericho).

Something is wrong here in the econ value of square part. It should be nowhere near that big. My best guess is that it is a factor 1000 too high. I will look into it when I get a chance. My guess is it comes from the econ code using 1000 people as the basis for production, whereas the rest of the code uses 1-person units. My guess is that somehow we have overcounted by that factor. A quick top-of-head calculation for jericho is that at 15k people and primitive tech they should produce about 75 units of production per turn. Govt value per turn due to tax rate would then be about 8. Multiplying by the 20x factor for long-term value gives 160, which is not too far off the 120 (000) number. I've been this explicit in my answer so that maybe you can fix the problem yourself, and not be held up by my lack of time.

-Mark