General AI

[jgr]

Ayup. As the latest recruit I will be looking at coding and general AI work with Mark.

This thread is for the discussion around AI implementation and modelling. I expect a degree of crossover with the military model as this sets a lot of the context. I will do my best to keep the discussions separate!

[jgr]

This is a summary of the thought processes in designing an engine to implement the AI for Clash.

High level military principles for the AI will be taken from the US military doctrine manuals and can be found summarised in
several games including M1 Tank Platoon II, F22 TAW and Eastern Front II. I believe that these principles are good for any historical period.

At its most simplistic, any plan must be:

(a) directed towards a specific goal
(b) achievable
(c) sensible, unnecessary risk should be avoided
(d) follow some basic rules

There are three levels of planning and action. A grand strategic level where policies are formed to achieve
long term plans (the 100 move plan). A strategic plan will set medium term goals (the 30 move plan) and the
third level deals with immediate tactical levels.

Each level is not followed sequentially, but should be thought of as providing environment in which each set
of rules is made. Each level above provides a default for the levels below.

At the top most level, the grand strategic plan must decide on how the country will develop. It must choose
between Expansionism or Neutrality. That Neutrality may be strictly neutral as Switzerland or it could be a
more defensive neutrality like Sweden. Expansionism is furthered by
Military, Economic or Political actions. Using one of these techniques does not exclude the use of the other
means.

If possible, the same techniques and basic algorithms will be applied to all three levels.

A key point about a genetic algorithm is that it requires enough data to be able to tell whether the solutions
that it is generating are converging to "good" solutions. This means we need to know what a good solution is
in the context of planning a grand strategy. This may be a problem. How can you tell whether your grand
strategy is a good one? It seems initially that the only way of defining the grand strategy is to use heuristics
and rules.

However it would be nice to perform some sensible analysis for all levels. A possible equation for expressing
the grand strategy is an optimisation of the following factors:

(M,E,P,I)

Where:

M = military
E = economic
P = political
I = strategic factors

For the strategic and tactical evaluation we can say that the military factors expand out into:

M = (U + S + T) +C

Where

M = all military units and support
U = unit
S = supply
T = transport
C = command


I is the "sum" of the factors that can be used to evaluate the "soft" components of a solution.

I = S + W + O + T

This is virtually identical to the standard SWOT analysis used in business. It looks at the strengths,
weaknesses, opportunities, and threats of a given situation. In political or military terms we still have to do the
same kind of analysis, not just for any economic planning. How far this can be taken remains to be seen, but it
seems a reasonable start point.

For our analysis the factors are:

S = strengths, apply greatest strength against biggest threat, or if no threat, then in a way giving best advantage
W = minimise our weaknesses when viewed against their strengths
O = what are the best opportunities to exploit assuming our success
T = minimise their opportunities to exploit assuming a failure

At the tactical level the expression is a purely military one and the economic and political factors disappear, so
we are left with trying to optimise:

(M,I)

The forces involved in any planning have to obey the following constraint:

Total forces = Home defence + Foreign assignments + Trade routes + Independent units

There is a slight problem with GA when trying to apply them to the problem of assessing military planning.
For a Genetic Algorithm based solution a framework needs to be in place that restricts the solution space to
one that can be analysed for "goodness" so that the algorithm knows when it converging on a solution. The
planning required for either the strategic or tactical levels tries to bring together a relatively large number of
factors, many of which are independent. This makes it difficult to perform meaningful analysis by looking at
all the facts as a group. However, the more simplistic nature of the military problem means that it may still be
possible to do analysis effectively.

There seem to be three ways of approaching the problem. (a) The component parts of the problem are
analysed and optimised separately. (b) A two stage operation for any military planning and action can be
implemented. A set of plans are created and then analysed as a group to find the "best". (c) Alternatively,
plans can be generated and analysed on the fly and the first plan passing acceptance criteria will be used.

I think this crosses over with some of the Miltary model thinking but I needed to create some background. After a few iterations it is still not clear about the best way of implementing an AI engine, so experiment is definitely in order in this area.

I hope what I am trying to do is clear, even if the text doesn't always make sense! I tried to relate general planning issues at all levels with how these may be evaluated using a GA based solution.

