Rolling Averages

In statistics, a rolling average, also called a moving average and sometimes a running average, is used to analyze a set of data points by creating a series of averages of different subsets of the full data set. So a moving average is not a single number, but it is a set of numbers, each of which is the average of the corresponding subset of a larger set of data points. A simple example is if you had a data set with 100 data points, the first value of the moving average might be the arithmetic mean (one simple type of average) of data points 1 through 25. The next value would be this simple average of data points 2 through 26, and so forth, until the final value, which would be the same simple average of data points 76 through 100.

In term of robocode, a rolling average is use to keep average of most recent data instead of all data collected. This is useful in most Statistical Targeting to hit any enemies that change their movement frequently. So, in order to match general description above, robocode's rolling average only take the last set of points to averaged.

Rolling Averages is recommended over straight averages because it can adopt better.

Rolling Averages were brought to the robocode community by Paul Evans. The first averaging code published by Paul are still used among top bots in the rumble.

Robocode's Rolling Averages

Ordinary Code

by Paul Evans

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

You fed the function with current averaged value (value), the value to be averaged (newEntry), the reading depth of history you need (n) and weighting to new value (weighting). The function will return the average altered by the new value in a way that simulates keeping a list of all readings with n depth and returning the average of the values in this list. The old value that exceed then limited will be removed from averaged value like a magic!

SpareParts Version

by Kawigi

Here is the same implementation as above that used by Kawigi in his SpareParts. It is easier to understand but slower.

public class Averager {
	private int totalentries;
	private double[] recent;
	
	public Averager(int size) {
		recent = new double[size];
		totalentries = 0;
	}
	
	public void addEntry(double entry) {
		recent[totalentries%recent.length] = entry;
		totalentries++;
	}
	
	public double recentAverage() {
		if (totalentries == 0)
			return 0;
		double total = 0;
		for (int i=0; i<Math.min(totalentries, recent.length); i++)
			total += recent[i];
		return total/Math.min(totalentries, recent.length);
	}
	
	public int totalEntries() {
		return totalentries;
	}
	
	public int recordedEntries() {
		return Math.min(totalentries, recent.length);
	}
}

I think his code is clear enough, I have no more to say.

Sample Implementations

Rolling Averages can change in various of ways, here are some implementation of rolling average.

Time Weighted Rolling Average

by Robert Skinner

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

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

With this implementation, the value will automatically weight upon their creating time. You just define half life of your data. (this mean, how many ticks you want before the value weight decrease by 50%)

(More to be added...)

Code Example

In almost all Statistical Targeting use rolling averaged. Here are some improvement to GuessFactor Targeting Tutorial to make it use rolling average.

First of all, I'll use Paul's code above. Now, call this function each time wave hit.

	static int readings = 0;
	// In WaveBullet class, replace old checkHit with this one.
	public boolean checkHit(double enemyX, double enemyY, long currentTime)
	{
		//if the distance from the wave origin to our enemy has passed the distance the bullet would have traveled...
		if (Point2D.distance(startX, startY, enemyX, enemyY) <= (currentTime-fireTime)*getBulletSpeed())
		{
			double desiredDirection = Math.atan2(enemyX-startx, enemyY-starty);
			double angleOffset = Utils.normalRelativeAngle(desiredDirection-startBearing);
			double guessFactor = Math.max(-1, Math.min(1, angleOffset/maxEscapeAngle()))*direction;
			int index = (int)Math.round((returnSegment.length-1)/2*(guessFactor+1));
			returnSegment[index] = rollingAvg(returnSegment[index], 1, Math.min(readings++, 200), 1);
			for (int i = 0; i < returnSegment.length; i++)
				if (i != index)
					returnSegment[index] = rollingAvg(returnSegment[index], 0, Math.min(readings++, 200), 1);
			return true;
		}
		return false;
	}

Don't forget to change each int[] stat into double[] stat! This code rolling by depth of 200 readings. However, this should be use in conjunction with Bin Smoothing in order to get best performance because the bin smoothing make sure that you don't rolling on zero on every bin that don't hit that time!