TronsGun

Tron/Shadow Gun

(or: Pattern Recognition Gun)
(or: Forward Pattern Matching Gun)

(or: how to make it to the top10 without GuessFactors)

The idea:

One day I decided I needed a good gun if I wanted to remain competitive against the ever-improving Robocode crowd. Being stubborn as always, I refused to go the GuessFactor way, no matter how brilliant and effective I knew it was. So I started by making the simplest of the pattern matchers, to see where it would lead me. Of course the biggest problem with pattern matching is the inconsistency of melee scans... if this gun was to work, it would have to work in melee. My main robot is still Tron, and melee is it's favourite game ;). So, I don't have detailed information on the enemy's recent speed/heading; what do I have that could possibly replace that? The idea was to find a "signature" for the enemy's past movement, preferably a scalar one so that it could be used to rate the "likeness" of the enemy's past movements. I started by calculating the distance traveled by the enemy in the last 15 ticks. That, coupled with the current speed, should give me an approximate measure on the enemy's recent acceleration/decceleration. I still needed a way to incorporate heading change into that, so I projected that distance onto the current enemy's heading. It started to work great, the sample bots were being crushed fast even in a crowded melee battle. So now I needed a way to make it work better against good random movers, in other words I needed some statistical element. So I did it like this: for every scan I find the N most similar situations in the enemy's history (lots of other factors were added, like distance traveled in 30/60/120 ticks, distance to me/wall, etc), I then "trace" the past enemy movement forward from it's current position, and calculate the angle that would hit if the enemy made each of those exact movements. From those angles (currently 50), I find the most recuring one, the one that would hit the enemy (with a tolerance of getWidth()*k) in the largest number of those cases.

Pseudocode:

Calculate the distance traveled by the enemy in the last 15/30/60/120 ticks, and save that along with its current speed, distance to me, distance to wall, etc.

Compare it with every single past scan, by summing the square of the errors (normalized to -1..1). Ex: diff = Utils.sqr(curr.speed / 8 - past.speed / 8) * factor1 + Utils.sqr(curr.dist15 / (30 * 8) - past.dist15 / (30 * 8)) * factor2 + ...

Take the 50 most similar past scans (minimum diffs) and trace each of those movements forward from the enemy's current position/direction. Calculate the firing angle that would hit the enemy's center in each of those cases.

Clean out any movement that leaves the enemy outside of the battlefield. Also save the tolerance angle for hitting the enemy in each situation (botWidth() / hitDistance).

For each of those angles, count the number of situations it would hit the enemy (taking the tolerance into account). Choose the one with the most hits. Fire at will! :)

---

Comments / Questions / Suggestions / Feedback:

You said: Take the 50 most similar past scans.Does that mean that you just compare single scans and dont search with a certain depth for most matching values (like normal pattern matcher do) ? --deathcon

Yes, I replaced the depth searching by a kind of "PM signature", by computing the distance traveled in the previous 15/30/60/120 ticks for each scan. That is why I don't call it a true pattern matcher. It is mix between a very highly segmented GF gun and a pattern matcher. It is not as dependant on the enemy's position relative to you as a GF gun, and it doesn't rely as much on a good scanner info as a normal PM. Another good name for it could be a guessAngle gun. :) -- ABC

Very funny that u said that... I have always thinked about our type of gun (as u know Musashi's gun is very similar to TronGuns, and TronGuns inspired the MultipleChoice in it) like an improved PM: we find a group of "best matches" (using factors like wall-dist, corner-dist, target bearing, and obviously the history positions), and then using MultipleChoice we filter the more "populated" angle. Althoght, you think about it as beeing a PM filter to a GF gun (right?). Two ways to face the same thing. -- Axe

Not really, I also think it is much closer to a PM gun than to a GF gun. There are no guess factors involved, just absolute angles. The MultipleChoice part is similar to a GF gun, but with angles derived from a PM method instead of factors of the max angle. Ok, a better name: Statistical Pattern Matcher. :) -- ABC

Agree with ABC about it being a pattern matcher. Note that a pattern matcher works in any time-ordered set of data, identifying the points in the past similar to the current ones and then rebuiling the enemy path (and the info used for it can be different from the one used for matching the data). I think the main difference beetwen PM and GF/Statistical targeting is that with PM the time dimension in heavily involved in the calculations (you explore the data through the time) but in GF/statistical targeting time is not involved at all (you segment the series by many values but the time. The only way to remotely deal with time is to add some kind of rollingAverage). -- Albert

GuessFactors versus absolute angles is a pretty small distinction if you're segmenting on distance. There are GF type stat guns out there using angle offsets and not GFs. -- Kuuran

---

I have a quick question, what do you do at the begining of the game when you dont have enough data? I am trying to implement a gun like yours in X2, but at the begining of the game (until round 4 or 5) I dont always have enough data so I just fire headon. -- Florent

Ummm, you sure you have a gun like this? Ali has it and it has data from tick 40 about. When you have only one sample in the log it's pretty easy to choose what sample to use. =) -- PEZ

Yes, I just found out that my movement projection algorithm was completly wrong ... At least now I know what is wrong. -- Florent