On Evaluating of Units' Relative Mobility

Share and discuss strategies for playing the game, and get help and tips from other players.

Moderator: Forum Moderators

Post Reply
dwarftough
Posts: 529
Joined: August 4th, 2019, 5:27 pm
Contact:

On Evaluating of Units' Relative Mobility

Post by dwarftough »

Hello everyone!

Recently in the Wesnoth official discord me and several other people have been having a discussion about how to properly evaluate relative mobility of units. Many units have the same mp, but somehow we feel intuitively that the move cost pattern of one unit is better than the move cost pattern of another unit. But how do we evaluate which one is better?

It's clear, if you think a bit more, that a pure evaluation without knowing frequencies of different terrains is near useless. If a map favours one or another faction, the balance will be skewed. The maps full of forests will favour elves and others who can cross forests easily, caves will skew the balance in favour of dwarves, saurians and other cave dwellers, and maps from Inky's Quest campaign full of Deep Water will completely turn the things upside down. So it's clear: a model for evaluation must consider terrain distribution.

My proposed model of evaluating mobility is the following. It requires us to know the frequency of occurring for any terrain type X (impassable may be excluded as noone in standard Wesnoth can pass it). For any unit we calculate values (1/move cost on X) * (frequency of X) for any X and then find the sum of these values. If the unit can't walk on X, by definition we assume move cost on X = infinity, 1/infinity = 0. I propose to call the sum a move output of the unit.

So, unit's move output = sum of ((1/move cost on X)*(frequency of X)) for all terrain types X. The measure unit of the move output is hexes per movepoint

What's the intuition behind this formula? When we calculate (1/move cost X), these values can be interpreted as "how many hexes of this terrain type the unit can cross spending one move point". This value will be in range [0;1]. When we find the weighted sum with frequencies as weights, we get an average value of how many hexes the unit can cross spending one move point for the given distribution of terrain frequencies.

Overall, the move output shows how good the unit's move pattern is with respect to the given distribution of terrain frequencies.
Co-founder and current maintainer of IsarFoundation, Afterlife Rated and overall Wesnoth Autohost Project
Developer and maintainer of my fork of World Conquest, Invincibles Conquest II
dwarftough
Posts: 529
Joined: August 4th, 2019, 5:27 pm
Contact:

Average Hex Speed per Turn

Post by dwarftough »

We've learnt to evaluate units' move patterns but different units have different MP per turn, how do we evaluate that? Easily!

As we have a move output value measured in hexes per move point, for a given unit we can multiplayer it with unit's number of move points per turn. As a result we'll get a value measured in hexes per turn which shows how many hexes (on average) the unit can cross in one turn (with respect of the given distribution of terrain types of course). This value, an average hex speed per turn, can be used to compare different units with each other.
Co-founder and current maintainer of IsarFoundation, Afterlife Rated and overall Wesnoth Autohost Project
Developer and maintainer of my fork of World Conquest, Invincibles Conquest II
dwarftough
Posts: 529
Joined: August 4th, 2019, 5:27 pm
Contact:

Isar's Cross Example

Post by dwarftough »

To give an actual example, we need to calculate a terrain frequency distribution for some MP map. As I'm too lazy at the moment to research all those complexities of the Wesnoth terrain system and write a tool for automatic calculating of the frequencies, I picked a rather popular and easy for calculating by hand map, Isar's Cross. Of course, Isar's Cross' balance is different to the standard MP balance, but it's enough popular and easy to count. Results are the following:

Castle: 0.051
Flat: 0.290
Forest: 0.102
Fungus: 0.033
Hills: 0.112
Mountains: 0.028
Sand: 0.191
Sh. Water: 0.107
Swamp: 0.058
Village: 0.028

My calculation should reflect the general picture for Isar. Also I note that for complex terrains (like Ford = Flat + Sh. Water) I counted it both as Flat and Sh. Water.

Now, some calculations for units with this Isar distribution:

Bats
Bats unsurprisingly have one of the best movecost patterns, their move output is 0.9835 hexes per movepoint.
Average Hex Speed: for a 0 lvl bat (a quick one) is 7.868 (8.8515) hexes per turn.
For a 1&2 lvl bat is 8.8515 (9,835) hexes per turn.

Gryphon Rider and Gryphon Master
Gryphons have 0.978 hexes per movepoint.
A 1 lvl gryphon rider has 8 mp (a quick one is 9 mp) and the average hex speed is 7,824 (8,802) hexes per turn.
A 2 lvl gryphon master has 10 mp (a quick one 11 mp), so 9.78 (10,758) hexes per turn.

Ghosts
Ghost is 0.9465 hexes/movepoint, with 7 mps it's 6.6255 hexes/turn

Dwarves
Dwarves have probably the best move pattern among land-based units. I got the move output being equal 0.89 hexes/movepoint.
A 4 mp dwarf has 3.56 hexes per turn.
A 5 mp dwarf has 4.45 hexes per turn.

Elves (usual feet)
Elves have the same move pattern except for flying units (shyde and sylph) and an elvish ranger line. For the common elvish feet the move output is equal to 0.713 hexes/movepoint.

Here we get:
An elvish scout with 9 mp (quick with 10 mp) has 6.417 (7.13) hexes/turn.
An elvish fighter and shaman with 5 mp (quick with 6 mp) has 3.565 (4,278) hexes/turn.
An elvish archer with 6 (7) mp (excluding rangers) has 4,278 (4,991) hexes/turn.

Note that a 5 mp elvish fighter only a bit higher in mobility rank than a 4 mp dwarf. And a 5mp dwarf is a bit better than even a quick 6 mp elvish fighter.
(to be continued...)
Co-founder and current maintainer of IsarFoundation, Afterlife Rated and overall Wesnoth Autohost Project
Developer and maintainer of my fork of World Conquest, Invincibles Conquest II
Computer_Player
Multiplayer Moderator
Posts: 188
Joined: March 16th, 2008, 6:39 am

Re: On Evaluating of Units' Relative Mobility

Post by Computer_Player »

I like this idea. I was thinking wesnoth gameplay is mature enough that we can create some more complex "Guideline" observations, similar to the 9,5,3, 1 piece valuation in Chess. Ofcourse even in Chess that is more of a guideline (the real value of a unit changes depending on the board state), but I welcome such attempts.

For an application I am thinking this would be helpful in analyzing / building campaign scenarios which usually follow a certain place theme. This would help you in balancing the map and evoking the feeling that you want from the player, especially considering his recruit/recall list. Another is in AI, this being one of the factors in selecting what the AI might want to recruit given a certain map.

Some suggestions to help refine this:

Modeling using terrain frequency is I think too simplistic. Perhaps we can add a modifier by first getting the frequency that units are placed on that hex / hex-type. This would naturally place keep/castle hexes, village and near village terrain high,etc. while accounting for map specific strategies/ lines of movement and the fact that near edge hexes have very low significance in some maps compared to others.

However since we are conflating all terrain types together whether they are significant or not, thus this would still run into some problems, but this is after all a simplification. But I think doing this would help it be more reflective of the move value so to speak.

Perhaps though this is moving away from move-cost valuation?
User avatar
patience_reloaded
Posts: 62
Joined: August 15th, 2019, 2:38 pm
Location: UTC+1

Re: On Evaluating of Units' Relative Mobility

Post by patience_reloaded »

Computer_Player, your ideas sound pretty good, however... I see some difficulties in evaluating it. There would be a need for clear-cut factors on how important a specific tile on a specific map is, and those factors would have to be both accurate and easy to understand for the improved formula to work. This will likely take A LOT of effort to make, a lot more effort than dwarftough's formula (which is already much more effort than the simple formlua which sparked the whole discussion, and evaluating that simple formula already took long enough).

