Segmentation/Old Discussion

I have started to make the forray into a Statistcial gun. I have heard people speak of segmenting the data. What does this mean and what are ways in which the data can be segmented? Thanks -- jim

I think I might be one of those talking about segmenting the data. With this I mean to keep different statistics for different "situations". Check the MakoHT/Code for a very brute and simple way of doing this. MakoHT (and pre-1.4.2 versions of Mako) uses three segments, all based on lateral movement.

• The enemy is traveling leftwards
• The enemy is stationary
• The enemy is moving rightwards

MakoHT uses two types of guns, both using a factor. It keeps three factors for each gun. I think that while I can't recommend the way MakoHT does it code-wise that the code well illustrates this.

Marshmallow started out by segmenting the statistics based on distance;

• Close
• Midrange (Called "Normal" in the debug output)
• Far

Newer versions uses nine segments, 3 lateral x 3 distance. Check the output window of Marshmallow 1.4.5.1 and you'll see it output it's virtual guns statistics for these segments. Most often it prints the lateral segments for the midrange distance segment. I won't tell you which gun is which, but the first one (number 0) is a direct-targeting gun and the fifth (number 4) is the pattern matcher.

I can give my strongest recommendations to start segmenting your statistics. This alone is one of the major things you can do to climb the rankings. But it has its drawbacks. The main one is slower learning. Marshmallow tries to counter this by accumulating segments. Only half-succeeding. -- PEZ

FloodMini (a statist himself) segments his statistics into a 3-dimensional array. The first index is the opponent's LateralVelocity at fire-time - a segment from 0-2, 2-4, 4-6, and 6-8. Against most bots, the most important ones are the 0-2 and the 6-8, and the other two look similar because they are the accelerating/decelerating segments, but against some bots that use intermediate speeds a lot (the other flood robots) and some robots that don't move perpendicular to you as much (like Tron), they are still quite useful. The second dimension is distance (segmented every 50, you could say that's too frequent, but I think bots that are trying to control their distance typically are doing it on multiples of 50, so that's why I decided to use it). The third dimension is the "virtual bullets" - what range the right answer occurs in. I avoid the segmentation of negative/zero/positive lateral velocity like PEZ described by multiplying the angle offset by -1 if the opponent's lateral velocity was negative when the bullet was fired (or if they were standing still, their last lateral velocity. I still keep the advantage that they will be in the first LateralVelocity segment in my statistics if this is the case, so I don't ignore stopping). Since both directions are essentially equivalent for most opponents, this helps me learn twice as fast. -- Kawigi

I beg to differ on "both directions are essentially equivalent for most opponents". Marshmallow tells a different story. Different guns are often used in the the leftwards dimension than the rightwards for most opponents. If it's worth the slower learning I don't know. I might try to group those two segments together while having small samples... -- PEZ

A future MegaBot statist gun may add a dimension for "last seen accelerating" and "last seen decelerating", and a dimension for the bot's relationship to the wall (segmenting on "would hit the wall if they went straight for 100", "would hit the wall if they went straight in the opposite direction from where they're going for 100", and "aren't close to a wall"). I'm convinced that most bots, even with good movement, have a weakness in movement often near the walls. -- Kawigi

Thanks for the feedback. This is something that I am already doing, at least for distances. I had not considered adding in a directionality to it. This may be my next enhancement to my development gun. jim

My current bot (Statistician) uses the same technique that Kawigi describes for lateral velocity, flipping the angles around instead of using an entirely different bucket. Statistician also has guns that segment based on past acceleration (1 for accelerating in the direction of the current velocity, -1 for accelerating in the opposite direction), past directional velocity, and past wave angle. All of his guns are also segmented based on bullet time instead of distance. This allows him to actually be able to hit with low-power bullets. -- nano

