Monday, June 29, 2015

Complex Game AI for Turn-based Strategy Games


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



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!


No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...