? ?
Notes from a Medium-Sized Island [entries|archive|friends|userinfo]

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

[Jun. 24th, 2005|07:11 pm]
[Tags|, ]

ICFP contest has got me feeling kind of down about programming. I really don't like the problem this year. I had my hopes up that since they had moved from "submit data or toy language program" to "submit real program to be run on real machine" that there was going to be some exciting new idea to the problem, but it's totally the same ol' "write a program for a robot living in some little toy world that competes well against other robots" thing. The twist on it I guess is that you have to sort of cooperate in the cops-and-robbers problem with other cop-bots while simultaneously competing with them. Still, the ant problem, being as it was sort of a different programming experience (since it was weirdly parallel), was vastly more fun.

[User Picture]From: platypuslord
2005-06-24 11:57 pm (UTC)
What would be an example of an exciting new idea for a contest?
(Reply) (Thread)
From: lambdacalculus
2005-06-25 02:24 am (UTC)
keep 'em secret, since the pop group is running it next year!
(Reply) (Parent) (Thread)
[User Picture]From: ssaiscps
2005-06-25 05:27 am (UTC)
yeah for some reason i just always find them annoying.
(Reply) (Thread)
[User Picture]From: ssaiscps
2005-06-25 05:27 am (UTC)
perhaps because they lack, i don't know, relevance, or maybe elegance.
(Reply) (Thread)
[User Picture]From: ywong
2005-06-25 05:56 am (UTC)
Whoa, wait a minute...what was this ant problem?
(Reply) (Thread)
[User Picture]From: jcreed
2005-06-25 02:14 pm (UTC)

The task was to submit an ant brain program which controlled each ant in a colony of maybe a few dozen to a few score ants, so that the colony successfully collected more food than a competing colony. Ways in which the ants could interact with the world were: moving, picking up or dropping a unit of food, detecting whether there are ants, food, home base, or chemical marker, depositing a chemical marker. Implicitly you can also kill enemy ants by surrounding them. Then they turn into food. Your score is how much food you have on your home base by the end of the run.

Now, this is basically the same format of "write a program to make your 'robots' beat the other guys' robots" but it was fun, I think, because the programming model was so weird.

The ant brains were not submitted as ML/Java/C++/whatever programs, they were submitted in a very simple language of finite state machines that included primitives for all the interactions mentioned above. So you could say things like "State 18: if there is food here, go to state 7, else go to state 9". The ants had no memory other than what state they were in. This meant that if you wanted to keep around a bit of memory but otherwise execute the same program, you had to duplicate your program; one for the "my bit is currently 0" world, and one copy for "my bit is 1". There was something like a 10,000-state limit on brains, which we thought was very generous at first, but having n bits of memory multiplies your program size by 2n.

The reason this model caused fun was that we spent a good chunk of time thinking about language design, which I think is way more fun than worrying about how we can squeeze performance out of executing code during the time our opponents are computing, by using threads and worrying about concurrency etc. etc. etc. which was the case this year for a while. We designed a little high-level language and compiled it down to low-level ant-brain format, and we had lots of fun king-of-the-hill tournaments among all the team members' current ant brain programs.

In the end the people that won the contest did so by --- well, this is my theory (which I share others around CMU) --- mainly being enormously clever in thinking of ant strategies. Not sure how much which programming language one used really mattered. I guess the winners' tools were good enough to let them get through enough iterations to come up with good strategies in the time limit.
(Reply) (Parent) (Thread)