ICFPC-2020: инопланетные сообщения, галактические бои и уральские программисты

Стали известны итоги международного соревнования по программированию ICFPC-2020. Контест, организатором которого в этом году выступал Контур, прошел в середине июля, результаты огласили по традиции на Международной конференции по функциональному программированию. Победителем стала команда Closed and Restricted Boltzmann Machine. Второе место разделили две команды из Японии. На соревнование зарегистрировалось рекордное для последних лет число команд — 500. До финала дошли только 95.

У Контура был достаточный опыт, чтобы стать организатором контеста: на протяжении 15 лет компания принимала участие в соревновании. Легенду выбрали про изучение Космоса и общение с внеземными расами. Участникам предложили разгадать инопланетный шифр, понять его и вступить в виртуальный бой с помощью галактического языка программирования. О том, как придумать и провести контест для программистов со всего мира нам рассказали сами организаторы.

Команда Контура несколько лет пыталась придумать концепцию и провести ICFPC. И вот осенью 2019 года ребята получили приглашение стать организаторами соревнования для программистов со всего мира.

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

Часто в ICFPC громоздкая формулировка задачи. В один из годов было 40 страниц спецификации, на ее чтение у участников ушло 3,5 часа. В этом году организаторы решили обойтись без текста и заменить его на инопланетные аудиосообщения и изображения, которые надо разгадывать. Это было максимально нестандартно. Все разгадки участникам нужно было писать в чат. На расшифровку ушло 4,5 часа, вся спецификация состояла из цитат чата.

- Я когда-то где-то читал, что математики придумали, как конструировать язык общения с инопланетянами. У нас с ними ничего общего, но мы можем начать с ними общаться. Это выглядело совершенно дико, контринтуитивно и совершенно непонятно. Я изучил разные наработки человечества в этой области. Оказалось, пока все сообщения в Космос были простыми. Мы же хотели усложнить задачу, так инопланетяне стали посылать нам сообщения, в которых описаны алгоритм и программа, которые нужно запустить.

К ноябрю 2019 года у ребят был почти готовый инопланетный язык программирования. Решили, что после введения этого языка участники получат большое сообщение, для расшифровки которого, нужно написать виртуальную машину, выполняющую код на «элиенском (от alien) языке». После исполнения кода должен появиться «тачевый» интерфейс инопланетной операционной системы. В содержании операционки будет PlanetWars — бои кораблей, которые вращаются вокруг планеты в двумерном пространстве.

Итого задача была такая:

1. Расшифровать инопланетный язык программирования

2. Реализовать на нем виртуальную машину, которая исполнит огромный код из файла

3. В файле написана операционная система (во время контеста мы ее назвали Galaxy Pad). В операционной системе есть туториалы, которые обучают тому, как управлять космическими кораблями.

4. В процессе прохождения туториалов нужно научиться общаться с сервером инопланетян без запуска операционной системы

5. Написать бота, который будет играть в PlanetWars и победить всех в этой игре

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

— Нужно было нарисовать кнопку, но ты не можешь ее изобразить как кнопку. И весь интерфейс превращается во что-то нечитаемое. А я как дизайнер интерфейсов пытался сделать все достаточно лаконично, просто и понятно.

Мы придумали мега концепцию, что наш интерфейс — это такие слои в пространстве. Каждый раз когда взаимодействуешь с какой-то штукой, она предлагает тебе следующее взаимодействие, и у тебя появляется новый слой с новой информацией с новыми кликабельными элементами. И когда у нас эта идея появилась, я себя просто представлял инопланетянином, висящим в пространстве перед таким голографическим объемным дисплеем многослойным. Получилось здорово.

Саша придумал 16 цивилизаций по всему Космосу. Для каждой была своя интерактивная иконка, которая ее характеризует.

Ожидание:

Реальность:

Среди списка рас в галактике на главном экране были неожиданные находки.

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

Кстати, ось z у инопланетян направлена вверх, как у математиков.

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

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

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

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

