User talk:Starrynte/DCLSHResearch

Various Questions

Can't beat Walls?

OK. I temporarily set the CPU constant to 1 second, just to test this. It currently searches through ALL the points and picks the closest one. Yet it can't beat Walls yet. I believe it's one of the following problems:

• GF implemented incorrectly, though I don't think it is this
• DC implemented incorrectly, a possibility
• Cannot just use the closest point (must use multiple ones), this is also a possibility
• Other?

Thoughts? --Starrynte 04:16, 22 September 2009 (UTC)

If Wall fire and you don't move, you won't normally beat it with GF gun, at leat in my development. » Nat Pavasant » 06:54, 22 September 2009 (UTC)

• I never knew that! Thanks for the info! --Starrynte 04:02, 23 September 2009 (UTC)

"Stopping"?

Occasionally, the bot seems to freeze (the radar stops turning but there is still a scan arc, text output from onscannedrobot stops, gun stops, basically as though the robot was stop except for the radar arc). The other bot keeps moving, robocode reports no errors and no skipped turns and no "robot stopped". It always freezes at the start of the round. I have duplicated this a few times. Any reason why? --Starrynte 04:02, 23 September 2009 (UTC)

I've never encountered that. What version of Robocode are you using? And have you tried any others? If it's only in the 1.7.1.4 beta, I'm sure Fnl would appreciate it if you filed a bug report here. --Voidious 13:15, 23 September 2009 (UTC)

Could you please post the code? I don't think it is a bug, for that I was once getting this too. It seems that I've some bug in my radar that time. » Nat Pavasant » 15:17, 23 September 2009 (UTC)

Same thing has happened to me, and in robots so simple that it really shouldn't happen unless there's a bug in the basic radar code--CrazyBassoonist 20:55, 23 September 2009 (UTC)

Only radar code is setTurnRadarRightRadians(Double.POSITIVE_INFINITY) in run() and setTurnRadarRightRadians(Utils.normalRelativeAngle((absBearing=e.getBearingRadians()+getHeadingRadians())-getRadarHeadingRadians())*2d) in onScannedRobot --Starrynte 01:58, 24 September 2009 (UTC)

Do you have:

while(true) {
    turnRadarRightRadians(Double.POSITIVE_INFINITY);
}

-- or --

while(true) {
    if (getRadarTurnRemaining() == 0)
       setTurnRadarRightRadians(Double.POSITIVE_INFINITY);
    // ...
    execute();
}

Or do you just do:

setTurnRadarRightRadians(Double.POSITIVE_INFINITY);
while (true) {
    // ...
    execute();
}

? If you do the last one, than if you are not moving you might sometimes lost the radar lock, which result exactly the same as your. I'm not sure it is Robocode's bug or not. Nat Pavasant 11:16, 24 September 2009 (UTC)

• I have the last one. What doesn't make sense to me is that the scan arc is still there, the radar stopped turning but the arc isn't a line. --Starrynte 01:17, 25 September 2009 (UTC)
  • The scan arc is an illusion. It is not updated, nor does scanning happen (even in a line), if a robot doesn't move in the slightest. Ignore that scan arc artifact. As far as why it stops, it's my understanding that when a collision occurs, it not only clears the movement that's set, but also clears gun/radar turns. Thus you need to reset the gun/radar turn. Every properly working infinity lock I see is done with either the first of the methods Nat listed, or with the second minus the if statement which is unnecessary. It it stopping upon a collision occuring? :) --Rednaxela 02:47, 25 September 2009 (UTC)
  • For now I'm using the first one, the second one the if is necessary, otherwise it doesn't lock --Starrynte 02:53, 25 September 2009 (UTC)
    • Hm, I'm stuck thinking in MegaBot land, where radar processing happens outside of the onScannedRobotEvent event. The 'if' in the second one is not needed IF your radar/scan processing happens between it and execute, which isn't usually the case in small codesize bots. --Rednaxela 03:01, 25 September 2009 (UTC)
      • But in most megabots, radar processing also happens in onScannedRobot(). Normally the first method is use, the second one only use for robots that have some process in main loop too. Nat Pavasant 11:37, 25 September 2009 (UTC)
        • Most megabots eh? I'd say... most non-modular ones maybe. Doing actual processing ouside of the main loop to me seems like a recipe for making the code unclear and tangled up. --Rednaxela 12:34, 25 September 2009 (UTC)
          • But a lot of megabots use onScannedRobot as its main loop in one-on-one. And Dookious, as one of the modular megabots, have only the second method radar code in its main loop! I used to do things in main loop, but once I start to use debugging graphics, I switch to onScannedRobotEvent, or in case of my current development, a CustomEvent with priority of 6. --Nat Pavasant 13:04, 25 September 2009 (UTC)
          • I think it's split pretty evenly. A fair number of 1v1 bots do processing on onScannedRobot, because why not? All PEZ's duelists and Dookious are among them. Any bot that was ever intended to have melee support is sure to do most real execution in the main loop instead. --Voidious 13:09, 25 September 2009 (UTC)

Dealing with Surfers

