Defence strategies? (for the AI)

[DaftVirgin]

When I have to defence, I usually retreat just behind the enemy's possible moves. I for a line of defence and I let them come to me first. When they are close enough, I charge at them with my defence line.

Hope this helped

[Yoyobuae]

I'm mostly a (learning) MP player. So I'm just gonna post some concepts I've learned thru experience.

Firstly, hex reachability is very important, in more ways than one. For example, terrain defense is irrelevant if the enemy can't reach you. Or taking further, it is irrelevant if the enemy is unlikely to attack. And why is that? Because those enemies will then be within reach of more your own units, which fight back and possibly kill the enemy.

This results in a sort of "pressure" being exerted by all units in the playing field. When pressure is equal neither force advances/retreats, when the pressure isn't balanced then one side retreats while the other advances. ToD also comes into play, causing the usual "back and forth" on certain match-ups.

Of course, how to program this into an AI is a real problem. There needs to be a way to keep track of how "dangerous" a hex is, both for the AI's own units and the enemy units. Probably keep this in some sort of structure, after each move it gets updated with the new info.

For the AI, making strong defensive position will involve calculating a position that doesn't put it's units in too much danger (by limiting the number of attackers via ZoC walls or such) and in turn puts the enemy in a dangerous position if it were to attack (by supporting the defensive line with heavy hitters that can reach and hit back the attackers).

[Caphriel]

You could probably achieve a fairly good approximation of how dangerous a hex is by calculating how many enemy units can reach hexes adjacent to it (something the engine already supports, since the user can have this displayed), and applying a ToD adjustment. A slower but more accurate method could calculate the potential and average damage that could be applied to any given hex instead of just counting units, and then adjust based on whether the AI is currently ToD-strong or -weak.

[Yoyobuae]

Yeah, I was thinking something like that.

The thing is that although a single enemy may be able to reach many hexes, it can only move to one of those in a turn. In general it might make hexes seem more dangerous than they really are.

Probably we might want to avoid "slow but accurate". Even a little slow can become way too slow if many iterations end up being needed. Probably some sort of score calculated with simple operations.

Also, the engine currently displays how many units can reach a hex, not how how many can reach adjacent hexes.

[Maiklas3000]

I wrote this in my review of LoW3: Ka'lian Under Attack, which is basically a defensive struggle for the allied leader until towards the end...

The AI for the allied forces needs to be improved, and it would be nice if the allied forces would cooperate with yours in some sense. I suggest taking a cue from flocks of birds or ant colonies, which self-organize by having each individual operate according to some simple rules. There should be rules like:

* somewhat prefer a hex two away from a friendly unit
* much prefer a hex next to a friendly unit
* more prefer a hex in line with two friendly units
* greatly prefer better terrain (no swimming without a good reason!)
* if you're poisoned, tremendously prefer villages, curers and healers, in that order
* if you're about to level up and are low on hit points, go for an easy kill if available (or easy combat if you just need one point), but otherwise avoid combat and seek healing

It would probably work best to have the computer move each unit one hex at a time, though that would be a big change.

To expand on what I said...

Bird flocking can be understood as emergent behavior arising from simple rules exercised by each individual bird. See Wikipedia. This strikes me as similar to what we want in Wesnoth... not V-shapes ideally, but lines.

Here is the algorithm I suggest...

For each unit, try each possible move (or a random sampling, if time is an issue.) Evaluate the move according to the following rules and any others that you want to throw in:

+1 for each friendly unit two hexes away
+2 for each adjacent friendly unit
+10 for being next to two friendly units who are not adjacent to each other
+20 for being next to two friendly units who are 180 degrees apart
-14 10% terrain
-8 20% terrain
-4 30% terrain
0 40% terrain
+5 50% terrain
+10 60% terrain
+20 70% terrain
etc.

(There should be a terrain differential bonus too, like when you could occupy a 60% hill surrounded by plains that the enemy could reach, for 30%, 40%, 50%, or 60% defense, depending on the enemy unit.)

