AI -- the Thread

[Mark_Everson]

Here is my attempt to move the AI approach forward towards something specific enough to start coding. It ain't there yet! But I am burnt out, and thought I would post this in rough form to get initial responses and ideas. I have left out some of the communication mechanisms that will be needed between Plans of different levels. also, I've only gotten partway up the command chain...


First, a few notes, refining what has gone before:

When Objectives are complete, plan reports this fact to parent using a TBD mechanism

Names for now are just placeholders


Specific Plan Objects have the following:
(an object whose name is pluralized implies a collection of X)

Objectives - have a
* Name (for GUI use)
* arguments passed in that are used by getValue (FE how to assess value of a mil. unit)
* getValue method that takes some object of Game State after a simulation of the Actions, and returns a value that indicates level of success of the objective.
* isAchieved method that says whether objective has been satisfied

Resources - are Clash objects of various sorts. Commands, money, Characters...

Assumptions - (I'm having trouble specing this one out for the general case, will return to it later, and you can also see some specifics below. comments welcome!)

Actions - (again, tough to put in a general fashion, see specifics associatied with different Plan objects)

a ParentPlan (object of type Plan at higher level in the hierarchy)

ChildPlans (objects of type Plan at the same or lower level in the hierarchy)

Success -
* has a compareTo function per Gary's post
* group of success values. In simulation, a number of different success values can be obtained even given identical Actions, Child Plans, etc. This saving of success values allows for assesment of ranges of results likely, characerizing riskiness.
* success as an absolute measure, rather than compared to another plan (perhaps success measures should also have an opportunity cost for Resources used). This prevents the case where marching an army a long ways off to conquer something would be preferred to conquering something of slightly less value a lot closer to home, and then freeing up the troops. Thoughts?)


Now, the first specific Plan:


AttackAreaPlan (Attack and take one or more squares)

Objectives - TakeArea, AvoidTroopLoss, EnemyTroopLoss, AchieveByTurn

Resources - Commands

Assumptions - EnemyForces

Actions - MovementPath(s), Orders specifying when to fight and when not

a ParentPlan - SectorStrategy

ChildPlans (none for now)

Success


AttackAreaPlan Object Details

Objectives -

TakeArea - Secure control of an area that is a collection of MapSquares
* Name ("Conquer Silesia")
* area - collection of squares that define area to be conquered
* value of captured square per unit economic value (may need more refinement)
* strategic value of conquered squares(when map AI functional so strategic value can be better assessed)
* getValue sums econ and strategic value over all conquered squares. Or perhaps adds for all conquered and subtracts for any lost from starting area
* isAchieved method returns true when all of area defined is conquered.

AvoidTroopLoss
* Name ("Military Losses")
* arguments passed in that are used by getValue (FE how to assess value of a mil. unit. For now we should just use creation cost as a simplification)
* getValue calculates army cost-to-build after executing Action and subtracts initial

cost-to-build.
* isAchieved method (not sure this is needed here, since everything is 'shades of gray'. If we want to add another parameter that says anything more than X is unacceptable, then this method again makes sense in this context)

EnemyTroopLoss
virtually identical to AvoidTroopLoss

AchieveByTurn
* Name ("Turn 38" or "340BC")
* parameter(s) specifying how much early or late completion affects value
* getValue returns bonus for early completion, or penalty for late.
* isAchieved is straightforward

Resources - Commands used in attack plan

Assumptions - EnemyForces for now we should just weasel on this and let the AI see everywhere. Perhaps forces just outside area should be counted also.

Actions -

*Path(s) Just path or paths attackers will follow
*Orders specifying when to fight and when not. FE "don't attack at less than 2:1 odds". Also includes other orders like leaving a garrison at a critical crossroads. More TBD

a ParentPlan - SectorStrategy

ChildPlans (none for now, although a complicated AttackAreaPlan could well be subdivided into more tractable AttackAreaPlans)

Success - use basic Success above, or something fancier depending on what we think we need.



DefendAreaPlan (defend given area)

This will have many Objectives and other objects in common with the Attack version. However, unless the area is only a few squares this one will almost certainly require child DefendAreaPlans. Now for some of the differences:

Trivially, we will have a DefendArea objective rather than an AttackArea
There could also be a ScorchedEarth Objective, and probably some more.

Assumptions - These are even more critical for good defense than they are for attack. One obvious one is enemy troops that are nearby to the area, and heading this way. Lets start with that for simplicity. Once enemy troop strength is established we need to worry about where they are going. I think we should spec this out further as we go along.



ReservePlan (reserves for undetermined future use)

The idea is that reserves can be drawn upon, giving a negative value from Success in the ReservePlan. If the Plan that wants to use the reserves has a Success gain large enough to justify the removal of the units, then the transfer will get approved (Ideally after all Plans that want them have their chance). Whether we need a method requestTransfer(Command) that returns a value, or whether this is handled some other way, I will leave to Gary's Judgment (lucky you! )

Objectives -

AvoidReserveDepletion
* Name ("Reserve Depletion")
* arguments passed in that are used by getValue (FE how to assess value of a mil. unit. in reserves. For now we should just use creation cost as a simplification, but this can be Much more nuanced later. Reserves in the right spot can have an importance Many times their base construction value.)
* getValue calculates army cost-to-build change after executing requested Action of removing the reserves.
* isAchieved method (don't know about this one here. maybe this points to us needing two high-level Objective classes, one that is Achievable and another that isn't)

Resources - Commands used in attack plan

Assumptions - N.A. or maybe this can be where the remove reserves order gets put in?

Actions - N.A. or maybe This can be where the remove reserves has its influence?

a ParentPlan - SectorStrategy

ChildPlans (none for now, although a complicated ReservePlan could well be subdivided into more tractable ReservePlans)

Success - use basic Success above.



SectorStrategy (Plan for a big chunk of the map, like a front in modern warfare)

Objectives -

