Прошло 49 часов с начала ICFPC 2018, сейчас расскажу, что происходило последние полтора суток.
От середины до конца 24-часового Lightning-раунда мы сделали несколько вещей: придумали абсолютно новую быструю стратегию для сборки моделей, оптимизировали написанную до этого надёжную и проверенную стратегию, настроили асинхронный запуск в облаке всех стратегий для решения всех задач и стали показывать результаты на красно-зелёной тепловой карте.
В итоге в концу Lightning-раунда мы смогли решить и сдать 185 задач из 187. Правда, всё это произошло уже после заморозки таблицы с лидерами для Lightning-раунда, поэтому мы не знаем, насколько высоко смогли подняться. За 6 часов до окончания Lightning-раунда мы были только на 32 месте из 42 команд, сдавших решения:
От середины до конца 24-часового Lightning-раунда мы сделали несколько вещей: придумали абсолютно новую быструю стратегию для сборки моделей, оптимизировали написанную до этого надёжную и проверенную стратегию, настроили асинхронный запуск в облаке всех стратегий для решения всех задач и стали показывать результаты на красно-зелёной тепловой карте.
В итоге в концу Lightning-раунда мы смогли решить и сдать 185 задач из 187. Правда, всё это произошло уже после заморозки таблицы с лидерами для Lightning-раунда, поэтому мы не знаем, насколько высоко смогли подняться. За 6 часов до окончания Lightning-раунда мы были только на 32 месте из 42 команд, сдавших решения:
В последний час Lightning-раунда мы буднично оптимизировали стратегии, получали и отправляли на проверку новые решения. Лениво обсуждали, какие могут быть изменения правил после окончания Lightning-раунда. По опыту участия в ICFPC прошлых лет, казалось очевидным и неизбежным, что теперь организаторы позволят участникам создавать задачи для других команд. Ваня Дашкевич @spaceorc был готов спорить, что всё так и будет.
Например, в ICFPC 2016 сначала было нужно решать оригами — разворачивать 2D-картинку сложенной фигуры оригами обратно в квадратный лист. А потом участники получили возможность создавать собственные сложные оригами, которые должны были решать соперники. Вот WYSIWYG-редактор, в котором создавала оригами команда The sound of lambda: https://www.youtube.com/watch?v=__fUHJFW4cc
Но всё пошло не так.
21 час назад закончился Lightning-раунд и обновились правила. К нашему удивлению, у наноботов, собирающих 3D-модели, появились новые умения. Раньше они могли делать тривиальные вещи:
— перемещаться по пространству двумя способами (переходит в соседнюю клеточку трёхмерного пространства или делать L-образный скачок, как шахматный конь),
— делиться надвое и соединяться обратно (в сборке модели участвовало от 1 до 20 ботов),
— заполнять клетку в пространстве материей.
Например, в ICFPC 2016 сначала было нужно решать оригами — разворачивать 2D-картинку сложенной фигуры оригами обратно в квадратный лист. А потом участники получили возможность создавать собственные сложные оригами, которые должны были решать соперники. Вот WYSIWYG-редактор, в котором создавала оригами команда The sound of lambda: https://www.youtube.com/watch?v=__fUHJFW4cc
Но всё пошло не так.
21 час назад закончился Lightning-раунд и обновились правила. К нашему удивлению, у наноботов, собирающих 3D-модели, появились новые умения. Раньше они могли делать тривиальные вещи:
— перемещаться по пространству двумя способами (переходит в соседнюю клеточку трёхмерного пространства или делать L-образный скачок, как шахматный конь),
— делиться надвое и соединяться обратно (в сборке модели участвовало от 1 до 20 ботов),
— заполнять клетку в пространстве материей.
Теперь максимальное число ботов увеличилось с 20 до 40. Они получили умение аннигилировать уже имеющуюся материю в клетке пространства. Это позволяло использовать совершенно недоступные ранее тактики — например, заставлять нанобота «выжигать» себе путь через уже построенную часть модели, в том числе выбираться из ситуаций, когда бот оказывался «заперт» внутри модели.
Но самое главное, что теперь ботам стали доступны групповые операции — коллективное заполнение пространства материей и коллективная аннигиляция. Для этого несколько ботов должны стать в углы пространственной фигуры, которую они хотят заполнить материей или аннигилировать. Два бота могут создать или уничтожить «линию» единичной ширины и высоты, четыре бота — «плоскость» единичной высоты, восемь ботов — кубоид. Вот как это выглядит в пространстве:
Но самое главное, что теперь ботам стали доступны групповые операции — коллективное заполнение пространства материей и коллективная аннигиляция. Для этого несколько ботов должны стать в углы пространственной фигуры, которую они хотят заполнить материей или аннигилировать. Два бота могут создать или уничтожить «линию» единичной ширины и высоты, четыре бота — «плоскость» единичной высоты, восемь ботов — кубоид. Вот как это выглядит в пространстве:
Но это было не всё. Кроме уже привычных заданий «собери модель» появились задания «разбери модель» и «пересобери из одной модели другую»! Это было неожиданно.
На самом деле в Lightning-раунде были жирные подсказки на такие изменения, но мы были не способны их заметить. Например, модели для сборки в Lightning-раунде назывались «LAxxx_tgt.mdl», а решения (инструкции по их сборке) назывались «LAxxx.nbt».
На самом деле в Lightning-раунде были жирные подсказки на такие изменения, но мы были не способны их заметить. Например, модели для сборки в Lightning-раунде назывались «LAxxx_tgt.mdl», а решения (инструкции по их сборке) назывались «LAxxx.nbt».
«LA» означало «Lightning Assembly», а «tgt» — «target». Закономерно, после изменения правил появились модели «Full Assembly» и «Full Disassembly», а также пары моделей «Full Reassembly» в двух вариантах — «source» и «target»:
Осознав изменения в правилах, мы последовательно прошли через стадии принятия неизбежного. Изменения очень плохо ложились на уже разработанные нами стратегии, поэтому в первую очередь хотелось заявить «ну, это нелепо» и откинуться на спинку кресла. Потом поняли, что не произошло ничего фатального — делать «сборку» мы умеем, «разборка и сборка» сводятся с разборке любым способом (например, групповой аннигиляцией) и сборке каким-нибудь из тех, что уже нам известны.
Наконец, начали думать над конструктивным развитием стратегий. Поняли, что надо уходить от стратегий в ключе «бот 1, перейди к соседней клетке и заполни её». Решили формулировать стратегии примерно так: «бот 1, нарисуй в области X вот такую часть модели; если хочешь — делись пополам и сам командуй своими потомками». Так можно создать примитивы, из которых уже составлять высокоуровневые стратегии: «разборка вон той части модели», «сборка выступающей части модели до финального состояния», «возвращение на исходную позицию».
Для этого была нужна новая архитектура. Ваня @spaceorc и Андрей @kostousov за работой над ней под присмотром Паши @xoposhiy:
Наконец, начали думать над конструктивным развитием стратегий. Поняли, что надо уходить от стратегий в ключе «бот 1, перейди к соседней клетке и заполни её». Решили формулировать стратегии примерно так: «бот 1, нарисуй в области X вот такую часть модели; если хочешь — делись пополам и сам командуй своими потомками». Так можно создать примитивы, из которых уже составлять высокоуровневые стратегии: «разборка вон той части модели», «сборка выступающей части модели до финального состояния», «возвращение на исходную позицию».
Для этого была нужна новая архитектура. Ваня @spaceorc и Андрей @kostousov за работой над ней под присмотром Паши @xoposhiy:
Получилось вот что: стратегии составляются из примитивов и комбинируются друг с другом с использованием модели fork-join. Каждый бот имеет задание, обладает ресурсами для его выполнения (возможность делиться на части) и умеет оценивать текущую ситуацию (степень готовности модели, своё положение в пространстве, недоступные для перемещения из-за других ботов области пространства).
Бот может выбрать примитивную стратегию для выполнения задания (например, двигаться к нужной клетке и заполнить её), а может разделиться и выдать задание своим потомкам (например, двигаться к вершинам кубоида, чтобы выполнить групповую операцию заполнения). Потомки будут выполнять задание самостоятельно, зная свои ресурсы и оценивая ситуацию. При этом стратегии отдельных ботов работают не только независимо друг от друга, но и асинхронно.
Вот реакция Паши, когда всё было готово:
Бот может выбрать примитивную стратегию для выполнения задания (например, двигаться к нужной клетке и заполнить её), а может разделиться и выдать задание своим потомкам (например, двигаться к вершинам кубоида, чтобы выполнить групповую операцию заполнения). Потомки будут выполнять задание самостоятельно, зная свои ресурсы и оценивая ситуацию. При этом стратегии отдельных ботов работают не только независимо друг от друга, но и асинхронно.
Вот реакция Паши, когда всё было готово:
Параллельно с работой над новыми стратегиями мы автоматизировали рутинные операции по оценке качества наших решений. Например, сделали обновляемую ежеминутно таблицу с информацией о том, насколько хорошо каждая из наших стратегий решает каждую из задач. Вот так выглядели верхние 10 % таблицы в конце Lightning-раунда:
Сейчас в ней появились новые задачи (602 штуки) и новые стратегии (пока 21), а также получаемая из организаторской таблицы лидеров информация о том, насколько наши лучшие решения отстают от решений других команд.
Чтобы ещё удобней было наблюдать за телеметрией, Лёша @beevee_ru придумал показать наши визуализаторы и дашборды на большом телевизоре и поставить его рядом. Даже пошли на другой этаж офиса за большой стойкой с двумя телевизорами, но идея разбилась о суровые ограничения физического мира — стойка не прошла по высоте в лифт:
Чтобы ещё удобней было наблюдать за телеметрией, Лёша @beevee_ru придумал показать наши визуализаторы и дашборды на большом телевизоре и поставить его рядом. Даже пошли на другой этаж офиса за большой стойкой с двумя телевизорами, но идея разбилась о суровые ограничения физического мира — стойка не прошла по высоте в лифт: