Editing revision 53 of Horizon/Questions

Robo Home | Changes | Preferences | AllPages

Editing old revision 53. Saving this page will replace the latest revision with this text.

On this page, I humbly beg for help from the Robocode masters.

=== Pummeled by Linear / Circular Targeting ===

I think I know why it is that [[Horizon]] is ranked much lower than [[BasicGFSurfer]] on RoboRumble. Check out these scores from the [[WaveSurfingChallenge2K6]]:

|Bot Name                  |Score vs. Bot A|Score vs. Bot B|Score vs. Bot C|'''Overall Score'''
| [[BasicSurfer]] 1.0      | 91.59         | 58.87         | 61.09         | '''70.51'''
| Horizon 0.9.2.1          | 99.184        | 53.574        | 38.346        | '''63.70'''

In other words, Horizon outperforms BasicSurfer by a large amount when dodging HOT, but, against linear/circular targeting, gets converted to spare parts. Not that BasicSurfer is exactly top-notch at dodging linear targeting, but at least it doesn't get *killed* by the challenge bots! Anyone have suggestions as to how to avoid this type of targeting? Is it segmentation on velocity? (At one point I tried putting segmentation on Horizon's movement, but even when I had only one segmentation dimension its learning became much too slow - see next question.)

=== Data Smoothing Across Segments ===

The gun used by the current version of Horizon has about the maximum segmentation it can before starting to lose performance from slow learning. This problem could probably be reduced if I had smoothing across segments in addition to smoothing across bins. Unfortunately, I haven't found any simple, easy to implement segment smoothing code. The current layout of my code looks like this:

<pre>
private double[][][][] gunStats = new double[DISTANCE_BINS][VELOCITY_BINS][LATERAL_VELOCITY_BINS][BINS];

private void updateWaves() {
	for (int i = 0; i < myWaves.size(); i++) {
		Wave ew = myWaves.get(i);

ew.advance(robot.getTime());
		if (ew.isHit(enemyLocation)) {
			double[] segment = getSegment();
			ew.logHit(segment, enemyLocation, rollingDepth);

myWaves.remove(i);
			i--;
		}
	}
}

private double[] getSegment() {
	int distanceSegment = (int) round(limit(0,
			myLocation.distance(enemyLocation) / 200, DISTANCE_BINS - 1));
	int velocitySegment = (int) round(abs(enemyVelocity / 2));
	int lateralVelocitySegment = (int) round(abs(enemyLateralVelocity / 2));

return gunStats[distanceSegment][velocitySegment][lateralVelocitySegment];
}
</pre>

Note that the logHit() method does [[BinSmoothing]] on its own, and has a weight of 1.0 by default but can also accept a weight parameter. How would I implement segment smoothing here (preferably without a large performance hit)?

----

For the poor performance against Bots B and C in the WSC, I just wanted to say it probably isn't segmentation - BasicSurfer doesn't segment at all and is still getting much higher scores than you. There are a lot of places the bugs could be hiding, so you probably know where to look better than I would, but the first thing that comes to mind is to make sure your Precise Prediction is still correctly predicting your movement after the changes you made. If you are WallSmoothing, controlling distance, or anything differently than the original code was, you need to make sure the prediction is predicting that stuff correctly. E.g., [[Dookious]] adjusts distancing / attack angle and does WallSmoothing every tick, so I have to simulate those decisions in every part of the prediction.

As for the DataSmoothing, I have always found this to be incredibly slow when I tried it, though I haven't tried it for a while. There are other ways to overcome the problem, though. You could have multiple buffers, some with lower segmentations than others, and sum them to get the score for any segment - if your high buffer has no data, it will just sum in as a 0. DynamicClustering is a different style of stats, but it basically has DataSmoothing built into how it works. There are other little tricks you could try, as well, like switching from a low segmentation to a higher one once you have enough data.

Hope some of that is helpful, good luck!

-- [[Voidious]]

I found that I get poor preformance vs B and C when the wave detection is a little off, it might dodge to late and get hit, Head On is easiest to dodge, and noticed very little difference in its stat. I personally like DynamicClustering, its power is unquestionable, as its used in Lukious, Shadow and Chalk, all very nice, very powerful bots. DataSmoothing is very slow on anything but two or three segments, I have tried it and it can really slow a bot down. --[[Chase-san]]

Thank you, thank you, THANK YOU! Not only did I find a bug in my surfing that caused waves to lag behind bullets by a couple ticks, but fixing that, tweaking a few variables, and sorting my GuessFactors with DynamicClustering instead of segmentation improved Horizon's scores against all three test bots:

So Horizon's surfing is now better overall than BasicSurfer against simple targeting. I also added DC to the gun, so I will be releasing an improved (hopefully) version soon.

-- [[AaronR]]

----

Time for a second round of questions.

=== Execute Every Turn ===

It's somewhat hard to understand how I have been working with Robocode for this long and not come upon this problem. The problem is: how do I execute a non-blocking call every tick? That is, I have a nonblocking method that I want to execute *exactly* once every tick, regardless of whether I scan the enemy or not on that turn. I can't use execute() or waitFor(), as those would cause all nonblocking calls to execute immediately, which is not what I want. Do I have to use custom events?

<pre>
public void run() {
	// ...

do {
		foo();
		execute();	// Won't work! Executes foo() and all other nonblocking calls!
	} while (true);
}
</pre>

* The code you have above is a good way to do it, but there are a few caveats.  1) make sure everything you want to execute that turn has happened by the time you make the execute() call, and 2) make sure you don't use any of the blocking API calls anywhere else in your code (e.g. don't call turnRadarRight() in onScannedRobot(), use <b>set</b>TurnRadarRight()).  Creating a custom event would work, too, but I think putting execute() into a loop in the run() method is more straightforward.  -- [[Simonton]]
** #1 you list was exactly the problem: execute() could get called before all events finish on a turn. I fixed the problem in my code by using a custom event with the highest possible priority that always evaluates to true, but I wanted to know if there was a better way. -- [[AaronR]]
* Something doesn't add up here.  When you say "before all events finish on a turn", do you mean an event like ScannedRobotEvent (or, actually, its handler, "onScannedRobot")?  If that's the case, events happen one after the other unless you're creating your own threads, and only after they are all done could execute() return.  So (unless you're using threads) no events can be in-process between calls to execute() in your loop above.  What am I missing? -- [[Simonton]]
** I think what you are missing is that I am using a custom-built plugin system that delegates events. The code looks like this:

<pre>
public class Horizon extends AdvancedRobot {
	private static List<Component> components = new ArrayList<Component>();

static {
		components.add(new RadarLock());
		// ...
	}

public void run() {
		// ...

for (Component component : components) {
			component.startRound(this);
		}

/* The problem */
		do {
			for (Component component : components) {
				component.eachFrame();
			}

execute();
		} while (true);
	}

public void onScannedRobot(ScannedRobotEvent e) {
		for (Component component : components) {
			component.scannedRobot(e);
		}
	}

public void onHitByBullet(HitByBulletEvent e) {
		for (Component component : components) {
			component.hitByBullet(e);
		}
	}

// ...
}

public abstract class Component {
	protected AdvancedRobot robot = null;
	
	public final void startRound(AdvancedRobot robot) {
		this.robot = robot;
		startRound();
	}
	
	protected void startRound() {
	}
	
	public void eachFrame() {
	}
	
	public void scannedRobot(ScannedRobotEvent e) {
	}
	
	public void hitByBullet(HitByBulletEvent e) {
	}

// ...
}

public class RadarLock extends Component {
	public void eachFrame() {
		robot.setTurnRadarRightRadians(Double.POSITIVE_INFINITY);
	}
	
	public void scannedRobot(ScannedRobotEvent e) {
		// ...

robot.setTurnRadarRightRadians(...);
	}
}

</pre>

I admit I was being somewhat unclear. The problem is, running Horizon with this setup makes it spin the radar forever without getting a lock, because scannedRobot() in RadarLock is being called *before* eachFrame(). That is, eachFrame()'s turnRadarRight(POSITIVE_INFINITY) is overriding scannedRobot()'s radar lock. I replaced the problematic loop with a custom event with the highest priority so that eachFrame() would always be called *before* any other events are executed.

-- [[AaronR]]

* Gotcha.  As far as any "better" ways - I think some of the big boys collect all the events in a list, then process them in a loop inside the run() method.  That gives you complete control over the order in which they happen.  But your solution also seems like a very good way to get code to execute before any events are processed. --[[Simonton]]

=== Move Away Code Could be Better ===

In Horizon, two sections of code work together to avoid being close to the enemy. The first is a simple angle adjustment that causes the bot to spiral outward. The second is a modification to the danger factor of predicted positions that looks like this:

<pre>
private double checkDanger(Wave wave, double[] segment, int direction) {
	double danger = 1.0;
	Point2D.Double location = predictPosition(wave, direction);

// ...

if (location.distance(enemyLocation) < myLocation.distance(enemyLocation)) {
		danger *= 1.02;
	}

return danger;
}
</pre>

The problem with this is, it tends to make the bot settle into a nice, comfortable spot in the corner and vibrate back and forth - not a good thing! However, taking out this adjustment makes the bot head along the wall that the enemy is on and barrel right towards them (due to the wall smoothing). What alternative methods of avoiding the enemy are there?

