Fixing the combat AI (cont.)

[Bibor]

AI LAND OFFENSE

My last article dealed with determining the proper decision-making and positioning in the defensive aspect of the game. This time I will to deal with the most difficult part - land-based offensive and counterattacks (thus leaving the easiest, naval combat for last).

So is it possible to design an effective combat AI? My example choice, Age of Mythology, proves that is a 100% correct answer. That game had an AI you could learn from, and it could beat you without cheating until you got better than it was (which was after several months), and the same is true for the Panzer General Forever AI.

Where the AI usually fails, and it is no different in this game, is that the AI has the proper questions but has the wrong answers. More specifically, the key to victory is not the capture of cities but the total annihilation of opposing forces and control over tacticaly important hexes. Captured cities, like resources, are the sideffect of the annihilation, not the other way around. Annihilation of opposing forces, furthermore, comes from removing them from the board, or to be most specific:

To make the AI able to achieve a military victory over another player, we must reduce cities, resources, roads and other militarily important features into a single, qunatifiable value easily understood by the AI. The aim of an agressive war is to reduce these values to an acceptable minimum.

STEP ONE: Learning the military strength

Before an AI should be willing to go to war, it has to access the situation first. How strong is it? How strong is the opponent? This is not just about existing military forces, its also about production capabilities. For the AI to be able to do that, we are going to run a series of calculations. I'll base it on the fact that AI has the whole continent explored, since it starts with gazillion units. If not, it will use the visible tiles.

Lets do an example on Medieval era.

a. First the AI takes note every time a certain player enters a new era (this time Medieval)
b. the AI should also count the number of turns that passed since that player entered its current Era
c. The AI reads its script that says the following:
- First tier Medieval era has 5 techs, second tier Medieval era has 6 techs
- Techs that give units in 1st tier are 1
- Techs that give units in 2nd tier are 4
- Average number of turns to reach next tech is 10 (maybe not the best number; discuss)
- If less than 50(5 techs*10 turns) + 10 turns passed since entering Era, treat only 1 medieval unit available
- For each 15 ((5 techs/4 units)*10) turns past 60 into medieval era add another unit
- Medieval unit costs: Pikeman 100, Longswordsman 150, Knight 150, Trebuchet170, Crossbowman 120 for an average of 138 per unit.
- Pre-medieval unit costs: Spearman 50, Swordsman 80, Horseman 80, Catapult 100, Archer 70 for an average of 76
- Consider Bismarck etc. for specific values.

d. It should take into consideration if the calculation's target is Hiawatha or Catherine or any other civ that has production bonuses based on some tech (or building).
e. it counts any maritime city states you are allied with (that are known to him)
f. Now what the AI does is that it assigns a number value to each of the opponents non-puppet cities based on the following factors:
- treat every other forest as lumbermill past 60 turns into medieval era
- treat all hills as mines
- add up the total possible hammer output of all visible opponent's hammer producing tiles (plus two for the city hex)
- add up total possible food output of all tiles that can produce (plus possible era benefits of maritimes)
- add up total population of all non-puppet cities
- Divide the total hammers produced by total population.
- Divide the total food production output of the 2-hex radius of a city by its population number*2, add known maritime era bonus. If it's not negative, confirm total hammer output of the city calculation
- check if number of hammer producing tiles is less than total population. If so, use the number of tiles instead
g. Now the AI takes into consideration the opponents budget (whether it can rush-buy units or not and if yes how many), using similar gold values to what I described here for hammers.
h. And finally, it comes to a conclusion of how many units can the enemy produce per turn if need be.


Lets see how this works out for me.

- Montezuma entered Renaissance era on turn 205 (now it's turn 219). Don't need a screenshot I hope
- Total number of hammers per turn within known borders: 71
- Total non-puppet population 34, total hammer-featuring tiles 39 so use population # instead
- total maximum production of hammers per turn: 71, or 2.08 per citizen (lets make it 2 for simplicity).
- total number of medieval units available: 4.
- average cost of his units: around 120.
- Montezuma can produce 0.59 units every turn.
- It also has +53 GPT and 374 Gold so it can rush-buy 0 units + one unit every 9 turns.

Thus his cities have the following unit production value:

Spoiler :

You'll immediately notice how numbers for Teotihuacan are off, but that's okay, gold is production as well.

Now I do the same thing to myself:
I check my production and divide it by number of my citizens:
98 hammers per turn, 43 non-puppet citizens, bringing it to 2.27 hammers per turn per citizen.
I also have all but trebuchet available so that's 120 cost per unit.
My cities can produce 0.81 units every turn.
I also have 4931 gold and 213 GPT which means I can rush buy 10 units and do it again every 2 turns.

STEP TWO: Calculating if an offensive war is winnable

After the AI calculated the production strenghts of enemy cities and nation, it's time to make a decision.

AI makes a projection for 10, 20, 50 and 100 turns. For sake of simplifying things now lets just take the 20 turns example now.

a. The AI (Monty in this case) checks the demographics/soldiers. Checks if the opponent is top or bottom. If neither, he takes the average value. Lets say he doesn't see us in top or bottom.
b. Now it checks his own soldiers value.
c. the AI now compares the hammer cost of its units to the power rating he just read and converts the average power rating to hammers.
d. In the given screenshots example, the average power rating is 65,317. I'm neither top or bottom. And I have 60,000 soldiers. Since I can't see Monty's units, I'll take my own for calculation.
- 1 trireme (60), 5 samurai (750), 1 knight (150), 1 crossbowman (120), 3 catapults (300)(maybe 3 GGs also count into power rating, dunno) for a total of 1380 hammers. 60,000/1380=43 hammers per power rating. Lets say 1 hammer equals 43 power rating (though my numbers may be off).
e. That means that by calculation, the average army strenght, and thus my army in hammers should be 1500 or roughly 10 units. A pretty precise estimate.
f. now the AI makes the projection based on 20 turns (lets say his strenght is also average, 1500 hammers).
- Enemy has 1500 hammers of units. AI has 1500 hammers of units.

Projection conclusion:
Enemy (me) can produce 16 units in 20 turns and immediately rush-buy additional 10 units, and rush buy another 10 units in 20 turns for a total or 44 units.
AI (Monty) can produce 11.8 units in 20 turns and immediately rush-buy additional 0 units, and rush buy another 2 units in 20 turns for a total of 13.8 units.

AI wisely decides it's time to boost economy not go to war.

 

[Bibor]

AI terrain battle plan

Now that the AI decided whether to go to war (lets say it did), its time for us to teach him how to decide where to go.

a. First it decides on the relative facing of the enemy considering bordering/facing lands. In our case we pretend the Japanese are AI and that Monty is the enemy, again using the "lines originating out from cities" method.

Spoiler :

b. Then it marks the whole territory for inpassable (red) and protected terrain (orange) in all enemy lands + 2 hexes outside of them (but ignoring friendly territory).

Spoiler :

c. Then it marks river crossings in line with the attack facing from first image (yellow)

Spoiler :

d. Now it marks the supply lines which consist of all 6 passable hexes around cities + a 2-hex wide tile line between them (hexes possibly connected by roads). We know there are two more cities outside this map.

Spoiler :

e. It can now cross-reference the protected (hills and good river crossings) tiles with supply hexes.

Spoiler :

f. And now lets clear it up a bit. These are the tiles it has to control to prevent reinforcements.

Spoiler :

g. Now we'll sneak in our production strength numbers and also count the number of "supply hexes" in a 2-hex radius of each city in question.

Spoiler :

h. We add up the numbers giving us the following values (we could also take into account strategic or happiness resources the 2-hex radius contains):
Tlacopan 9
Calixtlahuaca 17
Cologne 6
Texcoco 13
Tlatelolco 21

i. Taltelolco has the highest value of protective tiles, reinforcement lines as well as the highest production value, followed by Calixtlahuaca. But it's not over yet. No point marking the supply points if the AI has not enough troops to hold them. So the AI counts its troops: 8 melee, 3 ranged, 1 artillery, 1 Great general.
It needs enough troops to:
- protect its ranged while it bombards the defenders/city
- hold the supply points
- to semi-encircle the attacked city
so he draws deathstars around two cities that top in value - Tlatelolco and Calixtlahuaca.

j. First he draws a deathstar around Tlatelolco. It gets rid of any supply tile not adjacent to ranged or target city. Ouch, a deathstar requiring 4 ranged and 8 melee units. The AI automatically adds an expected 30% of melee units which brings it to 11 melee and 4 ranged units. 3 melee units short. It moves on to Calixtlahuaca.

Spoiler :

h. Calixtlahuaca looks much more promising. required are 3 ranged and 6 melee units + 30% bringing it to 9 required melee. It decides to go for Calixtlahuaca.

Spoiler :

STEP THREE: carving the path

a. The AI sorts its Deathstar at least 1 tile away from enemy borders in a circular fashion, protecing the ranged. Yellow is melee, blue is ranged, red is great general. Shown are the starting and final position of the deathstar.

Spoiler :

b. And two turns later:

Spoiler :

c. And one turn later, with arrows pointing next movement:

Spoiler :

d. And one turn later, with final movement.

Spoiler :

e. this obviously in case the Deathstar receives no resistance. Otherwise the whole deathstar stops and engages the enemy, but staying in formation.



STEP FOUR: preventing retaliation

Now that it decided on attacking Calixtlahuaca its time to think about retaliation.
a. First of all, the AI monitors the "city X has been conquered by Y". IF Y was the target civ, It checks how many turns before was it and what's the HEX distance to that city. He calculates every turn passed to be worth of 2 hexes of movement.
b. If there were no such events, the AI takes the second (or prior) top priority city it had for deathstar attack. In our example it would be Tlatelolco and presumes it will be the retaliation starting city. It adds two hexes around its own deathstar path makes a triangulation between its own territory, Tlatelolco and its own deathstar position. This is the retaliation area.

Spoiler :

So what the AI does is it takes the first map projection it did for protected terrain and makes a cross-reference with the Retaliation area". It picks the tile closest to its own lands to place a sentry there (horseman or scout, depending on what is available) in this case the sheep hills tile. It moves its defensive forces (which should be roughly 30% of attack force, available at all times) to Tokyo (higher production value then the puppet Beijing).

Spoiler :

 

[Bibor]

Counterattacks!

The long awaited (lol) counterattack mechanics suggestions, finally wrapped my head around them.

Turns out Oda was right about Monty having a retaliation force somehwere down there. As a matter of fact it was about to attack a city state down there when he saw movement around his borders at Calixtlahuaca and Cologne. Monty politely asked "WTH, Oda? Units near my borders?" and lets presume Oda replied truthfully "Fruits from your tropical lands will make fine addition to my pina colada".

Due to the two cities' sight radius (3 hexes from the city) this is what Monty sees:

Spoiler :

5 units and a Great General. It's not a feint attack! Run for the hills!

Remember, he has 3 swords and 2 archers for his defensive force. And we drew the roads that were invisible to Oda. Lets also be polite and give Monty 400 gold.

STEP ONE: PLOTTING OUT THE MAP

a. First the AI takes the position of enemy troops and adds 1 hex around it. That's the new NO-GO AREA (red border) and then it draws counterattack lines from cities (opposite of what Oda did).

Spoiler :

b. Now it determines the remaining good strategic positions (riversides, hills, forests) considering the facing (I'll paint them all orange)

Spoiler :

c. Now it calculates its realistic supply lines (road +1 hex away; city counts as road)

Spoiler :

d. And now, of coruse, it does a cross-reference of the two plots

Spoiler :

e. And lets clean it up for better view.

Spoiler :

STEP TWO: SETTING UP THE DEFENSE

f. AI goes through its defensive units and decides it can reach the protective positions around Calixtlahuaca in time, by the defensive routine I described in my prior post. He promptly upgrades his swordsman on the road before ending its movement and does the same to the other two after their movement is almost complete.)

g. The main Aztec attack force consists of 2 longswordsmen, 8 pikemen and 6 crossbowmen (he's short on iron). It calculates it can reach the protective positions around Tlatelolco and he proceeds to do so.

h. It draws a deathstar for its counterattack position, discaring any positions that would make a friendly melee NOT border a friendly ranged unit) of which there are none here, and positions them there first (even if it takes 2-3 turns). This is done to protect the other cities in case the attacked city falls too soon (promos or chinese GG or whatever luck the attacker may have) in which case there is no time for a counterattack deathstar move (but rather a new defensive position taken up by the "attack force".

Spoiler :

i. After evaluating the situation after the initial protective deathstar formation has been accomplished (maybe some of or most defensive units near Calixtla have fallen) it proceeds to make the counterattack deathstar planning. Lets say The defenses around Calixtla held barely, two longswordsman dead in the process.

Spoiler :

 

[r_rolo1]

Looks promising enough ... will obviously only comment after you finish it

 

[CYZ]

Isn't the deathstar tactic something human players will see coming after a while? Wouldn't predictability benefit from some matter of randomness in this?

 

[r_rolo1]

Probably. But the simple fact is the AI needs to be taught to protect it's units and to move on order first. Think on it as the RL square formation that was widely used by pretty much every european army in the late XIX century: it was predictable that everyone would use it , but it gave enough security to the army in marching order for being worthwhile to forget that detail.

 

[CYZ]

That's true, those deathstars can be quite powerfull even if you know where they're heading and that they won't break formation. But if I understand correctly the ai will take a small surplus of melee units to replace fallen units. Wouldn't it be a good idea to have them move around the deathstar in a somewhat less predictable way to throw human players of their feet somewhat.

 

[Tyrael]

Nothing's happening when I click "Show" on the spoilers, except the button changes to "Hide". The size of the gray spoiler area doesn't change and I see no pictures, which I assume are supposed to be in the spoilers. Is it just me? I tried refreshing and reopening firefox, neither worked.

 

[Bibor]

The site is down for some reason... damnit.

 

[Slowpoke]

This is cool on a large scale, but on a "how to fix the a.i. with as little work as possible so one can get some results now rather than a year later" I think there's better alternatives. Tactics involving being aware of one's surroundings take a very long time, and are probably more suited to pure military games. Step one is very much needed, the grand war strategy for the A.I. stinks, but for tactics it should probably be simpler.

One thing the A.I. needs to keep track of is "total deaths vs kills" during a war. AFAIK right now the only "Cowardice" indicator is A) length of war + B) units threatening their city - C) units of theirs threatening your cities. Sufficient loss ratios should alone signify a lost cause.

