The Clash of Civilizations 

AI in Clash - an Overview

Goals for the Clash AI are to give the player as challenging a game as they would ever want.  To achieve this we will have:


 The reason I started Clash was because the AI in Civ-type games is, IMHO, incredibly poor.  I realize that writing really good AI for such a game is extremely difficult.  However, at least in the many games of this type that I've played, the AI's reasoning usually has such big holes in it that you can drive a tank through it ;-)  I've thought a lot about how I would do the AI for such a game.  I'll lay out the framework that I plan into use here so that people can comment upon it, criticize it, or whatever.  I plan to do an hierarchical AI with several different levels. My approach is one of using an hierarchical AI continuously thinking about strategies in the background. There will be AI that thinks about extremely long-term things like how to get to industrialization from the middle ages, then at a "lower level" long term alliances and military strength, then shorter-term diplomacy, then attack staging… In this page I'm going to talk about the hierarchical AI framework I envision for Clash in general. I'm not going to talk in detail but what each level actually does, since: (1) this would then be 38 pages long; and (2) I don't even have all the details worked out yet. A later bit will focus down on the specifics of the diplomatic/military "realpolitic" AI as an example.  I'm very interested in hearing what people think about this approach.  I have seen mention of the idea of hierarchical AI in newsgroups and on the web, and can't claim it as my own.  A good summary that is still available can be found at:
http://www-cs-students.stanford.edu/~amitp/Articles/HierarchalAI.html

 I think that the AI should be hierarchical in games like this.  By hierarchical I mean that there must be an AI in charge of each level of thinking for each computer player of the game.  It's not necessary that the levels exactly duplicate what a typical human does in playing such a game, although I'm going to take that as my starting point. What I think most people do in a civ-type game is to think of things in several levels going all the way from overall strategy for winning (e.g. win the tech race and then engage in high-tech conquest) down to the military strategy for a particular battle.  The top-level in the AI hierarchy I'll call overall strategy. The overall strategy will probably be selected at the beginning of the game, and not changed unless the present strategy is clearly a complete failure.  The specific choice of overall strategy (e.g. high-tech conquest) will shape every decision every lower level of AI makes. This is roughly analogous to the chain of command in an army.  The commander-in-chief's overall goals guide the chief-of-staff's decisions, and so on through generals down to privates.  There is another analogy to the chain-of-command that I'd like to stress at this early point; not only do commands flow down the chain, information also flows up it.  In the sense of the AI hierarchy, I envision a module one level higher will have both a broader scope, and necessarily, a more crude picture of the world than the one below it.  The flow of information up the chain will attempt to prevent the higher level AI's making a poor decision based upon the incomplete information contained in its limited world-view.  I'll give an example of this later when I get into specifics.

I want to elaborate on a little is the point on "As much as possible, design the world models in the game so they are easier for the AI to handle" before moving on.  What I mean by this is that we try to avoid Really Sharp boundaries in the results our design elements can generate.  This would happen if when you do something just a little differently the result can change dramatically.  One example I could use from Civ2 is the more powerful wonders.  You either get them or you don't, and they can have far-reaching effects in gameplay.  A small difference in the rate of building a wonder can bring you from successfully building it, to getting beaten in the race.  Now Clash Will have this sort of thing anyway from things like who wins the big battle...  but IMO we should look for these elements in all the design models and try and get rid of as many of them as possible.  Anything that gives a big advantage should either be transient, or have a compensating downside.  (F.e. Democracy is great for tech... but there are limits to who you can declare war on etc.)

Hierarchical AI specifics

This figure briefly illustrates the flow of orders (down the chain) and information (up).  I talk about the details of some of these later.

1. overall strategy (e.g. high-tech conquest)

.............\/  "orders" flow down, e.g. maximize technological progress and cultural cohesion

2. 100-turn strategy (University; homogenize culture; Gun Powder...)

.............\/  orders....................^  information flows up (e.g. on military threats)

