RollingAverage

Rolling average means you only regard a certain depth of your recent history when calculating an average. The term entered the Robocode world with Paul Evans who also published a function that can be used for calclulation rolling averages:

static double rollingAvg(double value, double newEntry, double n, double weighting ) {
    return (value * n + newEntry * weighting)/(n + weighting);
} 

You feed the function with the current average (value), the most recent reading (newEntry), the depth of the recent history (n), and a weight, or importance, of this reading (weighting). The function will return the average altered by the new reading in a way that simulates keeping a list of all readings with n depth and returning the average of the values in this list. It's like magic.

All my bots use this function. Often like this:

averageBearing = rollingAvg(averageBearing, bearing, Math.min(readings, HISTORY_DEPTH), bulletPower);

Meaning that as long as I don't have enough readings I want a "straight" average from the readings I have and I get the result weighted by the bulletPower related to the current reading. -- PEZ

Are there any math people out there that can comment on this routine that I invented from scratch. For example:

• is it a good way of maintaining a recent average without storing data?
• is it called by another name in the math world?
• outside of the robocode community is it used by anyone else?

-- Paul Evans

I'm very far from a math person. But I am an empiric person if there ever were one. I have extensively tested this function side by side with some classes of mine which store data and thus always provides the "correct" answer. The function is very accurate from what I can see. Every time I stumble across a piece of my code where I use those classes I always remove those uses in favour of your function. Another usage of this function is to keep a "success rate". I do this often. It's done by initializing the success rate to 50 and then call this function with 100 for every success and 0 for every failure. This is how my Orcas and Makos and GB and other bots rate their VirtualGuns. -- PEZ

SpareParts does a different thing that accomplishes a similar goal. He has an actual Averager class that really does take the average of either all samples or the last n samples fed into it. I think it could be optimized very easily to find these averages more quickly, too. But I suspect it doesn't come back with answers overly different. It just completely forgets relics of the past, and weights all the recent samples exactly the same. -- Kawigi

I think this is commonly called a "moving average" or a "weighted moving average". Another possibility is to weight values by their age:

static double timeWeightedAverage( double newValue, double oldValue, 
				double deltaTime, double decayRate ) {
    double w = Math.exp( -decayRate*deltaTime );
    return( w*oldValue + (1-w)*newValue );
}

The contribution of the old values continues to shrink as a function of their age. The nice thing about this function is that for a value v(i) obtained at time T(i), its contribution to a weighted average value at time T(i+N) is the same no matter how many intermediate values have been computed between T(i) and T(i+N).

It might be easier to tune the decayRate if it's specified as a half-life, i.e the time required for an old value's contribution to shrink to half. The desired decayRate could be computed once like this:

static double computeDecayRate( double halfLife ) {
    return( -Math.log( 0.5 ) / halfLife );
}

I'm too much of a newbie to Robocode to comment on how effective this technique is compared Paul's rolling average. -- Robert Skinner

I recently had cause to look at Exponential Averaging - used primarily for technical analysis of share prices. It is essentially the same as my rolling average but Alpha factor is approximatly the inverse of the 'n' value of rolling average (actually 1/(n+1) ). If you don't want to store lots of intermediate values you have a choice - either keep a running average of all the values or use a rolling avarage/exponential avarage.

For those that just want an avarage of all the values so far...

if (count == 0) {
  count = 1;
  average = newValue;
} else {
  average = (average*count + newValue)/(count+1);
  count = count+1;
}

-- Paul Evans

Wouldn't it just be faster to write the above code like so?

average = (average*count + newValue)/(++count);

-- Vuen

If your just looking for a straight rolling average this method can be used

     static double rollingAverage(double average,double newValue) {
          return (average + newValue) / 2;
     }

I will give the same average as using Paul's method with a weighting of the current depth without the need to store a depth. The only problem is it doesn't give the flexibilty of wieghting -- Gorded

---

Is there much of a performance increase to be had by initialising the value to a value other than 0?? above pez mentions initialising to 50, then adding either 0 or 100 is this a dramatic improvement on simply adding 1 on success and 0 on failure?? -- Brainfade

That usage of the function is not about performance. It's just a way to simulate success rate (or hit rate if you like). Using 0 and 1 is just as good. Only you'll have to multiply by 100 if you want a percentage figure. If you know the approximate success rate before hand you can initialize the rolling average with that instead of 0 or 50 or whatever. -- PEZ

What may improve performance is to seed the stat buffer with typical values at the start - ask yourself what a typical bot will show as far as a curve at various segments. Most will show a more positive graph close up, a thinner middle-oriented graph far away. Most will show a positive spike when accelerating and a negative when decelerating or approaching a wall. If you could 'seed' the stat buffer with a slight bias in this direction, you might do better in early rounds against the majority of opponents. -- Kawigi

