disorder.ru

Каждый год осенью или в самом конце лета проходит международная конференция по функциональным языкам программирования — ICFP. Чтобы привлечь больше внимания к этому событию, за несколько месяцев до конференции организаторы устраивают соревнование для программистов — ICFP Programming Contest. Организаторы и страна проведения конференции каждый год разные, разные и задания для соревнования. Но все задания разных лет объединяет одно свойство, редкое для спортивного программирования: чрезвычайная необычность и увлекательность. Собственно именно эта черта «зацепила» меня и моих друзей, не участвовавших ни в каких соревнования, наверное, со школьных времен. В Интернете можно найти множество интересных отчетов участников прошлых лет, именно из одного такого отчета мы и узнали о ICFP.

Соревнование длится ровно трое суток. Участвовать могут все, у кого есть доступ к Интернету. Можно участвовать как одному, так и собираться в команды. Понятно, что выгодно собирать команду из людей, живущих в разных часовых поясах, чтобы пока один спит, другой работает. После завершения соревнований подводят предварительные итоги, оглашение окончательных результатов и награждение победителей происходит на самой конференции. В этом году конференцию и соревнование проводит университет Тохоку (Япония).

Не смотря на слово «функциональный» в названии, знание функционального программирования для участия не требуется. Также нет никаких ограничений на используемые языки программирования. Но те, кто хорошо знаком с функциональным программированием, метапрограммированием, DSL и прочими вещами из мира теории программ имеют неоспоримое преимущество, так как задания ICFP Contest всегда так или иначе связаны с этими проблемами. В нашей команде «функциональщиков» не было, писали мы на Python в объектно-императивном стиле, но это не помешало нам показать не самые плохие результаты.

Начало

За пару недель до старта у нас определился окончательный состав команды. В нее вошли всего три человека: я, Леша и Саша. Мы с Сашей представляли Москву и область, Леша — далекий континент Австралию. Так что некоторое покрытие разных часовых поясов удалось получить. Надо сказать, что изначально нас должно было быть на два человека больше, но по разным причинам они не смогли. Все-таки полностью уйти из мирской суеты на трое суток современному человеку непросто.

Для взаимодействия мы подготовили две виртуальные машины у разных облачных провайдеров, на которых разместили Git репозиторий. Если бы первая машина упала, мы бы быстро переехали на другую. Общение вели через Skype-конференцию. Если бы Skype упал, перешли бы на Google чат.

Свою команду мы назвали просто: Trup 16.

Леша никогда не ел слив никак не мог дождаться начала и поэтому постоянно мониторил официальный сайт соревнования на предмет появления каких-нибудь загадок или подсказок. И его внимательность была вознаграждена: картинка справа books.png с нарисованными книгами со знаком λ была заменена на new_books.png с тем же изображением:

И самое главное: размер картинки вырос и стал около 600К. Многовато для такого маленького изображения. Надпись на сайте рядом с картинкой гласила: «What’s in an image?» Леша посмотрел на картинку глазами HEX редактора и увидел, что к картинке «приклеен» ZIP архив. Отрезав архив и распаковав его, он обнаружил внутри Java класс. То есть к картинке был «приклеен» JAR. Запустив его, мы получили на выходе новую картинку:

Новая картинка тоже содержала в себе JAR, который при запуске выдавал первую картинку.

Итак, у нас есть две ключевые фразы: «Lambda The Gathering» и «Divergence Omega (λx.x x)(λx.x x)». Первая фраза происходит от названия популярной карточной игры «Magic: The Gathering». В ней игроки управляют войском волшебников, которые стараются убить друг друга с помощью заклинаний. Управление осуществляется с помощью карт; каждая карта позволяет волшебнику произвести определенное действие. Лямбда — это ключевое понятие лямбда-исчисления, дисциплины, изучающей анонимные функции. Омега же — это специальная конструкция из лямбда-исчисления, записываемая как (λx.x x)(λx.x x), которая является невычислимым выражением, так как бесконечно вычисляется сама в себя. Можно сказать, что эта картинка тоже в каком-то смысле омега. Получается, что скорее всего нам предложат написать программу для игры в карточную магическую игру на основе лямбда-исчисления. Ни в магических играх, ни в лямбда-исчислении мы ничего не понимали, поэтому просто покорились Судьбе и стали ждать старта.

