Talk:DrussGT/Version History

1.3.1 results

Interesting... it appears with 1.3.1 that switching the time segments to the style I've been using, has killed the score significantly, putting it behind Dookious. Maybe I should try DrussGT style time segments some time... --Rednaxela 09:10, 11 December 2008 (UTC)

I was playing with the code quite a bit... maybe it messed something else up. I'll do a revert and just keep the gun changes. In the TCRM it scored a satisfying 90.59 over 100 seasons...--Skilgannon 19:47, 11 December 2008 (UTC)

Hang on... I just looked at the details and it seems I'm getting lots of 0 scores, however only coming from Alcatraz. Also, it seems strange that in some of those battles I get 50% survival, but zero score?! Maybe this would be a good time to try out the revert features offered by the new database backed rumble =) --Skilgannon 04:55, 12 December 2008 (UTC)

Heh, I kind of think this server should still be rejecting 0 scores like the old one did... at least except when it matches the expected score reasonably :) --Rednaxela 08:14, 12 December 2008 (UTC)

---

Hey, hope 1.3.2 will stay at king! And hope you new AntiSurfer gun will kill Shadow! » Nat | Talk » 00:25, 12 March 2009 (UTC)

---

Have you realize that 1.3.1b and 1.3.2 took exactly 3 months to development! (and 9 minutes, actually) » Nat | Talk » 13:33, 24 March 2009 (UTC)

1.3.8 results

Just wanted to offer a "wow!" at the 1.3.8 rating. Awesome that you are still finding improvements. Are you trying to just crush any hope anyone has of ever catching up? =) (Just kidding, I reckon I'll make a run eventually, just having fun on something else for now.) --Voidious 15:00, 11 May 2009 (UTC)

Yeah, I decided to apply the very effective DC movement strategy of weighting scans by their inverse distance (eg. Shadow, Wintermute, CunobelinDC) to the gun as well. Seems it worked quite nicely =) And what's more, it's something that any DC gun can VERY quickly implement. --Skilgannon 08:44, 12 May 2009 (UTC)

Ah, cool. And hey, Lukious did that too! =) Actually, he used a 2D kernel density, with one of the factors being distance between the scans, but I think he also weighted by distance to search scan. I'm definitely making a mental note about this for my future DC endeavors. =) --Voidious 13:28, 12 May 2009 (UTC)

You are right it was very easy to implement. I have some versions of that idea now in test =). --zyx 14:33, 12 May 2009 (UTC)

Haha, actually, I don't think I've ever done a DC gun WITHOUT that feature... maybe I'm odd though :) --Rednaxela 15:37, 12 May 2009 (UTC)

It's interesting how well this worked, I had always assumed that the reason it worked so well for movement was because of the very limited data. I thought in a gun getting as much data as possible would be preferable, as there was a good chance some of the factors would just be noise against a large portion of the bots, and while a weighting method based on scan distance could certainly be effective, I thought one that tended towards infinity like the inverse distance one would be too 'harsh'. Seems I was wrong =) --Skilgannon 18:11, 12 May 2009 (UTC)

1.3.10

Re: kd-tree speed, how many dimensions do you have now? In testing my own kd-trees, IIRC it took something like half the match before the kd-tree was as fast as brute force with ~6 dimensions. Maybe my memory's off, but it took a while, and more dimensions takes longer. If you have a lot more, I wouldn't be surprised if it's slower than brute force over 35 rounds. My Diamond/Code#KdBucketTree.java has a runDiagnostics2 method that might be helpful to you in diagnosing the relative speeds of kd-tree vs brute force. The runDiagnostics2 is the more up-to-date method, you can just adjust the number of scans and number of dimensions (the array of random numbers) you put into the tree (though it could be coded more clearly), and you could just delete the comparison to my vanilla kd-tree. Good luck. =) --Voidious 13:47, 10 August 2009 (UTC)

Cool. I'll take a look at that. I'm running 11 dimensions, so... =) Maybe have a wrapper that uses brute force for the first N scans, and from then on uses the tree? Also your test uses perfectly distributed random numbers, so in real life the tree is penalised even further. --Skilgannon 14:01, 10 August 2009 (UTC)

