AI Attack Order - Optimal Or Not?

[Psyringe]

In another thread, the question arose how the AI picks the order of its attackers. Specifically: Does the AI choose the unit which has the best chance to win first, or does it simply choose the unit with the highest strength first?

To answer that question, I tried to set up a test:

AIAttackOrder.zip

In this test, your city (Cuzco) is defended by two spearmen. The spearmen have the "Formation" promotion, which gives 25% against mounted units. The AI waits outside with two horse archers and two axemen. The horse arcgers have no promotion. The axemen are monsters, they have all five strength promotions, all three city raider promotions, and the "Shock" promotion against melee units.

So, the horse archers have a higher base strength than the axemen (6 vs. 5), but when they attack the city, they only have a small chance to win, because the spearmen have a +125% bonus against them. Conversely, the axemen have a lower base strength, but - because of their promotions - could mop the ground with the spearmen while blind, handcuffed and having breakfast.

Now load the savegame and hit "end turn". You will see how the AI, totally unnecessarily, wastes the two horse archers in a senseless attack, before the axemen charge in and win the battle.

The same attack order can be observed when no unit has any promotions (in this case, the axemen would still be a better choice, albeit by a much smaller margin).

I'm surprised. So far, the AI has made a pretty good impession on me, and I did not expect such behaviour.

Now, I don't want to start one of these "the AI suxx0rz" vs. "the AI rulez" debates. These aren't helpful. However, I'd like to know whether the AI really behaves that dumb as in my test. The test may be flawed, here are possible reasons:

a) In the game, the AI may combine units in stacks. The player can do this too. When the player attacks a spearmen-defended city with a stack of axemen and horse archers, then the game picks an axeman as first attacker (I tested this with my save game). However, in the test, the attacking units are not grouped in a stack (there's no way to do this in the world builder). Thus the test situation is not representing a real game situation.

b) The AI assigns scripts to its units. These can be selected in the world builder. The AI in the game may set its scripts in a way that the test situation can not occur in the real game. (Note: I tested various scripts in the test situation and found no effect, but I wasn't very thorough and may have missed something).

c) The AI may move its units in a specific order. The world builder orders all units after strength. Since the AI in the test situation didn't have the opportunity to make a "plan", it falls back to moving one unit after the other in the order the units are represented in memory, which is the order given by the world builder.

Unfortunately I see no way to test for these possibilities. So I'm relying on you to answer two questions:

1. In your games, do you see the AI choosing its attack order like on the test situation?

2. Is the test flawed? If yes, can you improve it?

Okay ... it's your turn now.

 

[Eigenvector]

I don't think the test was flawed. It would be interesting to see what the AI would do given several other possible confrontations. From what I've seen the AI tends to pick the best unit to send in against my best unit.

 

[Dairuka]

Wow. Thats kind of scary...

No wonder fighting a war is the best way to beat the AI in the later difficulties. I never noticed this before.

 

[White Elk]

However, in the test, the attacking units are not grouped in a stack (there's no way to do this in the world builder). Thus the test situation is not representing a real game situation.

Try placing the units a few tiles away from the city instead of directly adjacent to it. Perhaps the units would stack on their own? Actually, to ensure that they stack.. you could place impassable terrain in such a way as to have only one approach to the city. Like a funnel.

EDIT: Ahh disregard. I loaded the save to edit in the funnel myself and realized that the units all shared the same tile. I thought that was what you'd meant by "a stack".

 

[Ranos]

I don't have any defensive stories in regards to this but I was going into attack an AI city with two separate stacks of units. Each had 2 Knights, 2 Macemen and 3 Catapults. Since I was moving them as stacks, they were only moving on tile per turn. When I moved one tile away from the city, there was a single Longbowman sitting outside, so I attacked with one of my Knights and killed the unit. The rest of the units in that stack, except the other Knight, had already moved that turn, so I left him there by himself. The AI attacked my Knight with an Elephant, obviously killing it and then moved the Elephant back into the city.

On my next turn, I moved my stacks adjacent to the city. On the AIs turn, it attacked the stack with only 1 Knight with its Elephant killing the Knight. It then attacked with 2 Crossbowmen killing my 2 Macemen.

In this case, it attacked in such a way as to take advantage of my weaknesses.

 

[eg577]

The order of attackers in that case (elephant first killing the knight, crossbows killing the maceman) was consistent with "attack with highest unmodified strength first" strategy, so we can't say for sure how it decided it.

The encounter as a whole though is good evidence that the AI will attack with its fixed garrison and run back to the city when it thinks it will come out ahead by doing so. I've noticed this too and find it interesting that the AI will actually do something with its garrison which is otherwise completely static (you'll never see the AI have a garrison leave its city for something more important).

