ICFP Contest 2020 от идеи до воплощения. Как организовать контест и выжить
В этом году мы стали первой командой из России, которая организовала международное соревнование по программированию ICFPC. В статье рассказываем, как перешли из участников в организаторы, какие грабли и вызовы встретили по пути и каким в итоге получился контест.
Как все начиналось
Леша Кирпичников (beevee):
Идея податься в организаторы была вызвана какой-то нарастающей фрустрацией от того, что каждый год на контестах ничего нового. Задачи на оптимизацию, планирование движения бота или графовые алгоритмы, что мы видим каждый год, уже всем надоели. Начали думать, а как бы сделали мы. Вот бы было, как в легендарных 2006 или 2007. Смесь ностальгии по былым годам и недовольство тем, как сделано сейчас. Причем недовольство во многом и задачей, и тем, как технически устроена игра в эту задачу. Последние несколько лет мы не особенно удачно участвовали в контестах часто по техническим причинам. Например, разработали хорошее решение, но из-за особенностей того, как надо было сдавать решения на контесте, мы допустили нелепую ошибку и не вошли даже в топ-50. Все это вылилось в то, что мы стали стучать виртуальными кулаками по виртуальным столам и говорить: дайте нам попробовать, сделаем по-своему.
Последние два года мы писали организаторам, что хотим попробовать себя в новой роли и разработать следующее соревнование. В сентябре 2019 получили положительный ответ и предложение стать организаторами ICFPC 2020. Мы обрадовались, согласились и только потом задумались, куда именно мы вляпались :)
Про цель
Все разделяли одну простую идею: раз уж взялись, то делать нужно хорошо! Делать просто очередной обычный контест мы не хотели. Хотели сделать что-то неожиданное, замечательное и запоминающееся. Это была основная цель. Все решения мы принимали исходя из этого.
Когда ICFPC только появился, 22 года назад, соревнование для программистов было редким явлением. Сейчас по миру проходит очень много разных соревнований, в такой реальности непонятно, какое место занимает ICFPC. Наш ответ такой: у всех остальных соревнований есть вполне определенный формат, а ICFPC — это единственное место, где этот формат можно как угодно нарушить и делать максимально нестандартную штуку. Хочешь ботов писать — иди на Coding Game и Russian AI Cup, хочешь алгоритмы — на codeforces, а хочешь что-то необычное, свежее, непохожее ни на что — на ICFPC.
Забегая вперед, скажем, что свою главную цель мы выполнили. ICFPC 2020 действительно стал необычным и запоминающимся. За счет чего это получилось и что нового было в этом году?
Максимально продуманная легенда
Разрабатывали соревнование мы с сентября 2019 до самого последнего дня начала контеста. Да и во время контеста тоже что-то доделывали. Параллельно с задачей придумывался сеттинг: мир, в котором эта задача могла существовать.
Итак, сеттинг. К земле приближается инопланетный корабль и передает нам на Землю сообщение о существовании нескольких разумных цивилизаций в нашей галактике. Все они участвуют в большом галактическом турнире по игре в своеобразные космические бои. И в следующем бою очередь команды землян сразиться с лучшей стратегией от предыдущего победителя. А прилетевший корабль — это просто… игровой сервер, на котором можно изучить правила игры и потренироваться. Через 72 часа обитатели нашей планеты должны написать программу, которая играет в эту игру, и победить в схватке двух цивилизаций.
Зачем этот турнир? Что будет с проигравшими? Какой приз ждет победителей? Мы не знаем! Но наверняка лучше выиграть, чем проиграть :) Поэтому за 72 часа наша задача выбрать самый лучший алгоритм, который способны сделать земляне, и отправить в финальную битву именно его. Финал в ICFP Contest — это и есть наш земной турнир между лучшими программистами со всей Земли за право поучаствовать в инопланетном соревновании от имени всех землян.
С сеттингом мы действительно заморочились. Участникам требовалось совсем немного усилий, чтобы поверить в реальность происходящего и прожить эту историю, а не просто поучаствовать в контесте. И, без шуток, пару раз нам прямо задавали вопрос, реально ли это все происходит или это просто часть сеттинга для контеста :)
Но строгое следование сеттингу усложнило нам жизнь. Мы сделали настоящий мир вокруг него, правдоподобную задачу даже в тех местах, где это шло немного в ущерб соревнованию. Например, мы больше не могли человеческим языком объяснять, что имели в виду инопланетяне и зачем это все нужно. Но мы твердо стояли на своем: мы ничего не можем сказать участникам кроме того, что участники могли бы сами понять только по сообщениям от инопланетян.
Формулировка задачи, Иван Зайцев и Пеговка
Часто в ICFPC громоздкая формулировка задач. Однажды было 40 страниц спецификации, и мы ее читали 4 часа. Это нас деморализовало. И у нас появилась идея: что если сделать контест без спецификации вообще? Вместо четких правил будут инопланетные сообщения, которые участникам нужно будет разгадывать самостоятельно. Когда придумывали сценарий, было очевидно, что сообщения из космоса мы должны как-то получить.
Так родился образ астронома Ивана Зайцева, который принимает на свой радиотелескоп в Пеговской обсерватории сообщения от инопланетян и просит помощи в их расшифровке. Это все стало первым вводным видео на ломаном английском
Для него Леша Кирпичников отрастил бороду (шутка, она сама отросла за время карантина), нашел медицинский халат, принес перфокарты. Мы распечатали текст, который Леша читает, чтобы он был как бы написан на перфокарте. Сделали бейдж с именем Ивана Зайцева, работника Пеговской обсерватории. В пользу легенды также создали блог Ивана Зайцева
Запись первого видео
Реквизит
Кроме этого видео, были посты в блог и еще два вводных видео.
В общем, всеми силами старались создать логичную историю. Это было максимально нестандартно. Никто так не делал раньше. Поэтому в самом начале контеста народ активно спрашивал: «Что делать то? Где правила, инструкции, какой код писать? Как очки зарабатываются?». На что мы отвечали «Ребята, какие еще очки! Мы получили сообщение от ИНОПЛАНЕТЯН, помогайте нам его расшифровать быстрее!». Все разгадки участникам нужно было закидывать в чат Discord, а мы собирали все дельные идеи в публично доступную спецификацию. Коллективный разум разгадывает в 10 раз быстрее, чем отдельные люди. Спецификация к задаче появилась через 4,5 часа, и вся она состояла из цитат участников в чате.
Почему Иван Зайцев
Имя хоть и простое, но выбрано не случайно.
Оно состоит из двух частей:
- Есть канадский астроном Yvan Dutil. Он один из авторов сообщения, которое в 1999 и 2003 гг. земляне отправляли к звездам с помощью радиотелескопа в надежде найти там разумную жизнь.
Многие, наверное, знают о существовании SETI — института поиска внеземного разума. Но есть еще и менее известный институт METI, который изучает возможности не просто наблюдения за космосом, а общения с внеземными цивилизациями. И с Земли уходило в космос уже несколько десятков посланий. Несколько из них имели вполне профессионально составленное содержание. Смотрите Arecibo message (1974) и CosmicCall (1999 и 2003). В нашем сеттинге мы находимся по другую сторону, мы получатели подобного сообщения.
Тут есть интересная проблема, как составить сообщение и суметь в нем рассказать что-то нетривиальное существу, восприятие которого, может быть, сильно отличается от нашего. Они не знают, где верх и низ, не знают базовых понятий, с помощью которых можно это донести. Yvan Dutil — один из авторов сообщения, которое реально отправили в космос. - Александр Зайцев — человек, фамилию которого мы взяли.
Это российский астроном, радиофизик, глава российской организации SETI. Он один из идеологов и активистов, благодаря которым как раз и реализовались проекты CosmicCall и CosmicCall2.
То есть нашими вдохновителями стали люди, которые причастны к отправке сообщений в космос.
Из чата организаторов
Почему Пеговка
Потому что есть Коуровка — настоящая обсерватория в 90 км от Екатеринбурга. Каурый — это масть лошади, пегий — тоже масть лошади. Отсюда родилось название. Это все такие пасхалочки. Мы пытались в разных местах наполнить, старались сделать так, чтобы везде был свой нюанс, какая-то фишка.
И получилось настолько хорошо, что за две недели до начала контеста у нас появились подражатели: еще одна «обсерватория», которая получила сигнал, где изображено не совсем то, что в наших. И тоже предложила участникам разгадывать нарисованное. Мы аккуратно, не разрушая сеттинга, сказали, что не знаем этих ребят, если хотите решать, решайте на свой страх и риск.
Итого задача участников была такая
- Расшифровать инопланетное послание.
- Понять, что там описывается язык программирования и виртуальная машина, его выполняющая, с дисплеем и тачскрином :)
- Реализовать на своем любимом языке программирования виртуальную машину и выполнить на ней последнее самое большое сообщение от инопланетного корабля.
- В запустившейся программе (участники назвали ее galaxy из-за значка, которым она обозначалась у инопланетян) разобраться с особенностями инопланетного пользовательского интерфейса, понять, что речь идет о галактическом турнире.
- Найти обучающие туториалы и изучить с их помощью правил игры.
- Написать бота, который будет играть в игру и победит всех.
Как придумывали концепцию задачи
Самый простой вариант — сделать задачу на оптимизацию и просто принимать файлы с решениями, которые легко проверять. Однако это ограничивает в выборе задач. Мы решили себя не ограничивать, что сложнее, но зато можно сделать такую задачу, которую мы хотим.
После того как обсудили желаемые качества контеста, начали накидывать и обсуждать идеи. Были мысли об издевательствах над известными играми, например, игрой «Жизнь» или «Элузис».
Первые пару месяцев мы встречались раз в неделю-две и штурмили. Мы старались найти какую-то не очень известную конструкцию, идею, погрузиться в нее, сделать что-нибудь интересное на ее основе.
Паша Егоров (xoposhiy):
В процессе штурмов я вспомнил, что когда-то где-то читал, что математики придумали, как конструировать язык общения с инопланетянами. Мы ничего не знаем про инопланетян, их физиологию и культуру, у нас нет общих понятий, но мы тем не менее можем начать с ними общаться. И математики якобы знают, как конструировать такие сообщения. Это выглядело необычно, загадочно и потому привлекательно. Появился повод разобраться, как это делается. Оказалось, у человечества действительно есть довольно много наработок в этой области. Они появились еще тогда, когда человечество верило в обилие разумных цивилизаций в галактике, готовых вступить с ним в контакт.Так, еще в 1960 году, когда человечество было уверено, что в ближайшие лет 5 установит радиосвязь с марсианами, немецкий математик опубликовал книгу «Lincos. Проектирование языка для межпланетного общения. Часть 1». Несколько сотен страниц подробно описывают, как общаться с инопланетянами. Начать в этой книге предлагается с математики и логики, а далее на примере диалогов двух собеседников вводить более сложные понятия, например, «хорошо» и «плохо».
У нас появилась дерзкая идея: что если на подобном языке не мы, а инопланетяне отправят нам сообщение. И что это за сообщение? Текст? Ну нет! Пусть они опишут виртуальную машину и пришлют нам операционку, которую нужно будет загрузить на этой виртуальной машине!»
Паша Егоров взялся за эту идею и начал ее прорабатывать. Он приносил на встречи такие картинки:
Мы их весело разгадывали, и через какое-то время стало понятно, что это самая проработанная часть. К ноябрю 2019 у нас был прототип сообщений от инопланетян, в частности описание виртуальной машины (на основе SKI-комбинаторов). Мы определились, что после введения этого языка программирования мы дадим участникам большое сообщение, для расшифровки которого им надо будет написать виртуальную машину, исполняющую код на инопланетном языке. После исполнения кода перед глазами участников должен появиться «тачевый» интерфейс инопланетной операционной системы (мы его называли aPad — как iPad, только aPad от alien). А вот что будет внутри этой операционки, до последнего оставалось загадкой. У нас были готовы авторская реализация виртуальной машины и несколько примеров программ, которые можно было на ней запустить.
Турнир и космические битвы
В декабре 2019 мы активно обсуждали содержание операционки. Победившей была идея PlanetWars. Бои кораблей, которые вращаются вокруг планеты в двумерном пространстве. Первые картинки этого выглядели так:
Идея требовала работы с числами с плавающей точкой. Это была проблема — вводить на инопланетном языке стандарт IEEE 754 никому не хотелось. Но тогда на нас накатило вдохновение, полученное от решения задачек из 12 дня Advent Of Code, которые как раз тогда мы все решали: гравитация должна быть дискретной. Долгое время эта часть контеста так и называлась у нас с префиксом АoC в честь Advent of Code, который подарил нам идею.
Дальше мы корректировали разные мелочи в правилах, в частности заменили все расстояния в нашем игровом мире на Чебышёвские и убедили себя, что планета должна быть квадратной:
(траектории на картинке декоративные, в пиксельном отображении их не было)
В итоге получилось, что инопланетный игровой сервер предлагал нам сразиться в дискретный 2D космический бой, в котором корабли могли маневрировать, стрелять странным оружием на расстояние, детонировать и разделяться на несколько кораблей. Все эти механики мы несколько раз уточняли, переделывали и балансировали. Мы старались сделать максимально простую игру, которую будет просто понять, и, с другой стороны, достаточно сложную, чтобы там были разные тактики и в нее было интересно играть.
Инопланетный интерфейс
Сложной задачей было придумать инопланетный интерфейс. Мы позвали в команду профессионального проектировщика интерфейсов. Саша Храмцов вложил много сил в то, чтобы сделать интерфейс понятным, но не использовать привычные землянам крестики закрытия, стрелочки, рамочки окон и прочие шаблонные вещи.
Саша Храмцов:
Визуальный интерфейс должен был быть максимально нечеловеческим, не похож ни на что. Грубо говоря, тебе нужно нарисовать кнопку, но ты не можешь ее изобразить как кнопку. Стандартные штуки для интерфейсов использовать нельзя. Всю информацию мы можем выводить только в каких-то знаках, символах. От такого подхода весь интерфейс превращается во что-то нечитаемое. А я как дизайнер интерфейсов привык делать все достаточно лаконично, просто и понятно
В первую очередь надо было придумать концепцию отображения на инопланетном экране. В космических боях корабли могут улетать на далекие расстояния в любую сторону, и надо уметь на экране все умещать. Поэтому первое решение, которое мы приняли: размеры экрана будут бесконечные во все стороны. Есть точка 0,0 — это центр, и во все стороны есть бесконечное пространство. Это начало координат в том числе помогало рассказывать истории: показывало где больше, меньше, где прошлое и будущее.
(история галактических боев с просмотром каждого боя)
Вторая задача: как отображать интерактивные элементы интерфейса. Ведь теперь мы не можем сказать «Давайте добавим кнопки над полем с кораблями» — поле бесконечное и у него нет «над». За много итераций и подходов родилась идея со слоями. Каждый раз когда взаимодействуешь с какой-то штукой, она предлагает тебе следующее взаимодействие, и для этого у тебя появляется новый слой интерфейса с новой информацией с новыми кликабельными элементами. У нас получился такой объемный интерфейс, как голографические экраны в фантастических фильмах.
Саша Храмцов
Я себя просто представлял инопланетянином, висящим в пространстве перед таким голографическим объемным многослойным дисплеем. Так я ставил себя на место пользователя.
(интерфейс космического боя и управления кораблем)
У себя мы эти экраны накладывали с разной степенью насыщенности — первый самый ближний и самый яркий, последний самый далекий и самый тусклый. Мы ожидали, что участники будут придумывать свои оригинальные способы визуализации, и они нас не разочаровали.
Наша версия: 
Одна из версий участников: 
(это главный экран операционной системы, центр галактики — точка (0, 0))
Саша Храмцов:
Передо мной стояла еще и такая задача: картинки, которые получаются у участников, должны быть настолько клевыми, чтобы им захотелось выкладывать их куда-то. В инстаграм, например. Среди организаторов мы говорили, что все должно быть instagrammable. Я придумал порядка 16 цивилизаций по всей галактике, для каждой была своя иконка, которая ее характеризует. Их можно было нажимать, открывать, разглядывать.
Во время контеста мы собирали скриншоты, которые участники публиковали в чате, твиттере и инстаграме — получился целый альбом!
Среди цивилизаций в галактике на главном экране была и небольшая пасхалка. Буквально в последний день добавили одну из рас — Эндо. Добавили в ответ на дискуссию участников в чате дискорда, которые часто вспоминали персонажа из контеста 2007 года — инопланетяшку Эндо. У участников было много вариантов, как этого Энду прикрутить в текущую историю. И в последний день Саша быстро нарисовал этого персонажа и иконку. Народ порадовался, когда нашел его:
Про перевернутые картинки
Инопланетяне немножко знают про цивилизации, которые есть во вселенной. Например, о землянах они узнали, видимо, с пластинки на аппарате «Пионер». Это изображение иногда критикуют за то, что оно слишком земное. Например, как инопланетяне должны были узнать, где на этой картинке верх, а где низ? Поэтому ради шутки мы решили перевернуть эту картинку вверх ногами.
Из чата участников: 
Потом нас осенило, что можно пойти еще дальше и перевернуть вообще все в интерфейсе вверх ногами! Вот какая была логика. Изображения инопланетяне передают просто в виде последовательности пикселей, расположить эти пиксели сверху вниз придумали наши участники сами. Потому что у людей так принято: слева направо, сверху вниз. И ошиблись! Потому что у инопланетян принято не так. Конечно же, ось Y у инопланетян должна быть направлена вверх, к звездам. Как у математиков :) И пиксели логично (по-инопланетянски логично) было располагать тоже снизу вверх. Участники тоже поняли это, но переделывать никто не стал. На вопросы в чате «А почему все вверх ногами?» другие участники отвечали «Тут так принято!», «Так исторически сложилось» и «Лень переделывать». Все, как в жизни! Как мы и задумывали :)
Предлагаем вам трехминутную экскурсию по интерфейсу Галактики:
Инфраструктура
В прошлые годы во время участия мы всегда расстраивались из-за того, как сделаны системы сдачи решений: как правило нужно было собирать zip-файл, в котором лежали бы исходники, исполняемый файл и инструкция, как все это запускать. В 2020 году должно быть по-другому. Есть же автоматизированные CI/CD, можно все собирать по коммиту в репозиторий. Автоматически запускать в докере. И участникам не надо будет вообще ничего для сдачи делать, кроме обычного коммита в гит. Поэтому мы вложились в инфраструктуру очень сильно. Мы собирали коммиты из репозиториев команды, считывали из специального файла в репозитории, какой язык они используют, и запускали их код в подходящем докер образе. После сборки проводились тесты, и если все хорошо, специальная турнирная система запускала код в турнир: выбирала соперников и запускала игру друг против друга.
У участников был личный кабинет на нашем сайте, где можно было смотреть статусы сборки и логи, какие игры твой бот играл и результаты этих игр. Даже визуализация игры была. Динамически обновлялись результаты в лидерборде. Все данные приходили по вебсокетам, не требовалось обновлять страницу.
Наша инфраструктура была готова к большим нагрузкам. Мы проводили нагрузочное тестирование. Можно было увеличить количество ресурсов динамически при росте нагрузки. Для этого у нас была гибридная система из своего и дополнительного кластеров в AWS на случай большой нагрузки.
В общем, мы сделали то, что как промышленные разработчики умеем делать и не можем без удобства: сайт, CI/CD, гит, масштабирование.
Оказалось, что не все разделяют наши страдания. В обратной связи от участников мы получили два вида отзывов «Инфраструктура была идеальна, все просто работало, не тормозило, мы даже не обращали внимания на нее, так удачно она была сделана» и «Инфраструктура отвратительна! Вообще-то не все знакомы с гитом!». Первых, конечно, было заметно больше. Однако в любом случае мы рады, что несем современные технологии в массы и заставляем людей знакомиться с лучшими практиками :)
Никита Сивухин:
Я занимался техническими аспектами, делал интеграцию с «Амазоном». Оказалось, что там не все так просто и «Амазон» не может тебе дать неограниченное количество мощностей, даже если мы готовы за это платить. Но в результате все получилось. Мы добились почти максимального возможного параллелизма: время обработки одного раунда турнира было 2 минуты. Примерно столько же, сколько длился один бой между парой соперников.
Про 72 часа контеста на стороне организаторов
Большую часть времени мы получали удовольствие от происходящего. Последний месяц не спали по ночам и не отдыхали в выходные, разбирались с новыми интересными штуками, и это было весело.
Во время самого контеста у каждого из нас были 16-часовые рабочие дни все эти трое суток. Была договоренность, что круглосуточно в чате должен быть хотя бы один из команды. Так, у нас была техподдержка 24/3 и мы активно отвечали участникам и помогали решать их проблемы.
Попеременно кто-то уезжал домой, кто-то оставался. Кроме техподдержки, мы запускали и останавливали разные этапы турнира, записывали следующие видео, писали твиты и посты в блог, следили за инфраструктурой и иногда что-то допиливали в ней. Финальное видео записывали тоже в процессе контеста. Всего было 5–6 видео, из них только парочку мы записали до начала, остальное в процессе. Видео, открывающее контест, записывали в последний час перед стартом.
(Организаторы контеста за работой)
Было очень страшно за контест и тяжело в первые сутки: за необычный формат мы получили гору негодования от участников, ожидавших чего-то привычного. Когда начались бои между участниками, стало полегче, времени прибавилось и стало хватать на креатив. Например, запустили на твитче трансляцию реплеев лучших сражений между участниками.
И предложили участникам, у кого уже закипел мозг, посидеть отдохнуть и посмотреть трансляцию соревнования. Была еще идея кого-нибудь посадить и голосом Дмитрия Губерниева комментировать эти бои, но не стали.
(Иван Зайцев смотрит трансляцию и переживает за судьбу землян)
(кадр из трансляции: можно было подглядеть крутые стратегии. На картнке корабль защитника разделился на много-много маленьких корабликов и их траектории выглядят запутанным клубком)
Демо боя можно посмотреть в отчете победителей
Про зрелищность и атмосферу
У ICFPC есть проблема: топовым командам обычно выгодно до последнего держать в секрете свои лучшие алгоритмы и выкладывать их в последние 5 минут. Чтобы все думали, что у них нет хорошего решения, и у противников не было шансов проанализировать и подготовиться.
У нас была задача это поменять и замотивировать все команды выкладывать свое наилучшее решение как можно раньше. Поэтому система турнира у нас была многоступенчатой. Она была чем-то похожа на Кубок мира по биатлону. Там были этапы, и за каждый этап тебе давалось некоторое количество очков в зависимости от занятого места. И в конце в финал попадают топ-20 команд по сумме набранных очков за все этапы. Таким образом, командам нельзя было отсиживаться в тени до последнего, надо было зарабатывать очки, чтобы пробраться в финал. Получился в итоге зрелищный чемпионат.
Атмосфера соревнования была скорее дружеской: все обсуждали идеи, общались, подшучивали друг над другом. Например, мы изменили название постоянного участника ICFPC команды The Cat #1. Написали специальный код, который в лидерборде переименовывал название команды на текущее место, которое они занимают, например, место 12 и название становится The Cat #12. Это просуществовало часов 6, прежде чем ребята из команды написали в чат: «Эй, вы чего сделали название нашей команды динамическим?))) Вы клевые, нам понравилось!».
Каким получился для вас этот контест
Вероника Самохина (aminopyrodin): «Эпично сложным и необычным».
Леша Кирпичников: «Мы делали контест, в который понравилось бы играть воображаемой идеализированной версии нашей команды. Команде из 5 или больше промышленных разработчиков, которые готовы почти не спать и рубиться все 72 часа, но при этом команде из гораздо более умных и крутых участников, чем мы сами. Это и хорошо, и плохо: нам бы точно понравилось в это играть, но были и команды с другими ценностями, которым это совсем не зашло. В конечном итоге по-другому и быть не могло: вряд ли мы бы стали делать что-то, что не понравилось бы нам самим».
Саша Храмцов: «Максимально мозголомный, эпический и масштабный. Потому что история, которая за всем этим лежала, развернулась очень широко. Получилась настоящая история. Контест из виртуального превратился в настоящий».
Никита Сивухин: «Многогранный и продуманный. Было очень много точек взаимодействия и компонентов системы как снаружи, так и внутри».
Про планы
Отдохнуть. Очень много затрачено сил, все это ради фана и любви к искусству. На такое можно пойти раз в жизни, штамповать такое никто не готов точно. Сейчас надо рассказать про наш опыт, возможно, поделать доклады. Эй, организаторы конференций и программные комитеты, хотите, расскажем про что-нибудь подробнее?!
Победители
Main round, 1st place
Первое место в основном раунде получила команда Closed and Restricted Boltzmann Machine (denplusplus). Ребята лучше всех выполнили задание, писали на Python, играли под нейтральным флагом, потому что все выходцы из России, но живут и работают в разных местах западного побережья США.
Main round, 2nd place
Второе место заняли две команды из Японии: многократные победители ICFPC Unagi, которые писали на Rust, и команда японских студентов 182020, их язык программирования C++. Эти команды обе заняли одно место, потому что их алгоритмы хоть и были разными, но показывали практически одинаковую результативность в турнире: то одна, то другая команда выходила вперед. Мы не смогли их разделить по разным местам и дали обеим командам второе место.
Lightning Round
Команда powder — победитель lightning раунда. Этот раунд длится первые 24 часа: выигрывает та команда, которая добилась наибольшего прогресса за это время. В нашем случае они решили больше всех туториалов, обучающих, как вести космические бои. В составе команды четыре человека из разных стран. Ребята писали на языке Haskell.
Judges» Prize
Приз жюри получила команда ребят из Уфы WILD BASHKORT MAGES (ripatti). Они так увлеклись написанием виртуальной машины, запускающей галактику, что решили реализовать своих ботов для игры так, что они играли без реверс-инжениринга протокола игры (как делали большинство), а нажимая на экран галактики и распознавая изображения. Неэффективно, но впечатляюще. Использовали язык OCaml.
Закончить хочется вольным переводом с английского отзыва Максима Муратова, участника команды с призом жюри (отзыв был написан еще до получения приза :)):
Удивительно новое ощущение от контеста: обычно изо всех сил стараешься победить и в конце чувствуешь неудовлетворенность результатом, потому что он все равно ниже, чем ты ожидал. А тут у нас было одно из худших выступлений за все участие в ICFPC, но на душе прекрасно и удовольствие получено.
Что почитать дальше
Пройти путь участника соревнования и попробовать расшифровать инопланетные сообщения
Начать нужно вот с этой страницы. Скачать recording of this message и попытаться понять, что же имелось в виду.
Когда это получится сделать, можно переходить ко второму сообщению. В опубликованной документации уже все расшифровано, поэтому если хочется избежать спойлеров, скачивайте только картинки сообщений. Второе сообщение будет здесь —, а дальше можно увеличивать цифру в ссылке и получить все сообщения вплоть до 41-го. Сверить свои ответы с правильными можно в документации. Например, второе сообщение расшифровано здесь.
Чтобы отправлять сообщения инопланетянам, нужно воспользоваться нашим прокси-телескопом. Инструкция здесь.
Когда все сообщения до 41-го будут расшифрованы, попробуйте понять, что инопланетяне хотят от нас в главном 42-м сообщении.
Почитать книгу про реализацию функциональных языков программирования
Главная книга, которая помогала нам делать контест, — это The Implementation of Functional Programming Languages, которую совершенно бесплатно можно прочитать здесь
Буквально нескольких первых глав достаточно, чтобы достойно справиться с задачей, описанной в инопланетных сообщениях :)
Сразиться в космическом бою с другой командой
Если у вас получится расшифровать инопланетные сообщения и написать свою реализацию Галактики, вы наверняка захотите потягаться в космических боях с кем-нибудь другим, кто хорошо умеет это делать.
Мы оставили работающий сервер, на котором это можно сделать. Найти себе достойного соперника среди участников ICFPC можно в нашем дискорд-чате
