DC and VCS

So, I have been working on my movement, and I theorized that VCS movements would have a small advantage in the rumble because VCS guns are so common. However, I dislike VCS because I have found KNN so much more intuitive. (Yes, I probably just had a lot of bugs in my VCS gun, but I still like KNN better.) The problem I have is that I can guess how important attributes would be for a random movement fairly well, but I can't guess what people would use in their guns so I can't do as good of a job with those. (Which basically means I just copy Diamond) So I wanted to try to make my KNN classifiers match VCS guns as much as possible (except for the flattener where being different is probably beneficial). Step one is to make classifiers that would match "typical" guns, like raiko, or GFTargeting tutorial, etc. Any thoughts on what is "typical" for VCS guns? Also I can't think of how the weights should be chosen. Any ideas?

Well, the same dilemma of "guess how important attributes would be" exists with VCS as well.

Anyway, fun thing is, you can actually determine in a fairly algorithmic manner, how to make a KNN search that behaves as closely as possible to a given VCS configuration (i.e. Raiko's like you mention) while still being continuious.

1. For each dimension, examine the VCS bins. If the size of the bins are non-equal (be careful to note how the minimum/maximum values of the dimension interact with the first/last bins), then you need to divise a continious function which curve fits the bin-size as a function of the value of the dimension. You can use any form of regression you like for this, provided the function stays above 0 for all.
2. For each dimension's "bin-size" approximation function, take it's integral. The resulting function should now be monotonic. We'll call this the "scaling function"
3. Feed each "scaling function" the minimum/maximum values for it's associated dimension and make note of the minimum/maximum values out of the function. Then divide the number of bins in the dimension by the difference between the maximum/minimum values, to get the scaling factor to make the range of the "scaling function" proportional to the number of bins. Multiply your "scaling function" by this.
4. Now, before inserting values into the kd-tree, you put them through this "scaling function", which should weight them approximately the same as how the VCS did :)

(Hmm... maybe I should write code to perform this procedure some time...)

Oh just to quickly reply to my old ponderings... I was slightly mixed up before. To get the scaling function you'd want to take the integral of the *inverse* of that bin width function.

Also, there's an easier procedure than that mess I was describing before:

Just do a regression to fit the data points of "bin number" versus "bin center" (and possibly add non-center points with the same bin number too), while ensuring the function resulting from regression is monotonic. That'll give the final scaling function straight out of the regression without needing any other funny business.

Well, the problem uwith that is it would copy the bins exactly which means that if a different bot used 6 distance bins instead of 8 it would give worse results. Thinking about it more, my guess is that giving each attribute equal weight is the best solution for a particular set of attributes and weighting attributes equally or proportional to the number of bots in the rumble using those attributes would be the best solution for the rumble. Anyways, weighting all attributes equally seems to give me about 3 more APS against Raiko.

I feel like "weighting everything equally" is almost an impossible notion. Like say you divide lateral velocity (range 0-8) by 8, and distance by 1000, and now you have them both in the range of 0-1, weighted "equally". But the lateral velocity is effectively weighted higher since the distribution is so much more spread out across the full range than distance (which is rarely 0 or 1000, and very frequently 400-600).

I've had some success with genetic algorithms for tuning attribute weights (with WaveSim), but still not a huge improvement on just hand tuning. The GA stuff is fun to play with though... Got some experiments running right now, in fact. ;)

I'm planning on some GA-esque searches on my weights for tuning down the road with deBroglie. How do you set up a nice loooooong set of 35 round Robocode battles for this? RoboResearch?

RoboResearch is certainly the tool of choice for running long sets of tests, but you'd really need your own layer of code on top of it to do any GA stuff. I'd instead just use the Robocode control API (which is pretty easy) for running the battles and collecting the results from your GA code, which is probably easier than manipulating RoboResearch.

The issue I haven't tackled yet is how to actually export each version of the bot to test. You'd have to package it from code with an Ant task or something, or export a .properties file that the bot reads in (probably the route I'll take).

All my GA stuff so far has used WaveSim, but I want to use some real battles to rewrite RetroGirl's movement. Keep in mind that GA with real battles will be VERY slow... I've had GA runs that take many days using WaveSim, and WaveSim is orders of magnitude faster than real battles.

Trying to workaround the slowness of full battles can be part of the fun. There are advanced GA techniques out there to deal with slow fitness functions. I tried some of them with Combat, tuning movement/targeting/energy management weights, all at the same time, against DrussGT in full battles. It gave me a +10% APS increase against it in 2 days, but a huge APS decrease against the rest of the population (Combat 3.9.0 (GA tuned) and Combat 3.8.2).

Maybe I´ll try GA tuning against the whole population someday, to avoid the specialization artifact that happened before.

I was thinking that a bot could read/write data from its local file directory. Read the file as "parents," select parents via fitness function, apply crossover/mutation.. load those values as weights, fight, write result at end of battle.

Lather rinse repeat for thousands of battles. Maybe start culling the least fit members of the population once it gets large enough...

This relies on the bot itself to determine its own score though... iffy.

Ah, yeah, that's an interesting idea. In 1v1 you should be able to determine the score. But I know I have a lot of other state associated with the GA stuff itself, so it would be some extra pain to have to import/export that every battle. You'd also miss out on any chance to multi-thread it.

Well, my weighiting them equally idea was only for the movement, for the gun I definitely don't think that will help. (But I'm not sure how much it will hurt.) For VCS movement, each dimension needs to be in a certain range for the gun to use the data from that point. So I would say that each attribute was equally important because the gun needs to match each attribute. (Assuming there was no secondary buffer to go to if there were no matches in a given segment) That being said, because VCS is a binary test, while KNN is a search for the closest point, a normal KNN can't be expected to work exactly like different (but similar) VCS systems. Thinking about it more, it seems like you're right about equal weightings being more complicated than weighitng everything 1.0, but I'm not sure how to deal with that. My initial guess would be weight = 1 / probability_randomly_distributed_situation_in_bin. Which would mean that the weight should be equally to the number of bins used for each attribute.