3. 10-turn realpolitic strategy [includes diplomacy, military build-up, economic development...]
............\/.....^.................................................\/.....^.....................................\/...^
4a. overall military (<10 turn)...............4b. Diplomatic AI..................4c.  economic AI
......apportions forces.................................implements............................implements
......between fronts…timing…....................diplomatic recipe…...............econ recipe
............\/.....^
5a. military theater AI (< 5 turn) given assigned resources
what specific attacks/ threats/ defensive strategies should be used on this particular front?
............\/.....^
6a. attack/defense AI (< 5 turn) make each att./def. achieve its goal
............\/.....^
7a. specific objectives ( 1-2 turn ) implement attack/def. On a turn-by turn basis

 To avoid losing parts of the audience at this point I think I need to interrupt the flow to discuss a few details.  As in any strategic game involving many players, each of whom has a multitude of potential actions, the search space the AI needs to examine in Clash is utterly enormous.  I'm trying to reduce the size of the problem to be mearly daunting.  The main tool accomplishing this is that as you get higher in the AI level the world gets increasingly more abstract.  So, in this framework, there is no AI that tries to control all the military units, economic planning, etc. directly. Since the search space is pruned down at each level things will, I hope, stay manageable (more details about this later ;) .   To aid in this we need to have our game models be 'scalable' as much as possible.  Scalable in this context means that the model for handling the detailed effects in the game model can also be scaled up to cover a broader swath of geography or time.  For instance, if the combat model can estimate the combat result for a whole military front/theater with a single simple calculation it will be much easier for us to get correct information on high-level what-if questions regarding a potential war.  However, even with things incredibly simplified, there are a lot of choices to be made by the AI. Fortunately, in a turn-based game there are usually a lot of spare clock cycles running around the can be used for the AI to think.  The key, I believe, is to use an AI mechanism that can easily be put on hold.
 One AI technique that I think satisfies this criterion is the genetic algorithm.  In a genetic algorithm approach, solutions to a problem are "evolved" by combining pieces of promising-looking solutions. The feature that makes this method easy to put "on ice" is that by retaining the few most promising solutions from a previous run you can essentially re-start where you were before.  I don't want to turn this posting into a lecture on AI, so I'll make a few quick points and then move back to the main topic. Genetic algorithms (GAs) are generally slow to converge to an optimal solution.  However, GAs can frequently get near a local optimum (a pretty-good solution) fairly quickly.  I think this will be adequate for a game that has a vast search space where most human players will also have strategies near a local optimum.  Another advantage of GAs is that they will hopefully surprise the player more than an heuristic AI will. This is because an heuristic AI essentially walks down a well-defined decision path in the search space, whereas a GA is more like a shotgun blast that will get some lucky hits (in possibly different parts of the search space each time). We shall see if we can demonstrate this advantage as the coding gets further along ;-) .  I can't close this section without trumpeting one further advantage of GAs.  Because of the adjustable GA parameters of population size and number of generations, GAs are easily tunable anywhere in the range from quick-and-dirty to "deep thought".  The player will be able to make the decision of how long they are interested in waiting for the AI.  Additionally, people with hot machines can get super-duper AI "for free".

 Getting back to the main topic, here's an example of chain-of-command effects illustrating how "orders" move down the chain.  Say, technologically we're in the Middle Ages. Our 10-turn term realpolitic AI is pondering whether we should mobilize our military to opportunistically attack a weak neighbor.  To simplify the discussion let's assume the realpolitic AI is only considering two alternatives, "peaceful" vs. "militaristic". If the overall strategy is the "high-tech" one mentioned above, the expected results for the two alternatives will be compared using a yardstick that emphasizes the ability to advance technological progress. Assume, for the moment, that the AI can come up with a set of "typical" results for both the peaceful and militaristic strategy. (I know that this is on the level of... "a miracle occurs".  What happens here is that a set of strategies and other civs' counter-strategies are examined by the GA in a simplified world that is a "stick-figure" model of the game world.)  Whichever result is best in terms of the high-tech yardstick would be selected.  If the neighbor had lots of universities and merchants, both of which help in the tech race, the conquest would be looked upon very favorably.  Alternatively, the neighbor might be very backward, and resistant to our culture ruling them. If taking them into our empire would actually have a retarding effect on our technological progress into the far future, then the realpolitic AI would weight the potential conquest unfavorably.
 We will probably put in by hand a number of what we think are successful overall strategies for use by the AI.  Additional overall strategies could be blends.   Other strategies could be cross-overs between these strategies.  For example, go for size and cultural cohesion until someone undertakes an industrial revolution, and then try to 'modernize' as quickly as possible.  Finally, we can use the game running by itself to develop new overall strategies.  In this type of meta-game variations of overall strategies would be tried through entire games, and then the best ones evolved further in subsequent games.  I don't know how far we can go with this, but its an attractive option.
 When the overall strategy for the game is selected, the level beneath it might be in charge of implementing the overall strategy at a long-term level, say 100 turns or more.  This will be the AI module in charge of the details for the technological and cultural progress of the society.  If we are given an overall strategy of high-tech conquest, which specific technologies and/or features of the culture should our civ try most to achieve, and in which order? (This is an extremely long-term area of strategy to model and unforeseen emergencies will frequently take precedence. ) The 100-turn strategy would consist of several "mile-posts" to be achieved.  One such plan might be paraphrased as: (1) get tech University; (2) invest money to homogenize culture in newly-conquered areas so they are less likely to revolt; (3) get tech Gun Powder; (4) modernize military but keep at same manpower level; and (5) get tech Open-Ocean Ships.  The hundred-turn strategy above, or one like it, will serve as a yardstick to evaluate strategies at lower level in the AI hierarchy. As previously mentioned there will also be information flowing up the AI " chain of command".  The 10-turn strategy model will, however sketchily, "scout out" the presence of military threats in the vicinity or other short-term threats that could destroy the long-term plan.  (To give an example, if there are very serious military threats around, this knowledge will be passed up from the 10-turn AI to the 100-turn AI.  With this information the long-term AI will not consider "scrap-the-army" type solutions, because they will tend to be fatal in such a situation.)
 Below the 100-turn AI in the hierarchy is the realpolitic AI. The crucial job of a Civ's realpolitik AI is to put it into as advantageous a position as possible with regard to its rivals.  This AI will look ahead 5-30 turns for opportunities and threats on the diplomatic, military, social (e.g. revolts) and economic fronts.  For a militarily aggressive power this means diplomatically isolating smaller powers so that they can be conquered one at a time.  (The smaller powers will of course realize what is going on and will tend to unite to defend themselves) Another attractive possibility is taking out a powerful adversary while he's down due to a revolt or other calamity. For more peaceful powers (or aggressive but realistic small powers) the object of diplomacy is to make peace with everyone, buying time to grow by peaceful expansion or economic/technological advancement.  Failing total peace they will generally attempt to form a defensive coalition that contains as much of the local area as possible.
 The primary driver of the realpolitic AI is diplomacy.  The military and economic factors that are a backdrop to the diplomacy, and will be handled in a rather sketchy fashion. I think this is a reasonable way to do it.  I'm sure Bismarck didn't wargame all his ideas, he must have relied on only broadly-based advice coming from his generals when plotting diplomatic strategy. The decisions arrived at by the realpolitik AI will be: "what are the desired diplomatic states with various foreign powers?", "what could we pay/demand in territory or treasure for those diplomatic states", and "how important is each of these desired diplomatic states to the overall plan".  It will also be necessary to include conditionals like: declare war on X if we can get an offensive alliance with Y.  These are needed to make the diplomatic plans coming out of the realpolitic AI more flexible.  One job of the "overall military" AI, below the realpolitic one, will be to keep the diplomatic calculations honest in terms there potential military outcomes.