* This is a basic problem with any orbital movement.  I think a lot of people (myself included) force the bot to switch orbit directions if wall smoothing would cause it to "dive" toward the enemy too sharply.  A new random movement I made couples this type of "dive protection" with a tendency to move toward the line through the enemy and the center point of the field.  I haven't tested it much in real battles yet, but judging by its behavior WaveSerpent does this same thing, and its movement is very good.  -- [[Simonton]]

* What I do in [[Decado]] is set the default orbital angle slightly away from perpendicular, but if I am further than 400 pixels from them I set it to slightly towards them. The value of 400 I sucked out of my thumb, but it seems to work quite well. I also gleaned (from [[RaikoNano]]) a very easy way to set the "dive protection" mentioned above: assuming a perpendicular bearing would have an 'offset' towards the enemy of PI/2, if the wallsmoothed bearing has an 'offset' of less than PI/3.5 I change orbit direction. This works for RandomMovement, I'm not sure how well it will work for [[WaveSurfing]]. -- [[Skilgannon]]

*After a bit of thought, here's how you could implement dive protection in [[WaveSurfing]]: if the projected position is a certain amount closer or further than the current position, add extra 'danger' to that direction. Maybe something like <pre>if(proj_dist/curr_dist < 0.8)increaseDanger(orbitDir);</pre> or <pre>if(Math.abs(proj_dist - curr_dist) > curr_dist/5)increaseDanger(orbitDir);</pre> --[[Skilgannon]]

=== Horizon Has a Seizure ===

Even with the enemy avoidance code taken out, Horizon spasms a lot. How do you deal with spasming? Also, I have tried adding a stop position to the code but it didn't make any improvement. Is there a way to detect when the bot is spasming and make it freeze instead?

* What's the problem with spasming? -- [[Simonton]]
** It is not a big problem, it's just that the movement doesn't have that gliding, sailing look that more advanced surfers do. It's more of an "it looks better that way" thing than an actual bug. -- [[AaronR]]

----

Now that the conversation has gotten completely out of control... =)

Where should we move this discussion to? It seems like so far, we have parts that could go to [[ShrapnelDodging]], [[AntiSurferTargeting]], [[GuessFactorTargeting]], maybe [[Trigonometry]]...

-- [[AaronR]]

I moved it over to [[WaveSurfing]], since that seemed like the biggest topic and it all related to that in some way or another. Feel free to delete this comment and your own if you want to keep this page nice and tidy. =) -- [[Voidious]]

----

This will probably be the last question before the 1.0 release of Horizon. I won't say anything specific about this release yet, but I will say that it will be completely different than the current version...

Anyway, here's the question:

=== Segmentation Optimization ===

The clustering factors used in the current release of Horizon are:
* distance to enemy
* velocity
* last turn velocity
* lateral velocity
* last turn lateral velocity
* time since direction change (where direction change is defined as a change in the three-way sign of velocity) [this factor is used in the gun only]

Can anyone suggest an improved set of segments? Possible factors I am considering include:

* advancing velocity, last turn advancing velocity
* time since velocity change (direction change seems to work better though)
* time since lateral velocity / lateral direction change

In addition, since I am using dynamic clustering, I can assign each factor a weight. Which factors should be weighted highest?

----

'''Post responses here'''

I think you have too many velocities; if you're in 1v1, I'd definitely just stick with lateral velocity. For me, these are the first attributes I try in a new gun: LateralVelocity, distance (or bullet time), time since velocity change (divided by distance or bullet time), accel (0 = decelerating, 1 = same speed, 2 = accelerating), and WallDistance.

The best way to segment WallDistance in 1v1, as far as I know / am concerned, is by segmenting on what amounts to "at what GuessFactor starting from now will the enemy be when they hit the wall if they keep orbiting me"; so a value of 1 means they will hit the wall right as my bullet arrives. One last minor thing: with DynamicClustering, I personally tend to do something like <code>min(wallDistance, 1)</code> for some values - if your WallDistance is 2 or 3 or 5, it amounts to about the same thing: you don't have to account for the wall. Hope this helps. (PS - they're not segments unless you're segmenting them! =) But segments and attributes are almost synonymous because of the popularity of VisitCountStats...)

Not sure I can give solid advice on the weights, but I'd say LateralVelocity and distance would be the first ones I'd try to give higher weights to.

-- [[Voidious]]

Thanks, that is exactly what I was looking for advice-wise! ;-) I think I threw in so many velocity factors because I saw someone said at some point that acceleration was a good segment (not factor or attribute, segment, since there were no GF guns using clustering at the time), and someone else said that lateral acceleration was also good, and ... you get the idea. -- [[AaronR]]

----

Well, as it turns out, that was not the last question before the 1.0 release.

=== Surfing Multiple Waves Isn't as Easy as It Looks ===

