Improved weapon selection

[decker]

Greetings fellow developers,

I'm interested to improve the way weapons are selected in a fight (both on
offense and defense). In this post, I will explain how the selection is done
currently, then I will propose a way to improve on it. Since this is not a
trivial change, I would need a confirmation to proceed before making my
modifications.


Currently, the weapon-selection code is located in many files:

Code: Select all

File ai.cpp line 98:

int choose_weapon(const location& attacker, const location& defender) {
	<snip>
        int best_attack_rating = -1;
        int best_attack = -1;
        for(size_t n = 0; n != attacks.size(); ++n) {
			const battle_stats stats = evaluate_battle_stats(get_info().map, get_info().teams, attacker, defender, n, get_info().units, get_info().state);
			const int attack_rating = stats.damage_defender_takes*stats.nattacks*stats.chance_to_hit_defender;
			if(best_attack == -1 || attack_rating > best_attack_rating) {
                 best_attack = n;
                 best_attack_rating = attack_rating;
            }
		}

		return best_attack;
	}


File ai_attack.cpp line 280:

int ai::choose_weapon(const location& att, const location& def,
					  battle_stats& cur_stats, gamemap::TERRAIN terrain, bool use_cache)
	<snip>
	for(size_t a = 0; a != attacks.size(); ++a) {
		const battle_stats stats = evaluate_battle_stats(map_, teams_, att, def, a, units_,
		                                                 state_, terrain);

		//TODO: improve this rating formula!
		const double rating =
		   (double(stats.chance_to_hit_defender)/100.0)*
		               minimum<int>(stats.damage_defender_takes,d_hitpoints)*stats.nattacks -
		   (double(stats.chance_to_hit_attacker)/100.0)*
		               minimum<int>(stats.damage_attacker_takes,a_hitpoints)*stats.ndefends;
		if(rating > current_rating || current_choice == -1) {
			current_choice = a;
			current_rating = rating;
			cur_stats = stats;
		}
	}


File playturn.cpp line 490:

class simple_attack_rating
	<snip>
	bool operator<(const simple_attack_rating& a) const
	{
		//if our weapon can kill the enemy in one blow, the enemy does not
		//drain back and our weapon has more blows, prefer our weapon
		if(stats_.damage_defender_takes >= stats_.defender_hp &&
		   stats_.amount_defender_drains == 0 && 
		   stats_.nattacks > a.stats_.nattacks)
		   	{
			return false;
			}
		
		int this_avg_damage_dealt = stats_.chance_to_hit_defender *
				stats_.damage_defender_takes * stats_.nattacks;
		int this_avg_damage_taken = stats_.chance_to_hit_attacker *
				stats_.damage_attacker_takes * stats_.ndefends;
		
		int other_avg_damage_dealt = a.stats_.chance_to_hit_defender *
				a.stats_.damage_defender_takes * a.stats_.nattacks;
		int other_avg_damage_taken = a.stats_.chance_to_hit_attacker *
				a.stats_.damage_attacker_takes * a.stats_.ndefends;
		
		//if our weapon does less damage, it's worse
		if(this_avg_damage_dealt < other_avg_damage_dealt)
			return true;

		//if both weapons are the same but
		//ours makes the enemy retaliate for more damage, it's worse
		else if(this_avg_damage_dealt == other_avg_damage_dealt &&
			this_avg_damage_taken > other_avg_damage_taken)
			return true;

		//otherwise, ours is at least as good a default weapon
		return false;
	}


File actions.cpp line 483:

