A Better AI.

[Iustus]

I didn't post a save yet. Sometimes a screenshot says it all, sometimes a save is useful to take a better look. In this case, you shall get a savegame, the 1214AD autosave.

I normally leave the cheatcode off so that I don't know that the AI is planning a dagger attack or some other spoiler information. I switched it on to look at the 1214AD autosave and got the screenshot with extra info for you. It is apparently the best settling spot for Cyrus (who's empire is very close), but the settling values are all pretty low. I think that the AI underestimates the value of luxury resources for happiness and trading. Yes, it is a poor city, but it is good for an empire. (The spot selected is the one inbetween the 4 furs.)

As I have already progressed further in this game, it is not a real problem to get some spoiler information from a savegame in the past. Apparently all the AI on my continent are planning a dagger attack. Probably because I'm playing with the aggressive AI setting. I'm about 15-20 turns or so further now and about all of the AI are at war now, so the dagger strategy worked. The dagger attack strategy of course will lead to less settling, but it is already 1212AD and the AI should have settled the spot by now.

http://forums.civfanatics.com/uploads/31106/AutoSave_AD-1214.CivWarlordsSave

Founding values.JPG

Some useful numbers:

DaggerAI:
(with 1 city) found sites of 1000+ will encourage building a settler
(with 2+ cities) found sites of 2500+ will encourage building a settler

All AIs (dagger or not):
(in financial trouble) require found site of 2000+ to build settler
(otherwise) require found site of 1+ to build settler

AIs are very unlikely to build Settlers while at war.

Cyrus is not in financial trouble in your game, but he is in war. Has he been in war often?

-Iustus

 

[Iustus]

I currently play with the latest Sevo/GIR/Keldath MOD loaded. Can I just use this "Better AI" MOD on top of their MOD? I'm guessing I just download this MOD and install it over their MOD folder. Please let me know if I can or cannot do this. Any information would be appreciated.

Thank you for your time!

Look inside their mod folder and check for CvGameCoreDLL.dll. If it does not exist, then you can add the BetterAI one and it will work fine (or just put the BetterAI one in CustomAssets and it will still work with the mod).

In this case, I strongly suspect that mod has its own CvGameCoreDLL.dll. What that means is the developer of that mod (GIR or Keldath or whoever) is going to have to add the BetterAI changes to their mod for you.

I have posted instructions on merging their code with BetterAI , it is rather straightforward.

Hope that helps,

-Iustus

 

[Roland Johansen]

Some useful numbers:

DaggerAI:
(with 1 city) found sites of 1000+ will encourage building a settler
(with 2+ cities) found sites of 2500+ will encourage building a settler

All AIs (dagger or not):
(in financial trouble) require found site of 2000+ to build settler
(otherwise) require found site of 1+ to build settler

AIs are very unlikely to build Settlers while at war.

Cyrus is not in financial trouble in your game, but he is in war. Has he been in war often?

-Iustus

Thanks, Iustus, that explains a bit why the AI has not founded the spot yet. The value is too low for an AI in dagger mode. Cyrus is not at war in that savegame yet. He will be in about a dozen turns. I know, I've seen the future If I recall correctly, he has not been at war yet in this game. But he has already settled about 15 cities, so maybe all those other cities had a higher priority. (Another note: this game has not been played with the same version of betterAI from beginning to where I'm now. I started the game a few weeks ago. It's a huge map and those games take a while to finish.)

Still, I would have founded that city a long time ago, just for the happiness benefits. The AI values those a bit too low I think. But I've read many posts of you and Blake and realize that it will be difficult to balance the code of settling in such a way that the AI will not settle too greedy in the middle of a bunch of resources and at the same time still value the resources highly.

If you value the resources very highly then the AI will settle at spots 1 tile of the coast just to get the maximum number of resources in the fat cross or he will take all of the resources with one city and leave nothing for the other cities. If you value them too low, then the AI will ignore them (which I think is what happens in this case).