День первый

Соревнование должно было пройти с нуля часов по Гринвичу пятницы 17 июня до нуля часов понедельника 20 июня, т. е. старт назначен на 4 утра по Москве. Домашние были предупреждены, что все эти трое суток нас «нет в этом мире». К сожалению, в пятницу пришлось-таки быть на работе, что не позволило использовать этот день по полной.

К моменту старта из нас троих бодрствовал только Леша, он первый и ознакомился с заданием. Как мы и предполагали, ближайшие трое суток мы будем играть в игру «Lambda: The Gathering». Точнее не мы, а программы, которые мы напишем. Правила игры таковы.

Играют вдвоем, делая ходы по очереди. У каждого игрока есть 256 слотов, пронумерованных от 0 до 255, и набор карт. Слот характеризуется двумя параметрами: здоровьем и значением. Здоровье — это целое число от -1 до 65535. Если здоровье положительно — слот жив, если равно нулю — мертв; специальное значение -1 говорит о том, что слот мертв и стал зомби, но об этом чуть позже. Значение слота может быть либо целым числом от 0 до 65535, либо функцией (как в программировании). Значение является валидным номером слота, если это целое число в диапазоне от 0 до 255. Перед началом матча все слоты игроков имеют здоровье 10000, а значение равно функции I (о ней тоже чуть позже).

На каждом ходу игрок может либо подействовать картой как функцией на значение слота, либо значением слота на карту. Игроки видят ходы друг друга. Значение, полученное при действии функции, становится новым значением слота. Ошибка возникает, если значение карты или слота, которым осуществляется действие, не является функцией или если количество применения вложенных функций превышает 1000. При возникновении ошибки вычисление функции прекращается и значение слота становится равным функции I. При этом все побочные эффекты, произведенные при вычислении функций до возникновения ошибки, не отменяются. Карты не тратятся и могут использоваться сколько угодно раз в течение матча.

Матч завершается либо после 100000 ходов, либо если у одного из игроков все слоты мертвы. В любом случае побеждает тот, у кого к концу матча больше живых слотов. Если количество живых слотов равное, присуждается ничья.

Теперь о картах. Организаторы не поленились и нарисовали для каждой карты интересную картинку, как в настоящей настольной игре. Я, пожалуй, приведу их здесь все, надеюсь, авторы не будут против. Кстати, надписи на картах позволяются глубже понять их суть.

