thirteen

ICFP Contest 2011 отчет (writeup) - San

июня 20, 2011 в 18:16 | Новости |

Провели соревнование в 2011 году классическим составом в том же месте.

Контест удался.

Принимало участие на удивление постоянное количество человек - семеро. Почетным гостем в этом году был маэстро dzhulgakov, и собирается продолжать! Мы использовали Java, как lingua franca для большинства участников.

Накануне мы успешно разобрали картинку на сайте организаторов, нашли там изображение омега комбинатора и намек на MTG, что дало повод всем прошерстить литературу по комбинаторной логике. Как оно ни страшно выглядит, но после всего прочитанного задание выглядит уже не так заумно, а когда мы сразу увидели комбинаторы в виде птичек, то стало ясно, что наконец-то функциональщина. В первый день сразу было написано почти всё (компилятор из лямбды в последовательности загрузки комбинаторов в сервер). Язык выглядит так (его расширения не приведены в этом примере)

@1 = 8192;
@0 = (^x.
 (help x x ((get 1)))
 (get x) x) 0;

Расскажу о прочих находках и интересных вещах, вперемешку.

* Мыслители sas и rst7 придумали само-модифицирующуюся программу. В нее приписываешь ноль, а у нее растет хвост из команд SUCC, и после вызова она становится длиннее, а внутри у нее число 0+длина доступно как аргумент, чтобы там может кого-то подлечить или атаковать. Это однотактовый (1 такт на запуск) сканирующий выполнятель.

* Рекурсию, ограниченную 1000 редукциями, можно делать как использованием Y-комбинатора, так и с использованием команды GET, с последующим к ней примененем своего операнда: @0 = x. (dec (K 5 x)) ((get x) x)).   Если добавить нолик, то он попадет в x, выполнится DEC 5, а затем возьмется копия самого себя (GET 0), и применится снова нолик, и всё повторится. Это не совсем рекурсия, тк у нее нет условий, а скорее tail call.

* Мы пробовали нумералы Чёрча, и они работают, но сами понимаете. С другой стороны на них удобно тестировать парсер и конверторы из одной формы в другую.

* Наш компилятор кажется не до конца оптимальный. Чего-то мы не поняли. И еще этот язык не ленивый, а вовсе даже strict. Это из-за того, что оно всё приводится в нормальную форму уже при загрузке, сервером. Это неприятно, т.к. код получается больше чем мог бы быть. Dzhulgakov расширял наш лямбда-язык до последнего дня, дорасширялся так, что стало страшно смотреть, с самого начала выйдя за уровень лямбда-калькулюса ВНИЗ к уровню комбинаторов, так сказать, прагмы компилятора. Javacc оказался в умелых руках dzhulgakov-a мощным инструментом. Теорию о преобразовании lambda v SKI нашли в википедии. Преобразование SKI в право-лево аппликативную последовательность увидели у организаторов на примере.

* Понятное дело, мы смоделировали всю runtime-систему, так что знаем состояние и врага и наше собственное точно как положено.

* Самым важным куском бота, дающим нам большую фору, если не 100% победу, является программа (rst7/sas/tilarids), запускающаяся самой первой, которая пробивает брешь в 255 ячейке противника, заселяет туда зомби, который один сносит 64 ячейки подряд под ноль с использованием рекурсии и двух команд help. Программа запускается 4 раза с разными аргументами, и это позволило нам покрыть всего противника нулями. Кое-кого это убивает к 177 ходу целиком. Программу написали и отладили за 4-5 часов до конца, так и оформили окончательный сабмит.