[Mark_Everson]

Jgr:

An official welcome to the forums, and the project!

Thanks for moving the ball forward on this! We also need to get you an official title, and work up a web page for the clash site. Are you interested in working up something that combines the stuff you have here, and my old page on Hierarchical AI? Either a Word document or HTML should be fine. Let me know if you're interested in doing that...

I think we also need some more introduction to this thread. Although this thread is mostly for us to talk shop on AI issues, it would be good if people who are interested but don't know the background, had a way to get up to speed. For those of you who feel like you have just jumped into the deep end, the old Hierarchical AI page may help you get your bearings.

And now on to what you say in your post.

You say that you're not sure how to evaluate the success of a long-term strategy. I think really the only way to do it is like I suggested in my old Hierarchical AI post. Even though there are dangers to playing off a proposed strategy against a bunch of guesses of opponents strategies, I don't see that we have any other good alternative. I also personally think that we will be able to get away with it, although not without a lot of work and adaptation. But if we can get a good set of heuristics, and a good very simple world model in which to play out the long-term strategies, I think we can be fairly successful. This approach also has one huge advantage to what is conventionally done with simple rules for AI in games. It can take advantage of any amount of time the player gives it. Also we can avoid the problem of population lock-in to particular sets of strategies by starting several populations from scratch, and playing the winner of each "semifinal" against each other. When the AI players save their plans from a particular session for reference, we will need to be sure to weight the fitness of plans not only by their absolute fitness against other strategies, but by their diversity.

I would characterize the grand strategic choices as much larger than simply expansionism or neutrality. But I'm sure we can fill in the gaps on that one as soon as we start work.

On the pure military problems, again I don't think it's quite as tough as you painted it. At least until you get down to the essentially tactical level of which armies moving exactly where. At the "strategic" level of which forces to operate on which fronts, I think of very simple world picture where all the armies on each front are aggregated into a big stack of military power will be able to get approximate answers in a reasonable amount of time.

I agree with you that I think most of the problems are amenable to similar Sorts of solutions, although obviously the "cartoon" of the world they are dealing with it won't be the same in any way.

[jgr]

I will revisit the Hierarchical AI and pull the suggestions in there into this thread.

I find am not completely clear on how the AI will be implemented in some areas. Some areas are more amenable to computerisation than others, for example, the military action control is more mechanistic than the grand strategic planning. The former is much more suited to rules and possibly some fuzzy stuff, whilst the latter is quite hard to evaluate using any technique. The main problem with grand strategy is that you have to do a lot of guessing. (More on this later)

I reckon that your comments about the grand strategy having to be simplified and subject to heuristics is about right.

Before I start work on the military action coding for the demo it would help me to have the big picture in my head. I will take the Hierarchical AI points and generate a list of typical AI requirements within the game and how they might be approached.

I still have a problem with how best to use the GA to evaluate plans. It looks like the middle tier of planning is the most appropriate place. There may have to be some bending or simplification as well.

The examples I have seen use very specific problems, often as an equation, where you use the GA to iteratively evaluate the factors of the equation. Because you know the "answer" to the equation, you can test each generation to see how well it is doing and therefore choose the best chromosomes to generate the next generation. For the military planning you can' reduce the problem to an equation (although I made a half-assed attempt to do so) but if you bend the thinking a little I feel there may be still scope for some kind of comparative assessment.

I am going to try and break comments into threads as there are several discussions here:

How to treat grand strategy, strategic planning and tactical planning. Reevaluating plans. Modifying plans. Then there is not just the problem of how to do it, but how to implement it. 8-)

[Mark_Everson]

John:

Let me give you a very broad-brushstroke view of how I think virtually every level in the AI can work. I believe this approach can work for everything except the top few levels of very broad overall strategy. I have specific models in mind, and/or on paper for virtually all of them, but I don't think going through the specific ones would be of value here. Here's how each level of the AI works.