• I — тождественная функция, возвращает свой аргумент. В лямбда-исчислении такая функция называется I-комбинатор и записывается как λx.x.
• zero — целая константа 0.
• succ — функция от n, возвращающая n + 1, если n < 65535, и 65535, если n = 65535. Если n не целое число, возникает ошибка.
• dbl — функция от n, возвращающая n*2 (удвоенное n), если n < 32768, и 65535, если n ≥ 32768. Если n не целое число, возникает ошибка.
• get — функция от i, возвращающая значение своего i-го слота, если он жив. Если слот мертв или i не валидный номер слота, возникает ошибка.
• put — функция от x, игнорирующая свой аргумент и возвращающая функцию I.
• S — самая сложная для понимая карта. Точнее сложная для тех, кто раньше не сталкивался с лямбда-исчислением и комбинаторами, т. е. для нашей команды. Карта S — это такая функция, которая принимает аргумент f и возвращает другую функцию, которая, если ее потом применить, принимает аргумент g и возвращает третью функцию, которая, если ее потом применить, принимает аргумент x, после чего применяет f как функцию к x (если f не функция, возникает ошибка), обозначая полученное промежуточное значение через h, применяет g как функцию к x (если g не функция, возникает ошибка), обозначая полученное промежуточное значение через y, применяет h как функцию к y (если h не функция, возникает ошибка) и возвращает полученное значение. Иначе говоря, . В лямбда-исчислении изначальная функция называется S-комбинатор и записывается как λf.λg.λx.fx(gx). Если с картой S все понятно, то дальше будет проще.
• K — функция от x, возвращающая функцию, которая игнорирует свой аргумент y и возвращает x. В лямбда-исчислении такая функция называется K-комбинатор и записывается как λx.λy.x.
• inc — функция от i, увеличивающая на единицу здоровье своего i-го слота, если до этого здоровье было от 1 до 65534, и возвращающая I. Если i не валидный номер слота, возникает ошибка.
• dec — функция от i, уменьшающая на единицу здоровье (255-i)-го слота противника, если до этого здоровье было больше нуля, и возвращающая I, Если i не валидный номер слота, возникает ошибка.
• attack — функция от i, возвращающая функцию от j, возвращающая функцию от n, которая уменьшает здоровье своего i-го слота на n, уменьшает здоровье (255-j)-го слота противника на 0.9*n (округленное вниз) и возвращает I. Если i или j не валидный номер слота, или n не целое число, или n больше здоровья i-го слота, возникает ошибка. Если при уменьшении здоровья слота противника оно должно стать отрицательным, то оно становится равным нулю.
• help — функция от i, возвращающая функцию от j, возвращающая функцию от n, которая уменьшает здоровье своего i-го слота на n, увеличивает здоровье своего j-го слота на 1.1*n и возвращает I. Если i или j не валидный номер слота, или n не целое число, или n больше здоровья i-го слота, возникает ошибка. Если при увеличении здоровья своего слота оно должно стать больше 65535, то оно становится равным 65535.
• copy — функция от i, возвращающая значение i-го слота противника. Если i не валидный номер слота, возникает ошибка.
• revive — функция от i, устанавливающая здоровье своего i-го слота в единицу, если он мертв. Если i не валидный номер слота, возникает ошибка.
• zombie — самая интересная карта. Карта zombie — это функция от i, возвращающая функцию от x, которая делает значение (255-i)-го слота противника равным x, если слот мертв, устанавливает здоровье этого слота равным -1 и возвращает I. Если i не валидный номер слота, возникает ошибка. Перед каждый ходом игрока значения его слотов, здоровье которых равно -1, по очереди применяются как функции к I. При всех этих автоматических применениях возникает ошибка, если значение слота не функция или количество применений вложенных функций превышает 1000. Возникновение ошибки не влияет на другие автоматические применения. После этого значение слота становится I, а здоровье 0. Кроме того, во время автоматических применений некоторые карты меняют свое поведение. Карта inc вместо увеличения здоровья своего слота уменьшает его. Карта dec вместо уменьшения здоровья слота противника увеличивает его. Карта attack вместо уменьшения здоровья противника увеличивает его. Карта help вместо увеличения здоровья своего j-го слота уменьшает его.

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

Прочитав задание, Леша впал в некоторую задумчивость, после чего распечатал карты и пошел с ними в парк играть сам с собой. Примерно в шесть утра по Москве проснулся я. Накануне я лег пораньше, поэтому мне даже будильник не понадобился, чтобы встать так рано. Ну и нервное возбуждение накануне конечно сыграло свою роль. Прочитав задание, я присоединился к Лешиной задумчивости и пошел делать кофе.

После кофе, перечитав задание несколько раз и поговорив с Лешей, стало понятно несколько вещей. С точки зрения аналогии с магической игрой слоты — это волшебники, функции — это заклинания. Сильные заклинания типа attack расходуют здоровье (или ману) того, кто их использует. Функции можно комбинировать, создавая более сложные функции — более сильные заклинания. Создание сложной функции занимает определенное количество ходов, и чем сложнее функция, тем дольше ее конструировать. С точки зрения же функционального программирования у нас есть три так называемые функции высшего порядка — S, K и I, позволяющие комбинировать остальные функции. Остальные функции производят различные побочные эффекты, меняя состояние своих слотов и слотов противника. Более того, гуглеж показал, что набор S, K и I комбинаторов является Тьюринг-полным, т. е. с помощью этих комбинаторов можно написать любую программу. Таким образом, данный набор карт является неким языком программирования, и, применяя эти карты в определенном порядке, мы создаем программу, результатом работы которой должна быть максимизация количества собственных живых слотов и минимизация количества живых слотов противника. Что ж, это задание вполне в духе ICFP. И, кстати, прочитав задание, я наконец-то понял, откуда происходит название компании-инкубатора стартапов Y Combinator — действительно, помимо S, K и I есть еще и Y-комбинатор, и много других.

