Precise MEA

Ok, so while I await the results from the latest release to see if my new strategy works, I wanted to know two things: 1) What do the experts think about imprecise MEA causing randomness in targeting?

2) Does anyone have an efficient, accurate method for calculating MEA?

The worst thing I see with imprecise MEA is shooting walls.

Imprecise MEA is not responsible for imprecise targeting. Precise MEA only cuts off angles that are not reacheable by the opponent. Simply said, precise MEA has only advantages. The benefits of imprecise targeting on the other hand, can cause quite an interesting discussion. Imprecise targeting is not perse worse than precise targeting, f.e. random targeting can be a valid strategy against (very) good bots.

Scaling/segmenting your gun differently than your opponents dodging makes it harder to learn/dodge and can be good. As long as it doesn´t shoot walls (unreachable angles). DrussGT keeps changing its gun weights (segmentation) in the next version every time someone knocks it off the top and seems to be working very well.

Well, that depends on how you use precise MEA. For Gilgalad I was scaling bin size by the MEA So I think that the buggy / random MEA added noise to the GF's. Another interesting point is that moving ahead 0.5 GF and then back 0.5 GF won't always end at zero because the wall smoothing may make the 0.5 GF much closer to GF zero than -0.5 is. However, that is a problem no matter how you calculate your GF's. I haven't given it detailed thought, but I think that as long as the enemy is making enough random and independent movement decisions between when you fire and when the wave breaks, the [centeral limit theorem] proves that their movement porfile will still approximate the normal distribution (which is why I think bin smoothing makes sense). However, I am unsure whether having the GF's scale or not would allow better/faster learning.

If so-called "imprecise MEA" is shooting walls, then your segmentation is inadequate anyway I'd say. I can't say I've ever seen RougeDC's gun (Also, the 5th place Scarlet in the rumble) shooting the walls, yet it just uses classical MEA. Now, I'm not saying so-called "Precise MEA" is pointless, because it can allow you to have a fast-learning gun omit wall segments (or give them lower weight), but it CAN actually have caveats worth paying attention to:

1. The algorithms most people use for it are not perfect, and may underestimate how far robots can move by a small amount. Usually, this is not a big deal because the imprecision is smaller than half-botwidth and the vast majority of guns aim for the center of the enemy, but theoretically it could cause some distortion.
   I've never seen it implemented before, but a targeting system could account for the fact that at the it never needs to aim beyond the GF of "MEA - botwidth/2 + tiny_amount", and thus improve hitrate near the edges. This is risky though, because if your "precise" MEA and botwidth calculations are not significantly more precise than is typical, you risk an enemy being able to take advantage of this and avoid being hit.
2. If a bot uses the so-called "precise MEA" for scaling it's guessfactors (as opposed to just cropping), while it may sometimes learn faster due to being able to omit wall segments, BUT as the data collected increases, it may become less precise because it relies on an assumption about how enemies react to walls, which may not be entirely accurate.

1 - It may not be perfectly accurate, but it's a heck of a lot closer than Math.asin(8 / bullet speed). ;) And if your gun is capable of learning GFs > 1 there's really no danger in that.

2 - I think the only assumption it makes about walls is that enemies can't move through them. :-P

1 - Well yeah, I wasn't saying "precise MEA" is bad, just that one has to not forget that it still has error

2 - I disagree. It assumes they use wall smoothing, and don't react to walls in a significant other way. If those assumptions don't hold, then scaling-style "precise MEA" introduces an unpredictable error. I haven't tested but I suspect that if you compared "precise MEA" and "classic MEA" data against SpinBot, you'll get a sharper (and more predictive) image with "classic MEA" ;-)

Well, neither would hold a candle to Play It Forward against SpinBot... ;)

Precise MEA's advantages are certainly strongest against wall smoothing movements, but I still don't feel it assumes that any more than traditional MEA assumes there isn't a wall at all. If they just bounce off the walls and end up at a negative GF, wall distance segments will cover it just as well either way. If they just run into the wall and stop, you're right that a traditional MEA might be more accurate, but a raw bearing offset would be even more accurate (orbital wall distance would map exactly to firing angle) and I doubt anyone's advocating that.

I prefer Circular targeting to Play It Forward against SpinBot :P. But then, Circular targeting only performs better (instantaneous learning) because it makes different assumptions which happens by luck to be right.

