Thoughts on creating a combat simulator

[falconne]

I wanted to create a combat simulation routine to help the AI determine whether it has enough units to defeat an enemy stack.

From a few threads I see in this subforum, it looks like the developers of this mod have already thought about this a bit. I was wondering if you have anything in progress?

From what I can tell from the code, solving this can get messy as the methods that calculate the result of a one on one duel between two units has side effects that change CvUnit fields, so it's not possible to simply call those methods and read the result and still keep the game state.

I see 3 messy solutions to the problem so far:

1) Create a new set of methods that are copies of the combat calculation methods but rewritten so they don't affect the game state. This solution obviously has so many problems I won't bother talking about them - it's not really a viable solution anyway.

2) At runtime, create copies of all the units involved in the combat and send those objects to the combat calculator (after which they can be destroyed). This would require subclassing CvUnit as it's an abstract class. The problem I see with this is that if I instantiate a new CvUnit, it's going to invoke CvDLLEntity::createUnitEntity. I don't know what side effects that has. In general I don't know if creating temporary units on the fly is a good idea - it might have unintended consequences in the game system.

3) Store the original state of the unit inside of CvUnit itself and restore the state of the affected units after the combat calculation is done. The advantage with this method is the Read and Write methods that already read and write the entire state of the object could be used. I presume these methods are used to write to a read from a saved game file. Unfirtunately there doesn't appear to be an implementation of FDataStreamBase within the SDK, so it would have to be completely implemented. This might still be worth it, as using those methods means, if new member variables are added to CvUnit in the future, the state saving functionality will keep working (unlike in method 2) above).

Have you guys come up with any alternative solutions that would be cleaner? I'm going to work on method 3), but I wanted to check if there were any other ideas out there.

 

[GatlingGun]

I wanted to create a combat simulation routine to help the AI determine whether it has enough units to defeat an enemy stack.

I've not done much research on the AI combat methods, but from watching how the AI plays vs how real players do it... I think it could be challenging to come up with accurate results anything except when the AI first attacks another stack... after that, you run into rather unpredictable pathing behavior.

The pathing behavior I'm talking about is to some degree how the defender responds geographically (i.e. retreat to the hill-forest), but to a larger degree which units counter-attack first... this is obviously not deterministic, and could make a huge difference in the outcome.

 

[Yakk]

I'd be tempted to go with 4:

4> Refactor the existing combat mechanics. Actions that cause "writing" to global state would instead call methods in an abstract class (which is stubbed out in the case of a simulation, and does exactly what it does now in when doing a real combat).

The downside of <4> is if it isn't migrated to the core branch, it can be somewhat annoying to keep up to date with changes.

Saving the state of the unit ... might not be good enough, because you run into problems where the unit state changes (like death) cause non-reversible side effects (unit deletion, python calls, etc).

...

One way to do this would be to write CvCombat.h and CvCombat.cpp -- a class that abstracts out the combat mechanics, instead of having the combat mechanics be embedded into the CvUnit.

Then you can have something like a CvUnitSimWrapper that implements CvUnit and wraps an existing actual unit and allows you to simulate a possible future...

Of course, this being C++, writing a class wrapper is hellishly annoying (you have to forward each method manually, sigh). To make it easier, figure out what CvCombat needs from a CvUnit, write a CvCombatUnit abstract interface, have CvUnit inherit from it, and then have your wrapper just implement the CvCombatUnit interface.

On the down side, this is intrusive code. :/

 

[falconne]

Interesting comments Yakk - we've obviously gone through similar thought processes.

4> Refactor the existing combat mechanics. Actions that cause "writing" to global state would instead call methods in an abstract class (which is stubbed out in the case of a simulation, and does exactly what it does now in when doing a real combat).

The downside of <4> is if it isn't migrated to the core branch, it can be somewhat annoying to keep up to date with changes.

I wanted to avoid changing the structure of the existing code because that would make merging difficult with other mods (especially ones that change combat mechanics). I expect I will have to do some of this anyway, as there are places where the combat code calls out to Python and a few other places where it changes state of other objects that do not affect combat evaluation. These would have to be protected by "if not in simulation" clauses. But in the interest of changing the existing code as little as possible, I'd prefer to do that than lift those bits out into different functions to be stubbed out.

