Difference between revisions of "Rolling Averages"

From Robowiki
Jump to navigation Jump to search
(Add {{Wikipedia}} template)
m (Fixed grammatical errors.)
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
{{Wikipedia|Moving average|Rolling average}}
 
{{Wikipedia|Moving average|Rolling average}}
In ''statistics'', a rolling average, also called a [[wikipedia:Moving average|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 ''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 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.
+
[[Image:Exponential moving average weights N=15.png|thumb|right|Exponential moving average weighting]]
  
Rolling Averages is recommended over straight averages because it can adopt for enemy  
+
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 considers the last set of points to be averaged.
 +
 
 +
Rolling Averages are recommended over straight averages because it can adapt to an adaptive enemy. In practice, the most commonly used form of rolling average, is an [[wikipedia:Moving average#Exponential moving average|Exponential moving average]].
 
   
 
   
Rolling Averages were brought to the robocode community by [[User:Paul Evans|Paul Evans]]. The first averaging code published by [[User:Paul Evans|Paul]] are still used among top bots in the rumble.
+
Rolling Averages were brought to the [[Robocode]] community by [[User:Paul Evans|Paul Evans]]. The first averaging code published by [[User:Paul Evans|Paul]] is still used among top bots in the rumble.
  
 
== Robocode's Rolling Averages ==
 
== Robocode's Rolling Averages ==
 
=== Ordinary Code ===
 
=== Ordinary Code ===
 
: by [[User:Paul Evans|Paul Evans]]
 
: by [[User:Paul Evans|Paul Evans]]
<pre>
+
<syntaxhighlight>
 
public static double rollingAvg(double value, double newEntry, double n, double weighting ) {
 
public static double rollingAvg(double value, double newEntry, double n, double weighting ) {
 
     return (value * n + newEntry * weighting)/(n + weighting);
 
     return (value * n + newEntry * weighting)/(n + weighting);
 
}  
 
}  
</pre>
+
</syntaxhighlight>
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 the''n'' limited will be removed from averaged value like a magic!
+
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 [[wikipedia:Moving average#Exponential moving average|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 ===
 
=== SpareParts Version ===
 
: by [[User:Kawigi|Kawigi]]
 
: by [[User:Kawigi|Kawigi]]
Here is the almost the same implementation as above that used by Kawigi in his [[SpareParts]]. It is easier to understand but slower.
+
Here is the implementation of a [[wikipedia:Moving average#Simple moving average|Simple rolling average]] that used by Kawigi in his [[SpareParts]]. It is easier to understand but slower.
<pre>
+
<syntaxhighlight>
 
public class Averager {
 
public class Averager {
 
private int totalentries;
 
private int totalentries;
Line 53: Line 55:
 
}
 
}
 
}
 
}
</pre>
+
</syntaxhighlight>
  
 
== Sample Implementations ==
 
== Sample Implementations ==
Line 60: Line 62:
 
=== Time Weighted Rolling Average ===
 
=== Time Weighted Rolling Average ===
 
: by Robert Skinner
 
: by Robert Skinner
<pre>
+
<syntaxhighlight>
 
public static double timeWeightedAverage( double newValue, double oldValue,  
 
public static double timeWeightedAverage( double newValue, double oldValue,  
 
double deltaTime, double decayRate ) {
 
double deltaTime, double decayRate ) {
Line 70: Line 72:
 
     return( -Math.log( 0.5 ) / halfLife );
 
     return( -Math.log( 0.5 ) / halfLife );
 
}
 
}
</pre>
+
</syntaxhighlight>
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%)
+
This is another implementation of a [[wikipedia:Moving average#Exponential moving average|exponential rolling average]]. This implementation is arguably more clear than the [[User:Paul Evans|Paul Evans]] version above, but is essentially equivalent. The difference is that in the [[User:Paul Evans|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...)
 
(More to be added...)
  
 
== Code Example ==
 
== Code Example ==
In almost all [[Statistical Targeting]] use rolling averaged. Here are some improvement to [[GuessFactor Targeting Tutorial]] to make it use rolling average.
+
Many [[Statistical Targeting]] algorithms use rolling averages. Here are some improvements to the [[GuessFactor Targeting Tutorial]] to make it use a rolling average.
  
First of all, it use [[Paul Evans|Paul]]'s code above. Now, call this function each time wave hit.
+
It uses [[User:Paul Evans|Paul]]'s code above. Call this function every time a wave hits.
<pre>
+
<syntaxhighlight>
 
static int readings = 0;
 
static int readings = 0;
 
// In WaveBullet class, replace old checkHit with this one.
 
// In WaveBullet class, replace old checkHit with this one.
Line 99: Line 101:
 
return false;
 
return false;
 
}
 
}
</pre>
+
</syntaxhighlight>
Don't forget to change each <code>int[] stat</code> into <code>double[] stat</code>. 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.
+
Don't forget to change each <code>int[] stat</code> into <code>double[] stat</code>. This code uses a rolling depth of 200 readings. This should be used in conjunction with [[Bin Smoothing]] in order to gain the best performance, because the bin smoothing makes sure that you don't roll on zero on every bin that doesn't hit that time.

Latest revision as of 02:10, 4 December 2012

Wikipedia
Wikipedia has an article about:

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.

Exponential moving average weighting

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 considers the last set of points to be averaged.

Rolling Averages are recommended over straight averages because it can adapt to an adaptive enemy. In practice, the most commonly used form 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 is 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

Many Statistical Targeting algorithms use rolling averages. Here are some improvements to the GuessFactor Targeting Tutorial to make it use a rolling average.

It uses Paul's code above. Call this function every time a wave hits.

	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 uses a rolling depth of 200 readings. This should be used in conjunction with Bin Smoothing in order to gain the best performance, because the bin smoothing makes sure that you don't roll on zero on every bin that doesn't hit that time.