AI -- the Thread

[Dale]

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?

[Mark_Everson]

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]

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?

[LDiCesare]

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.

[Yoav Sissman]

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.

[Mark_Everson]

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?

[Gary Thomas]

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

[Mark_Everson]

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]

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

[Gary Thomas]

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

[LDiCesare]

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.

[Mark_Everson]

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%.

[Gary Thomas]

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

[Velociryx]

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=-

[Mark_Everson]

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.