Difference between revisions of "GuessFactor Targeting Tutorial"

From Robowiki
Jump to navigation Jump to search
(ripped the tutorial from the old wiki)
 
(re-formatting page)
Line 1: Line 1:
The Guess Factor Targeting Tutorial by Kawigi
+
''The Guess Factor Targeting Tutorial by [[Kawigi]]''
  
GuessFactorTargeting is a simple idea and is also one of the most effective and practical targeting algorithms used in Robocode. This tutorial will go over how to make a simple GuessFactorTargeting gun, based loosely on code from FloodMini, who sports one of the most effective versions of the algorithm to date.
+
[[GuessFactorTargeting]] is a simple idea and is also one of the most effective and practical targeting algorithms used in Robocode. This tutorial will go over how to make a simple [[GuessFactorTargeting]] gun, based loosely on code from [[FloodMini]], who sports one of the most effective versions of the algorithm to date.
  
This tutorial is meant for people who already have an understanding of the Robocode API and know how to use non-blocking (setXXX) calls effectively.
+
'''This tutorial is meant for people who already have an understanding of the Robocode API and know how to use non-blocking (setXXX) calls effectively.'''
  
How it works
+
==How it works==
  
Many people already know what GuessFactorTargeting is all about, and they can probably skip this part. It was thought up by Paul Evans and first implemented in his fine robot, SandboxLump. He explains the algorithm [here]. However, some features of the original implementation were overly complex and possibly even less effective for one-on-one in today's competitive environment.
+
Many people already know what [[GuessFactorTargeting]] is all about, and they can probably skip this part. It was thought up by Paul Evans and first implemented in his fine robot, [[SandboxLump]]. He explains the algorithm [here]. However, some features of the original implementation were overly complex and possibly even less effective for one-on-one in today's competitive environment.
  