Additionally, after every city conquered with moderate losses, or severe dip in kills/deaths ratio altogether without a city conquered or heavily damaged, there should be a regrouping phase in which the war machine is stopped. Severely damaged units should go back to cities and heal up. The A.I. at the moment doesn't understand that units are worthless unless massed, and a regroupin will artificially make this happen.

Finally, the A.I. thinks too MUCH many times, when it comes to individual units. One problem that a good indie freeware game "battle for wesnoth" had for a while was the A.I.s individual units would simply not attack if the risk was too high. However, the "intelligent" behaviour was really bad: it allowed the player to easily pick off units with little to no risk by shuffling units around (in Civ5's case it is the human's horsemen picking off the befuddled archers). By making the A.I. more bullheaded, an advantaged A.I. could push an advantage, even if it did it in a stupid way.

And lastly, of course, the main reason people stomp the A.I., is a balance reason not A.I. stupidity: Nerf Great Generals please.

 

[LDiCesare]

I can't see anything inside your spoilered sections so this doesn't help much.

Power ratings are extremely inaccurate. They give an estimate of quantities but no idea of quality of troops. AI often attacks with a vast superiority in numbers (like 4 or 5 to 1) and ends up slaughtered because pikes and muskets don't fare very well against foreign legion and artillery.
It's not obvious in your proposed algorithm how you evaluate this difference in quality.
Also, it's not obvious how you count in allies like other civs or city states. I've had 2 ai's attack me on the same turn, which reeks of coordination for instance.

