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!