Robowiki - User contributions [en]

Talk:Robocode/FAQ

2011-08-09T20:51:46Z

Ceasar: /* What exactly determines the size of the bullets? */ new section

'''What is the difference between frame and tick in robocode'''

Answer: A tick refers to one unit, which is also called a Turn in Robocode. During one turn, you may perform one action as a Robot, or multiple (independent) actions as an AdvancedRobot. A frame is a unit of drawing to the Robocode client interface. If you are processing turns slowly, you will get one frame per tick / turn. However, if you up the turns per second beyond your computer's ability to render the frames, you will miss some frames of animation. This won't affect the robots' behavior, unless you foolishly added code in your <nowiki>onPaint( Graphics2D )</nowiki> method that alters your bots behavior. In that case, your bot will behave differently depending on whether or not the Paint button has been enabled, and if the framerate can keep up with the turnrate. -- Martin

Thanks Martin. I put your suggestion into the FAQ. :-) --[[User:FlemmingLarsen|Fnl]] 21:28, 10 October 2008 (UTC)

== Uploading your bot ==

This page mentions you can upload your bot to www.robocoderepository.com, but I haven't been able to upload there in several days. An alternative would be very welcome. I've tried several free hosters, but they all seem unreliable (one of the problems is hotlinking). Do you guys have any suggestions? If someone was capable and willing to fix this problem, I think some kind of server with php upload, or wiki fix not to capitalize the package name would be awesome. :) --[[User:Positive|Positive]] 19:40, 6 November 2009 (UTC)

Well, wiki file upload supports jar files... but the Mediawiki page name rules require starting with uppercase so... the wiki file upload will work iff (if-and-only-if) your package starts with uppercase (which is against Java conventions) --[[User:Rednaxela|Rednaxela]] 21:19, 6 November 2009 (UTC)

Well, as far as I know Red, Skil, Void, I and probably some more use our own host. If you want a free, reliable host I'd suggest Google Sites (which, AFAIK, Zyx uses). --[[User:Nat|Nat]] [[User talk:Nat|Pavasant]] 05:44, 7 November 2009 (UTC)

: Thanks for the suggestion, it seems to work! Although I do think a more general solution would be better to accommodate new users. --[[User:Positive|Positive]] 10:45, 7 November 2009 (UTC)

:: We are all (hopelessly?) waiting for [[oldwiki:Roborumble.org|Roborumble.org]] I think. Though I have been developing a robot upload that use the wiki login for a while now (untested, and about 10% done) --[[User:Nat|Nat]] [[User talk:Nat|Pavasant]] 10:49, 7 November 2009 (UTC)

== Are bullets fired from the end of the barrel of the turret? ==

Or are they initialized at the center of the robot's position? [[User:Ceasar|Ceasar]] 20:45, 9 August 2011 (UTC)

They start at the center of the robot on the tick that you call setFire (or fire or setFireBullet). --[[User:Voidious|Voidious]] 20:48, 9 August 2011 (UTC)

== What exactly determines the size of the bullets? ==

I noticed they scale based on power. I'm wondering how exactly that is determined. [[User:Ceasar|Ceasar]] 20:51, 9 August 2011 (UTC)

Talk:Robocode/FAQ

2011-08-09T20:45:31Z

Ceasar: /* Are bullets fired from the end of the barrel of the turret? */

Talk:Robocode/FAQ

2011-08-09T20:45:14Z

Ceasar: /* Are bullets fired from the end of the barrel of the turret? */

Talk:Robocode/FAQ

2011-08-09T20:44:39Z

Ceasar: /* Are bullets fired from the end of the barrel of the turret? */ new section

Maximum Escape Angle

2011-04-01T17:20:18Z

Ceasar:

When firing, the Maximum Escape Angle (MEA) is the largest angle offset from zero (i.e., [[Head-On Targeting]]) that could possibly hit an enemy bot, given the [[Robocode/Game Physics|Game Physics]] of [[Robocode]].

== Calculation ==

Let's assume a triangle with sides <code>a</code>, <code>b</code> and <code>c</code> and angles (vertices) <code>A</code>, <code>B</code>, and <code>C</code>. <code>A</code> is the angle opposite to <code>a</code>, <code>B</code> is opposite to b, and <code>C</code> is opposite to <code>c</code>. The [http://en.wikipedia.org/wiki/Law_of_sines Law of sines] says that:

[[Image:LawOfSines.png|center]]

Now let's say that your bot is in the vertex <code>A</code> and the enemy bot is in the vertex <code>C</code>. We will fire a bullet with angle <code>A</code> to hit the bot in vertex <code>B</code>. We know the value of <code>b</code> (it is the distance <code>D</code> from your bot to the enemy).
We don't know <code>c</code>, but we know that it will be the distance traveled by the bullet. Also, we know that <code>a</code> will be the distance traveled by the enemy bot. If we put <code>a</code>, <code>b</code>, and <code>c</code> as a function of time, we have:
<pre>
b = D
c = Vb * t (Vb is the bullet speed)
a = Vr * t (Vr is the enemy bot velocity)
</pre>
Now, using the Law of sines:
<pre> a/sin(A) = c/sin(C)
-> Vr*t / sin(A) = Vb*t / sin(C)
-> sin(A) = Vr/Vb * sin(C)
-> A = asin(Vr/Vb * sin(C))
</pre>
We don't know the value of <code>C</code>, but we can take the worst scenario where
<code>C = PI/2</code> (<code>sin(C) = 1</code>) to get a Maximum Escape Angle of
<code>A = asin(Vr/Vb * 1) = asin (Vr/Vb)</code>.

With a maximum Robot velocity of 8.0, a theoretical Maximum Escape Angle would be <code>asin(8.0/Vb)</code>. Note that the actual maximum depends on the enemy's current heading, speed, and [[Wall Distance]].

== See Also ==

* [[Maximum Escape Angle/Precise]] - Some bots use a more sophisticated calculation for Maximum Escape Angle, using [[Precise Prediction]].

{{Targeting Navbox}}
[[Category:Robocode Theory]]
[[Category:Terminology]]

Chase Bullets

2011-04-01T17:19:21Z

Ceasar:

{{stub}}

Firing a low power (i.e., high speed) bullet immediately after firing a normal or high power bullet. Since many robots' movements respond to detecting enemy fire, the assumption is that they will be dodging the high power bullet and the low power bullet will have a higher chance of hitting.

== See also ==

* [[Marshmallow/Cowboy Guns]]
* [[CigaretBH]]

{{Targeting Navbox}}
[[Category:Targeting]]

Mean Targeting

2011-04-01T17:18:48Z

Ceasar:

A style of [[targeting]] that averages the data from a few recent scans to use as input to its prediction algorithm.

== Linear Mean ==

Given the enemy's current position and their position <code>t</code> ticks in the past, assume the enemy will continue to move with the same direction and average speed deduced from these scans. The pseudocode would look like this:
* Take a present scan position and an older scan position, <code>t</code> ticks in the past. Ignore actual heading and velocity.
* Find the angle from from the old scan to the new one. This is the mean heading.
* Find the distance between the two points and divide by <code>t</code>. This is the mean velocity.
* Use these values as input to a [[linear targeting]] algorithm.

== Circular Mean ==

Given a collection of <code>x</code> recent scans of the enemy, calculate his average velocity and turn rate and assume that he will continue to move with those values. The pseudocode would look like this:
* Iterate over the group of scans, summing the <code>x - 1</code> heading changes and <code>x</code> velocities.
* Divide the sum of heading changes by <code>x - 1</code> to find the mean heading change.
* Divide the sum of velocities by <code>x</code> to find the mean velocity.
* Use these values as input to a [[circular targeting]] algorithm.

{{Targeting Navbox}}
[[Category:Simple Targeting Strategies]]

Random Targeting

2011-04-01T17:18:30Z

Ceasar:

A method of [[targeting]] that simply chooses a random angle among the angles that could possibly hit the opponent. Some successful [[NanoBots]] use this firing method. Its implementation is very small and for unpredictable movements, it will give a consistent hit percentage.

== Example ==

<syntaxhighlight>
// Add import robocode.util.* for Utils
// This code goes in your onScannedRobot() event handler.

public void onScannedRobot(ScannedRobotEvent e) {
double randomGuessFactor = (Math.random() - .5) * 2;
double bulletPower = 3;
double maxEscapeAngle = Math.asin(8.0/(20 - (3 * bulletPower)));
double firingAngle = randomGuessFactor * maxEscapeAngle;
double absBearingToEnemy = e.getBearingRadians() + getHeadingRadians();

setTurnGunRightRadians(Utils.normalRelativeAngle(
absBearingToEnemy + firingAngle - getGunHeadingRadians()));
fire(bulletPower);
}
</syntaxhighlight>

== A simpler solution ==

A simpler method is to assume that the enemy is traveling in a circle around you (see [[Musashi Trick]]), which is often true among NanoBots and [[:Category:1-vs-1 Bots|1-vs-1 bots]]. If the enemy is traveling in a circle around you, the maximum distance it can cover before a bullet reaches it is <code>enemy velocity / bullet velocity</code> (in radians). For example, a power 3.0 bullet fired at an enemy going at full speed should be fired at a [[Bearing Offset|bearing offset]] between -8/11 and +8/11.

== Selecting firepower ==

The advantage of a random gun is that it should have a roughly equal hit rate on any type of movement. This makes ideal firepower selection pretty easy to pre-calculate. In the following equations x is the choice of firepower. It is assumed that damage output per tick is the quantity you're interested in maximizing, it may not be.

Bullet damage, assuming firepower > 1:
<pre>D=4*x+2*(x-1)</pre>

The smallest size of a robot, in radians:
<pre>S=36/distance</pre>

The total escape area, in radians:
<pre>A=2*asin(8/(20-3*x))</pre>

Probability of a hit, assuming uniform spread of bullets over A:
<pre>P=min(1,S/A)</pre>

The expected damage from a shot:
<pre>E=D*P</pre>

The heat created by a shot:
<pre>H=1+x/5</pre>

The firing frequency:
<pre>F=1/ceil(H/0.1)</pre>

Expected damage per tick of combat:
<pre>DPS=E*F</pre>

Back substitution to get the expected damage per tick in terms of distance and x and optimization of DPS are left as an exercise for the coder.

== See also ==

* [[Maximum Escape Angle]]

{{Targeting Navbox}}
[[Category:Simple Targeting Strategies]]

Circular Targeting

2011-04-01T17:18:11Z

Ceasar:

== Description ==

A method of [[targeting]] which assumes that the target will continue moving with the same turn rate and at the same speed.

== Example ==

This is the code used in [[WaveSurfing Challenge Bot/C|WaveSurfing Challenge Bot C]]:
<syntaxhighlight>
//Add import robocode.util.* for Utils and import java.awt.geom.* for Point2D
//This code goes in your onScannedRobot() event handler

double bulletPower = Math.min(3.0,getEnergy());
double myX = getX();
double myY = getY();
double absoluteBearing = getHeadingRadians() + e.getBearingRadians();
double enemyX = getX() + e.getDistance() * Math.sin(absoluteBearing);
double enemyY = getY() + e.getDistance() * Math.cos(absoluteBearing);
double enemyHeading = e.getHeadingRadians();
double enemyHeadingChange = enemyHeading - oldEnemyHeading;
double enemyVelocity = e.getVelocity();
oldEnemyHeading = enemyHeading;

double deltaTime = 0;
double battleFieldHeight = getBattleFieldHeight(),
battleFieldWidth = getBattleFieldWidth();
double predictedX = enemyX, predictedY = enemyY;
while((++deltaTime) * (20.0 - 3.0 * bulletPower) <
Point2D.Double.distance(myX, myY, predictedX, predictedY)){
predictedX += Math.sin(enemyHeading) * enemyVelocity;
predictedY += Math.cos(enemyHeading) * enemyVelocity;
enemyHeading += enemyHeadingChange;
if( predictedX < 18.0
|| predictedY < 18.0
|| predictedX > battleFieldWidth - 18.0
|| predictedY > battleFieldHeight - 18.0){

predictedX = Math.min(Math.max(18.0, predictedX),
battleFieldWidth - 18.0);
predictedY = Math.min(Math.max(18.0, predictedY),
battleFieldHeight - 18.0);
break;
}
}
double theta = Utils.normalAbsoluteAngle(Math.atan2(
predictedX - getX(), predictedY - getY()));

setTurnRadarRightRadians(Utils.normalRelativeAngle(
absoluteBearing - getRadarHeadingRadians()));
setTurnGunRightRadians(Utils.normalRelativeAngle(
theta - getGunHeadingRadians()));
fire(3);
</syntaxhighlight>

== See also ==

* [[Circular Targeting/Walkthrough]] - An in-depth example of creating a circular targeting algorithm in Robocode, authored by [[Dummy]].
* [[CodeSnippets/Nano Circular Linear Predictor | NanoBot sized circular targeting example code]]
* Alisdair Owen's [http://www-106.ibm.com/developerworks/library/j-circular/ circular targeting tutorial] with iteration.

{{Targeting Navbox}}
[[Category:Simple Targeting Strategies]]
[[Category:Code Snippets]]

Linear Targeting

2011-04-01T17:17:36Z

Ceasar:

A method of [[targeting]] which assumes that the target will continue in the same direction at the same speed.

== Example of Iterative Linear Targeting ==

This is the code used in [[WaveSurfing Challenge/Bot B|WaveSurfing Challenge Bot B]]. The algorithm assumes that bots will come to a stop when they reach a wall.

<syntaxhighlight>
// Add import robocode.util.* for Utils and import java.awt.geom.* for Point2D.
// This code goes in your onScannedRobot() event handler.

double bulletPower = Math.min(3.0,getEnergy());
double myX = getX();
double myY = getY();
double absoluteBearing = getHeadingRadians() + e.getBearingRadians();
double enemyX = getX() + e.getDistance() * Math.sin(absoluteBearing);
double enemyY = getY() + e.getDistance() * Math.cos(absoluteBearing);
double enemyHeading = e.getHeadingRadians();
double enemyVelocity = e.getVelocity();

double deltaTime = 0;
double battleFieldHeight = getBattleFieldHeight(),
battleFieldWidth = getBattleFieldWidth();
double predictedX = enemyX, predictedY = enemyY;
while((++deltaTime) * (20.0 - 3.0 * bulletPower) <
Point2D.Double.distance(myX, myY, predictedX, predictedY)){
predictedX += Math.sin(enemyHeading) * enemyVelocity;
predictedY += Math.cos(enemyHeading) * enemyVelocity;
if( predictedX < 18.0
|| predictedY < 18.0
|| predictedX > battleFieldWidth - 18.0
|| predictedY > battleFieldHeight - 18.0){
predictedX = Math.min(Math.max(18.0, predictedX),
battleFieldWidth - 18.0);
predictedY = Math.min(Math.max(18.0, predictedY),
battleFieldHeight - 18.0);
break;
}
}
double theta = Utils.normalAbsoluteAngle(Math.atan2(
predictedX - getX(), predictedY - getY()));

setTurnRadarRightRadians(
Utils.normalRelativeAngle(absoluteBearing - getRadarHeadingRadians()));
setTurnGunRightRadians(Utils.normalRelativeAngle(theta - getGunHeadingRadians()));
fire(bulletPower);
</syntaxhighlight>

== Example of Noniterative Linear Targeting ==

This code gives decent linear targeting with a very small code size. However, the aim is slightly imprecise and it ignores walls. The basic code is used in a lot of [[Nano Bots]]:

<syntaxhighlight>
double absoluteBearing = getHeadingRadians() + e.getBearingRadians();
setTurnGunRightRadians(Utils.normalRelativeAngle(absoluteBearing -
getGunHeadingRadians() + (e.getVelocity() * Math.sin(e.getHeadingRadians() -
absoluteBearing) / 13.0)));
setFire(3.0);
</syntaxhighlight>

=== How It Works ===

We first find the other robot's [[Lateral Velocity|lateral velocity]] (how fast the other robot is moving parallel to you) with <code>e.getVelocity() * Math.sin(e.getHeadingRadians() - absoluteBearing)</code>. To find an approximate angle offset, you assume they'll continue moving parallel to at their lateral velocity until your bullet reaches them, giving you a triangle like this:

<pre>
/|
/a|
bullet speed * bullet travel time / |
/ |
/____|

lateral velocity * bullet travel time
</pre>

So your angle offset is: <code>asin((lateral velocity * bullet travel time) / (bulletSpeed velocity * bulllet travel time)) = asin(lateral velocity / bullet speed)</code>. It turns out that <code>asin(lateral velocity / bullet speed)</code> is almost exactly the same as <code>(lateral velocity / bullet speed)</code>, so we get rid of the asin for some more code size. The above code uses 13.0 for bullet speed, but this actually results in aiming that works better for a slightly lower speed than 13.0 because of the distortion from removing asin. (The speed of a power 3.0 bullet is 11.0.)

Finally, we add the offset to the absolute bearing to get the firing angle, and subtract the gun heading to get the gun turn.

== Exact Non-iterative Solution ==