I would be able to tell that I'm running in simulation mode without a global flag because "saved state" units that are being run through a combat simulation will have a public read only flag set that says they are "simulated" units.

In any case, I still need to have a safe way of changing the state of the unit that goes through the combat routines - for the defending units (and attack units with blitz), individual units may participate in combat multiple times during the simulation and their injury level needs to be factored into the combat each round. Also, attack units that cause collateral damage would injure healthy enemies before they get their turn for combat.

Saving the state of the unit ... might not be good enough, because you run into problems where the unit state changes (like death) cause non-reversible side effects (unit deletion, python calls, etc).

Well, with the Python calls, I would need to protect them as above, but as for units dying, the combat calculation itself doesn't delete the CvUnit after death. And "death" does not affect any state that can't be restored, as it just means hit points are at 0. If I were to use the existing stack attack code to do the entire simulation, then this would be a problem as the object is deleted at this level, but I probably won't be using that method. I would most likely have my own stack attack routine that runs through the whole simulation and returns the final results.

As for death, units that die on the defender side do need to be removed from the stack so they don't affect the subsequent combat rounds, but I obviously don't want the objects destroyed. What I'll most likely do is add a method to CvPlot to tell it to create a copy of its unit linked list (m_units), then "clone" those units inside m_units. By "clone" I mean tell each unit in m_units to save their state. My stack attack simulation routine would basically tell the CvPlot doing the attacking and the one being attacked to do this clone, so when the attack method is called with that target CvPlot, it actually works off the "cloned" (or "saved state") units in the CvPlot's list. When a defending unit "dies", my stack attack routine would remove it form the CvPlot's list and call the attack method again.

When the stack attack is finished, the routine can just call a "restore" on the two CvPlots, that would copy their stored linked list back and call "restore" on each unit in the list.

One way to do this would be to write CvCombat.h and CvCombat.cpp -- a class that abstracts out the combat mechanics, instead of having the combat mechanics be embedded into the CvUnit.

Then you can have something like a CvUnitSimWrapper that implements CvUnit and wraps an existing actual unit and allows you to simulate a possible future...

Of course, this being C++, writing a class wrapper is hellishly annoying (you have to forward each method manually, sigh). To make it easier, figure out what CvCombat needs from a CvUnit, write a CvCombatUnit abstract interface, have CvUnit inherit from it, and then have your wrapper just implement the CvCombatUnit interface.

On the down side, this is intrusive code. :/

If I understand you correctly, I think this somewhat similar to my 2) method. Basically creating a new or wrapper unit to pass into the simulation. This of course may still need to be done, if I find out there are some state changes that cannot be restored from.

I figure the final solution will have to include aspects of several approaches, as the combat code seems to branch quite a lot based on a multitude of factors. There's probably all kinds of side effects that need to be thought through and mocked out.

I've only spent a brief amount of time on this so far. All I've did was add state saving ability to CvUnit by using CvUnit::Read and ::Write to read and write its state to a data stream. The save and load game routines of the game use this methods too, so it gives me some confidence about their robustness for state saving. I've smoke tested it by having the unit save state and immediately restore - I stepped through each line in the debugger and it all seems to work ok.

When I've actually got the units running through combat simulations, I will do more through testing - possibly by serializing all the classes to an output stream before and after simulation and making sure they are the same.

 

[Yakk]

*nod*, sort of.

You rip the combat rules out of CvUnit, and place them in CvCombat.

CvCombat takes a CvUnit and other parameters, and runs a combat on the CvUnit.

But CvCombat doesn't take a full CvUnit -- it takes an interface that is "tight" and only details what it _needs_ to know to run the combat directly.

Now your CvCombat engine doesn't need a full CvUnit -- it only needs the specialized CvUnit sub-interface. And when you do your combat simulation, you create instances of that sub-interface. These SimUnits have the properties that are needed for a combat sim (strength, promotions, etc), but are not _real units_, so you don't have to worry about side effects.

Odds are they just redirect most of their queries to a 'real' CvUnit they are based on.

The CvCombat code (and code flow) looks nearly exactly like the existing CvUnit combat code. So changes become relatively simple to maintain.

 

[falconne]

I've started thinking about this again. I got distracted creating a tool that allows each AI player in a game to be driven by different AI mods, a sort of AI mod arena, which I felt was more interesting to work on. But now I'm ready to bring some attention back to this.