Oh yeah, and bigger cluster size favors brute force, too... Kd-tree might blow away brute force for one nearest neighbor, but 50 nearest is a lot different. --Voidious 14:14, 10 August 2009 (UTC)

Hmm... I'm tempted to make a N-Nearest-Neighbour Challenge to compare various KD-tree implementations as well as brute force, at different numbers of dimensions and so-called 'cluster sizes'... :) --Rednaxela 14:38, 10 August 2009 (UTC)

Go for it! I think k-Nearest Neighbour Challenge or KNN Challenge (I can accept the British / Canadian spelling :-P) would be a closer fit to the usual naming of this problem, like wikipedia:k-nearest neighbor algorithm. For 25,000 data points, cluster size 50, 10+ dimensions, my money's on my brute force algorithm. =) --Voidious 15:01, 10 August 2009 (UTC)

I was just re-reading the wikipedia:k-nearest neighbor algorithm page and I followed the link to wikipedia:Statistical classification, where I noticed something called wikipedia:Boosting, which looks to be about the same idea as Crowd Targeting. My attempts at trying to dynamically weight DrussGT's movement buffers in the past have been, generally, failures, but maybe the algorithms they provide as examples will be a bit more successful =) --Skilgannon 15:50, 10 August 2009 (UTC)

Hmm very interesting... It does appear to be like Crowd Targeting as it's often interpreted. I may be mistaken, but those methods don't appear to handle the case where something should be given negative weighting though, which is a key aspect in SaphireEdge's "crowd" model. --Rednaxela 16:20, 10 August 2009 (UTC)

Yes, in a gun case I can see how you might need to weight a certain gun negatively if, for instance, it is being actively dodged by a surfer. In a movement case, however, where we are just talking about weighting different sets of VCS buffers more or less depending on how much they correspond with enemy targeting. I think it could be proved that by simply segmenting data it is impossible to make your targeting worse, only better, so only positive (and possibly 0) weights are necessary. Interestingly, I think this also makes having multiple segmented data buffers a form of Probably approximately correct learning. I need to find out more about boosting =) --Skilgannon 14:21, 30 August 2009 (UTC)

We talked about "boosting" in the Machine Learning class I took in college. The only thing I remember about it is that the team with the best classification score on the final project used it. =) --Voidious 17:02, 10 August 2009 (UTC)

1.5.0

No changes for this version except move the movement code to DrussMoveGT? And where is 1.4? » Nat | Talk » 14:43, 6 September 2009 (UTC)

• 1.4 was down near 1.3.10, but I ditched that line due to it being a complete flop. 1.5.0, yes, it was just moving it out to a separate class, and also move all the gun references out of the movement code into a new class file. I also ditched 1.5.0 due to a tiny little bug that I was unable to find, but which cost me about 0.2APS --Skilgannon 06:12, 18 January 2010 (UTC)

1.6.7

On your latest update to help mirror bots - I had noticed your weakness here and wondered how you were going to address this. What's your idea on this? --Miked0801 20:43, 17 January 2010 (UTC)

Also, to let you know, I got a few NULL Ptr exceptions when running your bot vs. deith.Czolgzilla 0.11 - 3 in 35 rounds. There may be something amiss in your code.

Wow - I thought I killed all those NPEs - thanks for the heads up! The basic idea with this update is taking advantage of something goto-surfing gives me over true surfing - I know where my final destination is before actually reaching it. What I do is take the midpoint between me and the other bot and imagine it stays constant. Then I imagine that the other bot is mirroring my future predicted best location (I take the furthest forward prediction available from the movement) and check what the offset I would need to shoot at would be to hit my mirrored location. That offset is the value I use to cluster on. The idea I'm hoping for is that all bots tend to rotate around an imaginary point as they surf (or random move), and they also tend to be at the opposite side of the circle than I'm on in order to keep a decent distance, so their movements may tend to be slightly mirror-ish, and if I can tell my gun the point on the circle I'm going to be, it has a definite advantage trying to figure out which part of the circle they'll rotate to. Hope this makes sense =) --Skilgannon 06:12, 18 January 2010 (UTC)

