Как и в прошлом году, в этом году готовиться к ICFPC мы начали заранее. Основная проблема прошлого года была зоопарк языков программирования. В этом мы заранее договорились, что будем писать на Java, но позже, из-за того, что некоторые ребята умели писать только на С++, поменяли выбор на С++. Всем было понятно, что этот язык не подходит для такого рода соревнования, но идея писать в crazy mode и тратить время на memory leaks и другие чудеса С++ в принципе всех устраивала. Потом это немного выйдет боком – просранная инициализация переменной заставит нас поломать голову над тем, почему решение падает один раз из 20 посылок :о) А еще надо было писать под Linux, так что для меня это было еще и первое серьезное знакомство с vim.
Умные ребята заметили, что картинка на сайте с символом lambda содержит в себе JAR архив, в котором лежит другая картинка, с изображением MTG-карты с лямбдой. Было понятно, что условие будет связано с lambda calculus и с Magic: The Gathering. Это так и оказалось.

Условие.
Условие можно пропустить, если вы его знаете, или прочитать по диагонали (особенно описание карт). Вникать не обязательно.
Играют два игрока. У каждого есть 256 слотов. Каждый слот характеризуется его хп (в начале 10К) и его содержимым. Содержимое – либо число, либо функция.
Также у каждого игрока есть неограниченный набор карт. Каждая карта – это тоже либо число (такая карта всего одна -- zero), либо функция. На своем ходу игрок выбирает одну карту, и один свой слот. Если у слота ноль хп, ход сразу завершается, и ничего не происходит. Иначе, игрок говорит, хочет он сыграть слот на карту, или карту на слот. В первом случае, если в слоте функция, то она вызывается, и в качестве параметра ей передается выбранная карта, а если в слоте было число, то ход завершается с ошибкой. Во втором случае все происходит наоборот – значение в слоте передается в качестве параметра функции на карте. В обоих случаях результат выполнения заносится в выбранный слот.
Например, пусть в слоте лежит фукцния I (функция, которая принимает один аргумент, и возвращает его). Пусть игрок выбрал этот слот, и выбрал карту zero, а затем выбрал, что он играет слот на карту. Тогда значение на карте (ноль) будет передано функции в слоте (I) в качестве аргумента. Результат (который, очевидно ноль) будет помещен в слот.
Далее по тексту ход “revive 5” будет обозначать игру карты revive на слот 5, а ход “5 revive” – игру слота пять на карту revive (номер слота и название карты выбраны для примера).
Игра кончается либо когда у одного из игроков все слоты имеют 0хп, либо после 100К ходов.
Кратко пробежимся по картам:
I(x) – функция, которая возвращает x.
Zero – число ноль
Succ(x) – возвращает x + 1
Dbl(x) – возвращает x*2
Inc(x) – увеличивает хп в своем слоте x на один.
Dec(x) – уменьшает хп в слоте оппонента с номером 255-x на один.
Attack(i,j,n) – наносит в свой слот номер i n урона, а в слот оппонента с номером 255-j n*9/10 урона. То есть себе наносится урона больше. При этом если в своей клетке меньше чем n хп, то атака не пройдет – это важный момент. При этом если в слоте оппонента меньше хп, то атака пройдет, просто оставив в клетке 0 хп.
Help(i,j,n) – наносит в свой слот номер i n урона, и свой же слот j лечит на 11*n/10. Опять же, если хп не хватает в i-ой клетке, то ничего не сработает.
Put(x) – возвращает I.
Get(x) – возвращает содержимое своей клетки с номером x. Очень удобная функция :о)
Copy(x) – возвращает содержимое клетки оппонента с номером x.
Revive(x) – если в своей клетке x ноль хп (она мертва), делает в ней 1 хп.
Это все были скучные функции. Еще две функции выносили мозг:
K(x,y) – возвращает x
S(x,y,z) – вычисляет h=x(z), вычисляет g=y(z), возвращает h(g).
И одна функция делает всю эту игру втройне интереснее:
Zombie(i,f) – если у оппонента слот 255-i мертв, то делает ей -1 хп, и помещает туда функцию f.
Сразу же после этого, перед ходом оппонента, все клетки, у которых -1 хп, автоматически вызывают содержащуюся в них функцию (и кол-во хп меняется обратно на ноль), передав ей в качестве параметра I. При этом (и это самое крутое) в этот момент значение функций inc, dec, attack и help меняют знак в своем позитивном эффекте. Так, inc наносит урон вместо лечения, dec лечит вместо нанесения урона, attack лечит вместо нанесения урона врагу (но по прежнему наносит урон себе), help наносит урон дважды вместо нанесения урона и лечения.
Теперь к повествованию.