Сначала мы немного поигрались с программой организаторов, после чего принялись писать нечто, условно названное эвалюатором, умеющее вычислять результат приложения карт к слотам и слотов к картам. Саша и Леша знали Python, я немного знал Ruby, поэтому я решил не отрываться от коллектива и в экстренном порядке осваивать Python. К этому времени проснулся Саша и присоединился к нашей задумчивости. После небольшого совещания решили, что Саша займется эвалюатором, а мы с Лешей попытаемся разобраться с карточным языком.

Простейший вариант игры может выглядеть следующим образом. Применяем слот 0, в котором на начало игры находится тождественная функция I, к карте zero, получаем 0 в значении слота 0. Затем применяем карту succ к слоту 0, в слоте 0 после этого получается значение 1. Потом можно еще раз применить карту succ или карту dbl, получая таким образом любое нужное число. А затем применяем карту dec и уменьшаем на единицу здоровье вражеского слота. Описанную последовательность действий можно записать в виде такого выражения:

dec(succ(I(zero)))

Заметим, что пострадает при этом у противника слот номер 255 — 1 = 254. Насколько мы поняли, «зеркальность» своих и атакуемых слотов сделана для усложнения задачи. Со своим нулевым слотом легко работать, так как его номер получается из одной карты zero, а нулевой вражеский слот трудно «достать», для этого нужно с помощью succ и dbl собрать число 255, что не быстро.

Обратив описанный алгоритм в код на Питоне, я получил первый вариант игрока. Мы загрузили его на арену и стали ждать. Радости нашей не было предела, когда эта неуклюжая поделка одержала первую победу. Видимо, ей достался противник, который совсем ничего не делал. Счет по слотам был 256:253, то есть за 100000 ходов мы успели убить только 3 слота. Это понятно, ведь после каждой операции dec значение атакующего слота снова сбрасывается в I, чтобы сделать еще один dec нужно опять сначала собрать номер атакуемого слота. И так 10000 раз, пока слот не умрет. И тут мы увидели, как кто-то выиграл у нас 256:0 примерно за 50 тыс. ходов, а потом за 30 тыс., а потом за 20 тыс. То есть было понятно, что противник явно использовал какие-то эффективные сочетания функций, о которых мы еще не знаем. И это подстегнуло нас к новым поискам.

Нетрудно понять, что нам не хватает циклов. Циклы в функциональном программировании организуются через рекурсию, то есть вызов функции самой себя. Я вспомнил, что в описании задания помимо правил было еще несколько коротких примеров разных матчей с чем-то похожим. Мы не рассмотрели эти примеры внимательно при чтении задания, увлекшись эвалюатором, и, как оказалось, зря. В первом примере демонстрировалось, как пользоваться zero, succ, dbl и dec; до этого мы дошли самостоятельно. А вот второй пример был гораздо интересней. В нем показывалось, как использовать функции внутри других функций. Рассмотрим такое выражение:

S(K(help(zero)))(succ)(zero)

Преобразуем его:

S(K(help(zero)))(succ)(zero) = K(help(zero))(zero)(succ(zero)) = help(zero)(1)

Нам удалось собрать число 1 внутри выражения help с помощью конструкции SK. Фактически, мы научились передавать функции в качестве аргумента результат выполнения другой функции. Но это еще не все. Что, если мы передадим в качестве аргумента результат выполнения функции get? Скажем, такое выражение:

S(K(S(K(help(zero)(zero)))(get)))(succ)(zero)

После преобразования получим:

S(K(S(K(help(zero)(zero)))(get)))(succ)(zero) = K(S(K(help(zero)(zero)))(get)))(zero)(succ(zero)) = S(K(help(zero)(zero)))(get))(1) = K(help(zero)(zero)))(get(1)) = help(zero)(zero)(get(1))