The philosophy and assumption we make for GuessFactorTargeting is that our enemy is moving randomly in some way or another (in PatternMatching, we wouldn't be assuming that). The direction we need to shoot is the sum of several random decisions made by our enemy. One nice thing about sums of random values is that they tend to show statistical trends. The trick to GuessFactorTargeting is to find out which direction we should shoot each time we fire, and in the future, we fire in the direction that was correct the most often.
+
The philosophy and assumption we make for [[GuessFactorTargeting]] is that our enemy is moving randomly in some way or another (in [[PatternMatching]], we wouldn't be assuming that). The direction we need to shoot is the sum of several random decisions made by our enemy. One nice thing about sums of random values is that they tend to show statistical trends. The trick to [[GuessFactorTargeting]] is to find out which direction we should shoot each time we fire, and in the future, we fire in the direction that was correct the most often.
  
Guess Factor Targeting Terminology
+
==Guess Factor Targeting Terminology==
  
GuessFactor - a direction that may be fired in. Usually people talk about GuessFactors normalized over the maximum escape angle, where shooting directly where we see our target is GF 0.0, shooting as far ahead of our target as they could possibly get by the time our bullet would reach them is GF 1.0, and firing just as far behind them is GF -1.0. Note that to find this, we need to know what the maximum angle is as well as whether they are moving around us to the right (clockwise) or to the left (counter-clockwise).
+
; [[GuessFactor]]:
 +
: A direction that may be fired in. Usually people talk about [[GuessFactors]] normalized over the [[Maximum Escape Angle|maximum escape angle]], where shooting directly where we see our target is [[GuessFactors|GF]] 0.0, shooting as far ahead of our target as they could possibly get by the time our bullet would reach them is [[GuessFactors|GF]] 1.0, and firing just as far behind them is [[GuessFactors|GF]] -1.0. Note that to find this, we need to know what the maximum angle is as well as whether they are moving around us to the right (clockwise) or to the left (counter-clockwise).
  
MovementProfile - The combination of directions we could fire and the frequency that each direction is correct is what people refer to as the bot's "profile". Using tools like FloodGrapher, RoboGrapher and SmogPainter, you can actually view the profile of a give bot from saved data of other robots.
+
; [[MovementProfile]]:
 +
: The combination of directions we could fire and the frequency that each direction is correct is what people refer to as the bot's "profile". Using tools like [[FloodGrapher]], [[RoboGrapher]] and [[SmogPainter]], you can actually view the profile of a give bot from saved data of other robots.
  
RollingAverages - Also called moving averages and some other things. Basically a way of favoring newer data over older data. A guess-factor gun can be awful against a robot that changes its movement unless it uses rolling averages, however, for simplicity, I probably won't implement them in this tutorial.
+
[[RollingAverages]]:
 +
: Also called moving averages and some other things. Basically a way of favoring newer data over older data. A guess-factor gun can be awful against a robot that changes its movement unless it uses rolling averages, however, for simplicity, I probably won't implement them in this tutorial.
  
Segmentation - Sometimes we can get more relevant data by splitting it up on some parameters, rather than just looking at the general profile.
+
[[Segmentation]]:
 +
: Sometimes we can get more relevant data by splitting it up on some parameters, rather than just looking at the general profile.
  
VirtualBullets - An object that tracks where a bullet would be if it were fired along a certain trajectory and finds out if it would hit at that trajectory or not. These were used in all of the earliest guess factor guns to analyze the bot's MovementProfile.
+
[[VirtualBullets]]:
 +
: An object that tracks where a bullet would be if it were fired along a certain trajectory and finds out if it would hit at that trajectory or not. These were used in all of the earliest guess factor guns to analyze the bot's [[MovementProfile]].
  
Waves - Most current robots that use GuessFactorTargeting use Waves to find the bearing that they should have shot at, as an alternative to using several VirtualBullets. These are a little more efficient in general, and can also be modified slightly to give the exact same results as VirtualBullets (tracking ALL angles that would have hit, rather than just the median). This tutorial will use a Wave implementation.
+
[[Wave]]
 +
: Most current robots that use [[GuessFactorTargeting]] use Waves to find the bearing that they should have shot at, as an alternative to using several [[VirtualBullets]]. These are a little more efficient in general, and can also be modified slightly to give the exact same results as [[VirtualBullets]] (tracking ALL angles that would have hit, rather than just the median). This tutorial will use a [[Wave]] implementation.
  
Getting started
+
==Getting started==
  
 
First of all, I'm going to assume you already have a robot with some kind of Movement and Radar where the radar scans your enemy at least most of the time. Check other parts of the wiki for more information on that before continuing if you don't understand it. Let's start by implementing the wave bullet, since finding out what direction we should have used at any time is at the core of this algorithm.
 
First of all, I'm going to assume you already have a robot with some kind of Movement and Radar where the radar scans your enemy at least most of the time. Check other parts of the wiki for more information on that before continuing if you don't understand it. Let's start by implementing the wave bullet, since finding out what direction we should have used at any time is at the core of this algorithm.
Line 34: Line 40:
 
     * the time we fired
 
     * the time we fired
 
     * what clock direction our opponent is moving in relative to us (1 for clockwise, -1 for counterclockwise)
 
     * what clock direction our opponent is moving in relative to us (1 for clockwise, -1 for counterclockwise)
     * where GuessFactor 0 is (i.e. - the direction to our target at firetime)
+
     * where [[GuessFactor]] 0 is (i.e. - the direction to our target at fire time)
 
     * the power (really the speed) of the bullet
 
     * the power (really the speed) of the bullet
 
     * where to return the "answer" to.  
 
     * where to return the "answer" to.  
  
 +
<pre>
 
import java.awt.geom.*;
 
import java.awt.geom.*;
 
import robocode.util.Utils;
 
import robocode.util.Utils;
Line 58: Line 65:
 
returnSegment = segment;
 
returnSegment = segment;
 
}
 
}
 +