1. Strategy to guide this level comes down from above
2. Rules are used to generate an alternative series of possible best ways to execute the strategy (the number tested depends on processing time). Alternative counter-strategies based on knowledge of the enemy are also formulated (we can cheat on this if absolutely necessary, although I would prefer not to)
3. As much as possible our alternative best strategies are tested against good enemy strategies. This is Not done as a simple mathematical equation, but is rather played out in a simplified world model that we think can capture is the Essence of what is important for this level. So it is through simulation, rather than calculation that I hope to capture the interaction of different strategies by competing civs.
4. At this point, if it's required that we stop, we just pick from the best indicated strategies. If there is extra time there is a large variety of things that can be done. The one that I think is most attractive, is to encode the strategies as as individuals in a population of a genetic algorithm approach. We then pursue more simulations as in 3, but while tweaking the strategies through mutation and crossover. If the rule-based approach can give us any hints as to which are the most productive things to change, the more the better. The chromosomes will not generally contain numbers at all, but contain strategic objects. "Take Berlin", "obtain alliance against the Greeks". A mutation in the strategy might be something like "it would be nice to get an alliance against the Greeks, but it isn't that essential", or "it's Imperative". I'm not sufficiently foolish to think that this approach will very frequently give an answer better than the rule-based approach. However, it has the potential to break the AI out of the rut of always doing "predictable" things.

The hierarchical AI is used to form a bucket brigade for the strategies being considered. The higher strategic thought pours down from "above" (that is the higher level models). We assume in each model that the level above knows what it's doing. Just like the Captain follows the Colonel's orders in an army. However, the Captain knows the situation on the ground, and will occasionally ring up the Colonel and ask them to reconsider if things seem especially ill-advised. When the Captain has done his calculations about how best to achieve the result assigned to him by the Colonel, he then passes his plan down to those below him in the chain of command.

I have to go in just a few minutes, so I'll just say a few other potentially useful things. There is a fairly large literature on co-evolving populations using genetic algorithms, similar to what happens in natural selection. That is the literature you need to look at, not the little toy problems were people use GAs to solve "known problems" with well-defined functional solutions.

[Kull]

jgr: We've added an "AI Model" page to the Web Site. You too now have a "home"

[jgr]

Thanks, Kull, its good to have a home. 8-)

Mark, I hear what you are saying, and I agree with some of it(!)

I don't agree that any equation would be simple. It may be a simple expression, but each term could expand to be a more complicated term in its own right. I missed out a lot of summation symbols, for example!

I do agree that the hierarchy is very desirable, so that it would model a realistic chain of command. I also think that each unit should have a degree of autonomy, as well as fitting in to that chain of command.

One of the things that you do as a human player when evaluating a situation is to make plans using basic rules and Intelligence about the opposition's possible moves. These are then analysed and a "best" plan selected. This "best" plan is the one we feel is the strongest in terms of achieving the current goal, usually with the least risk. We often bring an element of our own personalities to this plan. Some prefer to take risks, others are more innovative but not risky, yet others are more predictable, etc. This is played through until it is shown to be wrong, with a capital "W", or it is successful. When simulating this behaviour with the AI, the rules bit is OK, and so is the guessing of the opposition position, because we are just applying the same rules with the enemy point of view.

The part that is more grey is how best to apply the GA approach. This seems to be best applied when carrying out the plan analysis. I originally thought that this could be achieved by ANNs but I reckon that these are too CPU intensive and they need to be trained. I feel that this poses problems for non-deterministic situations when you are trying to provide a real-time analysis.

Do you have a site reference for the GA material you are suggesting? I have only found sites which contain what I thought were fairly limited examples, so my understanding may be incomplete. From the data I have it seems to be a fact that you need to have a fairly constrained problem to solve before it works. This is patently not true when you are trying to analyse strategic problems, where you have a large number of degrees of freedom and the relationship between the different factors is loose or non-existant.

[Mark_Everson]

Kull & Dominic:

Thanks Much!

Jgr:

I looked around a little in my bookmarks, and didn't find anything Really useful in terms of co-evolving genetic algorithm systems. I'll try and look around some more today. However, you can probably get a ways if you just do searches including coevol* and the hyphenated version. Another approach is to start at the "genetic algorithms archive" on the Web, and just look at say the descriptions that the groups use of themselves. After a little poking around I'm sure you will be able to find something.

