View source for Talk:Gilgalad/movementStrategy

So, I've always been a big fan of Tomcat's movement strategy where, if I understand correctly, you use a bunch of classification schemes and then give them scores based on their performance. I tried this a long tie ago with Gilgalad, but it didn't work well. I'm giving it another shot now, and if nothing else, hopefully it will give me a better idea of what classifiers to use and when.

some data against raiko at the end of 35 rounds:

Classifier scores are based on the predicted probability given for a known bullet being within a certain range (for now +or- 0.2 radians). After each known enemy bullet, this is updated and the printed score is classifierNScore/classifier0Score.

Battle 1:


Classifier 0 scores :1.0
Classifier 1 scores :0.9755870469605517
Classifier 2 scores :1.2369225462233957
Classifier 3 scores :1.7528612982062486
Classifier 4 scores :1.5329624603178138
Classifier 5 scores :1.234924887594898
Classifier 6 scores :1.4174531972595874
Classifier 7 scores :1.3371945667211411
Classifier 8 scores :1.4380071717393625
Classifier 9 scores :1.893821500835094
Classifier 10 scores :1.9142428440452988
Classifier 11 scores :1.813500313301308

Battle 2:
Classifier 0 scores :1.0
Classifier 1 scores :1.1423071895729844
Classifier 2 scores :1.3729425281975491
Classifier 3 scores :1.7008483463501145
Classifier 4 scores :1.182167218778795
Classifier 5 scores :1.4489710167607848
Classifier 6 scores :1.458752434946134
Classifier 7 scores :1.4119814269034254
Classifier 8 scores :1.5747806346700741
Classifier 9 scores :1.7756977755746486
Classifier 10 scores :1.8393932242812359
Classifier 11 scores :1.6320145203001994

Battle 3:
Classifier 0 scores :1.0
Classifier 1 scores :0.9247600453962282
Classifier 2 scores :1.1469307013639247
Classifier 3 scores :1.5011101838893393
Classifier 4 scores :1.6256472273752074
Classifier 5 scores :1.5499125684940858
Classifier 6 scores :1.425592000093903
Classifier 7 scores :1.5781481081082624
Classifier 8 scores :1.6686308538501025
Classifier 9 scores :1.7011388408736738
Classifier 10 scores :1.7764882022837205
Classifier 11 scores :1.6438392150877148


the classifiers are set up as follows:

		ClassificationWeightingScheme CWS = new AntiSimpleTargeterWeightingScheme();
		MovementClassifier MC = new KNNMovementClassifier(CWS, 36, 0, 5, 3, 1.0, 
				Double.MIN_VALUE, 0.0, 0.15);

		CWS = new AntiSimpleTargeter2WeightingScheme();
		MC = new KNNMovementClassifier(CWS, 36, 0, 5, 3, 1.0, Double.MIN_VALUE, 0.0, 0.15);

		CWS = new AntiSimpleTargeter3WeightingScheme();
		MC = new KNNMovementClassifier(CWS, 36, 0, 5, 3, 1.0, Double.MIN_VALUE, 0.0, 0.15);
		
		CWS = new AntiStandardTargeterWeightingScheme();
		MC = new KNNMovementClassifier(CWS, 36, 0, 5, 10, 50.0, Double.MIN_VALUE, 0.0, 0.08);

		CWS = new AntiSemiAdvancedTargeterWeightingScheme();
		
		MC = new KNNMovementClassifier(CWS, 36, 1, 5, 5, 50.0, Double.MIN_VALUE, 4.0, 0.08);
		Classifiers.add(MC);
		MC = new KNNMovementClassifier(CWS, 36, 3, 5, 5, 50.0, Double.MIN_VALUE, 4.0, 0.08);
		Classifiers.add(MC);
		MC = new KNNMovementClassifier(CWS, 36, 5, 5, 5, 50.0, Double.MIN_VALUE, 4.0, 0.08);
		Classifiers.add(MC);
		MC = new KNNMovementClassifier(CWS, 36, 10, 5, 5, 50.0, Double.MIN_VALUE, 4.0, 0.08);
		Classifiers.add(MC);
		MC = new KNNMovementClassifier(CWS, 36, 20, 5, 5, 50.0, Double.MIN_VALUE, 4.0, 0.08);
		Classifiers.add(MC);
		MC = new KNNMovementClassifier(CWS, 55, 50, 5, 5, 50.0, Double.MIN_VALUE, 4.0, 0.08);
		Classifiers.add(MC);
		MC = new KNNMovementClassifier(CWS, 105, 100, 5, 5, 50.0, Double.MIN_VALUE, 4.0, 0.08);
		Classifiers.add(MC);
		MC = new KNNMovementClassifier(CWS, 36, 0, 5, 10, 50.0, Double.MIN_VALUE, 4.0, 0.08);
		Classifiers.add(MC);