Its clear there is some difficulty in how to program the AI to choose its attackers. If you consider melee/shock/cover/etc promotions to the unit's strength then you have to consider how the top defender will change by choosing that attacker. So choosing an attacker based on the "best first" principle and considering melee/shock type promotions would get calculation intensive quickly when both sides have large stacks. Even the worst AI should consider combat and city raider promotions though.

 

[calyth]

Did you notice any type of wrong math going on there?
I found that in the thread that you quoted, when getting the probabilities, the numbers are off. Samurai has a 10% strength I, and a 50% vs Melee, and the maceman has 40% city, 5% fortify and 50% vs Melee. Odds are reported as 8.8 v. 11.6, but the actual ratio should be 12.8 v. 15.6. If the game didn't shortcut the odds calculation, and get 12.8 v 15.6, the odds are a bit better for the samurai attacker than the one shown on screen.
I tried to post 3 screenshots on the gallery, waiting approval.
But as eg377 has said, it seems like the AI picks the attack with highest bast strength, which if it is indeed the case, something that the programmers have overlooked. But the AI still has done quite well to at least surprise some players. Wonder what would happen if this is corrected if the AI would choose the highest strength after bonuses.

 

[Viperace]

Respond to your question: AI attack optimal or not?

I say NOT .
Such a complex algorithm for the AI is simply too much work for Firaxis. For those who got some skill with programming AND mathematics will probably aware that this is too much work.

I think the what eg577 said is correct, a simple algorithm of 'attack with highest strength unit first' might be what made up of the civ4 AI now.

Last note, considering the vast of promotion path, it is just too time consuming to write a best algorithm. Firaxis won't bother about that... As long as AI units attack, fine ? good ! AI programmer: job done.

 

[Elsewhere]

Respond to your question: AI attack optimal or not?
I say NOT .
Such a complex algorithm for the AI is simply too much work for Firaxis. For those who got some skill with programming AND mathematics will probably aware that this is too much work.

Build a matrix representing the odds of unit vs. unit (with their bonuses), and then searching for the biggest number? Hardly a complex algorithm.

 

[Viperace]

If we are considering a simple one stack of units VS another stack units, then its fine that way.

But war is hardly that way... Ur stack of units might have some backup units which is several tiles away rushing to the frontline.

-Should the AI wait for them before commencing the attack?
-Should the AI use catapult to soften up the target or save it for another round?
-Should the AI thin up the defense from their deep territory in order to add extra defenses to the frontline?
-Should the AI split its forces from one big stack into 2 or 3 smaller stacks to reduce the chances of collateral damage?

...this could continue endlessly.


Gotta ask the programmer himself, I don't think they consider that much stuff..


EDIT: If there is a best algorithm , I would love to know, or learn.

 

[calyth]

Elsewhere: It's not complex that way, but it could be the case that by picking the biggest number, for the attacking AI, it would give an suboptimal choise for the defender. Maybe the best attacking choice would be against a unit that it has a bonus. But if we use a different unit to defend, it no longer becomes the best attacking unit. If we simply pick the best attacking odds to fight, the game might make it hard to defend anything.
It used to be the case in Civ3 where the AI picks the highest defense unit to defend against the highest attack unit on a stack vs. stack. They probably carried that over, neglecting the effects of bonuses.
I seem to have a hard time finding the time complexity for minimax.

 

[Wodan]

Regardles of this question, I frequently find the AIs choices suboptimal for the following reason: the AI may indeed pick the optimal first pairing. However, the second (or third, or fourth) pairing may be suboptimal as a result.

Occasionally it might be better to pick less of an overwhelming advantage on the first pairing, in order to substantially improve the second or third pairing.

Wodan

 

[karadoc]

What difficulty level have you got it set on? I have reason to believe that the AI doesn't play it's best game until prince or monarch.

 

[gradenko_2000]

I say NOT .
Such a complex algorithm for the AI is simply too much work for Firaxis. For those who got some skill with programming AND mathematics will probably aware that this is too much work.

I think the what eg577 said is correct, a simple algorithm of 'attack with highest strength unit first' might be what made up of the civ4 AI now.

The optimal solution would still be "attack with highest strength unit first", with the added condition of factoring in all the bonii of both attacker and defender.

So yes, the algorithm is correct, but no, the variables being fed into the algorithm are incorrect insofar as to determining the ratios between the units.

 

[André Alfenaar]

Attack order is very complex indeed. I have sometimes really think about it.

