Mostly Software

June 22, 2011

The ICFP Programming Contest 2011

Filed under: Software — Tags: , , , — schani @ 10:21 pm

Introduction

Last weekend saw yet another iteration of the ICFP Programming Contest, an event the glorious team Funktion im Kopf der Mensch could not miss.

The task

The task this year was to build a program that would play a card game, Lambda The Gathering, to be run on the contest organizer’s machines. The game is played with two players each, taking turns. In each round, a player must play one out of several kinds of cards, for each of which there is an infinite supply. Each player owns 256 slots, each of which has some “vitality”, initially 10000. If a slot’s vitality drops to zero it is dead and cannot be used anymore (unless it is explicitly revived). The object of the game is to kill all the opponent’s slots.

Apart from its vitality, a slot also holds a value, which is where the real action happens. A value can be either a number or a function. The cards in the game also represent functions, and the number 0. When a card is played, it must be played to a specific slot, meaning that the card’s value and the slot’s value are combined. The combination can be either that the slot’s value is applied to the card (right) or the other way around (left). Initially, each slot holds the identity function, I.

As an example, let’s say we want to generate the number 4 in a slot. Initially it will hold I, so we play zero right, giving I(zero), which is reduced to 0. Now we play the function succ, which takes a number and returns that number plus one, left, giving succ(0), which reduces to 1. In each of the next two turns we play the card dbl left. dbl is a function that doubles a number, so we end up with 4.

To actually do something, like attacking your opponent’s slots, there are cards whose functions have side effects. One of them is attack, which you supply with three numbers (it’s a curried function). The first is the number of one of your slots, the second the number of one your opponent’s slots and the third is the “strength” of the attack. Once the function has all of its arguments it will subtract the third number from your slot’s vitality and then subtract nine tenths of that number from your opponent’s slot. There is another function, help, which you can use to top up your vitality, so if you first help and then attack with the right strengths you will have damaged your opponent without having lost any vitality yourself.

Also among the cards in the game are S, K and I, representing the homonymous functions of the SKI combinator calculus. These three simple functions, together with function application, are Turing complete, which means that it is possible to build programs in slots.

http://www.complang.tuwien.ac.at/schani/blog/icfp2011/L1006883.jpg

Strategy

Actual programs can potentially damage the opponent much quicker than would be possible by building each attack by playing the respective cards anew. (Note that I’m talking about the programs (functions) in the game’s slots now, not about the program that plays the card game).

There is a limit to how long a slot’s function is allowed to “execute”, however, which is 1000 function applications. If it has not finished until then, execution is stopped and the slot’s value is reset to I. Any side effects stay, however, so an endless attack loop would do damage, though only a limited amount.

There is a good reason for not using endless loops, however, namely that, since the slot’s value is reset, the function is “lost”, so it has to be copied to another slot first (which is possible with the get function, but somewhat costly, since the function’s slot number has to be built first) or, even worse, generated again.

A better strategy is to use a function that does some more or less fixed amount of damage and then returns itself, or some slightly different variant of itself. The actual result of the function will, after all, be the new value of the slot. So, suppose we could build a function like this:

1:  function make_killer (slot) {
2:    return function (dummy) {
3:      kill_opponent_slot (slot);
4:      return make_killer (slot + 1);
5:    }
6:  }

If we generate this function and give it the number 0, it will result in a function that, given a dummy argument, will kill the opponent’s slot 0 and return a function that when called with a dummy argument will kill the opponent’s slot 1 and return a function that when called with a dummy argument etc. In other words, once we have this function we can kill one enemy slot per turn. In comparison, just launching a single attack without building more complex functions requires more than 50 turns, and that’s not sufficient to kill an enemy’s slot. If you factor in the help calls to top up your own vitality so as not to die quicker than the enemy you’re looking at more than 200 rounds just to kill a single slot of the enemy (assuming it has the initial vitality of 10000).

Feasibility

Unfortunately, it’s not completely trivial to write a function like this in SKI calculus. In fact, compared to SKI, x86 machine code looks incredibly high level. Fortunately, there is help. As luck would have it, I wrote a Scheme subset to Unlambda compiler many years ago. Scheme is essentially Lambda calculus and Unlambda is essentially SKI. In other words I was already a bit familiar with both SKI as well as the compilation algorithm (which is quite simple).

Here is the function from above in very simple Scheme:

1:  ((lambda (x) (x x))
2:   (lambda (self)
3:     (lambda (slot)
4:       (lambda (dummy)
5:         (kill-opponent-slot slot)
6:         ((self self) (succ slot))))))

Since there are no function names in SKI or pure Lambda calculus we have to achieve self-reference using a trick, namely the function (lambda (x) (x x)), which applies its argument to itself, so if you pass it your function then that function gets itself as its (first) argument, in this case named self. Note that I am assuming that we have sequential execution available, to first kill the opponent’s slot and then return the function for the next slot. This is not natively available in Lambda calculus, which doesn’t even deal with side effects, but can be implemented like so:

1:  ((lambda (dummy)
2:     do-this-afterwards)
3:   do-this-first)

How easily can we generate an attack function like the one above in a slot? The first step is to translate Lambda to SKI calculus. The simple algorithm (given in the task description) produces ridiculously huge programs. The problem is that since SKI calculus doesn’t know named function arguments the arguments must be passed downwards “manually” from where they originated. The simple algorithm passes them down all the way to all the leaves of the syntax tree, where they might or might not be needed. By cutting off the passing down at subtrees which don’t need the argument a significant reduction is achieved, but program size is still an issue, and depends a lot on how deeply nested the original function is.

Now that we have the function in SKI form, can we trivially play cards to summon it to a slot? It turns out that this is only possible in simple cases because a player’s turn can only apply a card left or right, so nesting on both sides of an application is not trivially possible. For example, it’s easy to generate S(S(SK)), starting from I, by applying K right and the S left three times. S((SS)K) also works: S right, S left, K right and S left. However, (SS)(KK) is not doable that easily.

There is a trick, though: Assume we already have some arbitrarily complex x, and we want x(MN). If we apply K left, S left and then M and N right we end up with ((S(Kx))M)N which, thanks to the way the S and K combinators work, reduces to x(MN).

This trick still only works if M and N are single cards. It can be used recursively however, and, using yet another similar trick, arbitrarily nested right sides can be produced, but at a great increase in the number of cards that have to be played. Before we figured out those tricks we came across a simpler general solution, using the card get, which, when given a slot number, reduces to the value that’s in that slot. If we use get and zero as the cards M and N in the trick above, the function will reduce to xy, with y being whatever is in slot 0. The generation algorithm built using this trick has to use more than one slot, and it depends vitally on slot 0, but it is reasonably simple and the overhead is small.

It looks as if we have all the pieces of the puzzle together now and can finally generate a function that does some serious damage quickly, but there is another problem. Let’s say we want to generate a function which, when given a dummy argument does the side effect of inc zero (the details of what inc does are not important here). In Scheme, that is (lambda (d) (inc zero)). Translated to SKI calculus it is K(inc zero). To generate it in a slot (assuming it holds I) we apply zero right, then inc and K left. After having applied the inc the slot’s function is inc zero, though, which is immediately reduced, thereby doing the side effect and giving as a result the function I, so after applying K left we end up with K(I) and a side effect we only wanted after giving the dummy argument.

Clearly, we need a way to “guard” side effects against immediate execution. The easiest way we found to do this is to build an equivalent function, but in a different way. From a completely functional point of view, i.e. ignoring possible side effects, the functions

1:  K(inc zero)

and

1:  (S(K inc))(K zero)

are the same – they both take an argument that is ignored and reduce to inc zero, but in the latter form the inc zero can only be reduced once the dummy argument is given. Let’s call such a function a “side effect function” – it requires a dummy argument and only once that is present will it produce a side effect.

What if we want to combine two such side effect functions, resulting in a new side effect function that does one first, then the other? It seems tempting to just apply the second to the first, like this:

1:  (lambda (d)
2:    (second-se-fn (first-se-fn d)))

The error in this approach is that even though (first-se-fn d) can only be reduced once the argument d is present, it is still, in terms of the SKI calculus, a function, and therefore a value, so second-se-fn can be reduced, even without d. What we need instead is a function that takes an argument and then applies first one function to that argument and then a second one. As luck would have it, that function is S. So, to combine two side effect functions, yielding a new side effect function, we have

1:  ((S first-se-fn) second-se-fn)

http://www.complang.tuwien.ac.at/schani/blog/icfp2011/L1006887.jpg

More strategy

With all of that in place we can come back to our self-returning slot-increasing attack function. As it turns out, passing around that extra slot number argument is quite an overhead when everything is translated down to SKI calculus, but we had already thought of a simpler solution. Instead of having the slot number inside the function we can use indirection: We store the number of the slot to be attacked in some other slot and use the get function to retrieve it from within the attack function. The disadvantage of this approach is that we need to increment the slot number after each attach, costing us one extra turn, but on the other hand we can switch to another slot to attack reasonably quickly.

After some optimizations, some of them directly on the generated SKI code, we managed to get the number of turns required to load this function down to below 180. After that we just have to load zero into a slot and we can kill one enemy slot every other turn.

One small detail I omitted above is that when attacking a slot the number you give will actually be inverted, i.e. giving 0 will attack slot 255, and vice versa. That makes it easy to attack high slot numbers but more difficult to attack lower ones, because higher numbers take more time to generate. Nonetheless, our bot doesn’t actually start its attack from the highest slot, as would be easiest. It first figures out which opponent slot holds the most complex function (using the trivial metric of counting the leaves of the syntax trees) and attack that first, then increment until we hit slot 0, then we start again from the highest slot, hopefully finishing off the opponent.

We did not have much time left to refine our bot beyond that. There are very few measures we take to defend ourselves. If one of our few vital slots is killed while we are generating our attack function, for example, we just revive the slot and the start over with generating the function. A smarter bot would try to salvage the pieces left in the other slots. If the slot we take the vitality from to launch attacks is killed, we’re dead in the water – we had code to help it get back into working condition, but we failed at the last minute to integrate it.

Overall, I think we’re doing quite well. We launch our first attack within about 200 rounds and can finish off a bot that doesn’t defend itself within a bit more than 500 turns after that. Against the best teams, however, we’re helpless – they can kill all 256 of out slots stone dead in less than 190 rounds, starting from scratch. Kudos!

http://www.complang.tuwien.ac.at/schani/blog/icfp2011/ltgvis.jpg

Contest organization

In the past I have taken contest organizers to task for screwing up in minor and major ways. This year, I am happy to say, there was almost nothing to find fault with. The task was clear, not artificially obscured, many-layered, interesting and enjoyable. There was a test submission server but teams didn’t depend on it and it worked quite well in any case.

So, from Team Funktion im Kopf der Mensch a huge Thank You to the organizers for this amazing job! May all future contests be organized this well.

Programming languages

Last year was the first year we used Clojure after using OCaml almost exclusively in the years before. This time we stepped back a bit and used OCaml for the actual bot, i.e. the program that will run on the organizer’s servers. The main reasons for this were that OCaml has a much smaller footprint and more predictable performance than Clojure and we wanted to make sure we didn’t hit against any limits, and that we felt somewhat safer writing an unsupervised program when protected by OCaml’s type system.

We still used Clojure for developing the attack functions, starting from Lambda calculus, going down to SKI and then generating a sequence of card application.

Our visualizer was written in C.

All of these languages did their respective jobs well. No complaints this time.

The Code

All the code we wrote for this year’s contest is available on GitHub. If you need any assistance with it, please email me.

About these ads

1 Comment

  1. It’s almost not fun to read this years report, due to the lack of complaints ;-)

    Anyways, it’s true, the organizers did a very good job this year.

    Comment by Martin Biely — June 24, 2011 @ 9:32 am


RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

The Shocking Blue Green Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: