[<< | Prev | Index | Next | >>]

Tuesday, September 03, 2002

ICFP Programming Contest



For fellow ICFP contestants who just want the technical skinny:

Hmm. I think that's about everything of interest. I turned in my lightning entry in twelve hours (Friday night at midnight), and only spent a couple hours sprucing it up when they announced dual-category submissions Saturday afternoon, so my bot has been psychologically prepared for an undignified, soggy death at the hands of more serious entries.

Best of luck, and may your bot never rust,

-Simon Funk

We now return you to our regular programming...

Last Friday at noon, the annual ICFP Programming Contest kicked of their three day competition by posting the challenge task... which I decided to see if I could tackle respectably in twelve hours or less.

With a couple of key strokes I shuffled over to the virtual desktop I have set up for coding (just two large windows side by side which I can flip between with a key), opened server.c in vi, and started typing while I was thinking about how to solve the problem. Yeah, yeah, you're thinking of that cartoon where the manager says "you guys start coding, and I'll go upstairs and find out what we're supposed to do." But I knew for starters I had to implement the basic infrastructure for a client and server, and C being what it is, that's plenty of typing right there. Sadly but fortunately, coding in C is mostly a cerebellar activity for me now, so most of my brain was free to multi-task.

I typed up a tiny Makefile and hit "make" but it wasn't finding my tcp libraries. Aw, heck, probably the last time I used them was on my NeXT and I never ported them to Unix. Fifteen minutes porting, re-build my utility libraries, popd back to where I was, hit make, it compiles, run it, presto: my server is accepting connections in one window, my client making them in the other, the foundation is done... But I better eat lunch and think about it some more before hours slip by and I pass out from hypoglycemia..

Culinarily sated with a paleolithic meal calculated to hold my blood sugar steady for the next many hours, time was already slipping by, and I had no small amount of details to implement, twice over, no less, since if I was going to be able to test my client, I needed to write a server too.

So while I was flipping back and forth between the task description and my vi windows, coding up basic client-server hand-shaking, convenience routines for sending and receiving messages given the basic format of the protocol, I'm thinking about my little robot trying to find his way, perhaps some sort of graph connecting convex corners of any obstructions... when finally it occurred to me I could probably just brute-force a complete gradient over the entire map. I knew it would be slow, so while I was thinking about how exactly to do that, I coded up a layer above it which would cache the results -- I figured the 10 most recently used would be more than adequate while staying within the stated memory limitations. By the time I was done with that, I was ready to code up the actual gradient computation, which is pretty much the only clever thing in the program and it's probably got some text-book name I'm just not familiar with: 

static
void computeGradient(Gradient g)
{
	// Theoretical max might be only 4000, but no time to figure it out.
	static short leadingEdge[10000][2][2];	// [item][alternate][x,y]
	int num, dist, x, y, toggle;

	forn(y, height)
		forn(x, width)
			g->dist[y][x] = -1;

	num    = 1;
	toggle = 0;
	dist   = 0;
	leadingEdge[0][toggle][0] = g->x;
	leadingEdge[0][toggle][1] = g->y;
	g->dist[g->y][g->x] = dist;

	while (num>0) {
		int oldNum, oldToggle;
		int old;

		oldNum    = num;
		oldToggle = toggle;

		num     = 0;
		toggle ^= 1;
		dist++;

		forn(old, oldNum) {// foreach old leading element
			int d, c;
			int xo, yo;
			xo = leadingEdge[old][oldToggle][0];
			yo = leadingEdge[old][oldToggle][1];

			for4(d) {	// For each direction it might go..
				x = xo + deltas[d][0];
				y = yo + deltas[d][1];
				if (offBoard(x, y))
					continue;

				c = board[y][x];
				if (c == '~' || c == '#')
					continue;

				if (g->dist[y][x] >= 0)
					continue;
				g->dist[y][x] = dist;

				leadingEdge[num][toggle][0] = x;
				leadingEdge[num][toggle][1] = y;
				num++;
			}
		}
	}

	g->maxDist = dist;	// Should be dist-1, but maxDist=0 is a hazard rather not have to worry about.

	gradientsComputed++;
}

Basically, it just walks out from the gradient's origin (g->x, g->y) in all possible directions (the robots can only move in the four major compass directions) and keeps track of how far it's had to go to get to each new square. If it lands on a barrier or a square it's been to before, that path is terminated (since we're interested in the shortest paths, the earlier path takes precedence). Otherwise, each new square fans out in the four directions again, and so on. The leadingEdge array keeps track of all the active squares at any given time, and by toggling between two copies of it, I avoid having to shuffle any data around.

I tried it out, it worked. The gradients looked good, and a quick timing test showed I could compute at least four per second on their worst-case map (1000x1000), and with my caching layer already in place I'd hardly be putting a dent in the one-second-per-frame average CPU time limitation.