battle_stats evaluate_battle_stats(const gamemap& map,
	<snip>
	double best_defend_rating = 0.0;
	int defend_with = -1;
	res.ndefends = 0;
	for(int defend_option = 0; defend_option != int(defender_attacks.size()); ++defend_option) {
		if(defender_attacks[defend_option].range() == attack.range()) {
			const double rating = a->second.damage_against(defender_attacks[defend_option])
			                      *defender_attacks[defend_option].damage()
			  * defender_attacks[defend_option].num_swarm_attacks(
d->second.hitpoints(), d->second.max_hitpoints())
			  *defender_attacks[defend_option].defense_weight();
			if(defend_with == -1 || rating > best_defend_rating) {
				best_defend_rating = rating;
				defend_with = defend_option;
			}
		}
	}

Here's a summary of the current selection process:

The player or the AI is considering to attack a defender unit with an attacker
unit. In both cases, the attacker wants to choose the best weapon for the
attack. To evaluate the best offensive weapon, the evaluate_battle_stats()
function is called. This function selects the best defensive weapon using a
simple "rating" formula and obtains the stats of the battle (damage dealt per
blow, number of blows, HP drained per blow, etc). With the info provided by
evaluate_battle_stats(), the code selects the best offensive weapon, also by
using a simple "rating" formula.

The rating formula used on defense is essentially this:
rating = damage_dealt_to_attacker_per_blow * nb_blows * defense_weight

In 99% of the cases, the weapon that does the most damage is selected. However,
the 'defense_weight' attribute can be used to make a weapon more or less likely
to be used (its default value is 1.0). Noyga provided an example where
'defense_weight' is useful:

In his faction, a unit can either retaliate with a lance (piercing) or a shield
(impact I think, with slow). Since the lance does more damage, it is almost
always selected. However, Noyga wanted the lance to be used against cavalry
units and drakes but the shield against other units. Hence he increased the
'defense_weight' attribute of the shield to obtain the desired behavior.

Another use of 'defense_weight' is setting it to zero to prevent a weapon to be
used on defense (thus making the weapon only usable on attack).

Of the regular units of Wesnoth, three makes use of the 'defense_weight'
parameter:

The Drake Warden and Drake Slasher use 'defense_weight' so that their
first-strike melee attack is prefered to their other non-first-strike melee
attack with higher damage. Also, the Giant Scorpion uses 'defense_weight' so
that its poisoning tail is used on defense.

The rating formula used on attack is about the same as the one used on defense,
except that 'attack_weight' attribute is not used in the code. The WML defines
this attribute but it does not appear to be supported in practice.


Improving weapon selection:

The rating formulaes used currently are simple and fit into the KISS philosophy
of Wesnoth. However, their results are sometimes suboptimal. Here are a few
examples:

A dwarve attacks a 3 HP skeleton with its hammer (10-2) instead of its axe (4-3)
because the hammer does more damage. A scorpion attacks an already poisoned or
undead unit with its tail because of 'defense_weight'. The unit described by
Noyga defends with its shield against an already slowed unit.

Granted, these cases does not happen often. Usually, units have only one choice
to defend. Likewise, their attack choice is also often limited. When there is a
choice, the simple heuristics gets it right most of the time. Still, it would be
possible to make smarter choices.

To improve the selection process, smarter heuristics would have to be used.
Here's how I'd do it:

The AI/GUI code calls evaluate_attack() to select the best weapon on offense.
The evaluate_attack() function takes several arguments: the attacker and
defender units, the expected location of the attack and an heuristic
"comparison" function. The evaluate_attack() function iterates on each offensive
weapon and compares the "best" weapon against the "current" weapon using the
comparison function.

To provide relevant informations to the comparison function, the
evaluate_attack() function calls evaluate_battle_stats(). This function has two
purposes: 1) select the best defensive weapon and, 2) provide statistics on the
potential battle.

Currently, evaluate_battle_stats() selects the best defensive weapon *before* it
evaluates the statistics of the battle. Thus, there isn't much information to
work with to select the defensive weapon. My idea is to tweak
evaluate_battle_stats() so that it computes the statistics for each potential
defensive weapon and uses another "comparison" function to make the selection.
In other words, when evaluate_battle_stats() is called, it iterates on each
defensive weapon that is in the same range of the attack weapon. It compares the
"best" defensive weapon against the current weapon using the defensive-weapon
comparison function. The output of evaluate_battle_stats() is the best defensive
weapon and the associated statistics.