I basically agree with everything else you said. I do want to stress that although humans may tend to appraise their strategy at relatively sparse intervals, I think we need to try and do it a little more frequently with the AI strategies. That's just because the human ones have a lot more thought in them than the AI ones will, and are less likely to be moderately disastrous IMO

[This message has been edited by Mark_Everson (edited January 20, 2000).]

[Mark_Everson]

Here's some stuff that may be of use...
http://www.natural-selection.com/has has some relevant publications on military
strategy that can be requested by email. Follow the links to publications.
The specific papers I haven't mind are "Evolution of Intelligently
Interactive Behaviors for Simulated Forces" and Evolving Integrated
Low-Level Behaviors into Intelligently Interactive Simulated Forces".
http://www.santafe.edu/sfi/publicati...ng-papers.html has a list of a
huge number of papers published by the Santa Fe Institute.I haven't had a
chance to go through all of these, but you might look through them for
attractive appearing titles. I think all the papers are available for
download in one format or another.
http://www.cs.cmu.edu/Groups/AI/html...netic/top.html is the genetic
algorithm FAQ I was talking about before.
http://gal4.ge.uiuc.edu/cgi-bin/orde....html&cart_id= appears to have some useful stuff on parallel genetic algorithms.

[This message has been edited by Mark_Everson (edited January 20, 2000).]

[jgr]

Thanks for the references Mark.

I did some digging myself and found some good, well documented, libraries at MIT and Michigan State. I am now studying the material.

[Mark_Everson]

jgr:

Great! Sorry the stuff I came up with was of limited use . Can you keep track of some of the better links, so that they can be put on the AI page?

By the way, you may not have seen the Demo 5 call to arms. Basically I need your best guess as to what you might be able to work up within the next month that we could include. Please let me know what you think after you had a chance to reflect on it. Just look for the thread that starts with "Demo 5 Attn".

[Kull]

jgr: By all means, send me the links so I can add them to your Model page!

[TheLimey]

I posted this in the CtP2 Suggestions forum, but I believe it might have some value here... although certain concepts are applicable, since the game is partially strategic and partially tactical.

I do hope you look to go with a fuzzy logic scripting system, interpreted as hints by the actual AI code. It worked very well in CtP1, although they didn't go far enough.

===

While I do understand some of the underlying principals of AI design, I guess what I know in a total way is very minimal indeed. I have nothing but respect for a good AI, and its programmer, for this reason.

As far as I tell, the CtP1 AI was a form of list processing. The AIP and FLI files were the parsed files that were conditionally processed, producing weighted answers as to what should happen. The results were
‘hints’ to the games AI dll, as to what should be done.

There are two main challenges that the new AI has to meet.

First is its obligation to pose as an effective threat to the player, by doing three things militarily; first building good stacks, second put those stacks on transport, or many transports (and reconstitute the stack at the other end) and lastly attack with those stacks. The only way that the AI was TRULY effective (at least overseas) was as a nuisance, by employing special unit attacks. The reason for this, is that one special unit can be effective. However, grouping was never a thing it did very well at.

Secondly, newly created units (created by scenario designers) might have a very tough time, since they, unless some thought is put into AI behavior, will be unused by the computer. This ultimately means that certain scenario units could be unnecessarily unbalancing. The way to solve this, of course, is to have enough groupings of behavior where the new units could fit in. Behavior can generally be defined as movement and attack, since you can ‘preempt’ combat and do something ‘clever’ in SLIC or do something during or after movement.

There was the concept of grouping units by type and them having behaviors, in CtP1.

The problem is… that there were not enough groupings for customizing, and the way the units were described was by static tokens… yes?

The archetypal new custom unit in CtP1, which was employable by the user, but not the AI was the cruise missile. It was one shot, offensive… preferably against towns… or carriers, so it should be grouped for best effect, unlike a nuke. Perhaps carried by subs or ships…(not carriers), and not travelling on its own, except to get into position.

The defensive version of this, which I would like to have seen, though for technical reasons (lack of size classes,) it was impossible, is the Anti Aircraft Missile. A one-shot ship or land-carried unit, that would be used in response to threats within its range radius. Of course, certain people might say… this is too specific. Civ is all about abstraction. However, scenario designers should be given freedom to express their ideas in a flexible product. That is ultimately what the culmination of “Civ” should be.