public class AntiSemiAdvancedTargeterWeightingScheme extends
		ClassificationWeightingScheme {
	
	public AntiSemiAdvancedTargeterWeightingScheme() {
		_weights = new double[] { 4.0, 4.0, 1.5, 2.0, 3.0, 3.0, 3.0, 3.0, 2.0};
//		_weights = new double[] { 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0};
	}

	@Override
	public double[] getPointCoordinates(DataWave wave) {
		MovementDataWave movementWave = (MovementDataWave) wave;

		double[] dataPointCoordinates = new double[_weights.length];
		dataPointCoordinates[0] = _weights[0] * movementWave.getBulletTravelTime()
				* 0.009166667;
		dataPointCoordinates[1] = _weights[1]
				* Math.min(Math.PI / 2, wave.getAheadWallDist()) / (Math.PI / 2);
		dataPointCoordinates[2] = _weights[2]
				* Math.min(Math.PI / 2, wave.getReverseWallDist()) / (Math.PI / 2);
		dataPointCoordinates[3] = _weights[3]
				* (wave.getVChange() + Rules.DECELERATION)
				/ (Rules.ACCELERATION + Rules.DECELERATION);
		dataPointCoordinates[4] = _weights[4] 
				* Math.sin(movementWave.getRelHeading());
		
		dataPointCoordinates[5] = _weights[5]
				* (Math.cos(movementWave.getRelHeading()) + 1) / 2;
		dataPointCoordinates[6] = _weights[6]
				* Math.abs(wave.getTargetVelocity()) / 8.0;
		dataPointCoordinates[7] = _weights[7] * Math.min(1.0, movementWave.getTicksSinceVelocityChange() / movementWave.getBulletTravelTime());
		dataPointCoordinates[8] = _weights[8] * movementWave.getRobotDistLast10Ticks() * 0.0125;


		return dataPointCoordinates;
	}
}

public class AntiStandardTargeterWeightingScheme extends
		ClassificationWeightingScheme {
	
	public AntiStandardTargeterWeightingScheme() {
		_weights = new double[] { 4.0, 4.0, 1.0, 2.0, 3.0, 3.0, 3.0, 3.0, 2.0};
//		_weights = new double[] { 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0};
	}

	@Override
	public double[] getPointCoordinates(DataWave wave) {
		MovementDataWave movementWave = (MovementDataWave) wave;

		double[] dataPointCoordinates = new double[_weights.length];
		dataPointCoordinates[0] = _weights[0] * movementWave.getBulletTravelTime()
				* 0.009166667;
		dataPointCoordinates[1] = _weights[1]
				* Math.min(Math.PI / 2, wave.getAheadWallDist()) / (Math.PI / 2);
		dataPointCoordinates[2] = _weights[2]
				* Math.min(Math.PI / 2, wave.getReverseWallDist()) / (Math.PI / 2);
		dataPointCoordinates[3] = _weights[3]
				* (wave.getVChange() + Rules.DECELERATION)
				/ (Rules.ACCELERATION + Rules.DECELERATION);
		dataPointCoordinates[4] = _weights[4] 
				* Math.sin(movementWave.getRelHeading());
		
		dataPointCoordinates[5] = _weights[5]
				* (Math.cos(movementWave.getRelHeading()) + 1) / 2;
		dataPointCoordinates[6] = _weights[6]
				* Math.abs(wave.getTargetVelocity()) / 8.0;
		dataPointCoordinates[7] = _weights[7] * Math.min(1.0, movementWave.getTicksSinceVelocityChange() / movementWave.getBulletTravelTime());
		dataPointCoordinates[8] = _weights[8] * movementWave.getRobotDistLast10Ticks() * 0.0125;

		return dataPointCoordinates;
	}
}


public class AntiSimpleTargeterWeightingScheme extends
		ClassificationWeightingScheme {
	
	public AntiSimpleTargeterWeightingScheme() {
		_weights = new double[] { 1.0, 1.0 };
	}

	@Override
	public double[] getPointCoordinates(DataWave wave) {
		MovementDataWave movementWave = (MovementDataWave) wave;

		double[] dataPointCoordinates = new double[_weights.length];
		dataPointCoordinates[0] = _weights[0] * movementWave.getBulletTravelTime()
				* 0.009166667;
		dataPointCoordinates[1] = _weights[1] * Math.abs(movementWave.getTargetVelocity() * Math.sin(movementWave.getRelHeading()))
				/ 8.0;

		
		return dataPointCoordinates;
	}
}

public class AntiSimpleTargeter2WeightingScheme extends
		ClassificationWeightingScheme {
	
	public AntiSimpleTargeter2WeightingScheme() {
		_weights = new double[] { 1.0, 1.0, 1.0};
	}

	@Override
	public double[] getPointCoordinates(DataWave wave) {
		MovementDataWave movementWave = (MovementDataWave) wave;

		double[] dataPointCoordinates = new double[_weights.length];
		dataPointCoordinates[0] = _weights[0] * movementWave.getBulletTravelTime()
				* 0.009166667;
		dataPointCoordinates[1] = _weights[1] * Math.abs(movementWave.getTargetVelocity())
				/ 8.0;
		dataPointCoordinates[2] = _weights[2] * (Math.cos(movementWave.getRelHeading()) + 1) / 2;

		
		return dataPointCoordinates;
	}
}

public class AntiSimpleTargeter3WeightingScheme extends
		ClassificationWeightingScheme {
	
	public AntiSimpleTargeter3WeightingScheme() {
		_weights = new double[] { 1.0, 1.0, 1.0, 1.0, 1.0};
	}

	@Override
	public double[] getPointCoordinates(DataWave wave) {
		MovementDataWave movementWave = (MovementDataWave) wave;

		double[] dataPointCoordinates = new double[_weights.length];
		dataPointCoordinates[0] = _weights[0] * movementWave.getBulletTravelTime()
				* 0.009166667;
		dataPointCoordinates[1] = _weights[1]
				* Math.sin(movementWave.getRelHeading());
		dataPointCoordinates[2] = _weights[2]
				* (Math.cos(movementWave.getRelHeading()) + 1) / 2;
		dataPointCoordinates[3] = _weights[3] * Math.abs(movementWave.getTargetVelocity())
				/ 8.0;
		dataPointCoordinates[4] = _weights[4] * (wave.getVChange() + Rules.DECELERATION)
				/ (Rules.ACCELERATION + Rules.DECELERATION);

		
		return dataPointCoordinates;
	}
}

AW 16:16, 31 March 2013 (UTC)

So, I have found a bug with Gilgalad's pathing where the path's coordinate is occasionally about 0.002 units from the correct coordinate. This is seems to happen only when switching from positive to negative velocity, but I think I handle the current rule for that correctly:

			if (moveDir != Math.signum(currentVelocity)) {
				if (currentVelocity > 2.0) {
					currentVelocity -= 2.0;
				} else if (currentVelocity < -2.0) {
					currentVelocity += 2.0;
				} else {
					currentVelocity = moveDir
							* (1.0 - Math.abs(currentVelocity) * 0.5);
				}
			}

