AI -- the Thread

[Mark_Everson]

Hi Laurent, thanks for the mini-review of GalCiv. So far I've resisted the temptation. I guess I'll wait until I have a substantial amount of time to blow. . . maybe sometime in 2006!

Originally posted by LDiCesare
I want AI to be able to attack walls:
AI must be able to switch production to good units. (snip)

Sounds like you're making good progress! Your approach here sounds good to me.

Now I have more or less coded the "ask for reinforcement of a given type" order, and it will take existing idle armies and give it to the required command.

Again, your take on it sounds good, certainly at least for now.

However, I still don't have the "change econ orders" plan. This is what I will really need now. If you have any suggestions on how to handle this, in particular what this means in terms of various levels of ai, I am interested:
The ai currently works by having units ask for orders to higher order plans, which take decisions when asked. This really means each unit executes its orders until it is over. So the high level ai is actually quite lazy, as it makes some computations in its thread, and gives orders off-handedly when asked by the real-world units. This doesn't work for econ orders, which never ask for anything.

The way I would do it is to give the overall military AI (Assuming you have one) a "BuildTF" Plan. The BuildTF plan would remember the lower-level Plan that requested it. The various BuildTF plans would also need some way to assign priorities so that the most vital units are built first. When the build called for by the plan was completed it would let the initiating plan know, and transfer control of the existing units over to that plan.

I could throw out further specifics, but I want to make sure this is the sort of thing you were looking for first. Please let me know what you want me to make further suggestions about.

[LDiCesare]

Mark, your answer makes me think of a way to handle it:
Currently, the military spendings are assigned at the beginning by script, can be changed by script. I'll change that into a BuildTF plan as you suggest, and this plan will get input from the taskforces that ask for reinforcements. It should be able to handle variations of the orders while keeping the same overall military budget (except maybe units support cost for a start).

[LDiCesare]

I have implemented the BuildUnitsPlan, which doesn't build task forces but only units, but at least it has notions of which proportions of units it wants to create.

I am in the process of writing the "ask for reinforcement" plan.
My question is when should this be called?
I thought first to call it when I realise that an attack plan will fail. The problem is I won't select that attack plan, and decide to use another plan instead. I could ask for reinforcements as a backup plan, the way the "stay here and merge" plan works, but that doesn't seem very clever unless I can estimate success correctly.
So, either I have a higher level plan which says "take this square" and realizes it needs reinforcements, or something else, like allowing an "attack plan" to trigger an "ask for reinforcement" plan when it sees its success is too low. This would lower the success of the plan in case of success but allow it to work... or something else...
The problem with the higher level plan is I have to build the upper layer of orders. Right now, orders are given to task forces, they try to see if they can do them and that's all. I don't think building a catapult to take down a city should require much more strategic thinking.
Opinions welcome, as always.

[LDiCesare]

I'm still coding... If you've tried the latest code/newai, you may notice that in Jericho, the ai is very passive. This is because Jericho ai rates 'wait' order very high and there is little or no randomness in the appraisal of the wait order. I am changing the wait weight in Jericho ai and better handling randomness in the choice of ai decisions in order to give it less fixed (and thus less predictable) behaviour.

[Mark_Everson]

Hi Laurent:

I haven't tried the new AI in Jericho yet. I put in all those wait orders because they made the old-style AI work better. Clearly with a more sophisticated AI they shouldn't be there anyway. Its good that you are changing the weight of wait

[LDiCesare]

Value of success, armies, squares etc.

I reached a stage where I'm almost calling reinforcements when needed. After several ideas of design, here's what I've come up with, and the list of questions that goes along with it:

When a plan to take a square is not as successful as expected (1) during a simulation, the plan decides that they need reinforcements, compute these (2), will simulate again, check for success, and then see if the success of the plan minus the cost of reinforcements(3) is worth it in order to compute the overall success value of the plan.

(1) Yes, "not as expected" is quite vague. Right now I coded it so it's just "if it failed", like the units couldn't take the square at all. It could be more evolved than that.

(2) Computing reinforcements is based on heuristics. That is not catastrophic because we will run a simulation again after having the reinforcements, but a bad heuristic here may kill the ai. Something random might be in order. More or less, the idea is to ask for (at least) as much power as what the opponent has left at the end of the simulation. So if you had an army of 4 fighting an army of 10 and ended the fight with 0 vs. 8, you'll ask for 8 reinforcements, giving odds of 12 vs. 10, which is short but should win. The heuristics for walls is even worse, as I consider the estimated amount of breaching power needed to breach the wall in half the number of ticks a turn lasts (so the rest of the army wan attack after the wall is breached). This will need testing.