Could it be possible to split the valuation of the settling spots and the order in which the spots are being settled? You'd have some code telling the AI where to settle its cities and then you would have some code telling the AI in which order to settle its cities. The spot described above with the many furs would get a low value for settling there so that the AI keeps a good pattern in its empire of cities. Nothing too close or too far apart, and all the other stuff that leads to a good city pattern.
But when an AI decides where to place the next city, it should not purely follow the above valuation. It should pick the 5 spots of highest value (5 distinct spots, at least 5 squares apart) and then reorder them according to other valuations. Some city sites would get a bonus because the resources within the fat cross of that new city will hold a number of food or luxury resources that the AI hasn't claimed yet. Or another potential city site might get a huge bonus because it has iron in its fat cross and the AI doesn't have iron or copper yet.

The advantage of splitting this code in two parts is that the AI won't destroy a nice pattern of cities with a huge preference to get its first iron resource. Could this work or is it too difficult to implement in the civ4 code? Settling code is really difficult, I get that, and this might not work at all.

 

[zakalwe]

With a governor rewrite I can mostly eliminate this phenomena and generally force it to pick optimal configurations. It is however not a trivial task - as I said it's been in every version of Civ (and SMAC) so it's not an easy thing to fix. The main problem is performance - any kind of brute force approach (ie comparing every possible configuration) will just be far too slow. Extremely clever techniques are needed...

While perhaps not the easiest thing to fix, this does sound like a fun challenge, don't you think? It looks to me like this is an instance of the knapsack problem. As such, it can be solved efficiently using dynamic programming.

To see how this maps down to the knapsack problem, consider each workable tile as an item whose value is a function of the tile yields (food, production and commerce weighted according to some preference) and whose cost is 1 citizen. Additionally, there are some number of available specialists, whose value is calculated similarly; these also cost 1 citizen each.

The problem is to maximize the total value of the chosen items while keeping the total cost below the number of available citizens.

The only complication I can see is the need to avoid unacceptable starvation (some starvation might be OK). One solution might be: Whenever the optimal tile/specialist selection leads to unacceptable starvation, gradually increase the emphasis placed on food, and recalculate the optimal selection until it avoids starvation.

Based on the awesome work you've done so far, I'm guessing that you have enough experience and/or theoretical background to see what I'm getting at here. If you'd like me to be more specific or provide more details, though, I'd be happy to.

 

[KrikkitTwo]

While perhaps not the easiest thing to fix, this does sound like a fun challenge, don't you think? It looks to me like this is an instance of the knapsack problem. As such, it can be solved efficiently using dynamic programming.

To see how this maps down to the knapsack problem, consider each workable tile as an item whose value is a function of the tile yields (food, production and commerce weighted according to some preference) and whose cost is 1 citizen. Additionally, there are some number of available specialists, whose value is calculated similarly; these also cost 1 citizen each.

The problem is to maximize the total value of the chosen items while keeping the total cost below the number of available citizens.

The only complication I can see is the need to avoid unacceptable starvation (some starvation might be OK). One solution might be: Whenever the optimal tile/specialist selection leads to unacceptable starvation, gradually increase the emphasis placed on food, and recalculate the optimal selection until it avoids starvation.

Based on the awesome work you've done so far, I'm guessing that you have enough experience and/or theoretical background to see what I'm getting at here. If you'd like me to be more specific or provide more details, though, I'd be happy to.

Actually that seems to be similar to the way it is done (food has a variable value)

Essentially it should be very easy,

1. look at each tile/specialist job available,
2. calculate the value of each based on valuations
3. work the greatest N tiles/specialists where N is the number of usable citizens (non-unhappy ones)

(with a reevalution of the value of food and repeating if you end up with starvation)

The only issue is what the default valuations of Food/Hammers/and Commerce should be.

It would only get more complicated if there were Interactions between tiles that could change there output... there aren't. Every worked tile produces the same amount regardless of what other tiles are being worked.

 

[zakalwe]

Yep, thanks for summing it up so nicely. I guess my reference to the knapsack problem is a bit misleading/confusing, in that this particular instance is a lot easier than the general case, since all items have the same cost (1 citizen).

 

[Iustus]

DaggerAI:
(with 1 city) found sites of 1000+ will encourage building a settler
(with 2+ cities) found sites of 2500+ will encourage building a settler

All AIs (dagger or not):
(in financial trouble) require found site of 2000+ to build settler
(otherwise) require found site of 1+ to build settler

AIs are very unlikely to build Settlers while at war.