</pre>
  
 
Now let's add a few useful utility functions that will come in useful:
 
Now let's add a few useful utility functions that will come in useful:
 
+
<pre>
 
public double getBulletSpeed()
 
public double getBulletSpeed()
 
{
 
{
Line 70: Line 78:
 
return Math.asin(8/getBulletSpeed());
 
return Math.asin(8/getBulletSpeed());
 
}
 
}
 
+
</pre>
It may not be obvious why the max escape angle is asin(8/bulletspeed) regardless of distance or any other considerations, but that is the furthest angle our enemy can theoretically be relative to where they were when we fired. More discussion on why this is the case is elsewhere on the wiki. If you ever get more than that, it is usually due to the discrete tick-based physics of robocode (i.e. - you can't hit someone with a bullet at time 7.5, so it will hit them at 8 and they will have gone just a little bit further), and due to imperfect data (especially missed scans).
+
It may not be obvious why the max escape angle is <code>asin(8/bulletspeed)</code> regardless of distance or any other considerations, but that is the furthest angle our enemy can theoretically be relative to where they were when we fired. More discussion on why this is the case is elsewhere on the wiki. If you ever get more than that, it is usually due to the discrete tick-based physics of robocode (i.e. - you can't hit someone with a bullet at time 7.5, so it will hit them at 8 and they will have gone just a little bit further), and due to imperfect data (especially missed scans).
  
 
Now let's get into the most significant part of our code - this method will check if the wave has hit the enemy. If it hasn't, it will simply return false. If it has, it will figure out what GuessFactor the enemy is at, find the appropriate index into the returnSegment and increment it. Then it will return true if it hit. Return true signifies that the wave should no longer be tracked.
 
Now let's get into the most significant part of our code - this method will check if the wave has hit the enemy. If it hasn't, it will simply return false. If it has, it will figure out what GuessFactor the enemy is at, find the appropriate index into the returnSegment and increment it. Then it will return true if it hit. Return true signifies that the wave should no longer be tracked.
 
+
<pre>
 
public boolean checkHit(double enemyX, double enemyY, long currentTime)
 
public boolean checkHit(double enemyX, double enemyY, long currentTime)
 
{
 
{
Line 90: Line 98:
 
}
 
}
 
}
 
}
 
+
</pre>
 
...and that's the end of our WaveBullet? class. Now we need to use it in our robot. First we need to create some sort of structure to store them in. I think an ArrayList or Vector is most appropriate. To make PEZ happier, I'll declare it as a generic List and then initialize it as an ArrayList. Note that if you have multiple threads that may want to access the list, you'll want to use a Vector instead, because ArrayLists aren't thread-safe. So this goes somewhere in your global variable declarations:
 
...and that's the end of our WaveBullet? class. Now we need to use it in our robot. First we need to create some sort of structure to store them in. I think an ArrayList or Vector is most appropriate. To make PEZ happier, I'll declare it as a generic List and then initialize it as an ArrayList. Note that if you have multiple threads that may want to access the list, you'll want to use a Vector instead, because ArrayLists aren't thread-safe. So this goes somewhere in your global variable declarations:
 
+
<pre>
 
List waves = new ArrayList();
 
List waves = new ArrayList();
 
+
</pre>
 
Note that it's not static, because I don't want to update artifact waves in the next round if I can avoid it. And some other things we will need for this:
 
Note that it's not static, because I don't want to update artifact waves in the next round if I can avoid it. And some other things we will need for this:
 
+
<pre>
 
static int[] stats = new int[31]; //31 is the number of unique guessfactors we're using
 
static int[] stats = new int[31]; //31 is the number of unique guessfactors we're using
 
int direction = 1;
 
int direction = 1;
 
+
</pre>
 
Now the fun work goes into creating and updating these waves in our onScannedRobot method.
 
Now the fun work goes into creating and updating these waves in our onScannedRobot method.
 