You don't talk much about how you move your troops to target city. Or if you do, without seeing the pictures, it's hard to guess. I wonder how you fare if for instance the only way to the enemy passes through 2 tiles in a mountain range.

I agree with the need to keep track "total deaths vs kills", at least for offensive wars. I'd also like the ai to agree to peace proposals with terms instead of refusing anything you offer and then offering a city and a big lump of gold the next turn by itself when the situation didn't change.

 

[r_rolo1]

Yup, bibor, forget rapidshare for photos ... use imageshack or photobucket, their are far more fitting for what you want in here

 

[Bibor]

Yup, bibor, forget rapidshare for photos ... use imageshack or photobucket, their are far more fitting for what you want in here

Yeh sorry guys, my own web is down and it seems that rapidshare doesn't allow clear access to images (puts you to their frontpage blah).

 

[Ahriman]

Some nice work, but I think this needs to be expanded to take into account alliances (eg even if Civ A is stronger than me, it might not be stronger than both me allied with CivB), local force concentration (it doesn't matter if you are tougher than me if your army is on the other side of the world, I can still make some quick progress) and other engagements (if you are already at war with another player, I should be much more willing to join in to attack you, ESPECIALLY if you are powerful, since this might be the only chance I get).

As a human player, I will often declare wars on the strongest player nearby I where I don't expect to gain much territory, but simply want to distract the player and destroy a lot of their army, to prevent them from going off and conquering someone else.

Also, I think it risks not being Fun; I worried that you are going to deter war too much. We do not want it to be too easy for a human player to deter war by keeping a large store of gold. Gold stores are not the same as actually committing the gold to buying units (which I then have to maintain). Fighting off enemy invaders, even when they are unsuccessful, is part of a fun game.

 

[g++]

GG's are not really the problem in my opinion. The major problem is the increase in movement from 1 to 2 for infantry and 2 to 4 for mobile units. The AI is clearly still written to only evaluate the tiles 1 or 2 in front of it and does not memorize troop location in fog of war which gives humans a massive advantage. Its essentially like playing peekaboo with an infant because the computer is blind 2 squares away and does not record previous combat like our minds do. So once you execute a hit and run attack the computer pretty much thinks it never happened. The computer should simply get a 4 tile view on higher difficulties. Essentially America's UA 2x for free and the AI's decision making code needs to be junked and re-coded for 4 square appraisals in combat.

The navy thing seems to be related to pathing and fog of war bugs combined with
a general desire to never build a navy so I think those are ingrained bugs from water tiles.

I think the computer likely already takes terrain into account at least a little but it should get more priority and the AI for ranged units needs to put way more priority on protecting itself. If I had a dollar for every time a cannon walked into my infantry since this games release I would be a rich man.

These are the three major problems imo.