То есть в качестве последнего аргумента help будет использовано значение слота 1. Таким образом мы можем использовать значения других слотов в качестве аргументов функций. Эти две техники позволяют нам собрать любое сколь угодно сложное выражение.

А третий пример был еще интересней. Допустим, значение слота номер 0 (номер слота важен) равно функции S(get)(I). Подействуем этой функцией на карту zero. Получим следующее выражение:

S(get)(I)(zero)

Преобразуем его (кстати, в лямбда-исчислении такое преобразование, заключающееся в подстановке значений аргументов, называется бета-редукцией):

S(get)(I)(zero) = get(zero)(I(zero)) = get(0)(zero)

get(0) очевидно даст значение нулевого слота, т. е. S(get)(I), в результате получится S(get)(I)(zero). Получили исходное выражение, которое будет вычисляться снова и снова, пока количество применений функций не превысит 1000 и не возникнет ошибка. После этого вычисление прекратится, и в слот запишется значение I. Мы получили ни что иное как омегу! Прелесть в том, что после возникновения ошибки побочные эффекты от вычисления омеги не «откатываются». Следовательно, если внутрь омеги «засунуть», например, dec, можно за один ход много раз провести операцию уменьшения здоровья слота противника.

Только как этот dec засунуть внутрь? А засунуть его можно вместо zero, с которого начинается вычисление значения (помните надпись на карте zero «Everything starts from zero»?). Для этого вспомним, как работает K-комбинатор. Он возвращает первый аргумент вне зависимости от второго. То есть если первым аргументом будет zero, то вторым может быть все что угодно, результат будет все равно zero. Тут важно отметить одну деталь. Не смотря на то, что K-комбинатор игнорирует второй аргумент, он его все равно вычисляет. В этом плане LTG является «жадной» игрой, а не «ленивой». Именно этим обстоятельством мы и воспользуемся. Не забывая, что для передачи функций в качестве аргументов других функций служит конструкция SK, получим следующее выражение для рекурсивного dec:

S(K(S(get)(I)(S(K(S(K(S(K(K(zero)))(dec)))(get)))(succ))))(zero)

Такое выражение уже трудно понять с первого взгляда.  На императивном псевдокоде оно будет выглядеть примерно так:

while true { i = 0 + 1 j = get(i) dec(j) }

То есть мы в цикле уменьшаем здоровье вражеского слота, номер которого находится в нашем слоте номер 1. Само выражение при этом хранится в слоте 0. Уничтожив очередной слот мы применяем succ к слоту 1, увеличивая его значение на единицу, таким образом переходя к следующему вражескому слоту. Однако после каждой рекурсии значение слота 0 становится равным I, и наше с трудом собранное заклинание исчезает. Чтобы обойти эту проблему, можно собрать выражение во вспомогательном слоте номер 2, а перед каждой атакой копировать его в слот 0 и запускать.

Собрав все эти идеи воедино, мы получили новую версию программы. Она уже успевала уничтожить около сотни вражеских слотов за 100000 ходов, и побивала, помимо совсем ничего не делающих врагов, также и тех, кто еще не освоил циклы. Однако более сильные команды продолжали стремительно уменьшать свое время полного уничтожения врага. К концу первого дня лидеры полностью расправлялись с нами меньше чем за несколько тысяч ходов, что для нас было пока недостижимым результатом.

Это все, что мы успели сделать за первый день. Время на часах перевалило за полночь, пора было ложиться спать, чтобы завтра пораньше встать и снова взяться за дело.

День второй

Утро началось с планерки. Саша работал над эвалюатором. Эта задача оказалось совсем не простой, баги в нем он вылавливал вплоть до самого конца соревнования. Поэтому мы продолжали играть «вслепую», не отслеживая состояние своих и вражеских слотов. Леша написал набор вспомогательных функций, упрощающих создание последовательности карт. Конечно, в идеале нам нужен был некий транслятор, который мог выражение вида attack(zero)(255)(K(8192))(zero) перевести в последовательность ходов, но это было совсем нетривиально.