The power of GF with (precise) MEA is its assumptions hold true to a greater number of competitors in RoboRumble than Circular targeting. If everyone in RoboRumble used circular movement, GF would suck.

It scales differently, though. The precise MEA is calculated once (in each direction) no matter how many data points you're aiming with. If you're trying to use 500 data points and aiming with DVs, that's 500 projections for out of bounds checking.

Diamond's 1v1 gun used to use DVs, but I saw a big jump in accuracy when I finally caved and switched to GFs. Still use 'em in melee, though, and think they're very cool.

What if we mix together ideas from DVs and non-iterative wall smoothing to calculate a more accurate MEA than simply using asin(8.0/Vb)?

Imagine 2 DVs, one trying to go as far as possible clockwise and the other counter-clockwise. Ignoring walls, the resulting angles will match asin(8.0/Vb). But when near walls, if we adjust those 2 DVs, like wall sticks are adjusted in wall smoothing, we get a more accurate MEA, using non-iterative trigonometry only.

I looked at this, the problem it has is that it doesn't take into account that as the angle changes the wave will hit sooner. You could account for this I guess, but the iterative predictive methods are fast enough, I think.

Something like non-iterative linear targeting can account for varied bullet travel times. But the resulting code will probably be very bulky, like most non-iterative methods.

Well, I didn't use a noniterative method and I actually don't know how I could, but I now use a "binary search" for attack angles to get a precise MEA that doesn't take heading or velocity into account. I may make a page for it with diagrams, but for now you would just need to look at the code to see what I mean.

I tried a non-iterative MEA in Combat and it is working quite well. It doesn´t take velocity and heading in account, but it does take walls into account.

I modeled the problem as 2 intersecting circunferences (bot moving and bullet moving) and 1 intersecting line (wall). There are at most 2 points where the 3 intersect. Then repeating it for all 4 walls for 8 escape points. Add the 2 escape points from classic MEA (ignoring walls) for 10 escape points. Do some out of bounds checking on all points and then find which remaining 2 gives the widest MEA.

There are some loops but they are fixed and independent from bullet travel time. Making it very cheap to calculate.

I can post the algorithm later.

I don't iterate to find the bullet flight time. By iterate I meant for my binary search.

I'll try to get a better answer with diagrams soon, but I will be gone over the weekend so it may not be ready until Monday. One thing I was thinking about was Bearing Offset Normalized by Reasonable Travel Path Index targeting (an excellent name right?) where the bins would be scaled non-linearly. So, if I started wall smoothing at GF 0.5 then 0.0 through 0.5 would all be bins of similar size, but 0.5 through 1.0 would be a different size. However, I haven't tried it yet because I have had other things to do and I don't think it would be much of an improvement on precise MEA. However, the main issue I have, with all GF targeting algorithms, is basically that a robot going forwards 0.5 GF's and then back as far as it can will not necessarily end up at GF 0 due to wall smoothing. I cannot think of any solution to this problem (besides simulating the enemy's movement with the same algorithm from an identical list of random numbers) but I think that changing the bin size might make the problem worse.

That being said, I have to admit that my imprecise MEA didn't seem too bad. However, I think this was because the wallsmoothing approximation that I used will work as long as the enemy starts facing a certain range of directions. Because wallsmoothing is so common and this range of directions was basically that a robot would use while wallsmoothing, that wasn't a bad assumption, but I don't like making it.

Wall segments only avoids shooting walls after the gun learns how the opponent reacts to it. So at least in the first round a gun can shoot walls.

First round, an opponent dodges the first bullet at factor 1.0. Then it gets close to walls, factor 1.0 (imprecise) is unreachable, it crashes on the wall and "dodges" the second bullet at factor 0.0. There is only 1 wave in the history, so a GF gun without precise MEA will use factor 1.0 (imprecise) and shoot the second bullet at the wall (and make your bot look stupid).

Now, which of the two is better, cropping or scaling, varies with the opponent.

True, but I'd say it can be learned away much much quicker than 1 round even, especially when tick-waves are used.

About cropping or scaling, yeah... I'd say the tradeoff comes down to a matter of low-distortion (fewer assumptions) versus fast-learning (reduced segmentation needed). The best choice depends on all sorts of circumstances. With 1) a sufficiently large number of rounds, 2) good wall segmentation, and 3) non-learning opponents, cropping will just about always be better. Conditions #1 and #3 may frequently not be the case though, so yeah.

What I have been thinking about trying when I get around to actively robocoding again, is including both scaling and cropping, and use both for deciding each shot. Possibly ways to do it would be averaging the probability curve for both, or picking the one that gives the strongest prediction, among other possibilities.

Are tick-waves any good against surfers? Intuitively, they should perform worse, so I never tried.

They seem to work well against surfers. I recall someone, I think rednaxela, saying that this is due to surfers usually not simulating non-firing waves. I currently use them, but I do weight firing waves higher (Diamond uses an oscilating virtuality attribute that weights waves closer to firing waves higher)

I certainly use them against surfers, but accuracy against top surfers is kind of a black art anyway. =) It's worth noting just how much data there is in virtual waves - you're talking about 1 data point every 15 ticks vs 1 every tick. That goes a long way in making up for the fact that they shouldn't be as relevant. And yeah, I use virtuality as one of the attributes in my KNN distance function, so I prefer waves closer to firing time when selecting data points.