(3)Here come many questions:
What is the cost of a unit in terms of Success objects?
What is the value of a square?
What is the value of a plan with regards to another plan?
Currently, each plan has a value based on the figure given in the militaryai.xml file. This value is multiplied by the success of hte plan, which is usually either 1 (for a plan like 'wait') or 0 if you couldn't take the square and something between 0 and 1 based on the casualties you take. This is fine for comparing plans between themselves.
This is not so fine for comparing plans to the building of units.
A unit has a building cost, including a number of personnel, which can be used to compute its value. In a plan to take out an enemy army, the value of the enemy army is of the same kind, so the success of the plan could be maximum (as read from xml file) if you kill the opponent with no loss, and a fraction of that based on the value of your losses vs. the value of the opponent.
Now for squares, this is even worse, since squares, units and plans each have their own values. Units and plans have costs or success values assigned form a file. Squares have nothing right now.

The value of a square is a function of many things:
- Strategic value (based on map ai);
- Economic value (based on what resources there are);
- Attrition value (better mine than someone else's).

The last one is very subjective and may be ignored. The first one is not going to be implemented soon except that cities and capitals will, arbitrarily, be worth more than regular squares.
So the big question is: What's the economic value of a square, or, how many units can be lost in order to conquer the square? Existing infrastructure, potential infrastructure (sites), and existing population, should all be part of the equation, but I have no idea what the equation even looks like (I can always put the figures in a file, but I'd like to have feedback/ideas about what the variables I should use are, and how they relate to each other).

[Mark_Everson]

Hi Laurent! Thanks for all the hard work!

Success on 0-1 scale now really bothers me. It seems to me that an absolute scale is much easier to handle. That way you can directly compare winning the war to winning a skirmish, and see that the one is vastly more important than the other. So, as before, I suggest using cash equivalents to evaluate success. I will write my suggestions using that assumption. You are free to re-scale these to a 0-1 scale any way you like if that is the way you prefer to do it.

The cash equivalent approach is summarized in “The AI Plan Object -- Second Draft (Feb 11 2002) “ earlier in this thread.

Value of Military units

For military units the obvious cash equivalent is the resources needed to build the unit. This can come from the Cost object for building the unit. Probably there should also be an effective cost associated with manpower. For now, I guess just pick a value. Maybe make each 1000 manpower = 10 Cost or something like that. The build cost of a unit only enters into the plan success if the unit is lost or reduced in function during plan execution.

In addition to the build cost there should be an opportunity cost associated with each unit. Using a unit in a plan means you’re not using it somewhere else. Something of order 5% of the build cost per turn might be right for this for now. This automatically ensures that two plans that are equal other than in travel distance will have success with the quicker-executed one showing up as better.

Value of a Square

As you say, Strategic and Attrition value can be ignored for now, so I’m going to focus on Economic value here. There are several types of economic value that we might want to give a square. I’ll go through some different choices, and my rough take on how they should be used. You can take my input and tweak it as you would like. There are two main distinctions for econ value: current economic value, and potential future economic value. The starkest case of potential value vs current value is a square with resources, but no people in it. First I’ll focus on currently-occupied squares since that is what I think you are mostly concerned about at this point.

Populated Squares, which already have an economy have two relevant values that are easily gotten in the code. They are the tax base (crudely, what the square is worth to the people themselves), and tax revenues (what the govt. really gets out of the square). Note that both these miss the value due to undeveloped special sites in the square. But special sites are usually exploited fairly early, so this loss doesn’t seem big for now.

This info is obtained with the two following lines of code:

economy.getEconomicInfo(Economy.ESTIMATED_TAX_ REVENUES)
economy.getEconomicInfo(Economy.PRODUCTION_TAX_BAS E)

Where lower case “economy” is the economy of the square, gotten with square.getEconomy() and “Economy” is the Economy class.

On a given turn the value of a square to a civ is something like value = taxes + 0.05 * tax base. The second part with the tax base is a placeholder for non-tax benefits that a civ gets from holding the square, like technological innovation etc.

But the civ should value the square based not on one turn’s value, but the value stream of the square projected into the future. For now we can just pick a multiplier to apply to the one-turn value. Something like 10 or 20x seems about right.