* Как и в любой игре, существуют защитные стратегии, и нападательные. Надо было найти баланс. Смешать всё вместе. Поэтому после зомбо-бомбера у нас грузится сначала маленькая программа-камикадзе, которая умеет рубить с плеча подозрительные цепочки врага. Потом, пока она их рубит, в промежутках подгружается следующая программа-камикадзе, которая на всякий случай умеет делать это быстрее. А когда и она загрузилась и даже работает, то грузится третья программа, которая умеет убивать тоже быстро, но не тратя собственных сил. Для этого она  выстреливает во врага, а потом себя лечит, всё в пределах 1 хода. Кушает она из ячейки с жизнью 65535, каковой баланс и поддерживает. Стреляет (когда сканируя) - за 2 такта на выстрел (инкремент цели + запуск). Пока делается подгрузка и расстрел противника, специальная программа, с более высоким приоритетом, мониторит на тему убитых ячеек (у которых жизнь 0) и восстанавливает их, приостанавливая выполнение прочей задачи в текущей точке. Потом прочая задача продолжается. Каждая программа (записанная в виде примера (см выше)) знает в какие слоты она грузит свой код, и слушая глобально изменения врагом своих слотов, может отменить свою дальнейшую загрузку (т.е. уже мусор в слоте), а потом рестартовать загрузку.

* Сразу после загрузки какой-то подпрограммы, мы копируем ее в известное место. Если одну из копий убьют, то она восстанавливается тут же из второй (get XXX). При запуске участвует только одна. С самым большим приортетом среди прочих программ дейтвует проверялка, не убили ли кого-то за последний шаг. Если да, то запускается лечилка тоже с макс приоритетом.

* Кое-где константы генерятся в текущем контексте  - вдруг можно украсть у оппонента, или скопировать и проинкрементить. Все возможные варианты генерируются в виде строк, потом компилируются и выбирается самый короткий вариант (на крайний случай есть 1 способ генереции константы с помощью dbl/succ/zero , он вам известен)

* Способ выбора слота врага для отстрела вначале был реализован собиранием статистики по активности его по ячейкам (записи в ячейку), и потом выбирается ячейка с самой длинной программой самая последне-модифицированная. Она и убивается. Затем был написан другой алгоритм, который определяет, какая ячейка читается (get) в процессе работы вражеских программ за последнее время (таким образом, выбирается самая “горячая” часть программы). Мне кажется, надо было брать больший срез времени для нахождения этого места, но работало не хуже, а сильно оттестировать не успели.

* Из нереализованного: анализ вражеской программы на сайд эффекты, с целью украдания. Был написан анализатор (трассировщик), который собирал сайд-эффекты, но использовать эту информацию и стырить произвольный код не успели. Потенциально можно было бы строить аттакера, а лечилку стырить, или строить лечилку, а аттакера стырить.

* Из нереализованного: запустить публичный сервер, к которому можно подсоединиться и сыграть в онлайне, и анонсировать его на IRC. Позволило бы нам, и другим посмотреть на чужой лямбда-код 8-). Не сделали это, т.к. у меня были сомнения, что хоть кто-то прийдет и вот так откроется. На удивление, моральных преград я не испытывал 8), т.к. организаторы явно не запретили это делать в своем задании.

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

По результатам мы далеко не первые. Хотя наша лямбда со 177-ходовым результатом кажется превышает всё что мы видели во время соревнований на тестовом сервере (и только что наткнулись на ссылку со 187-ходовым алгоритмом таким же), но, по-видимому, победители знают что-то еще, до чего мы не догадались. И таких людей, которые что-то знают, будет человек 20-25, думаю (я боюсь еще оказаться оптимистом).

Примечательно, что в этом году ICFP (fp - это functional programming) наконец-то был функциональным (хотя бы по форме), после трех лет непонятно чего. Функциональности было достаточно, и она постоянно стояла на пути (оптимизация кодов, думание в комбинаторах и лямбдах). Хоть основной алгоритм (игровой) был без привязки к лямбдам. Наверное этот факт и вызвал наибольший подъем духа участников. И, я смотрю, не только у нас, а и в отзывах на irc/jabber. У нас были полностью и в удовольствие заняты все участники команды. По этому поводу мы скажем троекратное: УРА! УРА! УРА!

P.S. отчет tilarids-a, отчет brox-a.

P.S. Наш сабмишн лежит в лямбде 8). Или по адресу http://thirteen.static.tor.hu/THIRTEEN.tar.gz