Monday, December 21, 2015

Battlecode idioms

In this post I talk about Battlecode-specific coding idioms I've used. Battlecode can encourage some weird constructions, usually because you want to save bytecodes. Before reading this post you should probably read Cory Li on bytecode optimization. Also check out Steve Arcangeli's code snippets.

Static everything

It turns out that accessing a static field or method of a class is cheaper (in bytecodes) than accessing a regular field or method. The reason is that normally to access a field or method you first have to push the "this" reference onto the stack, which costs an extra bytecode. So if you have a class for which you only ever make one instance, it's better to just make everything static and not make any instances.

Wait, but won't all your different robots interfere with each other by setting the same static fields? No: each robot has its own Java Virtual Machine. This means that static fields for one robot are not shared with other robots. (It has to be this way, otherwise you'd get free inter-robot communication).

In my code, everything is static unless there's a reason it can't be. One annoying case is that if you want to use virtual functions (that is, if you want to override a base class method or interface method) these have to be non-static.

Maps inside the broadcast array

This may change in the future, but in 2014 and 2015 each team had 65536 broadcast channels for communication between robots. This is a lot. It's enough that you can fit the entire map inside the broadcast channels, using one channel per square. Actually you can fit several maps, so I used this idea in several ways in 2015.

First, I used it to tell missiles what their targets were. When a launcher spawned a missile, it would write the robot ID of the missile's target to a broadcast channel corresponding to the missile's starting location. When the missile spawned, it would look at its location, calculate the corresponding broadcast channel, and read its target from that channel.

Second, pathfinding results were written to the broadcast array. I used a breadth-first search (BFS) algorithm to calculate, for each square on the map, which direction to move if you wanted to reach the current destination. So I had one channel for each map tile, writing to that channel the direction that a robot standing on that square should move next.

Third, the intermediate state of the BFS algorithm was stored in the broadcast array. This meant that many different robots could all participate in running the algorithm. So in my 2015 player, a miner with spare bytecodes would read the current state of the algorithm from the array and run the algorithm for a bit, writing results to the results channels. Then at the end of its turn the miner would write the new state of the algorithm to the broadcast array, letting another miner pick up where it had left off.

Instead of thinking of broadcasts in terms of little robots talking to each other via radio, you should think of the broadcast array as a region of memory shared by all your bots. Whatever you could do with shared memory, you can do with the broadcast array.


Precomputation

In some cases you can precompute things and store them in hardcoded static arrays. Then during play you can simply access the array instead of computing the thing. For example in 2014 robots could self-destruct, damaging all adjacent robots. I precomputed an array to answer the question, "Given that there is an enemy robot at position (dx,dy) relative to me, what directions can I move to bring myself adjacent to it?" The array gave a list of such directions for all small (dx,dy).

Be aware that initializing a static array does cost bytecodes. The compiler automatically writes a "static initializer" for your class, which is invoked when the class is loaded (which happens the first time each robot uses the class, so probably on its first round of life). If your static array is very large you may go over the bytecode limit on the first round of the robot's life. This may be fine, but be aware of it.

I heard Dan Gulotta suggest that hardcoded strings carry no such initialization penalty, so if you need to you can get around this initialization penalty by encoding your precomputed info in strings.

Here are some examples of this string trick that I might try using in 2016. Often you find yourself needing to take a square root when you compute a distance. In 2015 the devs set
Math.sqrt
to cost 20 bytecodes. But you can define a string containing the square roots of all numbers up to 32000 or so and then look up the square roots by indexing into the string:

Here we are using Java's octal escape codes in the definition of
lookup
. This can be used to specify
char
values between 0 and 255 decimal, which is 377 octal. The
integerSquareRoot
function above costs only 5 bytecodes per call, and you can save another bytecode by manually inlining it. This technique could be useful if you are computing square roots in a tight loop (and is probably a terrible idea otherwise). One limitation is that you are limited to about 32000 characters in string literals. Another limitation is that your text editor may balk at lines a hundred thousand characters long.

Another thing this technique might be useful for is precomputing random numbers.
Math.random
costs something like 75 bytecodes, so you could instead precompute random numbers, store them in a string, and pull them out at a cost of 5 bytecodes each.

Data structures

As Steve Arcangeli writes here, you should probably avoid java.util. Any data structures you need--lists, queues, sets, etc.--are best implemented as arrays if you want to be bytecode-efficient. Check out his example of a bytecode-efficient HashSet. I often find myself needing a queue, which I implement like this:

The array should be chosen to be large enough that you will never run over the end. It might seem wasteful to allocate a big array up front when you might not end up pushing many things onto the queue. However in Battlecode memory efficiency is not a concern. You are only charged for bytecodes, and you can use as much memory as you want as long as you stay under the limit, which is around 8 MB per bot. Java has a single bytecode to allocate an arbitrarily large array (even a multidimensional one!), so you may as well just allocate a really big one. The array is automatically initialized for free (to zero for integers, to false for booleans, etc.) which is often useful.


Debugging

I find it convenient to be able to quickly switch which indicator strings I am printing. For example maybe I want to take a break from working on combat micro to fix a pathfinding bug. I have some convenient debugging functions that allow me to do this:

Here is the Debug class that enables this. It also includes convenient functions for appending to an indicator string or clearing all indicator strings.

My Debug class also contained some utility functions for counting bytecodes, but I won't bore you by writing them out here.


Reading Java bytecode

If you want to come up with your own bytecode-saving tricks, it's helpful to be able to look at the bytecode itself. To see the bytecode that the compiler generates from your source, you can open up the .class file in Eclipse (probably other IDE's have a similar feature?). To learn what each instruction is doing you can refer to Wikipedia's list of JVM instructions.