ICFP 2015 ((ктулху фтагн))

[swizard]

Ну что, успешно упоролись свежим icfpc в этом году, спасибо всей команде за участие, было весело!
Репо солюшна вот здесь: https://bitbucket.org/skobochka/icfpc-2015/overview

По результатам всё традиционно: тонны кода, дичайший недосып, часы дебага наитупейших ошибок, сорванные в последние минуты дедлайны, страшнейшие факапы за мгновение до окончания раундов, и невероятные озарения спустя пятнадцать минут после. Собственно всё то, за что мы все этот конкурс так ценим :)

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

В итоге, историю я фактически угадал, но вспоминать криптографию и программировать квантовые компьютеры было не надо.

Собственно, задачу копипастить мне лень, надо читать введение от оргов (оно стоит того) и спеку (всё кратко и понятно).

А развёрнутая ретроспектива событий получилась какая-то такая (восстановлено по логам конфы):

Пятница.

• За пять минут до старта контеста я ушёл к стоматологу, и задание пытался читать краем глаза уже из-под бор-машины :)
• Вернулся через час, все участники пока осознавали правила. Но sectoid уже освоил самбишн решений.
• Ещё через полчаса я решил развести бюрократию в виде плана действий в корне проекта. Чтоб типа всё как у взрослых: разные подзадачи, там, каждый выбирает себе что-то и закрепляет за собой. Изначальная идея была в том, что в команде уже 5 человек, поэтому нужна какая-то минимальная координация.
• Но через некоторое время актуальность предыдущего пункта резко упала, потому что grepz снялся с конкурса по уважительным причинам, и нас осталось четверо.
• Далее наступил какой-то ад: уже через полтора часа после начала контеста на доске почёта какие-то команды стали зарабатывать по 600000 очков и выше. Меня в этот момент начала мучать лёгкая паника.
• turtle отправился делать генератор случайных чисел.
• sectoid и jtootf оказались знатоками Лавкрафта, и моментально нашли фразу власти из 51 символа: Ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn! Лол, как выяснилось в последний день, вместо восклицательного знака нужно было ставить точку :)
• 17:30 - мы с turtle всё ещё мучаем ГСЧ.
• Доску почёта продолжает нещадно колбасить -- орги, как обычно, правят баги "по-живому". Кому-то снимают очки, у кого-то, наоборот, они рандомно зарабатываются сотнями тысяч.
• 18:15 - sectoid принёс нам первые очки вручную сфабрикованным решением.
• 18:45 - у нас всё ещё нет никакого кода, мы лениво прикидываем, кто чем бы хотел заняться.
• 19:10 - всё ещё никакого кода, но jtootf нашёл какой-то симулятор гексо-тетриса на тикле, и решил на его основе сделать визуализатор.
• 19:30 - появился первый код: sectoid написал сабмитилку, а я сделал базовый скелет проекта, структуры данных и загружалку входных данных.
• План на лайтнинг я на тот момент видел так: надо строго сделать всю сопутствующую мелочёвку (карту, фигуры, координаты, движение / вращение, проверка валидности всех положений, спавн новых фигур), написать какой-нибудь колхозный брутфорс для нахождения места, куда надо уложить появляющуюся на поле фигуру, и реализовать базовый A* для построения скрипта команд с какой-нибудь простенькой эвристикой. Ну и какой-никакой транслятор команд.
• Далее задачи распределилсь так: sectoid отправился реализовать движение и вращение фигур, а я всё остальное :) turtle допиливал ГСЧ, а jtootf взялся сделать визуализацию.
• 20:10 - орги, наконец-то, справились со своей доской подсчёта, и она стала выглядеть по-человечьи, без многосоттысячных результатов у каких-то рандомных бомжей.
• Решаем с sectoid'ом в трансляторе команд реализовать микрооптимизацию: если вдруг каким-то магическим образом собралась последовательность, соответствующая заклинанию, то заменять её на заклинание (мощная идея, правда?).
• 21:00 - орги пригрозили, что любые команды в скрипте, которые воспоследуют после того, как игра будет закончена (на карте не останется валидных мувов), то решение аннулируется с нулём очков. Так вот, куда пропали все лидеры из рейтинга ;)
• turtle отправился писать Makefile для проекта, а я к этому моменту изобразил какой-то нищебродский A*. Проблема была в том, что пока не было механики вращения и движения фигурок, поэтому его не на чем было отлаживать. Поэтому я пошёл писать какое-то крайне позорное, но быстрое решение для поиска места, куда следует класть порождённую фигуру. "Стратегия" такая: запихнуть фигуру максимально низко в стакан, прижать максимально сильно к левому краю, повернув таким образом, чтобы справа осталось максимум места. Лол, конечно, но нужно было иметь хоть какую-то реализацию, нежели не иметь никакой.
• 21:00 - jtootf тем временем спрограммировал на тикле какой-то рендерер гексагонального поля, и поехал домой.
• То же самое порывался сделать sectoid, но потом передумал, решив сначала добить фигурки. Хех, как он ошибался.
• Выясняется, что координатная сетка на поле не для щенков. Чётные ряды сдвинуты в право относительно нечётных, поэтому оперировать координатами в терминах (row, column) невероятно мучительно. Сами фигуры задаются при этом относительно своей локальной системы координат.
• Я сходу порождаю очередную бомжацкую идею: давайте перейдём от описания фигуры в терминах пивот + списка координат её ячеек к такому виду: сдвигаем пивот в (0,0), а все ячейки кодируем последовательностями команд движения, которые надо выполнить, чтобы попасть в них. К счастью, меня не поддержали.
• 23:00 - у нас всё ещё пока нихрена нет. Sectoid таки поехал домой.
• Судя по лидерборду, народ где-то нашёл уже готовые тетрисовские солверы и адаптировал их под задачу. Опять приступ паники :)
• 00:00 - sectoid приехал домой, и мы дальше взмыленно обсуждаем, как правильно быть с координатами.
• 00:30 - всё ещё обсуждаем.
• 00:45 - всё ещё обсуждаем.
• 00:48 - turtle внезапно обнаруживает, а я внезапно читаю материал по этой ссылке, на которую sectoid уже несколько раз ссылался. Оказывается же можно использовать кубические координаты. Мало того, sectoid их уже использовал для поворота, лол.
• Короче, переходим на кубические координаты. Жизнь снова заиграла красками. А для доступа к полю преобразовываем их обратно.
• Бла-бла-бла.
• 01:40 - готовы движения и повороты фигур! Я бросаюсь доводить A* и выбор цели для фигуры, turtle программирует сгорание рядов при заполнении, sectoid пошёл делать транслятор скрипта движений.
• 03:00 - у меня заработал поиск пути, который стало возможно транслировать. Приступил потихоньку к поиску позиции для фигуры.
• 03:20 - sectoid берёт таск про спавн фигур (согласно заданию, их надо центрировать), turtle делает бинарь с поддержкой cmd args. У меня в этот момент очередная тупая проблема с тем, как сравнивать две фигуры на доске на эквивалентность (сортировать и сравнивать список ячеек долго, хочется быстро).
• 03:49 - jtootf напрограммировал базовый визуализатор, но пока непонятно как кормить его данными.
• 04:23 - я спрограммировал брутфорсный выбор позиции (на отъебись, конечно, но как-то он заработал).
• 04:30 - у sectoid тем временем затык со спавном: фигура никак не хочет правильно центрироваться.
• Чем позже становится, тем всё происходящее происходит всё медленнее и медленнее :) На какие-то элементарные вещи тратится непонятная куча времени.
• 05:00 - первый код в game-loop.
• 05:27 - на правах местного оракула, произношу пророчество:
  • swizard: подозреваю, что щас будет как-то так:
  • swizard: мы сделаем решение, засабмитим, и получим 0 очков
  • swizard: и далее надо долго дебажить что не так