These are two examples, but I can imagine another… a non-attacking, non-settling unit; one that either explores new sea or land territory, or wanders already discovered land or sea, in settled or unsettled regions. With SLIC, these movement patterns could be put to use, in ways that we don’t know now, but I’m certain will have great use later.

The extra or replacement AI unit classes that I am suggesting are:

SINGLE_SHOT_LAND_OFF
SINGLE_SHOT_SEA_OFF
SINGLE_SHOT_AIR_OFF
SINGLE_SHOT_TERROR (nuke)
SINGLE_SHOT_LAND_DEF
SINGLE_SHOT_SEA_DEF
SINGLE_SHOT_AIR_DEF
POWER_PROJECTION_SEA (the carrier, and sub?)
POWER_PROJECTION_AIR (nuclear strike aircraft)
POWER_PROJECTION_LAND (for completeness?)
WANDERER_LAND_EXPLORED_SETTLED
WANDERER_LAND_EXPLORED_UNSETTLED
WANDERER_SEA_EXPLORED_SETTLED
WANDERER_SEA_EXPLORED_UNSETTLED
WANDERER_AIR_EXPLORED_SETTLED
WANDERER_AIR_EXPLORED_UNSETTLED
WANDERER_LAND_UNEXPLORED
WANDERER_SEA_UNEXPLORED
WANDERER_AIR_UNEXPLORED

The problem of the static tokens in the AI file has to be remedied by moving their specification to where the units are defined; units.txt. I understand this is yet another line and flag to be added, and parsed. You could do vertical partitioning of the data, and split the property into another file… something like unitAIdef.txt or whatever. However, its important that if you want to have a customizable game, that you allow specification of a unit as within an AI behavior group.

The next thing to consider is how you want to define the organization of these units. Ultimately what you want to achieve is , say, a number of stacks; some bombard stacks with, for instance, a couple of attackers, and ranged units, and 5 bombard units (this stack would soften up targets for the assault) and some general purpose stacks with 4 strong and resilient attackers and 5 ranged attackers, to attack or perform defense within the empire, and some appropriate defensive stacks for cities. Sea stacks, air stacks and wanderer escort stacks would be yet another case.

You could define the proportions that you would like to see for each AI behavior pattern (aggressive, defensive etc.) and those would be scaled up or down as resources permitted into ‘build plans’ which the AI could carry out, still taking into effect ‘social’ building.

You might set up a text file that was parsed, with ‘descriptions’ of stacks… with incremental sizes and priorities… I.E.

Stack Defensive_Cities 255(all cities… not literatally 255) 10000 (priority)
{
Defensive_Land 1
Ranged_Land 1
}

Stack Offensive_Land_Stack 1 (a single stack to attack is the second priority) 5000 (priority)
{
Offensive_Land 1
Ranged_Land 1
}

Stack Defensive_Cities 255 1000 (third priority is a larger defensive force)
{
Defensive_Land 2
Ranged_Land 2
}

Stack Offensive_Land_Stack 1 (still single stack) 500
{
Offensive_Land 2
Ranged_Land 3
Slaver_Special 1
}

Stack Bombard_Land_Stack 1 450
{
Offensive_Land 2
Bombard_Land 2
}

AND SO ON, AND SO FORTH…


When a priority is met, you can move down the list

Lastly, stacks need to be treated as homogeneous entities in their own right, by the AI; they need to be regrouped after being split up to move past a city or across an ocean in small boats, and re-supplied with reinforcements after being damaged in battle. As new cities are added… perhaps parts of the attacking stack should be split off to constitute a new garrison.

[roquijad]

Hi TheLimey,

I only want you to know Mark will be on vacations (and out of the forums) for the next two weeks, so maybe you won't find a reply to your post until then...

Rodrigo

[Mark_Everson]

TheLimey:

I think some of these suggestions are certainly appropriate to Clash. Currenly we're far from this level of detail, but the ideas should be here when we get down to active work on the AI and Macro/Scripting language stuff.

Any comments on the specific models? Military, Econ, etc.? External feedback is useful since we're sometimes a fairly small group discussing each area . If you're interested the web site is the best place to start.