/dev/code

I submitted my final entry for the 2005 ICFP Programming Contest and the deadline has passed, so now I feel free to share the mini diary I kept while working on the project.

June 24-27, 2005 - It Begins

Friday, 7:08 PM
I'm finally home and eating supper. The contest started 9 hours ago. I had to work today, so the best I have been able to manage is to look through the rules. I am excited to get going. Last night, I did a few tests with Chicken Scheme since I suspected I might have to do some socket code. The LiveCD the contest people put out mentioned something about game servers. Now that I see that I just read from stdin and write to stdout, I am back to Ocaml. The other thing that leads me back to Ocaml is that I will have 5 seconds to make a move each turn, I might need all the speed I can get.

Friday, 7:28 PM
I'm starting on the parser now. I will make a callback interface similar to the way SAX works to handle each message event. For nested messages like wsk, I will have callbacks for each sub-message. The callback interface will allow me to simulate the server in code later without actually having to do the full protocol.

Friday, 9:24 PM
It has been a little bumpy with Ocaml, but the problem is a disconnect between the chair and the keyboard. I am getting the parser written now. I have code to dump out the wsk structure, am trying to get it running now.

Friday, 9:54 PM
Got the basic parser running a little while ago. Now I am adding in support for all the commands the server can send. I have been on #icfpc on freenode for a while now (I am mr_pengy) and it is a blast chatting with these folks. It makes me wish we were all in one big lab.

Friday, 11:48 PM
All the parsing is coded, now I am trying to build the graphs for foot and car paths. After that I think I may go to bed.

Saturday, 12:14 AM
I decided to keep a list of foot edges and car edges in each node, so I essentially have two trees. I am going to bring in my old fibheap code and add dijkstra's algorithm so I can do shortest path computations. I want to see if I can compute the shortest path between all points in each tree. There are < 300 nodes in the graph, so that's just a few hundred thousand distances to compute. I'll have to see how long it takes. If the size of the world increases substantially, though, this will be a bad idea. Time for bed now.

Saturday, 10:02 AM
I probably slept a lot later than I should have. I finally got caught up with the ICFPC mailing list – lots of rule clarifications. Time to code.

Saturday, 11:57 AM
If I were to quit now, it wouldn't be a total loss. I was wrestling with trying to squeeze my fibheap code into this project without making it become really ugly. Then I started thinking about alternate ways to compute the distances. I worked out a way to do Dijkstra's shortest path algorithm without a priority queue. Basically, I start with distance D=0 and I iterate through each node N looking for node Nadj with distance=D. Then, I look at each node Nadj' that is an edge node of Nadj. If the distance from N to Nadj' is greater than D+1, I update the distance from N to Nadj' to be D. When I have done that for all nodes, I then repeat the procedure for all nodes with D=1 and so forth, until I do not find a node to update. On my machine, doing this calculation for all 229 nodes takes about 0.03 seconds. The max distance on foot is 29, the max distance by car is 17. This isn't bad considering the map is roughly a 15x15 grid. This is pretty exciting, even though I have yet to write a complete bot, so I am going to get started on a robber bot.

Saturday, 1:15 PM
Still reorganizing the code and making a bot interface. Still no bot, but this should make it easier to write one. There was a mention on #icfpc to look up the Floyd-Warshall shortest path algorithm, I think that's essentially what I came up with. I am pretty sure mine is O(n^3) like Floyd.

Saturday, 4:16 PM
I'm working on a robber bot. As a first try, I am having it look for banks that it can get to before the cops do, with a certain margin for error. If it can't find one, it picks another place to go. I'm writing lots of functions that should make it easier to add other behavior.

Saturday, 8:53 PM
I have a pretty dumb robber bot. He got caught after robbing one bank. It's not that my cop is smart, the robber ran right into him. The robber targeted banks that were farthest away from the cops, but didn't know how to avoid cops in its path. I have been thinking for a while about what to do about that, and my current thinking is that I need to make a new shortest path algorithm that avoids cops. Basically, before traversing an edge, see if the destination falls within some constraints (no cop within 2 spaces, for example). That would allow me to plot a short path around a cop.

Saturday, 10:13 PM
My robber just made all the way through without getting caught, and having robbed several banks. The cops are still very dumb, and the robber needs some work. His choice of banks is still determined by how far away the cops are, but not how close he is. Also, I need to make some adjustments to make sure it picks valid moves. I had a problem with that and I need to make absolutely sure it validates the move. Still, I feel good about my progress.

Saturday, 10:43 PM
I figured out where the invalid moves were coming from and made several adjustments there. I also changed the algorithm to go for the closest bank now that the distances take cop proximity into account. If it were to get surrounded right now, it wouldn't be able to pick a path because it wouldn't find nodes that are “safe”. In that case, I will make an emergency flee function. I may let it go for a “less safe” path first, then any path where there is no cop. Otherwise, stay put.

Saturday, 11:45 PM
I added the emergency flee function, so it should be able to get out of a jam. Tomorrow I have to make a better cop. I submitted an entry already just in case my machine crashes. Can't be too careful.