In resume, there are basically two comparison functions, one for offense and one
for defense. The offensive function chooses the attack weapon that will be used,
and the defensive function chooses the best weapon to defend against each
offensive weapon considered.

Since function pointers would be used to call the comparison functions, it would
be possible to have many offensive comparison functions. That would enable the
AI to adjust its strategy based on the current state of the game. Also, the AI
and GUI code could use different functions. My idea is to keep things simple for
now and use a single offensive compairison function both for the GUI code and
the AI code. Normally, the comparison function used on the defense should be
unique.

It would be necessary to change the purpose of the 'attack_weight' and
'defense_weight' attributes. My proposal is to change these attributes to
'attack_enabled' and 'defense_enabled'. If it's 1, the weapon may be used on
attack/defense, otherwise it may not.

Performance issues:

The new implementation would be slightly more CPU-intensive. The heuristics used
in practice would contain more code than the current simple heuristics to handle
special cases. Also, the battle statistics would be computed more often in the
(rare) case where there are more than one choice for the defensive weapon. Yet,
I don't expect the change to have a signifiant impact on the overall
performance.


Thanks for reading, I welcome your comments on the proposed implementation...

[Noyga]

Hello,
About the *weight, i just implemented a minor change : now setting it to 0 disable the attack for attacking (attack_weight=0) or defending (defend weight=0).

In most cases the default weapon is the one that has the biggest :
damages per strike * number of strikes * weight value
So it is quite simple to adjust the weight to obtain a wanted behavior, sometimes we would would just use the weapon more than usual, sometimes almost exculsively on attck/defense.
I think it is a nice feature because it gives the possibility to adjust the behaviour so it can match more closely to the behaviour a real unit would have or make the unit special by its non standard behavior.
I don't really mind if the weighting system is changed provided :
- it stays simple ... It shouldn't be too difficult to adjust the weight
- an higher weight doesn't always make the weapon exclusive. I think it is also interesting to have non standard behaviour that can still use more than one weapon on attck or defense.

For attack, since the player can always override the choices i think it is always a good thing to improve the selection, it would makes the AI better and helps newbies.
This may however probably break how attack_weight is IHMO supposed to work.
Well since attack_weight is already non functionnal and never used so far i guess that is not a big deal.
I think however this setting can be interesting for some unit in a campagain whose behaviour would match more closely to its roleplay throught it may be stupid in some cases in a optimisation perspective.
For units potentially controlled by a player (a player or an AI in a MP games) i think this setting doesn't make sense (except attack_weight=0 to disable the attack) so we can just ignore the values ... Well those units would normally never have this setting modified, so it is maybe not a problem.
For these reason and the fact you may have better ideas about the weighting system, i hesitate to commit a defense_weight-like attack weight (i already implemented in my local folder).

For defense on one hand it would be nice to have a smarter selection.
On the other we can figure that the unit don't have as much time as the attacker to plan its attack, so it may make suboptimal choices.
I'm personnally happy with current defense.

For the organisation of the code itself it is always nice to remove duplicated functions, code cleanup are always welcomed and the other changes you suggest seems very nice, i would say : go for it !
I'm not sure you should change the defense behaviour through.
Perharps we shall test the two (one with current defensive behaviour, one with optimised defense behaviou)r & compare.

About the performance issue well we will see it it is too much CPU intensive or not.

[Noyga]

Here is another possible reason against a smarter defense : the defensive weapon would no longer be easy to predict, so i may complicate slightly the attacker's task.

[silene]

Also, the battle statistics would be computed more often in the
(rare) case where there are more than one choice for the defensive weapon. Yet,
I don't expect the change to have a signifiant impact on the overall
performance.