• 05:35 - делаю первый пуш кода game-loop.
• Внезапно обнаружил, что не хватает сжигания рядов. Вроде turtle делал.
• 05:45 - сжигание рядов есть, но не работает. Быстренько пишу консольный визуализатор, чтобы хотя б видеть что происходит.
• 06:00 - сжигание рядов всё ещё не работает.
• Тем временем, jtootf находит на картах подсказки-заклинания: R'lyeh и Yuggoth.
• 06:12 - сжигание рядов всё ещё не работает. Да что ж такое-то.
• 06:24 - пока turtle ремонтирует сжигалку, я не выдержал и написал параллельную версию, чтобы общий процесс разблокировался, и можно было что-то делать дальше.
• 06:24 - оказывается, sectoid тоже психанул и написал свою версию сжигателя рядов :) Итого у нас три имплементации одного и того же.
• 06:37 - ура, есть наконец решатель! Натравливаем его на все доступные таски.
• 06:48 - разумеется, баги. Эксепшны, выходы за границы массива, и прочая срань. Ремонтировать баги в семь утра тоже тот ещё кайф :)
• 06:59 - победили, есть 800 жалких очков на первой карте! На остальных, правда, нуль, ну да и чёрт с ним. Зато можно с чистой совестью идти спать.
• 07:10 -- делаю крестьянскую визуализацию на базе репла и (break) чтобы воочию понаблюдать перед сном за падающими фигурками. Наблюдаю, и иду спать.