Thanks, Iustus, that explains a bit why the AI has not founded the spot yet. The value is too low for an AI in dagger mode. Cyrus is not at war in that savegame yet. He will be in about a dozen turns. I know, I've seen the future If I recall correctly, he has not been at war yet in this game. But he has already settled about 15 cities, so maybe all those other cities had a higher priority.

In case I was not clear, if not in financial trouble, all civs will consider building a settler if there is a positive found spot. Since he has 15+ cities, I suspect it is just that he has always found a better spot.

I did not check to see if any of his cities had happiness issues. The AI could value happiness resources more if it needed them more, this would translate into increasing the value of the spot as its cities got close to the happy cap. The value of a 2nd (or more) of something, for trade purposes probably could be calculated better as well.

Right now I do not see this as a major problem. It will fill that spot when it runs out of other spots to fill, until then, if its cities are still growing, its not a huge deal (unless it loses the city site to someone else.

As far as war is concerned, once an AI decides to go to war, it is in war building mode (much lower chance of building a settler), even before war is declared. It can spend 20 turns in war mode, never declare war, and then give up and go back to peace. It still spent those 20 turns not building settlers.

Dagger AIs basically build a unit every other normally decided build. If there is a city site that matches those criteria, then it has a decent chance to build a settler as one of these every other builds, otherwise it will be a military unit.

Still, I would have founded that city a long time ago, just for the happiness benefits. The AI values those a bit too low I think. But I've read many posts of you and Blake and realize that it will be difficult to balance the code of settling in such a way that the AI will not settle too greedy in the middle of a bunch of resources and at the same time still value the resources highly.

Could it be possible to split the valuation of the settling spots and the order in which the spots are being settled? You'd have some code telling the AI where to settle its cities and then you would have some code telling the AI in which order to settle its cities. The spot described above with the many furs would get a low value for settling there so that the AI keeps a good pattern in its empire of cities. Nothing too close or too far apart, and all the other stuff that leads to a good city pattern.
But when an AI decides where to place the next city, it should not purely follow the above valuation. It should pick the 5 spots of highest value (5 distinct spots, at least 5 squares apart) and then reorder them according to other valuations. Some city sites would get a bonus because the resources within the fat cross of that new city will hold a number of food or luxury resources that the AI hasn't claimed yet. Or another potential city site might get a huge bonus because it has iron in its fat cross and the AI doesn't have iron or copper yet.

This seems overly complex to me. I think some additional value to the furs, when it needs them, should do the trick. It also seems like there may have been a change which overall values city found sites a bit low under some conditions, which perhaps needs a tweak. It is going to take a bit of testing time to see if its set exactly right.

-Iustus

 

[Iustus]

Actually that seems to be similar to the way it is done (food has a variable value)

Essentially it should be very easy,

1. look at each tile/specialist job available,
2. calculate the value of each based on valuations
3. work the greatest N tiles/specialists where N is the number of usable citizens (non-unhappy ones)

(with a reevalution of the value of food and repeating if you end up with starvation)

The only issue is what the default valuations of Food/Hammers/and Commerce should be.

It would only get more complicated if there were Interactions between tiles that could change there output... there aren't. Every worked tile produces the same amount regardless of what other tiles are being worked.

The big problem I see there is the 'recalculate if starving' part, that could end up being very expensive if you did it wrong. Losing you all the savings from using a new algorithm.

The current algorithm clears all the plots every time a change is made, and then one by one adds worked plots/specialists until there are no more citizens to place. Each time, it revalues food/hammers/commerce, based on the new reality. Primarily this means the food value changes. When the first citizens are placed, the city is starving (by definition), so food has a enormously high value, as it gets closer to not starving, the food value levels off, and non-food plots can be choosen. It is actually a little more complex than this, but thats the basic idea. The big problem I see with it is that it is a n^2 algorithm. It checks all 20 plots plus every specialist type, calculating the values for each, picks the best one, then repeats the same process again for the next one. I am leaving out the juggle it does at the end, to see if it can pick some poor food plots instead of some high food plots and still be doing ok. (Blake hates the juggle!)

It is definitely an interesting problem. I was looking forward to rewriting this thing, but Blake has started on it, so I will wait and see what he comes up with.

Since we have more or less feature frozen, this rewrite will probably not end up in the 1.0 release. Which answers someone else's question, yes we will be working post 1.0 on this. Personally I am working on some speed optimizations. You know the huge lag you get when you trade a map, I have a plan to get ride of that nasty. Sadly, a few optimizations I would like to make, I cannot because of save file compatibility. I did a source check in today, if you are building a mod that breaks save file compatibility, you can #define FASTER_VISIBILITY_NON_SAVE_COMPATABLE which will give you the speed up.

-Iustus

 

[ToxicBones]

Got 2 more emphase wrongs.

1. When building a settler in a bigger city and being imperialistic, the AI use 1F 1H over 2H, which would lead to settler completement 1 turn earlier.

2. 1F 2H and 1F 3H is preferred to be used over 5H and 2F 3C.
Perhaps it have something to do with the one unhappy person in that city.

 

[KrikkitTwo]

The big problem I see there is the 'recalculate if starving' part, that could end up being very expensive if you did it wrong. Losing you all the savings from using a new algorithm.
-Iustus

Well I was thinking about that, I figure the best way would be to give food a value something like 2^F where F ranges from 1 to 8.

If the value of F could be stored for a city from one turn to the next, then it could work something like

0. F=1 to start with so goto step 1
1. Check spots (at F=1, 2 for food value)
2. Get highest N "tiles"
3. Starving, so +1 to F (goto step 1)

1-3 loop for a bit until a food surplus is reached say at food =16 (F=4) and those tiles are used

Next turn

0. F is currently >1 so -1 F and goto 1*
1*. Check spots (at F=3, 8 for food value)
2*. Get highest N "tiles"
3*. Starving, so +1 F go to 1

F stays at 4, food value=16 is still needed to maintain growth

Next turn (a Pasture is built)

0. F is currently >1 so -1 F and goto 1*
1*. Check spots (at F=3, 8 for food)
2*. Get highest N "tiles"
3*. NOT Starving, so go to 0 [evaluate at a a Lower food value]

0-3* loop for a bit until they get the city to starve (or reach the minimum) and then the food need is adjusted one more up)


