Dodging Performance Anomaly?
Thanks for the amazingly fast reply. And for the movement system, I've only been working on robocode for about a month, and I started on targeting first. Another interesting thing is that DrussGT only scores 73% with a 17% hitrate against Pris, worse than mine, yet it totally trounces my bot in a direct battle. Has anybody thought about using Random Forest for movement or targeting? It uses an ensemble of decision trees for classification. Its slow to generate a forest, but running data through one is pretty fast. I could imagine a robot which only retrained a few of the trees in a forest every tick. Seems somewhat similar to what people are doing with K nearest neighbor classification.
I've looked at random forests before, another one which interested me was Extreme Learning Machines which are feed-forward NNs working in an ensemble. The trouble I found was that even though these methods are fast when compared to other machine learning techniques (K-means, feedback NN, SVM), they are still much slower than a single KNN call in a Kd-Tree just because of the amount of data they need to touch for each 'event'. A Kd-Tree trains incrementally in O(logN) and classifies in O(logN), with N being the number of items in the tree. I think the only thing faster would be a Naive Bayes classifier.
Feel free to prove me wrong though =) I'd love something which works well beyond the ubiquitous Kd-Tree!
Another thing to consider is how you are going to pose the question. A lot of the successful NN-based approaches have used a bunch of classifiers, one for each potential firing angle, and shooting at the one with the highest probability. Others have tried posing it as a straight regression problem, but I don't think those worked as well, possibly because of the high noise (against top bots you are lucky to get a 10% hitrate).
I'd be interested to hear what you end up trying, and how it works out.
Another neural net thing I haven't seen in any bots is recurrent neural nets with memory. I've heard they are very good at certain types of problems, where they need to be able to recall old information while still learning new stuff. I don't know exactly how to implement the back-propagation algorithm on them, and I am no NN expert, but it seems as if they might be good against adaptive movers.
I have heard that SVMs are significantly slower than RF, but work better on smaller data sets. Since RF can handle both categorical and numerical outputs and predictors, you could pose the problem asking for a GF, or a bin to fire in. I'm not sure if you can get multiple outputs out of it. Another nice thing is that you wouldn't have to weight all your different predictors because RF figures out which ones are important for you. I plan to test RF out of a bot on data gathered from battles soon. Even if it doesn't work well or is too slow, it could still determine good weights for predictors used in a KNN algorithm.
In all these classification algorithms, if speed is a big issue, why not make a system allowing the spread of calculations over multiple ticks? It seems like you don't need to train every tick in general.
Recurrent NN uses a lot of memory and processing power, both of which are fairly limited in the RoboCode setting. Speed is definitely the main issue, particularly when a lot of the time is already taken doing predictions to give more relevant features for classification. Even with spreading calculations over multiple ticks many popular techniques Just Wouldn't Work.
If you can't get multiple outputs out of the RF, just run a bunch of them, one in each bin, and choose the bin with the highest probability. Ie, each bin is a different class and you choose the most probable class. Quick and dirty regression without inter-dependency. I've actually thought about trying a Naive Bayes like this, just for kicks. I think Pris and a few others do their NN classifications this way.
Running 50+ random forests with 50 trees each would be a lot of computation. I am first going to try seeing how well one RF predicts a GF or bearing offset.
Executing one tree classification is pretty fast though, isn't it? I don't think 2500 of them per tick seems unreasonable. Or is it many times more than that? My main 1v1 gun does up to 13k loop iterations for its kernel density calculation, and that's on top of the kd-tree search for 225 nearest neighbors among up to ~25k data points. And the gun is the fast part of the bot. :-)
I've looked at random forests before, but only briefly, and only because I saw on Wikipedia that they are like the state of the art in machine learning classification algorithms. :-P The other classification system I've always wanted to tinker with was Support Vector Machines, which I learned about in school and seemed really cool/versatile.
My main efforts to top KNN have been clustering algorithms, mainly a dynamic-ish k-means and one based on "quality threshold" clustering. I managed to get hybrid systems (meaning they use KNN until they have some clusters) on par with my KNN targeting, but getting the same accuracy at a fraction of the speed wasn't useful.
KNN really is fast as heck and just seems perfectly suited to the Robocode scenario. But Pris is pretty damn impressive with the neural nets and I'm sure someone could do better.