I've tried segmenting on gunheat, but it leads to worse performance against non-surfers. No space for a VG array. Any other suggestions? --Starrynte 04:27, 24 September 2009 (UTC)

• Is it unusual for results to vary a lot across seasons? Since for example against CC I get scores ranging from 47 to 65 and against WLO I get 52 to 78 --Starrynte 04:59, 24 September 2009 (UTC)
  • Very normal. In fact even larger variations are things I regularly see. It takes many many many seasons to really get stable results against surfers (100+ seasons I'd say) --Rednaxela 05:09, 24 September 2009 (UTC)

In a MicroBot? My advice would be to ignore the surfers. =) But in general, rapid decay or removal of data is probably the most important thing. This would be low Rolling Averages in a Visit Count Stats system. In Dynamic Clustering (or even the k-means in TripHammer), removing oldest scans works, or weighting scans based on age. --Voidious 13:25, 24 September 2009 (UTC)

• Seems to help. Now to experiment with weighting, which I'm not using yet... --Starrynte 02:43, 25 September 2009 (UTC)

A few questions....

1. On the AntiSurferTargeting page of the old wiki, it suggested decrementing slightly when you actually hit the enemy. How would you do that in Dynamic Clustering?

2. Somewhere else on the old wiki, it said that you should count the waves 2-3 ticks before firing time as the firing waves. Why?

3. Any codesize-friendly way to get the closest, say 3 points from a set of points? (Keep in mind the set of points won't be large, at max probably 1000 points, so speed isn't TOO big of an issue)

4. Any recommendation for changes in the segments (currently lateral velocity, distance from center, distance from me)?

--Starrynte 01:19, 29 September 2009 (UTC)

My thoughts:

1. I use multiple sets of scans in my DC Anti-Surfer gun. One of them is collected from bullet hits, and I give those a negative weight in the kernel density calculation. Basically, a potential firing angle is penalized for being near a bullet hit firing angle. Doesn't sound very code size friendly, though.
2. If you fire and turn your gun on the same tick, the firing happens first. So the segmentation data on the wave should be from the tick before it is fired, because that's how it will be when you actually fire.
3. Not really. =) I have a MiniBot DC gun still lying around, but the part that gets the closest scans is pretty big.
4. I'm not sure distance to center is very useful in 1v1. Accel is a good one (whether the enemy accelerated, decelerated, or stayed same speed since last tick), and so are time since velocity change and wall distance.

--Voidious 01:37, 29 September 2009 (UTC)

• Which leads to the question, any easy way to find wall distance (particularly codesize)? --Starrynte 02:07, 29 September 2009 (UTC)

The smallest way would probably be Math.min(Math.min(enemyX, battleFieldWidth - enemyX), Math.min(enemyY, battleFieldHeight - enemyY)), which is the shortest distance to any wall. The smallest "good" way (imo) I know of to do it can be snagged from Komarious/Code, which basically tests if a bearing offset projected enemyDistance from my bot would be out of bounds or not. --Voidious 02:21, 29 September 2009 (UTC)

Lateral Acceleration

What is the maximum possible lateral acceleration, taking into account the fact that robocode is tick-based? --Starrynte 04:22, 26 September 2009 (UTC)

Max lateral acceleration is 1 pixel per tick, and max lateral deceleration is 2 pixels per tick. Just look at the formula, if the angle inside the sin() is PI/2 (or 90 degrees), ie. they are going perpendicular, then it is exactly the same as regular acceleration/deceleration. --Skilgannon 05:59, 26 September 2009 (UTC)

No, it's not the same Skilgannon. Consider the situation where a bot is moving at 8 speed perpendicular. In order to decelerate it can reduce it's speed by 2 units, AND it can also simultaneously rotate away from perpendicular in order to reduce the lateral velocity even further. --Rednaxela 04:00, 29 September 2009 (UTC)

Rednaxela is right, I once calculated those values, but don't have them anymore. But they where somewhere around [2.02, 1.02]. --zyx 01:28, 30 September 2009 (UTC)

I went ahead I try to figure them out again, this is the C++ code I used.

double max_deccel = 0, dsv, dev;
double max_accel = 0, asv, aev;
const double delta = 1e-5;
const double pi = acos(-1.);
for ( double x = 2; x < 8; x += delta ) {
  double y = x - 2;
  double vx = x * sin(pi / 2);
  double vy = y * sin(pi / 2 + pi / 18 - y * pi / 240);
  if ( vx - vy > max_deccel ) {
    max_deccel = vx - vy;
    dsv = x;
    dev = y;
  }
}
for ( double x = 0; x + 1 - 1e-9 < 8; x += delta ) {
  double y = x + 1;
  double vx = x * sin(pi / 2 - pi / 18 + y * pi / 240);
  double vy = y * sin(pi / 2);
  if ( vy - vx > max_accel ) {
    max_accel = vy - vx;
    asv = x;
    aev = y;
  }
}
printf("lat deccel (%.4f -> %.4f): %.10lf\n", dsv, dev, max_deccel);
printf("lat accel (%.4f -> %.4f): %.10lf\n", asv, aev, max_accel);

