swizard (swizard) wrote,
swizard
swizard

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

Ну что, успешно упоролись свежим 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 можно почитать тут.
Tags: cthulhu, fhtagn, icfp, icfpc, icfpc 2015, report
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 20 comments