Суббота

• 11:45 - подъём =) Пробуем взять лайтнинг.
• 11:55 - начинаем сеанс багфиксинга. Надо понять за что нам везде ставят нуль баллов.
• 12:00 - я начинаю лихорадочно делать покадровый вывод игры, чтобы его можно было скормить визуализатору имени jtootf.
• 12:26 - запушил возможность записи и вывода фильма в процессе игры. Прошу sectoid'а конвертнуть вывод в какой-нибудь json, чтобы jtootf мог его подхватить. Сам сел фиксить производительность солвера.
• 12:38 - ускорил решение в три раза, сел дебажить решение глазами через свой крестьянский визуализатор, который брейками :) Не вижу никакого криминала, игра идёт б/м корректно.
• 12:53 - sectoid тем временем никак не может совладать с cl-json, чтобы получить корректный выхлоп. В итоге отказывается от таска =) Я забираю обратно.
• 13:12 - что-то тоже обламываюсь сходу с cl-json, плюс ещё какая-то мелкая срань навалилась. А ведь основная проблема-то -- починить 0 очков на карте.
• 13:32 - побеждаю cl-json и часть мелкой срани. Всё ещё непонятно, почему 0 очков.
• 13:45 - выпиливаем из зависимостей lift =) Который год уже пытаемся писать какие-то юнит-тесты, и каждый раз облом. Не до них, код слишком быстро меняется и вообще устаревает.
• 13:54 - втыкаю в визуализатор, в упор не понимаю, что системе не нравится в нашей игре. На вид всё замечательно.
• 14:03 - пошагово сравниваем наше решение с видео с игрой, которое выложили орги. Порядок выпадающих фигур правильный, фиксирующие ходы (freezing moves) в порядке. Всё ещё непонятно, где засада.
• 14:26 - turtle изучает игру дальше, я занимаюсь какой-то ерундой. Что-то ускоряю, где-то что-то переделываю.
• 14:45 - отчаиваемся, сабмитим к лайтнингу решение, которое у нас уже есть. Которое с нулём очков.
• 14:53 - выясняется, что на 6 задаче у нас аж три с половиной тыщи очков. Значит, на каких-то конфигурациях оно всё же работает :)
• jtootf: "ну да, мы всё-таки на три места выше команды DNIWE ;)"
• 14:58:27 - turtle находит этот долбанный баг! Косяк со спавном фигуры -- она появляется не в том месте, где это оговорено правилами. У нас целых полторы минуты на его исправление =)
• 15:00 - лайтнинг успешно просран.
• 15:05 - новый план: отремонтировать баг, начать стабильно получать очки, и идти досыпать.
• 15:30 - sectoid ремонтирует свой код, а я, по-традиции, параллельно пишу свою версию его же.
• 15:33 - sectoid починил код, я написал свою версию. Сравниваем -- ни тот ни тот не работает как следует =)
• 15:44 - sectoid повторно починил свой код, а я, в свою очередь, починил свой. На первый вид оба работают, но оба не всегда.
• 15:45 - turtle пошёл в баню.
• 16:08 - я вроде отладил свой вариант спавна, сходу ошибок больше не нашёл. Осваиваю сабмит, чтобы сделать проверку.
• 16:54 - наконец-то не ноль в лидерборде! Sectoid тем временем добил свою версию, и порывается тоже засабмитить, но я предлагаю сначала прогнать всё на всех картах и тупо сравнить ответы двух наших спавнилок.
• 17:01 - проверка обломалась :)
• 17:25 - разобрались, косяк на моей стороне =) В честной борьбе побеждает sectoid, его решение уходит в game-loop.
• Всё, сабмиты пошли, расходимся по своим делам (моё дело -- вздремнуть пару часов).
• 18:00 - 20:30 - перерыв на сон и ужин.
• Тем временем, у нас уже три заклинания, помимо того, что дали в задании: Ia! Ia!, R'lyeh и Yuggoth.
• 21:00 - начинаю вяло читать всякие ссылки про тетрис и искуственный интелект в нём.
• Параллельно меня опять "осеняет" (прямо сезон откровений), что мы, в отличие от классического тетриса, знаем всю игру наперёд - какие и когда будут выпадать фигуры.
• jtootf тем временем регулярно накидывает разные ссылки на разные материалы по теме.
• sectoid неспеша пытается набрутфорсить больше заклинаний.
• И только к 21:45 я начинаю заниматься чем-то полезным: перетряхивать свой A*, чтобы он научился пользоваться заклинаниями для переходов по графу.
• jtootf с sectoid активно вспоминают лавкрафта в поисках новых заклинаний, а я отвлёкся на какую-то ерунду в плане фикса производительности.
• Примерно в 22:30 часть народа разошлось спать, часть куда-то подевалось, я остался один. Разговаривал сам с собой в конфе =)
• 01:39 - я спрограммировал поддержку заклинаний в A*. Попробовал засабмитить, но из-за какого-то бага на борде мне показало 0 слов силы, хотя очки засчитали.
• В конфе появился jtootf, вовремя, а то я уже устал сам с собой разговаривать.
• 01:45 - Тем временем мой солюшн стал потихоньку набирать очки. Команда в общем зачёте поднялась на 38-е место.
• 01:56 - 33 место.
• 03:00 - 24 место в турнирке!
• 05:00 - 8-е место на нулевой карте, 19 место в общем зачёте.
• 05:32 - 13-е место в общем зачёте.
• 05:40 - я отваливаюсь спать на рекорде: 11-е место в общей турнирке.