About the NPEs, I just saw a bunch against cx.micro.Spark 0.6. 12 in 35 rounds if that helps. Interesting idea for the anti-mirror stuff by the way. How big a factor is it if your surfing data changes after firing at such a point? --Rednaxela 07:23, 18 January 2010 (UTC)

Thanks - think I've killed them all now. If anybody spots any more please let me know! So far it's a very rudimentary version - if I had enough coding time and processing power I would

• predict forward until the next enemy wave should be fired
• predict all my movements forward until my wave (fired now) hits my mirrored surfing position
• use the offset of that for aiming
• then keep track of the scan and when adding scans use what movement I actually make, and not what I'm predicted to make (which is only truly 100% accurate up to the end of this wave anyways).

But first I want to see if there's any merit to the idea. So I haven't done any of the extra predicting forward, or keeping track of scans to make the data absolutely correct, or anything. All I have right now is using the furthest wave's safest reachable point (by following the best point on the closer waves) and then taking it's offset and multiplying it by the GF direction. If it doesn't hurt my score (in this state) I'll consider it a terrific success =) --Skilgannon 17:14, 18 January 2010 (UTC)

If you add 3 bots to the rumble, you should at least leave your client running to help with the calculating ;) --Miked0801 15:47, 27 January 2010 (UTC)

Yeah sorry about that... my client died from what looks like a corrupted HDD and I didn't have time to fix it then. I think I've fixed it by re-installing the JRE but I'm going to need to keep an eye on the HDD from now on... --Skilgannon 09:18, 29 January 2010 (UTC)

By the way, it's impressive how that improved DrussGT's performance against PolishedRuby. What's interesting though, is for some reason Toorkild gets a better score though... much better. Even more so than Axe's bots with anti-mirror movement. You may want to look into what happens in Toorkild vs PolishedRuby to find more opportunity perhaps. :) --Rednaxela 17:55, 29 January 2010 (UTC)

1.6.10 bughunting

Hey guys, so far (from my own machine) I have picked up NPEs at jk.mega.DrussGT.getBestPoint(DrussGT.java:1194) and at jk.mega.DrussGT.doSurfing(DrussGT.java:1616). If you spot any others please tell me =) --Skilgannon 09:44, 4 February 2010 (UTC)

Sorry for the late response. Hit the getBestPoint once here, against strider.Festis 1.2.1:

java.lang.NullPointerException
        at jk.mega.DrussGT.getBestPoint(DrussGT.java:1194)
        at jk.mega.DrussGT.doSurfing(DrussGT.java:1615)
        at jk.mega.DrussGT.onScannedRobot(DrussGT.java:207)
        at robocode.peer.robot.EventManager.onScannedRobot(Unknown Source)
        at robocode.peer.robot.EventManager.dispatchEvent(Unknown Source)
        at robocode.peer.robot.EventManager.processEvents(Unknown Source)
        at robocode.peer.RobotPeer.execute(Unknown Source)
        at robocode.peer.proxies.BasicRobotProxy.execute(Unknown Source)
        at robocode.AdvancedRobot.execute(Unknown Source)
        at jk.mega.DrussGT.run(DrussGT.java:143)
        at robocode.peer.RobotPeer.run(Unknown Source)
        at java.lang.Thread.run(Thread.java:619)

--Voidious 20:48, 5 February 2010 (UTC)

From 1.6.12 against toorkild 0.2.4b

=========================
Round 35 of 35
=========================
My hitrate: 0.13681592039800994
DC gun score: 174
PM gun score: 169
AS gun score: 170
gun: DC
Enemy damage: 963.2852093419626
My damage:    1421.6659683513403
Accumulated, weighted enemy hitrate % : 8.65954079741584
Flattener enabled: false
SYSTEM: Bonus for killing jk.micro.Toorkild 0.2.4b: 12
SYSTEM: jk.mega.DrussGT 1.6.12 wins the round.
Enemy damage: 984.3913840978221
My damage:    1481.6623683513399
Accumulated, weighted enemy hitrate % : 8.653287918748319
Thou rank tickle-brained bladder!
ERROR: DETECTED BULLET ON NONEXISTANT WAVE!

