BinSmoothing - Robo Wiki -= Collecting Robocode Knowledge =-

Could someone point me in the direction of some information about bin smoothing? --Andrew

It seems to be scattered all over the wiki. Could someone knowledgable on the subject post something here, please? -- Tango

Just pasting from another page. -- PEZ:

isn't bin smoothing used to counteract the problems of not predicting correctly?--andrew

I think of bin smoothing as a way to even out local dents that your bot otherwise would risk opting for. -- PEZ

Excuses, i heard a lot about bin smoothing, can u describe what does it means? -- Axe

Pugilist smooths the data it reads from the stat bins. Like so:

    double smoothedVisits(int index) {
	double smoothed = 0;
	int i = 0;
	do {
	    smoothed += (double)visits[i] / Math.sqrt((double)(Math.abs(index - i) + 1.0));
	    i++;
	} while (i < Pugilist.FACTORS);
	return smoothed / Math.pow(distanceToTarget() / bulletVelocity, 1.3);
    }

That is, each bin's visits are also counted (although less so) in its neighbouring bins. This might be a source of error though since the edge bins don't have neighbours on both sides. Then they get less smoothed visits and might be tricking P to see a dent at GF1 that it tries to reach. I have had no luck with trying without smoothing and with smoothing accounting for this though so I am not sure it matters that much. The last thing happening there is my bullet travel time weighting. -- PEZ

Didn´t understood yet the concept behind the smoothing idea... Why would you need it? -- Axe

I mean: this can really lead you into problems reaching the edge... -- Axe

If you think of the GFs as a valley you want to descend to get to the minimum. Then add a little noise to make it more real life. That noise creates local minimums here and there... areas where the bins to either side are higher than the bin you are in, however not at the true minimum. Smoothing flattens the entire valley. Hopefully the noise gets removed in the smoothing process and only the major features, the true minimum, survive the smoothing. -- Paul Ingemi

This is massive smoothing there, PEZ. It might be that this is giving you some trouble with the GF ends and is taking some accuracy agains simple guns. Probably Jamougha is doing it this way but anyway you could try to make this summation a little bit more locally bounded just with the thing in mind to take the size of your bot into account in relation to this bins. -- rozu

A less massive smoothing can be found in some versions of PPP. From my memory:

double smoothedVisits(int index) {
    double smoothed = 0;
    if (index > 0) {
        smoothed += visits[index - 1] / 2;
    }
    if (index < FACTORS - 1) {
        smoothed += visits[index + 1] / 2;
    }
    smoothed += visits[index];
    return smoothed;
}

-- PEZ

Yeah, I've done that too. I've tried lots of things. This seems to work best at the moment. I think I have a bigger problem somewhere else though and that I'll revisit the smoothing thingy when I have localized that bigger source of error. Funny though that WaveSurfing "works" even when it's broken. Quite a few bots there from #6 and down that are doing the broken WaveSurfing thingy. =) -- PEZ

Yeah, I've been wondering about that. I suspect WaveSurfing when it's broken still works because the positional sensor, or stat array, or whatever, either contains essentially random noise or is being sampled (due to bad movement prediction) almost randomly, so in the end you're choosing your new destinations pretty randomly, thus making a nice flattener. -- Kuuran

Yeah, i suspect that's exactly what my "wave surfing" is doing, just moving randomly. except that it is more flat (about 5.2) then my previous non-"wave surfing" movement--andrew

I can think of one way to get around the GF1 problem: just don't smooth it! A reason not to is that since it has half the neighbors, it should just be left alone. -- Nantuko Primus

But smoothing it collects at least that half of neighbours. Not smoothing it would only worsen the problem. -- PEZ

I was smoothing my gun statistics in Jekyl with a simplified kernel density estimator. When I was doing so I had the concept of a "window" which represented the segment of my stats that I wanted to smooth (the window was based on enemy bot size at the current shot distance). I then slid this window "across" my stat array for that distance to find the highest peak and took the shot. Early implementations had a hard time hitting +1 or near +1 movers. To overcome the edge problem I added any windows that were not "covered" past the edge twice. So if I had a window size of three, when I was at GF zero, I added GF one in twice (once for +1 and once for -1). If I had a window of five, when at zero I added GF one and two in twice, when at GF one I added in one twice. Pictorialy here is the stats to be covered with the window size five: -2 -1 0 1 2 3 4 5. You have to have as many to the right as to the left from i=0 to i=3. I used some kludge for even sized windows which I can not remember off hand (I think it involved rounding down to an odd number). Whatever it was I am sure was really clever (LOL). Seemed to work pretty well for me. Your milage may vary.

Also one other implementation I have seen in the shooting world is what Kawigi does (or maybe did) in FloodMini. Again this is a shooting implementation but at some point it all comes down to GuessFactors. When figuring out which GuessFactor to increment, FloodMini used Math.asin(9.0 / bulletVelocity) in it's formula for figuring GuessFactors. This created an "unreachable" bin that could still collect stats. I think when he actually shot Kawigi used some formula to convert to "reachable" space. It is all a bit fuzzy now. Has anyone tried this as a possible implementation? Create "sidelobes" that are only there to contain data for smoothing purposes. When storing data, use them as a store. When shooting or WaveSurfing only use them for smoothing and use MIN_BIN +3 and MAX_BIN -3 (for instance) for everything else? Just a thought. -- jim

I think the problem to be solved is that if you don't have anything in those edge bins that you have, the real edge bins after smoothing still look like they have less visits than everyone else, so your tendancy is to keep going forward to get to those edge bins, even though they've been over-visited. -- Kawigi

Here is cool way to do smoothing its pretty easy to manipuates as to how spiked of flat it can make your stats

 Math.pow(0.5, Math.abs(index - count))   --- 50% decrease

 Math.pow(0.1, Math.abs(index - count))   --- 90% decrease

I find this method pretty usefull

Well Gorded, you gotta realize that raising something to the power of 1/2 is the same as taking its square root, which is what most of us do already. --Chase-san
Actually, he's raising .5 to the power of something, which isn't the same. I have tried a lot of formulas and never found them to make too much of a difference, but I still feel like it's something worth investigating. I generally use (1 / square((index - count) + 1)) these days, which I think I got from PEZ and CassiusClay. Simple and works well for me. -- Voidious
- Opp, yah, I saw .5 and pow... well, blaim the brain. --Chase-san

Lot's of talk about edge protection when smoothing on this page. Yet I don't think any of the top surfers of today (October 2004) is using it. Was it all a ghost? To me it makes sense that the edges should look more attractive than they are without this protection... -- PEZ

I use edge protection in Shadow's surfing, the edge repeat method works best for me.-- ABC

Cool. I think I'll try it again in CassiusClay. Lot's of bugs and stuff clouding the results when I tried it last time. -- PEZ

I recently overhauled my bearing offset (guess factor) gun and in the process I didn't bother with doing bin smoothing any longer. To make a potentially long story shorter .. my score improved slightly in the Rumble without smoothing. Given the tediousness of the implementation and the drain on processing, I'll leave it out until I'm really tapped for new ideas to try. -- Martin / Ugluk