+
<pre>
 
public void onScannedRobot(ScannedRobotEvent e)
 
public void onScannedRobot(ScannedRobotEvent e)
 
{
 
{
Line 132: Line 140:
 
int[] currentStats = stats; //This seems silly, but I'm using it to show something else later
 
int[] currentStats = stats; //This seems silly, but I'm using it to show something else later
 
WaveBullet newWave = new WaveBullet(getX(), getY(), absBearing, power, direction, getTime(), currentStats);
 
WaveBullet newWave = new WaveBullet(getX(), getY(), absBearing, power, direction, getTime(), currentStats);
 
+
</pre>
 
Now we've processed our waves and created a new one for the current scan. Now it would be useful to use our data to actually aim. Note that this is exceptionally fast and we can get away with doing it every scan without a major performance hit:
 
Now we've processed our waves and created a new one for the current scan. Now it would be useful to use our data to actually aim. Note that this is exceptionally fast and we can get away with doing it every scan without a major performance hit:
  
Line 144: Line 152:
 
double angleOffset = direction*guessfactor*newWave.maxEscapeAngle();
 
double angleOffset = direction*guessfactor*newWave.maxEscapeAngle();
 
setTurnGunRightRadians(robocode.util.Utils.normalRelativeAngle(absBearing-getGunHeadingRadians()+angleOffset));
 
setTurnGunRightRadians(robocode.util.Utils.normalRelativeAngle(absBearing-getGunHeadingRadians()+angleOffset));
 
+
</pre>
 
Now we want to fire. If the firing actually happens, we add the new wave bullet to our ArrayList.
 
Now we want to fire. If the firing actually happens, we add the new wave bullet to our ArrayList.
 
+
<pre>
 
if (setFireBullet() != null)
 
if (setFireBullet() != null)
 
waves.add(newWave);
 
waves.add(newWave);
 
}
 
}
 
+
</pre>
 
And that pretty much concludes the onScannedRobot method, as well as the code of a basic unsegmented guessfactor gun. Of course, this gun won't be overly effective against most opponents. In order to make it more effective, it is best to "segment" this data depending on the situation, rather than using just a single 1-dimensional array of ints. For instance, it's fairly normal to segment on either distance or projected bullet flight time (distance / bulletSpeed). If you want to segment on distance every 100 pixels, you could change your declaration for the stat buffer to this:
 
And that pretty much concludes the onScannedRobot method, as well as the code of a basic unsegmented guessfactor gun. Of course, this gun won't be overly effective against most opponents. In order to make it more effective, it is best to "segment" this data depending on the situation, rather than using just a single 1-dimensional array of ints. For instance, it's fairly normal to segment on either distance or projected bullet flight time (distance / bulletSpeed). If you want to segment on distance every 100 pixels, you could change your declaration for the stat buffer to this:
 
+
<pre>
 
int[][] stats = new int[13][31];
 
int[][] stats = new int[13][31];
 
+
</pre>
 
... then you need to change one line in your onScannedRobot method, where you declare the array currentStats:
 
... then you need to change one line in your onScannedRobot method, where you declare the array currentStats:
  

Revision as of 13:04, 3 January 2009

The Guess Factor Targeting Tutorial by Kawigi

GuessFactorTargeting is a simple idea and is also one of the most effective and practical targeting algorithms used in Robocode. This tutorial will go over how to make a simple GuessFactorTargeting gun, based loosely on code from FloodMini, who sports one of the most effective versions of the algorithm to date.

This tutorial is meant for people who already have an understanding of the Robocode API and know how to use non-blocking (setXXX) calls effectively.

How it works

Many people already know what GuessFactorTargeting is all about, and they can probably skip this part. It was thought up by Paul Evans and first implemented in his fine robot, SandboxLump. He explains the algorithm [here]. However, some features of the original implementation were overly complex and possibly even less effective for one-on-one in today's competitive environment.