So most cities will check all of the tiles Twice (can I devalue food? No, Ok I need to go back)

Any time Food "Risk" changes through terrain improvements (or border changes, or happiness changes, etc.) there may be a several 'checkings' to adjust to the new environment. (ie devaluing food until starvation is reached and then one upvaluing food, or several upvaluings of food until starvation is avoided)

This way the # of calculations would only get large with a major change (waves of unhappiness or a city being conquered/founded)

A really interesting idea would be if the 'Avoid Growth' button basically determined what was considered Starvation for these purposes. [also the level of F could be limited based on the degree of starvation] Basically I see 3 types of 'Starvation' to a city

Stagnant
Food Deficit
Pop loss

'Avoid Growth' would mean you devalue food until devaluing it more would mean Pop loss (so it might move between Deficit and Surplus)

Normally you would stay one step above Stagnation not just Pop loss.

 

[Roland Johansen]

This seems overly complex to me. I think some additional value to the furs, when it needs them, should do the trick. It also seems like there may have been a change which overall values city found sites a bit low under some conditions, which perhaps needs a tweak. It is going to take a bit of testing time to see if its set exactly right.

-Iustus

Ok, Iustus, you know what you're doing.

Also interesting to hear about the governor rewriting. I hope you get it to work as you desire. Getting the values right can be tricky and there will of course always be people who won't like it.

Did you read about those defensive catapults of someone who didn't attack an attacking stack but chose to defend the city. Is there anything that can be done about that?

 

[snoochems]

Hi all.

Just a question about the AI and it's ability to plan a war...

Does the AI even PLAN a war? Or is it just a matter of declaring war, and then start organizing the assault and defense force?

I mean, when I go to war deliberately, I plan it... i send the bulk of my troops to the front lines, and organize my navy appropriately. The AI seems to go to war, and then start actually moving units and placing its army in strategic points.

 

[zakalwe]

This way the # of calculations would only get large with a major change (waves of unhappiness or a city being conquered/founded)

Additionally, you can improve the worst-case by doing a "binary search" over the range of food weights, until you find the food weight that gives you the food surplus you're looking for.

This should improve the worst-case complexity to O(N*log N*log W), where N is the number of tiles/specialists (which need to be sorted by value) and W is the maximum possible weight placed on food.

 

[Jet]

About the governor, it seems to me that if you have to weigh food against everything else, that will tend to make things complicated and/or bad at choosing the right amount of food. An alternative is to evaluate food and everything else separately. You can situationally compute a target total food intake H, and an value function v(tile) which considers everything else. Then the governor's problem can be to maximize total v(tile) subject to the constraint that total food yield >= H.

Here's another governor algorithm which tries to do that. The algorithm is to choose tiles two at a time, greedily maximizing value while always keeping food at a target average. I conjecture that choosing tiles two at a time finds a best solution because there are two dimensions, food and value. I'm not that familiar with combinatorial optimization, though. I don't know what the speed considerations are, so this is only trying to make the governor better, not faster, but I think this can be done in O(N^2 log N^2).

Details:

Spoiler :

Let pop = population.

Let J = the set of citizen jobs (tiles and specialist slots). If the number of some kind of specialist slot is limited to L, then J includes L of those slots. If the number is unlimited, J must include pop of that specialist slot. There's probably a more efficient way to handle specialist slots, but this suffices for a first cut.

Let H = target total food intake. (H for Hunger). Some function calculates it situationally based on happy, health, pop, emphasis buttons, and whatever else you like.

Let h = target average food = F/pop.

Let f(j) = the food yield of a citizen job j.

Let v(j) = the value of a citizen job j. Some function calculates it situationally based on emphasis buttons and whatever else you like. The output of v is actually a pair (V,f(j)) whose purpose is to allow jobs to be ordered first by their actual value V, then to break ties by food yield. The calculation of V must not consider j's contribution of food to H, but it should consider any other benefit of food - the only one I know of being when you're building a food item (a Settler or Worker.)

The goal is to maximize total v(j) subject to the constraint that total f(j) >= H.

Algorithm:

First take care of the special case where you don't have enough food. If the sum of f(j) for the pop highest-food jobs < H, set H to the value of that sum and start again.

For all |J|*(|J|-1)/2 pairs of distinct jobs j1 and j2, calculate fp(j1, j2) = f(j1) + f(j2) and vp(j1, j2) = v(j1) + v(j2).

for i = 1 to floor(pop/2)
... from among the pairs that will keep the average food yield at h, choose the one with highest vp
... remove those two jobs from candidacy
if there's a pop point left, then from among jobs that will keep the average food yield at h, choose the one with highest v