The code may have changed since then, so my comments may be irrelevant. But at the time I was working on this code, this is how I remember it to be: in order for the AI to get a good feel of the outcome of a big battle, it is running a lot of simulations on a set of movements involving many units. To speed it up, battle statistics are computed once before (without any supposition on the states of the units), and then cached and reused for all the simulations.

I probably misunderstood what you were suggesting, but if you meant to say that battle statistics would no more be cached in order to take into account units that have been slowed or poisoned during the simulation (since it would change the weapon used), then I expect a massive performance drop of the AI.

[Boucman]

I don't remember evaluate_battle_stat being a performence hit... it's quite straightforward IIRC


ok, a couple of points though

first, in the utils/ folder of BfW you will find a small perl utility called prkill, it was made by ott, and probably would help you with your heuristic.... it's perl, but the ideas might be usefull

don't dismiss the AI way of doing things right away either... the battle system is starting to become quite complex with abilities, leveling and all that sort of stuff taken into account, and it might be simpler and faster to do dry runs than to do a complete heuristic approch
(if you go that way, it might be worse adding a "dry run" mode to the attack function so it's the same code that is used for fake and reall attack, this would avoid future discrepency between the two modes)

OTOH the heuristic approch is tempting...

here is how I would do it (more ideas thrown around is never a bad thing )

add a new field to evaluate battle stat "outcome value" which would be a heuristic estimate of how "good" the outcome of the battle is. this outcome could take all sorts of things into account... abilities, death of A or D, leveling up... all the information needed to estimate that is available when calling evaluate_battle_stat

this would take attack/defense weight into account by simply multiplying a defoult aoutput by both those values. thus a value of 0 would reduce the output to 0 effectively disabling the attack

once you have calculated that for all attacks/defense pairs,
for each attack only keep the pair with lowest result (defender choose the weapon which gives the worst result for attacker)
and then the best remaining pair (attacker choose the best outcome for him)


when the player is human, the last step is only chosen to highlight the best weapon
when it's an AI, this choice is taken without doing any AI specific computation to choose the weapon. The heuristic is only at one place... code refactored properly

[decker]

Thanks for the comments! I browsed the code again and considered the points you
brought to my attention.


> The code may have changed since then, so my comments may be irrelevant. But at
> the time I was working on this code, this is how I remember it to be: in order
> for the AI to get a good feel of the outcome of a big battle, it is running a
> lot of simulations on a set of movements involving many units. To speed it up,
> battle statistics are computed once before (without any supposition on the
> states of the units), and then cached and reused for all the simulations.

> I probably misunderstood what you were suggesting, but if you meant to say
> that battle statistics would no more be cached in order to take into account
> units that have been slowed or poisoned during the simulation (since it would
> change the weapon used), then I expect a massive performance drop of the AI.

Yikes! You are indeed quite right. I missed this part the first time I skimmed
over the AI code. For reference, here's how I think it currently works.

Code: Select all

File ai_attack.cpp line 353:

<< If I understand correctly, this function analyses the attack on one target
   with several gansters. >>
void ai::attack_analysis::analyze(...)
	
	<<snip>>
	
	<< I assume there is one "movement" for each gangster attacking the
	  target. >>
	for(m = movements.begin(); m != movements.end(); ++m) {
		battle_stats bat_stats;
		
		<< Note: choose_weapon() calls evaluate_battle_stats(). >>
		const int weapon = ai_obj.choose_weapon(m->first,target,
			bat_stats, map[m->second.x][m->second.y],true);
		
		wassert(weapon != -1);
		weapons.push_back(weapon);

		stats.push_back(bat_stats);
		hitpoints.push_back(units.find(m->first)->second.hitpoints());
	}
	
	<< We run a number of simulations of the attack. >>
	for(int j = 0; j != num_sims; ++j) {

		int defenderxp = 0;

		bool defender_slowed= defend_it->second.slowed();

		int defhp = target_hp;
		
		<< Gang on the target until it is dead or we run out of 
		   gangters. >>
		for(size_t i = 0; i != movements.size() && defhp; ++i) {

Thus, when the AI plans to attack a target with several units, it first
determines the weapon that each unit will use against the target without
considering the state of any units. In this way there is no need to make
repeated calls to evaluate_battle_stats() during the simulation. As you point
out, it represents a massive performance gain (I estimate that the amount of
time required to execute evaluate_battle_stats() is in the same order as the
amount of time required to simulate a battle the way it is done currently).

The current combat simulations are therefore less precise but faster. A few
remarks on this topic:

1) Even if we plan with a suboptimal weapon, the actual attack can proceed with
a better weapon. The predictions of the AI will be skewed because of this
however, and I don't know how much it would affect the "smartness" of the AI.

2) As Boucman pointed out, it is tricky to keep the code that simulates a battle
and the code that actually performs the attack synchronized. I spotted two
locations where I believe there is a discrepancy:

- Backstab. This one is documented somewhere in ai_attack.cpp:

//note that we *could* also check if a unit plans to move there before we're
//at this stage, but we don't because, since the attack calculations don't
//actually take backstab into account (too complicated), this could actually
//make our analysis look *worse* instead of better.
//so we only check for 'concrete' backstab opportunities.
//That would also break backstab_check, since it
//assumes the defender is in place.

- Berserk. The combat simulation does not consider the 'berserk' attribute as
far as I can see. In fact, I don't see a mention of 'berserk' anywhere in
the AI files. It is probable that the AI doesn't realize the true potential
of ulfing an adept.

I'll continue this discussion as I address the following point...

> don't dismiss the AI way of doing things right away either... the battle system is
> starting to become quite complex with abilities, leveling and all that sort of
> stuff taken into account, and it might be simpler and faster to do dry runs than
> to do a complete heuristic approch
> (if you go that way, it might be worse adding a "dry run" mode to the attack
> function so it's the same code that is used for fake and reall attack, this would
> avoid future discrepency between the two modes)

I think the approach used by the AI is generally fine. I do not want to
try to predict the outcome of a combat with heuristics, as it is way too
complex. I believe dry runs are the way to go since they are both more precise
and easy to implement. Let me summarize on this topic:

The AI is planning an attack against a unit. The attack can proceed with several
weapons. The AI can either 1) choose the weapon to use with an heuristic and
make all dry runs with this weapon or 2) make dry runs with each of the possible
weapons (if there are 2 weapons, then there are 2 times as many total dry runs).
Currently, the weapon choice is done with an heuristic, in a stateless manner.