TakeEnemyTerritory - accomplished thru child AttackAreaPlans
* Name ("Conquer Silesia")
* value of one point of AttackAreaPlan success (used to characterize a sector strategy's success being predicated on taking enemy ground, this might range from 0 to 1)
* getValue sums all AttackAreaPlans and multiplies by value in line above
* isAchieved method returns true when all of AttackAreaPlans completed.

DefendOurTerritory - largely analagous to TakeEnemyTerritory Except that it is mandated that all friendly area of the front Must have an associated DefendAreaPlan so that the Sector AI will get feedback on any lost territory. The DefendAreaPlan need not have any Commands allocated to it.

Other ideas?

Resources - Sum resources used in all Child plans

Assumptions - This is an Enormously complicated issue. To be done right, SectorStrategy will need to estimate enemy forces and their disposition using all info available, formulate potential enemy actions, and then see if the Child plans handle those circumstances ok. For now we will just be dumb and happy and make no Assumptions, leaving estimated enemy disposition to the Child plans to guess.

Actions -

*Mostly these are the Child plans themselves
*Orders specifying when to fight and when not. FE "don't attack at less than 2:1 odds".

Also includes other orders like leaving a garrison at a critical crossroads. More TBD

a ParentPlan - MilitaryStrategy

ChildPlans (AttackAreaPlans, etc. this is where much of the action is)

Success - use basic Success above, or something fancier depending on what we think we need.

*** Much internal machinery for formulation of good Child plans, that will be in my next extended post.

[Mark_Everson]

One Important thing that we'll need soon, I forgot to mention in the post above. That is an actual mechanism to simulate the results of a combat without affecting the Clash world. There are a variety of ways it could be done. We will need to discuss if perfect simulation is feasible, and if not, what a good compromise is.

One bane of scenario writers is if they change something and the AI doesn't change its behavior to reflect the new reality. One reason our AI will be better than the run of the mill variety is that we will use in-game simulation to guide the AI. The result is that if a scenario designer changes a parameter, or throws in some oddball unit, the simulations will guide the AI to the correct use of the unit., and understand any change in its combat power trivially.

[Gary Thomas]

As far as designing things like, for example, Objectives, it is often helpful to think in terms of the general interface. In effect, what are the things the define an objective?

For example, it must have some kind of action to attempt to proceed to achieve it.

It must have a means of assessing its value, possibly in a multi-dimensional way.

It must be able to report that it has been achieved.

And, no doubt, many others. Using this approach makes the interface design a lot easier, and tends to isolate the things specific to a general Objective class.

Cheers

Gary

[Mark_Everson]

Today's take on things -- my apologies, this is a bit disjointed since it was done on my lunch hour amongst eating and other things…

Gary, I'll try to apply some of your ideas below. But I haven't been able to sit back and think deeply about minimalist Objectives and such. I will try thinking in that way, but frankly I'd rather just outline everything, and let you make those calls. Otherwise I will spend a lot of time mentally wrestling over it, and writing it up, and then you will explain to me why it is Wrong, and how you will do it differently Not a criticism, just a statement of fact as I see it .

Just to get it in the queue for coding we will need a Thread to run AI in the background. The first implementation of these ideas can probably do without it, but we will need it by the second AI wave I think.

Since objectives have single or multiple dimensions for evaluating success
should Dimensions be objects? Seems they should. Dimension would contain:
*a DimensionType identifier - Some sample DimensionTypes would be FriendlyTroopStrength, EnemyTroopStrength , EconomicValue, StrategicValue.
*initial value in that dimension,
*final value (after Actions taken) This value will change upon different simulations of the Actions are undertaken
* getDimensionChange function that returns change of Dimension value after Actions
* getValueChange that uses parameters to convert a Dimension change to a single scale like CC
*parameters for getValueChange that define a net value for the change in dimension. For now a single value times the change in dimension value (After vs Before Actions) will suffice. Eventually we might want some more-complicated functions of initial and final state.

The parameters for valuing the Dimension could be set by the highest AI for whole civ, or tweaked locally. But care needs to be taken with these, since the evaluation of a plan depends directly on those values. You can get almost any value for a plan you want by tweaking these values.

If a multi-dimensional value is needed for a Plan or Objective, then the Dimensions can be put together in a collection with a getValue function that returns a Collection of Dimension instead of a float

Complex vs Simple Plans

It has occurred to me that plans with and without child plans seem to behave in rather different manners. I think we need a ComplexPlan vs SimplePlan distinction. A SimplePlan has no children, its objectives are phrased in terms of basic Dimensions like EconomicValue. In terms of the "tree" of strategy, a SimplePlan is a terminal "leaf". Its Resources are used in the performance of Actions that achieve the Objectives.

A Complex Plan only does anything physical (Actions) through its child plans. Its objectives would be put in terms of success of the children plans. All it has is resources that it apportions to the children. The Resources are its to reapportion at will between child plans, but it performs no other action with the resources than apportion them to the child plans.

I will proceed using this dichotomy between plan type in the future unless serious objections are raised to it…

How to impart Flexibility to our AI plans? A ComplexPlan should IMO be able to have a logical-expression type structure associated with its child plans. FE an attack plan could have two children plans "Attack X" OR "Attack Y". For this flexible attack both children would be evaluated, and the final result would be the one that scores better at the moment. However, as circumstances change, the other attack might become better and that would switch to the active one. To make this work of course the two plans need a similar set of starting Actions, and it helps a Lot if X and Y are close to each other. Each turn, or even each tick when something changes, the two plans could be re-evaluated and the plan with the best score would be the one that gets executed.

Objectives for higher-level objects should IMO be quantified in terms of achievement of lower-level plans (Child plans). That is, a plan for a level below is in a way the Dimension for an Objective at this level. That seems best to me for reasons I'll explain when I have more time. If required performance of lower-level plans needs to be assessed in a multi-dimensional way, all dimensions from the child plan can be summed and returned to the parent object.

For example, [an Objective] must have some kind of action to attempt to proceed to achieve it.

I think that the Actions required to achieve the Objective are best handled by them being just the ones associated with the Plan itself. If that level of detail is not sufficient, then the given Plan should become a complex plan. I think Objective having their own Actions will be too confusing.

We need to be able to proscribe a temporal order for Actions also. I don't think that will be a shock to anyone, I'll try to include that notion in the Plan spec next rewrite. Perhaps we will also need logical expression support… As in "only start Action 3 if Objective 1 is complete".

That's all for now, opinions? Is this heading in the right direction?

[Gary Thomas]

This is really looking good.

Don't forget the sequencing element though. TIf this objective has that Objective as a prerequisite, the Plan will have some sort of ordering structure.

Cheers

[Mark_Everson]

Thanks, Gary! I think its coming together reasonably well, but its good to hear that I'm not completely fooling myself from someone else!

I will postpone the sequencing stuff for another day. But as an aside I only see Actions as waiting on fullfillment of Objectives at some level. Objectives won't wait on other objectives, that doesn't work within the system. But I do need to work out a timing spec... Seems fairly straightforward.


Ok, moving on! The stuff above needs a serious rewrite to bring it all up to snuff, but I’m not in the mood to do that at the moment, so I’ll just charge on.

How does a plan determine its Actions (or Child Plans for ComplexPlan)?
*SimplePlan - looks at objectives and Assumptions and formulates from there using determineActions method. FE for AttackAreaPlan the actions could be calculating a path to the most attractive economic or strategic target in the area, and getting the default minimum odds at which to attack from its parent.
*ComplexPlan – looks at overall Objectives and Assumptions. DetemineChildPlans function looks for good children to help it achieve its aims. Many children will be formulated based on the best rules we can provide. Then children, and groups of children, that satisfy the overall plan are evaluated. Finally, a best set is selected based on maximizing value from Objectives. (Perhaps the next-best set, or the few best non-selected ones are saved for future consideration?) FE a SectorStrategy plan will have AttackAreaPlan, DefendAreaPlan and ReservePlan children. If the Attack Objective is rated highly the search will focus on finding appropriate areas to attack in the region under control of the SectorStrategy. (The region should go fairly deep into enemy territory.) Rules we give it will look for good targets, and AttackAreaPlan children based on those rules will be created. Then the different sets of children are evaluated (by simulation) for success, and a single set of children is selected as the preferred one.

Once Actions have been determined an simulation has been carried out, a report saying what the best result is will be reviewed by its superior. If the result is not satisfactory, alternates can be proposed by the superior, perhaps with different weighing on the objectives. So a SectorStrategy plan with heavy weight on Attack may return only lousy, losing values. That is the signal to the parent strategy (OverallStrategy) that this plan is flawed and should not be carried out. Perhaps a plan with the same resources, but more oriented to defense will suffice. This would be the case if the enemy has superior defensive positions available) Or maybe even a defensive posture won’t help. Then the deal is “you are in Serious Sh*t, time to take Extreme action using any military, economic, and diplomatic means possible.” That could consist of OverallStrategy stripping another SectorStrategy of Resources to plug the gap, or changing GrandStrategy handling of the economy or diplomacy. Perhaps it is time to accept that humiliating peace settlement, and live to fight another day.

Where do Assumptions come from?
I can envision two types. Assumptions that come from the parent, and from the Plan itself.
* The from-parent ones would be used to probe overall possibilities, or ensure that the children that are being compared are all playing with the same assumptions. An example of probing possibilities: “Assume you are facing 2 armored divisions”. While another child of that parent would be given “… 4 armored divisions”. The parent can then decide how robust the plan is based on the value produced by each of the plans.
* The other type of Assumption is self-imposed by the Plan and just says what view of the world it is taking for its calculations. The use would be to maintain a record of the plan assumptions that can be compared to a different plan, or the same plan at a later date. I’m not sure the second type is critical in the short term, but I think it will be needed long-term.

[LDiCesare]

Looks good.
As I understand it, the AI you are describing is based on fixed resources, is it? I am unsure, as it could also fit resources-demand:

I bet a plan like "Invade Region XXX" would need troops you may not have so, in order to simulate its success, subplans would be 1)Build and ferry troops 2)AeraAttack, and the plan 1 would be preferred to plan 2 until the simulation reveals that "we will win".
This could require economic (at least) simulation in addition to military.

[Mark_Everson]

Hi Laurent:

Yes, the AI plan for now is using fixed resources. If the resources aren't adequate, then the parent should get the idea that the plan is lousy given available Resources. If even the best plans are awful, that is the signal the resources are a big problem. That would call for a change of strategy at a higher level. As I currently envision it, more resources can only come from reallocation of resources by the parent. The only level that actually gets new resources from the economy, and talks to the economy actively, should be the OverallMilitaryStrategy. That object will be associated with the High Command of the civ. If the GrandStrategy, the object in charge of all strategy including economic, diplomatic, and military, etc. decides units should be built, it will give them to the OverallMilitaryStrategy. At least pending further discussion that is the way I think it should work.

I think the Resources that a plan has can include "virtual" resources, that don't exist yet, that are expected to appear at some point. I guess we need a special kind of Resource to cover this. The Resource itself would identify when and where it is supposed to show up. The plans with virtual resources probably would also need a special Objective called ResourcesAvailable or something. The logic for plan actions could then have the later actions of the plan predicated upon the ResourcesAvailable objective being fulfilled at a certain level. One trade-off that the plan could identify itself is "do we wait for All the resources, or go ahead when Most are available". This would then be encoded in the preferred set of Actions for the plan.

It is possible we will need commands like your BuildAndFerryTroops idea. But I would prefer to keep the economic and military planning as separate as possible. As I see it currently troops that are slated to be built in the near future will be allocated as virtual Resources that will go down the chains of command just like the ordinary already-existing resources do. It seems cleaner to me this way.

That's all for now since I've got company

[LDiCesare]

Virtual resources sound good.
I'd also like to point out another kind of asumption: Other civs. I know this will be far fetched, as it mingles with diplomatic ai, but there is one point I think is relevant now:
You could have 2 war plans: One being war vs. civ1 while at peace with civ2 (neutral), and the other plan where both are allied.
The asumptions are clear, but going at war against a third party should be totally forbidden in plan 1. You don't want ai's to fight their neighbours without thinking of diplomatic and long-term results. The point is in plan 1, you can even totally ignore civ2 if they are neutral, making computations easier. This requires forbidding to go through their territory. This also means that some asumptions or objectives (keep peace with civ2) be mandatory in the evaluation of subobjectives, but can be ignored at the level above:
Plan 1 will do its utmost to keep peace with civ2, Plan 2 won't bother, and the father plan will decide which to choose based on the plans results from its point of view, i.e. military + diplomatic.