Working on past acceleration versus past velocity is really intelligent. Might pick up a few that would evade the stat gun otherwise. As for the near wall testing, definitely something to implement. Most robots use deterministic patterns to move away from walls, or at least discard some random ones to avoid crashing into the walls. This means there is a significant spike in determinism, and additionally, the possible statistical curve is cut down by alot, so it's easier to learn even if the bot is keeping it's near-wall movement as random as possible. Of course, among the variety of strategies to force people onto walls (notably firing to force antigrav to a wall), this is really only a rehash. Walls and corners tend to cause 1v1 problems in a big way whether or not you're learning to hit them better. As a result, it'd also be exceedingly difficult to test this gun's actual performance enhancement. -- Kuuran

I thought I'd mention here what FloodHT's been up to in this category. FloodHT 0.8 currently segments his statistics on distance/bulletspeed (not a bad idea, nano, it doesn't work as well against a few robots, but overall I like it), lateral velocity, acceleration (if the current velocity is within .5 of the previous velocity, I consider it to be constant speed, I can't remember if I use actual absolute velocity or absolute lateral velocity for this), and whether or not they would hit the wall if they went straight in their current direction for something like 100 pixels. FloodMini does something similar, but he only uses distance, the acceleration is based on actual velocity I'm pretty sure, and the wall segment comes into play if they would hit the wall going straight in their current direction at their current velocity for 10 turns. And then FloodHT also seperates melee from 1-on-1 stats. If I were 100% confident that I would still have a fast enough learning curve, I can think of two more things I may segment on in the future - AdvancingVelocity (would give me a better picture against Tron I'll bet) and time since last change in lateral direction. I'd even consider segmenting on the time before I would consider changing direction, if it gave me more accurate stats against top robots. The thing I like about such segmentation is that I can 'classify' the current state of movement of my opponent to the same degree as the original pattern-matchers could, but then I can take a much larger sample of experience to choose a shot angle. If a robot pattern-matches and finds a pattern of length 10 or so, often all the robot really knows from this is whether they're accelerating or decelerating, how long they've been doing that, and maybe when their last change in direction was, and they often use that one sample to guess what they should do next, where I take all samples that are similar in situation to what I'm seeing and I make my decision on the collection of data.