Заговорив о трансляторе с языка карт, стоит упомянуть язык Unlambda, о котором мы также узнали из Гугла, пытаясь понять задание. Это минимальный функциональный язык программирования, в котором есть только две функции s и k (аналогичные нашим S и K комбинаторам) и оператор аппликации ` (обратный апостроф). Оператор аппликации показывает применение функции к аргументу. Например запись `sk эквивалентна s(k). Заметим, что Unlambda — Тьюринг-полный язык, хотя в нем отсутствует I-комбинатор. Дело в том, что I-комбинатор является избыточным и выражается через S и K: I = SKK. Действительно,

SKK(x) = K(x)(K(x)) = x = I(x)

Нотация Unlambda позволяет записывать карточные выражения в более компактной форме. Например, выражение для рекурсивного dec можно переписать так:

``S`K(``S get I)(`S`K`S`K`S`K`K zero dec get succ)zero

Заметим, что если в аппликации участвуют два сложных выражения, то их нужно собрать по отдельности в разных слотах, а потом «склеивать» картой get. Поэтому наш гипотетический транслятор с Unlambda-подобного языка должен был бы помимо собственно разбора выражения иметь некий аллокатор слотов, которые в данном случае являются аналогом регистров процессора. Эта задача была для нас неподъемна, мы даже пытаться не стали.

Итак, ко второму дню стало очевидно, что с dec далеко не уедешь. Ясно, что нужно использовать карту attack. Но чтобы уменьшить здоровье слота противника на n, нужно затратить своего здоровья. То есть, для убийства слота со здоровьем 10000, нужно иметь слот со здоровьем не менее 11111. Для «накачки» здоровья можно использовать карту help, использовав здоровье какого-нибудь слота-донора. И тут Саша произносит: «А где написано, что в help i и j должны быть разными?» Это гениально! Допустим, мы делаем help 0 0 9999. Сначала здоровье слота 0 уменьшается на 9999 и становится равным 1. Затем здоровье этого же слота увеличивается на 1.1 * 9999 = 10998 и становится равным 10999. Таким образом после одной такой процедуры здоровье слота увеличилось почти на тысячу. Десять таких процедур — и слот «прокачан» для того, чтобы убить вражеский за одну команду attack. А если добавить к этому рекурсивный цикл, то можно получить заклинание, «прокачивающее» за один ход свой слот до максимального здоровья 65535.

Это был прорыв. Новая версия игрока, использующая рекурсивный help и attack успевала убить все слоты противника примерно за 7000 ходов. Таким образом, спустя сутки, мы повторили результат лидеров. Лидеры тоже не стояли на месте, продолжая поражать наше воображение могуществом своих заклинаний. Во второй день они убивали нас примерно за 500 ходов!

Второй прорыв случился ближе к вечеру, когда я, анализируя выражение для цикла, обнаружил еще одну замечательную конструкцию: S(put)(get). Замечательна она тем, что если положить ее в нулевой слот и подействовать ей на карту zero, в нулевом слоте вновь окажется это выражение. Действительно,

S(put)(get)(zero) = put(zero)(get(0))

Функция put(zero) игнорирует свой аргумент и возвращает I, а get(0) возвращает содержимое нулевого слота. В итоге получаем, что

S(put)(get)(zero) = I(get(0)) = get(0) = S(put)(get)

В отличии от цикла-омеги, здесь не происходит повторного вычисления, так как отсутствует последний аргумент zero, поэтому вычисление заканчивается и результат помещается в слот ноль. Таким образом, мы получили конструкцию, которая позволяет обойти тот досадный факт, что все наши сложные заклинания превращаются в I после применения. Полезное содержимое в эту конструкцию засовывается уже известным образом, через K(zero). Соединив эту конструкцию, условно названную репитером, с атакой и положив полученное в выражение в нулевой слот, мы можем убивать вражеский слот всего за один ход, просто подействовав этим заклинанием на карту zero (everything starts from zero!).