[Mark_Everson]

Hi Laurent, I agree. Assumptions should allow for specification of diplomatic status, and its military ramifications. Or, as you say, we can also allow a "Don't Care" assumption that says you can either tromp through a non-allied territory or not. But this later is potentially complicated, and I need to think about it a bit... but later.

[Mark_Everson]

This is a restructuring and re-synthesis of the design for the AI. For now we are focusing on military AI. I am revising to provide a current version that is a better basis for coding. There is much repetition of what has gone before, but AFAIK all the discarded or incorrect stuff has been removed.

This is the AI architecture to support the functions we've been talking about in this thread. This document is a somewhat-detailed proposal for a key piece of the AI code. 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 presenting here is the base object in section A, and specific implementations of it in section B. 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 accommodate your ideas.

The overall function of the Plan starts with quantified information about objectives, resources and assumptions that it gets from the parent (superior in the AI hierarchy). 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 of the plan. 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.

A. Overall Structure of AI Plans

There will be two basic types of plans, Simple and Complex (or perhaps Compound). To promote clearer discussion I'll introduce the Simple plan first. After the introduction I will follow up with further elaboration on these objects and how the AI will use them.

A.1 the SimplePlan (even a SimplePlan ain't simple)

The SimplePlan Object has:
(an object X whose name is pluralized implies a collection of X)

ParentPlan (the one that told it what to do, and that it reports to)

Objectives (take city W, make peace with Celts) The objectives will each be rated for importance in some Dimension(s) (discussed below), 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 combination of achievement levels of the objectives. This can be a simple weighted average across a single dimension in the most straightforward approach. More on this down below. When Objectives are complete, plan reports this fact to parent using a TBD mechanism that will eventually be covered in "Communications Mechanisms"

Resources (5th army, 1000 Clash Cash, Character Alexander) Resources are Fixed as far as the plan is concerned. If the Resources fail to give good results for a variety of Actions the Plan considers, it is a signal to the Plan above in the AI chain that the resources aren't up to the task, and strategy should be reconsidered. Resources that a plan has can include "virtual" resources, that don't exist yet, but are expected to appear at some quantified time.

Assumptions (assume city defended by army of X strength, assume the Big Noses won't attack us for at least 10 turns) Assumptions can either come down from the parent, or be characterized by the Plan itself.

Actions are the actual details of what the plan Does. Actions include a reference to the available resources, and an instruction to actually do something with them. To evaluate the Success of a plan the Actions are simulated in a way characteristic of the particular type of plan. The result of one or more of these simulations is encoded in a Success object.

Success Provides a concrete evaluation of this plan as compared to others in one or more Dimensions giving likely level of success given the objectives, resources... To be concrete, for a one-dimension approach, we can define success in terms of monetary equivalents, and let the $$$ speak for itself. Parent plan sets the Dimension definitions that include a function of success on each Objective. Success should ideally contain results for more than a single simulation. This allows Success to report not only an Average result of the trials, but also the spread of the results, which is an estimate of the risk involved in a plan.

DetermineActions – object (one for each type of plan, in Java parlance its static) is a function with Rules/methods for selecting Actions. This is where the real tough part is. Generally consists of good rules-of-thumb for successful strategies and the mechanics for implementing them in the Clash system.

Simulator – object (one for each type of plan, in Java parlance its static) contains the machinery to perform the simulations for the plan. It will have a function that simulates n runs of the plan, and gives that information to Success.

Communications methods for transmitting success or failure to the parent, and to communicate that some item is a serious risk to the plan's success.


A.2 How Success is determined given achievement of Objectives:

What I want to elaborate upon here is how the level of achievement of an objective contributes to the success function. You can see specific examples of Objectives in section B below. Since we are first going to implement simple attack-management Plans I'll just pick two obvious objectives an AttackAreaPlan 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 will assume here that for each objective we can simulate / calculate a success level. Don't take the function characterization too seriously for now.

(1) Take City -- success = monetary value of city over some future period.
(2) Minimize casualties -- success = -Replacement cost of units lost

Here success in each area is determined by values of objectives that we'd need to determine thru playtesting. For a particular plan these are held in a Dimension object, which can represent any dimension we care to measure, like money, lives lost, etc. But lets say for now we phrase everything 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.

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)__total
A._100___-30___70
B._80____-40___40
C._10____-50__-40

In simulation A we capture the city intact, and remove it from our enemy's hands, with a value of 100CC (this represents not a one-turn value of the city, but something going forward into the future). Our troop losses for A have replacement value of 30CC. The net result is +70CC. But in A everything worked out great. Simulations B and C show other cases for what may have happened, and their aggregate value. Overall this is 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 quite big, indicating it’s a risky proposition.


A.3 More detailed structure of SimplePlan sub-objects

a ParentPlan (object of type Plan at higher level in the hierarchy)

Objectives – (FE TakeArea, AvoidTroopLoss) have a
* Name (for GUI use)
* Dimension objects (FE how to assess value of a mil. Unit, or captured territory) These objects are covered in more detail below
* getValue method that takes some object of Game State after a simulation of the Actions, and returns a value in one or more Dimensions that indicates level of success of the objective.
* isAchieved method that says whether objective has been satisfied

Resources - are Clash objects of various sorts. Commands, money, Characters... Virtual Resources will need to be explicitly marked as such. Perhaps we should have an "available" field that says "NOW" for normal resources, and gives a number of turns for the virtual ones. It seems this will be a 'wrapper' class that potentially any game object can be put in.

Assumptions - Any object that is used in the final evaluation of the plan (enemy forces…) can be specified as an assumption. This will be another wrapper class. I'm having trouble detailing this one out for the general case, will return to it later, and you can also see some specifics below in section B. comments welcome!

Actions – Will be Orders given to Resources. Each Action object will consist of one or more
*orders applicable to a
*Resource
(again, tough to put in a general fashion, see specifics associatied with different specific Plan objects)

Success -
* has a compareTo function per Gary's post
* collection of success values. From simulations, a number of different success values can be obtained even given identical Actions, Resources, etc. This saving of success values allows for assessment of ranges of results likely, characterizing risk.
* success as an absolute measure, rather than compared to another plan (perhaps success measures should also have an opportunity cost for Resources used). This prevents the case where marching an army a long ways off to conquer something would be preferred to conquering something of slightly less value a lot closer to home, and then freeing up the troops. Thoughts?)
*risk (returns a standard deviation of how much success result is likely to vary given luck of the draw and imperfect information, etc.)

determineActions - is the function with Rules/methods for selecting Actions. This will be very specific to the plan type. Its output is the Actions the plan will simulate to evaluate itself. Speaking of which…

Simulator – has a Lot of details under the hood and a
*simulate function that runs n simulations and reports results to Success. Actual implementation requires results of simulate being recorded in terms of Dimensions in the Objectives. Then the Success object is loaded with the values of dimensions we're using, which completes the result of a single simulation.
*simultateTurn(input: Parent Simulator) that can run a single timeslice of the simulation. It is Critical to enable Linkage between different plans. More about this after introduction of complex plans. Upon completion of all the simulated turns results are reported as at the end of simulate, and also reported to the parent.

Communications methods - No spec yet