Воскресенье

• 13:20 - врываюсь в игру.
• Потихоньку собираюсь с силами начать нормальный солвер. Параллельно прощупываю почву, не хочет ли кто-нибудь спрограммировать его вместо меня =)
• 13:30 - sectoid там понаэкспериментировал с разными кандидатами в заклинания, в итоге одно добавилось, одно забраковалось (R'lyeh). Какое-то время я разъясняю ситуацию с багом на лидерборде, в итоге ръльех реабилитирован :)
• turtle тем временем в процессе делает распараллеливание обсчёта разных seed-ов в game-loop, чтобы они играли независимо на разных ядрах.
• В процессе у меня ломается сборка, и я начинаю активно ныть в конфу о необходимости ветвиться. Sectoid активно поддерживает, turtle активно сопротивляется :)
• 14:00 - на борде нам, наконец, зачли все 4 заклинания. Починили багу походу.
• 14:20 - turtle пушит параллельный game-loop.
• 14:41 - я сходил позавтракать, возвращаюсь -- а солвер всё ещё никто не пишет =) Ладно, сел программировать, решил для начала закодить вот этот вариант.
• 15:09 - понабежал sectoid с идеей, что можно собирать одно длинное заклинание из ходов нескольких фигур.
• Чуток пообсуждали идею: в целом, мне, например, всё понравилось, но я просто совсем хз как это ровно закодить. Надо же, получается, как-то тащить контекст через ходы всех фигур, включая "freeze move" - ход, который лочит фигуру. Он, получается, тоже должен участвовать в общем деле.
• 15:30 - я мучаю солвер, sectoid пишет тулзу для jtootf для упрощения поиска новых заклинаний.
• 16:30 - я сделал estimator, который берёт поле и фигуру и оценивает позицию. Привинтил к визуализатору и запряг turtle оценить вменяемость скоринга.
• Сам в это время сел делать брутфорсный поисковик позиций для нужд дебага. Суть токова: перебрать нахрен все клетки карты, и в каждую клетку попробовать запихнуть текущую фигуру. Если не получается, повращать её и опять попробовать запихнуть. Для всех мест, куда удалось запихнуть, собрать estimate score и запомнить позицию с максимумом. Короче, самый что ни на есть bleeding edge мировой науки, и вот это всё =)
• 17:00 - turtle даёт добро на estimate.
• 17:30 - мержу солвер в мастер и ухожу обедать. Sectoid тем временем сел писать расчёт официального скоринга.
• 18:00 - пустили параллельный обсчёт и сабмит всех задач на борду с новым солвером.
• turtle тем временем забрал солвер себе и пошёл экспериментировать с весами разных факторов.
• 19:06 - досабмитились решения: 18 место в зачёте.
• sectoid пошёл делать генетический алгоритм для автоматического подбора весов факторов.
• 19:25 - jtootf вбрасывает в конфу линк на алгоритм "Iterative deepening A*", а я этого не заметил :( Блин тока щас по логам увидел, жесть. Это же верное направление.
• 19:40 - начинаем с turtle классический вялотекущий срач по поводу гигиены разработки (не трогать грязными руками мастер, если собираешься всё ломать).
• 20:05 - заканчиваем срач.
• Я опять закопался в производительность.
• 21:10 - sectoid добил ГА, подобрать нормальные коэффициенты не удалось :(
• Я тем временем ради интереса выполнил поиск на гитхабе по ключевому слову "Yuggoth" и нашёл ненулевое количество открытых репо, в которых были файлы с заклинаниями =) Запустили проверку по всем тем, которых у нас не было, но облом -- это всё не заклинания.
• 22:00 - ищем по инерции ещё заклинания.
• до 23:00 занимаемся какой-то ерундой. Sectoid дописывает скоринг (не работает), я пробую чуток улучшить генерацию freeze move, чтобы оно, по-возможности, заканчивало заклинание, а не просто лочило фигуру. Заодно проверил, что будет, если эвристику расстояния до цели в A* развернуть обратно: стараться выбирать наиболее длинные маршруты (в надежде, что в маршруты влезет больше заклинаний). Ничего не вышло.
• 23:00 - прошу turtle собраться, взять свои руками выставленные коэффициенты, свой новый фактор, и довести решение до рабочего состояния, чтобы можно было объективно сравнить с тем, что есть. Если будет явное улучшение - заменим.
• 00:03 - устал чёто сильно, пошёл погулять.
• 01:24 - вернулся, врываюсь обратно.
• Пока гулял, подумал, что целесообразно нарыть в инете какой-нибудь словарик по вселенной лавкрафта, и тупо зарядит батчем на нулевую карту. Если 0 - весь батч выкидывается, если не ноль - ура, в этом батче есть заклинание.
• Параллельно привычно слазил на гитхаб, посмотреть, как там дела у конкурентов (да, я подлый, знаю). Принёс в берлогу добычу: заклинание Yogsothoth :)
• На этой оптимистичной ноте стартовала очередная итерация массовой рыбалки на предмет заклинаний.
• 02:33 - sectoid разгадал подсказку оргов про "Conway. Cocke. Hopcroft. Backus.", итого +1 заклинание: John Bigboote.
• 02:55 - вылавливаем ещё одно заклинание: tsathoggua
• 03:07 - вылавливаем Planet 10
• 03:10 - я пытаюсь найти подсказки в картах. На 24-ой карте обнаруживается закладка: выпадающие в процессе игры фигурки складываются в строку: icfp2015 :) Я уж думал, что это заклинание, но нет.
• 03:17 - решаем заканчивать на сегодня: собираем все наши найденные заклинания, и запускаем два раза сабмит всех карт: один раз решателем из мастера, второй -- решателем с коэффициентами от turtle. Конечная идея заключается в том, чтобы выбрать лучший вариант.
• 03:20 - не, не заканчиваем, рыбачим дальше =)
• 04:06 - turtle, а затем и пришедший ему на помощь sectoid больно бьются об рандомное поведение dymanic variables в кл при использовании в бинаре и с тредами.
• 04:30 - проблема решена. Но какая-то новая проблема у turtle с бинарём.
• 04:40 - нет, проблема не решена =) Я пока от безысходности снова ухожу в профилирование.
• 05:30 - наконец всё работает, turtle сабмитит оба варианта решений.
• 05:44 - какие-то результаты для сравнения. Нуууу, так - где-то получше, где-то похуже, но в общем поровну примерно.
• Короче, решаем, что мейнстримом теперь будут параметры turtle, и вмерживаем в мастер. Финальный сабмит, и идём спать. Я лично уже физически валюсь с ног.
• 06:10 - ложусь физически в кровать и какое-то время сонно размышляю, что нам делать с 24-ой задачей - она слишком здоровая, наш солвер её никогда в жизни не обсчитает. В этот момент меня озаряет, и я чётко понимаю, что я осёл =) Ну конечно же, надо искать позиции тем же самым A*, которым я ищу маршруты, потому что это банальный BFS traversal, и ему можно тривиально ограничить глубину просмотра. А при обходе графа тупо оценивать каждую позицию текущим нашим estimate, и трекать лучший результат. В итоге, на больших картах алгоритм сможет всегда находить решения, пусть иногда и неоптимальные по эвристикам, но неплохие.
• 06:30 - не выдерживаю, беру ноут и начинаю программировать прямо в кровати - вставать уже сил нет никаких. Параллельно произвожу мощный рефакторинг, и, в итоге, ближе к 10 утра (когда сел ноут) у меня есть решатель в бранче a-star-forever, который умеет быстро решать большие карты номер 14 и 24. На обычных он, правда, даёт результат хуже, чем текущий солвер в мастере, но я надеюсь после 12 дня его настроить.
• 10:00 - засыпаю, наконец.
• 12:00 - просыпаюсь, врываюсь в игру.
• Вкрадце рассказываю о новом решателе, и мы садимся его настраивать.
• 12:15 - расчехляем ГА имени sectoid, и пытаемся улучшить коэффициенты факторов.
• 12:30 - у turtle падает инет, у меня тоже падает инет, разваливается конфа, начинается разнообразная возня с резервными каналами, etc. Как всегда, всё крайне вовремя :)
• Дальше полноценных логов конфы нет, потому что часть общения переместилась то в обычный джаббер, то в скайп, и в итоге мы как-то собрались в скайповой конфе.
• Ближе к 14:00 удалось подобрать неплохие коэффициенты для солвера a-star-forever
• После 14:30 внезапно выяснилось, что у меня там какой-то баг, из-за чего использование заклинаний приводит к невалидному решению с нулём очков. Ремонтировать уже некогда, поэтому мы откатываемся на вариант в мастере.
• И, под самый финал, на сладкое, я неожиданно совершаю косяк и случайно затираю сабмит 14-й задачи в рейтинге. Пересчитать мастером мы её уже не успеваем (результата надо ждать пару часов), поэтому в конце контеста наша команда резко проваливается на 57-ю позицию =)

Ну вот как-то так, в целом. Было занимательно, ещё раз всем огромное спасибо! Выводов на этот раз нет, какой в них смысл, всё равно им не следуем :)

Отчёт turtle можно почитать тут.