Inner workings of the HoMM II AI


(Originally posted at http://www.celestialheavens.com/forums/viewtopic.php?t=12150 )

 

Combat AI

 

Fight value 

Every creature has a hard-coded "fight value," a number summarizing its worth in combat. The fight value is used quite often The fight value of a stack is simply the fight value of the creature times the number of creatures in the stack. 

Effects 

Heroes II chooses which spell to cast by computing a "heuristic," how many "points" it thinks casting a spell is worth, and picking the spell and target with the best heuristic. 

Many spells add or remove stack-modifying effects. There are fifteen such effects in HoMM II -- slow, haste, blind, bless, curse, berserk, paralyze, hypnotize, dragon slayer, blood lust, shield, the Medusa's petrify, anti-magic, stoneskin, and steelskin. The AI will compute a heuristic for how much the effect helps the creature, and use this to help compute its heuristic for casting a spell that will add or remove that effect. 

Here's how the heuristic for the various effects are computed: 


General: If the target has Berserk or Hypnotize already on it, then the heuristic for all effects except Anti-Magic is 0. Otherwise, the AI computes some number relating to the usefulness of a cast, and obtains the heuristic by multiplying that by the fight value of the stack, and then by a weight. Here are the weights: 


Haste: 0.1 
Slow: 0.1 
Blind: 0.4 
Bless: 0.45 
Curse: 0.45 
Berserk: 0.55 
Paralyze: 0.5 
Hypnotize: 0.65 
Dragon Slayer: 0.28 
Blood lust: 0.14 
Shield: 0.45 
Petrify: 0.25 
Anti-Magic: 0.2 
Stoneskin: 0.16 
Steelskin: 0.28 




Slow and Haste: If the potential target is adjacent an enemy creature, the heuristic is 0. Else, it estimates how many turns the creature will take to cross the battlefield both with and without the effect, and takes the difference. The heuristic is obtained by multiplying that difference by the weight and fight value. 

Bless and Curse: First, it computes the difference of the creatures max (Bless) or min (Curse) damage and its average damage. Multiplying that difference by the weight and fight value gives the heuristic. 

Dragon Slayer: If the potential target is adjacent a dragon, let x=1. Else, let x be the proportion of hostile creatures which are dragons. The heuristic is then x times the weight and fight value. 

Shield: The heuristic is the proportion of hostile creatures which are shooters (with a small bonus for castle combat), times the weight and fight value. 

Everything else: The heuristic is the product of weight and fight value.

 

Ballista and Turrets

There are four levels of priority. If a stack is blinded, paralyzed, petrified, berserkered, or hypnotized, it has priority 0. Otherwise, shooters have priority 3, flyers priority 2, and walkers 1. The turrets and ballista target the stack with highest priority. Ties are broken by the fight value of the stack. If there is a tie in fight value (e.g.: identical stacks), then the tie is broken in favor of lower stack index (i.e.: the one which is evaluated first). 

Stack Index Creature stacks are ordered by an index. For the most part, this is equal to the left-to-right order in which you bring them into combat, with summons being added at the end. It gets muddied though, as, e.g.: if a creature dies and its corpse is destroyed, then a new summon can get the lower stack index. (An army can have at most 20 stacks, which is very difficult to achieve outside of debug mode.)

 

General notes 

Rounding occurs in a lot of places, and I haven't really been tracking where. 

Also, note that the effects for Slow and Curse have negative heuristics, while the rest have nonnegative heuristics. However, the signs of all effect heuristics are often adjusted, so that e.g.: detrimental effects on hostile creatures have positive sign. 

Also, I forgot to mention: The heuristics for all effects is finally multiplied by the chance of the spell that casts it to succeed (usually 1, often 0, but 0.8 for Dwarves). Yes, this is the case irregardless of what spell is actually being cast. 

Durations 

The following table is used to weight spells by the duration left: 


0 0 
1 0.5 
2 0.65 
3 0.78 
4 0.85 
5 0.95 
6 1.03 
7 1.08 
8 1.12 
9 1.15 
10+ 1.18



Dispel, Mass Dispel, Cure, and Anti-Magic 

It first computed the sums of the sign-adjusted heuristics of the effects that will be removed, weighted by duration. 

When evaluating Mirror Image stacks, instead, the fight value of the stack is added. 

For Anti-Magic, the heuristic for the Anti-Magic effect, weighted by duration, is then added. 

For Cure, the fight value of the creature, times the proportion of the creature's HP recovered, times 0.75 is then added. 

Other effect spells 

This covers every spell except Anti-Magic which has a duration (i.e.: not Disrupting Ray, which is actually lumped with the direct-damage spells) 

The difference of the sign-adjusted heuristic of the effect added and any effect removed, both weighted by duration, is computed. (Bless and Curse override each other, Hypnotize and Berserk override each other, etc.) 

For blinded, paralyzed, and petrified creatures, the heuristic is set to 0, with the exception of defensive spells (Stoneskin, Steelskin, Shield, Mass Shield), where it is merely halved. 

For Stoneskin and Steelskin, when attacking a castle, the heuristic is multiplied by 1.5 for shooters. For Shield and Mass Shield, when attacking a castle, the heuristic is multiplied by 2 for shooters. 

Teleport 
The heuristic is 0. Always.

 

Chain Lightning

So, Chain Lightning hits a creature, and then moves on to the nearest creature which isn't immune. But how does it determine nearest? What measure of distance does it use? 

Pixels. It simply computes the Euclidean distance from the center pixel of one stack to that of another, and finds the closest. What if there's a tie? Sorry first player; you lose.