Difference between revisions of "User:Voidious/TripHammer"

From Robowiki
Jump to navigation Jump to search
m (link to displacement vector)
(misc updates)
Line 1: Line 1:
 
== Background ==
 
== Background ==
This is a new gun I'm working on that uses [[wikipedia:k-means clustering|k-means clustering]]. I knew [[User:ABC|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 [[wikipedia:k-nearest neighbor algorithm|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.
+
This began as a new gun using [[wikipedia:k-means clustering|k-means clustering]]. I knew [[User:ABC|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 [[wikipedia:k-nearest neighbor algorithm|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 ==
+
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 algorithm ===
Line 30: Line 32:
 
== Thoughts / Plans ==
 
== Thoughts / Plans ==
  
The [[Targeting Challenge RM/Results|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: [http://darkcanuck.net/rumble/RatingsCompare?game=roborumble&name=voidious.Diamond%201.39&vs=voidious.Diamond%201.372 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 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 originally thought this was only going to be useful against random movers, but there may be some potential as an [[Anti-Surfer Targeting|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 with just a few tests.
 
  
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.
+
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 [[wikipedia:Powers (comics)|Powers]], since it's part of my Diamond code base.)
 
(PS - the name is another cool superhero from [[wikipedia:Powers (comics)|Powers]], since it's part of my Diamond code base.)

Revision as of 17:55, 7 March 2010

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:

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.)