Yakk, I agree it would be safer to create a cut down class for combat which only implements combat specific methods. I would really like to just use a saved state technique so I wouldn't have to copy and paste any code, but using a cut down class would mean that only routines that I've explicitly okay'd get called and I won't lay awake at night wondering if there was some obscure area of the code I hadn't stepped through that has side effects.

I'll take this approach, wrapping a simulated unit class around a real CvUnit and only call into the real class for const methods that are confirmed to have no side effects. For large methods that have a few lines with side effects, I might add some conditionals that allow those methods to skip over those lines when in simulation mode - that way I won't have to duplicate large areas of code just to change a few lines.

 

[falconne]

I've got workable simulated combat unit class (as well as a simulated plot class to hold simulated combat units) going now. I've "simulated" the resolveCombat method and everything it depends on that changes state. Each simulated class wraps its corresponding real class inside itself, so it can pass non state changing calls down to the real class.

I'm looking through the AI's decision making code for a good place to try them out. I think I'll try it in the same place that the AI calls AI_compareStacks and test if simulating the stack combat in this situation produces a markedly different result than the ratio calculated by AI_compareStacks.

I'm trying to familiarise myself with the code around the area. I'm puzzled by this bit of code below that's from CvUnitAI::AI_attackCityMove and calls CvUnitAI::AI_stackAttackCity (whose purpose appears to be to push a city attack mission if this stack's power against a city plot in visible range is above a given power value). It seems to me the first call to AI_stackAttackCity is redundant, because even if it returns false, the second call makes the same request with a lower required threshold value:

//stack attack
if (getGroup()->getNumUnits() > 1)
{
    if (AI_stackAttackCity(1, 250, true))
    {
        return;
    }
}

//stack attack
if (getGroup()->getNumUnits() > 1)
{
    if (AI_stackAttackCity(1, 110, true))
    {
        return;
    }
}

Am I missing something? This seems to be either inefficient or a bug, depending on which power threshold value was really intended.

 

[falconne]

Does anyone have any save games or some known setups I can do in the World Builder that demonstrate and example of a AI "suicide" attack? I would like to step through the decision making code in that situation and see if I can find a way to for the AI to use combat simulation to avoid that type of mistake. Unfortunately, it seems rather difficult to make such situations come up in Auto Played games, presumably because the AI's own city defense system is not as sophisticated as a humans.

Having gone through the combat decision making code (albeit briefly), I begin to doubt the usefulness of a combat simulator until a whole bunch of other tactics work is done. You folks working on this mod would know the AI's tactical code much better than me, so at this point I think it best I ask you what your analysis of it has been. I'm just going to explain what I've concluded:

At least when it comes to attacking cities, it seems like the AI isn't all that bad at deciding whether a stack attack would work or not. The problem is, if it decides it's not strong enough, it doesn't seem to fall back and return with a bigger army - it just lets its units make opportunistic attacks at whatever's available, which might include a few of its units attacking the city just to cause some collateral damage.

The problem then is that the stack splits up, without a hell of a lot of analysis of the danger to its units by visible enemies in the vicinity. This allows a human to take on smaller stacks and destroy the AI piecemeal.

Preventing this behaivour won't help either, because a lot of the time this is desirable - if it can't complete its original mission and the AI has no capability to regroup and retry, then it might as well try and take some of the enemy out.

