Reply
 
Thread Tools
Old November 11, 2001, 15:06   #1
Mark_Everson
 
Mark_Everson's Avatar
 
Local Time: 12:33
Local Date: October 31, 2010
Join Date: Dec 1969
Location: Canton, MI
Posts: 3,442
AI -- the Thread
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'!
Mark_Everson is offline   Reply With Quote
Old November 12, 2001, 04:06   #2
LDiCesare
GalCiv Apolyton EmpireCivilization IV Creators
Emperor
 
Local Time: 18:33
Local Date: October 31, 2010
Join Date: Jan 2001
Location: Ashes
Posts: 3,065
(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)?
LDiCesare is offline   Reply With Quote
Old November 12, 2001, 16:58   #3
Dale
Emperor
 
Dale's Avatar
 
Local Time: 02:33
Local Date: November 1, 2010
Join Date: Dec 2000
Posts: 3,944
High-level AI
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?
Dale is offline   Reply With Quote
Old November 12, 2001, 19:04   #4
Gary Thomas
Prince
 
Gary Thomas's Avatar
 
Local Time: 04:33
Local Date: November 1, 2010
Join Date: Mar 2001
Location: New Zealand
Posts: 950
Pretty long-range planning here. 100 turns is 500 years.

Cheers
Gary Thomas is offline   Reply With Quote
Old November 13, 2001, 05:12   #5
Mark_Everson
 
Mark_Everson's Avatar
 
Local Time: 12:33
Local Date: October 31, 2010
Join Date: Dec 1969
Location: Canton, MI
Posts: 3,442
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.
Mark_Everson is offline   Reply With Quote
Old November 13, 2001, 07:09   #6
LDiCesare
GalCiv Apolyton EmpireCivilization IV Creators
Emperor
 
Local Time: 18:33
Local Date: October 31, 2010
Join Date: Jan 2001
Location: Ashes
Posts: 3,065
Quote:
Pretty long-range planning here. 100 turns is 500 years.
Well 100 turns military-wise is only around 10 years.
I like the breakdown 100 turns/20 turns/XX/1 turn. The 5 turns should probably be a bit more flexible in its duration since it will have trouble building things which require 6 turns.
(Edit - I started posting before Mark and finished after rugby 2 hours later...)
What about opportunist moves? e.g. You discover a (neutral) city is undefended, you might want to threaten or attack. Who decides on that?

Last edited by LDiCesare; November 13, 2001 at 07:14.
LDiCesare is offline   Reply With Quote
Old November 13, 2001, 09:48   #7
Simon Loverix
Warlord
 
Local Time: 16:33
Local Date: October 31, 2010
Join Date: Apr 2001
Location: Tongeren, Belgium
Posts: 163
The AI should always have a plan B, somewhere at mid-level.
example:
(plan A)The English send Drake to Granada to conquer it , (new information passed to higher level AI) but it seems too well-defended. (switching to Plan B: ) He slowly navigates back to London along the coast, hoping to do some piracy instead. (Information passed to higher AI: ) When reaches the Atlantic, Gibraltar seems badly defended. (Higher AI changes plan Biracy to plan B: conquer gibraltar) Drake conquers Gibraltar.

Quote:
2. Rules are used to generate an alternative series of possible best ways to execute the strategy
The best way to start with this is figuring out what should NOT be done. Throwing a nuclear bomb on troops sieging your capital, starting a military campaign in autumn to an area known for its harsh winters, overstretching,.. Counterstrategies generated also exclude the possibility that an enemy would do this. But mutations allow unexpected variations (Hannibal through the Alps,... )
After that give preference to strategies attacking weak points of the enemy.
Simon Loverix is offline   Reply With Quote
Old November 13, 2001, 15:37   #8
Richard Bruns
King
 
Local Time: 17:33
Local Date: October 31, 2010
Join Date: Nov 1999
Location: NC, USA
Posts: 1,579
Alternative?
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.
Richard Bruns is offline   Reply With Quote
Old November 13, 2001, 17:54   #9
Mark_Everson
 
