AI for global decision-making in 4X games

Question

I understand how things work in combat, but not quite in terms of global decision making.

For example, in Civ, at the global level AI has to juggle multiple objectives, e.g. whether to invest money in constructing Building A in City B, or choosing which tech to research, whether to declare war or offer peace to an opponent, etc.

So my question is, what sort of algorithms are used for this? My guess would be something like Gantt chart or numerical solution for an assignment problem that prioritizes jobs.

EDIT: more specifically,

1. How do I formulate an optimization problem
2. What kind of solution can be used?

For example, a 1) bipartite graph solved by 2) Hungarian method.

Answer 1

There is a reason why the AI in most 4X games is so bad that it can only challenge a moderately experienced player through blatant cheating: AI for 4X games is a really complex issue. It has to handle multiple conflicting priorities. The importance of these priorities depends on a ton of variables, a lot of them with uncertain or unknown values. And the actions to solve those priorities often also have a complexity level that makes it hard to estimate how feasible they actually are.

There is no one algorithm to solve the problem of long-term planning. And those which exist require a lot of game-specific tweaking to enable them to make vaguely plausible decisions within the context of the game they are used in.

But a couple algorithms which can help here are:

• Rule engines. Rule engines are basically long lists of conditions. "IF [I don't have a barrack] AND [I have the resources to build a barrack] THEN [build a barrack]". The simplest way to build a rule engine is basically a function with a ton of if statements. But many games outsource this to a domain-specific language to make it easier for the designers to experiment with the rulesets.
• Goal-oriented action planning. This algorithm picks a goal and then tracks backwards to check what needs to be done to pursue that goal. Example: "I want to capture that enemy city -> I need a unit capable of capturing -> I need a barrack to build such a unit -> I need 250 wood to build a barrack -> I should send a unit to collect wood". This algorithm allows to determine the cost of what it takes to fulfill each goal by adding up the costs of all the steps. This cost calculation can be used to decide which goal to pursue.
• Utility AI. The AI rates its situation based on certain metrics, and then uses a scoring system to decide what to do next. Example: "I am at war: +50 military importance. I have the strongest army: -27 military importance. I am far behind in technology: +43 tech importance. I am slightly ahead in economic development: -3 economy importance. Result: I should invest in technology".
• Machine learning. I don't believe I have actually seen a 4X game yet that does this. But with machine learning being all the rage right now, it might be worth trying to train a neural network to play your game.