About the raw terrain bonuses, as some have pointed out, sitting on 70% terrain is worthless if the opponent can't reach it, but with the threat of invisible units (e.g., Rangers) it's hard to be sure the opponent can't reach any particular hex, so I'd prefer the AI to err on the side of caution.

Choose the move with the highest score and repeat. If a unit still has movement points after moving, then leave it in this queue of units to move. (This will result in a fundamental change of how the AI moves its units, and it could be annoying to watch the AI scooting different units one or hexes at a time, I dunno.) You should probably add a noise function, so that the AI is not totally predictable.

Now, the next step is to add learning. Those weights, +1, +2, +5, etc., are difficult to know how to set. So set the program up to tune them itself, which is a simple form of learning. There's already a system for playing AI's against each other, so use that to evaluate a set of weights. For defense, you'd need to adjust the scenario, so that the defending AI is fighting an aggressive opponent, probably with more forces. Maybe the evaluation score would be whether the defenders survive or keep the offense out of a particular hex for X turns. Offense could be evaluated the same way. A neutral setting would be the typical way AI's are pitted against each other now, with an equal start against each other. This evaluation process is naturally CPU intensive, but just dedicate one mondo computer to it and let it work on it for a few weeks. One advantage of this approach is that you can just toss in every rule you can think of, like one for each idea in this thread, and any that are found unhelpful will tend to go to a weight of zero.

The engine for optimizing these weights could be made modular, so you could swap it out and try something else. Genetic algorithms, simulated annealing, neural nets... these are some of the possibilities. If that sounds scary, well, it's not really, but the first version can just have hand-set weights. I think the "flocking" behavior from simple rules would be the big win here, and the tuning of the weights would just be the icing on the cake.

[Jaykwon]

How does the AI currently deal with hidden units?
If this is not implemented already without my knowledge, it would probably be good to have the AI check what type of terrain his opponent team can hide in.
Should he in an upcoming battle be already outnumbered or evenly matched in terms of local strenght while moving his units, he should if possible choose a route that doesn't pass by such terrain types but still takes him to the intended square.

Low on battery so I'm keeping it short, but I suspect this could be applied after all other calculations, a simple check to see if a better route to the same target square exists. That would potentially prevent an already outnumbered AI from fighting an additional opponent in greatly favoured terrain, while also losing all moves and Maybe miss out on an easy kill.

[wesfreak]

I don't think anyone's said these ones before:

Defend against melee units with melee units and ranged units with ranged units so that the enemy takes max retaliation.

Keep in mind the maximum possible attacks that could be made on a unit. (assuming all enemy units attack that unit). If the chance that the unit is killed is more 10% than move that unit somewhere where there is a lower chance to be killed. (if this is too hard to make, then have the ai assume that all attacks will hit and move the unit if it would die)

Give each unit a value, depending on how important it is, with low cost units having a lower value, and have the amount of experience a unit has affect that value. Have lower value units defend higher value units. (so spearmen defend a mage, for example)

[CMaster]

For each unit, try each possible move (or a random sampling, if time is an issue.) Evaluate the move according to the following rules and any others that you want to throw in:

+1 for each friendly unit two hexes away
+2 for each adjacent friendly unit
+10 for being next to two friendly units who are not adjacent to each other
+20 for being next to two friendly units who are 180 degrees apart
-14 10% terrain
-8 20% terrain
-4 30% terrain
0 40% terrain
+5 50% terrain
+10 60% terrain
+20 70% terrain
etc.

...

Now, the next step is to add learning. Those weights, +1, +2, +5, etc., are difficult to know how to set. So set the program up to tune them itself, which is a simple form of learning. There's already a system for playing AI's against each other, so use that to evaluate a set of weights. For defense, you'd need to adjust the scenario, so that the defending AI is fighting an aggressive opponent, probably with more forces. Maybe the evaluation score would be whether the defenders survive or keep the offense out of a particular hex for X turns. Offense could be evaluated the same way. A neutral setting would be the typical way AI's are pitted against each other now, with an equal start against each other. This evaluation process is naturally CPU intensive, but just dedicate one mondo computer to it and let it work on it for a few weeks. One advantage of this approach is that you can just toss in every rule you can think of, like one for each idea in this thread, and any that are found unhelpful will tend to go to a weight of zero.