That should be pretty easy. Just keep a general stat buffer updated with the accumulated data of all bots you meet. Then use this buffer to seed the specific buffer of any bot you have never met before. -- PEZ

That's a good idea. But it would be better to just use the general buffer for working out where to fire, rather than actually seeding the specific buffer, otherwise it will reduce the acruacy of the specific one. -- Tango

Wouldn't that lead to difficult decisions about when to start using the specific stats? A bit of the point with using rolling averages is that more old readings will get decreasing weighting compared to more recent data. So the specific buffer would pretty soon be decontaminated. Depending on the depth of the roll of course. -- PEZ

Right. A higher rolling-coefficient in earlier rounds would make sense. The general stat buffer would probably be a sum-all sort of solution, just take the FloodMini-style accumulation of everyone faced and store it somewhere, converting it to averages when you initialize a rolling stat buffer that you actually use. The other option is to just create such a buffer against a range of bots and observe the results, then hard-code the basic gist into your bot somewhere. -- Kawigi

I think the file might grow a bit too large if you just accumulated it FloodMini-style. Hardcoding the data into the buffers sounds like a bad idea. It's both smaller, cleaner and much more flexible to just read the data from a file. Though 85 - the oldest data will have been multiplied by the factor the most times and it's influence will automatically shrink as I get new info. Is there anything you might want to control the selection of bots represented in this file. That's easy. -- PEZ

The only thing wrong with loading the file is that people delete data files. -- Kawigi

In order to favor the new data over the old, whenever I add new data to a segment, I multiply everything else in that segment (have just slapped together a guess factor gun, so I am not sure I understand all of this correctly) by some factor smaller than 1 - say .wrong with this approach? --MightyMoose

i don't think i understand you correctly. is what you have somthing like: velocityAverage=.6*velocityAverage+e.getVelocity()*.4? --]]amdrew]]

At the moment I am doing my average by avg=(avg+entry*WEIGHT)/(1+WEIGHT); and have WEIGHT = .05, which I usually tweak based on the application. It saves me from having to keep track of the number of previous entries. I use this with a WEIGHT around 1 for predictive bullet velocities when I do cool movement. -- Jokester

In my RRGC entry I use RollingAverage on enemyspeed. It is (avg * 49 + entry)/ 50, but the starting average is set on 4.0. Also I do not take into account the first ticks when the enemy does not move. -- GrubbmGait

You feed the function with the current average (''value''), the most recent reading (''newEntry''), the depth of the recent history (''n'').

I want to calrify this somewhat

• current average - do you mean by the average of all the bins?
• recent reading - do you mean the guessfactor you were going to add the new value to?
• recent history - meaning say 20, e.g. for the last 20 waves.

I don't know what most these actually mean and thats all thats keeping me from using it. Like where is the rollingAverage used, before you place the average into the bins or when your going to take it out, and how does it corrulate to the bestBin or bestIndex? -- Chase-san

The current average is the avarage of all insert entries up to a depth of n for one bin. You have a rollingAvg for every gf-bin, when a wave passes your enemy you call the avarage funktion for each of them. If the bin would have hit the enemy the newEntry is 1 if it missed it is 0. The code could look like this:

int nbins=21;
double[] bin_avarage = new double[nbins];

static double rollingAvg(double value, double newEntry, double n, double weighting ) {
    return (value * n + newEntry * weighting)/(n + weighting);
} 

void Hit(Wave wave)
{
    for(int bin=0; bin<nbins; bin++)
    {
        if(wave.binHit(bin))
            bin_avarage[bin]=rollingAvg(bin_avarage[bin], 1, 20, 1);
        else
            bin_avarage[bin]=rollingAvg(bin_avarage[bin], 0, 20, 1);
    }
}

Wave is a class storing the shot informations, it contains a function binHit(int bin) which determines if a bin would have hit the enemy. You have to do some research about the depth of your avarages and the weighting (If you want to use it).

This is my understanding of rollingAvg, i hope its right :) --Krabb

It's almost right. You need to keep track of how many readings you actually have and put in Math.min(readings, 20) instead of just 20 for the recent depth. If you don't then your first 20 readings will be weighted incorrectly. --wcsv

Ahh I got it, that helps alot, my bots aim improved to what I expected it should be. =) -- Chase-san

If you want to see the real effects of RollingAverage in your gun, try testing it with different depths against CassiusClay from the TC2K6... -- Voidious

Anyway to make this into a [Exponential Rolling Average]? --Chase-san

Yes. =D -- Voidious

I read Paul's comment above, but I didn't know what he ment about the Alpha, as well, they must of changed the formula's on wikipedia. --Chase-san