GoTo surfing.

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.

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...