If the inexact method above is not close enough for you (eg. you need to hit <code>sample.Walls</code> on a 1000x1000 battle field, or you're trying to do some [[Bullet Shielding]]), you will need an exact solution. The maths involved turns out to be surprisingly non-trivial. Here is an example implementation:

<syntaxhighlight>
public void onScannedRobot(ScannedRobotEvent event) {
// ... Radar code ..

final double FIREPOWER = 2;
final double ROBOT_WIDTH = 16,ROBOT_HEIGHT = 16;
// Variables prefixed with e- refer to enemy, b- refer to bullet and r- refer to robot
final double eAbsBearing = getHeadingRadians() + event.getBearingRadians();
final double rX = getX(), rY = getY(),
bV = Rules.getBulletSpeed(FIREPOWER);
final double eX = rX + event.getDistance()*Math.sin(eAbsBearing),
eY = rY + event.getDistance()*Math.cos(eAbsBearing),
eV = event.getVelocity(),
eHd = event.getHeadingRadians();
// These constants make calculating the quadratic coefficients below easier
final double A = (eX - rX)/bV;
final double B = eV/bV*Math.sin(eHd);
final double C = (eY - rY)/bV;
final double D = eV/bV*Math.cos(eHd);
// Quadratic coefficients: a*(1/t)^2 + b*(1/t) + c = 0
final double a = A*A + C*C;
final double b = 2*(A*B + C*D);
final double c = (B*B + D*D - 1);
final double discrim = b*b - 4*a*c;
if (discrim >= 0) {
// Reciprocal of quadratic formula
final double t1 = 2*a/(-b - Math.sqrt(discrim));
final double t2 = 2*a/(-b + Math.sqrt(discrim));
final double t = Math.min(t1, t2) >= 0 ? Math.min(t1, t2) : Math.max(t1, t2);
// Assume enemy stops at walls
final double endX = limit(
eX + eV*t*Math.sin(eHd),
ROBOT_WIDTH/2, getBattleFieldWidth() - ROBOT_WIDTH/2);
final double endY = limit(
eY + eV*t*Math.cos(eHd),
ROBOT_HEIGHT/2, getBattleFieldHeight() - ROBOT_HEIGHT/2);
setTurnGunRightRadians(robocode.util.Utils.normalRelativeAngle(
Math.atan2(endX - rX, endY - rY)
- getGunHeadingRadians()));
setFire(FIREPOWER);
}
}

private double limit(double value, double min, double max) {
return Math.min(max, Math.max(min, value));
}
</syntaxhighlight>

=== Explanation ===

We start by equating the co-ordinates of the enemy and our bullet at time <code>t</code> in the future (variables prefixed with e- refer to enemy, b- refer to bullet and r- refer to robot):

<pre>
eX + eV*t*sin(eHeading) = rX + bV*t*sin(bHeading)
eY + eV*t*cos(eHeading) = rY + bV*t*cos(bHeading)
</pre>

Re-arrange to make <code>sin(bHeading)</code> and <code>cos(bHeading)</code> the subject:

<pre>
sin(bHeading) = (eX - rX)/(bV*t) + eV/bV*sin(eHeading)
cos(bHeading) = (eY - rY)/(bV*t) + eV/bV*cos(eHeading)
</pre>

Because everything on the right hand side except <code>t</code> is known, we lump them into some constants to make them easier to deal with:
<pre>
Let A = (eX - rX)/bV
B = eV/bV*sin(eHeading)
C = (eY - rY)/bV
D = eV/bV*cos(eHeading)

sin(bHeading) = A/t + B
cos(bHeading) = C/t + D
</pre>

Before we can find <code>bHeading</code>, we need to find <code>t</code>, the time when the bullet hits the enemy.

Eliminate <code>bHeading</code> by using the identity <code>sin(x)^2 + cos(x)^2 = 1</code>:

<pre>
sin(bHeading)^2 + cos(bHeading)^2 = (A/t + B)^2 + (C/t + D)^2
1 = A^2/t^2 + 2*A*B/t + B^2 + C^2/t^2 _ 2*C*D/t + D^2
0 = (A^2 + C^2)/t^2 + 2*(A*B + C*D)/t + B^2 + D^2 - 1

Separate out 1/t:
0 = (A^2 + C^2)*(1/t)^2 + 2*(A*B + C*D)*(1/t) + (B^2 + D^2 - 1)
</pre>

This gives us a quadratic equation. To make it easier, we will introduce some more constants to hold each coefficient:

<pre>
Let a = A^2 + C^2
b = 2*(A*B + C*D)
c = B^2 + D^2 - 1

0 = a*(1/t)^2 + b*(1/t) + c
</pre>

Now we simply use the quadratic formula to solve for <code>t</code>:

<pre>
1/t = (-b +/- sqrt(b^2 - 4*a*c)) / (2*a)
t = 2*a / (-b +/- sqrt(b^2 - 4*a*c))
</pre>

The remainder of the code checks that a solution exists (<code>discrim >= 0</code>) and chooses the smallest non-negative <code>t</code>. We can't simply invert the trigonometric functions because they periodically repeat, so we must instead predict the x- and y- co-ordinates of the enemy at the target time. This approach has the side-effect of allowing us to handle walls as well.

== See also ==

* [[/Buggy Implementations|Buggy implementations of linear targeting]] - There are much faster algorithms to do this, but they don't seem to be correct all the time. If anyone can correct them it would be much appreciated.
* [[/Archived_Talk_20071111|Archived discussions about linear targeting]] - Discussions culled from the LinearTargeting and LinearTargeting/Discussions pages of the old wiki.

{{Targeting Navbox}}
[[Category:Simple Targeting Strategies]]
[[Category:Tutorials]]
[[Category:Code Snippets]]

Head-On Targeting

2011-04-01T17:17:00Z

Ceasar:

{{Youtube|C9Wmo94TUpw}}
{{stub}}

The simple strategy of aiming where you last saw the enemy. Works surprisingly well against surprisingly many bots, especially in [[Melee]] battles.

== Example ==

In <code>onScannedRobot</code>, add:

<syntaxhighlight>
double absoluteBearing = getHeadingRadians() + e.getBearingRadians();
setTurnGunRightRadians(
robocode.util.Utils.normalRelativeAngle(absoluteBearing -
getGunHeadingRadians()));
</syntaxhighlight>

== See also ==

* [[Musashi Trick]]

{{Targeting Navbox}}
[[Category:Simple Targeting Strategies]]
[[Category:Code Snippets]]

Anti-Surfer Targeting

2011-04-01T17:16:34Z

Ceasar:

{{Stub}}

A style of [[targeting]] that focuses on hitting [[wave surfing]] (or other adaptive) movements. This is not a specific targeting algorithm; there are many different elements that can increase accuracy against wave surfers.

== History of the idea ==

When [[wave surfing]] was first becoming widespread, many believed that it wouldn't be long before a targeting system came along that could hit a wave surfer as easily as it could hit any other movement system that wasn't randomized; after all, wave surfing follows a specific algorithm to end up at the [[GuessFactor]] that it thinks is safest, so it should be possible to simply track the same information in a gun and shoot at the safest spots.

In practice, given all the variables involved in wave surfing movement algorithms, this is simply not the case: wave surfing movements are still the most effective form of [[1-vs-1]] movement against nearly every targeting system. (One notable exception is that [[anti-pattern matching]] can still be far more effective against [[pattern matching]] guns.) Every wave surfer uses different [[segments]], distancing, and [[wall smoothing]], and while there are some very common surfing algorithms, there is still much room for variation among them.

== Common elements in anti-surfer guns ==

While nobody has found a targeting method that hits a top wave surfer as well as it hits top [[random movement|random movements]], much progress has been made towards improving aim against wave surfers. Some elements of a gun that work well against wave surfing include:

* Rapid decay of data - Since a wave surfer changes its movement each time it is hit, data gathered gradually becomes less relevant to hitting the enemy as the match goes on.
* Lower weighting of non-firing waves - Many guns fire [[waves]] every tick in order to gather as much information as possible. Since a wave surfer detects enemy fire and bases its entire movement system around where it will be when the wave (or bullet) hits, the data gathered by non-firing waves is much less relevant than against other movements.
* [[Pattern matching]] - While it is not as good as specifically tailored anti-surfer guns, pattern matching has always done relatively well against wave surfers by its very nature: wave surfing inherently simulates a gun that uses [[waves]] and/or [[GuessFactors]], so a targeting system that does not use either cannot be dodged as well.

{{Targeting Navbox}}
[[Category:Advanced Targeting Strategies]]

Smart Factor Targeting

2011-04-01T17:16:13Z

Ceasar:

== Introduction ==

This is a technique that I am trying to implement in [[AgentSmith]]. As I have not finished implementing it I don't know how good or bad it will be. As you can guess from the name its a variation on [[GuessFactorTargeting]] but thats as much as I am willing to say! I need all the help I can get against the top bots without giving away some of my secrets!

Once I release the bot into the rumble I will probably release details of the technique! Check back here for updates on how good or bad my implementation is! (Probably going to be really bad!)

--[[Wolfman]]

== Update 01/03/2006: ==

Just getting back into writing [[AgentSmith]] again after a bit of an absense! I've changed my mind on how to do this technique about three times so after having written it three different ways I think I might (with luck) be starting to get somewhere that is at least reasonable, so long as I can sort out a problem with memory that I seem to be having. Does anyone have any ideas why my bot will be running of memory? Is there any way I can track it to see whats using what etc? (Im using Eclipse by the way but don't know much about it). I've tried removing as many calls to "new" as possible so I just allocate everything at the start of the battle and never do it again. Still it seems to be running out after about 60 rounds ....

Maybe you have some circular reference somewhere so that the garbage collector can't free stuff. I don't think it's a good idea to move those object creations to the start. Better new them as they are needed and let the garbage collecter reap. You probably have a huge structure that you keep adding stuff too. That's where you should start looking. -- [[PEZ]]
Oh well I guess I will just have to plod along and see how I can improve things! --[[Wolfman]]

== Original chat ==

I've moved all this old chat into here for the moment. --[[Wolfman]]

Great! I love it when people try to come up with unorthodox ideas :-) Keep us posted! -- [[Vic]]

I believe I came up with an interesting (I can't say anything better) idea for a gun. But I would need a ready to use (and preferably as fast as possible) implementation of Red-Black Tree, as in C++ STL set class. Is there any such thing in Java? --[[lRem]]

If you just need something like std::set (regardless of implementation), you can use a Java TreeSet or HashSet (which behave like std::set and std::hash_set respectively). If you use a TreeSet, the objects you put in there either need to implement the Comparable interface (or in Java 5, Comparable<Type> interface), or you can pass in a Comparator implementation. The first case is analogous to implementing std::less for the type, the second is like passing in a strict weak ordering to use instead of std::less. An Iterator created by a TreeSet will iterate in the natural order (or the ordering you give it) of the objects in the set. If this order doesn't matter, you can alternately use a HashSet (which means you don't need a comparator, but you probably need to override hashCode to do something useful, and maybe equals as well). Many built in objects already override hashCode() and implement Comparable if there is an appropriate comparison that can be made. Java also has a TreeMap and HashMap class (which are analogous to std::map and std::hash_map). -- [[Kawigi]] (P.S.- man, am I just a show off today with library knowledge!) (P.P.S.- TreeMap/HashMap are common ways to store enemy information in melee so they can be indexed by name)

Cool :) Now I only need a lot of motivation to implement it ;) --[[lRem]]

{{Targeting Navbox}}
[[Category:Targeting Discussions]]

Zoom Targeting

2011-04-01T17:15:36Z

Ceasar:

ZoomTargeting is a hybrid of StatisticalTargeting and a new form of PatternMatching and should combine the best of both worlds. It uses SegmentedData (currently 6 dimensions) and gets this data using a variant of [[Wave]]s.

Its StatisticalTargeting properties should make sure that
*it is very good at long term learning and continues to improve even in very long matches
*it can exploit weaknesses such as spikes in the enemies MovementProfile
*it can do a good educated guess when PatternMatching fails (when there's not enough data in the microsegment)

Its PatternMatching properties ensure that
*it adapts very fast to new enemies or situations.
*it can exploit weaknesses such as dodging and other types of repetitive movement
*it can get a reasonably high hitrate early on in a match if there is no stored data
*it can be more accurate than StatisticalTargeting (if there's enough data in the microsegment)

The new thing is that this targeting method basically zooms in (more PatternMatching) or out (more StatisticalTargeting) depending on the amount of data it has and the zoom level's segment size. Currently I use 8 zoom levels with increasing segment sizes. PatternMatching takes place in what I call the MicroSegments. In these tiny segments even only 1 previously reported angle is enough to deliver a firing angle with a high probability of hitting the enemy. StatisticalTargeting takes place when you zoom out, in the MacroSegments. The segments here are much larger and contain more data to do statistical calculations with. Learning speed increases when the zoom level increases.

The PatternMatching algorithm that I use differs greatly from traditional PatternMatchers. You might even argue if it is PatternMatching at all. I call it PatternMatching because it matches to a very specific situation. As a result it performs very well against bots that other PM guns perform well against :-). A situation is basically a very small segment with a lot of dimensions. Currently I use 6 dimensions, but if I can solve a memory issue I will use even more. I might even try a dimension that uses the movement history to make it a more official pattern matcher :-). In practise, this algorithm is a bit less accurate against truly predictable movers like SpinBot or PatternBot, but more effective against random movers. And since none of the top bots are truly predictable.........

There is a nice side-effect to using MicroSegments: I keep track of the number of Segments ('situations') that are used. This number increases more rapidly as the enemy has better movement. I am guessing this Segment count (say after 1000 rounds) could be a nice alternative Movement Index.

-- [[Vic Stewart]]

How far are you in developing this awesome gun?

*The next step is to implement the Statistical calculations of the macrosegments.
*decide whether to fire a [[Wave]] every scan or along with a bullet.
*better memory management

Yeah, yeah, yeah..... You talk the talk, but does it walk the walk?

*So far the results are very encouraging. I was unsure if the new PatternMatching algo would work, but it does! For instance, it beats all but one of the samplebots in a 10 round match, without stored data, whilst being stationary. (only TrackFire is a problem but that's due to a known bug)
*I tested against one of the challengers in the PatternMatcherChallenge and with just the new PatternMatching algo I got its index down from 32% to 25%. I wonder what will happen when I add the StatisticalTargeting part....

Sounds great, can I help in anyway?

* Yes you can :-) I have two issues:

== Memory issue ==

Currently I am reserving memoryspace for every zoom level whether it is used or not. I use a simple (6 dimensional) array for that. The drawback of this is that memory is reserved for segments that I never use and memory soon spins out of control. Now I want to implement a dynamic array (Vector or ArrayList or something). The question is, which type of dynamic array would be most suitable for this situation? Most importantly I require the lowest possible memory footprint.

-- [[Vic]]

Both an ArrayList and a Vector would work here. The constructor for each allow you to specify the size of the Arraylist to be built. They will also grow as more items are added to them. The "growing" part can be expensive in terms of CPU cycles so you will most likely need to play with them to see how it works out with skipped turns. Of the two, I would imagine that the ArrayList would be more appropriate than the Vector. I am also unsure if this will buy you anything in terms of memory footprint as I think in the end both classes use an Array with wrapper methods to implement their functionality. -- [[Sparafucil3|jim]]

LOL, I already implemented this gun about three months ago for Statistician -- it's sitting on my hard drive right now. This gun was the main feature of Statistician (and his namesake) and it will be one of Tax's main guns. You can probably find me talking about it here and there on the wiki. Although, it will be better implemented in Tax due to the ability to segment stats more intelligently with his neural network. Oh, to answer your question, I used a HashMap that stores strings of movement. For instance, if I tokenize a bot's velocity into the letters a-p, where a is -8 and p is +8, then I might have a string that looks like this: "aaaacegiiii". I stick that in the HashMap, along with a two-dimensional array of all my segments, and I just update the array as I need to. This makes sure that you only use memory for the patterns that you have seen, and it is a very fast pattern-matcher. -- [[nano]]

Interestingly, this approach also allows an infinite amount of "zooming". Of course, there are memory limits, but I ran my algorithm at a maximum of 200 frames of movement, and it ran fast with no memory problems. Thank God for a fast and efficient HashMap implementation. -- [[nano]]

Ok, thanx. What would I use for index if I'd want to implement an ArrayList? Say, for instance, in my original multidimensional Array I want to access Angle[0][1][1][0][1][1]. I need to do some sort of mapping from the 6 original indices to a single one. A possibility might be to convert these indices to a single integer, in this case ranging from 0 to 63 (6 bits). But can I insert the Angle at position 54 [ArrayList: add(54, Angle)] without my ArrayList or Vector immediately reserving memory space for the preceding 0 to 53? I think not, but I'm not sure. Does anyone know for sure?

That probably means the HashMap is the better solution. I can put my single Index 54 in it along with my Angle value [HashMap: put(Indexobject, Angleobject). However, a HashMap stores both key and value objects. Suppose my original value to store is an int. I now need to construct a wrapper object for it, an Int. Also I need to construct an Int object for my key. Assuming an Int takes equal memoryspace (it is just an int with wrapper methods, right?) then I must conclude that using a HashMap requires double the amount of memory PER ENTRY. So, if I have less than 32 entries I should use the HashMap, else I should stick to my original Array. This is getting complicated... Although I think that in practise I almost never will get more then 32 MicroSegments per Segment. I'll try the HashMap and report back if it works...

-- [[Vic]]

It might be more sensible to just use a binary string instead of using an Integer object (might as well use java.lang.Integer, though, if you do that), meaning you would access the said angle by using map.get("011011") or something. Might be simpler. If you use the array thing, it might make sense to just go ahead and allocate the thing (4 bytes * size of the array for that many null pointers), it may not be a big hit when it's empty anyways. If you know some segments won't be hit, though, that's a consideration (particularly if it happens to be a lot of segments) -- [[Kawigi]]

It would sure be easier and more readable to use such a binary string. But how does the HashMap store this?
I guess it would generate a hash number so it will not use more memory then using my Int.. Is this assumption correct? -- [[Vic]]

That should be correct. If a HashMap turns out to be weightier than you can handle, you could also try just implementing your own Hashtable. For even more efficient memory (but a compromise on speed somewhat), you could throw everything into a BST or something. -- [[Kawigi]]

Binary Search Tree I presume.. Hmm gotta think about that tomorrow....it's getting late here. By the way, I already tried using a normal array and memory consumption goes through the roof, even with a high percentage of nullpointers. -- [[Vic]]

Kawigi, I don't understand how I would use a BST in my situation. I'm still interested since you spoke of more efficient memory so could you explain a little? But for now I've decided to go and try make my own container class. I only need a byte (8 bits) of memory for my key and I'm pretty sure all the java.util containers use an int (32 bits). Besides, it's a good exercise :-) -- [[Vic]]

Well, you sort them into the BST by key. The root key can either be the first MicroSegment you use, or an intelligently chosen constant one. Then you sort new MicroSegments into the BST as you have them. It shouldn't really ever take more memory than it needs, and in the best case, look-ups and insertions are O(log(n)). In the worst case, without intervention, look-ups are O(n), which probably isn't what you want. You can reduce that by a constant (in half, actually) by picking an intelligent root node all the time. If you think look-ups are more common/time critical than insertions, you can do checks to make the tree more balanced for consistent O(log(n)) look-ups at the expense of some checks and possible AVL rotations within the insertion part. -- [[Kawigi]]

Just use a TreeMap. ;) If memory is a problem with a HashMap (it was never really a problem with mine -- do you have less than 256MB?), then you can try it with a TreeMap. If that isn't sufficient, then consider implementing your own structure. These two Java implementations are incredibly fast and efficient (though they can be improved upon), and I would definitely try both before hacking it out on my own. -- [[nano]]

