ICFPC 2012 — соревнование по функциональному программированию

Всем доброго времени суток.

С 12:00 GMT пятницы, 13го июля, до 12:00 GMT понедельника, 16го июля проходит ежегодное соревнование по функциональному программированию, приуроченное к International Conference on Functional Programming 2012 ^[1] (ICFP).

Контест примечателен по многим причинам. Лично меня покорило задание 2010 года. В первую очередь тем, что нужно было не просто программировать, но и много заниматься reverse engineering'ом, ломать загадки других команд и создавать свои так, чтобы их было как можно сложнее решить.

Для тех, кто хочет узнать обо всем поподробнее:

• контесты прошлых лет ^[2]
• отчет команды 6-11 ^[3]
• отчет команды SnakeTeam ^[4]

Для остальных расскажу коротко. Нужно было придумывать и загружать на сервер «машины» и подбирать «топливо» для чужих машин. Но не все так просто. Изначально не был известен даже формат, в котором принимались ответы. Да и решение машин требовало неплохих познаний в математике.

В этом году задание ^[5] не такое веселое — нужно всего лишь программировать робота, который добывает лямбды из шахты и подозрительно похож на известную игру Supaplex ^[6]. Для того, чтобы участники не расслаблялись, организаторы периодически добавляют новые условия ^[7]. Соревнование разделено на два отдельных зачета — блиц (1 сутки) и основное соревнование (3 суток).

Для тех, кому не терпится — ссылка на саму игру ^[8].

К сожалению, мы слишком поздно узнали о контесте и не смогли собрать полноценную команду. Поэтому наша команда состоит всего из двух человек (разрешено до 20, командам меньше 4-5 человек обычно приходится очень трудно): меня и GreenPeace ^[9]

В первую очередь очень остро стоял вопрос — а стоит ли вообще заморачиваться? Вдвоем ведь почти ничего не успеем. Тем более никакого взламывания чужих решений в этом году не предусмотрено, а это было самым веселым. Потом решили, что можно попробовать сделать робота со случайным поведением и минимальным инстинктом самосохранения и отправить его в блиц-зачет, просто ради интереса. Следующей мыслью было написать эмулятор этой игры и проходить руками для обучения нейронной сети. И логичным следствием из этого стал перенос игры в JS и создание сайта для краудсорсинга ^[8]. Это уже под силу даже команде из двух человек. Насколько хорошие это принесет результаты — увидим позднее.

Времени мало, серверов под рукой нет, поэтому статика лежит на народе (надеюсь ему хабраэффект не страшен), а минимально необходимая динамика — на первом попавшемся бесплатном хостинге ^[10].

Об игре

Задача робота — собрать все лямбды и пройти к лифту. За каждую собранную лямбду робот получает 25 очков. Если он их донесет до лифта — еще по 50 за каждую. Если прекратит добычу (abort — кнопка «А») — по 25 за каждую. Ну а если утонет или получит камнем по голове — то никаких дополнительных очков робот не получит. За каждый шаг робот теряет 1 очко.

Кроме того, камни падают, если есть куда, скатываются друг с друга (вправо или влево) и с лямбд (только вправо).

Через несколько часов после начала организаторы добавили наводнение. Раз в несколько ходов вода поднимается, робот может в нее нырять, но не дольше чем на несколько ходов. Сколько именно составляет это самое «несколько» — зависит от карты.

В данный момент для игры доступно 999 карт (15 карт от организаторов и 984 случайно сгенерированные). Карты от организаторов сделаны вручную, интересны и заведомо проходимы. Для случайных карт мы не гарантируем ничего. На некоторых вообще ничего нельзя набрать. На других оптимальной стратегией будет сбор доступных лямбд и прекращение игры. Кроме того, на случайных картах пока нет наводнений. Но это будет исправлено сразу после того, как наша команда немного поспит. C начала контеста прошло 16 часов и сейчас самое время сделать перерыв на сон.

Планируемые обновления к игре:

• возможность undo
• карты с наводнением
• улучшенный алгоритм генерации карт
• прямые ссылки на карты

Вопросы, пожелания, багрепорты пишите в комментарии или в личные сообщения. Всем играющим — огромное спасибо.

UPD: Здесь буду выкладывать номера больших, интересных и, скорее всего, проходимых случайных карт, которые удалось найти: 313

Автор: Graphite