I need to finish this up soon, so I will make some more comments about the Genetic Algorithm techniques used.  If you don't understand GAs, just skimming this part should be enough.

For each level of AI you are doing (more about this later) you will be looking at a Coupled system of  Parallel Populations of GA-generated solutions Fighting It Out. What I mean by parallel populations needs to be explained.  Say we're doing the AI for one military front.  We (A) are at war with B.  One population of the GA will represent our strategies and the other population the strategies for B.  These populations are started using the ideas I'll describe later.  Basically some members of the population are generated by heuristic (basically, rules of thumb), and some "from the ground up" by GA.  To get the fitness for each individual in A (how good a strategy it is) we play it against x individuals in B.  The number of individuals to play against, x, will be determined by experimentation and how many clocks are available.

So we have set of first-generation strategies for A and B that we test against each other. For the strategies for B we make our best guesses based on A's knowledge of Bs forces and general aims.  Just to give a specific example; one strategy in A, call it A1 might be strike at North part of front with half of forces and hold elsewhere with the remainder spread thinly.  This is one of many strategies in the population A.  It will be played against x B strategies.  If we take x=3 we might have: B1 is defense-in-depth; B2 is attack in N; B3 Attack in S.  Now we go to a simulated way of fighting out the battles quickly to get a fitness measurement. You might also do several (y) tries on each battle so one bizarre result doesn't screw it up.

Lets say A's army is twice the size of B's and we award success point to be positive for a Good result for A.  So we fight out the three simulated combats and get the results: A1B1 gives +3; A1B2 gives +1; and A1B3 gives -2 (since they hit us where we're weak and can seriously hurt A even though we'll probably still win the war)  So we now have a fitness for A1 (and part of the fitness of B1-3).  After going through one generation we have evaluated p strategies for each of A and B where p is the population size.  To get estimated fitnesses for these populations we have had to evaluate p*x*y mock battles.  For the next generation we use the fitnesses of the previous generation in the usual way, and generate new populations A' and B'.  When we run out of available time we use the best one, or pick randomly among fairly good ones using some metric.

This method may be somewhat unstable in strategy generation to be perfectly honest, I just don't know yet.  The reason I suspect it may be a problem is that co-evolving populations tend to "lock-in" to each other, each optimizing itself depending on the other population.  The problem comes if B, in the actual battle, uses a strategy unlike what is in our guess at the B strategies.
 However this stuff happens in real life too...  At the beginning of the Battle of France in WWII Anglo-French planners Did Not Believe the Germans could possibly make it through the Ardennes in something under a few weeks, so their plan discounted that possibility.  Anglo-French plans were optimized to the "population" of what the Germans might do other than a Blitzkrieg launched thru the Ardennes.