In the debug window it said error so I thought you might want to know... --Miked0801 07:23, 17 February 2010 (UTC)

1.6.15

Congrats on the perfect PL record with this version. =) Credit to your changes, or just lucky? --Voidious 15:38, 9 March 2010 (UTC)

A bit of both I think. More a lack of bad luck, possibly. The only changes were made to the main gun, the anti-surfer needs a bit of work now I think =) Interestingly enough, the APS actually went down a little. Time is currently the limiting factor... --Skilgannon 20:04, 9 March 2010 (UTC)

Congrats on your achievement. I just looked at your gun code and there are some parts of it I'm not sure whether I just couldn't understand, or if there is actually a problem there. For instance, why do you have accel slices as -.5, .5 when accel only takes the values 0, 1, 2? Also, in the getOffset method, if the index height is 1 over the scan distance and you only use the index with largest height, why don't you just search for 1 nearest neighbor (supposely the one with smallest distance, and therefore biggest height)? --Navajo 22:27, 9 March 2010 (UTC)

Thanks =) Wow, yes, that -0.5 0.5 thing is definitely a mistake, thanks for catching that. It might even be why my anti-surfer attempts have seemed to be hitting a brick wall. As for the 1/distance issue, this is on purpose. For instance, if I had 1 scan that was a distance of 2, but 3 scans that were a distance of 3, and the 1 scan showed one angle is the best but the other 3 all agree on a different angle, it will fire at the 3 instead (which is probably a better place to fire). Notice that I have an option whether it uses this inverse weighting or not. I found that against some bots using the inverse helped (generally weaker bots with more predictable movement) but against others it was better to weight all the scans the same (generally the wave-surfing bots). Anyways, thanks for catching my bug with the acceleration in the anti-surfer gun, I think I'll be working on that now =) --Skilgannon 12:25, 10 March 2010 (UTC)

1.8.1

Hey interesting. I use quite a few in my movement (though I might as well use linked lists at that size). A couple thoughts I have about the multiple buffers/trees thing:

• I wonder if our attitude that multiple trees might be good is a misguided attempt to translate things from the VCS world to the DC world. And maybe if we freed our minds we'd think of something better.
• Lots of buffers works well in movement, but I'm not convinced it's really because of any "crowd wisdom". I've long suspected it's just a matter of constructing your danger values such that the safest spot is mostly the same, while the rest of the spots are randomized enough to make your movement unpredictable. If this is the case, it makes me think it won't do much for you in a gun.

The proof is in the pudding, though, so I'm very curious to see how this goes. =)

--Voidious 22:16, 14 April 2010 (UTC)

Indeed interest. Actually, that first point Voidious makes, is something I've hard on my mind for a while before. See, I've found that a single VCS buffer which is anti-aliased and interpolated reduces aliasing error as much as possible. It performed similarly to a while bunch of traditional VCS buffers. For this reason, I've come to the conclusion that the advantage of lots of VCS buffers is not due to "crowd wisdom", but due to the simple fact that lots of differently segmented buffers will average out the aliasing error to a degree, fixing the problem. Because k-nearest neighbors, anti-aliased VCS, and VCS "crowd" all show the same league of performance, I suspect that simply crowding trees may not help so much in the same way that lots of VCS buffers helps, at least not to the same extent. I think a "crowd" of trees could have some gains perhaps, however unlike the case of VCS, it isn't mending any aliasing error which I think is the biggest issue with a single VCS buffer. --Rednaxela 00:05, 15 April 2010 (UTC)

I've tried this on Gibbs several times and as Voidious said, it works well on movement, but I still haven't seem significant improvements using this to aim. I did however achieved good results combining trees with the same dimension but different size limits, mixing different cluster sizes, kernels and scan weighting. --Navajo 00:23, 15 April 2010 (UTC)