For an unoccupied square one can use
game.economics.settlement.settlementPlan.calculate EconomicHappiness() * population
as roughly equivalent to the tax base. The taxes number would then be the civ’s tax rate * tax base. Why don’t you put in a square.getEconomicValue() function that does the work for an already-existing economy as I outlined above, and just returns 0 if there is no economy. I will then flesh it out to do the unoccupied-square part in the future. Work for you?


Value of one Plan vs Another

Given my discussion above, I think the value of a plan is something like:

Plan Value = Econ value of target (if it is taken) – Mil units lost – Mil opportunity cost

(There are of course more things that need to go in this equation, like destroying enemy units, but I am focusing on the items under discussion right now. Also as discussed in the Plan doc, this should be done using the average of several simulations if the sims aren’t deterministic to get the idea of a range of outcomes.)

If you use the cash-equivalent approach, then you can directly compare two plans’ values. Two plans with value within about 10% of each other are probably roughly equivalent. You can also measure the value of one high-level plan vs another. Lets say we are comparing two overall plans that each use an army composed of 12 units. One overall plan might involve sending four groups of three units each to conquer a number of separate provincial capitals. Another might be to send the whole army to try and take the capital of another civ. We can compare the value of the overall plans by just adding up the values of all the component plans in the two alternatives.


I hope this is most of what you were looking for. Let me know what else you want suggestions on.

-Mark

[LDiCesare]

Thanks a lot, Mark. I'll probably put the getEconomicValue() into Square.
To clarify, the 0-1 range I use is the "success" measure, which is then multiplied by the "value" of the plan. Currently, plan value is read from file, and success depends on whether objective is reached or not, and casualties taken. With a more cash-based approach, the evaluation would be different, since value wouldn't be arbitrary (except for plans like wait).

One thing which may not have been clear in what I said:
Up to now, plans were suppsoed to work at constant resources, so you'd compare plans with various existing resources. What I am doing is making a plan that asks for building a new type of units (siege engines) when none exist. If the plan requires the building of new units in order to succeed, its value will be: (averaged over simualtions) value of square (if conquered) - lost mil units cost - existing mil units opportunity cost - mil units which have to be built cost.

I think the Square value will be very important, in particular in order to assess the value of defending a square, or sending scouts/sentries.

Note I'll always modify (muliply) the value of a plan by a factor depending on the ai type (aggressive, stonewall, random, etc.) so all ai's don't act the same.

[Mark_Everson]

Hi Laurent:

Your approach sounds decent overall. I think you will soon need to move to something like a cash-based approach. Your current method, unless I misunderstand, rates a basically worthless square the same as one with a thriving economy that is very valuable. That lack of assymetry will make the AI do weird undesirable things IMO. But I can see why you wanted to keep things simple just to get the AI up.

I can't wait to play your new version!

[LDiCesare]

I can't wait to play your new version!

You'll have to. I'm not finished for a while... You don't start realizing how dumb a computer is until you start coding an artificial intelligence:

(Me) You need catapults to take down the walls, and then some armies to take out the garrison.
(Computer) How can I know they take down the wall or take the garrison?
(Me) Well, here's a nice heuristics which tells you how much breaching power you need and how much attack strength, defense etc.
(Computer) Wow, great! I love those figures. How do I find out which units I need, now?
(Me, starting to despair) Well, you just check the figures, find the unit that best fits the profile...
(Computer) Yes, I can do that!
(Me) Sure, I already coded you to. Then you subtract the attack strength and all that and see how much you still need.
(Computer) Great. So if I haven't got any unit that can breach the walls, I cycle endlessly hoping one is created ex nihilo?
(Me) No, just send an exception, catch it up and tell the plan that the cost is infinite.
(Computer) Great! So now I know how much the units cost, and even have an idea what they are. I can decide whether to create them or not. When do I create them?
(Me) I have to reexplain you how to ask for reinforcements, because last time I told you how to fetch a unit and now I am asking you how to fetch a task force.
(Computer) Gee! I'm eager. How do I do that?
(Me) Wait a bit, I must compile you first.
(Computer) Great. I just don't understand why you put a ":" there, I expected a ";", but that doesn't matter much. You didn't tell me how units in reserve will behave or how all those nice new things will affect my current behaviour, like merging existing task forces...
(Me) Argghh... Not yet, wait a bit. Merging should be OK, you inherit the evaluation function from TakeSquare anyway so the multiplier for the econ value of the square is in already.
(Computer) Yes, but what about units which wait or are in reserve so they can be sent to merge? And how do I decide to send reserves there and build new units here? And how should I evaluate the cost of the plan if it gets resources from reserves versus if they are jsut built? And could you please explain me why you wrote "return result" in that void method?
(Me) ... (corrects the last compilation error)
(Computer) Oh, by the way, how will I tell the newly created units that they belong to that plan? You'll just add them to it? But will they stay where they are while others are created or join the other units? And what will be the meeting point? I thought I heard someone talk about a thing called "escort", do I need to know what that means right now?
(Me) (switches to apolyton forums).