Dimension (Objectives have 'em) - Since objectives have single or multiple dimensions for evaluating success we need Dimension objects. Dimension would contain:
*a DimensionType identifier - Some sample DimensionTypes would be FriendlyTroopStrength, EnemyTroopStrength , EconomicValue, StrategicValue.
*initial value in that dimension,
*final value (after Actions taken) This value will change upon different simulations of the Actions are undertaken
* getDimensionChange function that returns change of Dimension value after Actions
* getValueChange that uses parameters to convert a Dimension change to a single scale like CC
*parameters for getValueChange that define a net value for the change in dimension. For now a single value times the change in dimension value (After vs Before Actions) will suffice. Eventually we might want some more-complicated functions of initial and final state.
The parameters for valuing the Dimension could be set by the highest AI for whole civ, or tweaked locally. But care needs to be taken with these, since the evaluation of a plan depends directly on those values. You can get almost any value for a plan you want by tweaking these values, so they should Not be under control of any optimization done by the Plan itself.

If a multi-dimensional value is needed for a Plan or Objective, then the Dimensions can be put together in a collection with a getValue function that returns a Collection of Dimension instead of a float

A.4 Complex vs Simple Plans

In terms of the "tree" of strategy, a SimplePlan is a terminal "leaf". Its Resources are used in the performance of Actions that achieve the Objectives. But as we get higher on the strategy tree there is a need for plans that have sub-Plans (or child plans) in order to prevent a plan from getting arbitrarily complicated and intractable. If a Plan is complex, it can delegate the action to these lower-level plans. Plans with and without child plans seemed to behave in rather different manners in the initial design, so I've separated them. I think we need a ComplexPlan vs SimplePlan distinction.

A Complex Plan only does anything physical (Actions) through its child plans. I believe the child plans should be its only Actions. Its objectives can still be put in terms of basic Dimensions just like a simple plan. All that is needed is to aggregate the results from the child plans. A complex plan simply apportions resources to the children. The Resources are its to reapportion at will between child plans, but it performs no other action with the resources.

The ComplexPlan object has a spec that is identical to the SimplePlan, except the following:

Actions - All Must be Plans.

Simulator – In a Complex plan is where the Simulator really gets complicated. Simulation Together of the Actions (child plans) is especially important for things like the military sector AI. It is critical for correct simulation of use of reserves, value of feint attacks, and in general connection of different pieces of the action in different child plans. Of course, care must be taken to limit the scope of these connections or things may become computationally intractable. The Simulator will have methods for determining when simulation of the child plans Together is important. When that is the case, the simulate function will run the simulations for the relevant children together. That's enabled by the simultateTurn(input: Parent Simulator) method in the children. That function can run a single timeslice of the simulation. The simulations are run together timeslice by timeslice, until finished. There will need to be objects and/or methods in the Simulator to ensure this process is done smoothly. For now I will not specify these since the AI in the near future shouldn't include the extra complexity to implement this.

A.5 Flexibility and Timing in Plans

How to impart Flexibility to our AI plans? A ComplexPlan should IMO be able to have a logical-expression type structure associated with its Actions (child plans). FE an attack plan could have two children plans "Attack X" OR "Attack Y". For this flexible attack both children would be evaluated, and the final result would be the one that scores better at the moment. However, as circumstances change, the other attack might become better and that would switch to the active one. To make this work of course the two plans need a similar set of starting Actions, and it helps a Lot if X and Y are close to each other. Each turn, or even each tick when something changes, the two plans could be re-evaluated and the plan with the best score would be the one that gets executed.

We need to be able to prescribe a temporal order for Actions also. I don't think that will be a shock to anyone, I'll try to include that notion in the Plan spec next rewrite. Perhaps we will also need logical expression support… As in "only start Action 3 if Objective 1 is complete".

A.6 Resources and interconnection with Strategy

The AI plan for now is assumed to use Fixed resources. If the resources aren't adequate, then the parent should get the idea that the plan is lousy given available Resources. If even the best plans are awful, that is the signal the resources are a big problem. That would call for a change of strategy at a higher level. As I currently envision it, more resources can only come from reallocation of resources by the parent. The only level that actually gets new resources from the economy, and talks to the economy actively, should be the OverallMilitaryStrategy. That object will be associated with the High Command of the civ. If the GrandStrategy, the object in charge of all strategy including economic, diplomatic, and military, etc. decides units should be built, it will give them to the OverallMilitaryStrategy. At least pending further discussion that is the way I think it should work.

I think the Resources that a plan has can include "virtual" resources, that don't exist yet, that are expected to appear at some point. I guess we need a special kind of Resource to cover this. The Resource itself would identify when and where it is supposed to show up. The plans with virtual resources probably would also need a special Objective called ResourcesAvailable or something. The logic for plan actions could then have the later actions of the plan predicated upon the ResourcesAvailable objective being fulfilled at a certain level. One trade-off that the plan could identify itself is "do we wait for All the resources, or go ahead when Most are available". This would then be encoded in the preferred set of Actions for the plan.

A.6 Simulator

One Important thing that we'll need soon, I forgot to mention in the post above. That is an actual mechanism to simulate the results of a combat without affecting the Clash world. There are a variety of ways it could be done. We will need to discuss if perfect simulation is feasible, and if not, what a good compromise is.

A.7 How are Actions Determined?

How does a plan determine its Actions (or Child Plans for ComplexPlan)?
*SimplePlan - looks at objectives and Assumptions and formulates from there using a determineActions method. FE for AttackAreaPlan the actions could be calculating a path to the most attractive economic or strategic target in the area, and getting the default minimum odds at which to attack from its parent.
*ComplexPlan – looks at overall Objectives and Assumptions. DetemineChildPlans function looks for good children to help it achieve its aims. Many children will be formulated based on the best rules we can provide. Then children, and groups of children, that satisfy the overall plan are evaluated. Finally, a best set is selected based on maximizing value from Objectives. (Perhaps the next-best set, or the few best non-selected ones are saved for future consideration?) FE a SectorStrategy plan will have AttackAreaPlan, DefendAreaPlan and ReservePlan children. If the Attack Objective is rated highly the search will focus on finding appropriate areas to attack in the region under control of the SectorStrategy. (The region should go fairly deep into enemy territory.)

Continued...

[Mark_Everson]

Rules we give it will look for good targets, and AttackAreaPlan children based on those rules will be created. Then the different sets of children are evaluated (by simulation) for success, and a single set of children is selected as the preferred one.

Once Actions have been determined and a simulation has been carried out, a report saying what the best result is will be reviewed by its superior. If the result is not satisfactory, alternates can be proposed by the superior, perhaps with different weighing on the objectives. So a SectorStrategy plan with heavy weight on Attack may return only lousy, losing values. That is the signal to the parent strategy (OverallStrategy) that this plan is flawed and should not be carried out. Perhaps a plan with the same resources, but more oriented to defense will suffice. This would be the case if the enemy has superior defensive positions available) Or maybe even a defensive posture won’t help. Then the deal is “you are in Serious Sh*t, time to take Extreme action using any military, economic, and diplomatic means possible.” That could consist of OverallStrategy stripping another SectorStrategy of Resources to plug the gap, or changing GrandStrategy handling of the economy or diplomacy. Perhaps it is time to accept that humiliating peace settlement, and live to fight another day.

One bane of scenario writers is if they change something and the AI doesn't change its behavior to reflect the new reality. One reason our AI will be better than the run of the mill variety is that we will use in-game simulation to guide the AI. The result is that if a scenario designer changes a parameter, or throws in some oddball unit, the simulations will guide the AI to the correct use of the unit., and understand any change in its combat power trivially.

A.8 Where do Assumptions come from?

I can envision two types. Assumptions that come from the parent, and from the Plan itself.
* The from-parent ones would be used to probe overall possibilities, or ensure that the children that are being compared are all playing with the same assumptions. An example of probing possibilities: “Assume you are facing 2 armored divisions”. While another child of that parent would be given “… 4 armored divisions”. The parent can then decide how robust the plan is based on the value produced by each of the plans.
* The other type of Assumption is self-imposed by the Plan and just says what view of the world it is taking for its calculations. The use would be to maintain a record of the plan assumptions that can be compared to a different plan, or the same plan at a later date. I’m not sure the second type is critical in the short term, but I think it will be needed long-term.


B. Specific Plan Types for Military AI

Here is my attempt to move the AI approach forward towards something specific enough to start coding. It ain't there yet! But it is getting better with each revision. I have left out some of the communication mechanisms that will be needed between Plans of different levels.


Now, the first specific Plan:


AttackAreaPlan (Attack and take one or more squares)

a ParentPlan - SectorStrategy

Objectives - TakeArea, AvoidTroopLoss, EnemyTroopLoss, AchieveByTurn, AssembleResources

Resources - Commands

Assumptions - EnemyForces

Actions - MovementPath(s), Orders specifying when to fight and when not

Success

DetermineActions – see below

Simulator – see below
*simulate
*simultateTurn


AttackAreaPlan Object Details

a ParentPlan – SectorStrategy
(All methods or field not explicitly mentioned are assumed to have default behavior)

Objectives -

TakeArea - Secure control of an area that is a collection of MapSquares
* Name ("Conquer Silesia")
* area - collection of squares that define area to be conquered
* Dimension EconomicValue - value of captured square per unit economic value (may need more refinement)
* Dimension StrategicValue - strategic value of conquered squares(when map AI functional so strategic value can be better assessed)
* getValue sums econ and strategic value over all conquered squares. Or perhaps adds for all conquered and subtracts for any lost from starting area
* isAchieved method returns true when all of area defined is conquered.

AvoidTroopLoss
* Name ("Military Losses")
* Dimension FriendlyTroopStrength (How to assess value of a military unit? For now we should just use creation cost as a simplification)
* getValue calculates army cost-to-build after executing Action and subtracts initial
cost-to-build.
* isAchieved method (not sure this is needed here, since everything is 'shades of gray'. If we want to add another parameter that says anything more than X is unacceptable, then this method again makes sense in this context)

EnemyTroopLoss
virtually identical to AvoidTroopLoss

AchieveByTurn
* Name ("Turn 38" or "340BC")
* Dimension Timing specifying how much early or late completion affects value
* getValue returns bonus for early completion, or penalty for late.
* isAchieved is straightforward

Resources - Commands used in attack plan

Assumptions – EnemyForces. for now we should just weasel on this and let the AI see everywhere, and assume things don't change with time. Perhaps forces just outside area should be counted also.

Actions -