Ok, I've used the HashMap in the end and ... hey! it works :-) Even without optimizing initial capacity and load factor the memory consumption is a fraction of what it was. Thanks for your help guys! -- [[Vic]]

This is belated, but have you considered BSTs? -- [[Kuuran]]

Ok, next time read the page first. Umm.. the best way to imp a BST for future revisions is probably to keep it sorted on numerical key, the way you first proposed, with each number being a 6-bit long bit vector (with a couple bits of wasted memory, since you'll no doubt be using shorts for this). Then simply fly through, find your object, use the reference to get whatever data is attached to the key, et voila. Since memory consumption and readability are issues, simply use the binary operators for everything, they ensure every bit represents something instead of every byte, long, double or whatnot, this is cutting your memory consumption severely, and they maintain easy readability, everyone knows what's happening when you binary OR or AND values. BSTs also have the property of growing/shrinking to accomodate only the given data, just make sure to do your housekeeping. -- [[Kuuran]]

== Multiple choice issue ==

Suppose I have a segment with data and I want to calculate the best angle that would have the most chance of hitting the enemy.

some ascii art:

<pre>
-47_______*_**__**_____________________0________*_______________*_*____*_*______+47 degrees
</pre>

The * means a previously observed succesful targeting angle.
I can clearly see that i should not take the average angle (AveragedBearingOffsetTargeting)
This data shows me that there are two spikes, one at -30 and one at +30 degrees. The -30 angle has the most occurences and has a narrower spike, so this is the angle to choose.

I could of course calculate the angle range for that specific distance, loop from -47 to +47 and determine at what angle the most occurences fall within the angle range. But that would mean a loop within a loop (times number of zoom levels) so the performance would be not so good.

I could also calculate the angle range for that distance and iterate over the occurences, determining which occurence picks the most neighbouring occurences. Again a loop within a loop, but this time both loops are limited in size. And the result may not be optimal in some specific situations....

So, what would be the most elegant way to calculate this angle? Is there an algo with only one loop?

-- [[Vic]]

* I've just thought of an algorithm with 1 loop, although I'm not sure if you're around to hear it =). Basically, you calculate the bin width for the distance. Then you iterate across, adding the value of the bin on the right and subtracting the value of the bin on the left. You store the value and index of the best position, and if the current value exceeds the best value, you set bestValue = currentValue; and bestIndex = currentIndex;. I like FastBots. =) -- [[Skilgannon]]

Well, I've thought about this some, as I also do statistics with waves, and it seems like it would be more accurate to use those old-school virtual bullets, because *every* bucket that hits is recorded (and as you observe, you want the mode, not the mean). There are two ways I've thought of to tune this - the first would be to collect data the same way and then figure out how wide of a margin of error you are allowed. The eventual calculation does take a loop inside of the loop, but the inside loop would be trivial. The second way would be to have your wave bullet tell you every bucket in your array that would have hit. In this case there is much more to do toward the end of the wave's life, but calculating the angle is as simple as finding the index of the max. -- [[Kawigi]]

I have just the same problem with a new pattern matcher I'm developing. At the end, I get N bearings distributed in a line and I have to choose the best place to fire. None of the approaches I have testes satisfy me: Sometimes granularity is to big, sometimes to low... Now I'm using an approach of segmenting it it lets say 6 overlaped parts, search for the one with the higher density, zoom into the segment, do it again, and so on. But I'm thinking seriously in using a NN to learn the best bearing from the distribution. -- [[Albert]]

It seems to me that a binary tree structure would be perfect for this. The top node will have the total number of hits, then its children node will have the total number of hits on the left, and the total number of hits on the right side, and their children will be split up left and right as well, and so on. Then you can choose which level to shoot at based on the hit percentage for the best node at each level among all sibling nodes (nodes which have the same parent). For instance, at the second level you have full left and full right. Let's say after you have 100 measurements, you have 60 on the left, and 40 on the right. Then on the next level you have 40 20 10 30, from left to right. Then you will shoot at the third level, because 40 / 60 is a better percentage than 60 / 100. Of course, margin of error should play a part in this calculation as well. You could choose based on the highest minimum percentage after margin of error, or the highest percentage (probably a bad idea), or you could randomly choose based on the amount of overlap among all of the choices (that's how I do my dynamic distancing).

For instance, in this case, the margin of error for the 40/60 measurement at 95% confidence is 1.96 * sqrt(0.66 * 0.33 / 60) = 11.9%. Thus, the minimum hit percentage is 66.6% - 11.9% = 54.7%. For the 60 / 100 measurement, we get 60% - 9.6% = 50.4%. Therefore, we will choose the third level of segmentation (which is a particularly good term for this structure), and we will fire full left.

As for using a NN to learn the best bearing...how will you train it? It seems to me that it is a statistical problem no matter how you look at it -- though I suppose a kind of fuzzy logic would apply here. I don't know anything about that though. Have you done any research on using fuzzy networks to do statistical analysis?

-- [[nano]]

Well, I have a cloud of points (always a fixed number of N points) and I know the right bearing to hit for all my historical data. So I just have to train the NN with input vector (PredBearing1, ... , PredBearingN) and output value the right bearing to hit. What I want it the NN to decide which way is better to "average" the bearings. I think it should work, but I haven't tried it yet. -- [[Albert]]

[[nano]]'s idea of dividing it up and going in the direction where there are more is what I did with my first stat gun (although it didn't work at all) in [[SpareParts]]. -- [[Kawigi]]

Here is an old idea I had but never got around to: how about using Java2D rectangles to represent the enemy in the hit positions, then take intersections of these until you find the point with most intersections? -- [[tobe]]

Sounds pretty CPU-intensive for thousands of rectangles, but I'm sure it could be optimized somehow. -- [[nano]]

If you found thousands of matches in the pattern-analyzer, that would be a big hit :-p Of course, on the statistical side, that's still a problem. -- [[Kawigi]]

Thanks folks, there a some nifty solutions mentioned here.. however most of them seem not appropriate for my situation. My use of MicroSegments means that I have A HUGE NUMBER of them. That means I must minimize my use of memory. I think I'll try my own second option (which is basically the same as Kawigi's first option). That way I'm sure to minimize the amount of memory taken up (only the actual angle values, nothing more). Performance should be ok, and I'm only losing a slight bit of accuracy, but I actually think that this is discardable. -- [[Vic]]

Once again I haven't read this page fully yet, but here's my solution: Do a one-pass loop of all your data. Initialize an array of 95 ints (they represent -47 to 47). Set a variable (let's call it x) to 0 at start. Each pass of the loop look at your next n degrees. n is your first tuning factor. For each hit you have in the next n degrees, increment x by one. Dump that value in the element of your int array corresponding to the pass if the loop you are on. At the end of the pass, decrement x by some value. One is a tempting value here, but it's obvious that it will quickly become unable to lower x 'fast' enough, so I'd suggest this decrement value be a function of your total waves fired (total waves / 95, for example). This function is your second tuning factor. Scan through your array and the highest value should be your best guess angle. There is an issue that this might bias it towards the +47 side. I'd recommend the solution to this be you do this loop twice, once counting up and once counting down, then add up the corresponding elements in each array into a third array, then scan this third array. This will eliminate that bias if you find it becomes an issue. This should also be very fast, it's essentially a one-pass algorithm. Whether it works reliably or not is another story, I just thought most of this up while typing. -- [[Kuuran]]

No comments? -- [[Kuuran]]

Ooops... Must have missed your entry when this discussion was going on. Sorry. Anyway, I solved my problem using Kawigi's idea. Basically it's just converting the bunch to a guess factor array. In my case I also take bot width into account. --[[Vic]]

== Development stage 1 ==

developement stage 1:

firing waves:
* fire waves when firing a new bullet, store parameters that quantify the Situation when the wave was fired
* when a wave hits the enemy, calculate the gunbearing that would have hit it
* propagate the angle through a multidimensional tree structure
* if the Situation is new for any node in the tree then create a new node and store the Angle there
* if the Situation already existed, then replace the Angle stored there with the newly observed Angle
* recurse deeper into the tree until the Situation parameters cannot be further divided

aiming:
* ask the treemap for the Angle stored in the Node that most closely resembles the Situation

After thorough testing of the properties of this gun I realise that in this stage it's not yet competitive
gun against the state-of-the-art guns. You'll find that it loses to the top bots.
It's about equally effective as normal PatternMatching guns. (So not bad...)

good things:
- it learns very fast.. in early rounds of a match (no saved data) it beats most other top statistical guns. I hope i can retain this property when adding MultipleChoice in [[/Stage2]].
- its performance is very fast (maybe it could be on the list FastBots;-).
- it punishes the enemy if its movement is not flat in short timeframes.

bad things:
- it learnes slower than top stat guns in later rounds, because it is lossy in the lower segments.
- it still uses a lot of memory, although it is now capable of running 1000 rounds without crashing my system :-).
- it cannot punish the enemy if its long term movement profile is flawed (not flat), but its short term movement profile is flat.

-----
About its ability to find non-flat movement in short time frames. Only in
certain conditions I think. Since otherwise it would have spotted the
weakness of the Tityus 0.2-0.3 movement. You should probably keep that
version of the movement just for testing purposes. I know I will. =)

* yes .. that is strange .. it sometimes gets the weakness, but not nearly as good as DT does .. I think that it is because Tityus moves between segments too quickly. I'll have to think how (and if) i should solve this -- [[Vic]]

When it comes to finding weaknesses in the long term profile. If it's really
there you should be able to zoom out, shouldn't you? Maybe if you could use
a virtual guns type of approach with different zoom levels? I don't really
understand the theory behind zoom targeting so I might be way off here.

* Currently the MacroSegments don't yet have statistical properties, so they are much less accurate then the MicroSegments. The virtual gun type approach is in fact also part of the design. Each segment will have a hit ratio and when aiming I will choose the segment with the highest hit rate. In the next stage I will implement this. -- [[Vic]]

Can't you post your TargetingChallenge results with ZoomTargeting and your
pattern matcher for reference? Especially the latter one would be
interesting to keep there since it is one of the guns in the
MovementChallenge.

* I already posted the results for [[Mazer]], which has the ZoomTargeting gun WITH MultipleChoice stats in the MacroSegments. I'll post results for PatternMatcherBot also. --[[Vic]]

[[PEZ]]

{{Targeting Navbox}}
[[Category:Targeting Discussions]]

Zoom Targeting

2011-04-01T17:15:06Z

Ceasar:

ZoomTargeting is a hybrid of StatisticalTargeting and a new form of PatternMatching and should combine the best of both worlds. It uses SegmentedData (currently 6 dimensions) and gets this data using a variant of [[Wave]]s.

Its StatisticalTargeting properties should make sure that
*it is very good at long term learning and continues to improve even in very long matches
*it can exploit weaknesses such as spikes in the enemies MovementProfile
*it can do a good educated guess when PatternMatching fails (when there's not enough data in the microsegment)

Its PatternMatching properties ensure that
*it adapts very fast to new enemies or situations.
*it can exploit weaknesses such as dodging and other types of repetitive movement
*it can get a reasonably high hitrate early on in a match if there is no stored data
*it can be more accurate than StatisticalTargeting (if there's enough data in the microsegment)

The new thing is that this targeting method basically zooms in (more PatternMatching) or out (more StatisticalTargeting) depending on the amount of data it has and the zoom level's segment size. Currently I use 8 zoom levels with increasing segment sizes. PatternMatching takes place in what I call the MicroSegments. In these tiny segments even only 1 previously reported angle is enough to deliver a firing angle with a high probability of hitting the enemy. StatisticalTargeting takes place when you zoom out, in the MacroSegments. The segments here are much larger and contain more data to do statistical calculations with. Learning speed increases when the zoom level increases.

The PatternMatching algorithm that I use differs greatly from traditional PatternMatchers. You might even argue if it is PatternMatching at all. I call it PatternMatching because it matches to a very specific situation. As a result it performs very well against bots that other PM guns perform well against :-). A situation is basically a very small segment with a lot of dimensions. Currently I use 6 dimensions, but if I can solve a memory issue I will use even more. I might even try a dimension that uses the movement history to make it a more official pattern matcher :-). In practise, this algorithm is a bit less accurate against truly predictable movers like SpinBot or PatternBot, but more effective against random movers. And since none of the top bots are truly predictable.........

There is a nice side-effect to using MicroSegments: I keep track of the number of Segments ('situations') that are used. This number increases more rapidly as the enemy has better movement. I am guessing this Segment count (say after 1000 rounds) could be a nice alternative Movement Index.

-- [[Vic Stewart]]

How far are you in developing this awesome gun?

*The next step is to implement the Statistical calculations of the macrosegments.
*decide whether to fire a [[Wave]] every scan or along with a bullet.
*better memory management

Yeah, yeah, yeah..... You talk the talk, but does it walk the walk?

*So far the results are very encouraging. I was unsure if the new PatternMatching algo would work, but it does! For instance, it beats all but one of the samplebots in a 10 round match, without stored data, whilst being stationary. (only TrackFire is a problem but that's due to a known bug)
*I tested against one of the challengers in the PatternMatcherChallenge and with just the new PatternMatching algo I got its index down from 32% to 25%. I wonder what will happen when I add the StatisticalTargeting part....

Sounds great, can I help in anyway?

* Yes you can :-) I have two issues:

== Memory issue ==

Currently I am reserving memoryspace for every zoom level whether it is used or not. I use a simple (6 dimensional) array for that. The drawback of this is that memory is reserved for segments that I never use and memory soon spins out of control. Now I want to implement a dynamic array (Vector or ArrayList or something). The question is, which type of dynamic array would be most suitable for this situation? Most importantly I require the lowest possible memory footprint.

-- [[Vic]]

Both an ArrayList and a Vector would work here. The constructor for each allow you to specify the size of the Arraylist to be built. They will also grow as more items are added to them. The "growing" part can be expensive in terms of CPU cycles so you will most likely need to play with them to see how it works out with skipped turns. Of the two, I would imagine that the ArrayList would be more appropriate than the Vector. I am also unsure if this will buy you anything in terms of memory footprint as I think in the end both classes use an Array with wrapper methods to implement their functionality. -- [[Sparafucil3|jim]]

LOL, I already implemented this gun about three months ago for Statistician -- it's sitting on my hard drive right now. This gun was the main feature of Statistician (and his namesake) and it will be one of Tax's main guns. You can probably find me talking about it here and there on the wiki. Although, it will be better implemented in Tax due to the ability to segment stats more intelligently with his neural network. Oh, to answer your question, I used a HashMap that stores strings of movement. For instance, if I tokenize a bot's velocity into the letters a-p, where a is -8 and p is +8, then I might have a string that looks like this: "aaaacegiiii". I stick that in the HashMap, along with a two-dimensional array of all my segments, and I just update the array as I need to. This makes sure that you only use memory for the patterns that you have seen, and it is a very fast pattern-matcher. -- [[nano]]

Interestingly, this approach also allows an infinite amount of "zooming". Of course, there are memory limits, but I ran my algorithm at a maximum of 200 frames of movement, and it ran fast with no memory problems. Thank God for a fast and efficient HashMap implementation. -- [[nano]]

Ok, thanx. What would I use for index if I'd want to implement an ArrayList? Say, for instance, in my original multidimensional Array I want to access Angle[0][1][1][0][1][1]. I need to do some sort of mapping from the 6 original indices to a single one. A possibility might be to convert these indices to a single integer, in this case ranging from 0 to 63 (6 bits). But can I insert the Angle at position 54 [ArrayList: add(54, Angle)] without my ArrayList or Vector immediately reserving memory space for the preceding 0 to 53? I think not, but I'm not sure. Does anyone know for sure?