Однако широкомасштабному применению этого заклинания мешало одно «но». Номер атакуемого слота нужно держать в своем отдельном слоте, чтобы перед новой атакой изменять его, так как само атакующее заклинание остается неизменным. И тут кроется засада. Структура функционального языка LTG такова, что функцию get нельзя передать в качестве промежуточного аргумента функции attack, а номер атакуемого слота как раз идет вторым аргументом, а не последним. Леша сказал, что уже работает над этой проблемой. Я вспомнил, что во время вчерашнего гуглежа я где-то видел описание многих комбинаторов, среди которых вроде встречался тот, который меняет порядок аргументов функции. И точно, это было C-комбинатор. В SKI-базисе он выглядит так:

C = S(S(K(S(KS)K))S)(KK)

Леша быстро сварганил нам такой комбинатор для attack, а потом и оптимизировал его, сделав руками бета-редукцию.

Тут стоит сделать маленькое лирическое отступление и упомянуть о такой вещи как Combinator Birds. Комбинаторные птички появились из книги «To Mock a Mockingbird and Other Logic Puzzles: Including an Amazing Adventure in Combinatory Logic», в которой в игровой форме в виде головоломок объяснялась комбинаторная логика. Различные комбинаторы в этом книге представлялись в виде птичек. Этих птичек существует великое множество, и все они производят очень интересные эффекты. Все это мы тоже узнали благодаря соревнованию и гуглу. С помощью комбинаторных птичек можно было бы составить очень интересные заклинания, но эту тему мы почти не затронули за неимением времени.

Теперь у нас было выражение, убивающее вражеский слот за 2 хода (собственно атака плюс инкремент номера атакуемого слота). Так как мы накачивали здоровье атакующего нулевого слота до 65535, то мы могли безболезненно убить им 3 вражеских слота со здоровьем 10000, после чего необходимо было снова делать рекурсивный help. Так как выход из рекурсии происходил при возникновении ошибки, то использовать в ней репитер было бессмысленно, результат выполнения функции все равно был бы I. Поэтому заклинание рекурсивного help мы продолжали копировать из вспомогательного слота. Стоит отметить, что рекурсию и репитер можно запускать из любого слота, для этого нужно изменить «контейнер» K(zero) на, например, S(K(K))(succ), в этом случае выражение будет работать в первом слоте.

Со всеми этими новыми знаниями мы наконец-то смогли вплотную приблизиться к барьеру в тысячу ходов, требуемых для полного уничтожения не особо сопротивляющегося врага. Наш игрок управлялся примерно за 1100 ходов. К этому времени у нас накопилось некоторое количество прошлых версий программ, и каждую новую мы «стравливали» со всеми предыдущими, чтобы оценить результат, после чего загружали на арену. Последняя версия программы выигрывала на арене примерно половину сыгранных матчей.

Посчитав, что на сегодня достаточно, я отправился спать.

День третий

Последний день соревнований как обычно начался со стратегического совещания. Было решено сосредоточиться на следующих проблемах. Во-первых, Саша наконец-то довел свой эвалюатор до работающего состояния. Это давало нам широкие тактические возможности. Для начала мы решили уничтожать вражеские слоты не по порядку, а отыскивать наиболее важные для противника и бить в первую очередь в них. Важность мы оценивали как длину содержавшейся в слоте функции. Помимо важности нужно было учитывать «расстояние» до слота, т. е. насколько сложно собрать его номер. Саша и Леша взялись за этот кусок, условно названный «целеуказателем». Саша занимался частью, связанной с эвалюатором, а Леша реализовывал алгоритм построения произвольного числа оптимальным образом, учитывая возможности повторного использования чисел, оставшихся в слотах после прошлых операций. А я решил исследовать карты, которые мы пока совсем не использовали, в первую очередь zombie.

Помимо своего прямого назначения вредить хозяину зомби играют еще одну очень важную роль. Даже после того, как слот противника умер, его можно воскресить картой revive и продолжить пользоваться заклинанием, хранящимся в слоте. Но если после убийства слота его зомбифицировать, то заклинание меняется на то, что было указано в команде zombie, т. е. старое значение безвозвратно теряется. Поэтому мы первым делом добавили обязательную зомбификацию убитого слота пустой функцией I.

Затем я собрал более осмысленную функцию для зомбификации на основе рекурсивного help, что позволило использовать зомби для убийства дополнительного слота. Таким образом за один ход убивалось два слота: тот, на кого непосредственно направлена атака и тот, на который затем нападает зомби.

