Zoom Targeting

ZoomTargeting is a hybrid of StatisticalTargeting and a new form of PatternMatching and should combine the best of both worlds. It uses SegmentedData (currently 6 dimensions) and gets this data using a variant of Waves.

Its StatisticalTargeting properties should make sure that

• it is very good at long term learning and continues to improve even in very long matches
• it can exploit weaknesses such as spikes in the enemies MovementProfile
• it can do a good educated guess when PatternMatching fails (when there's not enough data in the microsegment)

Its PatternMatching properties ensure that

• it adapts very fast to new enemies or situations.
• it can exploit weaknesses such as dodging and other types of repetitive movement
• it can get a reasonably high hitrate early on in a match if there is no stored data
• it can be more accurate than StatisticalTargeting (if there's enough data in the microsegment)

The new thing is that this targeting method basically zooms in (more PatternMatching) or out (more StatisticalTargeting) depending on the amount of data it has and the zoom level's segment size. Currently I use 8 zoom levels with increasing segment sizes. PatternMatching takes place in what I call the MicroSegments. In these tiny segments even only 1 previously reported angle is enough to deliver a firing angle with a high probability of hitting the enemy. StatisticalTargeting takes place when you zoom out, in the MacroSegments. The segments here are much larger and contain more data to do statistical calculations with. Learning speed increases when the zoom level increases.

The PatternMatching algorithm that I use differs greatly from traditional PatternMatchers. You might even argue if it is PatternMatching at all. I call it PatternMatching because it matches to a very specific situation. As a result it performs very well against bots that other PM guns perform well against :-). A situation is basically a very small segment with a lot of dimensions. Currently I use 6 dimensions, but if I can solve a memory issue I will use even more. I might even try a dimension that uses the movement history to make it a more official pattern matcher :-). In practise, this algorithm is a bit less accurate against truly predictable movers like SpinBot or PatternBot, but more effective against random movers. And since none of the top bots are truly predictable.........

There is a nice side-effect to using MicroSegments: I keep track of the number of Segments ('situations') that are used. This number increases more rapidly as the enemy has better movement. I am guessing this Segment count (say after 1000 rounds) could be a nice alternative Movement Index.

-- Vic Stewart

How far are you in developing this awesome gun?

• The next step is to implement the Statistical calculations of the macrosegments.
• decide whether to fire a Wave every scan or along with a bullet.
• better memory management

Yeah, yeah, yeah..... You talk the talk, but does it walk the walk?

• So far the results are very encouraging. I was unsure if the new PatternMatching algo would work, but it does! For instance, it beats all but one of the samplebots in a 10 round match, without stored data, whilst being stationary. (only TrackFire is a problem but that's due to a known bug)
• I tested against one of the challengers in the PatternMatcherChallenge and with just the new PatternMatching algo I got its index down from 32% to 25%. I wonder what will happen when I add the StatisticalTargeting part....

Sounds great, can I help in anyway?

• Yes you can :-) I have two issues:

Memory issue

Currently I am reserving memoryspace for every zoom level whether it is used or not. I use a simple (6 dimensional) array for that. The drawback of this is that memory is reserved for segments that I never use and memory soon spins out of control. Now I want to implement a dynamic array (Vector or ArrayList or something). The question is, which type of dynamic array would be most suitable for this situation? Most importantly I require the lowest possible memory footprint.

-- Vic

Both an ArrayList and a Vector would work here. The constructor for each allow you to specify the size of the Arraylist to be built. They will also grow as more items are added to them. The "growing" part can be expensive in terms of CPU cycles so you will most likely need to play with them to see how it works out with skipped turns. Of the two, I would imagine that the ArrayList would be more appropriate than the Vector. I am also unsure if this will buy you anything in terms of memory footprint as I think in the end both classes use an Array with wrapper methods to implement their functionality. -- jim

LOL, I already implemented this gun about three months ago for Statistician -- it's sitting on my hard drive right now. This gun was the main feature of Statistician (and his namesake) and it will be one of Tax's main guns. You can probably find me talking about it here and there on the wiki. Although, it will be better implemented in Tax due to the ability to segment stats more intelligently with his neural network. Oh, to answer your question, I used a HashMap that stores strings of movement. For instance, if I tokenize a bot's velocity into the letters a-p, where a is -8 and p is +8, then I might have a string that looks like this: "aaaacegiiii". I stick that in the HashMap, along with a two-dimensional array of all my segments, and I just update the array as I need to. This makes sure that you only use memory for the patterns that you have seen, and it is a very fast pattern-matcher. -- nano

Interestingly, this approach also allows an infinite amount of "zooming". Of course, there are memory limits, but I ran my algorithm at a maximum of 200 frames of movement, and it ran fast with no memory problems. Thank God for a fast and efficient HashMap implementation. -- nano

