Frictionless Bananas

Team name: Frictionless Bananas
Team members: Jeremy Sawicki (jeremy at sawicki dot us)
Submission: submission.tar.gz

The Frictionless Bananas had only one team member this year. This page describes my 2011 ICFP Programming Contest entry.

Implementation

My submission was written in C++. It contains a simulator to track the state of the game, a quick and dirty system for managing the state of its own strategy, and a tool that can convert an arbitrarily complex value (function) into a series of moves to construct the value in a field, with or without the use of an extra field to build intermediate results.

Strategy

Defense

My program starts off by establishing some passive defenses. It executes help(i)(i+1)(9216) in a loop to fill the first 112 slots with a repeating pattern of vitalities: 784, 20137, 784, 20137, etc. This is designed to make it harder to attack those slots using a simple loop that performs the same action on each slot in a consecutive range.

Offense

After the initial defense phase, my program focuses on attacking. It constructs a looping function, intended to run as a zombie, that executes help(i)(i)(amount) on a range of consecutive slots. The amount is read from one of my program's slots via copy. The function is used repeatedly to attack ranges of slots found to be killable with the same amount of vitality.

Other notes

My program is able to resist certain attacks. If a slot that the program is currently using is killed, the program revives it and continues working. That is possible because values are preserved when slots are killed and revived. The program otherwise makes no attempt to revive killed slots. It also doesn't do much to defend against attacks that clobber values using the zombie function, but at least it detects that it occurred and aborts whatever it was working on.

On the unofficial duel server, these are my final program's results:

53 total matches
42 wins
- 39 after <100000 turns
- 3 after 100000 turns
10 losses
- 7 after <100000 turns
- 0 after 100000 turns
- 3 by exceeding time or memory limits (all against the same program)
1 draw

Because the program exceeded time or memory limits three times, the server stopped running it in further matches. I think I had a bug where the program would get into an infinite loop while trying to choose its next move. This only happened against certain opponents.

Some code

This function in slot 1 executes the defensive strategy when applied to zero. It takes 52 turns to build and execute.

S
(
  S
  (
    S
    (S(help)(succ))
    (K(9216))
  )
  (
    S(K(get))(K(1))
  )
)
(
  S(K(succ))(succ)
)

This function takes a slot number as an argument and "attacks" consecutive slots starting with that slot number when run as a zombie. It gets the attack amount from slot 3 and a copy of itself from slot 2.

S
{
  S
  (
    S
    (
      S(help, I)
    )
    (
      S(K(copy), K(3))
    )
  )
  (
    S(K(copy), K(2))
  )
)
(
  succ
)

My program constructs a function in slot 1 that applies the above function to any desired slot number. The opponent's slot 254 is killed if necessary (which can typically be done in one attack thanks to the higher vitalities produced by the defensive phase). Then the zombie is created by applying the following function to 1. The opponent's slot is decremented for good measure in case it was recently revived.

S(S(dec)(zombie))(get)

Overall impression

This year's contest was a lot of fun. Thank you to the organizers!

The Frictionless Bananas