Первый день, четверг.
Контест начался в пять вечера по моему времени. Я ошибся с переводом времени, и был уверен, что он начнется только в пятницу. Случайно открыв сайт в восемь вечера я был очень неприятно удивлен.
О стратегии пока думать было рано. В любом случае будет нужен эмулятор игры, поэтому сначала я написал классы карты, слота, игры, и вбил эффекты всех карт. С++ для этого оказался не самым лучшим выбором, но было поздно идти назад :о) Потом написал небольшой интерпретатор, который позволяет играть двумя игроками. Жюри предоставляло свой, но он был ужасно неудобен в плане управления, и добавления AI. День примерно так и кончился. Ребята за ночь хорошо проанализировали разные комбирации, и составили целую страницу идей.

День второй. Пятница.
Теперь, когда небольшой набор инструментов есть, можно пытаться думать о стратегии. Первая мысль, которую мы проверяем, это бесконечные циклы. Получается написать функцию, которая вызывает inc(0), то есть лечит нулевую клетку, а потом вызывает саму себя. Неприятность в том, что если в течение хода выполняется более 1000 функций, то ход останавливается с ошибкой (при этом выполненные эффекты не отменяются). Из-за этого лечащая функция успевает полечить только на 200. При стартовом ХП у клетеки в 10000 сразу видно, что inc и dec бесполезные функции (dec может быть разве что полезен добивать слот, который оживили revive-ом, так как у слота в этот момент 0 хп, но это мы так и не применили почти).
Несколько важных моментов еще: 0-ой слот стратегически очень важен, потому что к нему легко обращаться. Допустим, чтобы его оживить достаточно сделать x revive; x zero, где x – номер любого другого слота. И, в тоже время, нулевой слот очень сложно убить, потому что все функции, которые общаются к клетке оппонента, обращаются к клетке с номером 255-i, поэтому чтобы нанести урон в нулевую клетку, надо передать 255 в качестве аргумента, а набрать 255 используя только succ и dbl очень сложно. Ближе к середине контеста станет понятно, что тот, кто убивает нулевую клетку быстрее, побеждает, потому что оппонент теряет возможность эффективно играть.
Значит первая идея стратегии такая. Сначала мы набираем с помощью dbl число 8192 в 0-ом слоте. Потом мы делаем attack(0,0,get(0)), что значит, напомню
1. Нанести себе get(0) = 8192 урона в нулевой слот (он останется жив)
2. Нанести оппоненту 8192*0.9 урона в 255-0=255 слот
Затем сразу делаем attack(1,0,get(0)), что наносит нам 8192 урона уже в первый слот, а оппоненту опять 9/10 от 8К опять в 255. Это убивает 255-ый слот оппонента. А в убитый слот, как мы знаем, можно посадить зомби. А зомби вызывается от имени оппонента, и не имеет проблемы с 255-x. В зомби закладываем функцию, которая делает help(0,0,8192), которая, как мы помним, если выполняется от имени зомби, имеет другой эффект, и просто наносит два раза 8192 урона в нулевую клетку, что ее благополучно убивает. Затем строим функцию help(1,1,8192), которая убивает первую клетку таким же образом.
Сложность в реализации была в том, что не любую функцию легко построить. Например, пусть мы хотим получить attack(get(0),get(0)). Мы играем 0 get, получаем get (в нулевом слоте была функция I, мы передали ей get в качестве аргумента, и она вернула get). Мы играем 0 zero, получаем get(0). Мы играем attack 0, получаем attack(get(0)). Как теперь сделать attack(get(0),get(0))? Чтобы это сделать, надо сделать K 0, S 0, 0 get, 0 zero. Не тривиально? А что, если нужная нам функция гораздо сложнее? Поэтому пришлось потратить не маленькое количество времени на то, чтобы написать раскрывалку скобок – программу, которая берет на вход строку, и возвращает ходы, которые эту строку позволят получить. С таким функционалом писать ботов стало проще. Для не интерактивного бота (который просто за ранее вычисляет свои ходы, и играет их игнорируя действия оппонента) мы просто складываем в вектор результаты работы раскрывателя скобок.
Для первого бота мы просто написали функции вызова зомби последовательно с функциями help(0,0,8192), help(1,1,8192), доверив раскрывателю скобок их построить, и не думая об оптимизации этого процесса с помощью функции get совсем.
Такой бот за ночь с пятницы на субботу в неофициальной турнирной таблице, предоставленной организаторами,  занял третье место.