Ok, thanx. What would I use for index if I'd want to implement an ArrayList? Say, for instance, in my original multidimensional Array I want to access Angle[0][1][1][0][1][1]. I need to do some sort of mapping from the 6 original indices to a single one. A possibility might be to convert these indices to a single integer, in this case ranging from 0 to 63 (6 bits). But can I insert the Angle at position 54 [ArrayList: add(54, Angle)] without my ArrayList or Vector immediately reserving memory space for the preceding 0 to 53? I think not, but I'm not sure. Does anyone know for sure?

That probably means the HashMap is the better solution. I can put my single Index 54 in it along with my Angle value [HashMap: put(Indexobject, Angleobject). However, a HashMap stores both key and value objects. Suppose my original value to store is an int. I now need to construct a wrapper object for it, an Int. Also I need to construct an Int object for my key. Assuming an Int takes equal memoryspace (it is just an int with wrapper methods, right?) then I must conclude that using a HashMap requires double the amount of memory PER ENTRY. So, if I have less than 32 entries I should use the HashMap, else I should stick to my original Array. This is getting complicated... Although I think that in practise I almost never will get more then 32 MicroSegments per Segment. I'll try the HashMap and report back if it works...

-- Vic

It might be more sensible to just use a binary string instead of using an Integer object (might as well use java.lang.Integer, though, if you do that), meaning you would access the said angle by using map.get("011011") or something. Might be simpler. If you use the array thing, it might make sense to just go ahead and allocate the thing (4 bytes * size of the array for that many null pointers), it may not be a big hit when it's empty anyways. If you know some segments won't be hit, though, that's a consideration (particularly if it happens to be a lot of segments) -- Kawigi

It would sure be easier and more readable to use such a binary string. But how does the HashMap store this? I guess it would generate a hash number so it will not use more memory then using my Int.. Is this assumption correct? -- Vic

That should be correct. If a HashMap turns out to be weightier than you can handle, you could also try just implementing your own Hashtable. For even more efficient memory (but a compromise on speed somewhat), you could throw everything into a BST or something. -- Kawigi

Binary Search Tree I presume.. Hmm gotta think about that tomorrow....it's getting late here. By the way, I already tried using a normal array and memory consumption goes through the roof, even with a high percentage of nullpointers. -- Vic

Kawigi, I don't understand how I would use a BST in my situation. I'm still interested since you spoke of more efficient memory so could you explain a little? But for now I've decided to go and try make my own container class. I only need a byte (8 bits) of memory for my key and I'm pretty sure all the java.util containers use an int (32 bits). Besides, it's a good exercise :-) -- Vic

Well, you sort them into the BST by key. The root key can either be the first MicroSegment you use, or an intelligently chosen constant one. Then you sort new MicroSegments into the BST as you have them. It shouldn't really ever take more memory than it needs, and in the best case, look-ups and insertions are O(log(n)). In the worst case, without intervention, look-ups are O(n), which probably isn't what you want. You can reduce that by a constant (in half, actually) by picking an intelligent root node all the time. If you think look-ups are more common/time critical than insertions, you can do checks to make the tree more balanced for consistent O(log(n)) look-ups at the expense of some checks and possible AVL rotations within the insertion part. -- Kawigi

Just use a TreeMap. ;) If memory is a problem with a HashMap (it was never really a problem with mine -- do you have less than 256MB?), then you can try it with a TreeMap. If that isn't sufficient, then consider implementing your own structure. These two Java implementations are incredibly fast and efficient (though they can be improved upon), and I would definitely try both before hacking it out on my own. -- nano

Ok, I've used the HashMap in the end and ... hey! it works :-) Even without optimizing initial capacity and load factor the memory consumption is a fraction of what it was. Thanks for your help guys! -- Vic

This is belated, but have you considered BSTs? -- Kuuran

