Way back in June I won the Greed Tournament, a three week programming competition held by CodeCombat. In part 2 of this series I talked about the unit selection behaviour of my winning solution. This time, I will talk about gold prediction, which allows my solution to forecast the enemy’s future strength and decide whether an attack will succeed.
In part 2, when I talked about the attack behaviour, I mentioned that my code forecasts the enemy’s future strength so that we can know what to expect by the time our army gets to the enemy base. My measure of enemy strength is based on gold — the total gold that they have combined with the total gold value of the military units they currently have on the field.
In order to predict the enemy’s strength at some point in the future, we must be able to estimate how much more gold they are capable of collecting between now and that point. The more accurate this prediction is, the more confident we can be in our attacks.
To do this, I use linear regression. My solution samples the enemy’s cumulative gold (i.e. total gold collected) each turn, using the samples to compute a line of best fit. This is then used to predict how much gold they have at some future time.
Sampling and Prediction
Here is the main code:
Each turn, the enemy’s cumulative gold is computed and assigned to
We determine this by reading how much gold they currently have
and adding it together with the gold value of all the units
they have built over the game.
Every few turns this value is recorded in
enemyGoldHistory against the current time.
Once we have enough samples, the function
estimates how much gold the enemy will have at
seconds into the future
based on the history.
The lookahead time, 17 seconds, is about the amount of time
it takes for a military unit to walk from our base to the enemy base.
estimateHighLow doesn’t return a single value —
it actually returns three values: an upper bound, average, and lower bound estimate.
(The main code only actually uses the upper bound, though!)
Since the coins spawn randomly,
and we don’t know precisely how our opponent’s collection strategy works,
there will always be some uncertainty in any estimate we make.
The upper bound is a ceiling which we think the opponent will never cross
— given their history, we are certain they will not collect more than this much gold.
The lower bound is the opposite —
we are certain that the opponent will definitely collect at least this much gold.
We use the upper bound value to work out how
strong the enemy’s military could be.
To do this we simply subtract their current cumulative gold value
futureEnemyBonus, which tells us
how much more gold they will have collected by this time.
Then we add this to their current strength,
which is simply the gold cost of their living military units
combined with their reserve gold.
The Regression Model
The logic I’ve outlined so far
does all the grunt work of collecting data
and extracting some meaningful information
from the prediction,
but it all depends upon the prediction function,
to make accurate forecasts.
Here’s what it looks like
The first thing that happens is a bit of higher order function usage.
createRegressionFunc, which is a function
that accepts a bunch of points
and returns a new function,
representing the line of best fit.
This new function accepts an x-axis value (time)
and returns the corresponding y-axis value (gold) on the line
using the straight line equation
y = mx + c.
The values of
c are worked out
createRegressionFunc and “baked in” to the new function
before it is returned.
createRegressionFunc works these
c values out
using a simple linear regression formula.
I won’t attempt to cover this here —
there are plenty of maths websites that list the formula
and will do a much better job of explaining it than I can!
Now that we have a function for the line of best fit, we can use it to estimate values. Making a prediction is easy, as we can just plug in the time we want and get out a gold value. The upper and lower bounds are slightly more involved, however.
To determine upper and lower bounds I first calculate the standard deviation of the data. I then use this to draw a new line by offsetting the start and end points by a proportional amount. Hopefully this picture will explain what I mean:
So the calculate the upper bound,
I draw a line through
extrapolating into the future to find the required value.
The same happens for the lower bound, but with
As we move further into the future
the bounds widen,
as if to represent the increasing uncertainty
of the prediction.
The quality and quantity of the data also influences the bounds,
as more consistent data, or larger amounts of it,
will decrease the standard deviation.
I’m not particularly sure how sound this technique is, since I largely made it up via intuition, but it worked well enough for the competition, so it must be reasonably good!
Now you’ve seen how my Greed solution predicts my opponent’s gold income and uses this information to estimate their future military strength. I’ve explained how I used simple linear regression and sample variance to estimate an upper bound on my opponent’s performance, giving my solution confidence in its attacks. This, combined with my previous two blog posts, covers all the components of my Greed strategy.
I’ll be sure to keep my eye out for future CodeCombat competitions. I look forward to battling again with other intrepid wizards!