On oddity I noticed is that I will have -0.0 for my velocity when moving from 2.0 to 0.0, but I don't think that would cause problems. Perhaps my trig function is not exactly the same as that used by robocode and that causes the difference?

Thanks for any help.

Well, the problem seems to occur more when the angle is near a multiple of PI. Any interesting quirks with sin() or cos() near those angles?

There are quirks with fast math classes.

I did look at your code but couldn't figure anything to cause a small discrepancy. One thing to consider is a rounding error from the "1.0 - x" or the "x * 0.5", but that would be a much, much smaller error than .002.

You should be able to deduce whether it's the angle or the distance that's off. Like if it's 0.002 off along the same heading, it's the distance, while if the new and predicted points are the same distance from the previous point, it's the heading. Right?

So, I have been working on my movement, and I theorized that VCS movements would have a small advantage in the rumble because VCS guns are so common. However, I dislike VCS because I have found KNN so much more intuitive. (Yes, I probably just had a lot of bugs in my VCS gun, but I still like KNN better.) The problem I have is that I can guess how important attributes would be for a random movement fairly well, but I can't guess what people would use in their guns so I can't do as good of a job with those. (Which basically means I just copy Diamond) So I wanted to try to make my KNN classifiers match VCS guns as much as possible (except for the flattener where being different is probably beneficial). Step one is to make classifiers that would match "typical" guns, like raiko, or GFTargeting tutorial, etc. Any thoughts on what is "typical" for VCS guns? Also I can't think of how the weights should be chosen. Any ideas?

Well, the same dilemma of "guess how important attributes would be" exists with VCS as well.

Anyway, fun thing is, you can actually determine in a fairly algorithmic manner, how to make a KNN search that behaves as closely as possible to a given VCS configuration (i.e. Raiko's like you mention) while still being continuious.

1. For each dimension, examine the VCS bins. If the size of the bins are non-equal (be careful to note how the minimum/maximum values of the dimension interact with the first/last bins), then you need to divise a continious function which curve fits the bin-size as a function of the value of the dimension. You can use any form of regression you like for this, provided the function stays above 0 for all.
2. For each dimension's "bin-size" approximation function, take it's integral. The resulting function should now be monotonic. We'll call this the "scaling function"
3. Feed each "scaling function" the minimum/maximum values for it's associated dimension and make note of the minimum/maximum values out of the function. Then divide the number of bins in the dimension by the difference between the maximum/minimum values, to get the scaling factor to make the range of the "scaling function" proportional to the number of bins. Multiply your "scaling function" by this.
4. Now, before inserting values into the kd-tree, you put them through this "scaling function", which should weight them approximately the same as how the VCS did :)

(Hmm... maybe I should write code to perform this procedure some time...)

Oh just to quickly reply to my old ponderings... I was slightly mixed up before. To get the scaling function you'd want to take the integral of the *inverse* of that bin width function.

Also, there's an easier procedure than that mess I was describing before:

Just do a regression to fit the data points of "bin number" versus "bin center" (and possibly add non-center points with the same bin number too), while ensuring the function resulting from regression is monotonic. That'll give the final scaling function straight out of the regression without needing any other funny business.

Well, the problem uwith that is it would copy the bins exactly which means that if a different bot used 6 distance bins instead of 8 it would give worse results. Thinking about it more, my guess is that giving each attribute equal weight is the best solution for a particular set of attributes and weighting attributes equally or proportional to the number of bots in the rumble using those attributes would be the best solution for the rumble. Anyways, weighting all attributes equally seems to give me about 3 more APS against Raiko.

I feel like "weighting everything equally" is almost an impossible notion. Like say you divide lateral velocity (range 0-8) by 8, and distance by 1000, and now you have them both in the range of 0-1, weighted "equally". But the lateral velocity is effectively weighted higher since the distribution is so much more spread out across the full range than distance (which is rarely 0 or 1000, and very frequently 400-600).

I've had some success with genetic algorithms for tuning attribute weights (with WaveSim), but still not a huge improvement on just hand tuning. The GA stuff is fun to play with though... Got some experiments running right now, in fact. ;)

RoboResearch is certainly the tool of choice for running long sets of tests, but you'd really need your own layer of code on top of it to do any GA stuff. I'd instead just use the Robocode control API (which is pretty easy) for running the battles and collecting the results from your GA code, which is probably easier than manipulating RoboResearch.

The issue I haven't tackled yet is how to actually export each version of the bot to test. You'd have to package it from code with an Ant task or something, or export a .properties file that the bot reads in (probably the route I'll take).

All my GA stuff so far has used WaveSim, but I want to use some real battles to rewrite RetroGirl's movement. Keep in mind that GA with real battles will be VERY slow... I've had GA runs that take many days using WaveSim, and WaveSim is orders of magnitude faster than real battles.

Trying to workaround the slowness of full battles can be part of the fun. There are advanced GA techniques out there to deal with slow fitness functions. I tried some of them with Combat, tuning movement/targeting/energy management weights, all at the same time, against DrussGT in full battles. It gave me a +10% APS increase against it in 2 days, but a huge APS decrease against the rest of the population (Combat 3.9.0 (GA tuned) and Combat 3.8.2).

Maybe I´ll try GA tuning against the whole population someday, to avoid the specialization artifact that happened before.

I was thinking that a bot could read/write data from its local file directory. Read the file as "parents," select parents via fitness function, apply crossover/mutation.. load those values as weights, fight, write result at end of battle.

Lather rinse repeat for thousands of battles. Maybe start culling the least fit members of the population once it gets large enough...

This relies on the bot itself to determine its own score though... iffy.

Ah, yeah, that's an interesting idea. In 1v1 you should be able to determine the score. But I know I have a lot of other state associated with the GA stuff itself, so it would be some extra pain to have to import/export that every battle. You'd also miss out on any chance to multi-thread it.

Well, my weighiting them equally idea was only for the movement, for the gun I definitely don't think that will help. (But I'm not sure how much it will hurt.) For VCS movement, each dimension needs to be in a certain range for the gun to use the data from that point. So I would say that each attribute was equally important because the gun needs to match each attribute. (Assuming there was no secondary buffer to go to if there were no matches in a given segment) That being said, because VCS is a binary test, while KNN is a search for the closest point, a normal KNN can't be expected to work exactly like different (but similar) VCS systems. Thinking about it more, it seems like you're right about equal weightings being more complicated than weighitng everything 1.0, but I'm not sure how to deal with that. My initial guess would be weight = 1 / probability_randomly_distributed_situation_in_bin. Which would mean that the weight should be equally to the number of bins used for each attribute.

One problem I have with weighting the distance (or bullet travel time) dimension higher is that, as you said, the distances will mostly be in a range of 400-600. If I were using say one point and I had the option of distance = 450 and velocity change = 0 or distance = 499 and velocity change = 1 with the current situation as distance = 460 and velocity change = 1, the best choice is probably the second point, but weighting the distance higher may favor the first.

I have been wondering for a while how much of Gilgalad's ranking is due to the weighting of KNN and how much is due to a fairly good gun system and wave surfing algorithm, so I am puting a version with all weights (including gun and flattener weights) set to 1.0. (Actually, I forgot to change the weights on the enemy bullet power estimation to 1.0, but I currently only use that for onWin events so it shouldn't make a big difference)

Very interesting experiment! And it's shaping up to look like a fascinating answer!

