Root of all AI improvment cycling evil?

[jdog5000]

Well, after a lot of searching and head scratching, I may have found it ... the (main) root cause for why the AI far too frequently will have a worker on one tile putting a workshop over a cottage, while a worker on an identical adjacent tile puts a cottage over a workshop.

This could be huge for the AI's late game economy, so the fix has to be right.

First, the problem code in CvCityAI::AI_bestPlotBuild ... this section of code is assigning a value to improvements the AI might build on a plot based on yield. This is only part of the code which does this, but it's the main part.

	for (iJ = 0; iJ < NUM_YIELD_TYPES; iJ++)
	{
		aiFinalYields[iJ] = 2*(pPlot->calculateNatureYield(((YieldTypes)iJ), getTeam(), bIgnoreFeature));
		aiFinalYields[iJ] += (pPlot->calculateImprovementYieldChange(eFinalImprovement, ((YieldTypes)iJ), getOwnerINLINE(), false));
		aiFinalYields[iJ] += (pPlot->calculateImprovementYieldChange(eImprovement, ((YieldTypes)iJ), getOwnerINLINE(), false));
		if (bIgnoreFeature && pPlot->getFeatureType() != NO_FEATURE)
		{
			aiFinalYields[iJ] -= 2 * GC.getFeatureInfo(pPlot->getFeatureType()).getYieldChange((YieldTypes)iJ);							
		}
		[B]aiDiffYields[iJ] = (aiFinalYields[iJ] - (2 * pPlot->getYield(((YieldTypes)iJ))));[/B]
	}

	iValue += (aiDiffYields[YIELD_FOOD] * ((100 * iFoodPriority) / 100));
	iValue += (aiDiffYields[YIELD_PRODUCTION] * ((60 * iProductionPriority) / 100));
	iValue += (aiDiffYields[YIELD_COMMERCE] * ((40 * iCommercePriority) / 100));

	iValue /= 2;

The logic here is that the value of a new improvement is equal to a weighted valuation of the change in yield from the current improvement.

For most improvement types, the array aiFinalYields holds double the food, hammer, and commerce yield of the plot with that improvement on it. The reason it's doubled is so that for cottages it can be the sum of the yields with a cottage plus the yields with a Town, so aiFinalYields/2 would be the average between cottage and town (with integer math, often you want to put off doing division until you've done all the multiplication you're going to do).

Two times the change in food, hammer, and commerce yield versus the tiles current yield is then assigned to aiDiffYields (bolded line).

Finally, the food, hammer, and commerce yield changes for the potential new improvement are given their respective weights and added to iValue.

So, as a example, if a grassland tile has a workshop (1F, 3H, 0C) on it and the AI is considering the value of placing a cottage there, the math would look like:

aiFinalYields for cottage:
4 (2*2)
0 (2*0)
6 (1 + 5)

aiDiffYields for cottage replacing workshop:
2
-6
6

Depending on the weights iFoodPriority, iProductionPriority, and iCommercePriority, the AI may decide to make the switch. Now, imagine it does go ahead and replace the workshop with a cottage. It will then look at the cottage and consider replacing it with a workshop, producing:

aiFinalYields for workshop:
2 (2*1)
6 (2*3)
0 (2*0)

aiDiffYields for workshop replacing cottage:
-2
6
-2

See the problem? It's asymmetric. When the AI is considering replacing a cottage, it uses only the current yield and not the sum/average between current and final. There's a significant range of the iFoodPriority, iProductionPriority, and iCommercePriority values where this will produce a constant flipping between workshops and cottages.

Now, this asymmetry also produces the following twist:

aiDiffYields for cottage replacing cottage:
0
0
4

Of course, the AI will never actually start building a cottage on top of a cottage, no issue there. If the code I've included above was the end of the valuation, then this twist would solve the problem with workshop/cottage swapping:

Cottage replacing workshop case:

iValue of cottage = (iValue of cottage over workshop)/2 + (iValue of town over workshop)/2
= (iValue of cottage over workshop) + (iValue of town over cottage)/2

iValue of workshop = 0

Replace if:
(iValue of cottage) > (iValue of workshop)
which reduces to
(iValue of cottage over workshop) + (iValue of town over cottage)/2 > 0


Workshop replacing cottage case:

iValue of workshop = (iValue of workshop over cottage)
= -(iValue of cottage over workshop)

iValue of cottage = (iValue of town over cottage)/2

Replace if:
(iValue of workshop) > (iValue of cottage)
which reduces to
-(iValue of cottage over workshop) > (iValue of town over cottage)/2
or equivalently
(iValue of cottage over workshop) + (iValue of town over cottage)/2 < 0