*Path(s) Just path or paths attackers will follow. The paths I talk about here are the complete paths from where the TFs/Commands are Now to their final destination.
*Orders specifying when to fight and when not. FE "don't attack at less than 2:1 odds". Also includes other orders like leaving a garrison at a critical crossroads. More TBD

Success - use basic Success above.

DetermineActions - For now: Group forces first in city nearest to objective. Use cheapest path to objective. Objective should be at most several contiguous squares. Require that troops have 1.5:1 or better adjusted odds to attack (I'm not sure how to phrase this in terms of the military system since effective power entails Attack, Defense and Health of both armies. Any help Laurent?) We will cheat and allow the AI to see the enemy troops, even in the black.
Future: This can get quite sophisticated. Information about enemy dispositions will need to be obtained, or assumptions made. Paths that avoid enemy forces and good defensive areas for enemy are a must. Paths that could have any of a number of objectives would be preferred since they can confound an enemy defense. Launching of small feints could be included. Determination of supply situations along different routes is an important additional consideration. There are more considerations, but lets get the basics done first!

Simulator – For now: Assume that any enemy troops on line of march are bunched together and fought as a single battle in square with largest number of defenders. Also treat any enemy units within X squares (say 3 or distance to target, whichever less) as lumped into the defense.
*simulate - Just run an ordinary military battle to simulate. Care must be taken to copy the units first so that the simulation doesn't affect the actual units in the game. Same may be true of square itself.
Future: More sophisticated handling of individual enemy forces rather than assuming they can all unite. Use notion of enemy possibly bringing in reserves that are close enough. In fact a general simulation of what alternatives the enemy might be pursuing is a rich area for the long term.
*simultateTurn – As above but step-by-step to account properly for appropriate use of reserves upon setbacks. This would precipitate a tactical withdrawal until reserves can get there. Coupling individual attack and defense plans in simulateTurn could be quite challenging, but I think we can do a basically good job with it.

DefendAreaPlan (defend given area)

This will have many Objectives and other objects in common with the Attack version. However, unless the area is only a few squares this one will almost certainly require child DefendAreaPlans. So we might need two versions of this, one a Complex, and one a simple plan. Now for some of the differences with attack:

Trivially, we will have a DefendArea objective rather than an AttackArea
There could also be a ScorchedEarth Objective, and probably some more.

Assumptions - These are even more critical for good defense than they are for attack. One obvious one is enemy troops that are nearby to the area, and heading this way. Lets start with that for simplicity. Once enemy troop strength is established we need to worry about where they are going. I think we should spec this out further as we go along.

DetermineActions – this one is Tough, defense is much harder than offense to do in a smart manner
Near term: It’s a little easier than the long-term problem, since we'll cheat, and let the AI see the player's troops. Even if they are in the fog or black area. But the AI would not see movement orders. Since I think explicit handling of reserves is too complicated for the first pass, defense will be primarily point defense of cities. (If we can get a troop intercept order then the city defenders can go out to attack troops harassing the countryside if danger appears low.) I think the default allocations (when enemy troops are say greater than five turns' march away) should be inversely proportional to distance to the enemy's nearest city. We will need to figure enemy attack potential for each target as enemy troops get closer. For a start this can be done simply by counting enemy forces within an X-square radius. X might be 6 or so. With an explicit threat, troops should be re-allocated proportional to the threats as weighted by attack power or some better metric. This approach is still susceptible to being fooled by a player. The player, by approaching on a line that is roughly equidistant between two cities can cause the AI to split its forces in half, and then attack only half. But its still a good step in the right direction.
Long term: Pickets to detect enemy movements will need to be sent out if other game options to push back the fog aren't available. A strategic reserve will in many cases work better than point defense. Strategic strong-points along the border can be garrisoned to slow an enemy advance and give more time for mobilization of reserves. I'm sure there are more items that should go here, but in the interests of time, I will move on.

Simulator – Near term: assume all enemy forces within range of each city attack it massed together. This will be a conservative estimate, since some enemy units will be counted for more than one attack.
*simulate and simultateTurn are similar to the attack versions

ReservePlan (reserves for undetermined future use)

The idea is that reserves can be drawn upon, giving a negative value from Success in the ReservePlan. If the Plan that wants to use the reserves has a Success gain large enough to justify the removal of the units, then the transfer will get approved (Ideally after all Plans that want them have their chance). Whether we need a method requestTransfer(Command) that returns a value, or whether this is handled some other way, I will leave to Gary's Judgment (lucky you! )

For now I am leaving this one vague since I think we won't use it in the first wave of AI!

ParentPlan - SectorStrategy

Objectives -

AvoidReserveDepletion
* Name ("Reserve Depletion")
* arguments passed in that are used by getValue (FE how to assess value of a mil. unit. in reserves. For now we should just use creation cost as a simplification, but this can be Much more nuanced later. Reserves in the right spot can have an importance Many times their base construction value.)
* getValue calculates army cost-to-build change after executing requested Action of removing the reserves.
* isAchieved method (don't know about this one here. maybe this points to us needing two high-level Objective classes, one that is Achievable and another that isn't)

Resources - Commands used in attack plan

Assumptions - N.A. or maybe this can be where the remove reserves order gets put in?

Actions - N.A. or maybe This can be where the remove reserves has its influence?


SectorStrategy (Plan for a big chunk of the map, like a front in modern warfare)

ParentPlan - OverallMilitaryStrategy

Objectives - Pretty much these are the union of those for attack, defense and reserve plans. Possibly Dimensions for Attack and Defense versions should be different to allow a strategic attack/defense balance to be adopted. If there is no distinction between attack and defense one can have bizarre things like two sides switching countries being weighted equally than retaining their original countries. Other ideas?

Resources - Sum resources used in all Child plans

Assumptions - This is an Enormously complicated issue. To be done right, SectorStrategy will need to estimate enemy forces and their disposition using all info available, formulate potential enemy actions, and then see if the Child plans handle those circumstances ok. For now we will just be dumb and happy and make no Assumptions, leaving estimated enemy disposition to the Child plans to guess. Could include default Orders specifying when to fight and when not. FE "don't attack at less than 2:1 odds". Another Assumption could be strategic disposition as mentioned in Objectives above.

Actions -
* the Child plans themselves (AttackAreaPlans, etc. this is where the action is)

Success - use basic Success above, or something fancier depending on what we think we need.

DetermineActions – For now:
-1. Examine the strategic space (for now do every turn, can be relaxed later)
a. Evaluate a strategy with 100% of resources in DefendAreaPlan.
b. Evaluate a strategy with 100% of resources in AttackAreaPlan. Attack an area that "looks good". Looks good = minimum of Defender Power * distance. It is necessary to have a DefendAreaPlan child with zero resources as noted above.
c. Evaluate a strategy with 50% of resources in each.
Comparison of the plans a-c crudely maps out what the risks and opportunities are. It can be ignorant of threats just beyond the DefendAreaPlan distance threshold for seeing enemy troops, but we can live with that for now. (One way to handle that short-term is to increase the look-out distance from one to several squares randomly, which would make it tougher for the player to formulate strategies using the fixed distance against the AI). Once the strategic space is crudely mapped, try a strategy that is halfway between the two best scorers. Call that d. Pick the best strategy from a-d. If two are "close" in value pick one with less risk. Even this simple approach can be time-intensive. We will look at tradeoffs and simplifications needed if necessary at a later date.
Future: attack/defense balance can be specified by parent. There is Lots of potential for examining the strategic space in a better way. Simulation of enemy attacks even when none is apparent is a Must long-term.

Simulator – I think this is straightforward since all action happens in the child Simulators
*simulate will eventually run simultateTurn in the children to allow linkages between plans.
But there is one point I need to bring up. I will put it under Detail of Simulation below since it is of general scope and doesn't pertain just to this plan.


OverallMilitaryStrategy (Plan for all military endeavors of the civ)

a ParentPlan - GrandStrategy

I think I will leave this one vague for now! I don't think we need it as other than a placeholder for the immediate future. OverallMilitaryStrategy has complexities of its own. The parent, GrandStrategy, is probably The hardest part of the AI. As the lower levels of the AI are coded and actually used, I expect things will come up that will naturally go in this object, or its parent. When we get to that point, if not earlier, I'll get a spec out for OverallMilitaryStrategy and GrandStrategy.


GENERAL NOTES (some will be put in the discussion above as of the next rewrite)

Just to get it in the queue for coding we will need a Thread to run AI in the background. The first implementation of these ideas can probably do without it, but we will need it by the second AI wave I think.

We need Dimension-evaluation methods from the relevant models to figure changes in Dimension needed to evaluate an Objective. FE the economic model needs to be able to facilitate calculation of an EconomicValue dimension for any hunk of territory presented. This would then be modified for Who owns it since people in a civ they want to be part of will generally be more productive than ones in a civ they hate. This function should be fulfilled by each Dimension object.

Detail of Simulation (will eventually be moved up to the A. section)

Complex plans will probably eventually need to have two paths for simulation available to them. One is the detailed approach that I'm assuming above, where simulation gets passed down to all the children. That method will be Very computationally expensive, and should be used only for formulating final detailed plans. There is need for a "quick-and-dirty" simulation alternative when only higher-level concerns are being planned. The second approach will need to be hand-crafted for each plan type to capture the essence of what might happen, while using only the most important details. I have ideas for some of these issues, but will wait until later to elaborate. The way I envision this working is that when a simulate function is started it can optionally include the type of plan where you only want the quick-and-dirty one. FE when the GrandStrategy AI is looking at broad alternatives, it is not needed to bring the simulation down to individual attack and defense plans. The scope is much broader. When the GrandStrategy is thinking general strategic thoughts (as opposed to handing down the final plan) it might say that it wants simulation to stop at the OverallMilitaryStrategy level. IMO it will be very common to order simulation to terminate at the child plan level in most cases. In the long term we need to use feedback to compare the value determined for the crudely-fashioned plans to the value when a more detailed simulation is done. If the crude approach tends to over or under-estimate the results for a particular Plan, then a fudge factor can be thrown in to crudely correct. Note that when I'm talking about the fudge factors, they would apply potentially both to a Type of plan, and also to specific plans.

Here's a quick example to make this more concrete. GrandStrategy for France is considering attacking the Swiss with whom they are neutral at the moment. The Simulation is going to terminate at the OverallMilitaryStrategy level. Just looking at troop numbers the Swiss might look like an easy kill, since OverallMilitaryStrategy doesn't know about the terrain. When this strategy is selected as the best, a test will be run down to lower levels. SectorStrategy should know about the terrain effects. After the tests it will effectively say "Uh, boss, this is Not a good idea, can't be done with the resources you're giving me." What we need is a way to file that information in the Simulator object for OverallMilitaryStrategy. Then the next time a quick-and-dirty simulation is called for, it can adjust any "Attack Swiss" orders appropriately. This stuff is Far in the future for the AI, but I'm bringing it up now so that the Architecture can be made so as to accommodate such a thing. How to handle this sort of information in a sensible way is a Very severe challenge for the future.

[LDiCesare]

Mark,
Sounds good.
Here are a few critics:
A.2

2) Minimize casualties -- success = -Replacement cost of units lost

Should be a bit more than that, as building units takes time (add maintenance cost for the number of turns needed to build new unit?).

A.5 Complex plans:
We should probably have 2 complex plans objects, AND plans and OR plans. That way you have the logical structure through extra layers, and it is easier to prune a OR branch than maintaining inner structures.
From A.8, it also appears subplans can be used for various simulations, based on asumptions. These plans should be a variant of OR, like UNKNOWN_OR, since there won't be a choice between them, but they are all to be evaluated together to give the parent plan some input as to what sub plan to implement.

A.6 Now a proposal for simulations:
The code runs with random numbers. I suggest simulations don't use the same randomizer, so it would be easier to simulate good and bad luck. In the military, it is easy to know when an odd is for good or ill. We could use an even-distributed pseudo-random for the "average" result, and biased pseudo-randoms to simulate good and bad luck, thus getting a more accurate results distribution than by running lots of tests. Well-made randomizers could allow to simulate with only 3 or 5 points and give results you would otherwise need 10 runs to have, or give more accurate results than truly random 3 points.
For example, we could do 1 simulation with average random of 0.5 in (0-1) range, and one with 0.45, one with 0.55, then bias the whole thing by giving more weight to the 0.5 than to the others. I bet a 4-point with 0.45/0.48/0.52/0.55 would be a good simulation, as 0.5 may give unstable results. I should test the figures on actual fights to get an idea of the importance of the random factor, but won't code anything unless the principle is agreed on.

B: AttackAeraPlan lacks notion of terrain/map knowledge, as I can't see any assumption about the path to get to the area. There should be an asumption that path to get there exists and contains X enemy force, in addition to the enemyforces in the aera itself. By path I mean path from outside the area to inside, since inside paths are part of actions.

B. Determining odds to win:
Argh. Actually, the factors that could be used would be health*attack*defence*armor, but armorpen changes that, and distance strength allows for support fire and damage before closing so it is a bit complicated. For ancient times, distance can be ignored or factored in as 10% of fight, with melee being 90%, but it will be very different when fights take place at longer ranges, and when armies have different favourite ranges (e.g. impi/rifle). For the moment I can come up with something for distance that will not be too much off-mark, but the ratio will just be a rough estimation.

[Mark_Everson]

Thanks for the feeback Laurent:

Originally posted by LDiCesare

A.5 Complex plans:
We should probably have 2 complex plans objects, AND plans and OR plans.

Sorry, I don't really get it. If a complex plan we ORed with another then it would just be done one level higher where they have a mutual parent. I'm sure I'm missing something from what you mean, but haven't a guess what it is...

A.6 Now a proposal for simulations:
The code runs with random numbers. I suggest simulations don't use the same randomizer, so it would be easier to simulate good and bad luck. In the military, it is easy to know when an odd is for good or ill. We could use an even-distributed pseudo-random for the "average" result, and biased pseudo-randoms to simulate good and bad luck, thus getting a more accurate results distribution than by running lots of tests.

Sounds good for long-term optimization! I would wait on it for now just to keep things simple.

B: AttackAeraPlan lacks notion of terrain/map knowledge, as I can't see any assumption about the path to get to the area. There should be an asumption that path to get there exists and contains X enemy force, in addition to the enemyforces in the aera itself. By path I mean path from outside the area to inside, since inside paths are part of actions.

The paths and geographical knowledge are already meant to include Any intervening area. Not just actions inside the targetted area. The paths I talk about are the complete paths from where the TFs are Now to their final destination.

B. Determining odds to win:
Argh. Actually, the factors that could be used would be health*attack*defence*armor, but...

Thanks! Something simple will do for now. In the long haul some refinements are of course needed. It won't have to be perfect though, since knowledge of enemy troop strength before a battle is never all that great anyway.

[Mark_Everson]

I have edited the model post (Feb 11) to include some more specifics at the end. If you read it yesterday, the only additions are in the last part of the document, starting with SectorStrategy. Unfortunately the whole thing wouldn't fit in the two original posts, so I have tacked on the concluding remarks here...

Conclusion, for now

In writing this, there are many issues that I've glossed over. Weaknesses of the near-term AI approach outlined here are apparent in several areas. Nonetheless, I think it’s a solid framework to move forward with. I believe the most important defects, which surely are there, will mostly be found as coding, and actual use of the AI, go forward. Although if you can spot big ones now, more power to ya'!


That's all for now. Opinions, especially high-level ones, or ones about a near-term implementation that appears broken, are solicited!

[Plutarck]

One excellant idea I heard (I think Vel mentioned it as a suggestion for Civ3 somewhere, and I really liked the idea) was that of a Playbook (like in football). Now turning it into my idea...


The AI can have Plays made available to it (added to it's PlayBook), which it can use as a high-level way of planning invasions/defenses. This is one thing, more than any other, that AIs seem to suck at in every game I've played. It can build up forces, plan a base, and collect resources with the best of 'em, but when it comes to actually launching an attack...man-o-man, do AIs suck.

When considering how human players play, they use abstract plans, much like a football "Play".

The AI could even, one day in the distant future, develop and refine Plays on it's own by generating a history of all the decisions the AI made during a game, then (perhaps with assistance from a human) evaluate the decisions it made and find out how some of it's plans worked. So if something went really Badly, but something else went Well, and it wasn't just random-number luck in either case - it could try a different course of action, and thus learn from previously played games.


But in the more immediate future, a Play would consist of something such as "If Target has some power amount in comparison to me in the late middle ages, and I think I have suchnsuch chance of a successful campaign against them, then act really nice to Target and perhaps give them (ultimately useless) gifts while building an attack force of high movement attack units and a garrison force to defend areas I take, but leaving behind suchnsuch sized Sally Force to deal with any counter-attacks or counter-invasions...then Kill Them."

There really aren't that many Plays that even humans use, but AIs rarely even manage to use those effectively. A few examples would be:

Raid-n-Sue: Hit a weaker country fast and hard with a relatively small attack force, then move in a good defense force to defend from a counter-invasion, then use your superiority to negotiate a quick and beneficial peace agreement.

Scorched Earth Blitz: Attack with a large and exclusively fast attack force, raping and pillaging (and razing) whatever you take. The key is to keep moving and do as much damage as possible to cripple the enemy force before they have a chacne to counter-attack, then retreating back to your own (defended) territory before you take any heavy losses.

Then you can later form a more standard attack force and conquer the force you are now much more powerful than.

Diversion, Attack, Assault: Launch a small diversionary strike, but large enough to draw some forces towards it. Then land your previously unknown forces from the sea (or from land if your diversion was via sea) in a relatively distant local to cause your enemy to have to pick where he'll send his forces.

Then after waiting a bit to give him chance to think that the main invasion was coming from the sea and going there, and possibly tryin to take back what you got in your original invasion, throw the rest of the units you held behind at the enemy a little bit away from your diversionary force, and maybe adding a few defensive units to your diversionary force to keep it from being crushed.

The result is leaving a very good chance that your enemy will be totally confused as to where it should send it's forces first, possibly forcing an error of spreading too thin and loosing on multiple fronts, or sending too little defense to some fronts and overdoing others causing hard losses in the those undefended areas.

Requires a pretty big force to pull off, and is risky, but if the target bungles defense it could loose in a Big way.



And many other such plans. Just even basic plans, even if they are sometimes overly rigid, would really take a lot of load off the AI to simulate things that might happen in the future and make it seem a whole lot smarter.

There are also plenty of thumbnail sketching type tactics that are used by players to determine such things as chance of success or failure, and such simple rules could be used in the near-term in lieu of more sophisticated solutions.

[Mark_Everson]

Hi Plutarck:

I think we can put Playbook sort of stuff in the DetermineActions object. I had stuff like that in mind too. But we need to get things to the basics before we push too much on the sophisticated stuff . When the time comes though this sort of thing will be critical to doing a good job in an acceptable amount of time.

[Mark_Everson]

Hi Everybody:

I am bumping this up because I could Really use some comments or criticisms of the AI Plan proposal starting with my post of 13-02-2002 22:56 . Since the last enlarged revision I've only heard from two people! Even if military AI isn't your thing, the framework will be used for other types of AI too, so its important to hear if it sounds adequate for those purposes too.

Decent AI is supposed to be one of the core things that makes Clash unique. Please read it over and give me your thoughts, especially on what you think is missing, or inadequate. If its great, I'd like to hear that too .

Thanks,

Mark

[Mark_Everson]

I STILL would really like to see some comments or criticism on the main proposal several posts up. You can't miss 'em there are two about as long as your arm.

Anyone? I'm handing out three official Clash brownie points and a gold start to anyone who comments...

[LDiCesare]

Brownies?
Back to A.5: We can do it as you said, considering AND and OR to be various levels:
You have a plan like:
-(Attack Sicily AND Attack Normandy) OR (Attack Normandy) OR (Attack Sweden AND (Attack Denmark OR Attack Spain))-
you would describe it as a OR complex plan contain three sub-plans, one being a AND plan
made of a simple plan and a OR plan.
That's what I ment, do I have brownies?

Another point:
Does the evaluation function change with external factors?
Considering the appeal of an attack against a country will vary based on preferences which can vary based on government, a government change can turn a successful plan into a not-desirable one. I think of a policy like: "Don't use nukes" rather than "Don't go to war", which has an effect on the envisioned strategy. I am not sure whether other more strategic peace/war policies should intervene at this level.

[Mark_Everson]

Hey Laurent:

Sure, you get brownie points for the comments/question. Unfortunately the only brownies I'm giving out now are virtual

The complex plan logic would work pretty much as you say.

I am not sure I get completely your example on externalities. Things like government changes would be most likely to cause a change in the diplomatic AI that might make peace more likely. I don't see a big effect of a government change upon actions on the ground. The way that would happen would be that GrandStrategy could call for a pause while the diplomatic situation was being renegotiated. Hope this adresses your issue.

Thanks for the comments/questions!

[RM]

Mark:
I read your posts, but I have probably missed some of its details. Anyway here is some thoughts/suggestions.

First of all I would like to say that I think the plan tree idea is very good. Below is a suggestion of how to make it more stable (but it is all just thoughts, so I might be wrong of course). It will be mostly relevant for military operations, rather than grand strategy.

About success and objectives:
I think this is a simpler variant of the model, than the one you proposed (if I understood it correctly, which I am not sure of), but I think it is less gullible.
When a plan is given resources, it should both be given resources to be used, but not expended, and resources to be used, and if necessary expended.
For example, a plan to attack city A is given 8 units of infantry, but should only accept to lose 4 of them. If more is killed, then the AI should reevalute if the plan should be transferred more resources or cancelled. If it is cancelled, that might also makes one or more higher level plans failures as well.
Success is only when the mission goal is accomplished. A plan is always either not yet accomplished, failed or successful. Perhaps a time limit should be a goal for some plans.
The value of a successful plan is decided BEFORE it is put into action, not during.

About the flexibility:
Redeploying can be the death of any tactic AI if it is not very carefully implemented. I remember an old tactical wargame that I used to play. Its AI was OK, when I engaged it on one front it could give good resistance. But once I learned to engage it from two fronts I always beat it, because the AI kept moving lots of units back and forth between the fronts to respond to my moves, rather than using them to attack my units. It was not unusal to see the AI move a tank to one front, let it fight there for two turns, then suddenly disappear into the fog of war, only to three turns later appear on the other front. For those three turns, the tank had only been moving, when it would have been more useful fighting, even if perhaps not at the most optimal place.
So I think it is important that the AI actually tries carry its plans through, rather than starting on a plan, then decide it really wants do something else, and then change plans again before anything is fulfilled. A too reactive AI is an AI that is very easy to trick. That is one of the reasons for having a simplified success-rating, that is not reevaluted often.

Another reason is that if you use a plan tree, is that every level of the tree wants to be sure the lower level plans actually do what they are supposed to, not go about doing something else that turns out more economical, but fails to achieve the main goal. That is also the way it works in many military organisations. If the division staff orders a battalion to take a point, it counts on the battalion to take the point, even if it gets an opportunity to kill half the enemy army instead. Because if the battalion does not take the point, it might pose a threat to other plans the division staff has in mind, but the battalion does not know of.
Suggestions upwards in plan hierarchy should be rare, or at least only approved of, when it is MUCH better than the original objective (again, to avoid AI baiting).

Reserves:
A higher level plan should in addition to lower level plans have some resources in reserve that can be transferred to plans that do not fulfill its objectives, or seem not to be able to fulfill them. The primary communication upwards in the tree should be to request more resources. They should not take resources from a plan, until it is either completed or abandoned, to ensure nothing is done half-heartedly, or the player tricks the AI to redeploy troops.
When a plan has transferred all its reserve resources to its child plans, and still have one or more unfulfilled child plans, it has failed, and should be reevaluated.

Intelligence (as in military intelligence):
This is could be a very difficult thing to handle. It is important for the AI to do good recognaissance in advance so it knows what it is about to face, since the plans (according to my suggestion) should not change that often. The AI should for example not go to war, unless it thinks it has good chances to win it. It should not invade an area unless it plans to really take it.
Perhaps some higher level plans should begin with a ”scout area plan”, and first when it is finished decide a few child plans to split its resources between.

About OR-plans:
I think they are only viable before proper recognaissance is done, just to keep some flexibility, but the AI should then commit itself to specific tasks that it really tries to achieve.

Looks like the post turned out much longer than I planned.
To sum up everything above: let the AI stick to its plans and follow them through, unless they are too costly or higher level plans start to collapse.
One of the biggest mistakes in war (and sometimes in computer games as well) is indecisiveness.

RM

[Mark_Everson]

Hi RM, thanks for all the detailed ideas! I think your analysis of things we need to watch out for is spot-on. I have to admit that I do believe most of the problems you're worried about won't be as bad as you fear, but maybe you'll be the one that's right...

I have to admit I hadn't thought much about intelligence about enemy forces and dispositions yet. And how to get them by scouting, spying or whatever. Need to cogitate a bit more on that one.

Since coding here isn't imminent, I'm just going to think about your suggestions for a bit, and see what others think. Thanks for the coments, and for being willing to wade through it!

[LDiCesare]

Intelligence gathering:
We could have a general factor about assumptions, like if they are 10% sure, 50% sure, 90% sure. That way we know if the plan is confident in those assumptions. A plan would not be allowed to fire if its assumptions are less than a given figure (60%?), thus one sub-plan would always be "Make sure assumptions are correct/we have enough intelligence". The minimum confidence could vary based on the returns of the plan: You can gamble if you believe it will reap huge benefits.
How to increase the assumptions confidence is another problem, but it could be done by:
-spying
-exchanging maps/knowledge with neighbours (typically the Germans in early 20th century worked a lot with French and thus knew their defenses on the Maginot line very well)
-sending scouts (planes being excellent for that).

[Mark_Everson]

Hi Laurent:

You've raised some important issues here! Sorry it took me so long to respond...

I'm not sure I like your approach, but don't have anything really good to offer at this point. I guess my preference is to wait and see how the AI works out with plans based on different levels of information, and then determine how the AI should use that information in combination with its specified risk tolerance.

[Urban Ranger]

Dropping in...

Interesting thread so far, though my concern is your efforts are heading in the wrong direction.

To me, the important thing about designing AI is not how to do it, but what needs to be done. For example, Computer Player A just runs into Player B. Now what? How to proceed from there?

It seems that there lacks a clear (or vague) definition of what a computerised emperor should do. What should it do when invaded? When will it want to launch its own invasion? Will it attempt to colonise the new continent just discovered, or will it do it later? Will it be an expansionist or a perfectionist? Or will it shift objectives around as situations develop?

[LDiCesare]

Hi Ranger.
Interesting question. I think we are not in the wrong direction because that is what needs coding, and once you know how the machine thinks, you can give it higher level "orders".
To answer partly/vaguely:
I think AIs have to behave differently (have a personality) to be an interesting challenge. This can be modelled by the ruler and/or ethnic group having some preferences about warfare, research, expansion...

Now how does the AI handle contact?
1)Appraise other civilization: - military strength - economic strength - scientific advancement - population - attitude - other civs relationships - map
I insist that there must be a way to gather this information, as every simulation depends on it. Trading for such info and scouting are both acceptable.
2)Based on that info, check a list of possible attitudes:
-Attack them -Prepare to defend from them (subplans: Build defense force/offer tribute) -Trade with them -Ally with them -Threaten them into tribute