Ok, next time read the page first. Umm.. the best way to imp a BST for future revisions is probably to keep it sorted on numerical key, the way you first proposed, with each number being a 6-bit long bit vector (with a couple bits of wasted memory, since you'll no doubt be using shorts for this). Then simply fly through, find your object, use the reference to get whatever data is attached to the key, et voila. Since memory consumption and readability are issues, simply use the binary operators for everything, they ensure every bit represents something instead of every byte, long, double or whatnot, this is cutting your memory consumption severely, and they maintain easy readability, everyone knows what's happening when you binary OR or AND values. BSTs also have the property of growing/shrinking to accomodate only the given data, just make sure to do your housekeeping. -- Kuuran

Multiple choice issue

Suppose I have a segment with data and I want to calculate the best angle that would have the most chance of hitting the enemy.

some ascii art:

         -47_______*_**__**_____________________0________*_______________*_*____*_*______+47 degrees

The * means a previously observed succesful targeting angle. I can clearly see that i should not take the average angle (AveragedBearingOffsetTargeting) This data shows me that there are two spikes, one at -30 and one at +30 degrees. The -30 angle has the most occurences and has a narrower spike, so this is the angle to choose.

I could of course calculate the angle range for that specific distance, loop from -47 to +47 and determine at what angle the most occurences fall within the angle range. But that would mean a loop within a loop (times number of zoom levels) so the performance would be not so good.

I could also calculate the angle range for that distance and iterate over the occurences, determining which occurence picks the most neighbouring occurences. Again a loop within a loop, but this time both loops are limited in size. And the result may not be optimal in some specific situations....

So, what would be the most elegant way to calculate this angle? Is there an algo with only one loop?

-- Vic

• I've just thought of an algorithm with 1 loop, although I'm not sure if you're around to hear it =). Basically, you calculate the bin width for the distance. Then you iterate across, adding the value of the bin on the right and subtracting the value of the bin on the left. You store the value and index of the best position, and if the current value exceeds the best value, you set bestValue = currentValue; and bestIndex = currentIndex;. I like FastBots. =) -- Skilgannon

Well, I've thought about this some, as I also do statistics with waves, and it seems like it would be more accurate to use those old-school virtual bullets, because *every* bucket that hits is recorded (and as you observe, you want the mode, not the mean). There are two ways I've thought of to tune this - the first would be to collect data the same way and then figure out how wide of a margin of error you are allowed. The eventual calculation does take a loop inside of the loop, but the inside loop would be trivial. The second way would be to have your wave bullet tell you every bucket in your array that would have hit. In this case there is much more to do toward the end of the wave's life, but calculating the angle is as simple as finding the index of the max. -- Kawigi

I have just the same problem with a new pattern matcher I'm developing. At the end, I get N bearings distributed in a line and I have to choose the best place to fire. None of the approaches I have testes satisfy me: Sometimes granularity is to big, sometimes to low... Now I'm using an approach of segmenting it it lets say 6 overlaped parts, search for the one with the higher density, zoom into the segment, do it again, and so on. But I'm thinking seriously in using a NN to learn the best bearing from the distribution. -- Albert

It seems to me that a binary tree structure would be perfect for this. The top node will have the total number of hits, then its children node will have the total number of hits on the left, and the total number of hits on the right side, and their children will be split up left and right as well, and so on. Then you can choose which level to shoot at based on the hit percentage for the best node at each level among all sibling nodes (nodes which have the same parent). For instance, at the second level you have full left and full right. Let's say after you have 100 measurements, you have 60 on the left, and 40 on the right. Then on the next level you have 40 20 10 30, from left to right. Then you will shoot at the third level, because 40 / 60 is a better percentage than 60 / 100. Of course, margin of error should play a part in this calculation as well. You could choose based on the highest minimum percentage after margin of error, or the highest percentage (probably a bad idea), or you could randomly choose based on the amount of overlap among all of the choices (that's how I do my dynamic distancing).

For instance, in this case, the margin of error for the 40/60 measurement at 95% confidence is 1.96 * sqrt(0.66 * 0.33 / 60) = 11.9%. Thus, the minimum hit percentage is 66.6% - 11.9% = 54.7%. For the 60 / 100 measurement, we get 60% - 9.6% = 50.4%. Therefore, we will choose the third level of segmentation (which is a particularly good term for this structure), and we will fire full left.

As for using a NN to learn the best bearing...how will you train it? It seems to me that it is a statistical problem no matter how you look at it -- though I suppose a kind of fuzzy logic would apply here. I don't know anything about that though. Have you done any research on using fuzzy networks to do statistical analysis?

-- nano

Well, I have a cloud of points (always a fixed number of N points) and I know the right bearing to hit for all my historical data. So I just have to train the NN with input vector (PredBearing1, ... , PredBearingN) and output value the right bearing to hit. What I want it the NN to decide which way is better to "average" the bearings. I think it should work, but I haven't tried it yet. -- Albert

nano's idea of dividing it up and going in the direction where there are more is what I did with my first stat gun (although it didn't work at all) in SpareParts. -- Kawigi

Here is an old idea I had but never got around to: how about using Java2D rectangles to represent the enemy in the hit positions, then take intersections of these until you find the point with most intersections? -- tobe

Sounds pretty CPU-intensive for thousands of rectangles, but I'm sure it could be optimized somehow. -- nano

If you found thousands of matches in the pattern-analyzer, that would be a big hit :-p Of course, on the statistical side, that's still a problem. -- Kawigi

Thanks folks, there a some nifty solutions mentioned here.. however most of them seem not appropriate for my situation. My use of MicroSegments means that I have A HUGE NUMBER of them. That means I must minimize my use of memory. I think I'll try my own second option (which is basically the same as Kawigi's first option). That way I'm sure to minimize the amount of memory taken up (only the actual angle values, nothing more). Performance should be ok, and I'm only losing a slight bit of accuracy, but I actually think that this is discardable. -- Vic