That probably means the HashMap is the better solution. I can put my single Index 54 in it along with my Angle value [HashMap: put(Indexobject, Angleobject). However, a HashMap stores both key and value objects. Suppose my original value to store is an int. I now need to construct a wrapper object for it, an Int. Also I need to construct an Int object for my key. Assuming an Int takes equal memoryspace (it is just an int with wrapper methods, right?) then I must conclude that using a HashMap requires double the amount of memory PER ENTRY. So, if I have less than 32 entries I should use the HashMap, else I should stick to my original Array. This is getting complicated... Although I think that in practise I almost never will get more then 32 MicroSegments per Segment. I'll try the HashMap and report back if it works...

-- [[Vic]]

It might be more sensible to just use a binary string instead of using an Integer object (might as well use java.lang.Integer, though, if you do that), meaning you would access the said angle by using map.get("011011") or something. Might be simpler. If you use the array thing, it might make sense to just go ahead and allocate the thing (4 bytes * size of the array for that many null pointers), it may not be a big hit when it's empty anyways. If you know some segments won't be hit, though, that's a consideration (particularly if it happens to be a lot of segments) -- [[Kawigi]]

It would sure be easier and more readable to use such a binary string. But how does the HashMap store this?
I guess it would generate a hash number so it will not use more memory then using my Int.. Is this assumption correct? -- [[Vic]]

That should be correct. If a HashMap turns out to be weightier than you can handle, you could also try just implementing your own Hashtable. For even more efficient memory (but a compromise on speed somewhat), you could throw everything into a BST or something. -- [[Kawigi]]

Binary Search Tree I presume.. Hmm gotta think about that tomorrow....it's getting late here. By the way, I already tried using a normal array and memory consumption goes through the roof, even with a high percentage of nullpointers. -- [[Vic]]

Kawigi, I don't understand how I would use a BST in my situation. I'm still interested since you spoke of more efficient memory so could you explain a little? But for now I've decided to go and try make my own container class. I only need a byte (8 bits) of memory for my key and I'm pretty sure all the java.util containers use an int (32 bits). Besides, it's a good exercise :-) -- [[Vic]]

Well, you sort them into the BST by key. The root key can either be the first MicroSegment you use, or an intelligently chosen constant one. Then you sort new MicroSegments into the BST as you have them. It shouldn't really ever take more memory than it needs, and in the best case, look-ups and insertions are O(log(n)). In the worst case, without intervention, look-ups are O(n), which probably isn't what you want. You can reduce that by a constant (in half, actually) by picking an intelligent root node all the time. If you think look-ups are more common/time critical than insertions, you can do checks to make the tree more balanced for consistent O(log(n)) look-ups at the expense of some checks and possible AVL rotations within the insertion part. -- [[Kawigi]]

Just use a TreeMap. ;) If memory is a problem with a HashMap (it was never really a problem with mine -- do you have less than 256MB?), then you can try it with a TreeMap. If that isn't sufficient, then consider implementing your own structure. These two Java implementations are incredibly fast and efficient (though they can be improved upon), and I would definitely try both before hacking it out on my own. -- [[nano]]

Ok, I've used the HashMap in the end and ... hey! it works :-) Even without optimizing initial capacity and load factor the memory consumption is a fraction of what it was. Thanks for your help guys! -- [[Vic]]

This is belated, but have you considered BSTs? -- [[Kuuran]]

Ok, next time read the page first. Umm.. the best way to imp a BST for future revisions is probably to keep it sorted on numerical key, the way you first proposed, with each number being a 6-bit long bit vector (with a couple bits of wasted memory, since you'll no doubt be using shorts for this). Then simply fly through, find your object, use the reference to get whatever data is attached to the key, et voila. Since memory consumption and readability are issues, simply use the binary operators for everything, they ensure every bit represents something instead of every byte, long, double or whatnot, this is cutting your memory consumption severely, and they maintain easy readability, everyone knows what's happening when you binary OR or AND values. BSTs also have the property of growing/shrinking to accomodate only the given data, just make sure to do your housekeeping. -- [[Kuuran]]

== Multiple choice issue ==

Suppose I have a segment with data and I want to calculate the best angle that would have the most chance of hitting the enemy.

some ascii art:

<pre>
-47_______*_**__**_____________________0________*_______________*_*____*_*______+47 degrees
</pre>

The * means a previously observed succesful targeting angle.
I can clearly see that i should not take the average angle (AveragedBearingOffsetTargeting)
This data shows me that there are two spikes, one at -30 and one at +30 degrees. The -30 angle has the most occurences and has a narrower spike, so this is the angle to choose.

I could of course calculate the angle range for that specific distance, loop from -47 to +47 and determine at what angle the most occurences fall within the angle range. But that would mean a loop within a loop (times number of zoom levels) so the performance would be not so good.

I could also calculate the angle range for that distance and iterate over the occurences, determining which occurence picks the most neighbouring occurences. Again a loop within a loop, but this time both loops are limited in size. And the result may not be optimal in some specific situations....

So, what would be the most elegant way to calculate this angle? Is there an algo with only one loop?

-- [[Vic]]

* I've just thought of an algorithm with 1 loop, although I'm not sure if you're around to hear it =). Basically, you calculate the bin width for the distance. Then you iterate across, adding the value of the bin on the right and subtracting the value of the bin on the left. You store the value and index of the best position, and if the current value exceeds the best value, you set bestValue = currentValue; and bestIndex = currentIndex;. I like FastBots. =) -- [[Skilgannon]]

Well, I've thought about this some, as I also do statistics with waves, and it seems like it would be more accurate to use those old-school virtual bullets, because *every* bucket that hits is recorded (and as you observe, you want the mode, not the mean). There are two ways I've thought of to tune this - the first would be to collect data the same way and then figure out how wide of a margin of error you are allowed. The eventual calculation does take a loop inside of the loop, but the inside loop would be trivial. The second way would be to have your wave bullet tell you every bucket in your array that would have hit. In this case there is much more to do toward the end of the wave's life, but calculating the angle is as simple as finding the index of the max. -- [[Kawigi]]

I have just the same problem with a new pattern matcher I'm developing. At the end, I get N bearings distributed in a line and I have to choose the best place to fire. None of the approaches I have testes satisfy me: Sometimes granularity is to big, sometimes to low... Now I'm using an approach of segmenting it it lets say 6 overlaped parts, search for the one with the higher density, zoom into the segment, do it again, and so on. But I'm thinking seriously in using a NN to learn the best bearing from the distribution. -- [[Albert]]

It seems to me that a binary tree structure would be perfect for this. The top node will have the total number of hits, then its children node will have the total number of hits on the left, and the total number of hits on the right side, and their children will be split up left and right as well, and so on. Then you can choose which level to shoot at based on the hit percentage for the best node at each level among all sibling nodes (nodes which have the same parent). For instance, at the second level you have full left and full right. Let's say after you have 100 measurements, you have 60 on the left, and 40 on the right. Then on the next level you have 40 20 10 30, from left to right. Then you will shoot at the third level, because 40 / 60 is a better percentage than 60 / 100. Of course, margin of error should play a part in this calculation as well. You could choose based on the highest minimum percentage after margin of error, or the highest percentage (probably a bad idea), or you could randomly choose based on the amount of overlap among all of the choices (that's how I do my dynamic distancing).

For instance, in this case, the margin of error for the 40/60 measurement at 95% confidence is 1.96 * sqrt(0.66 * 0.33 / 60) = 11.9%. Thus, the minimum hit percentage is 66.6% - 11.9% = 54.7%. For the 60 / 100 measurement, we get 60% - 9.6% = 50.4%. Therefore, we will choose the third level of segmentation (which is a particularly good term for this structure), and we will fire full left.

As for using a NN to learn the best bearing...how will you train it? It seems to me that it is a statistical problem no matter how you look at it -- though I suppose a kind of fuzzy logic would apply here. I don't know anything about that though. Have you done any research on using fuzzy networks to do statistical analysis?

-- [[nano]]

Well, I have a cloud of points (always a fixed number of N points) and I know the right bearing to hit for all my historical data. So I just have to train the NN with input vector (PredBearing1, ... , PredBearingN) and output value the right bearing to hit. What I want it the NN to decide which way is better to "average" the bearings. I think it should work, but I haven't tried it yet. -- [[Albert]]

[[nano]]'s idea of dividing it up and going in the direction where there are more is what I did with my first stat gun (although it didn't work at all) in [[SpareParts]]. -- [[Kawigi]]

Here is an old idea I had but never got around to: how about using Java2D rectangles to represent the enemy in the hit positions, then take intersections of these until you find the point with most intersections? -- [[tobe]]

Sounds pretty CPU-intensive for thousands of rectangles, but I'm sure it could be optimized somehow. -- [[nano]]

If you found thousands of matches in the pattern-analyzer, that would be a big hit :-p Of course, on the statistical side, that's still a problem. -- [[Kawigi]]

Thanks folks, there a some nifty solutions mentioned here.. however most of them seem not appropriate for my situation. My use of MicroSegments means that I have A HUGE NUMBER of them. That means I must minimize my use of memory. I think I'll try my own second option (which is basically the same as Kawigi's first option). That way I'm sure to minimize the amount of memory taken up (only the actual angle values, nothing more). Performance should be ok, and I'm only losing a slight bit of accuracy, but I actually think that this is discardable. -- [[Vic]]

Once again I haven't read this page fully yet, but here's my solution: Do a one-pass loop of all your data. Initialize an array of 95 ints (they represent -47 to 47). Set a variable (let's call it x) to 0 at start. Each pass of the loop look at your next n degrees. n is your first tuning factor. For each hit you have in the next n degrees, increment x by one. Dump that value in the element of your int array corresponding to the pass if the loop you are on. At the end of the pass, decrement x by some value. One is a tempting value here, but it's obvious that it will quickly become unable to lower x 'fast' enough, so I'd suggest this decrement value be a function of your total waves fired (total waves / 95, for example). This function is your second tuning factor. Scan through your array and the highest value should be your best guess angle. There is an issue that this might bias it towards the +47 side. I'd recommend the solution to this be you do this loop twice, once counting up and once counting down, then add up the corresponding elements in each array into a third array, then scan this third array. This will eliminate that bias if you find it becomes an issue. This should also be very fast, it's essentially a one-pass algorithm. Whether it works reliably or not is another story, I just thought most of this up while typing. -- [[Kuuran]]

No comments? -- [[Kuuran]]

Ooops... Must have missed your entry when this discussion was going on. Sorry. Anyway, I solved my problem using Kawigi's idea. Basically it's just converting the bunch to a guess factor array. In my case I also take bot width into account. --[[Vic]]

== Development stage 1 ==

developement stage 1:

firing waves:
* fire waves when firing a new bullet, store parameters that quantify the Situation when the wave was fired
* when a wave hits the enemy, calculate the gunbearing that would have hit it
* propagate the angle through a multidimensional tree structure
* if the Situation is new for any node in the tree then create a new node and store the Angle there
* if the Situation already existed, then replace the Angle stored there with the newly observed Angle
* recurse deeper into the tree until the Situation parameters cannot be further divided

aiming:
* ask the treemap for the Angle stored in the Node that most closely resembles the Situation

After thorough testing of the properties of this gun I realise that in this stage it's not yet competitive
gun against the state-of-the-art guns. You'll find that it loses to the top bots.
It's about equally effective as normal PatternMatching guns. (So not bad...)

good things:
- it learns very fast.. in early rounds of a match (no saved data) it beats most other top statistical guns. I hope i can retain this property when adding MultipleChoice in [[/Stage2]].
- its performance is very fast (maybe it could be on the list FastBots;-).
- it punishes the enemy if its movement is not flat in short timeframes.

bad things:
- it learnes slower than top stat guns in later rounds, because it is lossy in the lower segments.
- it still uses a lot of memory, although it is now capable of running 1000 rounds without crashing my system :-).
- it cannot punish the enemy if its long term movement profile is flawed (not flat), but its short term movement profile is flat.

-----
About its ability to find non-flat movement in short time frames. Only in
certain conditions I think. Since otherwise it would have spotted the
weakness of the Tityus 0.2-0.3 movement. You should probably keep that
version of the movement just for testing purposes. I know I will. =)

* yes .. that is strange .. it sometimes gets the weakness, but not nearly as good as DT does .. I think that it is because Tityus moves between segments too quickly. I'll have to think how (and if) i should solve this -- [[Vic]]

When it comes to finding weaknesses in the long term profile. If it's really
there you should be able to zoom out, shouldn't you? Maybe if you could use
a virtual guns type of approach with different zoom levels? I don't really
understand the theory behind zoom targeting so I might be way off here.

* Currently the MacroSegments don't yet have statistical properties, so they are much less accurate then the MicroSegments. The virtual gun type approach is in fact also part of the design. Each segment will have a hit ratio and when aiming I will choose the segment with the highest hit rate. In the next stage I will implement this. -- [[Vic]]

Can't you post your TargetingChallenge results with ZoomTargeting and your
pattern matcher for reference? Especially the latter one would be
interesting to keep there since it is one of the guns in the
MovementChallenge.

* I already posted the results for [[Mazer]], which has the ZoomTargeting gun WITH MultipleChoice stats in the MacroSegments. I'll post results for PatternMatcherBot also. --[[Vic]]

{{Targeting Navbox}}
[[PEZ]]
[[Category:Targeting Discussions]]

Symbolic Dynamic Segmentation

2011-04-01T17:14:42Z

Ceasar:

A hybrid [[targeting]] method that acts as a [[Log-Based Targeting|log-based]] [[State Matching|state matching]] gun with [[dynamic segmentation]]. The goal is that with low segmentation, it acts like a [[Statistical Targeting|statistical]] gun, while with higher segmentation, it acts more like a [[pattern matching]] gun.

== Pseudocode ==

* Every turn, launch a [[wave]]. When it hits, add the [[bearing offset]] (or [[GuessFactor]]) to a hash table, indexed by a key that describes the enemy state at fire time.
* The key is a string derived from the attributes that you want to segment on, which represent the enemy state at fire time. For example, if you are segmenting by enemy velocity and acceleration, you define a function: f(velocity, acceleration) -> String(2)
* When aiming:
** Calculate the key for the current wave.
** Search the log for all (or last <code>X</code>) bearing offsets (or GuessFactors) previously recorded for this key. This returns a list of firing angles for this situation.
** Use a [[kernel density]] function to decide on the best firing angle from the list of firing angles.
** If the search for the key fails (or doesn't return enough results), remove the last symbol of the string and try again. This means that it uses a high segmentation when there is more data available, but reduces it when there is not enough data available.

== See also ==

* [[Virus|Bot: Virus]]
* [[State Matching]]
* [[Kernel Density]]
* [[Dynamic Segmentation]]
* [[Pattern Matching]]

{{Targeting Navbox}}
[[Category:Advanced Targeting Strategies]]
[[Category:Log-Based Targeting]]

Fuzzy Logic Targeting

2011-04-01T17:14:21Z

Ceasar:

I was thinking about this earlier and thought, hey why hasn't this page been made yet. I know the basics of Fuzzy logic, who doesn't but putting those basics into RoboCode is another thing altogeather. I figure fuzzy logic can be more of an -add on- then a actual gun. What is this technique, does anyone know, does it work? I have ideas on how it ''could'' work. But I just wanted to know why this page was here.

If anyone wants me to toss my idea on here feel free to ask, but it would probably make the aiming worse then better. -- Ann

Isn't GF targeting an implementation of fuzzy logic? It involves making decisions based on imperfect data. It assigns a 'goodness' score for the 'perfect data' indicating something, and then picks the best score - that sounds like fuzzy logic to me. --[[Jp]]

I wouldn't call GF targeting fuzzy logic. I think an example of fuzzy logic would be something like this: If damage taken per round > 40, enemy is a strong bot. If damage taken per round is < 20, enemy is a weak bot. If 20 < damage taken per round < 40, then "strongness" of enemy is (damage per round - 20) / 20. If behaviors against strong bots (like a flattener perhaps) were partially enabled based on this strongness factor, that would be an application of fuzzy logic. Basically fuzzy logic is just a way of saying that there are values in between true and false, or strong and weak in my example. --[[David Alves]]

I figured it would be something like the an gf betweem two bins, using otehr bins to get a fuzzy idea where between them to aim. However all my playing around in this has just crashed and burned. Overall it seems to lower the targeting score by a bit on a 39 segment gun. It might do better on a lower segment gun and thus be a nice add fast learning addon.

As for a gun in itself it could be something like a AverageBearingOffset gun with a fuzzy offset based on the last few turns. Or push my first idea to an extreme and only have 3 to 5 bins total and use fuzzy logic to determine the placement (would require something that definitely works). -- [[Chase-san]]

[[Chase-san]], you may want to reconsider the 3 - 5 bin approach. Remember that bins represent physical bearings within the possible bearings a bot may move. For example, in the time it takes a power 3 bullet to arrive, a bot can move a maximum of 46 degrees in either direction; so 3 bins might look like this:

<pre>
bin[0] -> -46
bin[1] -> 0
bin[2] -> 46
</pre>

Five bins:

<pre>
bin[0] -> -46
bin[1] -> -23
bin[2] -> 0
bin[3] -> 23
bin[4] -> 46
</pre>

Seven bins:
<pre>
bin[0] -> -46
bin[1] -> -30.67
bin[2] -> -15.34
bin[3] -> 0
bin[4] -> 15.34
bin[5] -> 30.67
bin[6] -> 46
</pre>

Basically, by using more bins, you make your statistical estimation more precise. 3 bins can only represents head on targeting (bearing 0) and linear targeting (bearing +/-46). A savvy bot will hide between these bearings. The flip side is that too many bins make your bot learn slowly. There's a tradeoff and most competitive bots use between 15 and 75 bins(at least the open source bots).

As for fuzzy logic, I often confuse probability with fuzzy logic. Strictly speaking, all of the learning bots I can think of use probability and I'm not aware of any that use true mathematical fuzzy logic. This article seems good about explaining the distinction: http://en.wikipedia.org/wiki/Fuzzy_logic. Cheers and best of luck in your hunt for 25. --[[Corbos]]

Maybe it is just my technique, but I don't see how slicing up the guess factor / bearing offset data more finely affects learning speed. Higher segmentation, definitely, but not more visit count bins. Then again when I register a hit I don't store a hit in just one bin. Ugluk has 101 bins in his bearing offset gun, and 111 in his guess-factor gun. It's certainly not the best gun around, but it's at 82% in the TC2K6 compared to the best bot at 90%. -- Martin (edit: the TC2K6 score does not include my recently added GF gun)

Well, if you picture a gun with a million bins, it's unlikely that any bin would get more than one visit, so your gun wouldn't pick the proper one, there would be too many bins that were tied with 1 hit each. I think that's the basic issue with too many bins: the more bins you have, the fewer visits per bin you have, so the harder it is to see a clear best bin. Have you tried changing your gun to use only 30-50 bins? For reference, [[Phoenix]] uses 31. I believe [[Dookious]] uses 47.--[[David Alves]]

Well, when I register a hit I measure the arc of the wave that crashed against me, and I drape that arc across my bins. So if I have a million bins, I'll be draping the hit across 150000 or so. The next wave crashes and drapes across another 150000ish, creating some overlap. The area of overlap is now the high point. I can pick one of the 75000 or so high water marks at random, or whatever technique you would use in a 30 bin setup in the same situation. It is my version of bin smoothing. -- Martin

Sounds like a good way of handling the issue I mentioned. =)--[[David Alves]]