Now each of these options is a plan unto itself, albeit high level one, as described per Mark. As long as no clear attitude has been decided, it is probable that few resources would be used to simulate an attack plan. It would do just to see if it is worthwhile, which means the returns of the attack plan would be taking lots of population/resources. Probably very few options would be run.
NOTA BENE: This means we have to tell a plan how many options at most it can envision, so it will not spend hours of processing power trying to accomplish something which is anyway highly unprobable.
Once an attack plan is simulated, an idea of how much damage can be dealt to whom in case of conflict is obtained. This leads to decisions like whether or not to go to war, whether or not to demand tribute and how much, or if it is a good idea to have trade/science relations with that neighbour. Considering these 3 options as exclusive, and forgetting alliances for a while, each can be seen as a plan with a total revenue from it (cost/gains of war, cost/gains of tribute, cost/gains from trade). The best plan is then chosen.
Note that 'best' depends on the cost, which itself will be biased based on the preferences (militaristic/trading/...). A civ that values conquest could multiply by 2 the result of attack plans and divide by 2 that of trading partnership for instance, and vice versa

I bet Mark will have a few things to say.

[Mark_Everson]

Originally posted by Urban Ranger
Interesting thread so far, though my concern is your efforts are heading in the wrong direction.

To me, the important thing about designing AI is not how to do it, but what needs to be done. For example, Computer Player A just runs into Player B. Now what? How to proceed from there?

