Optimal Scavenging (Warning: Math)

kennster007

New Member
Reaction score
8
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.

Method 1: 100 Spears in Tier 2
# of Spear FightersResources Per HaulTime 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 FightersResources Per HaulTime 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.

1576908639873.png

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.

1576908757941.png

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 FightersResourcesTime (s)Rate
Lackadaisical Looters (Tier 1)
100​
250​
2010​
0.124378​
Humble Haulers (Tier 2)
100​
625​
3011​
0.207572​
# of Spear FightersResourcesTimeRateIncrease from 100
Lackadaisical Looters (Tier 1)
101​
253​
2017​
0.125434​
0.001056
Humble Haulers (Tier 2)
101​
631​
3027​
0.208457​
0.000885
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!
 
Last edited:

kennster007

New Member
Reaction score
8
UPDATE! I was able to find the exact formulas for the time of each scavenging tier in the "Sources" tab after pressing f12 (or right click, inspect) on Google Chrome. By taking the derivative of the formula with respect to the haul capacity, I can make the second method of solving this problem much more precise and remove the need for tables. I was still unable to solve the problem using the first method, however.

t(x, p) = ((x^2 * 100 * p^2)^0.45+1800)*0.6830201284, x = haul capacity, p = fraction of the resource capacity of given scavenging tier (0.1, 0.25, 0.5, or 0.75)
or simplified:
t(x, p) = 5.425421728731242 * x^0.9 * p^0.9 + 1229.43623112

This makes the final rate function r(x, p) = p*x / (5.425421728731242 * x^0.9 * p^0.9 + 1229.43623112)

Note that the scavenging time is actually rounded to the nearest second. :)
 
Last edited:

Shinko to Kuma

Still Going Strong
Reaction score
748
UPDATE! I was able to find the exact formulas for the time of each scavenging tier in the "Sources" tab after pressing f12 (or right click, inspect) on Google Chrome. By taking the derivative of the formula with respect to the haul capacity, I can make the second method of solving this problem much more precise and remove the need for tables. I was still unable to solve the problem using the first method, however.

t(x, p) = ((x^2 * 100 * p^2)^0.45+1800)*0.6830201284, x = haul capacity, p = fraction of the resource capacity of given scavenging tier (0.1, 0.25, 0.5, or 0.75)
or simplified:
t(x, p) = 5.425421728731242 * x^0.9 * p^0.9 + 1229.43623112

This makes the final rate function r(x, p) = p*x / (5.425421728731242 * x^0.9 * p^0.9 + 1229.43623112)

Note that the scavenging time is actually rounded to the nearest second. :)
This actually fluctuates depending on the world.

The formula I use is

haul = time in seconds/ duration_factor - duration_initial_seconds) * (1 / (duration_exponent)) / 100) * (1 / 2);

the factor and exponent are different on each world
 

kennster007

New Member
Reaction score
8
This actually fluctuates depending on the world.

The formula I use is

haul = time in seconds/ duration_factor - duration_initial_seconds) * (1 / (duration_exponent)) / 100) * (1 / 2);

the factor and exponent are different on each world
Oh you're right. The formula that I found in the game's JS code was this:

Math.round((Math.pow(t*this.getLootPercent()*t*this.base.loot_factor,this.base.duration_exponent)+this.base.duration_initial_seconds)*this.base.duration_factor)

t is the total haul capacity of your army, this.getLootPercent() is just 100 * the loot factor, the duration_initial_seconds always 1800 (I think), and the loot_factor is the fraction of the total haul capactiy returned for each scavenging tier, so the resulting formula is:

Round(((t^2 * loot_factor^2 * 100)^duration_exponent + 1800) * duration_factor)

Do you know how I could determine those values based on the world settings?
 

Shinko to Kuma

Still Going Strong
Reaction score
748
Oh you're right. The formula that I found in the game's JS code was this:

Math.round((Math.pow(t*this.getLootPercent()*t*this.base.loot_factor,this.base.duration_exponent)+this.base.duration_initial_seconds)*this.base.duration_factor)

t is the total haul capacity of your army, this.getLootPercent() is just 100 * the loot factor, the duration_initial_seconds always 1800 (I think), and the loot_factor is the fraction of the total haul capactiy returned for each scavenging tier, so the resulting formula is:

Round(((t^2 * loot_factor^2 * 100)^duration_exponent + 1800) * duration_factor)

Do you know how I could determine those values based on the world settings?
they are in one of the config files of each world. I wrote an entire script using that formula months ago.

I believe you can get them with this from the scavenge screen:


var duration_factor = window.ScavengeScreen.village.options[1].base.duration_factor;
var duration_exponent = window.ScavengeScreen.village.options[1].base.duration_exponent;
var duration_initial_seconds = window.ScavengeScreen.village.options[1].base.duration_initial_seconds;


in the past it was a bit more of a pain to get them
 
Last edited:

Captured

Member
Reaction score
12
Just a question. @kennster007
Recently I decided to tackle the challenge of finding the optimal scavenging method.
Is it just me that read over the solution or isn't it mentioned?
I love your work and formulas :p

I can add something on this post. Maybe it is already said on the forum, but I am pretty new on .net so let's complain ;)

This is the amount of resources for each scavenging lvl, you already mentionned.
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
Then, how I am scavenging on my best.
If I want them home tommorow morning, i don't need to put 20 axe in it. Based on feeling, you need to add more.

Let's say at the last scavenge option (lvl 4 - 75%) i need 500 units. For the same loot on other scavenge lvls it wil be
3750 - 1500 - 750 ( - 500)

If you devide your troops into 26 pack amounts.
lvl 4 needs 2 packs
lvl 3 needs 3 packs
lvl 2 needs 6 packs
lvl 1 needs 15 packs
(Try it yourself: what is the best amount in each scavenge lvl if you have 2600 axe?)
2600/26 = 100
Lvl 1 = 1500
Lvl 2 = 600
Lvl 3 = 300
Lvl 2 = 200

If you are really into scavenging, your nuke can have at least this
6500 + X axe
X scouts
2600 + X lc
260 + X ma
X Ram
X cats

At lvl 4 you have
500 axe
200 lc
20 ma
10.000 each resource
14 hours 17 minutes 09 seconds

There you have it. My method of optimal scavenging.

Cheers,
M
 

kennster007

New Member
Reaction score
8
Yes my method would not be best for what you mentioned here:
If I want them home tommorow morning, i don't need to put 20 axe in it. Based on feeling, you need to add more.
I did mention this for your case though. Instead of 5 hours, you would use however long you needed until tomorrow morning.
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.
I believe that was is similar to what you suggested.
 

Shinko to Kuma

Still Going Strong
Reaction score
748
That's also the reason why I based my script to balance out the runtimes over all 4 categories. It's easiest if you launch everything at the same time every couple of hours for all villages. Mostbalanced time efficient and profit efficient way