One thing that I find interesting though: Even the simple formula that didn't even take terrain frequencies into account got some things right, like that flying is a huge buff that can compensate for a certain lack of moves (that formula has the 7-moves ghost ranked faster than the 9-moves elvish scout, which is true even with terrain frequencies taken into account).
Therefore: Do we even need the perfect formula, or is it enough for some things to use a more simple formula that is easier to evaluate?
User avatar
Atreides
Posts: 1155
Joined: March 30th, 2019, 10:38 pm
Location: On the 2nd story of the centre village of Merwuerdigliebe turning the lights on and off

Re: On Evaluating of Units' Relative Mobility

Post by Atreides »

Quick observation. Isar has more mtn+hill than forest. Maybe that skewed dwarves up and elves down? Maybe try a randomly generated map? (perhaps can even find out what formulas it uses somewhere...)
User avatar
patience_reloaded
Posts: 62
Joined: August 15th, 2019, 2:38 pm
Location: UTC+1

Re: On Evaluating of Units' Relative Mobility

Post by patience_reloaded »

Atreides wrote: February 6th, 2021, 6:14 pm Quick observation. Isar has more mtn+hill than forest. Maybe that skewed dwarves up and elves down? Maybe try a randomly generated map? (perhaps can even find out what formulas it uses somewhere...)
dwarftough's formula is specific for a map, meaning that the values calculated may be different for every map. But for that specific map, they aren't skewed. It might seem skewed when looking at a different map, but for the specific map the values were calculated, they represent the truth, as close as the formula can get to it.

dwarftough took Isar as an example here because isar is one of the most popular maps. Also, isar is pretty well balanced, which random maps have a tendency to not be.

Also, the simple formula I mentioned earlier calculated the dwarves to be heavily more mobile than the elves, due to the much better mobility on difficult terrains, so this might be not even due to Isar itself. Also, dwarves don't loose any of their speed even in forests. They have crappy terrain defense there, but they are still faster than humans or orcs, so a chance at a better overall mobility than the elves sounds reasonable to me.
User avatar
Atreides
Posts: 1155
Joined: March 30th, 2019, 10:38 pm
Location: On the 2nd story of the centre village of Merwuerdigliebe turning the lights on and off

Re: On Evaluating of Units' Relative Mobility

Post by Atreides »

I meant that the choice of map skewed the results. The formula is fine.
Computer_Player
Multiplayer Moderator
Posts: 188
Joined: March 16th, 2008, 6:39 am

Re: On Evaluating of Units' Relative Mobility

Post by Computer_Player »

patience_reloaded wrote: February 6th, 2021, 8:26 am Computer_Player, your ideas sound pretty good, however... I see some difficulties in evaluating it. There would be a need for clear-cut factors on how important a specific tile on a specific map is, and those factors would have to be both accurate and easy to understand for the improved formula to work. This will likely take A LOT of effort to make, a lot more effort than dwarftough's formula (which is already much more effort than the simple formlua which sparked the whole discussion, and evaluating that simple formula already took long enough).
You don't need to analyze these factors, what you need is just a good enough data set taken from human players (which already exists in the replay database / ladder database). However, thinking about it, what I suggested was NOT move-cost value and is even more restricted (i.e. you will probably only have data from the most frequently played maps). I note now that it is an exploration of a related idea but might ultimately be off topic.

Speaking of which, I wonder if it yields some interesting outcomes in particular maps. I'm most interested perhaps in water maps and how getting mer/naga units impact the move-cost so to speak. Land units have impassable terrain in deep water than water units can navigate (same issue with chasms and flying), so how should this be taken into account?
User avatar
Mystery
Posts: 57
Joined: June 17th, 2009, 3:16 pm

Re: On Evaluating of Units' Relative Mobility

Post by Mystery »

One thing to keep in mind is location of the tiles. The center will naturally be the most important and most contested part of any map, while the edges (especially border tiles) are less important because your movement is already restricted by the boundary. Many maps are bordered by water tiles, for example, which is rarely abusable and mostly used as a buffer between the "playable" area of the map and the hard boundary. Map-by-map, tiles also grow in importance the closer they are to a village. Not all tiles are created equal.
dwarftough
Posts: 529
Joined: August 4th, 2019, 5:27 pm
Contact:

Re: On Evaluating of Units' Relative Mobility

Post by dwarftough »

Atreides wrote: February 6th, 2021, 6:14 pm Quick observation. Isar has more mtn+hill than forest. Maybe that skewed dwarves up and elves down? Maybe try a randomly generated map? (perhaps can even find out what formulas it uses somewhere...)
Random maps are artificial and not balanced, especially considering that there are different kinds of them with different dominant terrains. What would be better is to pick some duel map which is recognized as good and balanced. And Isar... I picked it just because I was too lazy to count hexes on a different bigger map and at the same time Isar is so popular so the distribution has some relation to the real life. I dunno about mnt+hill skew but Isar has a lot of sand so it should definitely skew the results towards drakes/saurians/maybe dunefolk.
patience_reloaded wrote: February 6th, 2021, 8:26 am Do we even need the perfect formula, or is it enough for some things to use a more simple formula that is easier to evaluate?
We're not going to seek for a perfect formula, at least outright. We want to look at some models, which are by the very definition are simplifications of reality. Patience had a model, the details of which I can't remember now but which was flawed because of considering any terrain equal which is obviously not true. My model is the attempt to consider terrain different importance's in a simple, yet mathematically sound way with distributions and mean values.
Computer_Player wrote: February 5th, 2021, 1:57 am Perhaps we can add a modifier by first getting the frequency that units are placed on that hex / hex-type. This would naturally place keep/castle hexes, village and near village terrain high,etc. while accounting for map specific strategies/ lines of movement and the fact that near edge hexes have very low significance in some maps compared to others
That's a fair point but the problem I see now in this proposal is that we need some additional measure of the hex importance, and it seems quite subjective and hard to evaluate. Like, we can assign some weights to hexes depending on their position on the map, proximity of villages, etc., but these weights would be arbitrary which isn't quite good, you know.
Mystery wrote: February 16th, 2021, 12:17 pm One thing to keep in mind is location of the tiles. The center will naturally be the most important and most contested part of any map, while the edges (especially border tiles) are less important because your movement is already restricted by the boundary. Many maps are bordered by water tiles, for example, which is rarely abusable and mostly used as a buffer between the "playable" area of the map and the hard boundary. Map-by-map, tiles also grow in importance the closer they are to a village. Not all tiles are created equal.
The idea of a different importance of edge and centre hexes is indeed interesting. Though I'm not sure how to evaluate this factor in a best way. About a water/impassible border: for the proposed model if a unit can't walk a terrain type, it just doesn't contribute to the values (move cost = infinity so 1/mc = 0).
Co-founder and current maintainer of IsarFoundation, Afterlife Rated and overall Wesnoth Autohost Project
Developer and maintainer of my fork of World Conquest, Invincibles Conquest II
dwarftough
Posts: 529
Joined: August 4th, 2019, 5:27 pm
Contact:

Re: On Evaluating of Units' Relative Mobility

Post by dwarftough »

Hm, it turns out I didn't write down here another idea of mine which I dropped almost a year ago in discord. In order not to forget it it's time to write things down 🙂

So, the next method is tied to the specific map, not even the distribution. It's a bit similar to movement considerations for chess pieces. So, the method is: we take our unit, place it on each hex of the given map (considering that no other units are on the map) and count how many hexes the unit can reach from any given hex. Then there are several options how to evaluate the results: calculate the average number, compare min/max, maybe analysing data for the specific regions of the map.

