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.
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!