Talk:Dynamic Clustering

Straw is discussing his development of a gun for a Robocode competition that uses kNN classification and the opponent's last 5 GFs (guess factor) as dimensions. The gun performs well against surfers and simple movers, but has not been tested against random movement. Rednaxela suggests using the reference bots from the Targeting Challenge RM for testing. The gun is still being optimized and Straw is considering using a VG array or density calculations. Voidious is curious if the 5 GFs are treated independently or as a sequence. Rednaxela suggests using relative GFs as dimensions. Straw also mentions using 10 GFs instead of 5 and using descending weights on older GFs. The gun has shown promising results against flatteners, with a similar hit rate as Diamond's gun. The performance of the gun improves with an increased value of K.

– ChatGPT

I tried making a gun which uses kNN classification, in which the one dimension is shots (for data decay) and the others are the last 5 GFs the opponent went to on firing waves. Its very simple right now and I haven't tried much, but it does reasonably well (as in it doesn't get crushed, does better than random targeting) vs both surfers and simple movers. (Haven't tried against random movement yet) It seems similar to pattern matching on the opponents GFs. Any ideas?

can you show the robowiki the gun

Interesting. I think you should definitely test against RM, because surfers generally don't like anything with bullet waves, and simple movers are pretty easy to hit. Also, you might want to start with the basics (distance, velocity, relative heading, acceleration...) before you get into data decay and experimental dimensions. Good luck.

Don't worry! I am actively optimizing my more "normal" gun using standard predictors. What bots would you recommend as good test bots with strong RM? Tmservo its just a 6 dimensional KNN, 5 are lastGFs normalized to 0-1, last one is sqrt(shots)* .5. I haven't added any kernel density stuff to this tree, I plan to try that.

just drussgt, diamond, gilgalad, tomcat, xandercat, waveserpent, nene, gressuffurd,

Those are not bots with Random Movement as Straw asked for.

I'd suggest you use the reference bots from the Targeting Challenge RM, because they give you a good variety of random movements, and have been thoroughly tested against before, so the 'expected' result is fairly accurately known. You may wish to use RoboRunner to automate testing against that set as well.

Yeah, like Rednaxela said, the reference bots would work well. I'm curious, are you planning to have these two guns in a VG array, or are you just experimenting in parallel?

Not sure yet, could use a VG array, or might get results from two trees and do density calculations on the results from both.

Seems like a neat idea. I'm pretty sure I recall prior GFs being used in kNN targeting in the past (I think I may have tried that a little), but never (to my knowledge) going to the extreme of 5 prior GFs.

Works well against active flatteners. Bad against the rest. Anti-flattener classifier.

Well, I'd imagine it might work okay against oscilator, stop-n-go, and CircleBot movements... but out of strong movements, yeah, I'd mostly expect flatteners indeed.

If this does well vs flatteners, it would fit my strategy perfectly as I am trying to create anti surfer and flattener guns independently first. Another idea closer to pattern matching would be using the past 10 GFs of all waves, including non firing waves every tick. I am interested in the idea of looking at changes in GF between waves instead of absolute GF as Rednaxala is suggesting.

I'm curious how you're structuring this: Do you condense these 5 GFs into one attribute, or are they 5 independent attributes?

The most practical example this reminds me of is I believe Skilgannon uses his own last GF as an input to his gun to help crushing mirror movement. Using the enemy's previous movements I would guess to behave similarly to attributes like displacement distance last X ticks or time since velocity change.

My only other comments is that 5 seems like a lot. At an interval of 14 ticks, that's 70 ticks into the past, and more if you count the time it took to reach that first GF. My "distance last X" experiments have never gone past ~40 ticks, IIRC, and even that was not a strong signal.

Straw already said that there are six dimensions in his(?) gun, one for decay, and one for each of the enemy's last five visited GFs.

I'm just curious if they're being treated independently. A sequence like 0, 0.2, 0.4, 0.6, 0.8 actually might be quite close to 0.2, 0.4, 0.6, 0.8, 1.0, but if they're all treated independently, your classification won't see it that way.

If one wanted to make the ones you mention be treated similar, the way to do it would be to make the dimensions either:

GF[i], (GF[i] - GF[i-1]), (GF[i-1] - GF[i-2]), (GF[i-2] - GF[i-3]), (GF[i-3] - GF[i-4])

or perhaps:

GF[i], (GF[i] - GF[i-1]), (GF[i] - GF[i-2]), (GF[i] - GF[i-3]), (GF[i] - GF[i-4])

(where index 'i' is the most recent wave, 'i-1' is the second most recent wave, etc)

Of course, whether that would give better results than all independantly I have no idea about... and which of those ways of making it relative would be better I'm not sure about either.

I appreciate the concerned ? with his. I am male though.

Doesn't DrussGT use the opponents last GF in his targeting system, not his own? (in addition, a dimension called my expected mirror rotation at bullet hit time) It looks so far into the past because in both surfers and flatteners, (especially surfers) recent past movements are a good indicator of present movements. Fast decaying "normal" anti surfer guns do a similar thing in a different way.

Yes I do something similar in DrussGT, in two places.

1. I use the enemy's current GF as a gun attribute to help with oscillators

2. I use my predicted GF one BFT in the future as in input to help against mirror bots (and it helps a little against most other bots as well)

I'm also curious about the last 5 GFs - are they sorted and fed to the gun in ascending order, or are they used in the order they were collected? I feel that some distance/clustering method other than KNN might work best in this situation.

I agree that something other than KNN might be better, but its what I have set up right now. No sorting happens, the gun just has a dimension for the last GF, a dimension for the GF before that, etc. I found increased performance dropping data decay, going to 10 past GFs, and using descending weights on older GFs. Data decay shouldn't be necessary with this setup as if the opponent changes their movement patterns, they will change their GF sequences.

Exiting anti flattener results! The gun gets pretty much the same hitrate vs DrussGT (which can't shoot) with DrussGTs flattener allowed to turn on or forced off. Around 10.6% weighted from DrussGT's console. For comparison, Diamond's gun gets around 12.6%. The interesting thing is that the hitrate didn't go down at all with the flattener.

When I increase K in my GFs as dimensions gun, performance improves. Interesting.

by exactly how much per k

Having optimized weights appears to be very important, especially the weight on old vs new data. However, these optimal weights may not be the same against all opposing bots, particularly the case of hitting adaptive vs non adaptive movement. If your kD-Tree provides dynamic weighting functionality, you could theoretically have good weightings vs opponents after a few rounds. (See my post in "Hard-coded segmentation") The difficulty is thus finding the optimal weights for hitting a given opponent in short learning period. One approach would be to change your weights after a missed wave in a similar manner to training neural networks. When a wave hits, and your bullet misses, in non firing ticks (during which you have extra calculation time) do kNN searches to see if the weight on a particular predictor would have caused a better (closer to correct GF, or perhaps DV) prediction if it was higher or lower. Then, look at the results the past several calculations and look for trends, to avoid training on noise.(This is somewhat similar to what Gaff's gun does, it stores results from the past 5 missed waves and trains the neural network with all of them on a miss(If I remember correctly...)) This seems like it would tend to converge on better weights, which might help fight opponents with adaptive movement. It also would partially alleviate the curse of dimensionality on kNN classification, by lowering the weights of unimportant predictors (against a particular opponent) to close to zero, essentially removing them. Does anyone else have ideas for optimizing weights during combat?

In a gun, the easiest way would be having many sets of weights and put them all in a virtual gun array. But if all the sets perform similar to each other, the virtual gun will not be able to pick the optimal one due to noise.

And flatteners actively try to screw up most statistics, including virtual gun scores.

For tuning weights in a gun, I'd strongly recommend testing things offline with WaveSim or similar. It's a couple orders of magnitude faster to test against pre-gathered data.

Also, I've done quite a bit of tuning of gun weights this way. The gun weights in Diamond were evolved through a genetic algorithm with WaveSim. But honestly it barely outperforms the hand-tuned weights I had before that. I'm fairly skeptical that it's worth ever straying from "generally optimal" in order to eventually get "bot-specific optimal". That is, I think a gun with generally optimal weights tuned over 10,000 matches will beat bot-specific optimal tuned over <= 35 rounds.

Worth noting that all the tuning I've done was specifically on attribute weights though, not decay rate or other factors. My main gun doesn't decay, just my Anti-Surfer gun. (And you may not want to tune an AS gun against pre-gathered data, though Skilgannon has.)

Based on information from you and others who say that weights on predictors other than data decay have very little effect on performance, the method I described might only be useful for adjusting your data decay in an anti surfer gun. However, it might also allow you to add more specialized predictors which started at weights of zero and were only used if found to be relevant. For example, what if you found that looking at some statistic of the past 5 GFs a bot goes to helps against bots using flatteners, but not at all against anything else. Adding this to a statically weighted gun would probably decrease performance against everyone but opponents using flatteners. I might use WaveSim when I'm working on an anti non adaptive targeting system.

I notice that Wintermute prints out "move weights" to the console, and that they change. Is it changing kNN weights?

IIRC, there are several different KNN schemes, and it changes the weight that each of the results are valued at. So one for simple guns, one for intermediate, one for more complex guns, and a flattener scheme. Then these are evaluated and chosen depending on how well their contributions predicted the enemy gun.