Затем мы добавили в свою программу тактический элемент, известный как Zerg Rush. Суть его в том, чтобы в самом начале матча не тратить время на подготовку сложной инфраструктуры заклинаний для массового убийства слотов, а сделать максимально быстро простые заклинания, позволяющие убить один слот. При этом мы выбираем самый важный слот противника и зомбифицируем его. В результате при удачном стечении обстоятельств мы можем разрушить приготовления противника, и, пока он не очухался, добить. Прогон на арене показал, что эта тактика позволила нам продержаться около десятка тысяч ходов против тех команд, которым мы обычно проигрывали меньше чем за тысячу. С другой стороны мы все равно проигрывали им, видимо, у них были эффективные механизмы восстановления.

Затем я добавил простейший код, отслеживающий здоровье тех своих слотов, в которых хранятся заклинания, и воскрешающий их по мере необходимости. Это позволило одержать еще несколько побед на арене. После этого я попытался сделать полноценное «лечение» нулевого слота. Ведь если его убьют, то даже после воскрешения его здоровье будет равно 1, что недостаточно для работы рекурсивного help. На этапе отладки этого кода произошел забавный эпизод. К этому моменту наша программа уже довольно эффективно отслеживала ход игры, искала важные слоты противника, прицеливалась и уничтожала их. Я стравливал эти две одинаковые программы, в одну из которых и добавлял код лечения. Я долго не мог понять, почему не работает лечение, пока наконец не сообразил, что противник находит и уничтожает заклинание лечения раньше, чем я его собираю! Целеуказатель получился и правда отличный. Лечение я так и не довел до конца, так как время уже поджимало.

Окончательные результаты нужно было отправить не позднее 4 утра понедельника по Москве. В силу разницы во времени Леша к вечеру ушел спать, а мы с Сашей решили досидеть до конца. Мы сделали еще несколько мелких оптимизаций. Скажем, если в слотах, где у нас хранятся заклинания, обнаруживается I, значит наши слоты убиты и зомбифицированы, и мы уже ничего полезного делать не можем. Тогда мы переходили в бесконечный цикл и начинали воскрешать все слоты подряд. Такая тактика позволила «взять измором» ничью в некоторых ситуациях, а в каких-то даже выиграть с небольшим перевесом по слотам. Конечно, идеально было бы начинать все сначала, воскрешать слоты, накачивать их здоровьем, собирать заклинания, но на это уже не было времени.

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

Мы прогнали свои финальные тесты, отправили окончательное решение организаторам, а заодно и на арену. Через несколько минут я заглянул на арену и обомлел от ужаса. Наша программа на 56-ом ходу матча аварийно завершила работу! Такого у нас никогда не было. Мы начали лихорадочно анализировать ситуацию и поняли, что проблема как раз в коде, который ищет атаку при зерграше. Если он эту атаку находит, то что-то у него идет не так, и он выдает полную ерунду, из-за которой программа перестает работать. Вот это удар! Получается, что против сильных команд, которые успевают собрать раннюю атаку, наша программа вместо мощного зерграша просто падает. Но ничего не поделаешь. Я немного погоревал и лег спать, а Леша с Сашей еще через 45 минут нашли ошибку и исправили ее. Исправление, как водится, было в две строчки, но поезд уже ушел.

Результаты

По результатам первого раунда мы заняли 65-ое место из 199, во второй раунд прошли только первые 30 мест. Я выложил наш код на гитхабе, кому интересно, могут глянуть. Также свой код выложила японская команда «atomically $ save Madoka», которая с самого начала входила в число лидеров. Они успели сделать очень много, вплоть до собственной арены для обкатки разных AI. Рекомендую почитать их README. Они же после завершения соревнований подняли собственную арену, бои на которой идут до сих пор.

Что ж, это были незабываемые трое суток. Буду с нетерпением ждать ICFPC 2012, а пока есть время, засяду за Haskell.

P.S.

После подведения окончательных итогов организаторы выложили презентацию о том, как они готовили это соревнование.