AI -- the Thread

[Mark_Everson]

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]

(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)?

[Dale]

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?

[Gary Thomas]

Pretty long-range planning here. 100 turns is 500 years.

Cheers

[Mark_Everson]

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.

[LDiCesare]

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?

[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: ) 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.

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.

[Richard Bruns]

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.

[Mark_Everson]

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?"

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.

[Dale]

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.

What about opportunist moves? e.g. You discover a (neutral) city is undefended, you might want to threaten or attack. Who decides on that?

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.

[Yoav Sissman]

Hmmmmm.

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.

[Gary Thomas]

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

[Mark_Everson]

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.

[Yoav Sissman]

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.

[Gary Thomas]

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