Meanwhile, they announce out of the blue that they're going to make a test server available. Grr. Mine was already serving up maps and a few other things to my client by this point, but at least I hadn't gotten to the package handling yet. I download their server, try it out, it works with my client so I'm still rolling...

With the cached gradients as a ready-made tool, navigation is trivial--just walk down hill toward your destination's gradient. Plugged that in, worked first try--my robot's now heading straight to the nearest home base (where the packages can be found). And, once you get there, it turns out the same (cached) gradient makes package selection easy, since by definition that gradient is a map of how far (walking distance) it is to every reachable location from the home base.

Here I screwed up. Intuitively it was obvious that the value of a package was related to both its weight (which determines the points you get for it) and how far you had to go to deliver it, but I didn't want to get lost in the complexities of how that would interact with multiple packages going to multiple places (since I figured I wouldn't know relative distances beyond the first package) and left that factor out. Later on, I realized I had plenty of CPU to spare, so I chained the distance measure for package selection so each package was selected based on its distance from the previous package (i.e., so I had to compute new gradients for each package in a multi-package pickup, assuming they were destined for unique locations). Now with the inter-package distances available, I should have re-introduced the weight/distance factor in package selection, but I brain-farted instead.

Dinner was in order, so I chopped up some ginger and garlic and marinated the huge slab of ahi I'd purchased at Costco that morning, coded some more during the pre-heat and bake times, and had a fine meal of ahi and leaks saute'd in butter (left over from the night before) with half a papaya with a spoon of almond butter for desert. Mmmm.

I spent a lot of time just coding up book-keeping to maintain state--what other players are on the field, where, what are they carrying, what's their (approximate) score, what packages exist, where are they, how heavy and where are they destined for, and so on. I just inferred all that from whatever the server told me, regardless of what actions my own bot had issued (since you never know what actually happens--your eyes should always take precedence over your expectations..), and since the server spoke to me impartially about all players including myself, I didn't need any special code to maintain my own bot's state -- just a single global "me" that happened to point at my own bot.

Meanwhile, they'd gotten servers online so I could play and watch other people's bots in action, which was fun to see. My client dumped the current map with players overlaid, like this (the M is me): 

Turn:29/5000 Hydrophobic:0  Gradients:2/2  PackageCache:0/0=0% Attacks:0

Getting status...
.....................................................###########...............
...............................................................................
..........................................................@....................
..................~~~~~~~...........#................###########...............
..................~~~~~~~...........#........~~~~~~~~~~~~~.....................
......................~~~...........#.......~~~~~~~~~~~~~~.....................
....................................#..............~~~~~~......................
....~~~~~~~~~~~.....................#..............~~~~~~......................
....~~~~~~~~~~~.@...................#..........................................
....~~~~~~~~~~~.....................#..........................................
........................#.#.........######################################.....
........................#.#.................................#..................
........................#.#.................................#..................
#########################.################################.###.################
........................#.#..................~~~~~~......#.....#...............
.....~~~~~~~............#.#................~~~~~~~~~~....#.....#...............
...~~~~~~~...........M...................#~~~~~~~~~......###.###.....~~~~......
.........................................#~~~~~~~...................~~~~~~~....
.........................................#~~~~~~~....................~~~~~.....
.........................................#########....................~~~~.....
.......................................................................~~~.....
...............................................................................
...............................................................................
...............................................................................

[26] At:21, 7 #Pks:0/0 Weight:~0/30 Score:~0 ME
Getting packages...
Contemplating move (0 packages here)...
Moving E (bid=1).

So, I added a few heuristics for avoiding close-contact with other players, tweaked a thing or two, but basically it was working and doing it's thing, and since it was almost midnight I decided I'd accomplished what I set out to, and submitted it to the website.

Sadly, mine was the fourth entry! So now of course I'm quite curious about the other three--what language were they written in? By teams or individuals? Do they work? :) [Update: There were only 10 Lightning entries out of 160 total entries, and mine was the only Lightning entry in vanilla C.]

Of course, while I was taking a shower just after midnight I realized a couple of things I could improve, yadda yadda, but I was done, I needed my ugly-sleep. Then Saturday afternoon they decided they were going to allow multiple entries from the same teams--one for the lightening division (24 hours, heh), and one for the regular (3 days). So I added a couple of features, fixed one bug (my lightening entry avoids standing on the graves of dead robots, which was entirely an accounting error, not a religious statement) and submitted a final version. I'm sure they'll both get clobbered by more aggressive robots which will just plunk me in the water. But, hey, it was fun doing the mad dash, hack and slash coding. I'm usually so diligent about organization and commenting and modularity and all that. I approached this more like survival hacking, and I lived. Better than a night at the movies.

Here's my final entry, the worst code I've written in years. :) And appropriately, it does in fact have (at least) one trivial but fatal bug which I only discovered today--it hangs when there are home-bases which can't be reached. Perhaps the ICFP will (rightly) use my code as an example of why C is evil. :)

[<< | Prev | Index | Next | >>]

Simon Funk / simonfunk@gmail.com