Sunday, 9 AM
Over breakfast, I modified the robber's calculations for cop distances to account for cops changing from foot to car. I'm leaving for Meeting for Worship shortly, won't be able to get going again until after noon.

Sunday, 4:04 PM
I have been working on the cop for a while. I tried assigning the cops a beat where they walked from bank to bank. My robber still got a ton of money. Now I am trying to compute the vicinity where the robber should be.

Sunday, 5:29 PM
I have been working on smartening up my cop. The contest rules state that in the initial tournament, your cop must win – not just come in the top 3. Because of the way the evidence collection works, that means if the other cops stumble on evidence and you aren't the one to capture the robber, you lose. This seems a little too random for me. My cop now directs the other cops to the general vicinity of the last known location of the robber, adjusting for time (“Our fugitive has been on the run for 90 minutes...”), but also within a certain minimum distance away. The idea is that my cop comes in to the actual area and snoops around. It doesn't quite work that way, but it isn't too bad. Whenever my cop smells the robber, it computes the possible locations of the robber (based on last-known location) and joins that with the locations that are exactly the smell distance away. Then it picks a random one if there are any. My cop can now occasionally beat my robber. I'm going to see what the ratio is.

Sunday, 5:42 PM
Oops! In computing how far a robber could have moved, I forgot that the robber only moves on every other turn, so the area was much too wide.

Sunday, 5:55 PM
In 20 games, the robber won 12 and my cop won 8. Also, my cop lost to the other cops in 1 out of those 8.

Sunday, 7:12 PM
I am really starting to feel tired. This has been a tough project and I am sure I won't win. I would like to be able to get through the regular season part of it, at least. I have modified the robber a little bit. Before, when it couldn't find a regular move, it would look for a “safe” move, which was a move that maximized the distance from the cops. Now, it looks at the set of those moves and tries to maximize the safe moves from that move as well. I could probably play with the logic there a little, but I will first see if that improves its performance against my current cop.

Sunday, 7:27 PM
The robber won 14 out of 20 this time. It might be just a tiny bit better than before. I started logging its searches and I have seen it get out of a jam when it has picked an emergency move, but usually when it has to do that, it gets caught.

Sunday, 10:03 PM
I submitted my updated cop & robber. My team name is “O Caml, My Caml”. I just recently put in code to look at the informs from the Mcgruff bots again and now I am starting to see how I might use Bayes theorem to predict user location. Someone mentioned Bayes on #icfpc yesterday, but I didn't know what he was getting at. I googled and found a paper on predicting customer location on a wireless network and now I am beginning to understand. Unfortunately, there are less than 12 hours left, and I know I won't be able to last all night. I don't know if I can create a smarter cop in the next few hours or not. I'll give it a try.

Sunday, 11:07 PM
I tried a few other things with probabilities, trying to incorporate Bayes theorem, but it seemed to be a little worse than my previous algorithm. Perhaps the Mcgruff bots aren't so good at estimating probabilities. It looks like I'll be sticking with what I have.

Sunday, 11:32 PM
I just sent in my final submission for the first part of the contest. Time for bed.

Monday, 2:24 AM
I was in bed with the light off when I realized that if a robber never hit a bank, my cop wouldn't find him. I switched the cop to start off in beat mode. Now I am doing some analysis on what bank a robber hits last before getting caught. So far, "60-and-blackstone" and "53-and-the-other-lake-park" lead by far. I tried eliminating 60&B already and cops won 17 out of 30 times. I am trying again with all banks allowed. Then I will try with 60&B and 53&OLP removed.

Monday, 3:44 AM
I tried a number of combinations, including picking random banks, the farthest bank, sticking with a bank until it was robbed. In the end, the best strategy was still to aim for the closest bank, but don't rob the bank at 60-and-blackstone. That should be enough right there to disqualify me from the Judge's Prize. NOW I'm going to bed.

July 9-10, 2005 - And now, The Twist
The interesting thing about this contest was that after the initial 72-hour period, there was almost a two-week lull, then they announced a change in the rules that we had 24 hours to respond to. I can't say that my response was great, but at least I submitted something.

Saturday, 10:10 AM
I am in Blacksburg, VA getting ready to come home after a week at the Friends General Conference Gathering. My dorm room at Va. Tech has an internet connection so I have just logged in to start reading the "twist" in the problem specification. UGH! Cops can be bribed! I don't know how I am going to do this. I spend the next 20 minutes looking over the requirements.

Saturday, 3:20 PM
Ceal is driving right now as I work on my program. I have just adapted my original cop and robber to the new protocol. The robber doesn't offer any bribes and the cop doesn't accept them. At least I have something.

Sunday, 12:45 AM
I have just submitted my final code. I am really tired after waking up at 6, packing the van and driving about 4 of the 7 hours of the return trip. My robber tried to bribe cops, but my cop does not take bribes. I decided to leave the cop alone. This will probably cost me the judges prize, even though I don't think I had a realistic shot at it to begin with. This has been a fun project and I hope to go back and try to add better strategy to my programs later.