День третий. Суббота.
Но конкуренты придумывали более крутых ботов, и наш бот постепенно падал вниз. Надо было оптимизировать. Благодаря использованию метода get, и просто оптимизации всех частей кода, получилось убивать нулевую клетку на 50-ый ход. Но кто-то умел делать это быстрее – потому что проигрывали мы в конце с такой тактикой всем топовым командам. Но для этой стратегии улучшить этот аспект уже не получилось. Все, что мы смогли улучшить сильнее, это убийство последующих слотов – за счет, опять же, грамотного использования команды get, мы убивали последующие слоты раз в три хода, убивая все за 1200. Лучшее что я видел в дуэлях, это алгоритм, убивающий нас за 500 ходов с чем-то. Он был на первом месте очень долгое время. Но было понятно, что не важно, как быстро ты убиваешь все. Важно было как быстро ты убиваешь нулевую. Потому наш алгоритм, который работает за 1200, часто убивали за 70К ходов, просто потому, что убивали нам нулевую быстрее – а без нулевой мы не могли сделать ничего.
Вечером я забил на развитие алгоритма с зомби, и начал исследовать новую идею, бота под кодовым названием healer. Если набрать число 8192 в первом слоте, а затем сделать help(0,0,get(1)), то мы нанесем себе в нулевой слот 8192 урона, а потом полечим его на 11/10 от 8192, то есть в итоге мы полечим клетку на 800 хп. Если это делать в бесконечной рекурсии, то она успевает поличить до максимума – до 65К (любые числа больше 65К в игре делались равными 65К насильно) прежде чем падает из-за вызова 1000 функций. Полагая, что все оппоненты, как и мы, будут пытаться слепо нанести 10К урона в нулевой слот, это должно было делать его неуязвимым. Такое получалось сделать уже на 36-ой ход.
Идея интересная, но час был поздний. Развивать ее времени бы не хватило, а проверить концепт как-то было надо. В качестве проверки я написал простой алгоритм, который после лечения до 65К нулевой клетки лечил по очереди все остальные, а затем начинал делать attack(get(0),get(0),get(1)), храня в первом слоте 16К, а в нулевом счетчик, который после каждой атаки увеличивался на один. Таким образом каждый ход я наносил 16К урона себе в очередную клетку (в которой 65К хп – ей это как комариный укус) и 9/10 от 16К оппоненту в очередной слот. Полагая, что оппонент не лечился, это убьет ему слот.
В таком виде я бота заслал. Он убивал все слоты оппонента за 4К ходов, если оппонент бездействовал или не учитывал, что у нас может быть 65К хп. Healer играл хуже чем зомби (но это и ожидаемо – это проверка концепта). Для зомби все шаги были оптимизированы до фанатизма, а в этом боте просто вбиты в том виде, в каком приходили в голову. Некоторые топовые боты его рвали как грелку. Это тоже ожидаемо. Но в остальном он дал некоторую пищу для размышления.
1. Он часто побеждал после 100К хода со счетом 255-1. То есть у нашего бота был убит один слот, а у оппонента один оставался жив. Легко понять, что это значит, что против нас играет что-то похожее на нашего зомби – оно убивает 255 клетку нам (мы ее лечим очень поздно), а затем пытается убить что-то еще, но не ожидает, что там 65К хп. В тоже время мы отлечиваем все наши клетки кроме 255-ой (которую нам убили), а потом убиваем оппоненту все клетки кроме нулевой, потому что наша 255, об которую мы бы это делали, мертва.
2. Часто мы проигрывали после 100К хода со счетом, допустим, 96-160. Не сложно заметить, что сумма чисел равна 256. Это, как опять же легко понять, оппоненты, которые просто пытаются быстро убивать слоты по порядку с конца, в то время как мы лечимся по порядку с начала. И, так как они убивают быстрее, чем мы лечим, то в итоге счет в их пользу (одно лечение занимает шесть ходов в нашей реализации, а одно убийство – четыре в лучшей, которую я могу представить).
Я ушел спать, а ребята оптимизировали healer’а.

День последний. Воскресенье.
Утром восресения до конца контеста оставалось еще 8 часов, но это было воскресенье, и на него уже были планы, поэтому я вышел из игры. Позже ребята допилили нового helper’а, который убивал оппонента быстрее, но в итоге в неофициальной таблице результатов зомби выигрывал чаще, чем healer, и именно его мы заслали как наше финальное решение.

Все наши боты были не интерактивные – мы предпросчитывали последовательность ходов, и просто ее выполняли. Поэтому написанный мной в начале эмулятор, который позволял поддерживать по набору ходов текущее состояние поля, по большому счету оказался бесполезным.
Контест не оставил такого же ощущения удовлетворения, как прошлогодний. В основном потому, что в этом году из-за большого количества отвлекающий факторов, и планов, не получалось посвятить все три дня целиком контесту. Это очень обидно. Написать симулируемый отжиг, чтобы найти короткую последовательность убийства нулевой клетки, или какую-то модель машинного обучения, чтобы менять тактики на ходу в зависимости от действий оппонента, было бы очень интересно, но я даже не брался за это, потому что понимал, что времени не хватит. И писать это на С++ в vim было бы очень смело.
В следующем году придется очень заранее думать над тем, чтобы планов никаких не было. Надо отметить, что соревнования посередине ICFPC написать хорошо не получается. TCO Round 1 был в восемь утра, но за день до этого я лег в четыре, потому что дописывал бота. В итоге место в третьей сотне – событие, которого не происходило очень долгое время. А на раунд mail.ru я вообще забил, потому что был увлечен ICFPC. В любом случае я бы не полетел в Россию на онсайт :о(