I believe that making one dry run serie per weapon would be too expensive. I'm
more inclined to try a stateful heuristic, ie choose the weapon based on
the current state of the attacker and the defender. To do so,
evaluate_battle_stats() would need to be passed arguments that define the
expected state of the battle , ie attacker_slowed, defender_slowed=1, etc.
With the output of evaluate_battle_stats(), the heuristic could make a good
enough choice.

As Silene points out, this may results in a massive performance drop (my
guess is that would make the AI two times slower). On this issue, there's
also something called 'weapon_cache' that is apparently used to cache the weapon
choices that have been done in the past. I don't know what's the actual impact
on the performance.

Still, a stateful heuristic would make the AI plan better. Currently, the AI
attacks with the weapon it has chosen in a stateless manner. It results in a
stupid behavior from time to time. If we make the AI picks a better weapon in
the actual attack, it may jeopardize its predictions.

In resume, I don't know what should be done about this. Can we afford the extra
time, and is it worth it? Perhaps optimizing "safely" at the end to avoid some
stupid behaviors would be enough...


> first, in the utils/ folder of BfW you will find a small perl utility called
> prkill, it was made by ott, and probably would help you with your heuristic
> ... it's perl, but the ideas might be useful

Cool! Something that documents how the probabilities are computed. I'll have a
closer look later...