Mark_Everson's Avatar
 
Local Time: 12:33
Local Date: October 31, 2010
Join Date: Dec 1969
Location: Canton, MI
Posts: 3,442
Quote:
Originally posted by LDiCesare
What about opportunist moves? e.g. You discover a (neutral) city is undefended, you might want to threaten or attack. Who decides on that?
I think we can have an interrupt system that says: "something potentially big has happened, need to recalculate". BTW thanks for explaining about your post edit. I read the first one and thought "didn't he even read my post? What does this guy Want?"

Quote:
Originally posted by Simon Loverix
The AI should always have a plan B, somewhere at mid-level.
example:
(plan A)The English send Drake to Granada to conquer it , (new information passed to higher level AI) but it seems too well-defended. (switching to Plan B: ) *snip*
The best way to start with this is figuring out what should NOT be done.
Simon, I think the alternates can be to some extent saved if we use the tack of evaluating several strategically sound moves, and keeping several of the most attractive in storage for a period of time. I think what should NOT be done is easier. We will just have to make our heuristics (rules) to stop most of the dumb things before they need be evaluated. Easier said than done, but I think we can do Much better than most of what's available in the genre.

Richard, your three KISS rules are just where we'll be for probably the next few big steps with the demos. I don't know if we can go as far as you'd like in the evolving direction but we'll (I hope) be able to go far in each of the three big areas:
1) good rules
2) simulation to decide between rule-based approaches for each decision
3) evolution of simulated strategies for decisions as time allows

Maybe at some point we could give it a shot to close the loop and try and evolve (1) as you propose, but I'm skeptical because of the size of the parameter space.
Mark_Everson is offline   Reply With Quote
Old November 13, 2001, 18:00   #10
Dale
Emperor
 
Dale's Avatar
 
Local Time: 02:33
Local Date: November 1, 2010
Join Date: Dec 2000
Posts: 3,944
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.
Dale is offline   Reply With Quote
Old November 14, 2001, 10:04   #11
Yoav Sissman
Chieftain
 
Yoav Sissman's Avatar
 
Local Time: 18:33
Local Date: October 31, 2010
Join Date: Sep 2001
Posts: 30
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.
Yoav Sissman is offline   Reply With Quote
Old November 14, 2001, 11:29   #12
Gary Thomas
Prince
 
Gary Thomas's Avatar
 
Local Time: 04:33
Local Date: November 1, 2010
Join Date: Mar 2001
Location: New Zealand
Posts: 950
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
Gary Thomas is offline   Reply With Quote
Old November 14, 2001, 13:42   #13
Mark_Everson
 
Mark_Everson's Avatar
 
Local Time: 12:33
Local Date: October 31, 2010
Join Date: Dec 1969
Location: Canton, MI
Posts: 3,442
Just a few quickie points from work...

The '100 turn' AI I had in mind when I wrote the thing on the web page wasn't meant to be Evaluated exactly every 100 turns. That was just meant to be the timespan it would look out. FE in Civ2 it would consider the next bit target technologies to try to achieve. The '100 turn' AI might be re-evaluated every 20 turns or so. Or more often as required.

What is with 100 turns = 500 years??? 5:1 is only the conversion factor we'd hoped to use for classical antiquity. I think that regardless of what Really happens the AI needs to be able to win the game. If there are things in Clash that merit being planned out 100 turns in advance then the AI may well need to think about them. Lets not get bogged down into arguing over what time period our longest-term thinking for the AI should be just yet. We need to see what time periods are relevant in the game first. That will be among the last things to be done anyway since good rules to drive it require finishing most of the rest of the game, and people playing it to determine what the best strategies are.

Gary, I Do realize there are things more important than Clash, but what you're talking about ain't one of them.
Mark_Everson is offline   Reply With Quote
Old November 14, 2001, 13:47   #14
Yoav Sissman
Chieftain
 
Yoav Sissman's Avatar
 
Local Time: 18:33
Local Date: October 31, 2010
Join Date: Sep 2001
Posts: 30
While I have my objections to the time driven AIs, I don't share other people's concern over it.