If I remember correctly FuzzyLogic is just a possible set of data between two well defined sets of data (or even two other possible sets of data). However if you wanted to do a "pure" FuzzyLogic gun, you would have to define it as something like, the bot was here and now its here, so now it should be between here and that other place. I personally think a "good" Pure FuzzyLogic gun is fiction. Sure you could make a pure fuzzylogic gun, but I doupt it would fire anywhere near the correct vectors. Thus I think at best it could be used as a add on to a already existing gun type (one that atleast has some margin of success). Being a little fuzzy about where your enemy is going to be is gonna make you miss, IMHO. -- [[Chase-san]]

{{Targeting Navbox}}
[[Category:Targeting Discussions]]

Neural Targeting

2011-04-01T17:13:53Z

Ceasar:

{{Wikipedia|Neural network}}
A form of targeting that makes use of one or more neural networks to predict enemy movement.

== Early forms ==

The first known bot to make use of neural networks was [[Qohnil]]'s [[XBot]], in May, 2002, but not much is known about it. [[Albert]]'s neural network bot [[ScruchiPu]] came roughly a year later, which sparked some interest in neural networks on the RoboWiki. ScruchiPu used enemy speed and turn rate as input and output, iterating into the future one tick at a time to predict the enemy's movements, much like [[pattern matching]].

Several more neural targeting bots were released in the following years, meeting with varied success, but none approaching the accuracy of other top targeting methods.

== Recent developments ==

A more recent neural network bot is [[Engineer]], authored by [[Wcsv]]. Engineer uses [[Waves]] to collect [[GuessFactors]] that correlate to given situations, much like a [[GuessFactor Targeting (traditional)|traditional GuessFactor gun]], then feeds the situational attributes (as input) and resulting GuessFactors (as output) to the neural network as training data. Engineer was the first neural targeting bot to reach a [[RoboRumble]] rating of 2000+ when its initial release hit a rating of 2030 in May, 2006. (Incidentally, Engineer also uses this neural network system for its [[WaveSurfing]].)

Another attempt at neural targeting came in 2007 from [[Chase-san]] in the form of his [[Chase-san/Prototype|"Prototype"]] gun. Attached to an early version of [[DrussGT]]'s movement, it reached a rating of 2005 in the RoboRumble in September, 2007.

The most modern example of neural targeting is [[Gaff]], which uses [[waves]], [[GuessFactor|GuessFactors]], [[wikipedia:Radial basis function|Radial Basis Functions]], and two neural networks. [[User:Darkcanuck|Darkcanuck]] has composed a detailed write-up of its workings at [[Gaff/Targeting]]. Gaff's gun is quite strong, on par with other top gun types according to [[Targeting Challenge 2K7/Results|TC2K7 results]], and is probably the strongest [[Anti-Surfer Targeting|Anti-Surfer gun]] of any kind, according to [[Anti-Surfer Challenge/Results|Anti-Surfer Challenge results]].

== External links ==

* [http://www.geocities.com/chen_levkovich/tdlearningproject.html Temporal Difference Learning project]
* [http://www.jooneworld.com/ Java Object Oriented Neural Engine]
* [http://sourceforge.net/projects/jsomap/ JSOMap] - A Java-based package for working with Self-Organizing Maps (are another type of neural network).

== See also ==

* [[NeuraLib]] - A BPN library, [[code size]]: 603.
* [[NRLIBJ]] - A BPN java package.
* [[EANN]] - Evolving NeuralNetwork using Genetic algorithm.
* [[NeuralTargeting/TDNN]]

{{Targeting Navbox}}
[[Category:Advanced Targeting Strategies]]
[[Category:Targeting]]

Targeting Matrix

2011-04-01T17:13:30Z

Ceasar:

A technique employing knowledge at the intersection of linear algebra and statistics.

== Idea ==

Using projections, as described in linear algebra, it's possible to map an n-dimensional matrix, A, to a vector, b, via a third vector, x, such that Ax=b.

== Example ==

Consider we wanted to simply devise a matrix that would map distance to a firing angle. In order to do this, we might create an 3-dimensional matrix, with values <code>A = [x^2, x, 1]</code> for every x that we record, where x is the distance to our target at the time of firing, and a second vector, <code>b = [y]</code> where y is the correct firing angle. After acquiring three data points, we'll be able to arrange our vectors in the form Ax=b, as such:

<code>A = [[a^2, a, 1], [b^2, b, 1], [c^2, c, 1]]

x = [unknown1, unknown2, unknown3]

b = [[angle_a], [angle_b], [angle_c]]</code>

Now we wish to solve for '''x'''. To do this, we project A onto '''b'''. Therefore, we first multiply both sides of the equation by <math>A^T</math> to get:

<math>A^T * A * x = A^T * b</math>

And then multiply by the inverse of <math>(A^T * A)</math> to reach <math>x = (A^T * A)^{-1} * A^T * b</math>. We now can compute '''x'''.

With '''x''', it is possible to map distances to targets to firing angles, via simply inputing distance into the function:

<math>f(x) = unknown_1 * x^2 + unknown_2 * x + unknown_3 * 1 = angle</math>

Notice that the projection matrix, <math>(A^T * A)^{-1} * A^T</math>, was used to compute '''x''' rather than simply <math>A^{-1}</math>. This is because by using the projection matrix it is possible to compute '''x''' for any number of tuples. This is extremely useful since the alternative is to use a polynomial of dimension <math>n</math> to fit a line through all of the <math>n</math> data points.

This idea is also extremely powerful because it simplifies segmentation- in order to track another factor one simply appends a vector to A. For example, if one wanted to additionally track target velocity, one would simply append another vector to A, such that:

<code>A = [[v, a^2, a, 1], [v, b^2, b, 1], [v, c^2, c, 1]]</code>

where v is the target velocity. ('''x''' in this case would also need another element).

{{Targeting Navbox}}
[[Category:Targeting]]

Pyramid Bins

2011-04-01T17:12:22Z

Ceasar:

{{Youtube|QXggg1un_Pw}}

A form of statistical targeting that combines guess factors, segmentation, and visit count stats.

[[Image:PyramidSegmentation.jpg|right]]

==Idea==

Segmentation typically involves segmenting into a significant number of buckets- it's not uncommon to see 30 buckets or more. However, by scanning the distance to our target, we can actually reduce the number of buckets to only a fraction of what's typically used, based on the maximum escape angle and chord lengths. The result is greatly improved learning speeds and improved accuracy, particularly against wave surfers.

==Implementation==

In order to implement pyramid segmentation, we simply need to make a few calculations to determine how many buckets we'll need at any particular range.
-First, calculate the Maximum Escape Angle.
-Then using the triangle used to calculate the MEA, calculate the length of the side opposite the MEA. Since the triangle is Right, this comes out to be 'distance to target' * tan(MEA). Call this length 'C'.
-Divide 'C' by twice the width of a bot minus one, 36 * 2 - 1 = 71, and take the ceiling of the result. This gives the minimum number of buckets needed to hit the target at that distance.

By pre-calculating which distances lead to a change in the number of buckets, we can very easily implement this into our code. For simple purposes, the breaks are at d=79n/tan(MEA) for all integer n (but this only needs to be calculated up to the size of the battlefield). For Firepower=3, this comes out to a break at every 75 units, which isn't bad given that the size of a typical battlefield is 800 (that is, 11 buckets at most).

Notice that we used buckets of width 79- This means that in order to to work properly our gun must fire directly into the center of each bucket.

==Advanced Refinements==

-Since only at breakpoints are each of the buckets an even 79, it's clear that inbetween these breaks, all the buckets are of a width smaller than 79. This means that by firing directly into the edge buckets (0 and n-1 of our array) we actually are losing some accuracy. More advanced implementations could have the turret fire as close to the center as possible while still covering every point inside the bucket.

-The gun could also just the MEA by adjusting firepower. Since against a good wave surfer, the gun's accuracy will be at worst 1/n where n is the number of buckets, it could very well be worth it to slightly decrease firepower in order to constrict the MEA and stabilize the number of buckets.

-Furthermore, the bot could attempt to position itself at certain ranges that are better defined, rather than fight at ranges where information is sparse.

== Weaknesses ==

When the target is near walls, the shot often goes into the wall unless the [[Maximum Escape Angle/Precise|Precise MEA]] is calculated.

{{Targeting Navbox}}
[[Category:Targeting]]

Talk:Targeting Challenge (original)

2011-03-29T02:58:27Z

Ceasar:

The download link doesn't work. Is that intentional / can it be fixed? --[[User:Ceasar|Ceasar]] 02:21, 29 March 2011 (UTC)

I don't think it's intentional, and it looks like it can't be recovered from the file host. Have you considered trying a newer targeting challenge such as [[Targeting Challenge 2K7]]? --[[User:Ncj|Ncj]] 02:45, 29 March 2011 (UTC)

Yeah, I grabbed 2K6 immediately after. Just wanted to point it out in the case someone had the .zip. --[[User:Ceasar|Ceasar]] 02:58, 29 March 2011 (UTC)

Talk:Targeting Challenge (original)

2011-03-29T02:21:30Z

Ceasar: Created page with "The download link doesn't work. Is that intentional / can it be fixed? --~~~~"

The download link doesn't work. Is that intentional / can it be fixed? --[[User:Ceasar|Ceasar]] 02:21, 29 March 2011 (UTC)

Talk:Targeting Matrix

2011-03-25T22:24:58Z

Ceasar: Created page with "Has anybody ever tried using a matrix to fire before? It seems like an extremely natural fit. --~~~~"

Has anybody ever tried using a matrix to fire before? It seems like an extremely natural fit. --[[User:Ceasar|Ceasar]] 22:24, 25 March 2011 (UTC)

Pyramid Bins

2011-03-25T18:44:46Z

Ceasar:

Pyramid Bins

2011-03-25T17:15:29Z

Ceasar: /* Weaknesses */

A form of statistical targeting that combines guess factors, segmentation, and visit count stats.

[[Image:PyramidSegmentation.jpg|right]]

==Idea==

Segmentation typically involves segmenting into a significant number of buckets- it's not uncommon to see 30 buckets or more. However, by scanning the distance to our target, we can actually reduce the number of buckets to only a fraction of what's typically used, based on the maximum escape angle and chord lengths. The result is greatly improved learning speeds and improved accuracy, particularly against wave surfers.

==Implementation==

In order to implement pyramid segmentation, we simply need to make a few calculations to determine how many buckets we'll need at any particular range.
-First, calculate the Maximum Escape Angle.
-Then using the triangle used to calculate the MEA, calculate the length of the side opposite the MEA. Since the triangle is Right, this comes out to be 'distance to target' * tan(MEA). Call this length 'C'.
-Divide 'C' by twice the width of a bot minus one, 36 * 2 - 1 = 71, and take the ceiling of the result. This gives the minimum number of buckets needed to hit the target at that distance.

By pre-calculating which distances lead to a change in the number of buckets, we can very easily implement this into our code. For simple purposes, the breaks are at d=79n/tan(MEA) for all integer n (but this only needs to be calculated up to the size of the battlefield). For Firepower=3, this comes out to a break at every 75 units, which isn't bad given that the size of a typical battlefield is 800 (that is, 11 buckets at most).

Notice that we used buckets of width 79- This means that in order to to work properly our gun must fire directly into the center of each bucket.

==Advanced Refinements==

-Since only at breakpoints are each of the buckets an even 79, it's clear that inbetween these breaks, all the buckets are of a width smaller than 79. This means that by firing directly into the edge buckets (0 and n-1 of our array) we actually are losing some accuracy. More advanced implementations could have the turret fire as close to the center as possible while still covering every point inside the bucket.

-The gun could also just the MEA by adjusting firepower. Since against a good wave surfer, the gun's accuracy will be at worst 1/n where n is the number of buckets, it could very well be worth it to slightly decrease firepower in order to constrict the MEA and stabilize the number of buckets.

-Furthermore, the bot could attempt to position itself at certain ranges that are better defined, rather than fight at ranges where information is sparse.

== Weaknesses ==

When the target is near walls, the shot often goes into the wall unless the [[Maximum Escape Angle/Precise|Precise MEA]] is calculated.

[[Category:Targeting]]

Pyramid Bins

2011-03-25T17:15:12Z

Ceasar: /* Weaknesses */

A form of statistical targeting that combines guess factors, segmentation, and visit count stats.

[[Image:PyramidSegmentation.jpg|right]]

==Idea==

Segmentation typically involves segmenting into a significant number of buckets- it's not uncommon to see 30 buckets or more. However, by scanning the distance to our target, we can actually reduce the number of buckets to only a fraction of what's typically used, based on the maximum escape angle and chord lengths. The result is greatly improved learning speeds and improved accuracy, particularly against wave surfers.

==Implementation==

In order to implement pyramid segmentation, we simply need to make a few calculations to determine how many buckets we'll need at any particular range.
-First, calculate the Maximum Escape Angle.
-Then using the triangle used to calculate the MEA, calculate the length of the side opposite the MEA. Since the triangle is Right, this comes out to be 'distance to target' * tan(MEA). Call this length 'C'.
-Divide 'C' by twice the width of a bot minus one, 36 * 2 - 1 = 71, and take the ceiling of the result. This gives the minimum number of buckets needed to hit the target at that distance.

By pre-calculating which distances lead to a change in the number of buckets, we can very easily implement this into our code. For simple purposes, the breaks are at d=79n/tan(MEA) for all integer n (but this only needs to be calculated up to the size of the battlefield). For Firepower=3, this comes out to a break at every 75 units, which isn't bad given that the size of a typical battlefield is 800 (that is, 11 buckets at most).

Notice that we used buckets of width 79- This means that in order to to work properly our gun must fire directly into the center of each bucket.

==Advanced Refinements==

-Since only at breakpoints are each of the buckets an even 79, it's clear that inbetween these breaks, all the buckets are of a width smaller than 79. This means that by firing directly into the edge buckets (0 and n-1 of our array) we actually are losing some accuracy. More advanced implementations could have the turret fire as close to the center as possible while still covering every point inside the bucket.

-The gun could also just the MEA by adjusting firepower. Since against a good wave surfer, the gun's accuracy will be at worst 1/n where n is the number of buckets, it could very well be worth it to slightly decrease firepower in order to constrict the MEA and stabilize the number of buckets.

-Furthermore, the bot could attempt to position itself at certain ranges that are better defined, rather than fight at ranges where information is sparse.

== Weaknesses ==

When the target is near walls, the shot often goes into the wall unless [[Maximum Escape Angle/Precise|the Precise MEA]] is calculated.

[[Category:Targeting]]

Talk:Pyramid Bins

2011-03-25T17:13:32Z

Ceasar:

If I understood your ideas correctly, this used to be called [[oldwiki:VisitCountStats/Dynamic|VisitCountStats/Dynamic]]. --[[User:Nat|Nat]] [[User talk:Nat|Pavasant]] 07:49, 23 March 2011 (UTC)

If we want to get nitpicky about terminology, this isn't "segmentation" as the term is usually applied here. Segmentation tends to refer to the categorization of the target's current movement by things like velocity/acceleration/etc. I think this is more "Pyramid bins" --[[User:Rednaxela|Rednaxela]] 12:52, 23 March 2011 (UTC)

@Rednaxela, Ah, that makes more sense. Is there a way to rename the page. @Nat, Yeah, looks like I wasn't the first to come up with the idea. (Not that it's complicated, but something I just wanted to post in order to augment the GFTargeting tutorial). --[[User:Ceasar|Ceasar]] 12:52, 23 March 2011 (UTC)

To rename a page, you can use "Move" tab on the left of "History" tab. --[[User:Nat|Nat]] [[User talk:Nat|Pavasant]] 02:55, 24 March 2011 (UTC)

Did you mean "Precise Maximum Escape Angle" instead of "Precise Prediction"? --[[User:Nat|Nat]] [[User talk:Nat|Pavasant]] 06:11, 25 March 2011 (UTC)

Ah, yes. Fixed. --[[User:Ceasar|Ceasar]] 17:13, 25 March 2011 (UTC)

Wave Surfing

2011-03-25T05:00:36Z

Ceasar: /* Strategy */

{{Youtube|dqHmp_kMz-U}}

A form of precise bullet dodging movement used primarily in [[One on One|1v1]]. A [[Waves|Wave]] is a mechanic used to represent all possible locations of a bullet. Through observation of waves and bullets, one can try to project the relative dangers of each area of a wave in the air -- i.e., the likelihood that the enemy fired at various angles. (Note that Robocode bots cannot see bullets in the air.)

== History ==

[[User:ABC|ABC]] was the first to implement true Wave Surfing in a Robocode bot when he added it to [[Shadow]] in mid-2004. As of April, 2010, the top 40 duelists in the [[RoboRumble]] use a form of Wave Surfing.

== How it works ==
* Detect an [[Energy Drop|energy drop]] to know that a bullet was fired. Create a matching Wave.
* Gather data from <code>onHitByBullet</code> or <code>onBulletHitBullet</code>, always matching to the correct Wave, to learn what firing angles the enemy gun uses in different situations.
* For the nearest bullet(s) in the air, use [[Precise Prediction|precise prediction]] to deduce the areas of the wave(s) your bot could reach.
* Try to move to the safest reachable spot on each wave.

== Game Theory Perspective ==

[[Image:PayoffMatrix.jpg|right]]

Ideas from game theory have a clear niche when it comes to wave surfing. Consider for example, if one could determine the number of bins that the opponent is using at the time of firing. Based on that knowledge one could construct a payoff matrix in order to evaluate the best plan of action and consistently determine the best response.

For example, consider the payoff matrix at right. Assume that the target is at such a distance such that the shooter can fire in three unique locations that would hit the target regardless of where the target moves within the maximum escape angle. Then both players must choose from one of three strategies. The target can choose to move left, stay center, or move right. The shooter can choose to fire into the left bin, the center bin, or the right bin. If both the shooter and the target choose the same strategy, the target is hit; else, the shooter misses and loses some energy.

The question becomes, what is the optimal strategy? Clearly, if the target or shooter chooses a pure strategy, that is, always playing the same strategy, then the opponent has two unique best responses that will eventually lead to a win. Therefore, the optimal strategy is not to adopt a pure strategy, and instead opt for a mixed strategy- playing each of the strategies a certain percentage of the time.

In this case, since each strategy is effectively identical, it's clear that there exists only one Nash equilibrium at {(1/3, 1/3, 1/3), (1/3, 1/3, 1/3)}. (A Nash equilibrium is when both players choose a strategy such that neither would benefit by switching to a different strategy.)

== Styles of surfing ==

* [[/True Surfing|True Surfing]] - Decide each tick whether to move forward, backward, or stop. Used by the great majority of Wave Surfers and the [[Wave Surfing Tutorial]].
* [[/GoTo Surfing|GoTo Surfing]] - Calculate the safest spot on the nearest wave(s) and move there directly.
* [[/Melee|Melee Surfing]] - While many have tried their hands at Wave Surfing in [[Melee]], there hasn't been huge success. For now, check out the [[Talk:Wave Surfing/Melee|talk page]].

==See also==
* [[Wave Surfing Tutorial]]
* [[Waves]]
* [[Energy Drop]]
* [[Precise Prediction]]

[[Category:Movement]]

Talk:Wave Surfing

2011-03-25T04:55:02Z

Ceasar: /* The "Strategy" section */

== The Next Level ==

Quite a while ago I had an idea that could bring Wave Surfing to a new level, but I never got around to implementing it. Since the wiki's been quiet the last few days, I thought perhaps something like this might provide a kick to get things rolling again. My idea is Wave Surfing with a twist: not only do you surf the wave(s) that have been fired, but you also take into consideration the waves that have not yet been fired. By predicting your movement, you can predict what the enemy will see, and thus by looking at your movement stats you can see where they are likely to fire. Now, for the interesting part: by varying where you go, not only do you vary what GFs you reach, but you also vary what the enemy sees, and thus where they shoot. Danger can be calculated not only as a low point on a graph, but also on the entropy of the enemy's firing stats when presented with this movement. The more peaked the profile, the better this movement option (provided we can get to a low point). A system like this could basically 'figure out' how to do a movement type like [[Stop And Go]], and probably other amazing types of movement we haven't thought of yet. There! How's that for some food for thought? =) --[[User:Skilgannon|Skilgannon]] 20:23, 9 July 2009 (UTC)

Some interesting thoughts here. I'm initially skeptical (as usual =)) because it reminds me of the diminishing returns on surfing waves beyond the first couple. But ignoring that... One hurdle with this is that while you can predict your own movement, you can't (accurately) predict the enemy's movement, which also impacts what they "see" -- distance, lateral velocity, wall distance, etc. depend on enemy location as well as your own. It's a funny thought to use your gun to predict their movement to assist in your own movement. =)

So let's say you can guesstimate the enemy movement -- and maybe the full range of their movement options are pretty similar for our purposes anyway. So for each of my movement options, I'd figure out if/when the enemy would fire (based on gun heat) during that prediction, check my stats of the enemy's bullets fired / bullets hit, factor in the precise max escape angle of that firing situation, and multiply the probability he would hit into the danger calculation. Kinda similar to how many of us factor in distance (and maybe instead of distance, since these two factors would not be independent). I'm still skeptical, but this sounds really interesting!

Good to see I'm not the only one still pondering the next big thing. =) I still want to find a breakthrough in [[Anti-Surfer Targeting]]... I know it's there!

--[[User:Voidious|Voidious]] 20:52, 9 July 2009 (UTC)

: Gaff's anti-surfer score in the [[TC2K7]] isn't enough? I have a dev. version that scores 82.93 against surfers (15 seasons) but worse overall once the random movers are averaged in. If you create a new [[Anti-Surfing Challenge]] I'll be happy to keep looking for improvements. =) --[[User:Darkcanuck|Darkcanuck]] 21:49, 9 July 2009 (UTC)

: Hmm, those are some pretty sick scores. Besides the scores themselves, it's particularly impressive that you nail [[Shadow]] ''and'' [[RaikoMX]] so well with one gun. I'm guessing not by the description, but do you simulate enemy surf stats in any way? That's the main area where I think a breakthrough might await, but even my best efforts haven't yielded much. That Anti-Surfing Challenge sounds pretty appealing, actually, even if it will do squat in closing the gap to [[DrussGT]]. =) --[[User:Voidious|Voidious]] 00:34, 10 July 2009 (UTC)

:: Thanks, I'm very pleased with that gun. There's no simulation involved, besides a rough calculation of the min + max reachable GFs -- the rest is all NN magic. I promise to write it up one of these days, I'd like to see what tangents others might take. --[[User:Darkcanuck|Darkcanuck]] 03:58, 10 July 2009 (UTC)

:: I was once tried simulating the surfer stats, but the result with normal bin smoother will have a load of empty bins that have no data. So you can't really decide where to fire unless, of course, you are simulating a surfer movement too. But next generation Go-To surfer can kill that instantly. Note the next generation go-to surfer is not this next generation wave surfer, it will be like when you may chose a point that close to you, and stay still until the last moment and move to that spot in time when the wave reach or something more that that.
:: We can have anti-surfer challenge in Challenge 2K9, I think we should have one. I'll continue working on Challenge 2K9 when I have time (October, when the school holiday arrive.) » [[User:Nat|Nat]] | [[User_talk:Nat|Talk]] » 05:15, 10 July 2009 (UTC)

:: Yep, you probably shouldn't use ''only'' enemy surf data to shoot at. But there's important data there that I really think can be factored into the gun. I'd definitely account for what GFs they can still reach on each wave (ie, the "simulate their movement" part). I don't think an Anti-Surfer Challenge needs to be a subchallenge of another challenge, since most of our movement and targeting challenges aim to gauge rumble performance, while this one clearly would not. --[[User:Voidious|Voidious]] 13:44, 10 July 2009 (UTC)

::: If you look closely, the Challenge 2K9 is main challenge plus a bunch of subchallenges. I think most Anti Surfer gun indirectly simulating enemy surf stats already. Since we usually reduce twice on hit, it would result like the simulated enemy surfing stats plus normal stats to decide where to shot in a load of empty bins. However, we can assume that the enemy will not changes its direction until one wave passed over. Then we may assume which direction the enemy will go next, etc. » [[User:Nat|Nat]] | [[User_talk:Nat|Talk]] » 14:47, 10 July 2009 (UTC)

Fiddlesticks, this was going to be my killer idea once I made a wavesurfing bot!...Creating misleading spikes--[[User:CrazyBassoonist|CrazyBassoonist]] 21:10, 9 July 2009 (UTC)

Approaching this from a slightly different direction, you could "snap" your movement to certain points when you know they're about to fire, essentially reducing the resolution of their segmentation. In a single turn you can do that with velocity, snapping it to 8, 5, 2, 0, -2, -5, or -8. In two turns you can also keep acceleration constantly at 0. With a few more turns' warning you could limit velocity to even fewer values. This would be easiest against bots that fire slow, infrequent shots since your movement would be disrupted less often. -- [[User:Synapse|Synapse]] 23:29, 9 July 2009 (UTC)

Interesting... for a simple movement (stop&go, flat, singlebuffer flattenerless wavesurf), it is possible to predict a reasonable accurate location in future. Thus it needs a lot of processing so I don't sure if it will run in time. But it may make up to 100 rounds to learn how they move. I never tried (but I'm writing a library that do this in past 2 months. It's call BattlePredictor, originally I will use it for melee)

One thing that should be consider when creating a wave surfing robot that use this generation, it should be totally useless against a simple gun and probably loss score (I'm highly doubt that using this may lead to another performance enhancing bug). » [[User:Nat|Nat]] | [[User_talk:Nat|Talk]] » 01:28, 10 July 2009 (UTC)

I think you guys might have gone off on a tangent here... I don't think Skilgannon's idea really involves "creating misleading spikes" so much as factoring in which movement profile will be presented to the enemy and trying to choose an advantageous one. A best guess at the enemy's movement would be simple and might work well enough in most situations, so it need not be slow. It would be augmenting normal surfing instead of replacing it, so you shouldn't lose score against anyone. I like the idea of snapping velocity, Synapse; I think you might gain performance against simple learning guns but lose performance against bigger guns (which have fancier segments / attributes that could "see through" the trick). --[[User:Voidious|Voidious]] 13:44, 10 July 2009 (UTC)

Still if we augment it, not replace, the augmented result can make you drive into danger with some type of gun. I don't know that it will happen, but I highly doubt (with some hunch though) that this will not improved the score. But it doesn't mean that I'll not tried to do it. Synapse, if you limit the acceleration to zero, wouldn't it just goes back and forth? I know that velocity is the most popular segment, if distance isn't. But I don't think there is many guns that use ''n'' ticks acceleration (I know there is some bot use distance in last few/several turns). » [[User:Nat|Nat]] | [[User_talk:Nat|Talk]] » 14:47, 10 July 2009 (UTC)

Nat, the velocity and acceleration limitations would only be applied for two turns starting immediately before gunheat zero, so the enemy is forced to put all his battle data into a small number of segmentations. -- [[User:Synapse|Synapse]] 16:19, 10 July 2009 (UTC)

The reason I think this might be a big improvement over regular surfing is against the simple targeters: before we were just acting reactively, responding to the enemy bullets in the air, whereas now we could act pro-actively, by actually forcing bots to shoot where we want them to. This would eliminate all the 'lucky shots' that are the usual cause of being hit, due to not having enough room to manoeuvre (from walls) or being too close to dodge. Against other surfers, this bot could have a large advantage if it stayed at close distances, where it can still predict enemy shots a large number of ticks ahead, but the enemy would only have distance/bulletVelocity ticks to work with. Then there's the false spikes that were mentioned: I don't think these are really feasable, as the only way to make them is to create real spikes, and the more predictable stuff you do, the worse =) --[[User:Skilgannon|Skilgannon]] 16:15, 10 July 2009 (UTC)

''Some questions moved to [[User_talk:Starrynte#Wave_Surfing_Questions]]''

For me, there is no 'panacea' that is technically possible. I'd like to be able to get a copy of the enemy classes and just simulate what they'll do from there. If not, then have some algorithm which adapts to act exactly the same as them. Unfortunately, the first is against robocode rules, and the second is essentially a perfect DC movement/gun, which defeats the entire point of statistics, which is that there will be some situations where your rules are wrong. As such, I settle for statistics as a 'next best' option.
I've often thought that during the first 1 or 2 rounds against a learning bot the flattener should be enabled. However, it usually takes 1 or 2 rounds to determine whether the enemy is learning or not, so that is a bit of a moot point. Maybe assume some common ones, like HOT linear and circular, and from there just say 'if any bullet arrives which is not one of these, enable the flattener'. The trouble for me with this is that you are then specializing your bot against this specific rumble set, and not all bots which could be written, in general. --[[User:Skilgannon|Skilgannon]] 08:13, 18 May 2010 (UTC)

Ah, hmm. I think there is at least one large leap left in surfing stats. Our current surfers generally "learn what the enemy gun has learned" instead of "learning how the enemy gun learns". Against most learning guns, where a typical flattener will hurt your score, I still think there is a safe way to predict/dodge firing angles that you've never been hit at before... --[[User:Voidious|Voidious]] 12:42, 18 May 2010 (UTC)

Well, "learning how the enemy gun learns" is essentially what a pure flattener does, when facing a GF-based gun. The only times it wouldn't be advantageous could be: 1) Extremely different 'categorization' of the situation (i.e. Pattern matching, or rather esoteric segmentation), or 2) Different prediction mechanism (i.e. PIF). Now, I don't think #2 makes a huge difference to the mostly-orbital surfer, so the key lies in #1. My current dream of what would be good, would be having a "bank" of different flatterers, which categorize the situation in highly different ways (not just subtle segmentation changes), and then whenever the bot does get hit, see which flatterers expected that spot to be dangerous and rate them higher. Really, the enemy firing predictors in this group don't have to be 'flatteners' strictly speaking. Just make them a set of "enemy gun simulators" really and include the non-learning ones in the same infrastructure, perhaps include the traditional 'surfer' learning in the set as well, and let the best predictor of actual danger win. The idea is, rather than learn from what the enemy gun has done before, try to match it up with a "likely approximately correct hypotheses". Given how targeting has a 1-dimensional result, and the amount of solid data is sparse for normal surfing, I think picking the best matching predictor out of a set is reasonable. Note, I don't mean the predictor with the 'profile' matching the surfing data the closest, that wouldn't be accurate because the enemy fires at the spot they thing is most likely, not with a distribution matching the curve they see. I mean seeing which one(s) best predicted the hits/misses --[[User:Rednaxela|Rednaxela]] 14:04, 18 May 2010 (UTC)

: Well, I kinda remember I said this sometime ago and you object that movement doesn't have enough data to learn like this... See some old pages for BlackHole v2 (which mostly abandoned) it have something like this, only not this explicit. --[[User:Nat|Nat]] [[User talk:Nat|Pavasant]] 16:19, 18 May 2010 (UTC)

When I said "learning how the enemy gun learns", I didn't just mean to learn like a gun. I mean to actually learn what their learning method is and what attributes they are keying off of. So a modern flattener doesn't do that - it assumes they're learning a certain way and simulates it. I agree you might have different classes of flatteners/simulators. And yeah, there just isn't enough bullet hit data for us to get much smarter with projecting dangers from them alone. Ok, I was going to keep this close to my chest in case it works out, but here's some of my current ideas:
* Log virtual waves along with real waves. (The enemy is learning a lot from virtual waves and most of us don't even log them...)
* When you get hit, you know the firing angle they used. You can convert this to a GuessFactor. There are tiny discrepancies involving which tick's abs bearing they used, or if their gun finished turning, or some MiniBots hard-code the MEA, but not a whole lot of permutations. Abs bearing from fireTime - 1, position from fire time, and MEA = Math.asin(8/bullet speed) covers a ton of bots.
** I bet we could even pretty easily figure out how many bins they use.
** And if their GFs don't align with evenly spaced bins, maybe that's a sign it's DC or PIF.
* Look up all previous situations where you visited this GF.
* Compare this firing situation to the previous ones and try to figure out what they have in common. Ideally, a handful of attributes look very similar.
* Customize a flattener and start flattening. You can keep tuning it on the fly.
Now, if you are consistently hit with unlikely GFs or ones you've never visited, they're not using GFs. Maybe you can figure out they're doing PM and try APM. If you start with "regular" surfing, you can just disable all this magic until 3rd round and their hit rate passes 3% - we already dodge simple targeters well enough. We should probably move this discussion to [[Talk:Wave_Surfing#The_Next_Level]] or something... --[[User:Voidious|Voidious]] 14:54, 18 May 2010 (UTC)

: Began tinkering with "which attributes is he using" yesterday and realized some things. The main issue is that finding that an attribute is similar doesn't necessarily mean the enemy is using it to aim, it just means he ''should be''. =) If I analyze visits and bullet hits separately, the same attributes are most similar in both. If I compare them, that might be something, but the ratios all come out very close to even. I think the fact that I'm surfing these attributes (or similar ones) means I will not leave really big traces to one attribute across the many times I've visited a certain GF, no matter how the enemy is aiming. --[[User:Voidious|Voidious]] 02:14, 20 May 2010 (UTC)

: I also thought through it. In my mind it would more be an adaptive weighting system. I think the trouble you are encountering is in your "compare this firing situation to the previous one and try to figure out what they have in common". My idea is that the algorithm would be something like: 1) extract N (N = large) scans that are near to our current scan in certain dimensions we're fairly sure they're using (eg latvel, accel, distance) 2) take K previous scans from this cluster with the nearest GF to the current bullet we know about 3) look for any dimensions that on average have a low distance from our current bullet 4) set the weighting to be such that this cluster would be chosen (more or less) ie. dimensions with low distance have high weight, and vice versa. Your thoughts? --[[User:Skilgannon|Skilgannon]] 10:01, 20 May 2010 (UTC)

: Yeah, dynamic weighting is another possible application, I'm just not convinced there are many points there. I suppose my goal could be framed as dynamic weighting of the flattener dimensions, at least as a starting point. Using common dimensions to narrow down the search is an interesting thought, but I think we'd still find lots of similar dimensions even if the enemy isn't using them. But I will try some more experiments soon. (So far I'm just printing data against bots and comparing to actual segmentation.)
: Normalization is a big issue here, too, since different attributes have different distributions. Right now I'm using sqrt(average squared difference) of each dimension, then dividing by the standard deviation of that dimension. --[[User:Voidious|Voidious]] 16:33, 20 May 2010 (UTC)

I think I remember Skilgannon said that if we are precise enough, we should be able to hide between bins of like 21-bins GF gun.