This method maybe is a bit less elegant mathematically than the previous one, but it has a surprising property, as it works with the map and its geometry directly, it can consider teleport to some extent (the previous model evaluated only the movetype and couldn't do anything about teleport). For that we need to assign villages to their "typical" owners (usually it's clear on mp maps which villages belong to which player in the equilibrium state). But ofc it always should be kept in mind that this method gives evaluation of a unit's mobility on the empty board while in reality the board is never empty (and villages might have different owners than they're supposed to)
Co-founder and current maintainer of IsarFoundation, Afterlife Rated and overall Wesnoth Autohost Project
Developer and maintainer of my fork of World Conquest, Invincibles Conquest II
white_haired_uncle
Posts: 1440
Joined: August 26th, 2018, 11:46 pm
Location: A country place, far outside the Wire

Re: On Evaluating of Units' Relative Mobility

Post by white_haired_uncle »

dwarftough wrote: December 26th, 2021, 3:32 am Hm, it turns out I didn't write down here another idea of mine which I dropped almost a year ago in discord. In order not to forget it it's time to write things down 🙂

So, the next method is tied to the specific map, not even the distribution. It's a bit similar to movement considerations for chess pieces. So, the method is: we take our unit, place it on each hex of the given map (considering that no other units are on the map) and count how many hexes the unit can reach from any given hex. Then there are several options how to evaluate the results: calculate the average number, compare min/max, maybe analysing data for the specific regions of the map.

This method maybe is a bit less elegant mathematically than the previous one, but it has a surprising property, as it works with the map and its geometry directly, it can consider teleport to some extent (the previous model evaluated only the movetype and couldn't do anything about teleport). For that we need to assign villages to their "typical" owners (usually it's clear on mp maps which villages belong to which player in the equilibrium state). But ofc it always should be kept in mind that this method gives evaluation of a unit's mobility on the empty board while in reality the board is never empty (and villages might have different owners than they're supposed to)
I like this method much better. It seems to me that the first method is ignoring MP and its relation to MC. For example, as I understand it, a unit with MP=3,4 or 5 and MC=3 will advance one tile/turn, while a unit with MP=6-8 will advance two tiles per turn (and I THINK MP=1 or 2 can't move). So the movement distribution should be more discrete as MC rises, while the first model makes it pretty much continuous. But then again, I may not understand what you're going for since MP is not considered at all in the first method.

I think a better, and much harder approach would be something like foreach tile, how many turns does it take to get to every other tile? This would take into account, for example, a quick horseman having to trot around a mountain range, or a flier being able to cross lava (but perhaps spending one or more turns doing so). Just have to be careful that units don't get penalized because they can access tiles others can't.

As for teleport, "simply" run the calculation with all possible permutations of village states, perhaps weighing toward the map initial state in some way.
dwarftough
Posts: 529
Joined: August 4th, 2019, 5:27 pm
Contact:

Re: On Evaluating of Units' Relative Mobility

Post by dwarftough »

I have made an addon dwarftough's Study if anyone wants to play around this stuff. Open a map, enable the mod, proceed to the game and you'll have two right-click menu button to calculate.
white_haired_uncle wrote: January 19th, 2022, 10:41 pm So the movement distribution should be more discrete as MC rises, while the first model makes it pretty much continuous. But then again, I may not understand what you're going for since MP is not considered at all in the first method.
MP is kinda considered in the first method but yes, it's continuous numbers, which is a great shortcoming of the model as, you're correctly noticed, in Wesnoth mobility is discrete and the number of turns to reach a hex changes abrupty. Also it can't consider big patches of, let say, flat.
white_haired_uncle wrote: January 19th, 2022, 10:41 pm I think a better, and much harder approach would be something like foreach tile, how many turns does it take to get to every other tile? This would take into account, for example, a quick horseman having to trot around a mountain range, or a flier being able to cross lava (but perhaps spending one or more turns doing so). Just have to be careful that units don't get penalized because they can access tiles others can't.
Oh, that's indeed very interesting, I might try to add it into my Study addon when I have spare time
Co-founder and current maintainer of IsarFoundation, Afterlife Rated and overall Wesnoth Autohost Project
Developer and maintainer of my fork of World Conquest, Invincibles Conquest II
Post Reply