WaveSurfing/ReverseForwardSensors

Robo Home | WaveSurfing | Changes | Preferences | AllPages

Difference (from prior major revision) (no other diffs)

Changed: 22,68c22

I doubt this is the way to do surfing at all. Not that I'm sure of it, but I think looking ahead farther and predicting where you could go is better. -- 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

YALT doesn't do bin smoothing. Seems to work ok. Maybe that's "THE Bug" for me, I'll try smoothing. :-) --David Alves

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

I'd say that when YALT reaches 1960 points or so that it's working OK. =) WaveSurfing done properly should get you at least that far in the current rumble environment. 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

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

I doubt this is the way to do surfing at all. Not that I'm sure of it, but I think looking ahead farther and predicting where you could go is better. -- PEZ

/PrecisePrediction is nice. But it could be hard to fit in a minibot and also can be pretty nasty to implement without bugs. A much easier technique is to only (roughly) predict your future position one or two ticks away. Calculate where you'll be if you'd reverse and where you'd be if you "stepped on it". I call these positions reverse and forward sensors respectively.

To make this work you need to have enough bins in your stats array to make the reverse and forward sensors measure different bins. But you also need to do major BinSmoothing in order to avoid optimizing for local minimums and therefore get stuck in non-optimal positions.

Bots using:

Pugilist 1.4 -> 1.4.4

Comments / questions

so is this a way of doing true surfing? i guess i am doing this right now in R2d2, but i don't have any bin smoothing at all. maybe that is contributing to my badness. before i read this , i assumed it was kind of an optional thing, but you say it is neccessary. so i'll look into bin smoothing for my bot soon. --andrew

You don't need to have enough tons of bins to make sure that the bins aren't the same, just do what YALT 1.3 does:

if(forwardBin != reverseBin){

   //pick new destination

} else {

   //continue using the last destination we picked.

}

I doubt this is the way to do surfing at all. Not that I'm sure of it, but I think looking ahead farther and predicting where you could go is better. -- PEZ