Complex Game AI for Turn-based Strategy Games

Question

I'm doing some research for a turn-based Strategy game project and looking for good resources on this topic. The game is a typical war game where countries can fight each other, deploy units and have these units move around on a hexagonal tilemap, attack each other, etc.

I'm particularly interested in how the AI of Civilization V is organized! According to Wikipedia the game uses four different AI systems for different layers of the game's AI:

• tactical AI controls individual units
• the operational AI oversees the entire war front
• the strategic AI manages the entire empire
• the grand strategic AI sets long-term goals and determines how to win the game

Conceptually this looks like it makes a lot of sense to achieve a complex AI and it makes me curious to find out about how these different AI systems work (and work together). The tactical AI is probably the most easy to understand since it handles the decision-making for a single unit (move, attack, repair, retreat, etc.) but I think the other AI systems are where it really gets interesting. For example what does the operational AI do and how does it do that? I'm sure these are best-kept secrets by Firaxis Games but it would be cool to get some discussion started on this to find out more about it.

Also if anyone knows any good books that handle turn-based strategy game AI it would be great to know. Obviously this is a sparsely seeded topic on the web. I got "Programming Game AI by Example" but that book is more about single agent behavior AI than high-level goal-oriented AI.

Answer 1

Whilst I agree with DampeS8N's opening paragraph (i.e. game AI only needs to be smart enough to make the player think that it's smart), I feel that this question needs a little more elaboration. The data structures in use could be FSMs for all levels, but that doesn't really answer the question as to how the individual systems work.

Disclaimer: I have hardly played the Civilization games so my understanding of the gameplay is limited. If there are any obvious errors, I do apologise. Please correct me, and I'll gladly edit.

I'll be taking quotes from the original IGN Article.

1. Tactical AI

At the lowest level, the tactical AI uses the forces at hand to win a battle on a local scale.

This is probably the most standard part of the subsystem. There are limitless ways to carry this out from using FSMs, Behaviour Trees (or even performing random actions, depending on the difficulty of the AI).

However, since this is a turn based game, similar to Risk, I think what is more likely happening is that each unit is assigned a score. There are then multipliers attached to this score depending on different variables (allegiances, terrain bonuses, etc).

The outcome is then calculated by something like this:

If (AI unit score >> (much greater) enemy unit score) Then Completely destroy enemy unit
If (AI unit score > (somewhat greater) enemy unit score) Then Partially destroy enemy unit
If (AI unit score < (somewhat less) enemy unit score) Then Partially destroy AI unit
If (AI unit score << (much less) enemy unit score) Then Completely destroy AI unit

It makes sense that the AI will try and maximize this score when in battle.

Add in an epsilon value (e.g. small random chance of failure/success) and you've got a pretty decent looking AI (no one wants a perfect opponent, that's just not fun!).

2. Operational AI

One step up from that, the operational AI picks which battles to fight and makes sure that the necessary forces are available.

I think there are a couple of points to this:

• Evaluating current strength
• Reinforcement of units
• Evaluating which fights to pick/avoid

Evaluating Current Strength - This just screams Influence Map to me. It can be easily represented on a hex grid. As this subsystem is combat oriented, the influence values can be representative of the strength values of each unit in the vicinity. If you have a massive army focused in a small area of hexagons, the influence value will be huge and the operational AI will take this into account when evaluating fights to pick. Don't forget, the influence values of opposing armies will also be calculated. This allows the operational AI to predict potential incoming threats.

Reinforcements of units - By receiving information on opposing factions from the influence map, the AI can determine which units are under the most threat. The AI can then issue a command to close-by units to go and reinforce the threatened parties.