Civ type game often last for thousands of game years, but actually they only strive to represent everything that happened in the RW over the course of history IN MINISCALE.

Also we can only simulate the RW as much as it doesn't reflect on the players (both real and artificial ones) decisions. After all, this is a game, where the players play with the intention of winning, even if it involves considering armored warfare when you research Ancient Physics.
Yoav Sissman is offline   Reply With Quote
Old November 14, 2001, 14:01   #15
Gary Thomas
Prince
 
Gary Thomas's Avatar
 
Local Time: 04:33
Local Date: November 1, 2010
Join Date: Mar 2001
Location: New Zealand
Posts: 950
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
Gary Thomas is offline   Reply With Quote
Old November 14, 2001, 18:14   #16
Dale
Emperor
 
Dale's Avatar
 
Local Time: 02:33
Local Date: November 1, 2010
Join Date: Dec 2000
Posts: 3,944
Just a clarification over what I'm meaning about time-spanned AI's. I'm not saying "In 20 turns we will have this", I'm looking more at things that will take that amount of time. IE: To build up an attacking army would take about 20 turns. To move an army to another continent about 20 turns. These goals are re-evaluated all the time, but since the Civ's goals for that level will only differ slightly over a small amount of time, they almost become like Russia's "5-year plans". So if an "extraordinary" situation appears suddenly, it will be taken into account the next time the AI evaluates and make a different plan based on the changes.

Everyone cool now?
Dale is offline   Reply With Quote
Old November 14, 2001, 19:43   #17
Mark_Everson
 
Mark_Everson's Avatar
 
Local Time: 12:33
Local Date: October 31, 2010
Join Date: Dec 1969
Location: Canton, MI
Posts: 3,442
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.
Mark_Everson is offline   Reply With Quote
Old November 28, 2001, 12:42   #18
Mark_Everson
 
Mark_Everson's Avatar
 
Local Time: 12:33
Local Date: October 31, 2010
Join Date: Dec 1969
Location: Canton, MI
Posts: 3,442
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?
Mark_Everson is offline   Reply With Quote
Old November 29, 2001, 09:31   #19
LDiCesare
GalCiv Apolyton EmpireCivilization IV Creators
Emperor
 
Local Time: 18:33
Local Date: October 31, 2010
Join Date: Jan 2001
Location: Ashes
Posts: 3,065
Interesting article, Mark. I agree with it quite a bit but disagree when the author says that management examples don't work for game AI: Hierarchies are changed to adapt to the missions/projects. This leads me to say: I'd reorganize commands based on the missions available. That way one level of commands between high command and units would correspond to a given task, which avoids having separate hierarchies.
The individual unit contribution thing is very interesting, but, as the author says, you can oscillate. The author suggests tweaking of the preferences function so the unit prefers to stay in their current mission rather than have a new one. I think that should be tweaked based on the role of the unit in the mission: Is it currently active or just on its way to help: If not, a newly built unit 10 squares away from a front will go there while a unit one square away might not, since it is on its way to help on another front. This means the function will have lots of parameters. It may be we have to check it not every turn but periodically (which is what happens in RL-management, at least where I work), if it turns out to be either unstable/oscillating or resources-consuming.
LDiCesare is offline   Reply With Quote
Old November 29, 2001, 17:58   #20
Yoav Sissman
Chieftain
 
Yoav Sissman's Avatar
 
Local Time: 18:33
Local Date: October 31, 2010
Join Date: Sep 2001
Posts: 30
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.
Yoav Sissman is offline   Reply With Quote
Old December 19, 2001, 21:20   #21
Mark_Everson
 
Mark_Everson's Avatar
 
Local Time: 12:33
Local Date: October 31, 2010
Join Date: Dec 1969
Location: Canton, MI
Posts: 3,442
The AI Plan Object -- a Draft
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; December 20, 2001 at 11:23.
Mark_Everson is offline   Reply With Quote
Old December 20, 2001, 02:52   #22
Gary Thomas
Prince
 
Gary Thomas's Avatar
 
