GuessFactor Targeting Tutorial
The Guess Factor Targeting Tutorial by Kawigi
GuessFactor Targeting 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 GuessFactor Targeting gun, based loosely on code from FloodMini, who sports one of the most effective versions of the algorithm to date.
This tutorial assume that you understand the basic of non-blocking call and can use them effectively
Contents
How it works
Many people already know what GuessFactor Targeting 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 GuessFactor Targeting is that our enemy is moving randomly in some way or another (in Pattern Matching, 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 GuessFactor Targeting 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.
GuessFactor Targeting Terminology
- 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).
- 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.
- 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, We probably won't implement them in this tutorial.
- Sometimes we can get more relevant data by splitting it up on some parameters, rather than just looking at the general profile.
- 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.
- Most current robots that use GuessFactor Targeting use Waves to find the bearing that they should have shot at, as an alternative to using several Virtual Bullets. These are a little more efficient in general, and can also be modified slightly to give the exact same results as Virtual Bullets (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.
WaveBullet Class
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;
}
} // end WaveBullet class...and that's the end of our WaveBullet class.
Waves
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<WaveBullet> waves = new ArrayList<WaveBullet>();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
// Note: this must be odd number so we can get
// GuessFactor 0 at middle.
int direction = 1;Now the fun work goes into creating and updating these waves in our onScannedRobot method.
@Override
public void onScannedRobot(ScannedRobotEvent e)
{
// ...
// (other onScannedRobot code, might be radar/movement)
// ...
// Enemy absolute bearing, you can use your one if you already declare it.
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
// 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.
Fire at will!
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:
double guessfactor = (double)(bestindex - (stats.length - 1) / 2)
/ ((stats.length - 1) / 2);
double angleOffset = direction * guessfactor * newWave.maxEscapeAngle();
double gunAdjust = Utils.normalRelativeAngle(
absBearing - getGunHeadingRadians() + angleOffset);
setTurnGunRightRadians(gunAdjust);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);
}In this code, the robot will always shoot if gunheat is 0, even if the gun still has to turn. It might be better to skip shooting until the gun doesn't have to turn anymore or by just a very small amount. The condition below prevents the robot from shooting if the gun has to adjust by more than half a robot, i.e. 9 pixels laterally.
if (getGunHeat() == 0 && gunAdjust < Math.atan2(9, e.getDistance()) && setFireBullet() != null) {And that pretty much concludes the onScannedRobot method, as well as the code of a basic unsegmented GuessFactor gun.
Segmentation
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]; // onScannedRobot can scan up to 1200px, so there are only 13.... then you need to change one line in your onScannedRobot method, where you declare the array currentStats:
int[] currentStats = stats[(int)(e.getDistance() / 100)]; // It doesn't look silly now!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.