Evaluating which fights to pick/avoid - A couple of situations can occur here. If the AI detects a unit is under threat AND there are no nearby units to help it could a) decide to sacrifice the unit (if they're just lowly infantry, instead of an irreplaceable general, for example) or b) Order the unit to retreat. Conversely, if the AI detects a weak enemy unit near an army, it could order the units to take this enemy out.

Here's a decent paper that makes use of influence maps in Real Time Strategy games.

3. Strategic AI

Moving even higher, the strategic AI manages the empire as a whole, focusing on where to build cities and what to do with them.

"Where should I build a city?" just sounds like position evaluation. Chess programs and other games use it to determine the desirability of a given position. For example:

Hex A: Close to resources, on high terrain, close to allies, close to enemy Hex B: Far from resources, on mid level terrain, medium distance from allies, far from enemy

The position evaluation function could take these three factors like so:

Score = Proximity to resources (closer yields a higher score) + 
terrain elevation (higher yields higher score) + 
proximity to allies (closer is better) + 
proximity to enemies (farther is better)

And whichever hexagon has the higher score, will be where the city is built. More information on evaluation functions can be found here.

I reckon the strategic AI also has a bunch of pseudo-prebaked strategies in the game depending on the type of victory the AI is going for.

4. Grand Strategic AI

At the top of the ladder is the grand strategic AI, which decides how to win the game.

I think this is probably the simplest of the bunch, and it gives the impression that it's more impressive than it really is. In a game such as this, there will only be a finite number of victory types. The article mentions a Conquest victory, assuming that there are also Alliance victories, etc, it could be as simple as randomly picking one of the types and then pass it onto the other systems.

EDIT: Of course as pointed out by DampeS8N, the type of map could dictate the best victory condition to go for, in which case it could be hardcoded by the designers or some sort of evaluation function factoring in different variables.

Summary
I think what's really important to note about this kind of system is that the way the subsystems are layered, they don't actually need to be communicating a great deal with eachother. It looks to be a top-down architecture with the components loosely coupled. From a technical design point-of-view it's clean and it's flexible and probably takes its inspiration from Emergent Behaviour and/or the Subsumption Architecture.

I really do apologise for the length of this post, it's turned into a bit of a beast :(

Either way, I hope it helps!

Answer 2

In general AI in games shouldn't be thought of as 'complex' it is all about getting what you want with the least possible effort. The name of the game is Emergence.

In this case, your fundamental conceptualization is wrong. These 4 systems do not need to work together at all. They just need to look like they do. They can also be a lot more stripped down than you think they need to be.

You've also reversed the order of difficulty. The hardest component of Civ AI is the tactical AI, followed closely by the Operational. Strategic is probably very simple, and the grand AI is probably simpler still.

Communication between components is more like a system of grunts and less like real communication. From high level to low level it would look like this:

Grand AI

assess the state of the map. Given the knowledge the AI has (which could be everything or only what it would have if it was a player) it decides what end goal is fastest to reach. It is likely a Finite-state machine that does some number crunching and picks a goal. Possibly it is something more exotic; a Genetic Algorithm or possibly a Bayesian based doohickey. It then grunts down a message like "more science."

Strat AI

then looks at what it has available to work with using much of the same information. It goes about trying to meet that overall goal, but also worries about more detailed aspects of the game. Am I at war? Do I have starving people? so on. It is probably also a Finite-state machine, possibly Fuzzy Logic (which is really just an evolution on an FSM.) Let's assume it is a simple FSM. It will ask the above questions in an order where, given certain criteria, it will decide different things need to happen this round. I'm at war, allocate monies for training soldiers. My people are starving, build a granary here rather than building something sciencey.

Picking what units to build might be part of Strat AI or Op AI depending on how we are splitting things up.

Op AI

will take the units that are available and will assign them to move into different fronts of war. It will decide the overall shape of the conflict, where new units will head once they are deployed. It is probably also an FSM. It may notice that the enemy on Front A is attacking with units weak against Unit B, and will send more Unit Bs there, rather than to the other Front which is strong against Unit B. It will issue general orders to the units at large. Attack at will. Retreat. So on.

Tactical AI

is unit specific. Each type of unit will react differently to the general order. A unit that is intended to suicide, may ignore a retreat order. Units that are wusses might retreat even when told to fight. Civ is typically very light on this kind of thing. Generally all the units in Civ follow their commands. Given the larger order they are under, they are (see a pattern here?) an FSM. Am I injured? I should back out and heal up. Do I have an advantage in this location? Attack. Am I too close to attack? Back off. And the complexity of this FSM need not be much more than those 3 things to be effective and convincing as intelligent.

Can this be enhanced?

Yes, of course. The question is if the players will notice. And 99% of the time they will not.

Now, this is all decision making AI. There are other AI subsystems at play here. There is A* or some other path-finding algorithm that lets units find the shortest path to a location. There are algorithms for finding the best location to start new cities. So on. There are often grouped with AI, and often are really more complex then the 'thinking' part of the AI. In fact, the code for finding the answers to the questions the FSM needs to ask is often orders of magnitude more complex than the FSM itself. How exactly does one decide that