Thursday, June 30, 2011

ICFP 2011: Results

After many hours of hard work, we finally got the results ... and took place 192 out of 199! Though this may sound terrible, and it is, it is better than last year, in which we tied for last with 0 points because the competition was so devilishly hard. This year, we got a total of 68 points. Considering a win was worth 6 points, and a tie was pretty rare, this probably means we won 11 games and tied 2. There was a total of 198 games, so that's a pretty miserable win/loss ratio. In retrospect, I think our biggest problem was that we targeted the most used slots in hope of breaking them, but we didn't really kill slots fast enough. If we had the time we should have made use of some of the higher functions, especially zombie. Unfortunately our schedules really conflicted with ICFP this year, so we weren't really able to all get together and get a solid few days of work done on it. Overall, I'm pretty happy with the results, because there are some pretty experienced programmers in this competition, and to even have placed above any teams at all is a pretty good accomplishment.

Wednesday, June 22, 2011

ICFP 2011

It's been a few days since ICFP 2011 and we've finally had a chance to cool off and relax, so I thought I'd throw a blog post up about what we actually did.

Before I go into the details of the competition, allow me to introduce our team. We had four members in total. Three of us are prefrosh at MIT: Ryan Cheu, Kevin King, and myself Gurtej Kanwar. The three of us also happen to be the core members of IDKJava. Our fourth member, a talented statistician named Michael Clawar, is a rising senior at the high school Ryan and I attend. Naturally we were wary, because he aspires to attend our rival, Ha'vard. He was, however, a valuable member of our team, and we grudgingly came to accept his choice. With this formidable team assembled, we were ready to dominate.

We started off at around 8 PM, when the contest opened in our local timezone. We read the problem and immediately felt a little lost. None of us had any experience with Lambda Calculus or SKI combinators, and so we spent much of our precious time figuring out how the problem worked. In addition, we immediately had issues with the fact that we could not all meet up for the majority of this competition, because Kevin lives several hours away from the rest of us, and Michael was out of town for the majority of the competition. As a result we ended up using a lot of Skype, AIM, and Facebook to figure things out.

After finally getting a grasp of the problem statement about a day in, Ryan and I got together and we started work on simulating the situation, so that our "player" would have some idea of what was going on to make AI decisions. Ryan and I met up Friday evening, and we got cracking. We realized that the best way to code this would be to create some of our own data structures, such as a struct Slot and a class Card. One question we ran into was how to represent non-basic functions, such as functions that had been returned by S or attack. We decided to create individual classes for each of the different "stages" in these cards. For example with S, there is the main S card, and then two intermediate stages. Thus we had classes called S1, S2, and S3 to represent this. These classes could then call on the display functions of the arguments they had been passed to display themselves in proper parenthesized form.

Once we had our basic simulation set up, there was about a day's worth of debugging to go through, and special cases to add in. In particular, the zero card threw us off, because originally we thought there was a difference between it and the number 0. In the end, however, we realized that zero and 0 were the same thing, and then zero could not be called as a function as we originally thought. In addition we had to work out the zombie loop and add in another function to deal with the fact that some cards changed how they worked when being called by the zombie loop.

This took up the majority of our time on Saturday, leaving us just Sunday to get some strategy done. On Sunday I set up our program with the framework for creating an AI: a system for adding moves to a queue to be executed (actually a stringstream), and a few utilities, such as clearing slots, applying an SKI combinator, and applying a slot to another slot (given that the first slot was a function). I then unfortunately had to go to work, leaving Ryan to develop our entire strategy for all of Sunday. When I came back with two hours left in the competition, I found an elegant system, in which our program would constantly change which slots it would use, and constantly use help to add vitality and then use that extra vitality to attack the slots most used by the opponent program. Unfortunately, there were several bugs with our system, and it did not work as expected or segfaulted repeatedly, so we spent much of our remaining two hours trying to work out these bugs. With an outside pair of eyes, thankfully we managed to work them all out and with only a few minutes left to go had a working program. Because we were short I did not get a chance to test using the provided utility to see if our program actually worked, but we managed to get everything in on time, and we'll see how we did soon!

I'm pretty proud of how much we accomplished with such sub-optimal timings and conditions. If we had had all four days free and all of us could meet up, I believe we would have been in much better shape, but the fact that we actually submitted a working program at all is an improvement over last year, in which we were close but just missed the deadline on getting in something that worked. We did a great job!