So there doesn't seem to be much in the AI at the moment where a combat simulator would make it better. There're no obvious places where forward planning can be shoved in (and without forward planning, there's not much use for simulation). It seems to me there needs to be some theories developed around the best way for the AI to use stacks in enemy territory that are under threat - e.g. can it rescue them and if not, how can it cause the maximum damage to the enemy before the stack dies? To accomplish the latter, a combat simulator would be required so the AI can do some look ahead calculations.

Anyway, I guess what it comes down to is, do you guys have any ideas about forward planning combat tactics that can be added to the AI that I can use my simulation code in?

 

[Yakk]

I like using earth 1000 AD. It isn't a "real game", but looking at the Mongols, Chinese, Europeans and Arabic wars at the start is illuminating.

As an example, as the Spanish, I can kick the Arabs right out of Spain. As the Mongols, I can overrun China. As the Chinese, I can repel the Mongols. Etc.

One to work on is the Mongols. The first-wave force of horse troops isn't enough to take the northernmost Chinese city. Attacking with it is pointless -- it should be held back until the 2nd wave arrives.

I think, but am not sure, that the Mongol AI does the wrong thing -- it doesn't concentrate enough force to take the city in one blow. You can double check this, however.

Similarly, the Spanish have enough forces to take out the Arabian city in Spain, but only if they strike quickly. Possibly this is just the AI playing cautiously?

The wars over Jerusalem are interesting.

...

An interesting way to test this in the 'long run' would be to take something like 1000 AD, and have one player use the improvement while the others do not, and see if that player does better in a game?

 

[CivFanCCS]

From the games I have been playing lately, I think two scenarios are happening.

The first is the national suicide attack. This happens when you have a huge power ratio over an AI player and he/she declares war on you. I had a neighboring civ declare war on me when the power ration was over 10/1. I had approx. 30 cities on a huge map and the AI civ had 4.

This might happen because of a deal from another player that is just to good for them to refuse. Not sure, but I was at odds with the 4 civs to the north and the suicidal civ declared 2 turns after I made peace with an equally powerful civ that they were friendly with.

The second suicide attack has been described above. The AI sends a stack of 10 units to take out a city defended by 10 - 15 units of equal strength, sometimes with a follow-up stack or about equal size, if not a little smaller.

This makes no sense... a human would never do this, especially in the industrial/modern era. I can think of only one reason and that would be to create a diversion.

One last thing... I was in early modern era and a civ attacked me with a huge stack of around 100+ units. The civ attacked with the stack a fortified city on a hill that had about 60 - 80 units guarding it. They kept sending re-enforcements and attacking here and there with 5 -10 units, and I kept re-enforcing my defenders as well.... that stack they brought sat there for 30-40 turns until peace was declared. they could of re-routed and abandoned the attack on that city. Man are they lucky I had no oil. (think it was a holy city, could that be why they "wanted" it so bad?)

 

[falconne]

CivFanCCS, you wouldn't happen to have an autosave or something from that last game you were talking about, from a little before the AI sent that huge stack would you?

Any savegames anyone can point me to from just before the AI does something stupid would be a huge timesaver for pinpointing its weaknesses.

 

[PPQ_Purple]

The concept of this is to make a way for the AI to know wether it can beat an enemy stack?
I have a simple idea. You know that when you press shift, you get the aproximate odds for the battle.
Now all you need to do is create a method that calculates something like this:
This was written in C as I am no good with pyton. But it should be a easy translation.

A = number of attacking units
B = number of defender units
C[] = odds for combat (an indexed intiger that has A elements)

functions:

void count()
{Counts the number of units in each stack and places them in A and B.)

void colect()
{Runs through all the odds and records them in C[].}

bool check()
{
	int i = 0;

	while (B > 0)
	{

	if(A > 0)
	{
		if(C[i] > 80%) * could be modified to any precentage, but I do not recomend going below 40%
		{
			B--;
			A--;
		}
		i++;
	}
	else
	{
		return false;
	}
	return true;
}

If the function returnes true the AI goes for it.

The point is that the AI does the fallowing:
1. Checks the odds for combat of each unit in his stack,
2. Checks wether he can kill all the enemies before it loses all it's troops,
3. If yes, it attacks.

Alternatively, you could add a few extra lines to the code to get the AI to actualy know whitch units to attack with first.

It should just have a variable that conects the number from C to a specific unit. (EG. the AI should know at what unit it started counting.)

PS. What do you think? I think it could be done, and it would be much easier to do than any of the more complex simulators.

 

[Yakk]

A hard target is one in which you have to burn some of your units to 'crack' the enemy. Be it throw away sacrificial units, collateral damage 'softening up' units, or flanking retreating units.

Taking hard target is often worth it. As a human player, I know that even a 1% chance of victory (and 0% retreat chance) on a catapult can easily leverage into a serious tactical and strategic win, because I've seen that kind of situation before.

Teaching the AI that kind of "soft" tactical knowledge ... is hard. It happens to be easier to have the AI basically do a "save game, attack, reload" 3 to 5 times, and have it use that information to determine if the attack is likely to succeed.

With that capability, you could even deal with a combined assault on a city from multiple fronts.

 

[PPQ_Purple]

But if you had saves and reloads before every AI attack, that would slow down the machine it is playing on. You have to remember we arent playing on super computers.
If there is a AI routine that determenes how importmant a target is, it could be addapted to change the precentage.
So instead of:

if(C[i] > 80%)

We could have:

if(C[i] > 80% / importmance)

So the more importmant the target, the less the % needed for a attack.
This does not make the AI win, it makes him take more chances.
And for the A = number of attacking units, these don't have to be units in a single stack. They could be all the attack capable units with the city in their operational range.

 

[Yakk]

Yes, that slows it down. So, if you read the thread, one solution is to save and reload the state of the units in question. Alternatively, you "ghost" the units, and have the "ghost" units fight it out.

Both of these can be quite quick, and they duplicate the effect of "save and reload". And they generate an AI that can "figure out" if a fight is worth fighting or not.

I'm actually afraid the result will be too good, honestly.

 

[CivFanCCS]

Been playing a new game for sometime now... The AI sea assault is not too bad. They actually managed to take one of my decent cities... I was at war with 4 civs. I had minor tech advantage at the time. (Just acquired riflemen)

I think the AI should of burned the city instead of trying to hold it. The AI was quite far away (at least 4-5 turns by sea) and had no real backup support, plus they were furious with me. I just see no reason to try and hold a city with 15 units. They should of hit that city and got back in the boats and moved on. I had no real navy at the time and like I said I was at war with 4 civs, three of them were on the same land mass as myself. I had a lot of units in surrounding cities and quickly took back my city.

Anyhow to get to the point of this tread... I made peace with 3 civs except the one mentioned above. I decided that I was going to take the land mass they were on. Time goes by and we reach modern era. Took that long to build navy, re=group troops, etc. I destroy them city by city. Instead of attacking my 15 battleships and 6 carriers they keep sending 2 - 3 destroyers/battleships at my cities, with anywhere from 5 - 10 units. Total waste. They needed to defend their cities and instead they are sending units at mine??? I'm in debug mode and the war strategy was dogpile...pretty sure after the tide of war changed the AI stayed the same... thinking it could still invade. Then they attacked my massive fleet with 3 destroyers, 5 gallons and 6 transports! Just to give my ships exp?

Saves are posted below. (All auto saves and one real early. try the earliest auto save for the last example)

Some reason new zone alarm will not let me upload... I will post after I figure this out.

 

[PPQ_Purple]

Yes, that slows it down. So, if you read the thread, one solution is to save and reload the state of the units in question. Alternatively, you "ghost" the units, and have the "ghost" units fight it out.

Both of these can be quite quick, and they duplicate the effect of "save and reload". And they generate an AI that can "figure out" if a fight is worth fighting or not.

I'm actually afraid the result will be too good, honestly.

Ok, let's say we have a global war. (worild war)
We have 10 AI players, 8 of witch are at war. And each makes say 5 attacks per turn. That's 40 attacks, eather 40 saves and reloads or 40 ghost protocols. As nice as it seems, there is no machine that could take that much work, it would cash your game after a few turns.
My idea brings the AI to human level. It sais: "no one can realy tell if you can win. But is the chance worth taking? (returns true/false)."
I don't know how AI importmance is calculated, but it would easilt get the AI attacking even on 0.1% if the target is imoportment enough.

 

[Yakk]

The ghost trick is quite cheap, or at least it looks it.

And no, I don't use anything at all like what you describe when playing a game and deciding if I should attack. It is true I could try encoding something similar to what I do when I decide if I should attack[1] -- but simulating the fight is far easier and probably will be as effective.

[1] Which is something like "do I have enough catapults to beat down the behind-first defenders? Do I have enough base crackers to beat down the "front line" troop that the catapult will suck at? Can I afford those losses? Is my aggregate power estimate of my forces, after I estimate how many losses I'll take cracking the outer shell, sufficient to defeat the enemy, with enough forces held back to recover? Have I cut off the enemy base from resupply sufficiently that waiting is an option? Am I in a rush for other reasons? Will I have the forces left over to hold the base after I take it?

Do I have prior experience with this kind of defense, and these kind of attackers -- ie: what ratio of axemen to archers is usually good? Should I bypass this city and take out other cities, hoping to lure the AI into walking the archers out in the open? How is my supply line -- do I expect massive reinforcements soon? Is the AI under slavery, and pumping out units every turn?

Etc etc.

But computers don't work like people do at this level. Computers can solve certain classes of problem _really quickly_ -- among them, they can simulate Civ4 combats really quickly. They are also really bad at other classes of problem -- many of which are listed in my above description of what I personally take into account when deciding if I should attack.

Yes, save/reload is not practical. The "ghosting" of units and doing a simulation is, I fully expect, going to be very cheap. Not cheap enough to do 10s of times per unit move, but quite cheap.

 

[falconne]

Ok, let's say we have a global war. (worild war)
We have 10 AI players, 8 of witch are at war. And each makes say 5 attacks per turn. That's 40 attacks, eather 40 saves and reloads or 40 ghost protocols. As nice as it seems, there is no machine that could take that much work, it would cash your game after a few turns.
My idea brings the AI to human level. It sais: "no one can realy tell if you can win. But is the chance worth taking? (returns true/false)."
I don't know how AI importmance is calculated, but it would easilt get the AI attacking even on 0.1% if the target is imoportment enough.

Actually what I'm doing doesn't cost anywhere near what a save and reload does. The combat simulation uses, as you say, "ghost" units, but those objects are tiny. They wrap the real unit object inside them and pass all read only calls down to the real object. The only real data variable they contain is the integer that stores how much damage is done to the unit (so it can be changed during simulation without changing the damage value in the real object). This ghost object contains a bit of copied and pasted code from CvUnit which are the combat methods that read or change the unit damage value (which I modify to use the ghost unit's value instead).

The simulation itself is just a bit of number crunching that the computer doesn't have any trouble with. The combat mathematics are actually quite simple.

I should mention the AI already has a fast stack vs stack evaluation method that it uses when attacking cities. The reason this static evaluation is not good enough is that it doesn't allow the AI to "look ahead". The static evaluation gives the AI a reasonable idea if it can take the city or not with one specific stack, but that's all it does. If it realises it can't, if it has other units nearby, it will try to group them together and retry the evaluation. This is already one problem - the static evaluation can't tell the AI if multiple stacks working independently could take the city, as it can't work out how much damage would be done to the city defenders in a sequence of attacks.

The other problem is, even if this static evaluation tells the AI to attack, it has no idea if enough of the units will be left to defend the city from a reasonable counterattack. It can evaluate the danger posed by other enemy stacks in the area, but it's not very good at figuring out if what's left of its stack after taking the city can even hold it against the visible enemy stacks.

So what I initially thought the AI needs to do is be able to run a sequence of combat routines on simulated stacks that preserve their status (i.e. what units get killed, which ones die) so it can actually figure out if it's able to "secure" a given area. But then I realised that even if it had this ability - even if it knows it can't take a city - there usually isn't much of a contingency plan. If it has other units en-route, it will wait for those reinforcements, but if not, what should it do? A human player would fall back and come back with a bigger stack.

I haven't explored the code to anywhere near the extent the guys working on this mod have, but it seems to me the AI doesn't have that many decision paths that say "fall back". Even when it figures out using its current logic that it can't take a city, the AI will just make opportunistic (sometimes suicidal) attacks. It's better than doing nothing - at least it might kill a few enemies. Then it sends another similarly sized stack later on to attack the same city, because it has no memory of the previous failure. So the human just uses this city as bait to induce continual suicide attacks by the AI.

Anyway, my current situation is, I can't just throw combat simulation into places where the AI does strength comparison. Even if it does give more accurate results than the current evaluations, it would make the AI not attack at all if it can't win. Until the AI has the capability to fall back and return with more power, it's better to let the stack do as much damage as it can before the human destroys it.

What I'll do first is try and apply combat simulation to help the AI figure out its order of attack better, as it sometimes screws this up. It will allow me to test the simulation code and should have at least a small positive impact.

In the meantime I'm playing through a game and keeping copies of saves from just before the AI attacks one of my cities in a questionable manner. I will later rerun through those saves, stepping through the debugger, to build a better picture of the AI's "tactical" sense (and where it makes mistakes). I will then at least know what I'm talking about.