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 terms of robocode, a rolling average is use to keep average of more recent data instead of all data collected. This is useful in most Statistical Targeting systems to hit enemies that change their movement frequently. So, in order to match general description above, robocode's rolling average only consider the last set of points to be averaged.

Rolling Averages is recommended over the straight averages because it can adapt to adaptive enemy. In practice, the most commonly used type of rolling average, is an Exponential moving average.

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 feed the function the current averaged value (value), the value to be averaged (newEntry), the weighting on the old value (n) and the weighting on the new value (weighting). The function will return an exponential rolling average. Note, having both n and weighting is redundant, and many implementations simplify them to a single value expressing the bias towards newer data.

SpareParts Version

by Kawigi

Here is the implementation of a Simple rolling average 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);
	}
}

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 );
}

This is another implementation of a exponential rolling average. This implementation is arguably more clear than the Paul Evans version above, but is essentially equivalent. The difference is that in the Paul Evans version the deltaTime is fixed at 1, and the decayRate value was split redundantly into n and weighting. In this version, you can also calculate the decay rate to obtain a specific half life of data (this means, how many ticks you want before the weighting of a piece of data becomes 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, it 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 gain the best performance because the bin smoothing make sure that you don't rolling on zero on every bin that don't hit that time.