My thoughts are exactly the same, adding lots of buffers really does make the equivalent of a properly aliased, interpolated buffer, and since trees are already perfectly aliased (or rather, the data is never put into discrete bins) this shouldn't actually help. However, the reason I'm giving it a try is because all other attempts at dynamic weighting for guns seem to have failed, and I think this setup is perfect for some sort of Boosting. The fact that it lost around 0.5APS really doesn't surprise me, as I currently do not have any sane default weights, ie. all dimensions are weighted equally. I'll probably end up setting up all the possible combinations of buffers, running local tests, and then selecting the top 20 for anti random movement and the top 10 for antisurfer, or something like that. --Skilgannon 05:23, 15 April 2010 (UTC)

I'm still fairly ignorant of boosting, but I'm curious. Why "dumb down" your trees into weaker classifiers before trying to recombine them into a strong classifier? For instance, why not include your 11 dimension tree as part of your set? And are you using some type of boosting algorithm, or just doing KNN on all 4 trees and using the combined set as your cluster? (Which I'm not sure is "boosting", but maybe it is.) --Voidious 13:52, 15 April 2010 (UTC)

Boosting (as I understand it) is basically an algorithm which combines a whole bunch of 'weak' classifiers into one strong classifier by weighting them in some way. It doesn't matter how weak the learners are, if they have a hit rate > 50% then as long as there are enough of them, each saying something different, you can make an arbitrarily strong classifier. I'm actually currently setting up the framework so that I can have all ~2000 combinations of 11 attributes (from 1 dimension right through to 11) and run a testbed against them for a few seasons. Then I'll see which ones have the highest hit ratios and manually select those to include in the rumble release. --Skilgannon 14:51, 16 April 2010 (UTC)

My thought is, perhaps rather than just select the ones with the highest hit ratios, perhaps consider something such as "hit ratio to required cpu time" ratio maybe? After all, the strongest ones may use more dimensions and thus be the slowest, so maybe it would make sense to bias against slow ones to an extent. --Rednaxela 15:18, 16 April 2010 (UTC)

On second thought, simply dividing by cpu time doesn't make sense. One wants something more like "marginal gain of adding this classifier, versus it's required cpu time", and doing it that way would make it depend on the order the classifiers... The only way to ensure an optimal group, is to test ALL possible combinations that fall within a certain CPU limit, and to evaluate that effectively one needs to either have one's weighting or weighting algorithm already decided. --Rednaxela 15:24, 16 April 2010 (UTC)

Yeah, just picking the strongest and using them is not necessarily the best combination. If two have 99% mutual information, you're not gaining much by adding the second one, and you're doubling the weight of that 99% in your whole. Oh, and if any of them have a hit rate of > 50%, you'll be *really* kicking butt. ;) --Voidious 15:30, 16 April 2010 (UTC)

Actually a hit rate > 50% is required only when using boosting on an ensemble of 2 class classifiers. For multi-class boosting all you need for each classifier is a success rate better than random guessing. --Navajo 17:20, 16 April 2010 (UTC)

I know, I was just poking fun. =) --Voidious 18:42, 16 April 2010 (UTC)

1.8.7

Two comments:

• Heh... I was gonna ask about the BulletHitBullet thing, but I came to understand it while writing my comment. =) Interesting insight there.
• The gun turn thing is something I've played with. Right now, I calculate the angle I'd aim with if I were aiming this tick (firing next tick), and check if the gun is already within a bot width of that. Frankly, it's technically wrong. Sadly, trying to fix this showed the same or worse performance, so I ignored it and moved on... Maybe I'll try again, as that was a while ago.

Looks like you've gained yourself a small buffer at #1 (Diamond 1.5.17 and DrussGT 1.8.0 were like dead even), which might be all you need since I'm becoming a StarCraft 2 addict. =) But I'm actually quite satisfied with Diamond right now, despite the strong possibility of losing the Melee crown while failing to take the 1v1 crown...

--Voidious 00:38, 17 May 2010 (UTC)