Anyway if the starting heuristics are pretty good, and we use elitism, the strategies may not be too twitchy.

Now some general thoughts on how to do the GA chromosomes.  A chromosome  here represents a specific strategy handled in the GA framework.

1) I haven't actually Done any of this so it could be Wrong ;-)
2) IMO best way to do the GA in general is to start with good heuristics (guidelines) and rely on the GAs to modify the initial heuristic guesses. In parallel you want to create competely new (non-heuristic) strategies. Finally you compare the "original" strategies with the heuristic ones and their "optimized" forms. The best strategies at the end of this
process win.
3) The GA representation should IMO be generally Object-based, rather than bit-based. This has the cool feature that it is more understandable to us human types...
3a) "Emperor, we have through bribery of the Carthaginian high chancellor obtained their battle plan; here it is: 110000101010010110101011".
3b) "Emperor, we have through bribery of the Carthaginian high chancellor obtained their battle plan; here it is: Fake an attack on Aquilae using 3rd army. When troops have been drawn from Rome to answer it, Attack Rome with 1st 2nd and 4th armies delivered by trireme."
4) A lot of the chromosomes will be fairly large. we will probably need some mechanism to take into account how long the GA has to work its magic, and if that time is not as many clocks as we would like, restrict changes to genes that appear the most important. Perhaps the heuristics can help with this aspect.

Here's a few thoughts on chromosome content for some of the AI levels

1. overall strategy (e.g. high-tech conquest)
Maybe 10 numbers (maybe with a little logic) covering things like: aggressiveness; risk aversion; desired rate of technological progress and cultural cohesion...
Perhaps a few If-then kinda constructions, e.g. if we are much smaller than our neighbors go to this type of strategy which is better for that type of position.
These will be chosen from a list pre-bred by simulated runs of the game

2. 100-turn strategy (University; homogenize culture; Gun Powder...)
This will be maybe 5-10 objects with priorities on the different elements. Genes will consist of desired Technologies; weightings for economic growth and army size, a belligerence level (modifying that in 1) and such.

3. 10-turn realpolitic strategy [includes diplomacy, military build-up, economic development...]

Chromosome will be made up of genes that are mainly desired diplomatic states with various other civs, and how important they are to achieve (One object for each civ in contact with, may be trimmed if too many civs). Will include a factor for whether to mobilize army, short-term economic and internal political decisions

4a. overall military (<10 turn)
Which forces are committed to which fronts. What should their large-scale objectives be? (e.g. attack to take territory, attack to destroy enemy army, scorched-earth defense) Fairly small chrom. involving army group-level apportionment.

4b. Diplomatic AI
Not sure, just "tactical" information on implementation of goals and fallback positions in realpolitik strategy

4c. economic AI
ditto

5a. military theater AI (< 5 turn)
Given assigned resources and goals from 4a what specific attacks/ threats/ defensive strategies should be used on this particular front? This is going to be one of the more difficult ones to implement... And hard to do in a small amount of time. But I think it
can at least do better than conventional game AI that generally doesn't even Consider connections between different military actions...
The chromosomes here will be pretty large and complicated. Attacks can be vs. specific territory or armies directly, or attacks through denial of supplies... defense can be defending specific territories, rolling defenses. Either offensive or defensive armies can support other armies in their missions... So each gene is a Specific Objective carried out with Specific Troops, that needs to meet specific probability-of-success criteria, and sometimes with timing information.

6a. attack/defense AI (< 5 turn) make each att./def. achieve its goal.
Similar in character to 5a. Just at a more detailed level (do we split into two columns as approaching the target city...
At what confidence level of success do we reconsider and go back to 5a.

7a. specific objectives ( 1-2 turn ) implement attack/def. On a turn-by turn basis
Cast plans from 6a into a unit-by-unit action plan. At this level, each Gene is actions of a single unit or army. If plan is FUBAR report this and get a new plan.

Whew. It hurts my brain just to think about how complicated this is. I Strongly feel it can be made to work. It should produce reasonably competent AI that will be less predictable than most of what's in games now. The AI should also sometimes be able to stumble upon brilliant strategies!
 

 Well, if you read this far thanks for sticking with it ;-) My original intention had been to also provide here one or two-paragraph descriptions of the remaining levels of AI in the figure at the top of the page.  For now I think I'll just rely on the very short descriptions in the figure and chromosome descriptions to give you a sense of what they do.  If anyone out there has already tried this sort of setup for a game AI I would love to hear about it.
 



Home   Civilization Advances Chart (133K)   Map AI Screen Shot
 Economy Screen   Economic Development    Gaming/AI Links