Dodging Performance Anomaly?
← Thread:Talk:Pris/Dodging Performance Anomaly?/reply (2)
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.
You do not have permission to edit this page, for the following reasons:
- The action you have requested is limited to users in the group: Users.
- You must confirm your email address before editing pages. Please set and validate your email address through your user preferences.
You can view and copy the source of this page.Skilgannon (talk)
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.