I don't think that the it can be precise enough to check for bins. A lot of Robot doesn't wait for their gun to align before fire; this along with high numbered bins (I think Doki's 59 bins is high enough) should be impossible to precisely detect this. But the method of detecting enemy's segmenting attribute is interesting. But they could look similar by coincidence, especially robots that use huge buffers (Doki, Phoenix, etc.) or weight buffers (WaveSerpent, etc.) But really, the gun alignment could thrown this off easily. Sometimes the unaligned gun do better, because the 'unexpected' shot(s) will give noise in enemy's stats.

It may be just me, but I really think that optimize for vast majority of the RoboRumble doesn't seems right. I mean, yes it will boost your score, but, well, you should be able to... err... I don't know... It's confusing in me right now (well, I ''am'' confused and stressed right now, given the state of my country...) --[[User:Nat|Nat]] [[User talk:Nat|Pavasant]] 16:19, 18 May 2010 (UTC)

: Optimizing for the rumble population generally strikes me as "not truly intelligent", but at the same time, "there are only so many ways to skin a cat." I find it likely that any group of Robocoders would arrive at pattern matching, bearing offsets, and something resembling GuessFactors and PIF. So I don't feel like detecting those styles and special casing them is necessarily only specializing for the rumble. --[[User:Voidious|Voidious]] 17:12, 18 May 2010 (UTC)

== The "Strategy" section ==

Interesting section [[User:Ceasar|Ceasar]]. Mind if I rename it so something more like "A Game Theory Perspective on Wavesurfing"? I say that because that seems to be more what it is, plus I wouldn't say wave surfing inherently "employs ideas from game theory". Perhaps more like "ideas from game theory can be applied to wave surfing"?

Now that I've gotten what bothers me about section out... I really thing it's interesting to see this looked at from a game theory perspective. The general concepts here have been explored a fair bit in terms of how one tries to "flatten" a [[Movement Profile|movement profile]], and the "arms race" of both movement and targeting exploiting the uneven probabilities of eachother. If there were only wave at a time, then the ultimate "nash equilibrium" from the movement side, would simply be a movement that chose a uniform random value for the guessfactor to get to after calculating the range it can achieve. The ultimate "nash equilibrium" gun would be the same, in terms of having an equal chance of aiming anywhere where the opponent could go. Though it was never referred to in game theory terms, it was well known.

The reality is more complicated though, even for the simplified case of the nash equilibrium. In reality there is most often multiple waves in flight at any one time, and if you respond uniformly to the nearest wave, your movement profile will quickly start to approximate a gaussian distribution as the number of waves increases. This is due to movement choices in one wave limiting the movement choices in the next wave. Clearly, this has a movement weakness in that there will start to be an angles that are significantly better to aim at than others. Perhaps an interesting area to explore would be the game theory of the multiple-wave-at-a-time case? It seems to me that would be a trickier puzzle and likely vary significantly depending on more specifics of the situation. I'm rather sure that the 'ideal' route to maximize flatness of movement profile in the long run, would have to rely on past history of movement, and thus will end with short-term weaknesses, so I don't think simply optimizing for long-term movement profile flatness would quite be the nash equilibrium. So if optimizing for long-term flatness is not the equilibrium, and neither is picking a random angle each wave, then I suspect the true nash equilibrium would be somewhere inbetween.

This also reminds me of some anecdotal observations, such as how it's generally been found that even against strong targeting, it's rarely best to use solely use a flattener.

--[[User:Rednaxela|Rednaxela]] 03:42, 25 March 2011 (UTC)

Ah, that's all extremely interesting! To begin, don't hesitate to edit my edits- that's the whole point of a wiki of course! I'm just trying to put the ideas I have out there and hope to get some insight from the veterans in the process (as in, this :P).

Going onwards, very interesting to hear that game theory hadn't been tossed around before. Seems like a very natural fit, particularly given the use of bins. I suppose given that, I'll try to flesh out the ideas with some more pages on game theory ideas, and specifically as they apply to Robocode. Also, it somewhat sucks to hear that my theories are wrong and that I haven't solved Robocode. :P (I'm building a gun to do exactly what you describe there, haha.) More hope for my [[Targeting Matrix]] idea then!

But yeah, very interesting. I'll have to look into exploring what game theory has to suggest about multiple waves firing. My intuition is that it shouldn't really matter too much (that is, assuming a fair bit of simplification- really each wave ought to be more or less independent given the cooldown provided the distance is long enough) but given the mere existence of walls, it's clear things are never so simple.

Anyway, thanks for the thoughts. That gives me something new to really think about.

--[[User:Ceasar|Ceasar]] 04:55, 25 March 2011 (UTC)

Pyramid Bins

2011-03-24T19:43:58Z

Ceasar: /* Weaknesses */

A form of statistical targeting that combines guess factors, segmentation, and visit count stats.

[[Image:PyramidSegmentation.jpg|right]]

==Idea==

Segmentation typically involves segmenting into a significant number of buckets- it's not uncommon to see 30 buckets or more. However, by scanning the distance to our target, we can actually reduce the number of buckets to only a fraction of what's typically used, based on the maximum escape angle and chord lengths. The result is greatly improved learning speeds and improved accuracy, particularly against wave surfers.

==Implementation==

In order to implement pyramid segmentation, we simply need to make a few calculations to determine how many buckets we'll need at any particular range.
-First, calculate the Maximum Escape Angle.
-Then using the triangle used to calculate the MEA, calculate the length of the side opposite the MEA. Since the triangle is Right, this comes out to be 'distance to target' * tan(MEA). Call this length 'C'.
-Divide 'C' by twice the width of a bot minus one, 36 * 2 - 1 = 71, and take the ceiling of the result. This gives the minimum number of buckets needed to hit the target at that distance.

By pre-calculating which distances lead to a change in the number of buckets, we can very easily implement this into our code. For simple purposes, the breaks are at d=79n/tan(MEA) for all integer n (but this only needs to be calculated up to the size of the battlefield). For Firepower=3, this comes out to a break at every 75 units, which isn't bad given that the size of a typical battlefield is 800 (that is, 11 buckets at most).

Notice that we used buckets of width 79- This means that in order to to work properly our gun must fire directly into the center of each bucket.

==Advanced Refinements==

-Since only at breakpoints are each of the buckets an even 79, it's clear that inbetween these breaks, all the buckets are of a width smaller than 79. This means that by firing directly into the edge buckets (0 and n-1 of our array) we actually are losing some accuracy. More advanced implementations could have the turret fire as close to the center as possible while still covering every point inside the bucket.

-The gun could also just the MEA by adjusting firepower. Since against a good wave surfer, the gun's accuracy will be at worst 1/n where n is the number of buckets, it could very well be worth it to slightly decrease firepower in order to constrict the MEA and stabilize the number of buckets.

-Furthermore, the bot could attempt to position itself at certain ranges that are better defined, rather than fight at ranges where information is sparse.

== Weaknesses ==

When the target is near walls, the shot often goes into the wall unless [[Precise Prediction]] is used.

[[Category:Targeting]]

Pyramid Bins

2011-03-24T19:43:41Z

Ceasar:

A form of statistical targeting that combines guess factors, segmentation, and visit count stats.

[[Image:PyramidSegmentation.jpg|right]]

==Idea==

Segmentation typically involves segmenting into a significant number of buckets- it's not uncommon to see 30 buckets or more. However, by scanning the distance to our target, we can actually reduce the number of buckets to only a fraction of what's typically used, based on the maximum escape angle and chord lengths. The result is greatly improved learning speeds and improved accuracy, particularly against wave surfers.

==Implementation==

In order to implement pyramid segmentation, we simply need to make a few calculations to determine how many buckets we'll need at any particular range.
-First, calculate the Maximum Escape Angle.
-Then using the triangle used to calculate the MEA, calculate the length of the side opposite the MEA. Since the triangle is Right, this comes out to be 'distance to target' * tan(MEA). Call this length 'C'.
-Divide 'C' by twice the width of a bot minus one, 36 * 2 - 1 = 71, and take the ceiling of the result. This gives the minimum number of buckets needed to hit the target at that distance.

By pre-calculating which distances lead to a change in the number of buckets, we can very easily implement this into our code. For simple purposes, the breaks are at d=79n/tan(MEA) for all integer n (but this only needs to be calculated up to the size of the battlefield). For Firepower=3, this comes out to a break at every 75 units, which isn't bad given that the size of a typical battlefield is 800 (that is, 11 buckets at most).

Notice that we used buckets of width 79- This means that in order to to work properly our gun must fire directly into the center of each bucket.

==Advanced Refinements==

-Since only at breakpoints are each of the buckets an even 79, it's clear that inbetween these breaks, all the buckets are of a width smaller than 79. This means that by firing directly into the edge buckets (0 and n-1 of our array) we actually are losing some accuracy. More advanced implementations could have the turret fire as close to the center as possible while still covering every point inside the bucket.

-The gun could also just the MEA by adjusting firepower. Since against a good wave surfer, the gun's accuracy will be at worst 1/n where n is the number of buckets, it could very well be worth it to slightly decrease firepower in order to constrict the MEA and stabilize the number of buckets.

-Furthermore, the bot could attempt to position itself at certain ranges that are better defined, rather than fight at ranges where information is sparse.

== Weaknesses ==

When the target is near walls, the shot often goes into the wall unless [Precise Prediction] is used.

[[Category:Targeting]]

Wave Surfing

2011-03-24T18:11:52Z

Ceasar: Added a note on game theory

{{Youtube|dqHmp_kMz-U}}

A form of precise bullet dodging movement used primarily in [[One on One|1v1]]. A [[Waves|Wave]] is a mechanic used to represent all possible locations of a bullet. Through observation of waves and bullets, one can try to project the relative dangers of each area of a wave in the air -- i.e., the likelihood that the enemy fired at various angles. (Note that Robocode bots cannot see bullets in the air.)

== History ==

[[User:ABC|ABC]] was the first to implement true Wave Surfing in a Robocode bot when he added it to [[Shadow]] in mid-2004. As of April, 2010, the top 40 duelists in the [[RoboRumble]] use a form of Wave Surfing.

== How it works ==
* Detect an [[Energy Drop|energy drop]] to know that a bullet was fired. Create a matching Wave.
* Gather data from <code>onHitByBullet</code> or <code>onBulletHitBullet</code>, always matching to the correct Wave, to learn what firing angles the enemy gun uses in different situations.
* For the nearest bullet(s) in the air, use [[Precise Prediction|precise prediction]] to deduce the areas of the wave(s) your bot could reach.
* Try to move to the safest reachable spot on each wave.

== Strategy ==

[[Image:PayoffMatrix.jpg|right]]

Wave surfing employs ideas from game theory in order to dodge bullets most effective. Consider for example, that one could determine the number of bins that the opponent is using at the time of firing. Based on that knowledge one could construct a payoff matrix in order to evaluate the best plan of action and determine the best response.

For example, consider the payoff matrix at right. Assume that the target is at such a distance such that the shooter can fire in three unique locations that would hit all points that the target can move to. Then both players must choose from one of three strategies. The target can choose to move left, stay center, or move right. The shooter can choose to first in the left bin, the center bin, or the right bin. If both the shooter and the target choose the same strategy, the target is hit; else, the shooter misses and loses some energy.

The question becomes, what is the optimal strategy? Clearly, if the target or shooter choose a pure strategy, that is, always playing the same strategy, then the best the opponent has two unique best responses that will eventually lead to a win. Therefore, the optimal strategy will be a mixed strategy, playing each a certain percentage of the time.

In this case, since each strategy is effectively identical, it's clear that there exists only one Nash equilibrium at {(1/3, 1/3, 1/3), (1/3, 1/3, 1/3)}. (A Nash equilibrium is when both players choose a strategy such that neither would benefit by switching to a different strategy.)

== Styles of surfing ==

* [[/True Surfing|True Surfing]] - Decide each tick whether to move forward, backward, or stop. Used by the great majority of Wave Surfers and the [[Wave Surfing Tutorial]].
* [[/GoTo Surfing|GoTo Surfing]] - Calculate the safest spot on the nearest wave(s) and move there directly.
* [[/Melee|Melee Surfing]] - While many have tried their hands at Wave Surfing in [[Melee]], there hasn't been huge success. For now, check out the [[Talk:Wave Surfing/Melee|talk page]].

==See also==
* [[Wave Surfing Tutorial]]
* [[Waves]]
* [[Energy Drop]]
* [[Precise Prediction]]

[[Category:Movement]]

File:PayoffMatrix.jpg

2011-03-24T17:59:41Z

Ceasar: An example payoff matrix.

An example payoff matrix.

User talk:Ceasar

2011-03-24T16:26:14Z

Ceasar:

{| width="100%" style="background: white; "
| valign="top" width="60%" style="border: 2px solid #000; padding: .5em 1em; -moz-border-radius: 1em; -webkit-border-radius: 1em; border-radius: 1em" |
'''Welcome!'''

Hello, Ceasar, and welcome to [[RoboWiki]]! This place contains a wealth information about [[Robocode]], from [[Head-On Targeting|basic]] to [[Wave Surfing|more advanced]]. I hope you enjoy creating robots and being a robocoder!

If you are posting a comment on this wiki, please [[wikipedia:Wikipedia:Signatures|sign]] your messages using four tildes (<nowiki>--~~~~</nowiki>); this will automatically insert your username and the date stamp. If you are not familiar with MediaWiki, these links might help you out:
* [[wikipedia:How to edit|How to edit]] on [[wikipedia:|Wikipedia]], [[metawikipedia:Cheatsheet|Cheatsheet]] and [[metawikipedia:File:MediaWikiRefCard.pdf|Reference Card]] of MediaWiki on the [[metawikipedia:|Meta Wikipedia]].
* [[RoboWiki:ReadMe|Readme]] page.
If you need [[Help:Help|help]], check out the [[Robocode/FAQ|frequently asked questions]] or ask it on this page. Again, welcome!

—— [[User:Voidious|Voidious]] 02:10, 23 March 2011 (UTC)
|}

Welcome to the wiki! Nice to see you diving right in with making pages and discussing some theory. =) Best of luck with your bots. --[[User:Voidious|Voidious]] 02:10, 23 March 2011 (UTC)

Hey Voidious. Yeah, I'm actually pretty passionate about writing things down (I blog, and I'm a huge proponent of sharing knowledge), and a wiki where I can actually share stuff is pretty cool. I'm just curious, has Robocode kind of lost its community? The wiki simply lacking in a lot of parts, which, understandably there was an old one which everything would have to migrated from, but I imagine it would be a bit more dense if the community was still alive and kicking. [[User:Ceasar|Ceasar]] 12:26, 24 March 2011 (EST)

Targeting Matrix

2011-03-24T16:14:09Z

Ceasar: /* Example */

Targeting Matrix

2011-03-24T16:02:17Z

Ceasar:

A technique employing knowledge at the intersection of linear algebra and statistics.

== Idea ==

Using projections, as described in linear algebra, it's possible to map an n-dimensional matrix, A, to a vector, b, via a third vector, x, such that Ax=b.

== Example ==

Consider we wanted to simply devise a matrix that would map distance to a firing angle. In order to do this, we might create an 3-dimensional matrix, with values [x^2, x, 1] for every x that we record, where x is the distance to our target at the time of firing, and a second vector, [y] where y is the correct firing angle. After acquiring three data points, we'll be able to arrange our vectors in the form Ax=b, as such:

<code>A = [[a^2, a, 1], [b^2, b, 1], [c^2, c, 1]]

x = [unknown1, unknown2, unknown3]

b = [[angle_a], [angle_b], [angle_c]]</code>

Now we wish to solve for x. To do this, we project A onto b. Therefore, we first multiply both sides of the equation by <math>A^T</math> to get:

<math>A^T * A * x = A^T * b</math>

And then multiply by the inverse of <math>(A^T * A)</math> to reach <math>x = (A^T * A)^{-1} * A^T * b</math>. We now can compute x.

Since we have <math>x</math>, we can now accurately map distances to targets to firing angles, via simply inputing distance into the function:

<math>f(x) = unknown_1 * x^2 + unknown_2 * x + unknown_3 * 1 = angle</math>

Notice that we used <math>(A^T * A)^{-1} * A^T</math> (called the projection matrix, P) rather than simply <math>A^{-1}</math>. This is because by using the projection matrix we can actually compute <math>x</math> for any number of tuples. This is extremely useful since the alternative is to use a polynomial of dimension <math>n</math> to fit a line through all of the <math>n</math> data points.

This idea is also extremely powerful because it allows us to easily factor more in variables by simply increasing the dimension of A. For example, if we also wanted to track target velocity, we would simply append a vector to A, such that:

<code>A = [[v, a^2, a, 1], [v, b^2, b, 1], [v, c^2, c, 1]]</code>

where v is the target velocity. (x in this case would also need another element).

[[Category:Targeting]]

Targeting Matrix

2011-03-24T16:01:53Z

Ceasar:

A technique employing knowledge at the intersection of linear algebra and statistics.

== Idea ==

Using projections, as described in linear algebra, it's possible to map an n-dimensional matrix, A, to a vector, b, via a third vector, x, such that Ax=b.

== Example ==

Consider we wanted to simply devise a matrix that would map distance to a firing angle. In order to do this, we might create an 3-dimensional matrix, with values [x^2, x, 1] for every x that we record, where x is the distance to our target at the time of firing, and a second vector, [y] where y is the correct firing angle. After acquiring three data points, we'll be able to arrange our vectors in the form Ax=b, as such:

<code>A = [[a^2, a, 1], [b^2, b, 1], [c^2, c, 1]]

x = [unknown1, unknown2, unknown3]

b = [[angle_a], [angle_b], [angle_c]]</code>

Now we wish to solve for x. To do this, we project A onto b. Therefore, we first multiply both sides of the equation by <math>A^T</math> to get:

<math>A^T * A * x = A^T * b</math>

And then multiply by the inverse of <math>(A^T * A)</math> to reach <math>x = (A^T * A)^{-1} * A^T * b</math>. We now can compute x.

Since we have <math>x</math>, we can now accurately map distances to targets to firing angles, via simply inputing distance into the function:

<math>f(x) = unknown_1 * x^2 + unknown_2 * x + unknown_3 * 1 = angle</math>

Notice that we used <math>(A^T * A)^{-1} * A^T</math> (called the projection matrix, P) rather than simply <math>A^{-1}</math>. This is because by using the projection matrix we can actually compute <math>x</math> for any number of tuples. This is extremely useful since the alternative is to use a polynomial of dimension <math>n</math> to fit a line through each <math>n</math> data points.

This idea is also extremely powerful because it allows us to easily factor more in variables by simply increasing the dimension of A. For example, if we also wanted to track target velocity, we would simply append a vector to A, such that:

<code>A = [[v, a^2, a, 1], [v, b^2, b, 1], [v, c^2, c, 1]]</code>

where v is the target velocity. (x in this case would also need another element).