The philosophy and assumption we make for GuessFactorTargeting is that our enemy is moving randomly in some way or another (in PatternMatching, we wouldn't be assuming that). The direction we need to shoot is the sum of several random decisions made by our enemy. One nice thing about sums of random values is that they tend to show statistical trends. The trick to GuessFactorTargeting is to find out which direction we should shoot each time we fire, and in the future, we fire in the direction that was correct the most often.

Guess Factor Targeting Terminology

GuessFactor
A direction that may be fired in. Usually people talk about GuessFactors normalized over the maximum escape angle, where shooting directly where we see our target is GF 0.0, shooting as far ahead of our target as they could possibly get by the time our bullet would reach them is GF 1.0, and firing just as far behind them is GF -1.0. Note that to find this, we need to know what the maximum angle is as well as whether they are moving around us to the right (clockwise) or to the left (counter-clockwise).
MovementProfile
The combination of directions we could fire and the frequency that each direction is correct is what people refer to as the bot's "profile". Using tools like FloodGrapher, RoboGrapher and SmogPainter, you can actually view the profile of a give bot from saved data of other robots.

RollingAverages:

Also called moving averages and some other things. Basically a way of favoring newer data over older data. A guess-factor gun can be awful against a robot that changes its movement unless it uses rolling averages, however, for simplicity, I probably won't implement them in this tutorial.

Segmentation:

Sometimes we can get more relevant data by splitting it up on some parameters, rather than just looking at the general profile.

VirtualBullets:

An object that tracks where a bullet would be if it were fired along a certain trajectory and finds out if it would hit at that trajectory or not. These were used in all of the earliest guess factor guns to analyze the bot's MovementProfile.

Wave

Most current robots that use GuessFactorTargeting use Waves to find the bearing that they should have shot at, as an alternative to using several VirtualBullets. These are a little more efficient in general, and can also be modified slightly to give the exact same results as VirtualBullets (tracking ALL angles that would have hit, rather than just the median). This tutorial will use a Wave implementation.

Getting started

First of all, I'm going to assume you already have a robot with some kind of Movement and Radar where the radar scans your enemy at least most of the time. Check other parts of the wiki for more information on that before continuing if you don't understand it. Let's start by implementing the wave bullet, since finding out what direction we should have used at any time is at the core of this algorithm.

The data we need to do our work is basically these:

   * the location we are firing from
   * the time we fired
   * what clock direction our opponent is moving in relative to us (1 for clockwise, -1 for counterclockwise)
   * where GuessFactor 0 is (i.e. - the direction to our target at fire time)
   * the power (really the speed) of the bullet
   * where to return the "answer" to. 
import java.awt.geom.*;
import robocode.util.Utils;

public class WaveBullet
{
	private double startx, starty, startBearing, power;
	private long fireTime;
	private int direction;
	private int[] returnSegment;
	
	public WaveBullet(double x, double y, double bearing, double power, int direction, long time, int[] segment)
	{
		startx = x;
		starty = y;
		startBearing = bearing;
		this.power = power;
		this.direction = direction;
		fireTime = time;
		returnSegment = segment;
	}

Now let's add a few useful utility functions that will come in useful:

	public double getBulletSpeed()
	{
		return 20-power*3;
	}
	
	public double maxEscapeAngle()
	{
		return Math.asin(8/getBulletSpeed());
	}

It may not be obvious why the max escape angle is asin(8/bulletspeed) regardless of distance or any other considerations, but that is the furthest angle our enemy can theoretically be relative to where they were when we fired. More discussion on why this is the case is elsewhere on the wiki. If you ever get more than that, it is usually due to the discrete tick-based physics of robocode (i.e. - you can't hit someone with a bullet at time 7.5, so it will hit them at 8 and they will have gone just a little bit further), and due to imperfect data (especially missed scans).

Now let's get into the most significant part of our code - this method will check if the wave has hit the enemy. If it hasn't, it will simply return false. If it has, it will figure out what GuessFactor the enemy is at, find the appropriate index into the returnSegment and increment it. Then it will return true if it hit. Return true signifies that the wave should no longer be tracked.

	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]++;
			return true;
		}
		return false;
	}
}

