ICFP 2011 - Lambda: The Gathering
---------------------------------
Team Eta-Long Normal Form

The object of the competition was to build a program to play a
Corewars-style game with a functional programming twist, inspired by a
popular collectable card game.

We developed two programs in parallel: a simple Perl script and a more
complicated program, written in F#.

The Perl script ignores the opponent's actions entirely and mostly spits out
the contents of a text file prepared in advance. Some short, repetitive
loops are hard-coded into the script. We used this script to prototype and
test strategies.

The F# program observes the opponent's moves and models the game state,
using it to adapt its strategy.

In spite of its simplicity (or perhaps because of it), the Perl script
performed well against early submissions to the unofficial duel server,
peaking briefly at position 2 on Saturday night.

We are also pleased to present a simple script that wins the game in under
200 turns against a dumb opponent (dead-in-199.pl).

Observations about the game
---------------------------

The evaluation behaviour of the game makes it difficult to construct terms.
A card is evaluated as soon as it has enough arguments, even if it is nested
within a term that is incomplete; that is, it is not just the term in head
position that is evaluated.

Because it is only possible to pre- or post-apply cards, not terms in
general, a term application is tricky to build. Our usual trick to build the
term "(M N)" was to put M in some slot, put N in slot 0, then extend M to the
term "S(K M) get 0". This only works with slot 0 for N because it is a card.
We could not find any other way of compsing terms generally. Thus slot 0 is
crucial to the execution of any complicated strategy.

An interesting aspect of the game is the assymetry between a player's slot
indices and his opponent's indices. Most commands that affect an opponent's
slot take a number i and affect slot 255-i. Hence, while it is easiest for a
player to build terms in his own low-numbered slots, it is easiest to attack
his opponent's high-numbered slots.

Zombies seem to be a very powerful tool within this game. The help card
damages a slot twice when run by a zombie, making it useful for killing a
slot with high vitality in a single shot. Furthermore, as a zombie played on
the opponent indexes slots as the opponent would, zombies provide an easy
way to attack an opponent's low-numbered slots.

While we initially thought the copy card was intended to steal an opponent's
terms, when run within a zombie, it can easily read a term from the player's
low-numbered slots, which might be used to give the zombie an attack or a
target.

Zombies are also the only way of overcoming the game's limit of 1,000
applications per turn. Placing several zombies in the opponent's slots would
allow several times the number of applications to be executed in a turn.

At one point, we considered killing one of the player's slots with the help
card using a zombie in an opponent slot to place a zombie in this slot. This
zombie could reinstate the first, leading to a self-replicating zombie. This
mechanism could be used to execute an attack automatically every turn.

The get card seems to be the easiest way of forming a loop, which can be
used to perform many attacks in a single turn. It may also be possible to
loop using only the S and K combinators, but construction of (for example) a
Y combinator seemed likely to be expensive, so we did not explore this. As
a slot is reset to I when it exceeds its limit of 1,000 applications, it is
often worthwile to make a copy of a loop before executing it, so that it can
be reused.

Note that get retrieves the contents of a slot at the start of the turn, not
the intermediate results of evaluating it.

Strategies used
---------------

Killing 0 quickly, directly:

As construction of complicated terms seems to require slot 0, a good
strategy for disrupting an opponent is to kill slot 0. The fastest way to do
this (assuming the opponent doesn't strengthen 0 before then) seems to be to
attack directly, using slots 0 and 1 to do 8160 (= 255 * (2 ^ 5)) each.

Killing 0 quickly, using a zombie (zombie0.pl):

A slightly slower method of killing slot 0 is to:
attack slot 255, using slots 0 and 1 to do 8192 damage each;
put a zombie in slot 255 that uses "help 0 0 8192" to kill slot 0 in one shot.
This takes 45 turns.

Keeping 0 dead permanently:

If the opponent does not react to being attacked, it is sufficient to kill
slot 0 quickly. However, if it then revives slot 0 (which it can do in 2
turns), there is little benefit. So a more useful strategy in the long term
is to ensure that once slot 0 is dead, it stays dead.

In order to achieve this, we build a term that, when a card is applied to
it, uses dec on the opponent's slot 0, then uses a get to recreate itself.
Thus, whenever our program notices that the opponent has revived slot 0, it
can kill it immediately in a single turn. Without the use of slot 0, it will
be difficult or impossible for the opponent to construct any terms that
revive and heal slot 0 in a single turn.

Zombie helper (zombiehelp.pl):

We build a zombie that:
reads a target number i from a fixed slot;
uses "help i i 8192" to kill that slot in a single turn, if it is unchanged.

Then we repeatedly place the zombie and increment the target to kill all of
the opponent's slots, taking 5 turns for each slot after the first. A
weakness of this approach is that it will not harm any cells that have
already been damaged.

Zombie bomb (zombiebomb.pl):

We build a zombie that, by copying a term placed in one of the player's
slots, runs a loop that uses "help i i 8192" on a sequence on 59 consecutive
slots in a single turn.

Combining this strategy with killing 0 quickly, using a zombie, and
deploying the zombie bomb repeatedly, we can win outright in under 200 turns
against an opponent who does nothing. The weakness of the strategy is that
the loop terminates if it encounters a slot it cannot kill because it has
too little health.

Dec many loops (decmanyloops.pl):

We construct a loop that uses dec twice on 91 consecutive slots in a single
turn, before being destroyed. With three such loops, we cover the entire
range of 256 slots. We save the terms so that they can be reused many times
quickly. Setup takes 77 turns, while copying and using the terms takes 12,
dealing at least 2 damage to every slot. This makes it a good way to kill
many weak slots, which perhaps were killed and then revived by the opponent.

Dec many gadget:

We construct a term that uses dec on 164 consecutive slots in a single turn,
then recreates itself. We construct two such terms to cover all 256 slots,
then run them repeatedly, dealing at least 1 damage every 2 turns.

Reviving important cells:

If the opponent kills an important cell, namely, one that is being used to
construct a useful term, we revive it as quickly as possible.

Strategies used in the Perl script
----------------------------------

The longest-standing version of the Perl script (under
duel-submissions/subzombie)
used the following strategies, in order:

Killing 0 quickly, using a zombie
Zombie helper (repeatedly, with a few revives interleaved)

This was later replaced with a version (under duel-submissions/subhistory)
that ran a zombie bomb before using a zombie helper.

Strategies used in the F# program
---------------------------------

The F# program maintains a record of the state of the game. It has a number
of strategies, each of which supplies a sequence of moves to a pipeline. If
the opponent disrupts the basic strategy, for example by reviving one of its
slots or attacking one of the player's, it interrupts the pipeline to
respond. A strategy is described by a list of moves, with "breakpoints"
specifying where a strategy may be resumed if it is disrupted.

The program starts by building a gadget to keep slot 0 dead permanently. It
kills slot 0 directly and thereafter attempts to keep it dead using the
gadget. Next, it uses a zombie helper to iterate over all the cells,
hopefully killing most of them. Finally, it uses the dec many gadgets to
clear any remaining cells.

If any of the player's low-numbered slots are killed, the program
immediately tries to revive them.


Our thanks go to the organisers for thinking up such a fun and interesting
problem!

