User:Voidious/TripHammer

Background

This is a new gun I'm working on that uses k-means clustering. I knew ABC had tried and abandoned it once upon a time, so I found myself wondering what kind of concessions you would have to make to get k-means clustering working in Robocode's CPU constraints. At first glance, k-means clustering indeed seems a lot more CPU intensive than k-nearest neighbors. But as I considered how I might implement it, I realized that it was not only viable, it could even be pretty fast.

How it works

The algorithm

• The first k points added are used as the initial locations of the means. (Note that these points are not permanently tied to the clusters beyond just being the first points in them.)
• When a new point comes in, assign it to the nearest cluster and update the mean.
• After the new point is added, go through a few old points and reclassify them. If a point should be in a different cluster, move it over and update the means of both clusters.
• I keep a circular linked list of all points to keep track of which point should next be reclassified. New points are added at the "end" (right before the current list pointer), so it's always reclassifying the point that was least recently examined.
• To aim, just find the nearest cluster, then do some kernel density on the points in that cluster to decide on a firing angle.
  • If there's not much data in the nearest cluster, add in points from one or more nearby clusters until we have "enough". This should make it behave similarly to k-nearest neighbors in the early rounds and in rare circumstances with very few points. (Simply using KNN in these situations is another option I'm considering.)

Technical notes

• Regarding the initial means: I first tried k random points (common in k-means algorithms), and I've since tried slightly randomizing the first k points that are added, but just using the first k points has worked best.
• When adding/removing points to/from clusters, updating the cluster mean is easy with one weighted average calculation, so that's really fast.
• Right now, finding the nearest cluster is brute force, so this is one of the slower parts of the code. Not that it's all that slow to do brute force KNN on such a small data set, but it also runs many times per tick. There are methods to speed this up in k-means algorithms, such as the filtering method detailed here, but I don't think that method would work in my k-means algorithm and I haven't come up with any of my own methods yet.
• Kernel density is the other slow part of the code, since these clusters can have thousands of points. Some things I do to speed it up:
  • I test fixed, evenly spaced angles (like Ali) instead of every angle in the cluster (like Diamond).
  • I use Quartic instead of Gaussian kernel density (see here), so I'm not doing costly Math.exp operations all the time.
  • I may play with reducing the number of points used in the kernel density (e.g., with nearest neighbors, or using randomly chosen points). But I like leveraging the huge amounts of well classified data, and so far it's still fast enough for 35 rounds.
• Current settings:
  • 250 clusters.
  • Reclassifying 20 points each tick.
  • The scan distancing function is almost exactly the same one as Diamond's main gun, except I'm using Manhattan distance.
  • I'm using precise GuessFactors (as in precise MEA, like Dookious), not displacement vectors (like Diamond).

Of course, this is a bit different than Lloyd's algorithm, the most common k-means algorithm. But it continually recenters the clusters and reclassifies data points much faster than it adds them, so the clusters should still converge nicely.

Thoughts / Plans

The TCRM results are far better than any other gun I've made. I used it in Diamond 1.39 in place of the usual KNN Main Gun, and it performed about even: 1.39 vs 1.372. It's encouraging to see such strong results, but this isn't enough for me to keep it in Diamond. If I find future improvements, I will try it again.

I originally thought this was only going to be useful against random movers, but there may be some potential as an Anti-Surfer gun, as well. Limiting the size of the clusters and cycling out old points seems like it would behave a lot like a low rolling depth in Visit Count Stats buffers. I've gotten some respectable Anti-Surfer Challenge scores already (better than Diamond's current AS gun, even).

I used Diamond's code as a base, which made development pretty easy. It's actually a rather simple design. This also meant I could easily integrate it into Diamond's Virtual Guns array. I don't think it's fast enough for melee, and I don't think Wave Surfing has enough data to make it useful there, so for now it's just a 1v1 gun experiment.

(PS - the name is another cool superhero from Powers, since it's part of my Diamond code base.)