User:Voidious/TripHammer

Background

This began as a new gun using 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.

TripHammer became a place for me to experiment with different forms of clustering. I only posted about k-means and KNN variants, but I put significant time into a couple other clustering algorithms, too. So far, I haven't found one that improves on KNN (regular "Dynamic Clustering").

TripHammer k-means: 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

I still think it's worth exploring other forms of clustering. In targeting, there are parts of the data space that are very dense. A more sophisticated clustering system would recognize them and let you leverage all of that very relevant data (the power of SuperNodes). In the rest of the data space or before you have enough data, you can fall back on KNN. If I resume working on this, I think I will develop a test harness that lets me test against pre-gathered data sets, which should make testing much faster than running actual battles. (For random movers, that is... obviously surfers react to the gun.)

I used Diamond's code as a base, which made development pretty easy. The k-means algorithm is actually a rather simple design. This also meant I could easily integrate it into Diamond's Virtual Guns array. Diamond's current gun is called "TripHammer KNN", which uses all of the little tweaks I found during this experiment, but just KNN, no k-means.

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