ICFP stands for International Conference on Functional Programming. The conference is famous itself, but what is the most funny thing for people like me who loves programming just for its fun, not for its money outcome, is the traditional programming contest. Every year, several months before the conference, a task is published and everyone is welcome to try solving it better than the others. 3 days (that is, 72 hours) are given. Usually there's either a problem which can be solved better or worser, and the best solution wins, or (as in this year's contest) there are some rules of a game, your program is the player, and the championship between the programs is held after the programmers' time is over: this means you write a program, submit it to the organizers before the 72 hours are over, and then, without your supervision, your program faces its opponents on a virtual arena.
This year the game was named Lambda: The Gathering.
According to the funny legend, it is a kind of card game like these played
by modern yangsters (such as Magic: The
Gathering). Organizers of the contest prepared an amusing
deck of playcards, each of them a wonderful piece of the art (their
original images are to the left and right here on the page; I hope
organizers will not blame me for copyright violation, heh...) However, the
longer you read the rules, the lesser it looks like a card game. The game
is played by two players; each of them have every card; actually, you've
got an unlimited number of copies of every card. Also, each player has 256
slots, and in each slot a card, or a handful of them, is stored.
When you make the move, you actually don't spend a card (or, if you like,
you spend the card but an unlimited number of them is still in your hands).
The last thing is that each slot has a so called vitality which is
changed by some of your moves, and your task is to kill your opponent's slots
keeping your own slots alive.
Here's where all the cardplaying legend disappears and the actual task
starts. The pieces called «cards» are actually constants of a
well known SKI combinator
calculus; for this game, there are the three combinators (S, K,
I), the constant zero, the built-in functions succ and
dbl (all these actually gives you Turing-completeness and the
natural numbers), as well as side-effective gameplaying functions:
get (returns/copies the contents of the given slot), put
(simply returns I; used to clear slots), inc (raises vitality of
your slot), dec (decreases vitality of your opponent's slot),
help (allows to share vitality between your slots),
attack (spends your vitality to destroy the vitality of your
opponent), copy (steals cards from your opponent's slot) and even
zombie. The full set of the game's rules is found on the official
ICFPC 2011 announcement page (unfortunately the domain name
icfpcontest.org is used for each subsequent contest each year;
I don't know how to figure out the 'permanent' address of this page; if you
know, please let me know as well :) )
First of all, the mechanics of the game must be implemented. Actually, you can go without it (as I'll explain later, I started without the logic implementation), and your program will even be able to beat some of the opponents. It is like fighting blind: okay, you can make an assumption that your opponent simply stands still and waits for you to come and kick his ass; you can then go and try some kicking. If, and only if, your opponent really stands still, you can even make some progress :) But in case he is moving, you'd better be able to see where he is. Furthermore, he can try kicking YOUR ass, as well, so it seems to be a good idea to know when to move your poor ass away from his kicking foot.
The program you write here is intended to read information from its
stdin and write to stdout. What you write is
your own moves; what you read is the moves of your opponent. However, it
is not sufficient just to read the moves: you need to know what happens
in the game, so you must have your own implementation of all the
rules.
The next thing to do (although not all the people realize it) is a kind
of playground to test effects of some move combinations. Fortunately, the
organizers provided a program which reads moves and tells you what happens
(that is, displays the state of the game), but it has very inconvenient
interface. Actually the main purpose of the program is to make a match
between two opposing computer players represented as programs; the
possibility to play as a human looked to me much like a last minute change.
The next thing is to get familiar with all these combinator calculus and figure out how to code complicated things using combinators. Again, you can do without it, but the practice shown that you'll spend hundreds of moves on what can be achieved in ONE move if you prepare that move carefully. By the way, in this task it was not sufficient just to know how to combine the combinators: according to the game rules, you could apply a primitive (a «card») to a slot (in which there could already be a complicated expression), but you can't directly apply one slot to another, so just to build a desired combinator expression was sometimes a brain-blowing task.
And now, at last, you should come up with some game strategy. Actually,
if you were playing the game yourself, you could easily make decisions
watching what your opponent do. But it's your program, not you, who will
actually face the opponent. So it must be written in such a manner that,
basing on the situation of the game, it could make an adequate response to
your opponent.
It was midday of Friday, several hours into the contest time, when I actually found the time to look at the task. The first look is always important. Actually, noone pays you for solving contest tasks, and if you dislike it, then hardly you can do any good during the contest; now if you don't do any good, then obviously you don't get the only payout: that joy and satisfaction. I used to take part in the ICFP contests since 2002, and every year I wait for these three days as for an unique source of intellectual joy, but... well... Once the task was so complicated that I even couldn't come up with any result; another year I disliked the task so much that I decided not to waste my time and preferred to take a trip to a countryside for some air.
This year it was not easy to decide whether I want to continue. That Friday was a busy day for me, I had to settle some realworld problems, so I read the task and turned away from my computer for several hours.
Later afternoon I opened my preferred text editor (what? Vim :) ) and started to implement the cards
and theirs applications to each other. The language I used was old good
C++ — without STL (which I hate). It is not too new for me to
implement computation models in C++: being the author of InteLib is a good experience :) In the
past, I participated in ICFP contests just to make some demonstration for
InteLib. However, the past is in the past: now I just wanted to have some
joy, and that's all. I didn't see how InteLib can make my life easier in
this year's contest so I decided not to forearm with it. Actually it
could help later to implement the decision making but the overhead could
prevent me to get at that point. The only library I finally used in my
contest submission was ScriptPP (as a
replacement for the standard string class).
Late at night of Friday the implementation of the "Card Deck" was almost complete; well, let me say I didn't even give it a single try that night: it was only a set of C++ classes, not a program. It was necessary first to understand how to play this game and what the program must actually do. I reread the rules carefully and paid certain attention to details. Organizers announced an unofficial duel server where one can submit a program to be matched against other programs. Besides that, they provided a very simple example of a valid submission which actually did a no-operation (although perfectly valid) move until the game ends. You see, there's no need to know anything about the state of the game to do so, because you can always apply the I-combinator (which just evaluates to its argument) to the slot: the result will be written back to the slot, but this will be exactly the same thing which was there before. The program was a bourne shell script of several lines.
I modified the program a bit. Finally, you know there are slots of the
opponent, and you know the way to do some damage to them: why don't try?
My first program did "dec 0" ad infinitum: all I had to do for that is to
apply my own slot (any of them) to the card "zero", then apply the card
"dec" to that slot. After that, the slot is filled with "I" (which the
"dec" function returns; the "I" card seems to be the favourite default
value of the authors of the task); you can start again. So, using this way
you simply spend 2 moves to decrease the opponent's slot 0's vitality by 1.
20000 moves &mdash and the slot is dead.
I downloaded the demonstrating program (organizers provided it as a binary) and matched my primitive slow killer against the organizers' example; it won (256:255, heh). But I noticed it only takes 20000 of 100000 moves to do this, do I decided to go a bit further. The next program (still written in bourne shell) made the sequence
0 zero dec 010000 times, then went on killing the next slot. This was a bit more complicated, because the next slot has the number 1 (oh, no, it actually is 254, but when you do "dec n", you damage (255-n)th slot). Anyway, there's no card with the number 1, so you've got to prepare it. The sequence now contains three steps:
0 zero // slot0 := 0 succ 0 // slot0 ++ dec 0 // dec (slot0)so it takes 30000 moves to kill another slot. But 50000 moves are still left! So, now comes the
0 zero // slot0 := 0 succ 0 // slot0 ++ succ 0 // slot0 ++ dec 0 // dec (slot0)and it kills yet another slot, using up another 40000 moves. The 10000 are still left, but using this dumb technique you can't do anyting useful with them.
I submitted this "solution" to the duel server and was surprized that it performed not so bad: it won many games and I found it within the 50 best competitors. Well, this was only Friday night (but very, very late), slightly more than 20 hours of contest time so far. Okay, I could perhaps rewrite this program in C++ but what for? it became obvious for me that primitive things are not what is needed to create a good solution. So at that time I started to play with the organizers' game implementation to figure out how one can use these combinators.
All the inconvenience of the program's interface turned out to be a real
problem. You had to enter three lines for each move: "1" or "2" to specify
the "direction" (do you want to apply a card to a slot or a slot to a
card), then type either name of the card (and then the slot number), or
first the slot number, and then the name of the card. I feel totally
unable to type this: I needed to think about combinators, not about "what
is the direction and is it 1 or 2 this time". The problem was so serious
that I launched my Vim and quickly coded a simple program which launched
the organizers' game emulator as a child process and feeded it with what it
needed. From the user's point of view, it only took one line to explain a
move: one could type "inc 0" to apply the "inc" card to slot "0", or type
"5 dec" to apply the slot "5" to the card "dec". Sometimes we
underestimate the costs of low usability: this is one of the most terrible
mistakes a programmer can make. The simple program which changed my
"interface" costed me 5 to 10 minutes to code, but my speed at
SKI-combinators at least tripled.
The next problem was that from the very beginning of the experiments I found it distracting to retype commands I already typed, so I created another module (a set of classes) to represent a single move as well as a generalized "procedure" consisting of moves; initially there were two of them, first to make the given number in the given slot (using "succ" and "dbl" operations) and the second to run a "script" consisting of single moves. Here is an example of such a script:
// -1 is the number 'j' for 'heal' (slot to be healed)
// -2 is the slot from where to copy the heal volume
OneStep script_time_to_heal[] = {
S("put", 0),
S("put", 1),
S(1, "zero"),
S("help", 1), // (help 0)
S(0, -1), // #0: j
S("K", 1),
S("S", 1),
S(1, "get"),
S(1, "zero"),
S(0, -2),
S("get", 0),
S("K", 1),
S("S", 1),
S(1, "get"),
S(1, "zero"),
OneStep()
};
Negative numbers are "parameters", for which the actual values are passed
to the constructor of the "procedure" object.
But all these were just instruments, while the real goal was to figure
out how to do recursion using the combinators. It was
obvious for me that I need it: rules allowed up to 1000 applications during
one move! Definitely if you can only do one thing while your opponent does
1000, then you're to loose the game. However, it was deep night in Moscow
(GMT+4), around 24 hours into the contest time, 4 A.M. locally, I was not
too sleepy but too tired to dive into the serious math. So I took my dog
to a walk, checked how
my primitive shell script is doing on the duel server, had some fun from
its surprisingly high position and then went to sleep.
When I got up, I quickly prepared a breakfast, took a brief walk with my dog and got back to the keyboard. Recursion was still my primary goal; I did searches on the Internet, lots of experiments etc. I quickly found it is not so easy to build the necessary expression of combinators even if you do know it. Actually the problem became obvious even during the previous day. For example, suppose you want to do "attack 0 255 5000". It is easy to compose "(attack 0)" within a slot: you simply do "5 zero", then "attack 5", and here it lies, in the slot 5. But how to "append" the 255? First of all you need the 255 in another slot. So, here we are, with "(attack 0)" in one slot and 255 in another. And so damn what?! You can't just apply them one to the other. The solution is a bit complicated. The idea is that you must prepare a function which, when applied to a slot number, will compose what you need. You have to use the "quoting" combinator K for this purpose: when you apply K to something (say, "x"), you get the function "(K x)" which will return you the "x" when you apply it to anything else. In order to compose something, you use the S combinator which takes two arguments, applies them both to the third argument and then applies the first result to the second.
Here is how to compose "attack 0 255". First, you create the number 255 in the slot #0. It is important to use #0, because "zero" is the only number you can use directly; anything else must be first taken from somewhere. Then, you do (I use the slot 5 in this example):
5 zero // 0 is in #5
attack 5 // (attack(0)) is in #5
K 5 // K(attack(0)) is in #5
S 5 // S(K(attack(0))) is in #5
5 get // S(K(attack(0)))(get)
// remember, there's 255 in #0
5 zero // voila! #5 contains the desired (attack(0)(255))
Look how this worked: in "S(K(attack(0)))(get)", the top level
"functor" is S, and it has two arguments: "K(attack(0))" and "get". You
apply the whole construction to "zero"; S applies both of it arguments to
that zero, and "K(attack(0))" simply ignores the zero and returns its
argument "attack(0)", while "get" gets the contents of the slot with the
given number (zero in this example), so it returns 255 which was in #0.
Now "S" has two results: "attack(0)" and "255", and it finally applies one
to the other, so we get exactly what we need. But we have to apply this to
another number, which is the attack amount. Okay, prepare the number
(better a power of 2, e.g. 8192) in the slot #0 and do:
K 5 S 5 5 get 5 zeroand here you go: you loose 8192 of your slot 0's vitality, but damage your opponent's slot #0 by (9/10)*8192.
Well, now look and see it is only one simple command! We spent 10 moves just to compose it, not counting the moves we need to prepare the numbers (255 and 8192).
Anyway, let me get back to my story. What I needed is recursion. From Internet I learned that if you've got a function (let's name it "a"), then to do a recursive application you need to construct another function (let's call it "b") which is "S(K(a))(S(I)(I))" and then apply take the function "S(I)(I)" and apply it to that "b". I decided to use "inc 0" as "a", as to recursively increment my slot #0's vitality. But one moment! you can't just take "inc" and apply it to "0", it will immediately work and return "I", it is not what you want! So here is what I had to do, finally:
0 zero
K 0 // #0: K(0)
1 inc
K 1
S 1
K 1
S 1 // #1: S(K(S(K(inc))))
1 get // #1: S(K(S(K(inc))))(get)
1 zero // #1: S(K(inc))(K(0))
So, the slot #1 now contains "S(K inc, K 0)" (I omit some parentheses and
add a comma for clarity). Whatever argument you apply this to, you get
simply the application of "inc" to "0". Ten commands only to make a simple
"quotation"!
And now the interesting part begins. We've got the function "a" in the slot #1, now we need to compose "b" which is S(K a, (S I I)). So we do:
put 0 // #0: I
S 0 // #0: S(I)
0 I // #0: S(I)(I)
S 1
K 1
S 1 // #1: S(K(S( a ))), a is for short
1 get
1 zero // #1 now contains the "b"
Well, the function "b" is in the slot #1, but it is not the end of the
story. We need to apply "S(I)(I)" to it. By the way, we need to apply SII
to it, not vice versa, so we'll need the "b" in the slot #0 (well,
it is possible to avoid using #0 but it is hard: you'll need to use "S(K
get, K n)" instead of simply "get"). So here we go, copy the "b" into the
#0 slot, then compose "SII" in the #1, and do the application:
put 0 // #0: I
0 zero // #0: 0
succ 0 // #0: 1
get 0 // Now "b" is copied to #0 from #1
put 1 // #1: I
S 1 // #1: S(I)
1 I // #1: S(I)(I)
K 1
S 1
1 get // #1: S(K(S(I)(I))(get)
1 zero // here we go!!!
The last command is a kind of final hit: it starts the recursion, doing
"inc 0" again and again, within the single move.
Yahooo!!! But wait, what's the hell? The vitality of the slot #0 during
my experiment was 10000, and it only became 10124. Ohhh damn the
restrictions :) Only 1000 applications are allowed per move, and each
recursive call takes 8 of them, plus one for that "1 zero" command
initially — so here we are sitting with our 124 complete recursions.
Definitely the result of 124 was not too impressive, but it was working recursion which was really important, not that 124 addition to the vitality. Remember the "help" card? Now the good thing: it is possible to apply it to the same slot. E.g. "(help 0 0 8192)" will distract 8192 from #0's vitality but will immediately add (11/10)*8192 right back! Definitely it is better than that simple "inc 0", heh. Why not to apply recursion to it instead? So I immediately did, and got 65535 of vitality in #0 — the maximum allowed by the rules. This was my happiest moment during this contest :-)
Meanwhile, other contestants started to submit their good programs to the duel server, and my poor bourne shell "vitality decrementor" had a great fall to 70+ positions. It was time to help the little soldier. Now that I had a practically unlimited source of vitality, I could try something. My first fighting program created in C++ didn't use that "The Deck" implementation, is still fought blind. But what I reused without any modifications was the module of scripts and procedures. The strategy was as simple as a hammer: get 65535, attack the enemy's #0, #1, #2 (each with 16384 of the attack power, which is sufficient to kill the slot; actually, 16384 is the least power of 2 which is greater than 10000), then again perform the recursion and get 65535, and go on until the slot #255.
From the first test run, the solution didn't work: the whole system
(the organizer's game simulator, the simple program as the sparring partner
and my new program) just hanged. However, I quickly understood what
happens: guys, this thing is called "buffered output" :). You see, when
you program writes to the terminal, each linefeed symbol forces the buffer
to be flushed, but the contest organizers' programs is not a terminal! I
added fflush(stdout) after each move and the program worked, killing the
opponent completely (256:0) in about 25000 moves. I quickly submitted it
and went for a brief walk.
While I had my walk, my new soldier fought many other programs on the duel server, so that I found it around the 35th position when I returned to the keyboard. It was obvious though that I will not achieve anything serious without the game status information. Blind fight is only good when your opponent stands and waits for you to kick him. It was very easy to stop my new program during the fight: the enemy just had to kill either my slot #0 (okay, this wasn't an easy task as it was constantly revitalizing) or slot #1 (which really was easy). It was time to get back to my implementation of The Deck. So I did.
At first, I added a "text representation" method to all of my "card" classes. Without it, perhaps I couldn't debug the whole thing. Then, I added to the program another module to write logs, and made the possibility to build the program with logs disabled as well as with logs enabled. I started to analyse the input of the fighting program instead of simply discarding it. To my surprize, after a coredump or two, the whole thing just worked: logs of my program and the output of that organizers' programs shown the same state of the game. It tooks about 3 hours to bring all the things to the working state, and it was a late night again.
It was the right time to think about the game strategy. There were some obvious things to do such as detection of the opponents' attacks and reviving the dead slots, etc. Also there were two cards I didn't understand how to use: that "copy" and "zombie", both with too complicated functionality; certainly I implemented them both in my simulator, but who could tell me how to make actual use of them?
However, an interesting event interupted my chain of thoughts: I
notices that someone on the duel server won a party against my program in
less than 2000 moves. It was 10+ times quicker than I could.
So I distracted from the game strategy and tried to figure out how to
perform the recursion in a more sophisticated way: namely, how to "iterate"
through the slot numbers. It was obvious for me that it is possible; the
only problem was that I couldn't figure it out how to do that,
actually.
It was very late at night when I understood I can't do anything serious right now and tried to sleep. But, unfortunately, I couldn't. Perhaps I looked a bit like that zombie on the card to the right :) After a sleepless hour in bed, I returned to the computer and started to implement the game strategy, added the notion of a 'job' (the set of procedures that achieve a certain goal), assigned them some priorities, so that, e.g., any job got interrupted if the slot #0 is dead: it is critical to revive it first. It was an early morning when I finally managed to sleep.
It is the problem of all ICFP contests. The last day begins, the instruments are ready, and it is the time for real accomplishments using them — but you're overburned. The point here is that pure coding takes not too much intellectual effort; this is exactly what happens during the first day, when the brain is fresh and ready to work. But when it comes closer to the end, you need your intelligence more and more, and at the same time you've got less and less of it to use.
This time it was just the same story. Falling asleep I had a hope I'll be able to understand how to do my good recursion, but the new day started, the sun got up, and I felt I can't solve any math problems anymore, at all. I tried hard, and again, even harder. I drinked litres of tea and took several cups of good coffee. I went for a walk again, and returned. Nothing could "revive" my brain, it simply refused to work.
So I gave up with the math and contiued with the game strategy using what I had at the time. There were a lot of things to do, to implement revitalizing the slot #0 from others, to make some reserves in adjacent slots (my final submission runs with 65535 of vitality in #0, #1, #2 and #3, and in case something happens to the #0, it is "revive"'d and immediately healed up to 8128 from one of the adjacent slots, then the abovementioned recursive "help 0 0 4096" is done and the game continues). I was creating new versions, submitting them to the duel server, testing them against each other; very usual type of activity during the last contest day. Meanwhile, some of the opponents killed my robot in just 204 moves showing me how should it REALLY be.
One time I even have seen my robot at the seventh position in the
table. I even made a screenshot of it; I have never been that close to the
top in ICFP contests. Certainly this has nothing to do with actual win: my
submission was on 55th place when the table got frozen nine hours before
the contest end.
However I continued: actually I did implement another critical feature but was late to see how will it do until the freeze of the tournament table. At the midginght (4 hours before the contest end) I tried to get to bed abandoning any new hopes but in several minutes jumped in again being awoke by another idea to implement. Hell, my last submission was done 40 minutes before the end, and I immediately realized it contains a bug, so I fixed the bug, tested the new version, performed the submission procedure (oh mighty organizers, why did you create such a cool UNOFFICIAL duel server and used that damn inconvenient google services for all the OFFICIAL things?!) and finally submitted the fixed version in less than 5 minutes before the official end of the time.
During this writing, I finally realized how to do that damn recursion. I didn't test it however, so I'm not sure I'm right.
Furthermore, I realized how to do without recursion. It is not limited anyhow how many unfinished function applications can be in a single slot; so you can build a real monster in a single slot, and it even will work quicker than the recursion. Well, it takes some time to construct such a monster, but you can copy it and store somewhere, and once you need it, you "get" it into the #0 and just apply to... err... zero?
The duel server is still running. Perhaps I give a try to all these ideas. Why not?
This contest was definitely the best one since 2002 when I started to participate them. However...
Guys, next time PLEASE don't use these damn AJAX-based Google services. I couldn't manage to post a single comment to the official contest blog entries. Yes, my firefox has the NoScript module, but even disabling it, allowing all the JS hell to run didn't help me.
The official submission form was inconvenient, there was no registration so you had to type all that email, URL, real name each time you did a submission. Well, this DOES matter when there's less than 5 minutes until the end.
Hmmm... that's all of my criticism, and now...
THANKS A LOT TO THE ORGANIZERS
Yes guys, this was the best ICFPC I ever had. Thank you for the wonderful task, which had a very low minimal requirement but nevertheless a very good space for getting better. Thank you for the card images, which wasn't actually a part of the task but made all the game much funnier. Thank you for making the simulator available (in some past contests, you had to implement all the things manually, using specifications, without a chance to test the implementation correctness). Thanks for the duel server which added the element of real time sport competition.
Finally, thank you for not stopping the duel server after the end of the contest. I hope you will not stop it now. It is really a fun to have the opportunity to continue, be it hundred thousand times unofficial.
Hey, I'm starting to like Japanese people :-)
Questions? Comments? Here please: http://www.stolyarov.info/pvt/icfpc2011