------------------------------------

Since (iValue of cottage over workshop) + (iValue of town over cottage)/2 cannot be both > 0 and < 0, there would be no flipping (assuming the priority weights for different yields stayed roughly constant).

However, if the iValue produced by this section of code is > 0 for an improvement, then there are a bunch of extra multipliers and adders that are considered. These extra factors depend on aiDiffYields but are quite different depending on which fields are possitive, so the asymmetry rears its head.

So, my proposed solution to this problem is to change this line:

aiDiffYields[iJ] = (aiFinalYields[iJ] - (2 * pPlot->getYield(((YieldTypes)iJ))));

so that instead of using 2x the current yield for cottage tiles, it uses the sum of the cottage and town yield. This would change the workshop over cottage case to:

Modified Workshop replacing cottage case:

iValue of workshop = (iValue of workshop over cottage) - (iValue of town over cottage)/2

iValue of cottage = 0

------------------------------------

Since this is potentially a big deal, I wanted to get feedback and ideas from all of you:

- Do you see any other simple change which could fix this flipping?
- Do you see any reason not to change this?
- What potential side-effects might there be?

 

[Yakk]

Crap. I saw that a while back when trying to get the "best city production" ... and didn't follow through with checking it. (in particular, the "improving terrain is the average of the terrain and the terrain after 2 improvements -- I didn't track down where it does the diff between the yields, and spot the bug you did).

In a mod with a really slow growth rate improvements, this creates artefacts -- but those artefacts already existed. Except now they cause flip-flopping.

Wait a second...

		aiFinalYields[iJ] += (pPlot->calculateImprovementYieldChange(eFinalImprovement, ((YieldTypes)iJ), getOwnerINLINE(), false));
		aiFinalYields[iJ] += (pPlot->calculateImprovementYieldChange(eImprovement, ((YieldTypes)iJ), getOwnerINLINE(), false));

That doesn't use the function I was thinking about. There is a function that looks 2 steps ahead -- that looks all the way to the end of the improvement chain?

...

This change looks like a really good one. There is no legitimate reason for that asymmetry that I can think of. After implementing it, it might have to be toned down from average of current and final -- but it will generate much better behaviour until then.

Other parts of the AI may end up being screwed up by this -- there might be a shortage of food/production if the AI's value for cash vs production vs food was tweaked for 'good behaviour' with the 'I tear down cities' code.

Of interest that in the current system, the AI will want to build cities in the "best" spot nearby. Then if that spot has no other legal improvements (inland green, say), it will let it grow. If it grows enough, when farming is legal, it will resist turning into farms.

 

[Roland Johansen]

Good job finding this.

I'm a bit surprised though as I remember inquiring before (I guess that was in the days that Blake was still working on the BetterAI) whether tiles were valued equally after placement as before placement, especially in the cottage case. I guess that realising that the code is asymmetric isn't that easy. It's easy to miss the asymmetry in valuation of tiles before and after placement.

So, my proposed solution to this problem is to change this line:

aiDiffYields[iJ] = (aiFinalYields[iJ] - (2 * pPlot->getYield(((YieldTypes)iJ))));

so that instead of using 2x the current yield for cottage tiles, it uses the sum of the cottage and town yield. This would change the workshop over cottage case to:

So you equalise the value of an improvement during the building phase and the replacement phase. Sounds perfectly logical.

I guess that cottage and town and workshop are just examples in this post. It would work exactly the same for village and town and farm. And if someone were to create other improvements which change over time, then these would also get the same treatment, right?

By the way, I think you're making it sound more complicated with a line like this:

Modified Workshop replacing cottage case:

iValue of workshop = (iValue of workshop over cottage) - (iValue of town over cottage)/2

Or are you planning to really code it like this? I got the impression that you were going the adjust the valuation of the already placed cottage so as to make it equal to the valuation that it gets during placement (=cottage + town).

Since this is potentially a big deal, I wanted to get feedback and ideas from all of you:

- Do you see any other simple change which could fix this flipping?
- Do you see any reason not to change this?
- What potential side-effects might there be?

1) no this change seems to be the most logical one
2)... nope
3) If present valuations were balanced around the undervalued cottage (when already placed on the map), then some replacement wouldn't happen when needed. Farm chains are of course the most interesting one. So check whether the AI values food high enough and notices the value of chain irrigating that corn tile.

Two inquiries:

-Are all tile improvements in all the parts of the code adjusted for civic and tech effects?
-Are special tile enhancements due to random events taken into account in both the before and after improvement calculations?

And again:

 

[Roland Johansen]

Of interest that in the current system, the AI will want to build cities in the "best" spot nearby. Then if that spot has no other legal improvements (inland green, say), it will let it grow. If it grows enough, when farming is legal, it will resist turning into farms.

I had heard that the AI would value food higher when the city was suffering food shortages. Would that valuation be enough to replace a town with a farm when really needed? I've seen the AI tear down towns, so I guess it sometimes thinks farms are better than towns.

 

[PieceOfMind]

Looks like a big breakthrough! Well spotted jdog

If all goes well, you could use this as one of the strongest selling points of Better AI, and gosh.. human players might even be able to automate works with <gasp> "workers leave old improvements" unchecked! That might be wishful thinking though.

If I get a bit of time I might take a look at this code as well and see if I agree with the proposed change. I find it a lot harder to interpret formulas when they're in code form like this, so I might have to get the pen and paper out, and translate into a more readable lanugage.

 

[Maniac]

You could have the AI consider how long it will take for the improvement to upgrade to town. Might become too complex though.

 

[PieceOfMind]

You could have the AI consider how long it will take for the improvement to upgrade to town. Might become too complex though.

It's a good point. At the moment the town upgrade could take 300 turns but the AI would still weigh in its value when considering a cottage. I'm not sure what a good compromise would be though.

I do think it's kind of important though. At one point I wanted to mod in an improvement that was an upgrade of a town (a metro) and it would take 90 turns or so to upgrade from a town.

 

[Maniac]

Even for the unmodded game, it could improve the AI: building cottages becomes less attractive in the endgame when there are fewer turns left.

 

[Yakk]

You could have the AI consider how long it will take for the improvement to upgrade to town. Might become too complex though.

*nod*, that involves future discounting. Adding something like a future discount curve is probably a good idea in an AI -- to reflect moving between long-term planning and short-term panic, or even to distinguish between leader personalities (some leaders will go short-term during war, others might not)...

But the AI is pretty far away from that point.

 

[Maniac]

I assumed it could be a simple rule of thumb like: a benefit in sixty turns is half as valuable as a benefit now.
The real problem is finding out if that sixty turns is in fact an accurate estimate.

 

[r_rolo1]

I agree with Maniac and Piece of Mind that improvements that get better with time should have some kind of rule of thumb regarding the usefulness of the improvement compared with other more imediate alternatives. But going hardcore with rule of thumb... well, complicated. Not only because the diferent game speeds, but also because, picking the cottage, you don't magically go from cottage to town... you have the hamlet and the village in between and it is not rare that the "cottage" will spend more time in this intermediate states than in the both extremes combined ( this will apply to other modded improvements that also mature or rot ). But calling the XML to check the values and make a average everytime you think on building a cottage would be , at least, extremely taxing ....

 

[The_Reckoning]

Do they take into account Civics? US/FS/Emancipation cottages are worth a lot more in the long term than other options, and CS/SP post-Chemistry workshops are worth a lot more than otherwise.

 

[jdog5000]

Yes, civics are taken into account.

 

[ecc]

I'll be ecstatic when you release the next version. I use automated workers and usually at half point in the game is where an infinite loop of cottage to workshop to cottage change starts taking place on the tiles in my cities. It's a real PITA and hope something can be done to remedy it, thanks jdogg

 

[Lone Wolf]

. I use automated workers and usually at half point in the game is where an infinite loop of cottage to workshop to cottage change starts taking place on the tiles in my cities. It's a real PITA

Turn the "Automated Workers Leave Old Improvements" option on.

 

[ecc]

Turn the "Automated Workers Leave Old Improvements" option on.

Well yes that is an option but will at a point become a limitation. If the old improvements are never updated to better improvements as new technology comes along than it keeps me behind. So the only way around that is to manually use the workers which is what I'm trying to avoid to begin with.

 

[jdog5000]

It happens to the AI too ... or did

Not sure when I'll have the next BBAI version up with this fix, but it makes a noticeable difference to the AI. Going to put together another UP first, then obviously include that in BBAI. Next weekend maybe.

 

[Poppis]

This sounds amazing.

 

[snipperrabbit!!]

I think an AI "cottage decision" must take into account the end game turn too.

 

[Bezhukov]

The big problem is that cottages/workshops are both suboptimal choices once one hits the midgame, where lumbermills beat both (trade routes give all the commerce you need). But, of course, at that stage, the AI has already chopped all its forests.

Hug those trees - disable AI chopping now!