Once again I haven't read this page fully yet, but here's my solution: Do a one-pass loop of all your data. Initialize an array of 95 ints (they represent -47 to 47). Set a variable (let's call it x) to 0 at start. Each pass of the loop look at your next n degrees. n is your first tuning factor. For each hit you have in the next n degrees, increment x by one. Dump that value in the element of your int array corresponding to the pass if the loop you are on. At the end of the pass, decrement x by some value. One is a tempting value here, but it's obvious that it will quickly become unable to lower x 'fast' enough, so I'd suggest this decrement value be a function of your total waves fired (total waves / 95, for example). This function is your second tuning factor. Scan through your array and the highest value should be your best guess angle. There is an issue that this might bias it towards the +47 side. I'd recommend the solution to this be you do this loop twice, once counting up and once counting down, then add up the corresponding elements in each array into a third array, then scan this third array. This will eliminate that bias if you find it becomes an issue. This should also be very fast, it's essentially a one-pass algorithm. Whether it works reliably or not is another story, I just thought most of this up while typing. -- Kuuran

No comments? -- Kuuran

Ooops... Must have missed your entry when this discussion was going on. Sorry. Anyway, I solved my problem using Kawigi's idea. Basically it's just converting the bunch to a guess factor array. In my case I also take bot width into account. --Vic

Development stage 1

developement stage 1:

firing waves:

• fire waves when firing a new bullet, store parameters that quantify the Situation when the wave was fired
• when a wave hits the enemy, calculate the gunbearing that would have hit it
• propagate the angle through a multidimensional tree structure
• if the Situation is new for any node in the tree then create a new node and store the Angle there
• if the Situation already existed, then replace the Angle stored there with the newly observed Angle
• recurse deeper into the tree until the Situation parameters cannot be further divided

aiming:

• ask the treemap for the Angle stored in the Node that most closely resembles the Situation

After thorough testing of the properties of this gun I realise that in this stage it's not yet competitive gun against the state-of-the-art guns. You'll find that it loses to the top bots. It's about equally effective as normal PatternMatching guns. (So not bad...)

good things: - it learns very fast.. in early rounds of a match (no saved data) it beats most other top statistical guns. I hope i can retain this property when adding MultipleChoice in /Stage2. - its performance is very fast (maybe it could be on the list FastBots;-). - it punishes the enemy if its movement is not flat in short timeframes.

bad things: - it learnes slower than top stat guns in later rounds, because it is lossy in the lower segments. - it still uses a lot of memory, although it is now capable of running 1000 rounds without crashing my system :-). - it cannot punish the enemy if its long term movement profile is flawed (not flat), but its short term movement profile is flat.

---

About its ability to find non-flat movement in short time frames. Only in certain conditions I think. Since otherwise it would have spotted the weakness of the Tityus 0.2-0.3 movement. You should probably keep that version of the movement just for testing purposes. I know I will. =)

• yes .. that is strange .. it sometimes gets the weakness, but not nearly as good as DT does .. I think that it is because Tityus moves between segments too quickly. I'll have to think how (and if) i should solve this -- Vic

When it comes to finding weaknesses in the long term profile. If it's really there you should be able to zoom out, shouldn't you? Maybe if you could use a virtual guns type of approach with different zoom levels? I don't really understand the theory behind zoom targeting so I might be way off here.

• Currently the MacroSegments don't yet have statistical properties, so they are much less accurate then the MicroSegments. The virtual gun type approach is in fact also part of the design. Each segment will have a hit ratio and when aiming I will choose the segment with the highest hit rate. In the next stage I will implement this. -- Vic

Can't you post your TargetingChallenge results with ZoomTargeting and your pattern matcher for reference? Especially the latter one would be interesting to keep there since it is one of the guns in the MovementChallenge.

• I already posted the results for Mazer, which has the ZoomTargeting gun WITH MultipleChoice stats in the MacroSegments. I'll post results for PatternMatcherBot also. --Vic

PEZ

Targeting Quick Head-On · Linear · Circular · Random · Mean · Area · Head-Fake Statistical Laser · Avg Bearing Offset · Factored Angular · Visit Count Stats · BestPSpace Log-Based Pattern Matching · Dynamic Clustering Heuristics Neural · FuzzyLogic Hybrid Symbolic Dynamic Segmentation · Zoom Targeting · SmartFactor · Anti-Surfer Firing Angle Bearing Offset · GuessFactor · Play It Forward · Displacement Vector Energy Selecting Fire Power · When To Fire Terms Bullet Travel Time · Waves · Multiple Choice · Max Escape Angle Related Targeting Challenges · Segmentation · Chase Bullets · Virtual Guns · Saving See Also: Category:Targeting