1) I think precise MEA (with scaling, as Rednaxela is talking about above) is simply a truer mapping of a random mover's decision making process to firing angle. Random movers may decide "I'll move this direction for X ticks" or "each tick I have an X chance of reversing direction". If they never reverse direction, with precise MEA they'll always end up near GF=1. Without precise MEA, where they end up is all over the place depending on wall distance.

With precise MEA, wall segments can still be used to refine the data and learn about dive protection, while without it, they have to learn how wall distance impacts MEA and dive protection. So I personally don't see why imprecise MEA would be better after enough rounds, with good wall segments, or against non-learning opponents. I might concede "probably just as good after enough rounds", but "after enough rounds" is quite a caveat ;), and it would have to be "better" eventually to average out to even be "as good" over the whole battle. I also might concede "not worth the CPU time", but I haven't found a better use for it.

In my mind, raw bearing offsets are to GuessFactors what imprecise MEA is to precise MEA.

2) I don't know of any efficient algorithm for it. I simulate movement (with precise prediction) without wall smoothing, with wall smoothing, then reiterating the with wall smoothing a couple times to move more directly towards the farthest reachable point. I also add an extra 10% to that, though it doesn't matter because my gun could learn GFs > 1 if they happened. The only way I know of to really optimize this is with a lot of precomputed stuff in a giant lookup table, like "Fast Math" classes.

Oh, with regards to the efficient algorithm question... I have some prototype-stage code around for pre-calculated movement tables that cover maximum reachable area. It works pretty nicely though I've yet to put it in a robot. These tables would make for a very efficient way to estimate MEA. (I came up with this code for the purpose of creating a super-fast surfing algorithm that can skip normal precise prediction)

That said... generating and using those tables is awfully messy to code (lots of awkward tricks to minimize table size without sacrificing useful data) ;)

I was trying not to blow your cover in case that was a super secret weapon you were going to deploy sometime, but I figured it's been long enough in the making that I could drop a hint. ;)

This way I´ll probably end up copy-and-pasting all Rednaxelas fast algorithms in my bot. I put FastTrig already and it tripled the FPS. Thinking in putting Rednaxelas KD-tree as well (will probably triple the FPS again). Although I don´t see a fast MEA helping as much since you can cache MEA inside waves.

So, if you don't mind giving a few more hints would the tricks include rotating the battlefield so that you only need to save the information for one wall or something more complicated? As for using Rednaxela's algorithms, I like to code my own, but I fequently check his to see great ideas that I didn't think of.

If I'm understanding the terminology correctly, in older versions of XanderCat I used cropping in the gun (using basic MEA calculation as a base but only shooting where my predictor claimed the opponent could reach). However, in the latest versions I use scaling in the gun (maximum reach based on the predictor mapped to the end bins). I do not use scaling in my wave surfing drive, however. Others results may vary, but in my robot, scaling improved performance in my gun but reduced performance in my drive. For what reasons I haven't fully analyzed.

And of course, then there is the question of how the bins are scaled across the MEA range. I did a little drawing on some approaches on a precise MEA discussion. For my gun, I currently use evenly distributed bins (image 3 of my awesome MSPaint diagram on the Precase MEA discussion page), which has the interesting aspect that the 0 factor location for me is not fixed. I have not fully researched the effectiveness of differing approaches on this.