singalen. ICFPC-2011: Lambda: the Gathering (Reply)

Если добавить зомби, всё становится круче.
Мила Йовович

Пока японская трава не отпускает, надо писать.
Наша команда, кста, прославляет своим названием (и, надеюсь, бе-ме результатом) компанию Ciklum.

Последние три дня прошли в зомбическом угаре.
Задание на очередное соревнование ICFPC японцы придумали на редкость удачное, хотя и слишком умное для нас :D

В этом году програмы участников должны играть друг с другом в некую Lambda: the Gathering - гибрид Magic: the Gathering, SKI-исчисления (вот пример готового языка) и машины Тюринга.

Правила

Если вкратце, у двух игроков есть:

15 видов "карт", каждая из которых - это функция;
игровое поле из 256 ячеек. У ячейки есть "жизнь" (в начале игры - 10000) и "значение" (число или функция), в начале - функция I(x)=x.

Вот примеры карт-функций:

I(x) возвращает x
succ(x) возвращает x+1
copy(i) возвращает значение i-й ячейки врага
attack(i, j, n) бьёт (255-j)-ю ячейку врага на 9n/10 жизней, ценой убавления n жизней у нашей i-й ячейки;
zombie(i x) садит в (обязательно мёртвую) (255-i)-ю ячейку врага шпиона-зомби с функцией x, который будет делать на поле врага всё, на что запрограммирован; там есть нюансы, о них позже;
revive(x) оживляет мёртвую ячейку и даёт ей 1 очко жизни.

Ходы. Игроки ходят по очереди. Каждый ход:

сначала наступает "час зомби", когда подсаженные врагом зомби ("см. рис. 1") автоматически вылазят из могил и делают своё дело, противное всему живому;
потом игрок применяет (вычисляет) одну из 15 "карт"-функций к значению одной своей ячейки,
или же наоборот, применяет значение (тоже функцию) из одной "ячейки" к "карте".
если функция вычислилась без ошибки, то результат записывается в ту же ячейку;
в любом случае, у вычисления функции может быть побочный эффект, который остаётся.

Некоторые карты-функции могут возвращать в результате другие функции. Таким образом в ячейке можно накапливать длинные формулы, а потом "запускать" их "на раскрутку". Это, собственно, Тюринг-полная машина. Или не совсем полная, как мы заподозрили позже.

Например, функция K(x, y), применённая к x, вернёт другую функцию - Kx - которая, применённая к любому y, вернёт x ("запомнит" x, а y выбросит). Таким образом, K позволяет отложить вычисление x столько раз, сколько K мы навесим на x.

Длина хода. На такой машине можно построить бесконечный цикл. Поэтому ход каждого игрока ограничен — вы не можете вычислить более 1000 функций за ход (грубо говоря, вычислить формулу более чем из 1000 функций).

Победа. Выигрывает тот, кто убьёт оппоненту все ячейки, или, по истечении 100 тыс. ходов — тот, у кого больше живых ячеек. Возможна ничья.

В "час зомби" функции, меняющие здоровье, работают "наоборот": inc() уменьшает на 1 нашей, а dec() увеличивает вражеской ячейке; attack() всё так же платит здоровьем нашей, чтобы увеличить (!) здоровье вражеской, а help() не "переливает" из одной нашей в другую, а уменьшает здоровье обеим. Собственно, help() в функции зомби — самое мощное атакующее оружие.