ICFPC-2018
2018-07-25 07:01 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
dastapovВ этом году ICFPC был про футуристическую 3D печать.
Коротко задачу можно описать так:
Вам дается описание 3d-модели, составленой из кубиков одинакового размера. Все кубики или стоят на земле или одной из сторон соединены с каким-то другим кубиком. У вас есть "нанобот", который может перемещаться в пространстве (наплевав на гравитацию) и "печатать" кубики в непосредственной близости от себя. Кроме того, от бота можно "отпочковать" нового бота (и так до 20 штук) и кроме того, можно временно "включить антигравитацию" в зоне печати, и тогда кубики, не прикрепленные к чему-то, будут висеть в том месте, в котором их напечатали. При отключенной антигравитации висящие в воздухе кубики считаются фатальной ошибкой и вызывают завершение программы.
Зона печати - это куб со стороной R, от 20x20x20 до 250x250x250 в зависимости от модели. Все операции с ботами имеют какую-то цену в виде затрат воображаемой "энергии", причем цены варьируются от 1-15 единиц за перемещение бота в пространстве до 30*R*R*R за каждый "ход" (в рамках которого каждый бот выполняет одну операцию) при включенной антигравитации. Ваша задача - свести затраты энергии на печать конкретной модели к минимуму.
Вам дается описание 186 моделей, и "стандартная программа печати" для каждой из них. "Стандартная программа" всегда одинакова - включаем антигравитацию и ездим одним ботом туда-сюда "змейкой" по всем клеткам на высоте 1, 2, 3 ..., печатая кубик непосредственно под ботом (если он там должен быть). В конце обхода антигравитация выключается и бот возвращается в (0,0,0) -- вернуться "домой" было необходимо по условиям соревнования.
Понятное дело, что на это уходило громадное количество энергии - для моделей 200х200х200 каждый ход стоил 240 миллионов единиц энергии из-за дополнительных расходов на антигравитацию, а ходов могло быть несколько десятков тысяч...
Отдельно стоит упомянуть структуру программы для печати, которую вы должны были сформировать. Программа - это простая последовательность команд без каких-либо возможностей ветвления, организации циклов и т.п. У каждого бота был уникальный идентификатор (число от 1 до 20), и на очередном ходу каждый бот по порядку (по возрастанию ID) получал из последовательности команд в программе рвно одну инструкцию и выполнял ее.
Для меня первый день начался в 17:00 по местному времени, но освободился я только к 18:00.
Организаторы любезно предоставили визуализатор моделей и визуализатор процесса печати, но они были написаны на JS. Я JS только читаю (со словарем), и мне не очевидно, можно ли найти способ запускать визуализаторы из командной строки, а не через форму в браузере. Писать свой (нетривиальный) визуализатор - это по опыту прошлых лет почти всегда время, потраченное впустую.
Учитывая, что все входные форматы были бинарными (и все, что можно, было в них представлено наименьшим количеством бит), то первым делом я написал декодер и энкодер для програм, а так же код, который считает общее количество энергии, затраченное программой -- чтобы меньше зависеть от организаторов и их кода, который я мог запустить только в браузере.
Поиск оптимальной программы для печати был, очевидно, NP-полной задачей и хорошие эвристики для нее были мне неизвестны. Но по по опыту в lighning round зачастую побеждает тот, кто "берет больше, кидает дальше и продолжает кодить, пока оно летит", а не тот, кто придумал самый классный алгоритм. В результате я реализовал первое, что пришло в голову - берем программу тупой печати, предоставленную организаторами, и слегка ее оптимизируем. Вместо того, чтобы отключать гравитацию в самом начале, будем проверять, будет ли к чему-то прикреплен следующий печатаемый кубик, и если нет - то включим антигравитацию, напечатаем кубик и постараемся отключить ее как можно скорее.
На этом месте часы показали 0:50, и я пошел спать. Отослать решения можно и завтра -- тем более, что я еще даже не прочитал о том, что и как надо засылать.
Так как я "сова", то на второй день утром я сладко спал. Проснувшись, я выловил несколько мелких багов, поразмышлял о том, что делать дальше и наконец-то сгенерировал решения для всех имеющихся задач, собрал архив с решениям и отослал его. На часах было 11:18. Тем временем организаторы сказали, что за 6 часов до окончания lightning они отключают обновление таблицы с результатами, и я опоздал на 18 минут :)
Своей позиции в lightning я в результате не знаю.
Следующим очевидным шагом на выбранном мной пути было продолжать оптимизировать тупую программу для печати. Напомню, что тупая программа была последовательным обходим всего объема печати с помощью перемещений бота на одну соседнюю клетку, перемежаемая командами печети кубика. Если зона печати была большой, а модель - мелкой, то большую часть времени бот планомерно "утюжил" пустое пространство по одной клетке за раз, тратя на это кучу времени и энергии. Естественно было бы пропускать все ненужные перемещения и передвигаться к следующему печатаемому кубику наиболее оптимальным образом. Плюс, естественно, включать антигравитацию (командой Flip) только тогда, когда без нее было никак.
Где-то к 15:00 я заслал все оптимизированные таким образом решения. До конца lighning было еще два часа, но я решил, что больше я ничего радикального не придумаю, и сел писать декодер описания модели из бинарного файла. В процессе я понял, что если кубики находятся по соседству, то можно переместиться к первому из них, и, никуда не сдвигаясь, напечатать и соседний (или может даже несколько). Это, как мне кажется, и было финальным вариантом решения, отправленного на момент окончания lighning round.
Дальше я сел писать свою реализацию обхода модели. Идея была в том, что если я придумаю, как обходить модель более-менее оптимальным способом (например, чтобы не нужно было использовать антигравитацию в принципе), то дальше можно было бы думать, как разделить модель на части, и построить каждую часть отдельным ботом.
Со старта, естественно, надо было идти к ближайшему опирающемуся на что-то кубику, который, естественно, мог быть только из самого нижнего слоя. Дальше начинались варианты - можно было забираться вертикально вверх и строить "столб" поверх этого кубика, или можно было идти в ширину, или комбинировать движения вверх и в сторону, учитывая что бот мог построить до 18 кубиков вокруг себя, не сходя с места.
За этими экспериментами незаметно подошел к концу lightning round.
По окончании lightning организаторы опубликовали изменения к условию задачи - максимально возможное количество ботов увеличилось до 40, и боты получили возможность коллективно строить группы кубиков за один ход. Два бота могли построить "отрезок" из кубиков (длиной до 30 штук). Четыре бота, расположенных по углам, могли построить прямоугольную "плитку". Восемь ботов могли построить параллелепипед (с длиной стороны, опять таки, до 30 кубиков). Затраты энергии на рисование были совершенно такими же, как при рисовании поштучно, но зато можно было нарисовать много кубиков за один ход. Кроме того, была добавлена команда Void, позволяющая разрушать кубик и превращать его обрано в энергию, и групповые варианты команды Void, аналогичные описаным выше.
Все это я поначалу пропустил, так как пытался продолжать оптимизировать свой алгоритм построения одним ботом. Но все эксперименты упирались в то, что чаще всего на сложных моделях бот замуровывал себя в угол и оказывался в позиции, из которой не было выхода.
В конце-концов я плюнул и прочел обновленное условие. Кроме новых команд организаторы добавили два новых типа задач: "разобрать модель" -- начиная со стартовой модели разрушить все кубики и закончить программу с полностью пустой рабочей областью, и "перестроить модель" -- в которой тебе даны стартовая модель и целевая модель, и тебе надо превратить стартовую модель в целевую с минимальными затратами энергии.
После прочтения документации на групповые команды я начал фантазировать - ведь можно пытаться собирать модель из максимально возможных параллелепипедов и потом дорисовывать нужное. Или рисовать объемлющие параллелепипеды и отсекать ненужное. Или делать то же самое "плитами", и рисовать модель слоями снизу вверх. Но может быть так, что плиты максимальной площади ориентированы в вертикально плоскости. И вообще - задача оптимального разбиения модели на плиты или параллелепипеды наверняка или сводится к задаче раскроя прямоугольника, или к чему-то подобному, но тоже NP-полному. А подбирать/перебирать эвристики можно очень долго, и не факт, что к концу соревнования получится что-то стоящее.
На этом месте я взял свой код для оптимизации тупых решений от организаторов, добавил туда поддержку Void (для одного кубика), и "оптимизировал" все имеющиеся решения для всех трех типов задач, и заслал решения. На часах было 22:00.
При этом я понял, что для целого ряда задач разборки и переделки мое решение работать не должно, так как при удалении кубиков я не проверял, не отвалится ли от модели какой-то кусок и антигравитацию не использовал никогда.
Я посмотрел мои решения для сложных моделей визуализатором от организаторов и сосредоточился на двух основных проблемах, которые у меня явно бросались в глаза. Во-первых, для задач на сборку я явно иногда пропускал момент, в который уже можно отключить антигравитацию, и держал ее включенной на шаг-два-три дольше, чем нужно. Во-вторых, некоторые задачи на разборку ужасно тормозили. В коде отключения антигравитации нашелся обидный баг в месте, которое должно было перебирать ранее неприкрепленные кубики и прикреплять их к вновь построенным до тех пор, пока это возможно. В тормозящих задачах на разборку вылез баз в pathfinding.
В час ночи у меня был код, способный за разумное время решить все имеющиеся в наличии задачи и не упасть :)
Я заслал решения и пошел спать. Обновление турнирной таблицы жутко тормозили (на протяжении всего соревнования) и я так и не увидел, на каком я месте. К двум часам ночи сервер организаторов прочихался и я оказался восьмым (в основном потому, что мало кто вообще к этому времени что-то заслал).
На следующий день утром я обнаружил себя на 13-м месте и проснулся с мыслью, что надо же наконец научиться что-то делать одним ботом и браться за несколько. Особо светлых идей у меня не было, и я решил начать с того, чтобы сделать свой генератор обхода модели снизу вверх (для конструирования) или сверху вниз (для разборки), и дальше может в процессе что-то придумается.
Генератор написался где-то к 11:00 (я уже говорил, что я сова?) и неожиданно оказалось, что для некоторых задач на разборку он работает заметно лучше, чем оптимизированная тупая программа от организаторов. Которая должна была, по идее, делать ровно то же самое. Тут стоит отвлечься и заметить, что мой код сохранял в отдельные файлы кол-во эниергии, затраченной на решение задачи, и процентное отношение этого количества к стандартной программе от организаторов и к предыдущей моей попытке решения этой задачи. Это здорово помогало видеть, улучшается код или нет.
При ближайшем рассмотрении оказалось, что я и организаторы обходим слои в разных направлениях. Ок, - подумал я. Раз других идей нет, будем копать в этом направлении.
Всего возможных способов обхода каждого слоя было восемь - можно начать в одном из четырех углов, идти из него в одну из двух возможных сторон, а далее "змейкой" по всем оставшимся рядам. Первым делом я стал выбирать лучших вариант обхода из восьми возможных для все модели в целом, при этом после выбора направления для первого слоя направления для всех остальных были предопределены. В конце слоя бот поднимался уровнем выше, меня направление обхода на "противоположное" и так далее.
Результаты улучшились для всех задач. Увы, я не знал, на сколько это улучшило мои позиции, так как турнирная таблица тормозила. Я перестал на нее смотреть и стал возиться дальше.
Дальше я попоробовал выбирать направление обхода каждого слоя из восьми вариантов, и брать наилучший из восьми. Результаты улучшились еще где-то на 10-15%, но код начал ТОРМОЗИТЬ.
Тормозил он в основном потому, что для выбора наилучшего варианта на каждом слое я пересчитывал энергию всей программы с самого начала, так как другого мой код не умел.
Все, что имело отношение к состоянию рабочей области, было сделано число-функциональным и добавление одной команды в программу обновляло общую энергию за линейное время. Проблемы со скоростью почти пропали (ну, кто бы сомневался).
Почти, но не совсем. Некоторые задачи продолжали тормозить, и тормозил там pathfinding. Я потратил какое-то время на улучшение мелочей тут и там, но с pathfinding-ом yичего особо умного не придумал.
Кроме того, решения задач на разборку тормозили из-за того, что мой алгоритм определения, не отвалится ли сейчас кусок модели, был написан в лоб и имел время работы, пропорциональное количеству оставшихся кубиков.
Тут я с женой отправился Гулять По Полям и Считать Зайцев, и в процессе она мне и говорит человеческим голосом: "а зачем ты, добрый молодец, так убиваешься? Ты научись решать задачу сборки так, чтобы тебе не требовалась антигравитация вообще. А как научишься, то для разборки сначала реши, как модель собрать, а потом разбери строго в обратном порядке. И ничего у тебя не будет отваливаться".
Тут у меня случился facepalm, все зайцы испугались и разбежались, и я пошел домой, и поменял свой код так, чтобы он при проходе слоями вверх строил только те кубики, которые гарантировано не отвалятся, затем делал проход вниз и снова строил кубики, которые не отвалятся -- при этом распологая бота не над, а под местом строительства. И так далее до тех пор, пока что-то продолжает строится.
Оказалось, что все модели, кроме пяти, собираются за один проход вверх-вниз. И задача разборки, таким образом, была сведена к задачи сборки.
Дальше я стал смотреть, действительно ли мои решения для разборки работают, и тут оказалось, что несколько моих решений в визуализаторе от организаторов просто не работают -- бот пытается проходить через занятые кубиками клетки.
Оказалось, что у меня банальная ошибка в реализации проверки выполнимости команды LMove, и она была в коде все это время, но на задачах на сборку этот баг не "выстреливал", а вылез только в задачах на разборку.
Все это время я плавно катился вниз по турнирной таблице и скатился до 45-го места.
Я заслал все имеющиеся у меня обновленные решения, попытался дождаться обновления таблицы, но у организаторов все по-прежнему тормозило. Я оставил компьютер считать решения для всех еще нерешенных задач и пошел спать.
Пока я спал, за два часа сервер организаторов "прочихался" и я поднялся до 26-го места.
Соперники мои не спали и за ночь с 26-го места я скатился обратно до 42-го. Но когда я проснулся, меня ждала куча посчитанных за ночь решений, я заслал их и тут же поднялся до 22-го места (из 95 команд).
После этого я чуть-чуть улучшил свое решение так, чтобы бот при обходе наверх пытался выбирать позиции в текущем ряду, в которых можно зарисовать максимальное количество клеток ниже себя (и аналогично при обходе вниз). Это дало еще 10-15% улучшения.
Как это повлияло на результаты, я уже не знал, т.к. организаторы заморозили таблицу за шесть часов до окончания соревнования.
Дальше я какое-то время улучшал свой код по мелочи -- в основом тем, что прекращал обходы/циклы как можно раньше.
А затем у меня случился второй facepalm. ВНЕЗАПНО я понял, что в задачах на сборку и задачах на разборку используются одни и те же модели. И соответственно с моим подходом задачи на разборку можно вообще не решать - достаточно загрузить имеющееся решение соответствующей задачи на сборку, "развернуть наоборот" и сохранить. Было очень обидно не сообразить это раньше :(
Ну, лучше поздно, чем никогда. Я написал соответствующий кусочек кода и затем до конца соревнования (в течении, наверно, пары часов) только считал решения сложных задач (с большими номерами) и засылал организаторам.
Кроме того, стало понятно, что для задач по переделке моделей часть из них тоже уже встречалась раньше в задачах на сборку, но тут я уже ничего менять не стал.
В сухом остатке у меня были решены все задачи на сборку - и, соответственно, все задачи на разборку -- а также все задачи на переделку, кроме пяти-шести штук.
Хоть турнирная таблица и была вроде бы как заморожена, но организаторы все время что-то досчитывали/пересчитывали (абсолютно непрозрачным образом) и в результате я перемещался по таблице туда-сюда, пока не стабилизировался на 26-м месте.
Я оптимистично ожидаю, что финальный результат будет получше, но узнаем мы это, как всегда, через месяц.
В целом этот год получился, как по мне, ни то, ни се. Организация была не на высоте (хотя с условиями не накосячили, что большой плюс), и 3d я исторически не очень люблю.
Команда моя называлась "Bot the Nanobot in the Race to the Bottom".
Код: bot-the-nanobot-icfpc-2018.zip
Вот как выглядел мой путь по турнирной таблице:
Выводы стандартные: не экономьте на сне, ходите гулять, записывайте мысли на бумажку. Общение с женой рулит, за что ей традиционно большое спасибо :)
Коротко задачу можно описать так:
Вам дается описание 3d-модели, составленой из кубиков одинакового размера. Все кубики или стоят на земле или одной из сторон соединены с каким-то другим кубиком. У вас есть "нанобот", который может перемещаться в пространстве (наплевав на гравитацию) и "печатать" кубики в непосредственной близости от себя. Кроме того, от бота можно "отпочковать" нового бота (и так до 20 штук) и кроме того, можно временно "включить антигравитацию" в зоне печати, и тогда кубики, не прикрепленные к чему-то, будут висеть в том месте, в котором их напечатали. При отключенной антигравитации висящие в воздухе кубики считаются фатальной ошибкой и вызывают завершение программы.
Зона печати - это куб со стороной R, от 20x20x20 до 250x250x250 в зависимости от модели. Все операции с ботами имеют какую-то цену в виде затрат воображаемой "энергии", причем цены варьируются от 1-15 единиц за перемещение бота в пространстве до 30*R*R*R за каждый "ход" (в рамках которого каждый бот выполняет одну операцию) при включенной антигравитации. Ваша задача - свести затраты энергии на печать конкретной модели к минимуму.
Вам дается описание 186 моделей, и "стандартная программа печати" для каждой из них. "Стандартная программа" всегда одинакова - включаем антигравитацию и ездим одним ботом туда-сюда "змейкой" по всем клеткам на высоте 1, 2, 3 ..., печатая кубик непосредственно под ботом (если он там должен быть). В конце обхода антигравитация выключается и бот возвращается в (0,0,0) -- вернуться "домой" было необходимо по условиям соревнования.
Понятное дело, что на это уходило громадное количество энергии - для моделей 200х200х200 каждый ход стоил 240 миллионов единиц энергии из-за дополнительных расходов на антигравитацию, а ходов могло быть несколько десятков тысяч...
Отдельно стоит упомянуть структуру программы для печати, которую вы должны были сформировать. Программа - это простая последовательность команд без каких-либо возможностей ветвления, организации циклов и т.п. У каждого бота был уникальный идентификатор (число от 1 до 20), и на очередном ходу каждый бот по порядку (по возрастанию ID) получал из последовательности команд в программе рвно одну инструкцию и выполнял ее.
День первый, lightning round
Для меня первый день начался в 17:00 по местному времени, но освободился я только к 18:00.
Организаторы любезно предоставили визуализатор моделей и визуализатор процесса печати, но они были написаны на JS. Я JS только читаю (со словарем), и мне не очевидно, можно ли найти способ запускать визуализаторы из командной строки, а не через форму в браузере. Писать свой (нетривиальный) визуализатор - это по опыту прошлых лет почти всегда время, потраченное впустую.
Учитывая, что все входные форматы были бинарными (и все, что можно, было в них представлено наименьшим количеством бит), то первым делом я написал декодер и энкодер для програм, а так же код, который считает общее количество энергии, затраченное программой -- чтобы меньше зависеть от организаторов и их кода, который я мог запустить только в браузере.
Поиск оптимальной программы для печати был, очевидно, NP-полной задачей и хорошие эвристики для нее были мне неизвестны. Но по по опыту в lighning round зачастую побеждает тот, кто "берет больше, кидает дальше и продолжает кодить, пока оно летит", а не тот, кто придумал самый классный алгоритм. В результате я реализовал первое, что пришло в голову - берем программу тупой печати, предоставленную организаторами, и слегка ее оптимизируем. Вместо того, чтобы отключать гравитацию в самом начале, будем проверять, будет ли к чему-то прикреплен следующий печатаемый кубик, и если нет - то включим антигравитацию, напечатаем кубик и постараемся отключить ее как можно скорее.
На этом месте часы показали 0:50, и я пошел спать. Отослать решения можно и завтра -- тем более, что я еще даже не прочитал о том, что и как надо засылать.
День второй, окончание lighning round
Так как я "сова", то на второй день утром я сладко спал. Проснувшись, я выловил несколько мелких багов, поразмышлял о том, что делать дальше и наконец-то сгенерировал решения для всех имеющихся задач, собрал архив с решениям и отослал его. На часах было 11:18. Тем временем организаторы сказали, что за 6 часов до окончания lightning они отключают обновление таблицы с результатами, и я опоздал на 18 минут :)
Своей позиции в lightning я в результате не знаю.
Следующим очевидным шагом на выбранном мной пути было продолжать оптимизировать тупую программу для печати. Напомню, что тупая программа была последовательным обходим всего объема печати с помощью перемещений бота на одну соседнюю клетку, перемежаемая командами печети кубика. Если зона печати была большой, а модель - мелкой, то большую часть времени бот планомерно "утюжил" пустое пространство по одной клетке за раз, тратя на это кучу времени и энергии. Естественно было бы пропускать все ненужные перемещения и передвигаться к следующему печатаемому кубику наиболее оптимальным образом. Плюс, естественно, включать антигравитацию (командой Flip) только тогда, когда без нее было никак.
Где-то к 15:00 я заслал все оптимизированные таким образом решения. До конца lighning было еще два часа, но я решил, что больше я ничего радикального не придумаю, и сел писать декодер описания модели из бинарного файла. В процессе я понял, что если кубики находятся по соседству, то можно переместиться к первому из них, и, никуда не сдвигаясь, напечатать и соседний (или может даже несколько). Это, как мне кажется, и было финальным вариантом решения, отправленного на момент окончания lighning round.
Дальше я сел писать свою реализацию обхода модели. Идея была в том, что если я придумаю, как обходить модель более-менее оптимальным способом (например, чтобы не нужно было использовать антигравитацию в принципе), то дальше можно было бы думать, как разделить модель на части, и построить каждую часть отдельным ботом.
Со старта, естественно, надо было идти к ближайшему опирающемуся на что-то кубику, который, естественно, мог быть только из самого нижнего слоя. Дальше начинались варианты - можно было забираться вертикально вверх и строить "столб" поверх этого кубика, или можно было идти в ширину, или комбинировать движения вверх и в сторону, учитывая что бот мог построить до 18 кубиков вокруг себя, не сходя с места.
За этими экспериментами незаметно подошел к концу lightning round.
День второй, начало основного соревнования
По окончании lightning организаторы опубликовали изменения к условию задачи - максимально возможное количество ботов увеличилось до 40, и боты получили возможность коллективно строить группы кубиков за один ход. Два бота могли построить "отрезок" из кубиков (длиной до 30 штук). Четыре бота, расположенных по углам, могли построить прямоугольную "плитку". Восемь ботов могли построить параллелепипед (с длиной стороны, опять таки, до 30 кубиков). Затраты энергии на рисование были совершенно такими же, как при рисовании поштучно, но зато можно было нарисовать много кубиков за один ход. Кроме того, была добавлена команда Void, позволяющая разрушать кубик и превращать его обрано в энергию, и групповые варианты команды Void, аналогичные описаным выше.
Все это я поначалу пропустил, так как пытался продолжать оптимизировать свой алгоритм построения одним ботом. Но все эксперименты упирались в то, что чаще всего на сложных моделях бот замуровывал себя в угол и оказывался в позиции, из которой не было выхода.
В конце-концов я плюнул и прочел обновленное условие. Кроме новых команд организаторы добавили два новых типа задач: "разобрать модель" -- начиная со стартовой модели разрушить все кубики и закончить программу с полностью пустой рабочей областью, и "перестроить модель" -- в которой тебе даны стартовая модель и целевая модель, и тебе надо превратить стартовую модель в целевую с минимальными затратами энергии.
После прочтения документации на групповые команды я начал фантазировать - ведь можно пытаться собирать модель из максимально возможных параллелепипедов и потом дорисовывать нужное. Или рисовать объемлющие параллелепипеды и отсекать ненужное. Или делать то же самое "плитами", и рисовать модель слоями снизу вверх. Но может быть так, что плиты максимальной площади ориентированы в вертикально плоскости. И вообще - задача оптимального разбиения модели на плиты или параллелепипеды наверняка или сводится к задаче раскроя прямоугольника, или к чему-то подобному, но тоже NP-полному. А подбирать/перебирать эвристики можно очень долго, и не факт, что к концу соревнования получится что-то стоящее.
На этом месте я взял свой код для оптимизации тупых решений от организаторов, добавил туда поддержку Void (для одного кубика), и "оптимизировал" все имеющиеся решения для всех трех типов задач, и заслал решения. На часах было 22:00.
При этом я понял, что для целого ряда задач разборки и переделки мое решение работать не должно, так как при удалении кубиков я не проверял, не отвалится ли от модели какой-то кусок и антигравитацию не использовал никогда.
Я посмотрел мои решения для сложных моделей визуализатором от организаторов и сосредоточился на двух основных проблемах, которые у меня явно бросались в глаза. Во-первых, для задач на сборку я явно иногда пропускал момент, в который уже можно отключить антигравитацию, и держал ее включенной на шаг-два-три дольше, чем нужно. Во-вторых, некоторые задачи на разборку ужасно тормозили. В коде отключения антигравитации нашелся обидный баг в месте, которое должно было перебирать ранее неприкрепленные кубики и прикреплять их к вновь построенным до тех пор, пока это возможно. В тормозящих задачах на разборку вылез баз в pathfinding.
В час ночи у меня был код, способный за разумное время решить все имеющиеся в наличии задачи и не упасть :)
Я заслал решения и пошел спать. Обновление турнирной таблицы жутко тормозили (на протяжении всего соревнования) и я так и не увидел, на каком я месте. К двум часам ночи сервер организаторов прочихался и я оказался восьмым (в основном потому, что мало кто вообще к этому времени что-то заслал).
День третий, воскресенье.
На следующий день утром я обнаружил себя на 13-м месте и проснулся с мыслью, что надо же наконец научиться что-то делать одним ботом и браться за несколько. Особо светлых идей у меня не было, и я решил начать с того, чтобы сделать свой генератор обхода модели снизу вверх (для конструирования) или сверху вниз (для разборки), и дальше может в процессе что-то придумается.
Генератор написался где-то к 11:00 (я уже говорил, что я сова?) и неожиданно оказалось, что для некоторых задач на разборку он работает заметно лучше, чем оптимизированная тупая программа от организаторов. Которая должна была, по идее, делать ровно то же самое. Тут стоит отвлечься и заметить, что мой код сохранял в отдельные файлы кол-во эниергии, затраченной на решение задачи, и процентное отношение этого количества к стандартной программе от организаторов и к предыдущей моей попытке решения этой задачи. Это здорово помогало видеть, улучшается код или нет.
При ближайшем рассмотрении оказалось, что я и организаторы обходим слои в разных направлениях. Ок, - подумал я. Раз других идей нет, будем копать в этом направлении.
Всего возможных способов обхода каждого слоя было восемь - можно начать в одном из четырех углов, идти из него в одну из двух возможных сторон, а далее "змейкой" по всем оставшимся рядам. Первым делом я стал выбирать лучших вариант обхода из восьми возможных для все модели в целом, при этом после выбора направления для первого слоя направления для всех остальных были предопределены. В конце слоя бот поднимался уровнем выше, меня направление обхода на "противоположное" и так далее.
Результаты улучшились для всех задач. Увы, я не знал, на сколько это улучшило мои позиции, так как турнирная таблица тормозила. Я перестал на нее смотреть и стал возиться дальше.
Дальше я попоробовал выбирать направление обхода каждого слоя из восьми вариантов, и брать наилучший из восьми. Результаты улучшились еще где-то на 10-15%, но код начал ТОРМОЗИТЬ.
Тормозил он в основном потому, что для выбора наилучшего варианта на каждом слое я пересчитывал энергию всей программы с самого начала, так как другого мой код не умел.
Все, что имело отношение к состоянию рабочей области, было сделано число-функциональным и добавление одной команды в программу обновляло общую энергию за линейное время. Проблемы со скоростью почти пропали (ну, кто бы сомневался).
Почти, но не совсем. Некоторые задачи продолжали тормозить, и тормозил там pathfinding. Я потратил какое-то время на улучшение мелочей тут и там, но с pathfinding-ом yичего особо умного не придумал.
Кроме того, решения задач на разборку тормозили из-за того, что мой алгоритм определения, не отвалится ли сейчас кусок модели, был написан в лоб и имел время работы, пропорциональное количеству оставшихся кубиков.
Тут я с женой отправился Гулять По Полям и Считать Зайцев, и в процессе она мне и говорит человеческим голосом: "а зачем ты, добрый молодец, так убиваешься? Ты научись решать задачу сборки так, чтобы тебе не требовалась антигравитация вообще. А как научишься, то для разборки сначала реши, как модель собрать, а потом разбери строго в обратном порядке. И ничего у тебя не будет отваливаться".
Тут у меня случился facepalm, все зайцы испугались и разбежались, и я пошел домой, и поменял свой код так, чтобы он при проходе слоями вверх строил только те кубики, которые гарантировано не отвалятся, затем делал проход вниз и снова строил кубики, которые не отвалятся -- при этом распологая бота не над, а под местом строительства. И так далее до тех пор, пока что-то продолжает строится.
Оказалось, что все модели, кроме пяти, собираются за один проход вверх-вниз. И задача разборки, таким образом, была сведена к задачи сборки.
Дальше я стал смотреть, действительно ли мои решения для разборки работают, и тут оказалось, что несколько моих решений в визуализаторе от организаторов просто не работают -- бот пытается проходить через занятые кубиками клетки.
Оказалось, что у меня банальная ошибка в реализации проверки выполнимости команды LMove, и она была в коде все это время, но на задачах на сборку этот баг не "выстреливал", а вылез только в задачах на разборку.
Все это время я плавно катился вниз по турнирной таблице и скатился до 45-го места.
Я заслал все имеющиеся у меня обновленные решения, попытался дождаться обновления таблицы, но у организаторов все по-прежнему тормозило. Я оставил компьютер считать решения для всех еще нерешенных задач и пошел спать.
Пока я спал, за два часа сервер организаторов "прочихался" и я поднялся до 26-го места.
День последний
Соперники мои не спали и за ночь с 26-го места я скатился обратно до 42-го. Но когда я проснулся, меня ждала куча посчитанных за ночь решений, я заслал их и тут же поднялся до 22-го места (из 95 команд).
После этого я чуть-чуть улучшил свое решение так, чтобы бот при обходе наверх пытался выбирать позиции в текущем ряду, в которых можно зарисовать максимальное количество клеток ниже себя (и аналогично при обходе вниз). Это дало еще 10-15% улучшения.
Как это повлияло на результаты, я уже не знал, т.к. организаторы заморозили таблицу за шесть часов до окончания соревнования.
Дальше я какое-то время улучшал свой код по мелочи -- в основом тем, что прекращал обходы/циклы как можно раньше.
А затем у меня случился второй facepalm. ВНЕЗАПНО я понял, что в задачах на сборку и задачах на разборку используются одни и те же модели. И соответственно с моим подходом задачи на разборку можно вообще не решать - достаточно загрузить имеющееся решение соответствующей задачи на сборку, "развернуть наоборот" и сохранить. Было очень обидно не сообразить это раньше :(
Ну, лучше поздно, чем никогда. Я написал соответствующий кусочек кода и затем до конца соревнования (в течении, наверно, пары часов) только считал решения сложных задач (с большими номерами) и засылал организаторам.
Кроме того, стало понятно, что для задач по переделке моделей часть из них тоже уже встречалась раньше в задачах на сборку, но тут я уже ничего менять не стал.
В сухом остатке у меня были решены все задачи на сборку - и, соответственно, все задачи на разборку -- а также все задачи на переделку, кроме пяти-шести штук.
Хоть турнирная таблица и была вроде бы как заморожена, но организаторы все время что-то досчитывали/пересчитывали (абсолютно непрозрачным образом) и в результате я перемещался по таблице туда-сюда, пока не стабилизировался на 26-м месте.
Я оптимистично ожидаю, что финальный результат будет получше, но узнаем мы это, как всегда, через месяц.
В целом этот год получился, как по мне, ни то, ни се. Организация была не на высоте (хотя с условиями не накосячили, что большой плюс), и 3d я исторически не очень люблю.
Команда моя называлась "Bot the Nanobot in the Race to the Bottom".
Код: bot-the-nanobot-icfpc-2018.zip
Вот как выглядел мой путь по турнирной таблице:
Выводы стандартные: не экономьте на сне, ходите гулять, записывайте мысли на бумажку. Общение с женой рулит, за что ей традиционно большое спасибо :)
(no subject)
Date: 2018-07-26 05:50 am (UTC)(no subject)
Date: 2018-07-26 01:38 pm (UTC)(no subject)
Date: 2018-07-26 03:19 pm (UTC)Спасиьо за отчет. Стратегии у больших и маленьких команд сильно отличаются. Мы переделку дефолтных трейсов сразу отсекли, как малоперспективную.
Мы команда kontur.ru (9 человек)