-Sacrifice troops to soften the defences?
-Attack with horse archers first because they can withdraw? Even when they have a lower chance of winning? The AI did this, and it isn't that stupid.
-Attack spearmen with horse archers simply because you have a lot of them and want to save your swordsmen for later?
-Attack with inexperienced toops first? Mostly yes, but sometimes not.
Etc. Etc.

 

[Psyringe]

Thanks for the answers so far.

I agree that getting an optimal attack order is extremely difficult if you think beyond the scope of the battle in question. Questions like "Should I sacrifice a weak unit so that my strong unit has a better chance to win, thus will gain another promotion and will become even stronger" are not easy to answer, neither for the player nor for an AI.

"Optimal battle order for the battle in question" could be done or at least approximated however. The AI just has to look at its stack and check for every unit in it, which unit would defend against it and how good are its odds. Then it attacks with the unit that has the highest odds. The strange thing is that the algorithm for this is already there - it's used to choose the single attacker when you attack with a whole stack of units (uncheck "stack attack" so that you can see which unit attacks). And it's a quick and easy algorithm too. So why doesn't the AI use it in my test? Either the AI is unnecessarily stupid, or my test is flawed and doesn't represent a real game situation.

Note: "Highest odds first" still isn't the best order possible. If the "best attacker" has only marginally better odds than the second best attacker for the first fight, but vastly better odds as all other attackers against a second defender, then the "second best attacker" should attack first in order to maximize the chances to win the whole battle), but I agree that this might not be feasible for an AI (it can be coded, but may take too much time to execute).

I'm still interested in observations how the AI chooses its attackers in real game situations. Does it choose the unit with the highest base strength (as in my test), or the unit with the best chance to win?

 

[Meffy]

Ah, what a refreshing thread! It's a long way from "this game suXX0rZ" to an intelligent discussion including stuff like...

the time complexity for minimax.

There are some good observations all through here. I've been wondering about this but haven't done a lot of fighting yet. Next game...

 

[Jimbo30]

The AI might attack first with the Horse Archers as there is a chance (however small) that they could cause some damage then withdraw, making it all the easier for the axemen.

It might not then again.

 

[Psyringe]

The AI might attack first with the Horse Archers as there is a chance (however small) that they could cause some damage then withdraw, making it all the easier for the axemen.

You raise an interesting point, I think withdrawal chance isn't factored in in these decisions at all.

But in the test situation that would be a stupid thing to do, since the axemen would win the battle easily anyways, no matter whether the spearmen are wounded or not.

 

[KrikkitTwo]

Did you notice any type of wrong math going on there?
I found that in the thread that you quoted, when getting the probabilities, the numbers are off. Samurai has a 10% strength I, and a 50% vs Melee, and the maceman has 40% city, 5% fortify and 50% vs Melee. Odds are reported as 8.8 v. 11.6, but the actual ratio should be 12.8 v. 15.6. If the game didn't shortcut the odds calculation, and get 12.8 v 15.6, the odds are a bit better for the samurai attacker than the one shown on screen.
I tried to post 3 screenshots on the gallery, waiting approval.
But as eg377 has said, it seems like the AI picks the attack with highest bast strength, which if it is indeed the case, something that the programmers have overlooked. But the AI still has done quite well to at least surprise some players. Wonder what would happen if this is corrected if the AI would choose the highest strength after bonuses.

Actually the way the odds are calculated ARE 8.8 v. 11.6 only Strength bonuses are counted to the attacker all the rest are counted as penalties to the defender
so Sam=8+10% combat1 =8.8
Mace= 8 +40% city+5% fortify+50% melee-50% Sam's Melee=8+45%=11.6

Basically what does need to happen is the AI (or a good Human player) needs to do is
1. for each attacker determine what defender will be used against it
2. determine which attacker will result in the best strength ratio

so attacker=Knights+Macemen, Defender=Pikemen+Longbowmen in a new city (0% bonus)
if the Knight attacks the ratio will be 10 v. 12 (because the pikeman will be chosen by the defender)
if the Mace attacks the ratio will be 8 v. 7.5 (because the longbow will be chosen by the defender)

So the Attacker should use the Mace to attack first (it has the best ratio v. the unit that will be chosen against it)


Although Andre's point about other strategies can be factored in (it would be ideal if the computer looked at all possible orders of attack and figured out the odds, ie considering the later attackers odds) of course that should also go in into whether the computer will attack city X with Army Y at all or whether it should wait for reinforcements, and Pillage instead (HA and Axeman v 2 Spearmen should be Axe attacks, HA Pillages while Axe heals before getting the second spearman.. depending on how much of a rush the AI is in to take the city)