On Evaluating of Units' Relative Mobility
Moderator: Forum Moderators

 Posts: 71
 Joined: August 4th, 2019, 5:27 pm
On Evaluating of Units' Relative Mobility
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.
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.

 Posts: 71
 Joined: August 4th, 2019, 5:27 pm
Average Hex Speed per Turn
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.
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.

 Posts: 71
 Joined: August 4th, 2019, 5:27 pm
Isar's Cross Example
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 landbased 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...)
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 landbased 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...)

 Posts: 129
 Joined: March 16th, 2008, 6:39 am
Re: On Evaluating of Units' Relative Mobility
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 / hextype. 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 movecost valuation?
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 / hextype. 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 movecost valuation?
 patience_reloaded
 Posts: 44
 Joined: August 15th, 2019, 2:38 pm
 Location: UTC+1
Re: On Evaluating of Units' Relative Mobility
Computer_Player, your ideas sound pretty good, however... I see some difficulties in evaluating it. There would be a need for clearcut 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 7moves ghost ranked faster than the 9moves 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?
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 7moves ghost ranked faster than the 9moves 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?
Re: On Evaluating of Units' Relative Mobility
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...)

Any typos are the fault of my laptop keyboard!
Lonely Era (Ice Age) maintainer: https://forums.wesnoth.org/viewtopic.php?f=19&t=42630
Merry Christmas Campaign maintainer: https://forums.wesnoth.org/viewtopic.ph ... 97#p662897
Any typos are the fault of my laptop keyboard!
Lonely Era (Ice Age) maintainer: https://forums.wesnoth.org/viewtopic.php?f=19&t=42630
Merry Christmas Campaign maintainer: https://forums.wesnoth.org/viewtopic.ph ... 97#p662897
 patience_reloaded
 Posts: 44
 Joined: August 15th, 2019, 2:38 pm
 Location: UTC+1
Re: On Evaluating of Units' Relative Mobility
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.
Re: On Evaluating of Units' Relative Mobility
I meant that the choice of map skewed the results. The formula is fine.

Any typos are the fault of my laptop keyboard!
Lonely Era (Ice Age) maintainer: https://forums.wesnoth.org/viewtopic.php?f=19&t=42630
Merry Christmas Campaign maintainer: https://forums.wesnoth.org/viewtopic.ph ... 97#p662897
Any typos are the fault of my laptop keyboard!
Lonely Era (Ice Age) maintainer: https://forums.wesnoth.org/viewtopic.php?f=19&t=42630
Merry Christmas Campaign maintainer: https://forums.wesnoth.org/viewtopic.ph ... 97#p662897

 Posts: 129
 Joined: March 16th, 2008, 6:39 am
Re: On Evaluating of Units' Relative Mobility
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 movecost 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.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 clearcut 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).
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 movecost 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?
Re: On Evaluating of Units' Relative Mobility
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. Mapbymap, tiles also grow in importance the closer they are to a village. Not all tiles are created equal.