The engine for optimizing these weights could be made modular, so you could swap it out and try something else. Genetic algorithms, simulated annealing, neural nets... these are some of the possibilities. If that sounds scary, well, it's not really, but the first version can just have hand-set weights. I think the "flocking" behavior from simple rules would be the big win here, and the tuning of the weights would just be the icing on the cake.

By and large a good idea, here comes a bit of analytical finetuning:
Your weights concerning the defense reflect the way, most people tend to think about these percentages, like: "10%, ooh, scary", "40%, that's normal" or "70% is just 10% better than 60%". But the expected damage is the possible damage times the chance to hit, i. e. of 10 points possible damage, a unit standing on 70% terrain will get only 3 points damage on average. Seen the other way round, if you have a unit with 30 hitpoints on 70% terrain, your enemy will have to deliver 100 hitpoints to that hex in order to kill it, on average. On 60% terrain, that figure drops to 75, a decrease of one quarter! On the other hand, 10% defense would take only 33 hitpoints attack, 20% defense only increase the figure to 37.5, an almost neglectable difference.

What I'm saying is, that the weights should be linear to the damage necessary to kill a unit, which is linear to the resources bound, if the enemy decides to remove that unit. For example:
10 for 0%
11.1 for 10%
12.5 for 20%
14.3 for 30%
16.7 for 40%
20 for 50%
25 for 60%
33 for 70%
50 for 80%
100 for 90%
So now you know, why there is no 80% or 90% defense terrain in the game. It would simply be too good...

Another point: Defense is only good, if you have some hitpoints to defend. So I'd rather suggest to use the average hitpoints an enemy has to deliver to a unit to kill it as a score, that is: HP/(100%-defense).

[Maiklas3000]

Is the AI improved in 1.9.3 relative to 1.8.3? I searched the changelogs and found nothing substantial, but my experience is that the AI is better. I think it's better at retreating, better at healing wounded, better at flanking, and better in mutual support and moving to nondangerous hexes. True or false impression?