The results are

lat deccel (6.4478 -> 4.4478): 2.0300517561
lat accel (4.1138 -> 5.1138): 1.0237884289

This maximums are achieved at rather odd velocities (6.4478, 4.1138) those aren't lateral velocities but actual velocities. Changing delta to 1, uses only integer values for speed, and the maximums are:

lat deccel (6.0000 -> 4.0000): 2.0298153934
lat accel (4.0000 -> 5.0000): 1.0237746471

Hope this helps. --zyx 01:53, 30 September 2009 (UTC)

• It does, in fact, thank you! As for the "odd" velocities, it isn't that odd I think because if you're going slower you can turn faster. --Starrynte 02:08, 30 September 2009 (UTC)
• Hmm, actually the theoretical maximum decel is 8, since if you're going full speed and you hit a wall, you could go from 8 to 0. --Starrynte 03:25, 30 September 2009 (UTC)

Does assuming the direction is 1 when the enemy isn't moving cause a large performance hit, compared with assuming the direction is the last "good" lateral velocity? --Starrynte 02:08, 30 September 2009 (UTC)

Well, it probably depends on your gun, but it certainly could confuse your gun a lot against a Stop And Go movement. I'd test against some of the top MicroBot duelists to see what happens when they orbit you counter-clockwise (particularly if they orbited you clockwise in the previous round(s)). --Voidious 02:26, 30 September 2009 (UTC)

Max Escape Angle

Is it better to use a fixed MEA (i.e. asin(8/11) ) or a MEA that depends on enemy velocity (i.e. asin(enemy velocity/11) )? If they're about equal, what are the pros and cons? --Starrynte 05:04, 29 September 2009 (UTC)

No it isn't the same. Haven't test asin(enemy velocity/11) though. But one BIG problem is when enemy is currently stop, this code will yield zero as an MEA. Now enemy moves, wave hit, and we found that the angle offset is 40°, which is ~GF0.86 (40°/46.6°) with normal MEA, but it is (40°/0°), which is Double.POSITIVE_INFINITY in java, with your variable MEA. You see the point. Nat Pavasant 12:23, 29 September 2009 (UTC)

Er, I don't think "asin(enemy velocity/11)" makes sense. That would only make sense if they never exceeded their current speed. If you mean MEA via Precise Prediction (which does depend on current velocity), then some people seem to think it's good for guns but not for surfing. I don't think there's any kind of valid MEA that depends on current velocity other than "Precise MEA", or perhaps a variant on standard MEA that doesn't quite use precise prediction but considers how the enemy must accelerate (which would be almost as complicated as "Precise MEA" anyway I think) --Rednaxela 15:06, 29 September 2009 (UTC)

Ah yes, I forgot that this is *Max* escape angle :) --Starrynte 01:13, 30 September 2009 (UTC)

Shooting out of bounds

How are angles that potentially shoot out of bounds filtered? Do you just assume the current enemy distance? --Starrynte 05:07, 29 September 2009 (UTC)

I don't think many bots (not DrussGT anyway) do this. But I know that Coriantumr uses what you describe. --Nat Pavasant 12:25, 29 September 2009 (UTC)

Bots that do "Precise MEA" cannot shoot out of bounds since the no GF with that scheme can be out of bounds. Many bots don't use that either though (none of mine do) and still have very strong guns. As I see it, if the bot has a decent wall segment (or that "Precise MEA"), then it will tend to avoid shooting out of bounds on it's own without an explicit mechanism. --Rednaxela 15:01, 29 September 2009 (UTC)

Disabled

What are pros and cons of collecting GF data while disabled? --Starrynte 02:54, 3 October 2009 (UTC)

Con: Any bot that knows there are no bullets in the air is free to move however they want and "poison" your stats (intentionally or not). Pro: Against any bot that continues to move normally, you are collecting useful data. Personally, I stop firing waves when I'm disabled, but still register ones that were already fired. --Voidious 03:01, 3 October 2009 (UTC)

Comparison to segmentation

Your description of translating a data point into a bin reminds me of segmentation and Visit Count Stats. I'm curious - could you give any more details on how this works, and/or how it's different than segmentation? --Voidious 13:15, 23 September 2009 (UTC)

It actually is similar to segmentation, only rather than having say stats[VELOCITY_SEGMENTS][DISTANCE_SEGMENTS][WALL_SEGMENTS][etc...], you'd have just stats[COMBINATION OF VELOCITY, DISTANCE, WALL, ETC]. The combination is the LSH process. --Starrynte 02:03, 24 September 2009 (UTC)

Maybe not a first?

You know... I think that maybe this isn't the first Locality Sensitive Hash targeting in Robocode. Doesn't Locke's description seem to sound like a form of locality sensitive hash targeting? It does say "Along with that Observation, a number of situational parameters are stored. The Log is ordered in such a way that similar Observations will become neighbours." and once looking at the code I noticed it stored things in a 1d list which it tried to order to preserve locality. --Rednaxela 04:29, 24 September 2009 (UTC)