— ICFPC есть проблема: топовые команды всегда свои лучшие алгоритмы и решения держат в секрете до последнего и выкладывают их за 5 минут до финиша. Чтобы у противников не было шансов проанализировать и подготовится. У нас была задача это поменять и замотивировать все команды выкладывать наилучшее решение как можно раньше. Поэтому система турнира у нас была многоступенчатой. Она была чем-то похожа на Кубок мира по биатлону. Там были этапы и за каждый начислялись очки. В финал попали 20 команд по сумме набранных очков за все этапы. Таким образом у команд нет шансов отсидеться в тени. Получился в итоге зрелищный чемпионат. Решения постоянно улучшались, это было наглядно! — говорит Алексей.

Атмосфера соревнования была скорее дружеской: все обсуждали идеи, общались, подшучивали друг над другом. Например, организаторы изменили название постоянного участника ICFPC команды Cat #1. Написали код, который в лидерборде мог переименовывать название команды на текущее место, которое они занимают, например, место 12 и название становится Cat #12. Это просуществовало часов 6, после чего ребята из команды написали в чат: «Эй, вы чего сделали название нашей команды динамическим?)))Вы клевые, нам понравилось!»

— Забавно было наблюдать за тем, как команды называют части кораблей, которые построили. Корабль состоял из топлива, радиаторов, лазеров и двигателей. Но это мы их так называли. У инопланетян все на своем языке. Команды должны были выяснить с помощью экспериментов, за что отвечает та или иная часть корабля и придумать им какие-то названия. Кто как называл: “теломерами”, командой “крю”, “бейбис”, — вспоминает Павел Егоров.

Победителей разных раундов огласили вчера. Ими стали пять команд:

Main round, 1st place

Первое место в основном раунде получила команда — Closed and Restricted Boltzmann Machine. Ребята лучше всех выполнили задание, писали на Python.

Main round, 2nd place (two teams share the prize)

Второе место заняли две команды из Японии: Unagi, которые писали на Rust, и 182020, их язык программирования C++. Команды написали очень похожих ботов для решения задачи.

Lightning Round

Команда «powder» — победитель lightning раунда. Этот раунд длится первые 24 часа: выигрывает та команда, которая смогла быстро что-то сделать. В нашем случае они решили больше всех туториалов и лучше всех научились вести бой. В составе команды четыре человека из разных стран. Ребята писали на языке Haskell.

Judges’ Prize

Приз жюри получила команда ребят из Уфы WILD BASHKORT MAGES. Они так увлеклись написанием галактики, что решили реализовать своих ботов для planetWars так, что они играли, нажимая на экран галактики. Очень неэффективно, но впечатляюще. Использовали язык OCaml.

— Удивительно новое ощущение от контеста: обычно изо всех сил стараешься победить и в конце чувствуешь неудовлетворенность от результата, потому что все равно ниже, чем ожидал. А тут у нас было одно из худших выступлений за все участие в ICFPC, но на душе прекрасно и удовольствие получено, — говорит Максим Муратов, капитан команды из Башкирии.

По словам участников и организаторов ICFPC-2020 — один из сложнейших контестов за всю историю. На соревнование зарегистрировалось рекордное количество команд — 500. Но до финала дошло меньше, чем обычно, всего 95. Обычно в первый день контеста участвуют 300 команд, 150 доходят до конца.

Организаторы тоже остались довольны. Говорят, что сами бы хотели сыграть в нечто подобное :)

— Хотели сделать то, что запомнится и будет сильно не таким, как раньше. Чтобы это было что-то неожиданное замечательное и запоминающееся. Это была основная цель. Все решения мы принимали исходя из этого. Кажется, у нас все получилось, эту цель мы достигли. Когда ICFPC только появлялся, 20 лет назад, это было редкое явление. Сейчас много всего проходит, в такой реальности не понятно, какое место занимает ICFPC. Надо понять, ради чего его проводить. Наш ответ был такой: у всех остальных соревнований есть вполне определенный формат, а ICFPC это единственное место, где этот формат можно как угодно нарушить и сделать максимально нестандартную штуку. Хочешь ботов писать – иди на Coding Game, хочешь алгоритмы – иди на CodeForces, а хочешь что-то необычное, свежее, непохожее ни на что – иди на ICFPC.