For defense, I really could not ask any more of the AI than it did under 1.9.3 in the scenario TRoW: The Vanguard (replay and screenshot here.) This is a peculiar scenario, but maybe there is something to be learned and extrapolated. Because of the chokepoints, each unit can only be attacked by one or two units. And because of this, the AI is pretty passive/defensive. So maybe for defense, the AI should have a very low attack depth setting and locate its troops where they can be attacked by very few units, and the rest might take care of itself. (You might think that the AI is sitting at the chokepoints only because I am. That's only partially true. When I opened chokepoints as traps, the AI did not always fall for it.)

In that scenario, the AI also did a good job of playing cat-n-mouse with a Chocobone versus my troops in the more open area at my southwest flank. I was maneuvering trying to get to where I could kill it and not be killed, and it was doing the same to my troops. Spooky. The AI understands this sort of fluid defense.

I was also impressed by the AI's behavior in TRoW: The Rise of Wesnoth (the last scenario). There, some of the AI controlled bad guys use grouping=offensive by night and grouping=defensive by day. I was impressed by the lines it (sometimes) formed. And although at first I chuckled when it formed a blob, with units not moving very purposely, I learned the hard way to respect the blob. The blob grew and grew and closed in on my mounted units, which ran but they could not fall back past my main front. The blob won.

[Atz]

Is the AI improved in 1.9.3 relative to 1.8.3? I searched the changelogs and found nothing substantial, but my experience is that the AI is better. I think it's better at retreating, better at healing wounded, better at flanking, and better in mutual support and moving to nondangerous hexes. True or false impression?

The old "default" AI was replaced with RCA AI. RCA AI was actually available in 1.8 - for instance, if you start a multiplayer game and select "Computer" in the player box, another box will appear beneath that which lets you pick the AI used - but "default" was, well, the default.

[alluton]

Yeah RCA ai is surely better but still it lacks use of some abilityes. Mby you someone could code that ai would think that in hexes next to healer would be village(then ai would be tricked to go there) and ai would use healing. Anyway using abilityes effective way is big part in ai development. Also using formations is big part. Anyway ai has improved alot.

[bobknows]

The point system sounds great, and it is perfect to use to make multiple ais because you only need one ai and then just change the points system.

I would also suggest that we lessen the points for being near multiple units as that may cause clumping.

Another issue I can see is the ai moving each unit individually, not as a whole.
If each unit moves to what is best for itself then when playing certain units, such as orcs you will see them immediately attack, then then retreat to stay alive which will completely change how they are played

I would suggest we use the points system in cells of 3-5 units and be able to swap units between cells, each one based for one purpose such as healing, wall, wall support, attack support (slow, poison, one healer) attack,

This would allow for units to die for the cells success.

[Great_Mage_Atari]

It would seem to me that no matter what the AI uses the homing signal theory. It captures all available villages in its direct vicinity first. After that it makes its advance to enemy troops. If another enemy somehow interferes with that line of attack (say like a fish going for food) the AI will then attack the nearest unit (if of course the AI's health is not too low and the enemy is not too strong). AI attack procedures are predictable, if not obvious.
As for the defensive strategies of the AI, there isn't a ton. Unless the AI is specifically programmed and is set to defending one hex or a group of hexes, defense is not the word of the day. AIs are usually set to attack units, not to defend them.

[Temuchin Khan]

The discussion in the following thread is relevant to this topic:

http://forums.wesnoth.org/viewtopic.php?f=15&t=35062

Pay attention in particular to my experiment with how the AI recruits on a 100 x 100 map with all the factions. It's nothing like what it does on standard 40 x 40 maps!

[Jabie]

I'd strongly recommend that factor in the difficulty level when considering the AI.

BfW is two games: a strategy game and an RPG. You should therefore assume that, on the easiest level of any campaign, the player is more interested in the narrative than the challenge. Being unable to progress past a specific scenario is incredibly frustrating. It's ultimately a failure for the developer as it is for the player, as the player will not be able to experience a pretty cool scenario two or three scenarios down the chain and everyone has wasted their time. This isn't to say that the lowest levels can't be a challenge, just be very wary of making the opposition too good. On the lowest levels it's often better for the AI to make the occasional mistake than to play a perfect game.

Also, bear in mind also that many scenarios require the player to attack within a (frankly artificial) time limit. This is a pressure that the AI is seldom faced with, and it can sometimes act as a balance. On many occasions, it would be far easier for a player to fight a war of attrition in a defensible location, soak up enemy attacks and then rush in with overwhelming forces. A tight turn limit can force a player to be more aggressive than would be strategically sound.

A second advantage that the AI has over the player is that it is often vital for the player to level up their King unit. This means that occasionally the player must risk his king unit, a shortcoming that the AI never has to face. On the highest levels targetting a "king" unit when you've got a chance to kill them is fair game. On lower levels it can smack of being a little game-y if there are several legitimate targets to go for and the AI ignores them all to go for the throat. Sure it certainly can make sense to do that from a strategic perspective, but it may not make sense to do it from a narrative one. This is especially crucial in a travel from A to B across hostile terrain with limited troops scenario.

As for AI mistakes, the main one I've seen is for the enemy king to leave his throne unguarded. It might be that the King nips out to kill a weak skirmisher or toddles a village to heal some light damage from a scout unit. Very often, however, it will do so without considering the possibility that the player can sneak a unit onto the throne. If the usurper can hold out, the enemy king won't be able to recruit and the player can move in for the kill. The best solution would be for the AI to divert a nearby unit to guard the throne, but another solution may be for some castles to be "Fortresses" which not allow recruitment but also provide a minor health boost, thus incentivising the AI to stay put when it's only taken a few flesh wounds.