Archived talk:Horizon 20071111
Up 16 places with 0.9.6, what's new? -- Skilgannon
I took your advice and made the bot do all of its clustering and sorting of scans at the time the relevant wave is fired. It seemed to help the surfing a lot, it shot up the WSC2K6 scores close to 85. In addition, adding a default hit logged at GF 0 got the bullet damage scores vs. Bot A as low as 28 over 500 rounds. - AaronR
How much has it helped vs. bot B and C? I'm guessing it would have made a huge difference, because LT/CT only use data at the time of fire. Just wondering, are you using a rollingAverage for your surfing? -- Skilgannon
Since you are still a little bit below BasicGFSurfer, I'm thinking that you still have some bugs to sort out ;-). Looks like these are the bots with the biggest differences:
I watch battles against my problem bots, and go through the code looking for why it would have reacted the way it did. I haven't looked at your code, but if it's structured well you should have no problem finding them. Good luck =) --Skilgannon
You're getting mashed by any and every sort of pattern-matcher. How about adding a time-since-something segment in your surfing? -- Skilgannon
- Actually, I was going to try that for one of my beta releases. Last night I started to go through my problem bot statistics, but I didn't finish. The other problem I'm having is with rammers, I get problem bot ratings of -40 or more against a few of them. -- AaronR
- You do want to do as well as possible against rammers, of course, but depending on your rating, they may always be "problem bots", technically. Getting 70% against a good RamBot is about as good as you can hope for. =) -- Voidious
- Firing full power at very close range (say 150) will get you at least 50% against any rammer, assuming you really aim for it ;-) -- GrubbmGait
- Yeah... I think I have a bit of a problem with the "aim" part. At very close range, my GF gun can overestimate the escape angle of some rambots and miss them altogether. It's painful to watch. =) -- AaronR
- Are you segmenting on distance? It shouldn't matter, of course, because RamBots should have a huge spike at GF0. -- Skilgannon
- I am using distance as a clustering factor, but I found it is more effective to just fire HOT at distances of less than 150. Look at the version history page, 1.0beta3 pretty much fixed my problems with rambots. -- AaronR
Sorry I've been gone for a while, my workload has been nasty lately. I was just running some tests with the development version of Horizon when I noticed that the bot was skipping a ridiculous number of turns. So I fiddled with things for a while and eventually managed to figure out that I actually have two molasses-like sections of code:
- My twelve-way precise prediction.
- The part of the clustering code that adds and removes scans from the log.
It seems that I didn't notice this in my performance before because I never bother to run Robocode before starting my rumble client (for which I keep a separate Robocode installation), meaning that the default super-high CPU constant is used. So now I have to optimize my code, which is something I *really* hate doing.
For your precise prediction, Krabb (I think it was Krabb) pointed out a clever optimization, assuming you're surfing more than one wave at a time. The idea is to get your full danger for all waves if you continue going in your present direction. Then when you're checking the "reverse directions" danger, you can break early if the danger is greater than your "continue" danger, even if you haven't checked all waves yet. --David Alves
Aha! It turns out that my precise prediction had nothing to do with the problem. Rather, the slow code was exclusively in my clustering implementation. Guess what the problem was: I was using java.util.LinkedList to store my log history. I replaced the collection class with a custom circular array structure, which eliminated the problem altogether. So basically, Java collections are slow and inefficient - but we knew that already. -- AaronR
- Let me guess, you were accessing it by index? -- Simonton
- (Edit conflict) Nope, that's what's weird about it. I was using add(T), removeFirst(), and a foreach loop, all of which should have O(1) time for a linked list. At least, I think that's what I was using... ooh, ouch, apparently I had switched to accessing by index at one point during my efforts to "optimize" my code. I had to switch because I was modifying elements, which isn't allowed by Java's foreach construct. However, the optimist in me is saying, "The new structure is faster anyway." =) -- AaronR
I don't think there's more than a few percent difference between their LinkedList class and one you could write yourself. ABC brought that issue up once before, but it turned out he had been using list.get(int i) inside a for loop, so what should have taken theta(N) time took theta(n^2) instead... --David Alves
- Yeah, same here. However, I am no longer using a linked list structure at all, but rather a circular array. Because I have a fixed bound on the log depth, I can simply maintain the indexes of the beginning and end of the structure and overwrite the old entries as necessary. It has the same time bounds but should be slightly faster in practice. -- AaronR
1.0beta9 seems to have made HUGE gains compared to 1.0beta8. Only 27 battles have passed, but I'm still gonna call it: I think it will be your ticket to The2000Club. Well done in either case! --David Alves
- I'm watching the comparison charts between 1.0beta9 and 1.0beta8 (and 1.0beta8GF), and I think you might be right. 2034.33 after 214 battles! -- AaronR
Alright, I'm an idiot. I released the MC2K7 test version of Horizon as the official version, meaning it had Raiko's gun. Ironically, it ranked about the same as RaikoMX... So for the second time in a row, I have been embarrassed by my gun only to find out that it means I have a very good movement. -- AaronR
Although, wow, that is a lot lower. Are you sure your gun is bug-free? Can it hit Walls consistently and whatnot? A 120 point difference due only to gun sounds very wrong to me. --David Alves
I gotta second what David said. With that big a difference, I'd even wonder if you might have a bug that is making you just shoot with HeadOnTargeting... ? Sounds like you have a very strong movement, in any case, and I think that's usually harder than getting a good (or good enough) gun. -- Voidious
I watched some battles and it's definitely not firing with HeadOnTargeting, it hits walls well enough. Could there be a bug in the Angle -> GF -> Angle conversion process? For example if the target is moving clockwise around your bot, and it moves .5 radians in front of the GF0 line, maybe you store that as GF .7 or something, but when converting back to angles you convert the .7 GF to an angle of .8 radians and end up shooting too far ahead / behind... --David Alves
That's possible, but not likely, since most of the original source for the gun was from the largely bug-free GFTargetingBot. Also, much of the code is shared between the movement and gun, including some (but not all) of the GF conversions. I'll look into it, though - I may have broken something while I was fiddling. Maybe improving my debugging graphics will help me find the problem. -- AaronR
Just out of curiosity, how many scans are you searching through? And also, how much are you weighting each attribute? -- Skilgannon
My log depth is 7200, and my cluster size is 5. My weights are: distance = 2, velocity = 1, acceleration = 3.5, lateral velocity = 2, time since acceleration = 2.5, wall distance forward = 5. I know those weights seem odd, but the tests I've been running seem to indicate that that is the approximate order of importance of those attributes against low to midrange random movements (which of course make up most of the rumble). Against high-end random movements and surfers, it is much less important to weight wall distance high.
I think I have may have found the problem. I just created a test bot called WallsReverser. It acts exactly like Walls for the first five rounds, then behaves like a mirror image of Walls (that is, circles in the opposite direction) after that. GFTargetingBot does what a correctly implemented GuessFactorTargeting gun should do with this bot: hit it just as well on the sixth round as on the fifth. It didn't care what direction the bot was orbiting in. However, when I put Horizon against WallsReverser, it fired as if it was targeting Walls - completely ignoring the fact that the bot was now moving in the opposite direction! It figured out the new pattern fairly quickly, but that doesn't solve the problem. Worse yet, I have no idea what is causing this, since the GF-to-angle calculation is multiplied by the lateral direction like it should be.
I would check that you are actually setting the direction to what the enemy's lateral velocity's is. Another thing to check is that you multiply both when you store the angle and when you use the angle to fire from. Shadow uses a MUCH larger log size (about 15K), and a much larger cluster size (50), so if it doesn't slow you down too much you might want to give that a try as well. IMO you should use lateral velocity or velocity, but not both. Maybe switch one to advancing velocity, and weight it lower. And just to check, you are normalizing your data for each attribute to values between 0 and 1, not -1 and 1, right? Absolute values of your lateral velocity are necessary, otherwise your gun won't see reverse the same way it sees forward. -- Skilgannon
Sounds like you're either multiplying by orbit direction too many or too few times, in either your Angle -> GF or your GF -> Angle code.
When saving a scan:
GF = orbitDirectionAtFireTime * Utils.angularDifferenceBetween(gf0Angle, shooterAtFireTime.absoluteAngleTo(p) / Utils.maxEscapeAngle(power)
angle = angleToTarget + Utils.maxEscapeAngle(bulletPower) * GF * orbitDirection
Another possibility is that when you store a wave you're using the target's current orbit direction instead of their orbit direction at the time you fired. Incidentally angularDifferenceBetween(fromAngle, toAngle) is just Utils.normalRelativeAngle(toAngle - fromAngle), but I like the name better. Before I put it into a method I was always forgetting which part should be on which side of the minus sign. =) --David Alves
(Edit conflict) Here are my responses to Skilgannon:
I would check that you are actually setting the direction to what the enemy's lateral velocity's is.
- I found the problem. The lateral velocity was being calculated and stored incorrectly in the gun. This has been fixed, and the gun's behavior is now correct.
Shadow uses a MUCH larger log size (about 15K), and a much larger cluster size (50)
- In versions prior to 1.0beta9, the log size was even lower. I will be fiddling with the constants more in the future.
IMO you should use lateral velocity or velocity, but not both.
- Again, I will be changing things around in the future. Some of the constants in my code are still pulled out of the air.
You are normalizing your data for each attribute to values between 0 and 1, not -1 and 1, right?
- I am normalizing each value to between -1 and 1 or 0 and 2, subtracting them, and using the absolute value of that. The data that goes into the distance function will be negative for some attributes, but the distance itself is always positive.
Absolute values of your lateral velocity are necessary
- I have tried it both ways. Each one seems to work better for some bots and not for others. I am not using absolute values in velocity or lateral velocity at present, but I may change this in the next version.
And to David Alves:
- The GF conversions were correct. Only the way lateral velocity was calculated and stored was buggy.
Just a couple sidenotes: Raiko and GFTargetingBot should be very similar in performance, as they are both based on Tityus. Also, a log depth of 7500 seems fine, though other DC guns do use many more; a cluster size of 5 seems a little small, but not 100-points-below-Raiko small. =) Sounds like you have found the big bug, though, so best of luck in your quest for 2K! As for using absolute value of velocity / lateral velocity: I absolutely think you should do this. Why should -7 or 7 make a difference? Odds are the bot that's moving doesn't see them as different, and it will majorly inhibit your learning speed. -- Voidious
- Edit Conflict: Your other gun bug must have been hiding this from you. If the lateral velocity is signed, your gun will learn twice as slowly. It's like using your direction as an attribute. -- Skilgannon
- In my (pattern matching) experience, it actually doesn't make that much difference to consider forward as backward in your gun (though I always do). Some difference, but it certainly doesn't make it 2x better. Actually, with the standard pattern matcher currently in WeeklongObsession, it makes absolutely no difference whatsoever (in the micro rumble). -- Simonton
I'd like to thank Simonton for finding the massive bug in my gun. The bug was caused by - surprise, surprise - movement tweaks! When I modified part of my shared Wave class to more accurately detect wave intercepts for the surfing, I inadvertently destroyed the accuracy of the gun's logging algorithm. With that fixed, my rumble scores should improve considerably. -- AaronR
- This bug has been in my code since at least the 1.0beta rewrite. No wonder I've never been able to get above 1975 or so ... *suddenly dizzy, experiences deja vu, goes to check that the right gun is in place* ... OK, I'm good. -- AaronR
Looks like you'll have yourself a ticket into The2000Club once you reach 1000 battles... get those clients running, people! =) --David Alves
- My client just finished spending 15 minutes rebuilding the robot database. =) -- AaronR
In addition to fixing that bug, I also introduced several other tweaks in the 1.0betaF4 release. I'll have the full version history for the 1.0betaF series ready as soon as I can remember all of the changes I made. -- AaronR