> (if you go that way, it might be worse adding a "dry run" mode to the attack
> function so it's the same code that is used for fake and reall attack, this
> would avoid future discrepency between the two modes)

I thought some time ago to make a battle simulator that accurately models a
battle. Currently, the evaluate_battle_stats() function doesn't handle drain &
slow properly. The AI code doesn't run the battle accurately either. I toyed
with the idea of using the code of the attack() function both to perform the
actual attack and to simulate it and decided against it. There are three issues:

1) GUI code is intermixed in this function and would need to be bypassed.

2) Replay code is intermixed in this function to replay past attacks and would
also need to be bypassed.

3) The fake attack requires additional parameters to consider the 'would be'
situation (terrain of the attacker, slow, hp, etc.).

I'd rather have two different functions and risk some discrepancies than having
one monstruous function. I planned to handle this issue once I settled the
weapon selection stuff...


Summary: having a better attack heuristic might prove too slow and Noyga does
not want a better defense heuristic. So what should I do? More comments welcome,
thanks for your time!

[Yogin]

ok, as I'm not a coder, some of my understanding may be off.

Nevertheless, here's my $.02.

If the AI simulates entire battles in order to decide whether to attack or not, with "simplified", or "sub-optimal" weapon choices, I don't see that as a problem as long as when engaged in the actual battle it can choose the "optimal" weapons.
Why? Well, certainly, the AI would miss certain opportunities to attack as present than were it to simulate fully(I think what Decker is calling state-ful), since a better weapon choice could've yielded better simulation results, and therefore a more aggressive strategic decision.
However, I think the AI is too aggressive as is, and over-attacks, putting itself in tactically poor situations, so this "sub-optimal" simulation would just curb this behavior.
Secondly, having the actual battle decisions be "stateful" and "optimal" simply increases the probability of successful attacks, and isn't a bad thing, imo.

It's a philosophical issue, and I think if the patch were to fix the AI choices DURING the battle, and leave the sub-optimal choices for BEFORE the battle informing whether to engage in offensives, it would bring the AI strategy more along the lines of Sun-Tzu: never engage in battle unless victory is assured(paraphrased). When the AI finally did engage in a battle, it's performance would be better than it had expected. If this resulted in over-passification of the AI, it would be a problem, but I don't think it will.

Summary: Leave it simple for the simulations, but at the point of actual attack, make it smarter. I think this results in a better AI than simple for both, or smart for both.

[decker]

> Why? Well, certainly, the AI would miss certain opportunities to attack as
> present than were it to simulate fully(I think what Decker is calling
> state-ful), since a better weapon choice could've yielded better simulation
> results, and therefore a more aggressive strategic decision.

That's also what I thought at the first glance. However, there is a potential
problem. The "better" attack might not be the one that makes the most damage.
Currently, the AI mostly chooses the weapon that does the most damage and
makes the attacker receives less damage. Poison and slow are not taken into
account.

Code: Select all

const double rating =
		   (double(stats.chance_to_hit_defender)/100.0)*
		               minimum<int>(stats.damage_defender_takes,d_hitpoints)*stats.nattacks -
		   (double(stats.chance_to_hit_attacker)/100.0)*
		               minimum<int>(stats.damage_attacker_takes,a_hitpoints)*stats.ndefends;

If, at the time of the actual attack, the first attacker suddently chooses to
cause less damage, but poison its foe and receive less damage, it might
become impossible for the AI to kill the defender as it originally assumed.
So it is not clear that the cleverness of the AI would improve with
last-minute overrides.

[Yogin]

This last example sounds similar to what we were talking about in the MP thread: "UD vs woses." The decision to poison, or use a poisoning unit must be informed by the greater strategic(tactical) decision to attack, and how many units to attack with. eg. you don't poison a unit you plan to kill this turn, you only poison units you know will survive your attack.

[Sapient]

This comes up very rarely, but I thought I'd mention it: if the AI lands on an object that grants a new attack option, it is not considered for the attack in progress.