Victor Sergienko (singalen) wrote,
Victor Sergienko
singalen

Categories:

ICFPC-2011: Lambda: the Gathering

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


Пока японская трава не отпускает, надо писать.
Наша команда, кста, прославляет своим названием (и, надеюсь, бе-ме результатом) компанию 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() в функции зомби — самое мощное атакующее оружие.

День первый


Вот сели мы за это задание...

Продолжение здесь, окончание здесь
Tags: icfpc, Как дела, Профессиональное
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 19 comments