Fast units should get the first strike in battles

[dimag0g]

Currently, when the AI governs fast units in a battle, it will move them as far as possible in every move, potentially letting the enemy have the first strike, even with slower units. E.g. imagine a bunch of rogues (Y) with the speed Sy of 5 cells per turn charge towards dwarves with Sx of 2 cells. Only battlefield cells along the chosen path are displayed:

1 2 3 4 5 6 7 8
X|▀|█|▄|▄|▄|▄|Y|

The current AI will move Y into cell 3, giving X the opportunity of the first blow, which is unwise.

The simplest fix is the following heuristic: if the distance D between X and Y is less than twice the speed Sy (6 < 2x5), then Y should only move by D - Sy = 6 - 5 = 1 cells. The idea is to reach the enemy the next after walking the maximum distance Sy, minimizing exposure to the first strike from enemy units.

In the example above, Y will move into cell 7, avoiding being hit by the enemy slower than themselves, while making sure they could strike the next turn, unless X retreats. Note that this could be exploited by the enemy who has magic or shooters: retreating X by one cell at a time would buy them several turns. Perhaps it makes sense to only make a partial move if Y was not hit in the previous turn.

A different yet still simple fix is to consider both speeds (Sx and Sy). If the distance D between X and Y is less or equal than Sx + Sy (6 <= 5+2) and the unit is faster than its target (Sy > Sx; 5 > 2) then Y should move by D-Sx-1 = 6-2-1 = 3 cells. This solution minimizes the chances of X to retreat, but exposes Y to potential attacks from other enemy units which Y is not targeting.

In the example above, Y will move into cell 5, avoiding being hit by X, while making sure they could strike X the next turn, even if X retreats.

A more complicated solution would include the evaluation of the entire battlefield. Each cell can be assigned a rating equal to the total potential damage from all enemy units during the next turn. When D becomes less than twice the Sy, Y will modify its path to stand in a cell with the smallest expected damage, while still being able to reach its target X in the next turn.

PS. Please let me know if I overlooked an already existing issue. If nobody is working on the topic, I would consider working on it, perhaps implementing the simplest solution to begin with. Don't expect miracles from me though, it will be the first time I touch the AI code.

[Branikolog]

If I'm not mistaken, there's no such issue opened.

Nice suggestion, but in future we need to take into account, that slower units can block the target troop (for example, when we talk about ranged troops) which prevents our fast unit from attacking target unit the next turn. This can be easily abused by players.

[dimag0g]

@Branikolog Yes, there will be several edge cases to sort out once this is implemented. I suppose we will never figure out all of them until we implement this and test. I'm pretty certain this feature will make battles more challenging on average even with some issues like the one you mention.

BTW, could anyone experienced with the AI give me a hint which files/functions I should be looking at? battle_army.h? battle_troop.h?

[LeHerosInconnu]

Hello @dimag0g and @Branikolog,

I had made a small list of remarks concerning the improvement of the AI from Heroes 2: https://heroes2.forumactif.com/t936-fheroes2-1-0-enhanced-fheroes2-combat-ai. Feel free to open new issues for them (some features have already been implemented by @idshibanov). @idshibanov is working on AI improvement, and it would be nice to see with him what he has already planned to avoid working on the same task. :)

[dimag0g]

@LeHerosInconnu, thanks, that was an interesting read. Personally, I believe it is best to collect all such improvement ideas in a single place, github issues page seem just right for that.

I'll wait for @idshibanov to tell what he thinks of this particular improvement before I do any coding. Right now I'm just browsing through AI code trying to make some sense out of it for myself.

[idshibanov]

In general I agree that we need this kind of logic. I already had this feature on my personal list, I just rarely create issues myself because we already have so many of them open. If you want to get your hands into AI code - be my guest and have fun.

A more complicated solution would include the evaluation of the entire battlefield. Each cell can be assigned a rating equal to the total potential damage from all enemy units during the next turn. When D becomes less than twice the Sy, Y will modify its path to stand in a cell with the smallest expected damage, while still being able to reach its target X in the next turn.

I think this is a way to go instead of adding situational logic. I already have logic calculating something similar to "rating equal to the total potential damage" in BattlePlanner::archerDecision when AI searches for a safe spot to move to. Start from there and see if you can apply this for the melee units.

BTW, could anyone experienced with the AI give me a hint which files/functions I should be looking at? battle_army.h? battle_troop.h?

What you need is ai_normal.h and ai_normal_battle.cpp. BattlePlanner class is the one making AI decisions during the combat, picking the Actions which are then executed by Arena code. Note that for melee units I have offensive/defensive code paths which are selected based on both armies strength and composition.

Also keep in mind that there's a big change coming in #2943, waiting for the merge. You might want to merge it locally to avoid conflicts. If you have more questions let me know.

[idshibanov]

Okay, I just took a stab at this myself in order to try to get in this feature into upcoming 0.9.2 release.

In the example above, Y will move into cell 7, avoiding being hit by the enemy slower than themselves, while making sure they could strike the next turn, unless X retreats. Note that this could be exploited by the enemy who has magic or shooters: retreating X by one cell at a time would buy them several turns. Perhaps it makes sense to only make a partial move if Y was not hit in the previous turn.

I thinking doing minimal moves (1 tile in your example) is problematic as it limits unit options next turn.

A different yet still simple fix is to consider both speeds (Sx and Sy). This solution minimizes the chances of X to retreat, but exposes Y to potential attacks from other enemy units which Y is not targeting.

In my implementation I tried to handle both quoted issues. AI calculates threat for every tile on the path to target (avoiding going through the full board). If threat is 0 (no enemy can reach) unit will move up as close to the enemy as possible, otherwise it will try to minimize damage received from all enemy units.

[zenseii]

Hi, @oleg-derevenetz. I believe this issue is quite similar to the one you recently addressed with your PR. Do you think we should close this issue?

[oleg-derevenetz]

Hi @zenseii

I believe this issue is quite similar to the one you recently addressed with your PR. Do you think we should close this issue?

Actually the "first strike" logic should have been already implemented a long time ago, my PR just fixed some corner cases. I don't know why this issue is still open.

[ihhub]

Then I am closing this issue :)