DeletedUser25583
Guest
Hello everyone!
This is one of my first posts to the forum. I hope you find it helpful/interesting!
Recently I decided to tackle the challenge of finding the optimal scavenging method. We can't consider of the objective of this problem to be simply to get the most resources. We must think of the objective as getting the most resources per unit time. In other words we want to maximize the rate at which we scavenge resources. One may think that this is achieved by putting all of your troops into the highest tier of scavenging this unlocked, but this is not the case. As shown below the resource rate can be increased by distributing troops between tiers.
So with that information, the problem is this:
Given a number of soldiers, how can we distribute them among the 4 tiers of scavenging to maximize the resource rate?
To start, we need an idea of how the number of resources and the scavenging time are determined when you enter your troops into the scavenging page. The resources are easy. Each tier returns a percentage of the total carrying capacity of the army you send.
Tier 1 (Lackadaisical Looters): 10% of total haul capacity
Tier 2 (Humble Haulers): 25% of total haul capacity
Tier 3 (Clever Collectors): 50% of total haul capacity
Tier 4 (Great Gatherers): 75% of total haul capacity
After experimenting for a short while, I discovered that the scavenging time is a linear function solely based on the number of resources that will be gathered. It does not take into account travel speed. Below are the graphs of scavenging time (y-axis) vs. total haul capacity (x-axis) for the first 3 tiers.
So because the number of scavenge-able resources (r) is a function of the carrying capacity of your troops, and the scavenging time (t) is a function of the number of scavenge-able resources, we should be able to get a function for the resource rate (r/t) given only the quantity of each troop type or the total haul capacity. Below are graphs of the functions of resource rate vs. haul capacity for the first 3 scavenging tiers.
Here we can see the concept of diminishing returns, which is the reason behind why it is better to split up your troops between tiers instead of putting them all into the highest one.
Attempt #1 at Solving This Problem
(This method didn't work, but I thought it was interesting. Feel free to skip.)
I first wanted to solve this problem with only spear fighters and then attempt to expand it to all units. By using quadratic regression, I was able to get a pretty accurate function for resource rate vs number of spear fighters for each tier. Then I constructed a non-linear mixed integer program to maximize the sum of the rates of each tier. I'm not going to put the details for all of this here, but I'll post it in a reply if anyone is interested. Unfortunately with my knowledge from my university, I was unable to solve the model with an LP solver (because it's not linear) or with a Lagrange multiplier (no closed form solution as far as I can tell).
In addition the functions for the resource rates vs the number of spear fighters were inaccurate for 2 reasons.
1. As the number of spear fighters increased, the function became more inaccurate for smaller numbers of spear fighters due to the nature of regression.
2. Time and resource values being rounded up or down within Tribal Wars itself.
Attempt #2 at Solving This Problem
Another way that I thought of to solve this problem is to allocate soldiers one-by-one to each tier by choosing the tier that will return the highest increase in the resource rate. There is a proof that this works because the rate functions are increasing and convex (f'>0, f''<0), but it is lengthy, and I can link a similar proof if anyone is interested. This method sounds sounds simple enough, but there are a few challenges:
Let's start with an example. For simplicity's sake, Let's say I only have the first 2 tiers unlocked. Let's also say I have 100 spear fighters in each tier 1 and tier 2. Increasing the number in each by 1 would produce the following results:
Therefore, I would allocate the spear fighter to tier 1, and I would keep on allocating to tier 1 until the increase diminishes to the level of the other tier. If we were to start from 0 troops with all tiers unlocked and kept kept allocating, we would observe that the increase in each tier's rate would all eventually be equal to one another. This is where we can find optimality.
Now, the problem has been transformed into finding the distribution of troops such that allocating one more soldier to any tier would result in approximately the same net increase in resource rate.
To solve this, I have made a table of the resource rates of each tier for each possible army capacity. We can assume that the troops that the player wants to use to scavenge are given, so we can use the total resource capacity of that army and distribute that capacity among each tier in that way. Then using an integer linear program, we can distribute the troops so that the haul capacity for each tier most closely matches the capacity that we allocated. By solving the problem this way, we not only find an optimal solution, we can also eliminate the problem of deciding who to allocate first, and we can enforce the 0 or >=10 troop requirement in the constraints of the linear program. Again I won't post many of the details unless someone asks for them, in which case I will reply to this topic answering whatever I can.
PLEASE NOTE! This method is only "optimal" if you are able to restart scavenging for each tier as they become available, which is not really possible for most players. If a player wants to start scavenging and then stop playing for 5 hours, the player should just stuff as many troops into the highest tier until it reaches a 5 hour duration and then move down a tier and repeat.
If you managed to read through all of this, thank you!
Tell me what you think!
This is one of my first posts to the forum. I hope you find it helpful/interesting!
Recently I decided to tackle the challenge of finding the optimal scavenging method. We can't consider of the objective of this problem to be simply to get the most resources. We must think of the objective as getting the most resources per unit time. In other words we want to maximize the rate at which we scavenge resources. One may think that this is achieved by putting all of your troops into the highest tier of scavenging this unlocked, but this is not the case. As shown below the resource rate can be increased by distributing troops between tiers.
Method 1: 100 Spears in Tier 2 | ||||
# of Spear Fighters | Resources Per Haul | Time Per Haul (s) | Rate (Resources Per Second) | |
Lackadaisical Looters | 0 | 0 | 0 | 0 |
Humble Haulers | 100 | 625 | 3011 | 0.207572 |
Sum: | 0.207572 | |||
Method 1: 50 Each | ||||
# of Spear Fighters | Resources Per Haul | Time Per Haul (s) | Rate (Resources Per Second) | |
Lackadaisical Looters | 50 | 125 | 1648 | 0.07585 |
Humble Haulers | 50 | 313 | 2184 | 0.143315 |
Sum: | 0.219165 |
So with that information, the problem is this:
Given a number of soldiers, how can we distribute them among the 4 tiers of scavenging to maximize the resource rate?
To start, we need an idea of how the number of resources and the scavenging time are determined when you enter your troops into the scavenging page. The resources are easy. Each tier returns a percentage of the total carrying capacity of the army you send.
Tier 1 (Lackadaisical Looters): 10% of total haul capacity
Tier 2 (Humble Haulers): 25% of total haul capacity
Tier 3 (Clever Collectors): 50% of total haul capacity
Tier 4 (Great Gatherers): 75% of total haul capacity
After experimenting for a short while, I discovered that the scavenging time is a linear function solely based on the number of resources that will be gathered. It does not take into account travel speed. Below are the graphs of scavenging time (y-axis) vs. total haul capacity (x-axis) for the first 3 tiers.
So because the number of scavenge-able resources (r) is a function of the carrying capacity of your troops, and the scavenging time (t) is a function of the number of scavenge-able resources, we should be able to get a function for the resource rate (r/t) given only the quantity of each troop type or the total haul capacity. Below are graphs of the functions of resource rate vs. haul capacity for the first 3 scavenging tiers.
Here we can see the concept of diminishing returns, which is the reason behind why it is better to split up your troops between tiers instead of putting them all into the highest one.
Attempt #1 at Solving This Problem
(This method didn't work, but I thought it was interesting. Feel free to skip.)
I first wanted to solve this problem with only spear fighters and then attempt to expand it to all units. By using quadratic regression, I was able to get a pretty accurate function for resource rate vs number of spear fighters for each tier. Then I constructed a non-linear mixed integer program to maximize the sum of the rates of each tier. I'm not going to put the details for all of this here, but I'll post it in a reply if anyone is interested. Unfortunately with my knowledge from my university, I was unable to solve the model with an LP solver (because it's not linear) or with a Lagrange multiplier (no closed form solution as far as I can tell).
In addition the functions for the resource rates vs the number of spear fighters were inaccurate for 2 reasons.
1. As the number of spear fighters increased, the function became more inaccurate for smaller numbers of spear fighters due to the nature of regression.
2. Time and resource values being rounded up or down within Tribal Wars itself.
Attempt #2 at Solving This Problem
Another way that I thought of to solve this problem is to allocate soldiers one-by-one to each tier by choosing the tier that will return the highest increase in the resource rate. There is a proof that this works because the rate functions are increasing and convex (f'>0, f''<0), but it is lengthy, and I can link a similar proof if anyone is interested. This method sounds sounds simple enough, but there are a few challenges:
- Since each unit type has a different carrying capacity, which ones should I allocate first?
- How do I allocate units when a tier has <10 units already allocated? I have no data for these numbers due to the in-game restriction of using no fewer than 10 soldiers to scavenge.
Let's start with an example. For simplicity's sake, Let's say I only have the first 2 tiers unlocked. Let's also say I have 100 spear fighters in each tier 1 and tier 2. Increasing the number in each by 1 would produce the following results:
# of Spear Fighters | Resources | Time (s) | Rate | ||
Lackadaisical Looters (Tier 1) | 100 | 250 | 2010 | 0.124378 | |
Humble Haulers (Tier 2) | 100 | 625 | 3011 | 0.207572 | |
# of Spear Fighters | Resources | Time | Rate | Increase from 100 | |
Lackadaisical Looters (Tier 1) | 101 | 253 | 2017 | 0.125434 | 0.001056 |
Humble Haulers (Tier 2) | 101 | 631 | 3027 | 0.208457 | 0.000885 |
Now, the problem has been transformed into finding the distribution of troops such that allocating one more soldier to any tier would result in approximately the same net increase in resource rate.
To solve this, I have made a table of the resource rates of each tier for each possible army capacity. We can assume that the troops that the player wants to use to scavenge are given, so we can use the total resource capacity of that army and distribute that capacity among each tier in that way. Then using an integer linear program, we can distribute the troops so that the haul capacity for each tier most closely matches the capacity that we allocated. By solving the problem this way, we not only find an optimal solution, we can also eliminate the problem of deciding who to allocate first, and we can enforce the 0 or >=10 troop requirement in the constraints of the linear program. Again I won't post many of the details unless someone asks for them, in which case I will reply to this topic answering whatever I can.
PLEASE NOTE! This method is only "optimal" if you are able to restart scavenging for each tier as they become available, which is not really possible for most players. If a player wants to start scavenging and then stop playing for 5 hours, the player should just stuff as many troops into the highest tier until it reaches a 5 hour duration and then move down a tier and repeat.
If you managed to read through all of this, thank you!
Tell me what you think!
Last edited by a moderator: