ICFP Contest 2011

Lambda: The Gathering

The task of the ICFP contest 2011 was writing a player for the card game Lambda, The Gathering. This is a two player game where players can lay out cards in front of them in 256 slots and apply them to the cards they previously put out. There are cards like dec and attack that steal vitality from the opponent, cards like inc, help and revive that restore vitality on the player slots. To apply these cards, the player has to combine them with numbers, which can be built by placing the zero, inc and dbl card. There is also the possibility to place zombies in dead slot of the opponent that are executed automatically before the other player's turn start. One can copy cards from one slot to another, even from the opponent using get and copy. Finally, but most important it includes cards for S, K and I combinators.

Since it would be easily possible to write infinite loops that completely kill the opponent in one move (or at least prevent him from doing anything else), there is a limit on the number of card application in one move. The limit is 1000, which sounds much and is normally also not an issue. However, it makes it hard to kill all 256 slots in one move. The game ends, when all slots of one player are dead, or after 100,000 moves. In the latter case, the player with more slots wins.

The player get as input only the card played by the opponent. However, since the game mechanics are exactly describe, they can from this deduce the full information over the game state. However, player's whose implementation is buggy may have a huge problems since they can not even notice that something has gone completely wrong.

The usual strategy of two player game using min-max tree with alpha-beta pruning does not seem to be very successful in this context, because (1) at every turn the player can choose between 7680 moves and (2) good strategies need a lot of preparation and it is not unusual to have 100 moves without even starting an attack on the opponent. So the brute-force approach does not work in my opinion.

Instead I implemented a fixed strategy that the player follows. At many places it needs to react, e.g. if the opponent attacked one important slot. But all in all it follows a fixed set of moves. The first challenge was to allow an easy way to state these strategies, in a way that still allows flexibility (e.g. aborting an attack if the opponent already defended against it).

Strategies

There are so many possible strategies in this game that I cannot list them all. Here are some ideas:

• Kill slot 0 of the opponent. Since numbers are build from zero, succ, and inc, the zero slot is the most important slot in the game. Killing this slot takes about 50 moves (which for this game is quite fast). However the opponent can revive it in two moves, so this strategy is not so useful.
• Prepare a complex card, so that the slot 0 can be killed with one move while restoring the card. One can use a mixture of attack and help to keep the vitality of the own slots constant. This takes a lot of preparation though, and the opponent may prepare a similar revive command to restore the slot immediately. Also he may try to work around using slot 0 (which is possible, but can be much slower)
• One can install zombies in opponent slots. These can quickly kill slots using the help card that works differently in zombie mode. There is a nice way to kill around 70 slots of the opponent with one zombie, however this requires the slots to have roughly the same vitality.
• One can install multiple zombies, each having its own function application limit
• One can install a zombie that installs a zombie back, which installs a zombie back,... This ping-pong zombie will give you a free attack in every move, while you can prepare your next attack
• One can install a zombie that installs multiple zombies that do a massive attack on the opponent.

My Submission

My submission (also on github) made it into the top thirty :) It combines a few of the above strategies: Use a zombie that kills 70 slots of the opponent at once (provided they have the initial vitality) and apply it 4 times to cover all slots. Then prepare an advanced reviver to revive about 30 slots at once and giving them some health. Then it installs a ping-pong zombie that keeps the first few slot of the opponent low (by applying a few dec cards—if the opponent puts massive health points into the first slots, the attack has no effect). Finally, it kills every slot one by one with a zombie that does a help with the right amount of vitality.

There are a lot of ways to improve it. E.g., with the use of help one can restore much more health points in an advanced reviver than I expected. In fact, one can restore a few thousands points with a single help card.

Similarly one can use a combination of attack and help to kill a slot without depending to know its vitality. The only important thing is to have a healthy slot, which can be ensured by an advanced reviver. Using such an attack, one can kill about 20 slots in a single move.

The main problem is to find a compromise between a fast attack (one has to be faster than the opponent), a sophisticated attack (that can not be prevented by the opponent), and defending oneself against faster and less sophisticated attacks. Installing a strong reviver seems to be a good idea, but if that means that the opponent starts its unstoppable attack earlier than you the best reviver cannot prevent it.

There is probably a winning strategy for the first player, but most probably, this strategy can never be found, since the number of states of this game is too large.