Inner workings of the HoMM II AI

[Darmani]

This will be a series of posts explaining how the HoMM II AI makes its decisions. I'll post things as I figure them out. Expect a lot about the combat AI now, but don't expect anything on the adventure map AI for a while.

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:

Code: Select all

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.

[UndeadHalfOrc]

Very interesting.

[GreatEmerald]

That's pretty much how AI in general works. You have to give priority to things and define certain conditions which define whether or not using something will be favourable.

[kyrub]

Amazing work, thanks for sharing.
Do you plan to improve the AI?

[Darmani]

If my Grad AI class taught me anything, it's that AI is so broad that every computer scientist can call themselves an AI researcher. Data structures are AI! Shortest-path searches are AI! Random number generation is AI! Linear programming is AI!

As far as game AIs go, you have to make your comparisons pretty loose to say that's how they all work. Most chess AIs evaluate positions using a similar heuristic function -- but only after looking ahead several moves, something the HoMM II AI does not do at all.

It's easy to spend hours tweaking weights without improving results -- I've been there. Theoretically, you can think of heuristics as attempting to estimate the probability that you are in a situation where a given cast is the optimal one, given limited information. This is sound as long as the heuristic for a cast is proportional to the log-likelihood that you are in a situation where the cast is best. Judging by the even numbers, there's no doubt that these weights were created by hand-tweaking rather than by any data-driven approach. Of course, a data-driven approach is a lot of work, and a good heuristic is usually beaten by a deeper lookahead.

Do I plan to improve the AI? Maybe, but not in the near future. The AI really needs to be completely rewritten and put on more solid ground. Unfortunately, at the moment, the combat logic is completely intertwined with the combat graphics. Improving network play is a much better target.

[GreatEmerald]

Yes, but the whole idea is the same, different actions get a different rating plus they are scripted. The only alternative I know is having AI like in current Arcomage Clone where the computer simply takes the first card it can use and plays it... Which I hardly consider an AI.

Extending it to anticipate enemy's moves may be a little too much for a single-threaded app. Waiting for the AI to move is never a good thing.

[Darmani]

In order for the AI to choose the best move, there must be a notion of "best" move. This is very hard to do without having a notion of "better" move. No matter how it compares moves to determine which one is better, since there's only a finite number of moves, it winds up being equivalent to assigning a score to the move and comparing the score.
(In fancier terms: Every total ordering on a finite set has an embedding in the natural numbers.) So yes, in that sense, every AI is written this way, but this observation isn't very useful for discussing AI design.

[UndeadHalfOrc]

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

That formula doesn't explain why the computer will fly in 50 black dragons just to kill 1 archer. (They fixed this in H3)

[ThunderTitan]

That formula doesn't explain why the computer will fly in 50 black dragons just to kill 1 archer. (They fixed this in H3)

Because obviously something somewhere makes it so that a ranged troop has higher priority then any number of melee troops... either a bug or an oversight.

[Darmani]

No, because this is only how the heuristic for effects is computed. This isn't how the heuristics for spells is computed. (For example, the heuristic for casting the "Haste" spell on a Slow'ed creature is the sum of the heuristic for removing the "Slow" effect and adding the Haste effect.) This has nothing to do with how the AI moves its troops.

For a taste of that, I think we already guessed all of this, but:




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.)

[UndeadHalfOrc]

There is an ongoing open source remake of Heroes 2. Obviously they'll have to rebuild the AI from scratch.

Perhaps you'd like to get in touch with them, Darmani? (Sorry, can't find a link to their project at the moment)

[Kristo]

So Darmani, how are you able to determine all this? Painstaking research in game? Disassembled code? Both? I ask because I think there are a few of us here with a software background who could help.

[Darmani]

From what I know of behavioral psychology, saying too much publicly will destroy my motivation (and please don't speculate publicly either). If you PM me, I can try to share what I've done, though I don't think I'll be logistically capable of collaborating for a bit.

Anyway, I guess the short answer is disassembly.

By the way, I've not tested it, but I believe there's a bug so that it actually bases the heuristic for the Dragon Slayer effect on how many dragons there are on its own side.

[kyrub]

(stupid comment self-deleted)

Do I plan to improve the AI? Maybe, but not in the near future.

Pity. I was looking forward to some improvement.

[Darmani]

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:

Code: Select all

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.

[GreatEmerald]

Interesting, teleport does work fine in HoMM3.

[Darmani]

This isn't *really* AI, but

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.