I've got most of the movement coded for Horizon 1.0, but the danger calculation and precise prediction related to surfing multiple waves is giving me a problem. Specifically, I realized that during my precise prediction, I would have to advance not one but all of the waves I am surfing. Of course, if I actually did this, I wouldn't be able to surf the waves after one tick (since the state is being corrupted), so I have to make a copy of all of the waves. However, because I still have danger calculations for the next waves after this, I have to do the copying recursively. And the recursive copying is now three-way instead of two-way, since I added evaluation for a stop position. Oh, and I still have to do all of this three times, because I need to determine which direction to surf. The inevitable result of this three-way recursive deep copying three times is that my robot is using up all of my system's memory and skipping turns all over the place.

Now what?

----

'''Post responses here'''

Hmm, I'm not sure I really understand your code situation - why do you have make multiple copies of all the waves? Let me try this: as you move tick by tick through the prediction, you can calculate the bot's distance to the wave source and the distance the wave has traveled by that tick, without actually modifying the wave (and thus needing to copy it to have the original version); those are all the data you need to check if the wave has intercepted you by that tick. Am I imagining this dilemma correctly, or am I way off here? =) -- [[Voidious]]

You are close, that is pretty much what I was doing with all of my previous versions that only surfed one wave (look at lines 213-217 of BasicSurfer, that is what I was doing). My current problem is that I now have to determine when one wave hits, precise predict that, and then determine when the next wave will hit, ''adjusting for the time during which I was predicting my surfing for the first wave''. So I could predict that wave A will hit in 10 ticks, then start predicting wave B, but I have to compensate for the distance B "traveled" while A was being predicted. To do this I either have to mutate the waves in the precise prediction function or have the function pass back an integer indicating how many ticks will elapse before the relevant wave hits, and then mutate the waves in the danger function. Either way I end up with a mess.

P.S. Sorry if I can't make it any clearer, my code is about as clear to me as mud right now.

-- [[AaronR]]

So why can't your precise prediction function return a class with position and time? Than that will be the base to calculate the next-wave danger. Not that I used it, but probably I also need it if I want to improve my multiple-wave precise prediction.  -- [[GrubbmGait]]
* You are dead on, that is what I need. It seems like a bit of a waste to make a whole class just for one function though. But I suppose the only alternative is to pass an integer to the precise prediction method by reference, and since Java doesn't have pointers, some of the screwier aspects of the language (wrapper classes) would come into play. So yeah, I'll probably just make an inner class. -- [[AaronR]]

What I did in DrussGT was to weight waves by multiplying the danger at a point by pow(0.55, timeUntilArrival - 15). This function tapers off quickly, so the closest waves get weighted almost exclusively, but it will still weight ChaseBullets quite highly. However, why don't you return an array of points from your PrecisePrediction, adding a point each time a wave passes? -- [[Skilgannon]]

You do need to compensate for the time B traveled while surfing A, but no need to permanently "mutate" the wave! The wave has logged its starting (center) point, time fired, and bullet velocity. Your wave class could have a ''distanceToBot(Point2D bot, time t)'' method that calculates ((how far from wave source to enemy bot) - (distance traveled at time t)) - you'd surf it until that is less than zero. When you surf wave A, say you have a variable ''time = now'' that increments by 1 as you surf; then pass that off to the method that's surfing wave B and start at time t = wave A intercepted you. Right? -- [[Voidious]]

* Re-reading, I wonder if this is what you are already doing... ? :-\ But this shouldn't include making a copy of every wave, I don't think. -- [[Voidious]]

Here is basically what my code ''should'' do:

* My movement function invokes my danger function on wave A with direction -1.
** My danger function calls my precise prediction function on wave A, passing in the bot's current location and 0 ticks already elapsed.
*** My precise prediction function determines wave A will hit in 5 ticks at point X.
** My danger function adds a danger from point X and recursively calls itself on wave B.
*** My danger function calls my precise prediction function on wave B, passing in - here's the key - ''point X and 5 ticks'' already elapsed.
**** My precise prediction function determines wave B will hit in 10 ticks at point Y, ''after adjusting for the 5 ticks already elapsed in getting to point X''.

... etc ...

Hope that makes things clearer.

-- [[AaronR]]

Well, if that's not what your code is doing, then you need to refactor =). I always put it off, because I'm scared of breaking things when I do. -- [[Skilgannon]]
* Been there, done that. =) I think that at this point the only thing stopping me from fixing everything trivially (using [[GrubbmGait]]'s suggestion) is that I won't have access to my computer with Robocode on it until later tonight. -- [[AaronR]]

Summary:
Consciousness check: 6 - 4 =
This change is a minor edit. Send email notification that Horizon/Questions has been changed.
(Visit Preferences to set your user name.)

View other revisions
Robo Home | Horizon | Changes | Preferences | AllPages