I've mentioned elsewhere that I'm trying to remember some of the statistics that I used to basically understand. I'd like to be able to take different cross-sections of my stat buffer and rate the viability of the data there. The main problem with adding these extra segments would be that I'll start out with each enemy with even more empty segments, and all FloodHT can think to do with all those empty segments is try head-on targeting. What I'd like to do is have some intelligent system where I try every cross-section of my stat buffer (one that is just all the stats with no segmentation, one that segments on distance, one that segments on lateral velocity, one that segments on both of those, and so on) and I get a gun offset as well as some sort of number that tells me how sure I am about that gun offset. I assume that this number would be proportional to the sample size (although probably not linearly) and it would probably include other factors. I've also thought that it would be inversely proportional to the variance, or possibly the variance from the mode (since I'm using the mode, not the mean, to fire). FloodHT 0.7 had the ability to look at any cross-section of its stat buffers, but didn't do anything incredibly intelligent with it, except for mass-production of VG's that FloodHT couldn't figure out were inferior in the long run. I used it to attempt to declare certain parameters irrelevant to firing against a certain opponent, when what I really did was make my firing worse when those parameters would have been relevant. If I had some kind of function that would recognize that I have insufficient data in some segments and use a broader segmentation, but recognize that I have better, more precise data when I do have enough, I wouldn't have to fear the loss of learning speed from adding more segments to the gun, and space for saved data would be my only worry. If anyone has any idea on how I could rate the various cross-sections of data that I have, then, let me know. -- Kawigi

When Marshmallow comes across a close-to-empty segment it accumulates it's "neighbouring" segments to choose a shot angle. Could you do something like that maybe? -- PEZ

I've considered doing some of that as well. Actually, while I haven't had much success and I probably have a bug in it, I tried making an averaged bearing offset type gun once that had very small segments and would adjust all factors every time a wave hit using a rolling factor that was inversely proportional to the difference in the factor and the actual specs for the wave. I don't know if any of that made sense, but I was thinking of it as basically an over-simplified neural sort of system. And I digress... I actually have a funny prototype of the system I was describing that's based off of FloodMini. However, it's somewhat unpredictable, and doesn't seem to start with more loosely segmented gun and then lock on to more highly segmented guns like I want it to.-- Kawigi

About distance segmentation. In some of my bots I also segment on bullet travel time and I will probably go that way with Marshmallow as well. I started with it when I realised SandboxDT does it and after some thinking I came to the conclution that mere distance segmentation is inferior. Though with my bots it doesn't matter that much since I always fire power 3 bullets. -- PEZ

Paul Evans does that? I wasn't aware of that. I actually original became familiar with the technique from nano, above, when he was working on Statistician. And does M really ALWAYS fire power 3? About the problem above, I think I'll try rating the cross-sections of the stat buffer by the square root of the number of samples divided by the number of segments included. We'll see if that seems to work. I'll probably divide by something, too, I don't know. If I can't get something that's basically certainly better than FloodMini without saved data and just as good or better with saved data, I'll probably scratch it. -- Kawigi

Yep, take a look at Marshmallow/DTGunTest. M fires power 3 until the end of the round where either M or its enemy has lower energy than 12. -- PEZ

Hmmm... I wasn't aware of that. Of course, what you're also saying is that the times where you're not firing power 3 are the times it's most important to hit. -- Kawigi

Sometimes yes, if the round is tight to the end. -- PEZ

So i just wanna check if i'm segmenting in the same way as everyone else. I have an array of integers with the same number of dimensions as factors i want to segment on. I fire my virtual bullets with all the data wrapped up inside, and when they hit i unwrap the data and find out the index for each of these dimensions. When i want to aim the i find out the indexes for the factors, and loop through to find the highest value for a guess factor:

It looks something like (well a bit ago it was):

Called in VBulletHit:

 intelligence[distIndex][(int)((vb.factor*20)+20)][wallIndex][accIndex][latVelIndex]++

Called in doGun():

  for(int i=0; i<41; i++)
        {
            if(intelligence[distanceIndex][i][wallIndex][accIndex][latVelIndex]>bestVal)
            {
                bestVal = intelligence[distanceIndex][i][wallIndex][accIndex][latVelIndex]
                bestIndex = i;
            }
        }

Does that look liek what everyone else has got?? Ok, so the problem i'm having is how to balance learning speed against performance. At the momeent my stat gun seems to take about 300 rounds to properly lock in, and in the early rounds against an opponent it really struggles. Is there a rule of thumb that says which segments need higher granularity or is it just a case of fiddling and finding out what works best??

Pez, i am interested in your idea of summing the surrounding values, however i dont see how you know which ones to add. In my implementation there are 5 dimensions meaning that there are (cant be bothered to work it out) lots of surrounding values?? do you just do it for the guess factor above and below??

Also, Kawigi, i remember reading somewhere that floodmini fires it's virtual bullets every scan, and was wondering whether this disadvantaged you at all, seeing as some bots react to enemy bullet fire.

I believe i have drivelled enough now... --Brainfade

I agree that adding all surrounding values in a 5-D array or something is a little more complicated than PEZ, who only has a 2- or 3-D array. That looks fairly similar, though, to what I do, except I always make the shot angle the last dimension of the array, because it makes it easier for me. Some people also don't only sum their hits in each bucket, they use a 'rolling average' which weights more recent values higher than older ones. I've messed with that a little bit, it works better against some bots (particularly those who switch modes or otherwise 'learn' movement), but against most opponents, I find that's it's just more unstable.

About granularity, I'd say that higher granularity isn't necessarily better or worse. There's a *chance* that you'll be a little more accurate with smaller segments, but in general, you only have an approximation anyways, and tuning that approximation by identifying a more specific state doesn't help you much. Ultimately, the amount of granularity you want is just the amount you need to get a good idea what's going on in your opponent's movement. From there, it's not a bad idea to discard anything that doesn't make a difference against the opponents you care the most about. For instance, I think my statist robots would get a more accurate picture of Tron if they segmented on AdvancingVelocity (I haven't actually tried it, it's just a theory), because as it is, they only see how he's moving laterally to them, and Tron would tend to go at somewhat sharp angles toward or away from me, and I wouldn't know the difference. But Tron is the only top bot I think this would help against. It might also help against Crazy, but I'm not overly worried about beating the sample bots. And my bots don't have a huge amount of trouble beating Tron anyways. So I leave that segment out for two reasons - it would make me learn slower (not a lot slower, maybe, most of the robots I care about would usually have an advancing velocity close to 0 anyways), and it would need to save 3 times as much. The compression would make it less, but that space is precious. That's also why I changed FloodMini's distance segmentation to every 100 pixels from every 50 and capped it at 10 segments. FloodMini also used to have 4 or 5 LateralVelocity segments, now he has 3. My reasoning is that against almost any robot, all the middle ones are basically the same. And when I know acceleration/deceleration, I get an even better picture of what's going on when they're in those middle velocities.

About firing a wave every scan, FloodHT 0.8 and all versions of FloodMini do it. You be the judge if they are handicapped by it :-p But seriously, the next FloodHT will do both (and rate them in a VG-type way. I may eventually track when they change direction relative to my fire time, and look for a correlation, but for now, this is easier). The advantage of taking in your stats constantly is obviously that you can learn faster. FloodMini is pretty good after 30 rounds, and about as good as he gets by 100 or so. And as good as he gets means beating almost anyone. However, it means learning wrong against a few robots. Overall I wouldn't say it's a big hit against it. Some people are under the impression that having movement based on bullet fire is a weakness. FloodMini's gun makes not reacting to bullets a weakness. Assuming he learns correctly, he can potentially learn 10 to 16 times faster (the number of ticks it takes for your gun to cool), assuming he's getting a scan every tick. -- Kawigi

I will seriously consider using every scan for updating my stats... On the question of accumulation of related segments. I only have two dimensions of segmentation with low granularity (3 in each dimension as described at the beginning of this page). It gets an easily drawable tic-tac-toe-like board. So it's easy to identify neighbours. With five dimensions I guess you could start with checking if you have enough samples in your segment and then, if not, scrap dimensions in reverse order of importance until you have enough data. -- PEZ

Been there, tried that. The problem is this requires waaaaay too much computing power. Better strategy seems to be: start simple, grow from there. More specifically, start with just an array of angles to fire and add datapoints untill the data smooths out. In the meantime, keep N segmented arrays segmented by your N dimensions (distance, time since last turn, distance to wall, ...). When the data is smooth enough, choose a dimension that looks te most promising (the one with the highest peak or maybe another evaluation criteria) and use that one. While this data is smoothing out, create N-1 copies of it and segment them in the N-1 remaining dimensions ... and after this step you're segmenting your data in 2 dimensions. You can keep this up untill all your dimensions are used up. This algorithm makes sure your data is always relevant (by adding dimensions incrementally), is fast enough (due to the relevant data you don't need to collapse dimensions which is computationally intensive), and makes sur you segment in the most relevant dimensions first (which is good since you'll probably never collect enough data to segment into all dimensions and keep enough datapoints). This is something I'm still working to perfect ... I hope it'll ever see the light either in my mega-bot or in some else's ... -- FnH

Actually, it doesn't have to be computationally intensive. I've got a way to effectively store my stats with every combination of segmentation parameters possible (2^N), and it's perfectly accessible. I can do it all fast, but my problem is figuring out which to use. If I have decided to rank my parameters in order of importance like PEZ said, I could use my algorithm for that, too, I would probably just keep an array of 'descriptions' of each incremental gun. Since I'm not using the code actively in any bot, anyways, maybe I should post it somewhere (FloodHT 0.7 used it)... -- Kawigi

Ok, the next day i've got free (wont be for a while though, stupid summer job...) i'm gonna make a list of all logical segmentations, and mess around with them to see which are worthwhile and which are not. Does anyone know of a good bot(s) to test against?? I remember david alves said he tested against eve, but i'm not so sure eve is upto the task. Also, i want to implement a system whereby i store both short term and long term stats, and fire using whichever is best. Is this how other people use short and long term guns or does everyone just using rolling average weighting?? And last question (which is slightly off topic) does a method in java that returns an object always return a reference to the object?? I'm looking for a way to reference and dereference pointers in java (c style) and this is the best i can think of. I really hate having loads of time to thinmk up ideas, but not enough time to sit down and actually code it... --Brainfade

Marshmallow weights in the short term data into the long term. That makes the long term data rule, but shorter term information might push the decision in this or that way. Though with M short term means really short. It's not meant to capture changes in strategy. It's meant to capitalize on cornered bots or similar states. Yes, you always get a reference to the returned object. I don't think you should try do c style stuff in Java. Better search for the Java way of doing things. The absolutely best book on Java (and a contender for best book on any computer subject) is "Effective Java - Programming Language Guide" by Joshua Bloch. Buy it, steal it, trade your grandma for it, do whatever it takes to get it. -- PEZ

Alot of maths, slow learning times, and memory consumption.... you really think this is worth it all? I won't say its not, but if you ask me quick learning times are vital when facing bots that change their dodging patterns. I tried a tactic against marsmallow the other day where I mix smart dodging patterns with very simple ones (circle, box, triangle etc,etc) and I was amazed that my bot could win 3 rounds in a row using the circle pattern against marshmallow. Also when marshmallow homed in on the circle pattern it became less effektive against the smarter dodgepatterns. If you ask me, quick learning is essential. -- Jimpa

Agreed. I'm not sure I'm even going to try push Marshmallow all that much further because of the inherent learning delays of its design. My next attempt on the crown might be through GloomyDark. However, I think mixing dodging patterns is very hard to do and risky business in the long term. You risk creating short and long term spikes in your movement profile and become the victim of good statistical aim. I think that creating both short and long term learning ability through the use of VirtualGuns might be a working strategy. Time will tell. =) Welcome to the wiki Jimpa! I was beginning to wonder if you would ever show up. -- PEZ