[Mark_Everson]

LOL!

Yep, AI can be a real hassle. But the rewards will be enormous when you're done. Remember in the AI for a lot of games the comp asks all those questions of the programmer who then says "ignore that, I'm on deadline".

Don't worry, I won't be sitting, looking at my watch, waiting for your AI! But it had better be soon.

[LDiCesare]

Right now I have to create a new Command, which I use to create rally points:
If a task force needs reinforcements, it will create a MergeCommand on top of itself into which all reinforcements will be sent. When they all reach the same square, they'll all be merged into the initial taskforce again...

[Mark_Everson]

Hi Laurent:

Thanks for the details on how you're going to do it. They make sense. I assume no update this weekend means you have too much RL. I hope it was the fun kind of RL rather than the other!

-Mark

[LDiCesare]

It was the really bad kind of RL... (my wife was ill, then I had left my computer in Paris and couldn't take it back home until today when she was better, and now I got that worm which kept rebooting the PC, it took me two hours to get rid of). The whole thing under a moist 37 Celsius degrees (100 F) in the coolest places. The good news is I'm on holidays (though my wife is not, which means I'll stay home with the kids, so I my have some time to program while they kill err.. play with each other)

Anyway, I did some progress last week, maybe will be able to get a few things done this and next week:
Mostly, I made a test scenario in which the player stands idle not doing anything while th pitiful ai plans an attack. While still not great, the scenario proves the ai is better than before: It won't move before it has a sizeable enough army. It may sometimes move too early, but instead of moving ten units one by one towards its target and then leaving them there waiting for them to decide to merge or leave to attack another place, the ai now groups its units together before moving them to a plae it knows it can take.
The ai also knows when it wants reinforcements, and what kind, but I'm not yet up to it building the units (or putting them where it knows it can use them).

I got rid of the threads part for the moment, because that ate too many resources and I mostly did it wrong. I'll have to redo it later when it works when everything is in the same thread.

Here is how I used to do the simulations: Run them independently of the turn the player was in. This didn't work well because I kept simulations of a fight 3 turns ago with more current ones, when both attacker and defender had changed. I now reset all simulations at the start of every turn, and reassess everything. This works fine, but I'll need something better when I tackle mid and long-term plans.
I hope I'll be able to send you the code either this week end or sometimes next week. I'm not sure I'll be able to, but I'll try.

[Mark_Everson]

Hi Laurent, good to hear from you! I had some RL of my own. . . I was caught in the big blackout in the States! Fortunately we were only out of power for 16 hours, and didn't lose water. I think all the food in the freezers is fine, although some of the ice cream got very soft. Another 8 hours or so, and I would have had to throw out everything. Fortunately we were in the first 10% of the Detroit Metro area to get our power back. That was a lucky break, since it may be most of the way through the weekend before most everyone has power back.

My sympathies on your wife's illness and the temperatures. Hopefully the kids won't annhialate each other .

Originally posted by LDiCesare
Anyway, I did some progress last week, maybe will be able to get a few things done this and next week:
Mostly, I made a test scenario in which the player stands idle not doing anything while th pitiful ai plans an attack. While still not great, the scenario proves the ai is better than before: It won't move before it has a sizeable enough army. It may sometimes move too early, but instead of moving ten units one by one towards its target and then leaving them there waiting for them to decide to merge or leave to attack another place, the ai now groups its units together before moving them to a plae it knows it can take.
The ai also knows when it wants reinforcements, and what kind, but I'm not yet up to it building the units (or putting them where it knows it can use them).

That sounds really good. You need to remember that to make a really good non-cheating AI is an Extremely time-consuming task. It seems what you have is already a very substantial improvement. It will really help with all the scenarios when you think it is ready to be used on a routine basis.

BTW, I just heard from Richard, and he expects to have time to work on scenarios in the near future. For that reason when you get to something that is useable, it might be a good idea for us to release it to Richard as a Testbed version. I'll rely on your judgement as to when its ready, and will certainly want to play, er, I mean test it too!

I hope I'll be able to send you the code either this week end or sometimes next week. I'm not sure I'll be able to, but I'll try.

Sounds great, good work.