Yeah, I have some serious doubts as to how correct all our GF stuff actually is. I think I've solved my 1-off 'performance enhancing bug' in the gun, it was actually right previously, as the bullets are moved before the robot. So technically, in the painting, the bullet should be on the trailing line of the wave, not the leading. Take a look at the DrussGT painting if you're confused. 1.8.8 released, which reverts putting the bullet on the leading line, but still keeps the VG changes (including putting the VG on the right tick). If this works I'm going to have a try at precise min/max GFs again. --Skilgannon 09:25, 17 May 2010 (UTC)

From what I remember, DrussGT does its gun in onScannedRobot, isn't it? If so, isn't the Paint did after onScannedRobotEvent() ? --Nat Pavasant 13:37, 17 May 2010 (UTC)

Yes, but the screen is painted, then the bullets' location are updated, then the collisions are checked, then the robots' locations are updated. So the wave should precede the bullet by one velocity at the time of painting, because it is updated before the enemy moves. --Skilgannon 15:13, 17 May 2010 (UTC)

Yes, but... onScannedRobot(), then onPaint(), then process until execute(), then timer tick, then screen painted, then update bullet/robot... I have experiment with this a while ago, with both debug paint and debug print. If you update wave in onScannedRobot, it should line up with bullet exactly. If you do that in run(), it should be trailing the wave, isn't it? --Nat Pavasant 03:04, 18 May 2010 (UTC)

Yes, that's correct for at the time of painting. However, the important thing to note is that the bullets are moved again before collisions are checked, and before the robots are moved. As such, although at the time of painting the waves should be at the same place as the bullet, what is actually important is that at the time of collision the wave should be at the same point as the bullet. Since we can't update the position of the wave while the robocode internals are working, we need up update it before. If you look at the latest DrussGT painting it should be clear: the rear wave is where the bullet is at the time of painting, and the forward wave is where the bullet will be when the collisions are checked. We then do our precise intersection based on these 2 waves. --Skilgannon 08:13, 18 May 2010 (UTC)

Just writing that down... thx -Jlm0924 21:35, 17 May 2010 (UTC)

I might agree, but what do you mean by "all our GF stuff"? I think our guns are pretty darn accurate, tho I never rule out another leap. I have serious doubts our surfing stats are working exactly how we think they are against any type of learning gun. Hard to describe exactly... But I've tried a ton of stuff with surf stats that I really feel should help yet fails miserably. --Voidious 13:21, 17 May 2010 (UTC)

I guess I just have a general grudge against statistics, which is the general context that GFs are used in =) Anything which can't give me a definite answer has an extra layer of error in interpreting exactly what the data means. I don't think there is anything which anybody can agree on when it comes to surfing stats - I mean, Shadow doesn't even age his data. I find that ridiculous. I've been thinking of converting DrussGT to using arrays of raw GFs rather than arrays of bins, and from there possibly even convert to DC. But even if I manage the conversion without any bugs, it will be a daunting task trying to get everything tuned like it was =) I've been doing some experimentation with using a gaussian kernel density for the gun, but it seems to make my gun useless against surfers while not really helping the anti-RM side of things. I may release a version anyways, just for kicks. Currently DrussGT uses a 'uniform' kernel, just testing raw overlap of GF ranges.--Skilgannon 15:13, 17 May 2010 (UTC)

Personally, I think GFs are a pretty ingenious way of analyzing enemy movement. =) Can you give an example of what would give you a "definite answer" and no "extra layer of error"?

As for surf stats, yeah, they're all over the place. I'm definitely at a point where "Wave Surfing" is an insufficient description of a movement. But for example, the general perception is that we are learning the dangerous firing angles and avoiding them. This is undoubtedly true, but I'm not sure that more accurate projection of dangerous firing angles is what separates a good surfer from a great one. If the enemy gun is still learning, it's also critical to tune how/when you visit the non-dangerous (from your surf stats' perspective) firing angles. Yet nobody does this explicitly besides flatteners against really high hit rates. And perhaps you should never have a firing angle seem too safe, since you might dive too close to get to it. If I add a super lightweight flattener, to flatten among the safe angles while still dodging the dangerous ones, it does nothing for me. I just know I am missing something.

--Voidious 20:49, 17 May 2010 (UTC)

Continued at Talk:Wave_Surfing#The_Next_Level....