Ey thanx PEZ :) I have been away from robocode for a while but now I'm stuck again.. Still working on my guns, and improved dodging ofcourse. You all seem to under estimate the importance of not getting hit (and its still much easier than learning to aim well.. believe me :P) And as usual i cant keep my big mouth from flapping ;) nice to be here anyway. It just might pop up a new bot soon :p -- Jimpa

You must probably exclude a few of us from the "You all" set. I haven't left the MovementLaboratory for many hours since I entered it some half a year ago or so. And Paul seems to be able to improve his movement endlessly (from a position where his movement is the best by a huge margin). If you think you have a movement that can compete, enter it into the MovementChallenge. -- PEZ

Read it. Very nice stuff! I must get the graphers.... I take back what I said about you guys dont spend time on your patterns. Seeing here how fast you guys are developing I think I have a very good chance at beeing a complete newbie again, so dont expect to much competition from me. :/ -- Jimpa

Hmm... The current version of Fractal segments data across 100 angles by 80 distance ranges. This is obviously a lot... But when data is gathered, it is smoothed across many bins, so it's not as slow to learn. I'll soon program it to start out by smoothing across a very large number of bins to gather data quickly, and slowly reduce the smooth radius as the match progresses. -- Vuen

---

Here's an interesting idea for rating the importance of a segmentation based on "information gain" concepts in decision tree learning: /Prioritizing -- Kawigi