One problem I have with weighting the distance (or bullet travel time) dimension higher is that, as you said, the distances will mostly be in a range of 400-600. If I were using say one point and I had the option of distance = 450 and velocity change = 0 or distance = 499 and velocity change = 1 with the current situation as distance = 460 and velocity change = 1, the best choice is probably the second point, but weighting the distance higher may favor the first.

I have been wondering for a while how much of Gilgalad's ranking is due to the weighting of KNN and how much is due to a fairly good gun system and wave surfing algorithm, so I am puting a version with all weights (including gun and flattener weights) set to 1.0. (Actually, I forgot to change the weights on the enemy bullet power estimation to 1.0, but I currently only use that for onWin events so it shouldn't make a big difference)

Very interesting experiment! And it's shaping up to look like a fascinating answer!

More accurately, for VCS, I would guess attributes don't have a level of "importance" (in the algorithm itself, using some is more important than using others), you just test how much you can segment the data while still having enough data, and choose arbitrary cutoff points, which is probably why I find KNN more intuitive. But I'm still trying to think of a proof for an optimal similarity between a VCS system with evenly distributed data accross all dimensions, with a set number of divisions in each dimension, but the divisions being started arbitrarily while being evenly spaced (ie. any number between 0 and 100 is the start of the first distance bin, each bin covers 100 units, and we pretend the points can't be less that the minimum value)

I've only seen a fraction of the VCS guns out there, but "typical" configurations are probably modeled after the big / influential VCS bots, like Raiko, PEZ's bots, FloodMini, maybe even Dookious.

I guess maybe this question is for other people, since if you're looking at Diamond, you already know what I think about what attributes are best. =) But no shame in starting with a Diamond-inspired configuration and trying to improve from there. I certainly took guidance from Raiko and CassiusClay, and I also keep my eye on what brainiacs like Rednaxela and Skilgannon are doing.

I think a more difficult task is modeling data decay in KNN surf stats. Whenever you get hit, it means that your existing data is inaccurate. (If it were accurate, you wouldn't have been hit.) Where you got hit is the peak in that segment of his gun, so it needs to out-rank the other data points in that segment of your stats, but you have no segments so you can't just use rolling average. I think tuning this aspect of your KNN surf stats is at least as important as getting the attributes just right.

DrussGT uses a "bullets shot" classifier to give higher weight to newer data and works somewhat like data decay. It makes k-NN search extrapolate a bit, but still helps increase the score against learning opponents.

IMHO, the advantage of VCS over DC is CPU performance. But VCS compresses data into bins and some information is lost, while in DC it isn´t. So, well tuned DC should perform better than well tuned VCS, unless you start skipping turns.

That is for the gun, but a similar thing is definitely useful in movement. Best would be one log which has data rolling, and one without to handle simple bots and make sure you don't forget anything about them. That trick actually comes from Rednaxela, and possibly even originally ABC. It causes the Kd-Tree to be a bit slower as the match progresses, but works wonders against surfers and is behind my recent-ish PL improvements.

I have a similar view on VCS vs DC - VCS is faster at lookups (obviously, index lookups are O(1)) but less accurate due to the discretisation of both the bins and the segments. However, even in a DC environment VCS has its place: if I were surfing DC I would cache my results in an array just like VCS to make lookups faster when evaluating surfing points. Note, DrussGT's movement doesn't actually use segmented VCS in the movement anymore, but instead lists of hit indexes in each segment. This reduced my storage space and my logging-hits time, and actually reduced my retrieve time as well because many of the hits are different representations of the same original hit (from my many buffers). I did some trickery with weighting the hits to make sure it gives exactly the same results as my VCS with a rolling average would have.

It's worth noting that in movement, you have far less data, so CPU speed is less of an issue. Until you get into flatteners, and even then maybe virtual wave flatteners (which are rare), DC surfing could probably do fine without even using kd-trees. Precise prediction far outweighs information management, I think.

And yes, having a dimension that is pure linear time is certainly one of the simpler approaches to KNN data decay... ;)

What I was actually doing in my gun was having a non-linear time dimension, and it worked out a lot better than straight linear. I think I ended up with 1.2*T^(0.4) or so, instead of 0.005*T. Those weights were genetically evolved with my WaveSim-ish setup.

It makes sense that at the beginning you want your data to decay faster than towards the end...

I've generally considered the time dimension a pretty blunt/naive approach (I think I used it in Lukious), but I've been mulling it for the last hour and now I'm thinking it's actually pretty reasonable. I might even tinker with it some in Diamond (especially now that I have your secret formula, muahahaha!).

I know I've posted it elsewhere, but the main system I use in decaying Diamond's surf stats is like this:

• No time dimension, but each data point is timestamped.
• After choosing k neighbors, sort them inverse chronologically and weight them by rank. (Eg, 16/8/4/2/1.)
• Optionally (like in flattener), I also cap the size of the log and remove the oldest points.

Tuning k is like adjusting the granularity of a VCS buffer: k=1 is like a super highly segmented buffer (most similar situation wins, regardless of age), while a larger k is like a less segmented buffer with rolling average.

While I've tried this in my Anti-Surfer gun, too, the most effective decay I've found there is just capping the size of the log and discarding old points.