Difference between revisions of "Rolling Averages"
(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 | + | 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. |
− | + | [[Image:Exponential moving average weights N=15.png|thumb|right|Exponential moving average weighting]] | |
− | Rolling Averages | + | 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 | + | 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]] | ||
− | < | + | <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); | ||
} | } | ||
− | </ | + | </syntaxhighlight> |
− | You | + | 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 | + | 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. |
− | < | + | <syntaxhighlight> |
public class Averager { | public class Averager { | ||
private int totalentries; | private int totalentries; | ||
Line 53: | Line 55: | ||
} | } | ||
} | } | ||
− | </ | + | </syntaxhighlight> |
== Sample Implementations == | == Sample Implementations == | ||
Line 60: | Line 62: | ||
=== Time Weighted Rolling Average === | === Time Weighted Rolling Average === | ||
: by Robert Skinner | : by Robert Skinner | ||
− | < | + | <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 ); | ||
} | } | ||
− | </ | + | </syntaxhighlight> |
− | + | 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 == | ||
− | + | 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 [[User:Paul Evans|Paul]]'s code above. Call this function every time a wave hits. | |
− | < | + | <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; | ||
} | } | ||
− | </ | + | </syntaxhighlight> |
− | Don't forget to change each <code>int[] stat</code> into <code>double[] stat</code>. This code rolling | + | 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
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 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.
Contents
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.