Hi Urban Ranger:

Thanks for looking it over, and your comments. Sometimes criticism is much more important to hear than complements.

But in this case you're Wrong, Wrong, Wrong!!!

Sorry couldn't resist... I would have put the [monty python] tag around the "Wrongs" if it wouldn't have spoiled the effect...

Anyway, silliness aside, you are very right that we need all those details. But what I think needs to come first, and Laurent talked about this some too, is a framework in which to handle it. We've each thought a lot about these things, and could certainly have long profitable discussions about 'em. That the sort of thing we in fact did a few years ago in the project. The problem is that lots of things that are far from appearing in the game get lots of discussion, and progress on the actual coded game slows enormously. So for now we are mostly focusing discussions around:
1. What has been implemented, and how to improve it
2. What is soon about to be coded, and what to do on it.

There are two major game components in Demo 6, military and economy. The economy can Almost run itself at this point in the game, leaving the big hole in AI as Military Tactics and low-level strategy. That's why we have in this thread been discussing the framework and how to make it work for D6-type situations. So the most useful things you could contribute at the moment are ideas as to how to do those things right. But I understand those aren't the most glamarous or interesting parts of the AI challenge...

So, UR, in terms of the details you are looking for, we will start out with some AIs that are ideas of our own, but we are hoping that refined strategies come From Players. That is one of the big advantages we have of doing a completely open series of alpha and beta releases. For relatively straightforward military tactics and strategies there are Already some details under DetermineActions parts of several of the plans. You may well have missed 'em since they are in amongst a Lot of text. Just search this page for DetermineActions and you'll see 'em fairly quilkly. Would like your comments on them.

