 |
| |
|
|
|
Its time for a new round of AI discussions since we're going to try and get the framework going for Demo 6. I'll start this off with a High-Level description of what I have in mind for AI. After that I'll give some links that I think are useful to look over (so I don't always have to say, read thread X  ).
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. (see Hierarchical AI link below for more detail) 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 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.
Links:
The Clash AI Web Page has lots of good stuff. Among them are old discussions and some links on AI.
The Hierarchical AI page has more details on the ideas I sketched out above.
The thread preceeding this one isGeneral AI.
And finally there's the Map AI page on the web site.
Ok, lets get this topic cookin'!
|
|
| |
|
|
LDiCesare
|
|
  |
|
King
Ashes
|
Jan 2001
time: 01:45
| |
|
|
(Moved from Military Model)
How do you get the army you want in place for a given task?
I am supposing you know you want to get attack force to fight a supposed force of X in a given square. The high level AI also knows it must defend some spots. How does it know it can move some units from a previous attack, but shouldn't move units defending a city? Should it build units, and of what kind?
All decisions come down to:
1) What is my ideal units orders/builds for my goal? Ask for that budget.
2) Given a budget, do what I can.
Considering (1/budget), the question is:
Q1) Do I need new armies or can I move around existing ones.
Considering (1) and (2), the question is:
Q2) What units do I need (transports, artillery, infantry???)
For Q1: If timing is considered, we need to know how much time is needed to get an army in place from somewhere, plus how much to build it. How does that relate with econ RoI?
For Q2: Can we give preferred building queues/stacks? For instance, for an attack I want (1 Light cavalry/2 Phalanx/1 Archer) stacks. How do we match the wanted armies and the econ orders (where does the code doing the choices belong)?
|
|
| |
|
|
|
In all games that require a strategic AI, there has not been one that could handle "high-level strategic" situations very well. We all know that an AI can handle raw number crunching brilliantly, whether it's keeping track of objects, or knowing exactly where everything is on the map, but it can't look at a situation and say, "Hmmm..... I want that resource, so I'll build up my attacking army on that front for an invasion in 10 turns. Oh, I'll also need more defenders there to counter his ally."
Here's how I see an AI could work out it's "high-level strategy":
1. 100 turn AI
Generalised main goals of Civ.
- In 100 turns, build 15 new cities.
- In 100 turns, have taken over Civ X.
- In 100 turns, have two allies, Civ Y and Civ Z.
2. 20 turn AI
Intermediate "high-level strategies". Basically, the steps to getting goals in 1 above.
- Must build 3 new cities each 20 turns.
- Ensure border area with Civ X has as many "attacker" units as "defender" units.
- Pay tribute to Civ Y to raise regard/trust. Trade with Civ Z to increase trust.
3. 5 turn AI
Low "high-end strategy" AI which provides the steps to 2 above.
- Build settler in city 5. Build road from city 5 to square (7, 9).
- Move tank brigades from safe front to border area of Civ X ready to push for capital. Upgrade defenders in border area from muskets to rifles.
- Move diplomat from city 2 to Civ Y capital. Trade advisor to authorise "Free-trade" law and reduce tariffs.
Information flows up and down these three AI levels ensuring accurate decisions are made. This is very important when the 5-turn AI comes across a new/changed situation. IE: 5 turn AI picks a tank brigade to move from front A. However, 2 turns later Civ A declares war on us. 5 turn AI then asks the 20 turn AI whether that tank brigade is needed on front A or front X. The 20 turn AI is definite that it must have that resource on front X to build tanks. Consequently it tells 5 turn AI to move the tank brigade to front X. 5 turn AI moves them to front X while trying to hold off civ A with the defenders on front X.
In order for an AI level to make these decisions, it must number crunch (which we know it does very well).
- How many attackers does Civ A have on the front?
- How many defenders do we estimate from spy reports that Civ A has in those 3 cities?
- How many defender points must we have to "hold" Civ A's attackers?
- How many attacker points must we have to take city G?
- etc......
Once all this is worked out, comparing is needed to be done by the AI to work out that 5 tanks and 2 artillery have 80% chance of defeating 3 infantry in city G with wall type 3. Once all the "5 turn goals" are worked out (take city G, siege city U, cover city G-U road to stop reinforcements) it should be simple for the AI to allocate the units on the front based on the priorities worked out.
This is how I invisage the strategic AI functioning. The tactical AI is another matter. Maybe I'll talk about it later.
Comments?
|
|
| |
|
|
Prince
New Zealand
|
Mar 2001
time: 13:45
| |
|
|
Pretty long-range planning here. 100 turns is 500 years.
Cheers
|
|
| |
|
|
|
Hi All:
Lets see what I can address now... Laurent, your post is the big pain, since it asks some tres annoying quesions . But important ones.
Dale: I agree pretty much with what you've written, with the exception that your bit uses civ-specific ideas like "build cities" that aren't really applicable to Clash. (The world will start out fairly populated, there will be relatively few enormous underpopulated areas that civs can mostly freely expand into.)
Laurent:
Well, the short, honest, answer to your group of questions is "I don't know..." as in I haven't got any specific details worked out yet. (That's part of the goal for this thread.) But here are my general thoughts:
First, where does the code go? I think the AI code for each model should be under that model's package in a .ai sub-package, with only farther-reaching AI stuff going in the generic AI package. When there is an overlap of "jursitictions" between the models, we either have a military-economy interface AI, or just have the military and econ AIs figure it out between themselves through questions and answers as I outine in the next paragraph.
For preferred building of queues/stacks, I think the Military strategy object associated with that Command will tell the economy, here is what I want, and when I need it, and where I need it -- Can you provide it, and at what cost. Then it checks against its budget, and if budget isn't enough it considers either recalculating forces needed (estd. of course) or asking for more budget.
In terms of how builds interact with ROI for military units, its not clear they should. If the military needs something and thinks its worth paying for, it can simply buy it, overriding the ROI system. But if Mil AI asks the Econ AI for the cheapest way to get X unit(s) to spot Y by time Z, that answer would figure the cheapest way using probably ROI calculations.
The tradeoffs between using existing forces and building new ones is complicated. But essentially the commanding Mil AI can ask General HQ what the civ's general position is on build vs "use available" and then weigh the criteria. (Or ask another AI to do it).
Realistically, by Demo 6.0 I think we'll only have some crude overall strategic and tactical AI working. I expect the tactical AI would just deal with existing forces and currently planned builds to keep it simple. But we want to have at least some of the architecture for grander things figured out.
|
|
| |
|
|
King
NC, USA
|
Nov 1999
time: 02:45
| |
|
|
Obviously I'm not an AI guru, but it seems that this is one of those areas where the KISS principle applies. I think we should consider a more rudimentary AI, one that follows a few simple rules:
1) Defend valuable spots.
2) Attack weak spots.
3) Conserve resources.
Instead of trying to make it act like a human or a government, maybe we should consider making it act like an animal: existing for the purpose of growing and reproducing.
Obviously long term planning is nice, but an AI that does nothing more than react to situations can be just as good of an opponent. A desire to grow as much as possible combined with good cost/benefit analyses should be a good foil for any player.
Also, I'm a big fan of emergent behavior and "evolving" the AI. Instead of scripting things for the AI, I think we could get great results with Mark's gene idea. Program a desire to grow as much as possible and a way to alter behavior, and then set computer players up against each other in a series of automated deathmatches with no graphics or user interface.
I think it would be great if we could make some kind of SETI@Home type of program that runs AI bouts in idle time and then passes the best "genes" back to a server. After a few months of that, we could probably get a really powerful AI even if the thing ran on just a few computers.
|
|
| |
|
|
|
quote:
Pretty long-range planning here. 100 turns is 500 years.
|
I believe this is needed. 500 years could be used for:
- Science goals
- Economic power rating
- Sometimes takes 500 years to make an angry Civ happy with you
- It can take 500 years (in gameplay) to overcome an entire Civ.
Basically, the 500 years idea is for the "general" direction of the Civ. IE: expand and conquer, or diplomacy for world peace, or economic power for monopolies, etc.
Mark:
I was using generalities that anyone not deep into the Clash project could relate to through their own Civ experiences. 
quote:
What about opportunist moves? e.g. You discover a (neutral) city is undefended, you might want to threaten or attack. Who decides on that?
|
quote:
The AI should always have a plan B, somewhere at mid-level.
|
In my model, the "5 turn AI" would report to the "20 turn AI" any unexpecteds, and it's the "20 turn AI"s responsibility to adjust to it.
Another idea I just thought of, is maybe have another level of AI that is purely looking for opportunities and plan B's. This AI's responsibility is to examine the map, find weak/strong spots and propose a plan to the 20 turn AI. If given a plan by the 20 turn AI it has to come up with a backup. Basically, two AI's work in conjunction with each other to find/exploit weaknesses/strengths.
This type of AI could work in the background not slowing things down during "idle" time. It just permeates options round and round it's little sylicone head.
|
|
| |
|
|
Chieftain
|
Sep 2001
time: 03:45
| |
|
|
Hmmmmm.
quote:
How do you get the army you want in place for a given task?
I am supposing you know you want to get attack force to fight a supposed force of X in a given square. The high level AI also knows it must defend some spots. How does it know it can move some units from a previous attack, but shouldn't move units defending a city? Should it build units, and of what kind?
All decisions come down to:
1) What is my ideal units orders/builds for my goal? Ask for that budget.
2) Given a budget, do what I can.
Considering (1/budget), the question is:
Q1) Do I need new armies or can I move around existing ones.
Considering (1) and (2), the question is:
Q2) What units do I need (transports, artillery, infantry???) |
I would like to suggest a somewhat different approach. Please tell me if you think it's more or less practical.
While the concepts of '100 turn AI', '20 turn AI', and so on are useful for understanding the AI hirarchy, it seems that eventually most of the AI chromozomes will have more to do with considering certain issues for an indefinite time then with taking responsibility for a time period.
Every chromosome will ask the relevant other chromosomes for the data it needs to make its decisions, and will supply info to and take orders from the chromosomes above him. The decision making process will also involve overall AI variables (such as agressiveness and risk taking) in some of the levels.
I'll try to explain:
One chromosome could use the map AI and information on nearby enemy units to identify certain regions of the map (that have sufficient activeness) as relatively independant 'fronts' and maintain a dynamic set of all of them.
Each Front AI will run the combat condition in its area and attempt to get as close as possible to obtaining its front objectives. Those objectives may come in a form of the relative importance of the various possible goals (defensive and offensive alike). The Front AI will be using yet smaller chromosomes to give specific orders to TFs.
The Front AI will be the one best aware to the possible developments in the front, maybe by using a simple simulation of the offensive and defensive capabilities and various tactical shifts. It will use that info to estimate what will happen if one TF will be diverted elsewhere or added as reinforcemnet, and will pass that info up in the chain of command in terms of the resulting overall effect on that front objective.
The Military Operations AI (or whatever) will hear from each Front AI and for each amount of mobilized military resources it may posses it will try to estimate what is the best allocation between fronts (in what front some extra power can do the most good?)
The resulting 'production function' (sort of speak) of military operations will be combined with other military expenditures and will help a higher level AI to decide if new military units should be trained/scrapped.
For some decisions (especially long term ones) we'll probably have to use hureistics; FE it seems that it'll will be difficult for the computer to calculate from scratch using only GAs how much military reserves it should keep. But whenever possible we should try and convert the process into number crunching. Handling seperate alternative plans (such as conquer Granada if possible and else do some piracing) will be difficult for the AI.
Maybe I haven't said anything really new here, but I would like to stress that IMHO we shouldn't rely on planning ahead for constant time periods too much. It's hard to approximate what can be achieved in 100 turns, and as we get closer to the end of the 100 turns the AI will be able to give lower level AIs less and less information on what should be done.
If we meet all of our objectives in 80 turns we can just start a new 100 turn plan there, and if we don't finish the plan in 100 turns we can just give it extra time or reconsider. But still I think that a more flexible approach will eventually be neccessary if we are to accomplish our ambitious AI goals.
Objectives don't have to be reevaluated every turn; The amount of calculations we can allow ourselves is dependant on our computational resources. Obviously lower level AIs will require more frequent reconsidering. But we shouldn't limit ourselves to plans of fixed length.
This design style should IMO sit relatively well with our OOP based implementation.
|
|
| |
|
|
Prince
New Zealand
|
Mar 2001
time: 13:45
| |
|
|
To be honest, I am not very enthused with time driven goals. In particular I do not know of any realistic plans (in real life history) which span 500 years. Saying that scientific goals are in that category is like saying that Queen Isabella should have been planning for computers. Scientific planning actually takes place on a very short time span. The Manhattan Project and the moon landings come to mind. Both happened in less than one turn, never mind 100.
I would be more inclined to rate the AI in terms of breadth of effect - civilization wide, province wide, local, with perhaps long, medium and short term objectives in each, where the actual time span is vaguely specified.
Laurent: congratulations on the win over the Springboks. On the other hand they are not the force they used to be - even the All Blacks beat them. Now England beating Australia - that is something. We managed to beat Ireland, but the game wasn't even televised - there are rumblings of revolt down here over that. I wonder if anyone else reading this forum realizes that there are some things much more important than even Clash?
Cheers
|
|
| |
|
|
Prince
New Zealand
|
Mar 2001
time: 13:45
| |
|
|
quote:
What is with 100 turns = 500 years??? 5:1 is only the conversion factor we'd hoped to use for classical antiquity. |
The code I originally got announced "Five years pass..." every turn. Ergo, I assumed that 1 turn = 5 years, hence 100 turns = 500 years. The logic seems unassailable.
Cheers
|
|
| |
|
|
|
Hi All: Good discussion! Just for the record after a few weeks of discussion I will try to take the best ideas and put them together in an overall proposal for the AI. That will focus most on the things that will do the game most good now -- more tactical sorts of AI. But I hope to have the rest at least sketched out.
I agree with Yoav's comments that AI hierarchy should not be only discriminated by timespans, but also geographic areas, or other demarcations that make sense. I suspect after we kick these ideas around a bit we can find a limited set of AI types that cover most important circumstances.
|
|
| |
|
|
|
I came across an interesting article at GameDev that I thought I should post here. Its about so-calledProject AI . You can skip the early sections of the article, since they are only about various dumb ways to do game AI. The interesting thing to me in the Project AI article was the idea of having a measure of the marginal contribution of adding a unit to a project. In the Clash context we could do this by various levels of command rather than just by unit.
Thoughts / opinions?
|
|
| |
|
|
Chieftain
|
Sep 2001
time: 03:45
| |
|
|
I like the project oriented point of view but I don't see any reason why there would be oscillation or why a unit will be dispatched to one project and then get reassigned elsewhere when it gets closer to the object area (and hence more valuable to it), unless if there's a real change in condition.
Of course we have to consider the cost of transferring units from point A to point B, but I don't see an innate value in keeping units in their current tasks, unless we assume it exists to save reavaluations.
I'll post some of my thoughts on the layered structure of the AI when I find the time.
|
|
| |
|
|
|
Hi All:
[this has been heavily edited (20-12-2001) from the original post of Dec 19]
I am laying out the AI architecture to support the functions we've been talking about in
this thread. I have a proposal for one key piece, and I would like to see what people think
about it. I call this object a Plan, but the name isn't important. There would be all
sorts of sub-types of Plans, targeted for use in different AI functions. What I'm proposing
here is just the base object. One test you can subject my proposal is to think about
several quite-different things you want the AI to be able to do. See if the Plan framework
can accomodate your ideas.
The Plan Object has:
a list of Objectives (take city W, make peace with Celts) The objectives will each
be rated for importance, and what success looks like (for some plans losing 1/4 of an
attacking army is acceptable, for others it is a catastrophe) The Success of the plan is
scored by a weighted estimate of achievement of the objectives. More on this down below.
a list of Resources (5th army, 1000 Clash Cash, Character Alexander)
a list of Assumptions (assume city defended by army of X strength, assume the Big
Noses won't attack us for at least 10 turns)
a (list of) Actions (An action, which would include a reference to the available
resources, becomes an instruction to actually do something, and hence can be simulated, with
(one way or another) a success level or probability calculated. The important point about an
action is that it must be possible to simulate it.)
a ParentPlan (the one that told it what to do, and that it reports to)
a list of ChildPlans (if the Plan isn't at the lowest level, it can delegate some of
the action to these lower-level plans)
a SuccessFunction (returns a number between 0 and 1, giving likely level of success
given the objectives, resources... The sucess level 0 corresponds to 'normal' failure, and
1 to success, but the [0,1] range might be able to be exceeded. OR We define success in terms of monetary equivalents, and let the $$$ speak for itself (depends on how we want to work the success function, more on that below) Parent plan sets these defininitions thru a function of success on each Objective)
a RiskFunction (returns a standard deviation of how much SuccessFunction result is
likely to vary given luck of the draw and imperfect information, etc.)
The overall function of the Plan is to get information about objectives, resources and
assumptions from above. It takes the inputs, does some AI magic involving heuristics,
simulation, and perhaps other scary words. The magic generates Actions which are evaluated.
Then the plan reports to the parent on average expectation of success, and risk. The parent
then does one of three things: approves the plan and orders it to go forward; scraps the
plan and lets it die; or tweaks the inputs to the plan to see if it can get something it
likes better. The last part can be done by asking the plan "what do you need to get 90%
success" or the parent can just change things and ask the plan what its new success and risk
functions evaluate to.
Most of the details on the objects within the Plan are TBD. The one that I have given a
little more thought to is the Objective. We'll come up with a bunch of classes of
objectives that are beyond the scope of what I want to say now. What I want to mention is
how the level of achievement of an objective contributes to the success function. Since we
are first going to implement simple attack-management Plans I'll just pick two obvious
objectives an Attack Plan might have, in words: (1) Take the city W, and (2) minimize loss
of troops. How should we specify a success level given these two things that's generic
enough to use for any plan?
I have two options for this, and I'm going to just crudely sketch them out for now.
Option 1 (what I started my thought process with)
I will assume here that for each objective we can simulate / calculate a success level, and
that its roughly in the range [0,1]. And we'll use a simple function in each case. Don't
take the function charaterization too seriously for now.
(1) Take City -- success = 1 if city taken, 0 if not.
(2) Minimize casualties -- success = (Army strength after) / (Army strength before) + .1
So given different Actions that the plan comes up with we can simulate success over one or
more models of how combat works, assumptions about how many we're fighting, how far troops
can get etc. I don't want to get into details here, because this will be where much of the
work goes in. But through either simulation or rules of thumb we can get a distribution of
success levels for 1 & 2. Lets say we do three trials (all using same Actions) and get the
following results
__(1)_(2)
A._1___1
B._1__.8
C._0__.7
If we want to get a combined success level for the whole plan for each scenario, we need to put the individual success levels together somehow. Lets say for now that we just multiply the two success levels. We'd get values respectively of 1, .8, and 0, giving an average of 0.6. So its not a great attack. Looking at the standard deviation of the numbers would tell you its fairly risky too, things can swing either way quite dramatically. That makes it different from a 'safe' 0.6 where you almost always get something near 0.6 for the result.
Option 2 (Which I think is the more attractive option)
Here success in each area is determined by global values of objectives that we'd need to determine thru playtesting. But lets say we phrase everyting in terms of CC (Clash Cash). So put bluntly cities and provinces have monetary value, units have value and replacement costs, etc. Things in enemies' hands also have (negative) value to us. With a scaling like this, each plan would produce a value that is basically the sum of the values of objectives attained (and resources depleted). If we want to get sophisticated we can use discounted cash flows to get at the time value of money. A similar table to what I had in option 1 might look like this (in units of 1000 CC):
____(1)__(2)__total
A._100___-30___70
B._80____-40___40
C._10____-50__-40
So again its probably not a really good attack. I just mostly picked the numbers out of the air, but the 80 in B is meant to represent significant damage to the city upon taking it. And the 10 in C damage to something the other guy retains control of. On this scale the average is 23 and the standard deviation again quite big.
What do you think of the general approach, and the two specific Success options?
Last edited by Mark_Everson on 20-12-2001 at 15:23
|
|
| |
|
|
Prince
New Zealand
|
Mar 2001
time: 13:45
| |
|
|
I would add Actions to this system. An action (which would include a reference to the available resources) becomes an instruction to actually do something, and hence can be simulated, with (one way or another) a success probability calculated.
The important point about an action is that it must be possible to simulate it.
The risk function doesn't seem to have a use here. Since the result of the SuccessFunction is a probability, its variance is p(1-p) with some adjustment for sample numbers.
Cheers
|
|
| |
| <
|
iracy to plan B: conquer gibraltar) Drake conquers Gibraltar.