I'm not specifying the data structure and algorithms for the set of pairs of jobs, but I suspect that with ingenuity one could devise something good enough. For example -- if you assume that the number of distinct fp values is reasonably small, you could use a doubly-linked list of fp bins sorted by fp, each bin being a doubly-linked list of job pairs sorted by vp, with one pointer from each job to the links for the pairs the job is a member of. Then at each iteration you'd look at the bins with minimum or better fp; you'd look at the highest-vp pair within each one, and choose the best one. It looks like the setup couldn't have higher complexity than a flat sort - O(|J|^2 log |J|^2) - and the selection and update would be O(pop^2 * (# of fp bins)). With this data structure, you wouldn't have to implement that business of v returning a (V,f(j)) pair.

 

[peacenik]

Great to hear that the project continues after Release 1.0. I just played a game on 'Noble' to get my first taste of the mod improvements, playing to get a feel of the changes, not a challenge, and I got slaughtered by China and Russia ganging up on me in about 1450 AD! This never would have happened to me prior to 'better AI'.

I hesitate to bring this up now, because save game compatibility is one of the cornerstones of your project, but both Blake and Iustus have commented over time regarding improvements they could make that would break save game compatibility, so they were not pursued. I hope you consider heading away from save game compatibility if you think that is the best way to improve the AI.

 

[Ralgar]

yes we will be working post 1.0 on this.

I would love it, if after the 1.0 release and some optimizations you guys would go beyond save-game-compatibility. Giving the AI a sense of a planning the future and several objectives it pursuits.

 

[Harrier]

I do not have a problem with breaking "save game compatibility". If I want to keep playing a current game - I just don't load the version that breaks the saves until I have completed the game. Simple really.

Maybe the way to go is:

1. Publish version 1.0 - which is save game compatible. The only future work on this version will be bug fixes.

2. Start a new version with the changes that break saves. If people are aware of that fact - it should not be a problem.

Those wanting to test this second version should be prepared to expect a few updates that break current games whilst the development takes place.

A warning to that effect should be all that is required.

So keep up the good work Blake and Iustus.

 

[Mutineer]

I am not sure what algoritm used currently, I will give a shot for a fast algoritm.

Assumptions:

No empacis mean we want a max productivity, which is SUM(Resource*multiplicator).
Cities wihich are below happiness and health limit can apply increased food multiplicator in no empasys settings.
Different empacis mean we want to acieve max empasys resource with out starwation.
Algoritm should be universal, no matter what mods are applyed.
Assume all mods mean 1 pop work one tie or can have one spec. Spec ties are limited or unlimited.
Assume food as the only resourse that is absolutly needed, but jenerally algoritm can be extended to include other resource as compalsory resource.
Assume existance of forced ties.

Calculate number of population which do not work forced ties/specialists. = NPOP
Calculate total food needed. = NFood.

Calculate Productivity multiplifyers.
MShields = burocracy bonus* buildings bonus * empasys bonus.
MCommerce = buricracy bonus * (Tax&#37;*Money building bonus + Sci%*Sci Building bonus + Culture%*culture buildings bonus* culture valus)/100% * empasys bonus
MSci = Sci building bonus* empasys bonus
MMoney = Money building bonus *Empasys bonus
MGP = GP buildings bonus *Empacyc bonus *Value bonus
I probably would not use commerce empacyc bonus for specialists
(Assume 0 Value for Culture. For cities that going for cultural win for AI culture value couls be put to 1)
Calculate total avalible ties.

Tot slots = Number of ties city has + Number of limited specislists slots + Avalible population * (true/false) present unlimited specialists.

I make no assumption on can specialists make food or not.

Calculate default food weigth:
Calculate slots weigth with out food.

Non food slots weigth = Sum(NResourse * MResource) + weigth of continue working tie(like cottagess, weigth could be calculated as Increase/Nturns to increase*MBonus)
calculate max average slot weigth with out food MaxAverage = Sum(Best slots)/NSlots

Calculate food slots and max food MaxFood = Sum(food in biggest NSlots) .

If food empass, food needed (NFood) = min(MaxFood, max food can be used with out loss for city grow, as city currently can grow only 1 pop turn.

Now aproximate bit, this is pure aproximation:

MFood = MaxAverage*NSlots/MaxFood // this is the only funny bit,
//it is based on my intuition, as I can not prove it mathematically stright away.
//But one of principles of emrirical calculation is it is does not matter how precise you weight is, so
//long as you take in account all factors.

Iterative bit:
begin
Calculate full slots weigth as Non food slot weigth + NFood*MFood
Check if Sum Food in best Nslot food >=NFood

I suspect it should work, but need some testing and may be an iterative bit at this moment,
I Sum <NFood then
begin
New MFood =MFood *NFood/(Food achieved)
Go to start of iterative bit
end
exit
end


I tend to be horrible in trying to write pseudo programss, hopefully one can undestand what I wrougth.

Efficiency of algoritm depends on efficiency of sorting
NBest out of M total, which should be for an efficient algoritm be =
M* LN(M) or even M*LN(N)

I realy forgot which algoritm would be most of use, where is my Knyth?

 

[Wodan]

One thing I've noticed about the latest build (1/8) is about the AI's responsiveness to an invasion, in terms of what to build and what to spend limited cash to upgrade.

e.g., I'm invading with Cossacks and have 12 of them scattered around pillaging. The AI builds Knights. Clearly, Pikemen would be a much better choice. Knights vs Cossacks = roughly strength 5 vs 15. Pikes vs Cossacks = roughly strength 12 vs 15. I think he's building his best unit without consideration for what he can see hurting him.

Same thing for upgrades. I'm looking at a mixed bag of garrison troops which include some warriors. Clearly upggrading warriors to pikes would be a better choice than upgrading horse archers to knights.

Wodan

 

[Pep]

The trebs attacking Alexandria can't bombard the city from the hill! But moving them to another position makes bombard to work properly again...

I have also notice in this game that AI is not using the proper defenders to counterattack my stack. It should build more catapults. When it's in danger, it whipes many units (which I think is a very smart tactic) but it chooses the wrong defender (too many longbows that fall easily under the trebs attack).