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:
- AI that thinks in 'Levels' about strategy,
from very high level down to small details. This is an Hierarchical
approach
- Levels will go from very abstract
pictures of the world at high levels, down to pretty accurate copies
of the world, for small things
- Corrections will be made in the higher
level AI to incorporate information from the more detailed AI levels
below it
- As much as possible, design the world
models in the game so they are easier for the AI to handle
- Use good rules-of-thumb (heuristics)
as a firm base for AI actions
- As much as possible evolve unique
strategies Beyond the heuristics using Genetic Algorithms
- Test AI strategies as much as possible
using Monte Carlo techniques (copy the world as that AI sees it; how
does the strategy play out in the copies?)
- Threaded AI that can take advantage
of any time not used by the world model and the interface
- Allow the player to give the AIs any
arbitrary advantages that they deem necessary
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 real politic 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 merely 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.
(To learn more about
this topic, click here) |