It seems that there lacks a clear (or vague) definition of what a computerised emperor should do. What should it do when invaded? When will it want to launch its own invasion? Will it attempt to colonise the new continent just discovered, or will it do it later? Will it be an expansionist or a perfectionist? Or will it shift objectives around as situations develop?

We hope to get to some of these in the coming months. But without diplomacy working, its hard to refine what you do with an invasion, beyond the straight military stuff. But dealing with invasions is something we will be doing at least at a purely military level in the not-too-distant future. There are already some comments on these ideas on the AI web page near the end. In the part where I talk about fighting on a 'front' IIRC.

For the high-level sorts of planning and evaluation you talked about its the critical stuff that goes into the DetermineActions part of a plan. As Laurent said, we'll have a bunch of settings for each player that determine aggressiveness, risk aversion, and a number of other tendencies for the AI. These tendencies will be used in two places:
1. Shaping DetermineActions with modifiers. The pacifist civ won't look at many warlike alternatives.
2. Weighing the results that are simulated as Laurent said.

Whew, that's about enough for now. Some other (fairly obvious) points about strategy are on the AI web page, I will just put one quote up here for your info below.

We Will do all the important things you're talking about, but its going to take some time, and we need to IMO maintain the discipline to do it in usable-sized chunks. Both Laurent and I are Very interested in the AI aspects of Clash, but much of the rest of the game needs to be there before the challenging but very interesting parts of the AI design will really matter.

Cya,

Mark

From the AI web page (ref at top of this thread):

The crucial job of a Civ's realpolitik AI is to put it into as advantageous a position as possible with regard to its rivals. This AI will look ahead 5-30 turns for opportunities and threats on the diplomatic, military, social (e.g. revolts) and economic fronts. For a militarily aggressive power this means diplomatically isolating smaller powers so that they can be conquered one at a time. (The smaller powers will of course realize what is going on and will tend to unite to defend themselves) Another attractive possibility is taking out a powerful adversary while he's down due to a revolt or other calamity. For more peaceful powers (or aggressive but realistic small powers) the object of diplomacy is to make peace with everyone, buying time to grow by peaceful expansion or economic/technological advancement. Failing total peace they will generally attempt to form a defensive coalition that contains as much of the local area as possible.

[Polemos]

Posted from email.

me :
Evolving strategies genetically requires a good fitness function. And for games of this size, those are hard to generate. Preventing the AI from being predictable is a good thing, but you can do this in another way : evaluate the effectiveness of various moves or short-term strategies and choose a cut-off point. From the strategies that make the cut-off point we can choose one at random. Alternatively choose one strategy such that the likelihood of being chosen is proportional to the evaluated effectiveness.

mark :
I basically agree with what you say. First of all, I think we are helping ourselves out a lot in the fitness function area by having the AI be hierarchical with relatively contained levels, each with their own fitness function. I think I'm most in line with your final comment, in that
the selected strategy should be some random draw based on a function of the fitness of each strategy. I don't think I'd make it proportional, since then even a boneheaded strategy could have a moderate chance of being selected. But it depends on exactly how we make the fitness function, so I'll defer detailed discussion of that until later.

me :
The hierarchical AI model I like, and I think that's the only way to get decent results for a game like this. Modelling AI efficiently in this manner is pretty much game-dependent though I suspect - you probably don't want the AoW 1 type AI where it starts taking forever to take its turns.
The second draft of the plan seems pretty complicated.
And generic planning is really hard to implement. But I like the specific low-level plans like "AreaAttackPlan". I think they'd work well.

Mark :
The low-level plans would be the thing we would try out first as the proof-of-concept. I agree with you that the higher-level stuff is a bit complicated, but I think in time we can do a good job on it.

Me :
Unfortunately the game itself, although it looks beautiful, seems to run *really* slowly on my celeron
300. Is there a known reason for this? Because testing
may be extremely painful if I can't get it running faster."""

Mark :
I have a 300 MHz Pentium III machine, and it runs fairly quickly on Dawn and Jericho, a bit slow on Delenda and definitely slow on Attila. I think the issue here is the Celeron processor combined with the relatively low
clock speed. There is another guy who describes his computer as a "Gateway piece of ****" and he has problems that I suspect are similar to what you are
going through. If the other aspects of what we are doing are sufficiently intriguing, I think we can design scenarios with smaller maps for you to test out the AI on. First you would need to verify that the game runs
basically decently in the Dawn scenario. If that's the case, then we can reduce that slowness by reducing the map size for your AI testing scenario.
We have not done any speed optimization at all on the code, and only a little is planned for the near future. That's because were taking a radical programming approach that suggests we should put off optimization until the very end so we know what it is that really needs to be optimized.

Me :
But what I really want to say is that the current AI
spec seems quite complicated, although I'm not sure
how much of it you've implemented. I mean it sounds
good but for a demo shouldn't one start with something
small and make the interface to the AI able to support
a more complex one?

Mark :
Absolutely none of that spec has been implemented. What is in the demos now is a much cruder AI that Gary slapped together so we would have Something.
As I think is discussed in the AI thread we would start to implement this by doing the lower-level parts of the plan first, which seems to be the things you most agree with. If you are saying that we don't need to implement
the most complicated parts even of the lowest-level AI first, then I agree with you. Getting something that uses the framework interface first, as you suggest, seems like a good strategy. But I do think it should be done with the eventual aim of converging on the plan, although that could be months in the future. Let me know what you think about this approach..

[Mark_Everson]

Welcome to the Clash forums Polemos!

Thanks for posting our email exchange, it may be useful for others who are new to the Clash AI concept.

I hope to hear more of your comments on the Plan stuff in the near future!

-Mark