More accurately, for VCS, I would guess attributes don't have a level of "importance" (in the algorithm itself, using some is more important than using others), you just test how much you can segment the data while still having enough data, and choose arbitrary cutoff points, which is probably why I find KNN more intuitive. But I'm still trying to think of a proof for an optimal similarity between a VCS system with evenly distributed data accross all dimensions, with a set number of divisions in each dimension, but the divisions being started arbitrarily while being evenly spaced (ie. any number between 0 and 100 is the start of the first distance bin, each bin covers 100 units, and we pretend the points can't be less that the minimum value)

I've only seen a fraction of the VCS guns out there, but "typical" configurations are probably modeled after the big / influential VCS bots, like Raiko, PEZ's bots, FloodMini, maybe even Dookious.

I guess maybe this question is for other people, since if you're looking at Diamond, you already know what I think about what attributes are best. =) But no shame in starting with a Diamond-inspired configuration and trying to improve from there. I certainly took guidance from Raiko and CassiusClay, and I also keep my eye on what brainiacs like Rednaxela and Skilgannon are doing.

I think a more difficult task is modeling data decay in KNN surf stats. Whenever you get hit, it means that your existing data is inaccurate. (If it were accurate, you wouldn't have been hit.) Where you got hit is the peak in that segment of his gun, so it needs to out-rank the other data points in that segment of your stats, but you have no segments so you can't just use rolling average. I think tuning this aspect of your KNN surf stats is at least as important as getting the attributes just right.

DrussGT uses a "bullets shot" classifier to give higher weight to newer data and works somewhat like data decay. It makes k-NN search extrapolate a bit, but still helps increase the score against learning opponents.

IMHO, the advantage of VCS over DC is CPU performance. But VCS compresses data into bins and some information is lost, while in DC it isn´t. So, well tuned DC should perform better than well tuned VCS, unless you start skipping turns.

That is for the gun, but a similar thing is definitely useful in movement. Best would be one log which has data rolling, and one without to handle simple bots and make sure you don't forget anything about them. That trick actually comes from Rednaxela, and possibly even originally ABC. It causes the Kd-Tree to be a bit slower as the match progresses, but works wonders against surfers and is behind my recent-ish PL improvements.

I have a similar view on VCS vs DC - VCS is faster at lookups (obviously, index lookups are O(1)) but less accurate due to the discretisation of both the bins and the segments. However, even in a DC environment VCS has its place: if I were surfing DC I would cache my results in an array just like VCS to make lookups faster when evaluating surfing points. Note, DrussGT's movement doesn't actually use segmented VCS in the movement anymore, but instead lists of hit indexes in each segment. This reduced my storage space and my logging-hits time, and actually reduced my retrieve time as well because many of the hits are different representations of the same original hit (from my many buffers). I did some trickery with weighting the hits to make sure it gives exactly the same results as my VCS with a rolling average would have.

It's worth noting that in movement, you have far less data, so CPU speed is less of an issue. Until you get into flatteners, and even then maybe virtual wave flatteners (which are rare), DC surfing could probably do fine without even using kd-trees. Precise prediction far outweighs information management, I think.

And yes, having a dimension that is pure linear time is certainly one of the simpler approaches to KNN data decay... ;)

What I was actually doing in my gun was having a non-linear time dimension, and it worked out a lot better than straight linear. I think I ended up with 1.2*T^(0.4) or so, instead of 0.005*T. Those weights were genetically evolved with my WaveSim-ish setup.

It makes sense that at the beginning you want your data to decay faster than towards the end...

I've generally considered the time dimension a pretty blunt/naive approach (I think I used it in Lukious), but I've been mulling it for the last hour and now I'm thinking it's actually pretty reasonable. I might even tinker with it some in Diamond (especially now that I have your secret formula, muahahaha!).

I know I've posted it elsewhere, but the main system I use in decaying Diamond's surf stats is like this:

• No time dimension, but each data point is timestamped.
• After choosing k neighbors, sort them inverse chronologically and weight them by rank. (Eg, 16/8/4/2/1.)
• Optionally (like in flattener), I also cap the size of the log and remove the oldest points.

Tuning k is like adjusting the granularity of a VCS buffer: k=1 is like a super highly segmented buffer (most similar situation wins, regardless of age), while a larger k is like a less segmented buffer with rolling average.

While I've tried this in my Anti-Surfer gun, too, the most effective decay I've found there is just capping the size of the log and discarding old points.

FYI, was random page surfing for like 2 minutes and came across a previous discussion about KNN data decay, if anyone's interested: Talk:DrussGT#Head-to-head_27.

So, I have GoTo surfing of two waves working, but it is skipping a lot of turns. I haven't done any detailed tests but it seems like the battle speed is fairly fast for a bot in the top 10 so I am assuming that the turns are only being skipped because all of the calculations are done in one turn. Any ideas on how to improve performance? (A break down of the time spent on various things each turn is now printed at the end of each round.)

I did several things to get my goto working at decent speed:

1. Cache the danger value at each point on the second wave. That way, if you are able to reach the exact point before the wave hits, you don't need to look up the danger again.
2. Before calculating your second wave dangers, get all your first wave dangers. Sort each of these by danger, lowest to highest. That way, you can immediately break the moment your first wave danger exceeds your minimum first+second wave danger, because from then on it is impossible to get less than that.
3. Optimize your precise prediction as much as you can, then optimize it some more. Use FastTrig. Avoid divides. Cache values for cos/sin if your heading won't be changing any more. Compare squared distances instead of computing square roots.
4. Try to make your danger calculation as fast as possible. It gets called a LOT. If possible, stick everything in a 1D array so you just check the danger at that GF (or across a range) as you need it.

There's probably more, but I think these were the big ones.

1 and 2 looks a lot like transposition tables and pruning techniques used with success in chess engines. I was trying to find something similar in robocode for months, but failed.

You can cache square roots in 3 and only need to recalculate them when wave log is updated.

I will try more optimizations later today but one big one that I do use is only calculating changes in the movement path for the final calculation. So I make and estimate path and then I use the points along that path for my real paths until I need to move to a different point (Which is at most four indices prior to the destination point.) Skipped turns only seem to be a problem in the first round now (less than 5 turns skipped for the other rounds) here is a how time is spent in the first round against Raiko:

Wave Danger Time = 24.566979999999997 (time spent getting points from the KdTrees for the waves) OnScannedRobot Time = 197.411769 (time spent in OnScannedRobot for the movement) Wave Management Time = 39.465934 (time managing movement waves (this includes precise intersection for virtual waves every turn)) Move Calc time = 664.440483 (times spent calculating my movement path, includes the next four items) Path generation time = 230.93243999999999 (precise predictor path generation) First wave angles time = 266.566414 (precise interesection on the first wave) Check Danger time = 111.454803 (danger for the first and second wave, includes the time from the next item) Second wave danger time = 108.967914 (precise bot width and danger for the second wave)

Time spent on movement = 906.613341 Time spent on gun = 239.867495

One more thing. I use DC surfing so I don't actually spend that much time calculating the danger, less than 3 milliseconds for the first waves for the whole first round. And finally I do limit myself to the 5 best movement options from the first wave.

So, I have tried all of the ideas above, but am still skipping turns. Obviously I can still work on 3 and 4, but I had a question for the second wave points optimization: is a hashmap fast enough or should I try to make a custom class to handle that? Also, I ran Gilgalad 1.8 on Windows (yes, I admit it, I use Windows sometimes) to show some other people and noticed that it didn't skip any turns!?! Further tests show that it will occasionally skip turns but not nearly as much as it does on Linux (Fedora 16). This was all on the same computer but with slightly different versions of robocode (both 1.7.X however). Any ideas as to why it skips more turns on Linux?

My number one guess is... perhaps you are using a 64-bit OS in one case and 32-bit in the other case?That can have a significant impact on performance with pointers (which the JVM relies on much more heavily than typical compiled code)

Yes, the Linux installation is 64-bit but the windows is 32 bit. Thanks!

Maybe you have different CPU constants?

I spent about a month optimizing Tomcat and may give only one advice - accurate instrumenting for spent time measurements. Not only avg, but also min & max times. Only after i do it, i findout Tomcat's hotspots.

Didn´t try on Linux yet (yep, another Windows user). But in Windows 7, CPU affinity is having an impact on skipped turns. Which means different time sharing algorithms are leading to different amount of skipped turns.

Point 2 - I just use an arraylist for first wave points and another for second wave points. Put the first through Collections.sort() then iterate through. At each point calculate the min reachable second wave danger. However, if the first wave danger is more than the min first+second then break. I'm not sure why a hashmap would even help here?

Have you checked that your JVM is the same version for both? And CPU constant? 64 bit might be better at the raw throughput for the benchmark but about the same for stuff with lots of decisions in it, like a bot.

Actually 64-bit would probably be worse in some things too. Specifically, 64-bit mode means pointers take twice as much memory, thus effectively doubling memory bandwidth requirements for code that spends most of it's cpu time dealing with pointers between objects. For the case of robocode bots, deep recursive data structures are not too uncommon, and additionally Java is more subject to this problem than compiled object oriented languages, because Java doesn't allow non-reference composition of classes.

I meant would there be a faster way to cache the dangers of points on the secondary wave. For the first wave paths, I use an array and a quicksort that takes an array of dangers and returns an array of the order of the dangers, which was the fastest way I could think of doing this. I don't know much about hashmaps so I was wondering if there would be a faster way to store about 400 points and thenk check if any of them were identical to another point, on thinking it over, the points would probably be added in increasing or decreasing order of X and Y so I may be able to keep an arraylist sorted without much overhead.

Hmm. What I do is pre-calculate a whole bunch of points by precise predicting until a few ticks after the second wave has hit. Then I use these points as 'destinations' for my goto algorithm. Each point holds its own danger value, and this danger is the one used if the point is 'reachable', otherwise I calculate a new danger for whatever location the wave hits me at. That way I never run into problems with duplicate points, association etc.

What are the units of your time measurements?

The time measurements are in milliseconds, but I used System.nanoTime() so they should be fairly accurate. I have a few more ideas for optimizations that would make a large improvement, but hopefully I can get back to adding new features rather than making old ones run faster. Since I have the week off, maybe, just maybe, I can take the throne before I turn 18...

Well, I have spent untold hours optimizing and am still skipping turns on my 64-bit JVM but now I have two ideas. In the first round, Gilgalad is about 2 times slower than it is in the last round. Since it is processing more values in the last round, the difference should be due to the optimizer. So I tried using proguard to optimize Gilgalad before the start of a battle. There may have been some small improvement, but it isn't really noticeable. I don't know how the Java optimizer works, but is it possible that the CPU time spent on the optimizer is counted as time spent on the robot. This is the only explanation I can think of for why the speed is so much better later in the round but optimizing at compile time doesn't help. (Well, other than the "AW is making another of his stupid mistakes." explanation.) So my first idea was to try proguard. My next idea is to warm up the JVM with some pointless calculations for the first 30 turns of a battle, where I don't need to do anything CPU intensive, so I could surf some fake wave and not actually move on the fake path or something. However, I don't like the idea of making Gilgalad waste time doing nothing to make it appear faster.

The JIT compiler (optimizer) counts how many times each piece of code is executed and compiles them after a threshold is achieved (1500 executions in client mode, 10000 in server mode). Compilation is done in a background thread, and that piece of code stays in interpreted mode until the background compilation finishes. So, the optimization runs in background and should not interfere unless you limit the JVM to a single core. In client mode, optimization finishes faster and the JVM consumes less memory, but the resulting compiled code is slower. Server mode is the opposite.

You can change the threshold with the -XX:CompileThreshold=10000 option, change the optimizer to run in foreground with the -Xbatch option, choose client mode with the -client option, and server mode with the -server option. Experimenting with different settings may help understand what is going on.

Maybe it is skipping turns while it is still running in interpreted mode (beginning of first round), after the bot history grows a bit. After the code switches to compiled mode, it becomes faster and stops skipping turns.

Warming the JVM with pointless calculations probably won´t work since the JIT compiler will compile only that piece of pointless code. And sometimes, warming up confuses the optimizer and it activates the wrong set of optimizations, resulting in slower compiled code.

It might have something to do with your java settings - maybe try using the client VM instead of the server one (which is default on Linux IIRC).

Otherwise, try giving DrussGT a run and see how many turns get skipped. It usually skips around 2/match on my laptop.