...and that's the end of our WaveBullet? class. Now we need to use it in our robot. First we need to create some sort of structure to store them in. I think an ArrayList or Vector is most appropriate. To make PEZ happier, I'll declare it as a generic List and then initialize it as an ArrayList. Note that if you have multiple threads that may want to access the list, you'll want to use a Vector instead, because ArrayLists aren't thread-safe. So this goes somewhere in your global variable declarations:

	List waves = new ArrayList();

Note that it's not static, because I don't want to update artifact waves in the next round if I can avoid it. And some other things we will need for this:

	static int[] stats = new int[31];	//31 is the number of unique guessfactors we're using
	int direction = 1;

Now the fun work goes into creating and updating these waves in our onScannedRobot method.

	public void onScannedRobot(ScannedRobotEvent e)
	{
		...
		(other onScannedRobot code)
		...
		double absBearing = getHeadingRadians() + e.getBearingRadians();
		//find our enemy's location:
		double ex = getX() + Math.sin(absBearing)*e.getDistance();
		double ey = getY() + Math.cos(absBearing)*e.getDistance();
		
		//let's process the waves now:
		for (int i=0; i<waves.size(); i++)
		{
			WaveBullet currentWave = (WaveBullet)waves.get(i);
			if (currentWave.checkHit(ex, ey, getTime())
			{
				waves.remove(currentWave);
				i--;
			}
		}
		
		double power = Math.min(3, Math.max(.1, /* some function */));
		//don't try to figure out the direction they're moving if they're not moving, just use the direction we had before
		if (e.getVelocity() != 0)
			if (Math.sin(e.getHeadingRadians()-absBearing)*e.getVelocity() < 0)
				direction = -1;
			else
				direction = 1;
		int[] currentStats = stats;	//This seems silly, but I'm using it to show something else later
		WaveBullet newWave = new WaveBullet(getX(), getY(), absBearing, power, direction, getTime(), currentStats);

Now we've processed our waves and created a new one for the current scan. Now it would be useful to use our data to actually aim. Note that this is exceptionally fast and we can get away with doing it every scan without a major performance hit:

int bestindex = 15; //initialize it to be in the middle, guessfactor 0. for (int i=0; i<31; i++) if (currentStats[bestindex] < currentStats[i]) bestindex = i;

//this should do the opposite of the math in the WaveBullet: guessfactor = (double)(bestindex-(stats.length-1)/2)/((stats.length-1)/2); double angleOffset = direction*guessfactor*newWave.maxEscapeAngle(); setTurnGunRightRadians(robocode.util.Utils.normalRelativeAngle(absBearing-getGunHeadingRadians()+angleOffset));

Now we want to fire. If the firing actually happens, we add the new wave bullet to our ArrayList.

		if (setFireBullet() != null)
			waves.add(newWave);
	}

And that pretty much concludes the onScannedRobot method, as well as the code of a basic unsegmented guessfactor gun. Of course, this gun won't be overly effective against most opponents. In order to make it more effective, it is best to "segment" this data depending on the situation, rather than using just a single 1-dimensional array of ints. For instance, it's fairly normal to segment on either distance or projected bullet flight time (distance / bulletSpeed). If you want to segment on distance every 100 pixels, you could change your declaration for the stat buffer to this:

	int[][] stats = new int[13][31];

... then you need to change one line in your onScannedRobot method, where you declare the array currentStats:

int[] currentStats = stats[(int)(e.getDistance()/100)];

Now stats from different distances will no longer be stored together. Experiment with different segmentation axes to see what works well. For a little discussion on effective segmentation schemes, look at the discussion on SegmentedData/Segments.