Local Time: 04:33
Local Date: November 1, 2010
Join Date: Mar 2001
Location: New Zealand
Posts: 950
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
Gary Thomas is offline   Reply With Quote
Old December 20, 2001, 07:23   #23
Mark_Everson
 
Mark_Everson's Avatar
 
Local Time: 12:33
Local Date: October 31, 2010
Join Date: Dec 1969
Location: Canton, MI
Posts: 3,442
Hi Gary:

Action is good (though I try to avoid it frequently ), I'll update the Plan spec. Success isn't a probability. Lets wait until I refine what I mean, and then we can revisit your point.
Mark_Everson is offline   Reply With Quote
Old December 20, 2001, 11:28   #24
Mark_Everson
 
Mark_Everson's Avatar
 
Local Time: 12:33
Local Date: October 31, 2010
Join Date: Dec 1969
Location: Canton, MI
Posts: 3,442
I have heavily modified my post on the Plan object (three posts above this. Anyone that has already read it is requested to go back and go through it again, since I'd really like your suggestions. I made the mistake of editing the post from a screen grab or something, so the formatting is all screwed up. My apologies!

-Mark
Mark_Everson is offline   Reply With Quote
Old December 20, 2001, 11:52   #25
Gary Thomas
Prince
 
Gary Thomas's Avatar
 
Local Time: 04:33
Local Date: November 1, 2010
Join Date: Mar 2001
Location: New Zealand
Posts: 950
That is becoming a good framework. The only real suggestion that I have is that we do not confine or restrict the concept of success. Rather than converting everything to probabilities (death to statisticians!) or to money (death to accountants!), I think we should work in a more generalized area. It is possible to take a cost benefit approach without restricting the area of measuremment. Things like losing the minimum number of men can be a criterion.

Accordingly, I would have a Success object, of a general nature, perhaps just an interface. All we really want to do is say whether a particular success is better than another one, with some numeric estimation of the measure of the difference.

In my view, at this point, we should not attempt to restrict it any more than that.

Cheers
Gary Thomas is offline   Reply With Quote
Old December 20, 2001, 11:59   #26
LDiCesare
GalCiv Apolyton EmpireCivilization IV Creators
Emperor
 
Local Time: 18:33
Local Date: October 31, 2010
Join Date: Jan 2001
Location: Ashes
Posts: 3,065
I like the approach. I think Gary's Success object idea is a good one because it could allow modelling different behaviours from the AI. Some might not be effective, but you could model Cash-based success, Casualties-are-unimportant succcess, and other success schemes. So a bloodthirsty despot would behave differently from a democracy. I like the Cash approach a lot however, although I believe that one must take into account the production capability: A city is worth f.e. 100 gold/turn, so taking it from the opponent is worth 100* the number of turns I'll keep it (assumptions here). Heuristics might come in to help decide the various values of cash/casualties/other success factors.
LDiCesare is offline   Reply With Quote
Old December 21, 2001, 08:49   #27
Mark_Everson
 
Mark_Everson's Avatar
 
Local Time: 12:33
Local Date: October 31, 2010
Join Date: Dec 1969
Location: Canton, MI
Posts: 3,442
Glad you guys think its shaping up!

A generic Success object is fine by me. I'll write it up that way the next time I revise the spec.

Gary:

"Things like losing the minimum number of men can be a criterion."

That can be handled just fine (at least for a game) with the $$$ approach. Along with Laurent, a modern democracy with high income etc. might place a very high value on each life, whereas Stalin... I just think it is a vast simplifying factor if we can estimate the value of everything in a single currency, and the best is... currency. This can be a supported function of Success without being required for everything though.

Laurent:

"I like the Cash approach a lot however, although I believe that one must take into account the production capability: A city is worth f.e. 100 gold/turn, so taking it from the opponent is worth 100* the number of turns I'll keep it (assumptions here)."

The 100 was meant to be a discounted cash flow at a TBD discount rate, counting income out into the forseeable future, and also including things like population contribution to technological advance. So the per-turn value might be 10kCC at a discount rate of something like 10-20%.
Mark_Everson is offline   Reply With Quote
Old December 21, 2001, 13:19   #28
Gary Thomas
Prince
 
Gary Thomas's Avatar
 
Local Time: 04:33
Local Date: November 1, 2010
Join Date: Mar 2001
Location: New Zealand
Posts: 950
I would envisage Success being an interface, with a compareTo function, with possible financial calculations inside an implementation.

Unlike Mark, I cannot see that everything can be reduced to monetary terms. I have the misfortune ito live in a country in which an aberrant government (since removed from office) that adopted that philosophy. They turned everything into companies that were supposed to return a profit. So we have the bizarre situation that the social welfare agency responsible for paying the dole is supposed to make a profit. It doesn't work.

It is my perception that most real political decisions are based on emotional terms. I do not relish the idea of a game in which the AI decisions are all made by accountants.

Also many political decisions are made to get votes. The idea of quantifying this in money terms is mind-boggling though not impossible.

Cheers

Gary
Gary Thomas is offline   Reply With Quote
Old December 21, 2001, 16:14   #29
Velociryx
staff
PtWDG Gathering StormApolytoners Hall of FameC4DG Gathering StormThe Courts of Candle'Bre
Moderator
 
Velociryx's Avatar
 
Local Time: 16:33
Local Date: October 31, 2010
Join Date: Apr 1999
Location: of Candle'Bre
Posts: 8,664
Mark, thank you for extending the invite to head this way! A fascinating and thought provoking thread!

With regards to what has been laid out thus far, I agree with the notion that for the practical purposes of allowing the AI to make determinations (and hopefully, intelligent ones), reducing plot points on the map (cities) and the units that are defending/near them to $$$ values is the simplest way to go (and by the way, the model outlined above is excellent so far!), however, Gary makes a good point with his last post.

Seems to me all well and good to use the abovementioned formulae to get the AI to crank out a reliable, well-put-together attack force, and to perhaps even defend itself reasonably well, however, the part that lies outside the bounds of the formulae is motivation.

This is where Gary's posts rings most true in my mind's eye, so far as game terms go.

The cost-analysis approach excels at allowing the AI to put together his plan, and execute it in passingly good fashion, but it begins to crack in the face of determining the when and why of the attack.

Admittedly, I have not yet played this game (a condition I will happily remedy this weekend), so I'm in scant position to comment on possible motivational factors....just an observation on what's been presented so far, based on a good deal of reading after taking Mark up on his invitation....

-=Vel=-
__________________
The list of published books grows. If you're curious to see what sort of stories I weave out, head to Amazon.com and do an author search for "Christopher Hartpence." Help support Candle'Bre, a game created by gamers FOR gamers. All proceeds from my published works go directly to the project.
Velociryx is offline   Reply With Quote
Old December 21, 2001, 17:30   #30
Mark_Everson
 
Mark_Everson's Avatar
 
Local Time: 12:33
Local Date: October 31, 2010
Join Date: Dec 1969
Location: Canton, MI
Posts: 3,442
Hey Velociryx, thanks for dropping by! And good to hear your thoughts, esp. that us bunch of inbred Clashers are possibly not completely deluding ourselves...

All:

As to whether we use money-evaluation or other and varied objective functions... I expect we will go through a bunch of things as experiments, and see what works well for what type of plan. I'm inclined to just leave that topic for now. When I have the time and inclination I'll fix up the Plan spec. Once that's out of the way we can start discussion about what the AttackPlan and DefensePlan approaches might be. This will be a Big topic, but we can start just with the stuff that is relevant in D6.

Anyone have other proposals for the next items on the agenda for AI? I'd like to keep things focused on things that are implementable soon for the moment.
Mark_Everson is offline   Reply With Quote
Reply

Bookmarks

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is On

Forum Jump


All times are GMT -4. The time now is 12:33.


Design by Vjacheslav Trushkin, color scheme by ColorizeIt!.
Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2010, Jelsoft Enterprises Ltd.
Apolyton Civilization Site | Copyright © The Apolyton Team