[[Category:Targeting]]

Targeting Matrix

2011-03-24T16:00:48Z

Ceasar:

A technique employing knowledge at the intersection of linear algebra and statistics.

== Idea ==

Using projections, as described in linear algebra, it's possible to map an n-dimensional matrix, A, to a vector, b, via a third vector, x, such that Ax=b.

== Example ==

Consider we wanted to simply devise a matrix that would map distance to a firing angle. In order to do this, we might create an 3-dimensional matrix, with values [x^2, x, 1] for every x that we record, where x is the distance to our target at the time of firing, and a second vector, [y] where y is the correct firing angle. After acquiring three data points, we'll be able to arrange our vectors in the form Ax=b, as such:

<code>A = [[a^2, a, 1], [b^2, b, 1], [c^2, c, 1]]

x = [unknown1, unknown2, unknown3]

b = [[angle_a], [angle_b], [angle_c]]</code>

Now we wish to solve for x. To do this, we project A onto b. Therefore, we first multiply both sides of the equation by <math>A^T</math> to get:

<math>A^T * A * x = A^T * b</math>

And then multiply by the inverse of <math>(A^T * A)</math> to reach <math>x = (A^T * A)^{-1} * A^T * b</math>. We now can compute x.

Since we have <math>x</math>, we can now accurately map distances to targets to firing angles, via simply inputing distance into the function:

<math>f(x) = unknown_1 * x^2 + unknown_2 * x + unknown_3 * 1 = angle</math>

Notice that we used <math>(A^T * A)^{-1} * A^T</math> (called the projection matrix, P) rather than simply <math>A^{-1}</math>. This is because by using the projection matrix we can actually compute <math>x</math> for any number of tuples. This is extremely useful, because if this was not possible, then we could have to use a polynomial of dimension <math>n</math> to fit a line through <math>n</math> tuples.

This idea is also extremely powerful because it allows us to easily factor more in variables by simply increasing the dimension of A. For example, if we also wanted to track target velocity, we would simply append a vector to A, such that:

<code>A = [[v, a^2, a, 1], [v, b^2, b, 1], [v, c^2, c, 1]]</code>

where v is the target velocity. (x in this case would also need another element).

[[Category:Targeting]]

Targeting Matrix

2011-03-24T15:59:49Z

Ceasar:

A technique employing knowledge at the intersection of linear algebra and statistics.

== Idea ==

Using projections, as described in linear algebra, it's possible to map an n-dimensional matrix, A, to a vector, b, via a third vector, x, such that Ax=b.

== Example ==

Consider we wanted to simply devise a matrix that would map distance to a firing angle. In order to do this, we might create an 3-dimensional matrix, with values [x^2, x, 1] for every x that we record, where x is the distance to our target at the time of firing, and a second vector, [y] where y is the correct firing angle. After acquiring three data points, we'll be able to arrange our vectors in the form Ax=b, as such:

<code>A = [[a^2, a, 1], [b^2, b, 1], [c^2, c, 1]]

x = [unknown1, unknown2, unknown3]

b = [[angle_a], [angle_b], [angle_c]]</code>

Now we wish to solve for x. To do this, we project A onto b. Therefore, we first multiply both sides of the equation by <math>A^T</math> to get:

<math>A^T * A * x = A^T * b</math>

And then multiply by the inverse of <math>(A^T * A)</math> to reach <math>x = (A^T * A)^-1 * A^T * b</math>. We now can compute x.

Since we have <math>x</math>, we can now accurately map distances to targets to firing angles, via simply inputing distance into the function:

<math>f(x) = unknown_1 * x^2 + unknown_2 * x + unknown_3 * 1 = angle</math>

Notice that we used <math>(A^T * A)^-1 * A^T</math> (called the projection matrix, P) rather than simply <math>A^-1</math>. This is because by using the projection matrix we can actually compute <math>x</math> for any number of tuples. This is extremely useful, because if this was not possible, then we could have to use a polynomial of dimension <math>n</math> to fit a line through <math>n</math> tuples.

This idea is also extremely powerful because it allows us to easily factor more in variables by simply increasing the dimension of A. For example, if we also wanted to track target velocity, we would simply append a vector to A, such that:

<code>A = [[v, a^2, a, 1], [v, b^2, b, 1], [v, c^2, c, 1]]</code>

where v is the target velocity. (x in this case would also need another element).

[[Category:Targeting]]

Targeting Matrix

2011-03-24T15:59:15Z

Ceasar:

A technique employing knowledge at the intersection of linear algebra and statistics.

== Idea ==

Using projections, as described in linear algebra, it's possible to map an n-dimensional matrix, A, to a vector, b, via a third vector, x, such that Ax=b.

== Example ==

Consider we wanted to simply devise a matrix that would map distance to a firing angle. In order to do this, we might create an 3-dimensional matrix, with values [x^2, x, 1] for every x that we record, where x is the distance to our target at the time of firing, and a second vector, [y] where y is the correct firing angle. After acquiring three data points, we'll be able to arrange our vectors in the form Ax=b, as such:

<code>A = [[a^2, a, 1], [b^2, b, 1], [c^2, c, 1]]

x = [unknown1, unknown2, unknown3]

b = [[angle_a], [angle_b], [angle_c]]</code>

Now we wish to solve for x. To do this, we project A onto b. Therefore, we first multiply both sides of the equation by <math>A^T</math> to get:

<math>A^T * A * x = A^T * b</math>

And then multiply by the inverse of <math>(A^T * A)</math> to reach <math>x = (A^T * A)^-1 * A^T * b</math>. We now can compute x.

Since we have <math>x</math>, we can now accurately map distances to targets to firing angles, via simply inputing distance into the function:

<math>f(x) = unknown_1 * x^2 + unknown_2 * x + unknown_3 * 1 = angle</math>

Notice that we used <math>(A^T * A)^-1 * A^T</math> (called the projection matrix, P) rather than simply <math>A^-1</math>. This is because by using the projection matrix we can actually compute <math>x</math> for any number of tuples. This is extremely useful, because if this was not possible, then we could have to use a polynomial of dimension <math>n</math> to fit a line through <math>n</math> tuples.

This idea is also extremely powerful because it allows us to easily factor more in variable by simply increasing the dimension of A. For example, if we also wanted to track target velocity, we would simply append a vector to A, such that:

<code>A = [[v, a^2, a, 1], [v, b^2, b, 1], [v, c^2, c, 1]]</code>

where v is the target velocity. (x in this case would also need another element).

[[Category:Targeting]]

Targeting Matrix

2011-03-24T15:57:43Z

Ceasar: Created page with "A technique employing knowledge at the intersection of linear algebra and statistics. == Idea == Using projections, as described in linear algebra, it's possible to map an n-d..."

A technique employing knowledge at the intersection of linear algebra and statistics.

== Idea ==

Using projections, as described in linear algebra, it's possible to map an n-dimensional matrix, A, to a vector, b, via a third vector, x, such that Ax=b.

== Example ==

Consider we wanted to simply devise a matrix that would map distance to a firing angle. In order to do this, we might create an 3-dimensional matrix, with values [x^2, x, 1] for every x that we record, where x is the distance to our target at the time of firing, and a second vector, [y] where y is the correct firing angle. After acquiring three data points, we'll be able to arrange our vectors in the form Ax=b, as such:

<code>A = [[a^2, a, 1], [b^2, b, 1], [c^2, c, 1]]

x = [unknown1, unknown2, unknown3]

b = [[angle_a], [angle_b], [angle_c]]</code>

Now we wish to solve for x. To do this, we project A onto b. Therefore, we first multiply both sides of the equation by <math>A^T</math> to get:

<math>A^T * A * x = A^T * b</math>

And then multiply by the inverse of <math>(A^T * A)</math> to reach <math>x = (A^T * A)^-1 * A^T * b</math>. We now can compute x.

Since we have <math>x</math>, we can now accurately map distances to targets to firing angles, via simply inputing distance into the function:

<math>f(x) = unknown_1 * x^2 + unknown_2 * x + unknown_3 * 1 = angle</math>

Notice that we used <math>(A^T * A)^-1 * A^T</math> (called the projection matrix, P) rather than simply <math>A^-1</math>. This is because by using the projection matrix we can actually compute <math>x</math> for any number of tuples. This is extremely useful, because if this was not possible, then we could have to use a polynomial of dimension <math>n</math> to fit a line through <math>n</math> tuples.

This idea is also extremely powerful because it allows us to easily factor more in variable by simply increasing the dimension of A. For example, if we also wanted to track target velocity, we would simply append a vector to A, such that:

<code>A = [[v, a^2, a, 1], [v, b^2, b, 1], [v, c^2, c, 1]]</code>

where v is the target velocity. (x in this case would also need another element).

Pyramid Bins

2011-03-24T14:58:41Z

Ceasar: moved Pyramid segmentation to Pyramid Bins: Misunderstood vocabulary at time of instantiation.

Pyramid segmentation

2011-03-24T14:58:41Z

Ceasar: moved Pyramid segmentation to Pyramid Bins: Misunderstood vocabulary at time of instantiation.

#REDIRECT [[Pyramid Bins]]

Talk:Pyramid Bins

2011-03-24T14:58:41Z

Ceasar: moved Talk:Pyramid segmentation to Talk:Pyramid Bins: Misunderstood vocabulary at time of instantiation.

Talk:Pyramid segmentation

2011-03-24T14:58:41Z

Ceasar: moved Talk:Pyramid segmentation to Talk:Pyramid Bins: Misunderstood vocabulary at time of instantiation.

#REDIRECT [[Talk:Pyramid Bins]]

Talk:Pyramid Bins

2011-03-23T17:02:50Z

Ceasar:

Pyramid Bins

2011-03-23T06:09:32Z

Ceasar: /* Idea */

Maximum Escape Angle

2011-03-23T06:08:12Z

Ceasar:

When firing, the Maximum Escape Angle (MEA) is the largest angle offset from zero (i.e., [[Head-On Targeting]]) that could possibly hit an enemy bot, given the [[Robocode/Game Physics|Game Physics]] of [[Robocode]].

== Calculation ==

Let's assume a triangle with sides <code>a</code>, <code>b</code> and <code>c</code> and angles (vertices) <code>A</code>, <code>B</code>, and <code>C</code>. <code>A</code> is the angle opposite to <code>a</code>, <code>B</code> is opposite to b, and <code>C</code> is opposite to <code>c</code>. The [http://en.wikipedia.org/wiki/Law_of_sines Law of sines] says that:

[[Image:LawOfSines.png|center]]

Now let's say that your bot is in the vertex <code>A</code> and the enemy bot is in the vertex <code>C</code>. We will fire a bullet with angle <code>A</code> to hit the bot in vertex <code>B</code>. We know the value of <code>b</code> (it is the distance <code>D</code> from your bot to the enemy).
We don't know <code>c</code>, but we know that it will be the distance traveled by the bullet. Also, we know that <code>a</code> will be the distance traveled by the enemy bot. If we put <code>a</code>, <code>b</code>, and <code>c</code> as a function of time, we have:
<pre>
b = D
c = Vb * t (Vb is the bullet speed)
a = Vr * t (Vr is the enemy bot velocity)
</pre>
Now, using the Law of sines:
<pre> a/sin(A) = c/sin(C)
-> Vr*t / sin(A) = Vb*t / sin(C)
-> sin(A) = Vr/Vb * sin(C)
-> A = asin(Vr/Vb * sin(C))
</pre>
We don't know the value of <code>C</code>, but we can take the worst scenario where
<code>C = PI/2</code> (<code>sin(C) = 1</code>) to get a Maximum Escape Angle of
<code>A = asin(Vr/Vb * 1) = asin (Vr/Vb)</code>.

With a maximum Robot velocity of 8.0, a theoretical Maximum Escape Angle would be <code>asin(8.0/Vb)</code>. Note that the actual maximum depends on the enemy's current heading, speed, and [[Wall Distance]].

== See Also ==

* [[Maximum Escape Angle/Precise]] - Some bots use a more sophisticated calculation for Maximum Escape Angle, using [[Precise Prediction]].

[[Category:Robocode Theory]]
[[Category:Terminology]]

Maximum Escape Angle

2011-03-23T06:07:26Z

Ceasar: Undo revision 18858 by Ceasar (talk)

When firing, the Maximum Escape Angle (MEA) is the largest angle offset from zero (i.e., [[Head-On Targeting]]) that could possibly hit an enemy bot, given the [[Robocode/Game Physics|Game Physics]] of [[Robocode]].

== Calculation ==

Let's assume a triangle with sides <code>a</code>, <code>b</code> and <code>c</code> and angles (vertices) <code>A</code>, <code>B</code>, and <code>C</code>. <code>A</code> is the angle opposite to <code>a</code>, <code>B</code> is opposite to b, and <code>C</code> is opposite to <code>c</code>. The [http://en.wikipedia.org/wiki/Law_of_sines Law of sines] says that:

[[Image:LawOfSines.png|center]]

Now let's say that your bot is in the vertex <code>A</code> and the enemy bot is in the vertex <code>C</code>. We will fire a bullet with angle <code>A</code> to hit the bot in vertex <code>B</code>. We know the value of <code>b</code> (it is the distance <code>D</code> from your bot to the enemy).
We don't know <code>c</code>, but we know that it will be the distance traveled by the bullet. Also, we know that <code>a</code> will be the distance traveled by the enemy bot. If we put <code>a</code>, <code>b</code>, and <code>c</code> as a function of time, we have:
<pre>
b = D
c = Vb * t (Vb is the bullet speed)
a = Vr * t (Vr is the enemy bot velocity)
</pre>
Now, using the Law of sines:
<pre> a/sin(A) = c/sin(C)
-> Vr*t / sin(A) = Vb*t / sin(C)
-> sin(A) = Vr/Vb * sin(C)
-> A = asin(Vr/Vb * sin(C))
</pre>
We don't know the value of <code>C</code>, but we can take the worst scenario where
<code>C = PI/2</code> (<code>sin(C) = 1</code>) to get a Maximum Escape Angle of
<code>A = asin(Vr/Vb * 1) = asin (Vr/Vb)</code>.

With a maximum Robot velocity of 8.0, a theoretical Maximum Escape Angle would be <code>asin(8.0/Vb)</code>. Note that the actual maximum depends on the enemy's current heading, speed, and [[Wall Distance]].

== Further Improvements ==

The above gives a solid estimate of the maximum escape angle, but in practice, it's slightly different.

[[Image:RobocodeMaximumEscapeAngle.jpg|center]]

Notice that the triangle formed by assuming PI/2 as the lateral angle of our target fails to cover a small part of all places the target could go. For most cases, it's entirely negligible, as a curved path reduces the time it takes for the bullet to reach the target. But in the case of very specific firing strategies, the fault can become apparent, and the maximum escape angle must be redrawn.

== See Also ==

* [[Maximum Escape Angle/Precise]] - Some bots use a more sophisticated calculation for Maximum Escape Angle, using [[Precise Prediction]].

[[Category:Robocode Theory]]
[[Category:Terminology]]

Maximum Escape Angle

2011-03-23T06:07:17Z

Ceasar: Undo revision 18857 by Ceasar (talk)

When firing, the Maximum Escape Angle (MEA) is the largest angle offset from zero (i.e., [[Head-On Targeting]]) that could possibly hit an enemy bot, given the [[Robocode/Game Physics|Game Physics]] of [[Robocode]].

== Calculation ==

Let's assume a triangle with sides <code>a</code>, <code>b</code> and <code>c</code> and angles (vertices) <code>A</code>, <code>B</code>, and <code>C</code>. <code>A</code> is the angle opposite to <code>a</code>, <code>B</code> is opposite to b, and <code>C</code> is opposite to <code>c</code>. The [http://en.wikipedia.org/wiki/Law_of_sines Law of sines] says that:

[[Image:LawOfSines.png|center]]

Now let's say that your bot is in the vertex <code>A</code> and the enemy bot is in the vertex <code>C</code>. We will fire a bullet with angle <code>A</code> to hit the bot in vertex <code>B</code>. We know the value of <code>b</code> (it is the distance <code>D</code> from your bot to the enemy).
We don't know <code>c</code>, but we know that it will be the distance traveled by the bullet. Also, we know that <code>a</code> will be the distance traveled by the enemy bot. If we put <code>a</code>, <code>b</code>, and <code>c</code> as a function of time, we have:
<pre>
b = D
c = Vb * t (Vb is the bullet speed)
a = Vr * t (Vr is the enemy bot velocity)
</pre>
Now, using the Law of sines:
<pre> a/sin(A) = c/sin(C)
-> Vr*t / sin(A) = Vb*t / sin(C)
-> sin(A) = Vr/Vb * sin(C)
-> A = asin(Vr/Vb * sin(C))
</pre>
We don't know the value of <code>C</code>, but we can take the worst scenario where
<code>C = PI/2</code> (<code>sin(C) = 1</code>) to get a Maximum Escape Angle of
<code>A = asin(Vr/Vb * 1) = asin (Vr/Vb)</code>.

With a maximum Robot velocity of 8.0, a theoretical Maximum Escape Angle would be <code>asin(8.0/Vb)</code>. Note that the actual maximum depends on the enemy's current heading, speed, and [[Wall Distance]].

== Further Improvements ==

The above gives a solid estimate of the maximum escape angle, but in practice, it's slightly different.

[[Image:RobocodeMaximumEscapeAngle.jpg|center]]

Notice that the triangle formed by assuming PI/2 as the lateral angle of our target fails to cover a small part of all places the target could go. For most cases, it's entirely negligible, as a curved path reduces the time it takes for the bullet to reach the target. But in the case of very specific firing strategies, the fault can become apparent, and the maximum escape angle must be redrawn assuming the target takes an arced path rather than a straight one.

== See Also ==

* [[Maximum Escape Angle/Precise]] - Some bots use a more sophisticated calculation for Maximum Escape Angle, using [[Precise Prediction]].

[[Category:Robocode Theory]]
[[Category:Terminology]]