Ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn
Начать нужно с того, что в этом (ok, в 2015-ом) году наша команда усилилась и стала интернациональной. К нам присоединился довольно-таки известный в узких кругах окамлист Fred. (Sorry, Fred, use google translate or something to read this...) Какая нелёгкая занесла его в Москву, я не помню, но всё срослось удачно, и Fred все три дня активно упарывался вместе с нами и в итоге сделал львиную долю работы. И если бы не моя тупость, то это даже могло сказаться на нашем результате. Но не будем забегать вперёд.
Проблема
Надо признать, что парни из Galois неплохо отжигали хинтами. Тут тебе и Ктулху, и роботы, и диарсен(?) и какое-то непонятное
Всё это выглядело очень многообещающе и спровоцировало много обсуждений и волны переписки.
А в итоге в качестве проблемы было предложено написать банальный AI для гексагонального тетриса. Вместо лямбд, виртуальных машин и вот этого всего мы получили простую как доска задачу дискретной оптимизации. Т.ч. сделанные в предыдущем посте предсказания отчасти сбылись. В общем, проблема выглядела удивительно не по-icfpc'шному.
Кстати, гексагональный тетрис на поверку оказался и не тетрисом вообще, т.к. фишка была не столько в укладывании unit'ов, сколько в правильной траектории каждого юнита.
Ну, хорошо, всё подробно изложено на официальной странице, а я очень кратенько. Дан "прямоугольный" стакан с гексагональной сеткой (может быть частично заполненный). И дан конечный список unit'ов — фигурок в том порядке, в котором они будут появляться. Фигурки могут состоять из одной или нескольких клеточек (cells) и вращаться вокруг центра вращения (pivot point). Центр вращения не обязательно лежит "внутри" фигурки, что позволяет им проходить сквозь сплошную среду.
Очередная фигурка появляется вверху по центру стакана и двигается под воздействием команд: влево, вправо, влево-вниз, вправо-вниз, поворот по и против часовой (на pi/3).
Если очередная команда неприменима, то фигурка застывает в текущем положении (lock) и дальнейшая последовательность команд применяется к следующей фигурке.
По правилам игры фигурка не имеет права возвращаться в состояние, в котором уже была. Поэтому последовательности команд типа "влево-вправо" или "6 поворотов по часовой" всегда приводят к застыванию фигурки.
("The Old Ones do not take kindly to stuttering computations!"
Как и положено в тетрисе, после того, как ряд стакана полностью заполнен, он исчезает и верхние ряды смещаются вниз.
В гексагональной сетке это приводит к достаточно специфическим эффектам.
So far, so good.
А теперь самая забавная часть. Каждая команда для фигурки может быть закодирована одним из множества символов.
Например, команда "влево" может быть представлена любым из символов {p, ', !, ., 0, 3}.
Таким образом в последовательность команд можно было вплетать т.н. фразы силы (power phrases).
И вот за них-то и давали больше всего очков.
Было известно, что всего фраз силы существует 18 штук и приводилась самая короткая из них: "Ei!".
Остальные фразы предлагалось открывать самостоятельно.
Пятница
Лично я в пятницу общался с риэлторами - удивительная порода людей, конечно, - и прискакал в поту и в мыле в офис где-то за час до публикации задания. Только-только успел охладиться под кондиционером и попить чайку. Мозги были тотально выедены.Фред в четверг бухал с какими-то русскими в бане и выглядел тоже не лучшим образом.
Лёха тоже на что-то жаловался: то ли на работе его доставали, то ли дома, то ли что-то еще. По-моему, работать заставляли, изверги.
В общем, команда наша подошла к контесту в классическом своём состоянии тотального раздолбайства. Прочитав задание, мы созвонились, обсудили его и каждый взялся за своё.
Лёха, естественно, принялся хакать сервер оргов и строить питоновскую обвязку. Fred героически взял на себя разработку интерпретатора игры на окамле. А я некоторое время потупил, понял, что толку от меня мало и принялся изучать творчество Лавкрафта на предмет поиска фраз силы.
Неожиданно выяснилось, что Fred в теме. Он не только принёс нам первую фразу силу (вынесенную в эпиграф данного поста), но и подсказал мне какие-то вещи про этот волшебный R'lyehian язык. Более того, вооружившись grep'ом, make'ом, полным собранием сочинений Лавкрафта и английским словарём он запилил первую версию NLP фреймворка, с помощью которого я в течение остатка вечера охотился на фразы силы. Всех обнаруженных подозреваемых я отправлял Лёхе в "уютную пытшную", где он их верифицировал через прогон на серваке организаторов. В итоге, там что-то верифицировалось не так, потому что единственная найденная за вечер фраза была "R'lyeh", хотя впоследствии выяснилось, что нашёл я их немало.
Разочарованный таким низким КПД я полез в википедию и поизучал до кучи пантеон Лавкрафтовских богов. К счастью, организаторы вовремя опубликовали в твиттере следущее: "We are enjoying watching contestants search for power phrases, but the Deep Ones discourage cutting & pasting from Wikipedia." А то могло случиться страшное.
Еще одна полезная вещь, которую я сделал тем вечером, - это наваял и запустил скрипт, который должен был скачивать leaderboard каждую минуту. Правда, как выяснилось через три дня, скачивал он совсем не то, что нужно. :-)
Суббота
В субботу я проснулся с готовым решением проблемы в голове, о чём не замедлил сообщить при встрече парням. Неожиданно, оба согласились, что план мой не лишён смысла...Идея состояла в том, что общая задача дискретной оптимизации неплохо декомпозировалась на две ортогональные подзадачи: оптимальное укладывание отдельной фигурки в стакане и поиск максимально длинной (дорогостоящей) последовательности "терминалов". Терминалами или терминальными положениями мы называли финальное положение фигурки, в котором она в итоге застывала в стакане.
Фразы силы предполагалось вплетать независимо в траекторию каждой отдельной фигурки. Как в точности это делать было не совсем понятно, хотя и ясно, что это будет какой-то поиск в дереве возможных ходов, в котором множество "элементарных" ходов будет расширено фразами силы. Еще было непонятно, где, собственно, брать эти самые фразы силы, поэтому решено было этот вопрос отложить в долгий ящик, т.е. где-то до понедельника.
Является ли положение фигурки в стакане возможным терминалом определяется двумя свойствами: наличием легальной траектории от начального положения до искомого и наличием нелегального хода в искомом положении. Поэтому проблему поиска множества всех терминалов предлагалось решать при помощи нехитрого динпрожика, который бы дал множество всех достижимых положений, и фильтра по числу доступных из данного положения легальных ходов.
Если представить себе множество терминалов, как множество возможных ходов из данного узла дерева, то высокоуровневая задача оптимизации неожиданно превращается в задачу поиска самого ценного пути от корня до листа в дереве. Истинную ценность пути, правда, определить нелегко, а с учётом наличия в задании ограничения на объём памяти и время самым разумным вариантом казался алгоритм типа beam search с высотой "центра масс" в качестве эвристики.
В общем, не протупив и трёх часов с момента общего сбора я приступил выполнению первой задачи: построения множества терминалов для данной фигурки и стакана. Естественно, на хаскеле. У меня, правда, еще не было способа строить все возможные ходы для фигурки из данного положения, т.к. Fred продолжал бороться с вращениями.
В целом у него всё нормально работало, но иногда он приходил ко мне и произносил текст, начинающийся с фразы: "Ok, Sasha...", что означало, что он нашёл еще один какой-нибудь забавный косяк. Косяков было много. Во-первых, одна из команд сумела-таки расшевелить The Old Ones тем, что обнаружила возможность сделать бесконечный цикл... Потом была куча разъяснений и дополнений к правилам. В итоге орги даже выложили кино правильной обработки ходов для некоторых проблем.
Но лично я был спокоен как мамонт. Ясно было, что Fred в итоге добьёт интерпретатор и я таки заимею правильный "внутренний граф" для проблемы динамического программирования. А пока сойдёт и кривенький. Поэтому можно спокойно двигаться вперёд по заранее намеченному плану, не обращая внимания ни на какие внешние раздражители. Даже на весёлое рубилово, происходившее по всем фронтам: в leaderboard'е, официальном irc и неофициальном русскоязычном jabber'е. Похоже, везде успевала отжигать команда "Диких Башкортостанских Магов". Запомните это имя. Оно еще встретится. Дело дошло до того, что самим Древним пришлось вмешаться и орги попросили прекратить вакханалию и поубивать клоны команды "Hack the loop" :-)
Лёха тем временем конкретно упоролся питоновской обвязкой и полностью захватил власть над орговским сервером. Fred'у тоже нужно было сабмиттить какие-то решения для отладки, а Лёха уже пользовался Fred'овским интерпретатором для визуализации и скоринга решений. В общем, пока я витал в своём динпрожьем астрале, эта парочка неплохо спелась.
Кстати, я к тому моменту ни разу и не запускал Fred'овский интерпретатор, т.ч. даже не посмотрел, какие квалификационные проблемы предложены оргами. Т.е. решал поставленную задачу в своей обычной манере: полностью абстрактно, игнорируя любую конкретику. Частные случаи нас не интересуют, знаете ли.
В общем-то на разработку динпрожика, доставание из него множества терминалов и кратчайшего пути до каждого терминала, на простенькую запускалочку, на парсинг входных и генерацию выходных форматов весь день у меня и ушёл. Зато последний коммит был "WOW!" и разъяснялось, что весь этот колхоз умеет генерировать решение проблемы на глубину единственной фигурки. Один слой beam search, если угодно. Это было очень близко к полностью рабочему решению. А ведь еще была только середина контеста. Очень непохоже на нашу команду. Правда на лайтнинг мы опять не успели.
Лёха тоже воодушевился моими успехами и под шумок закоммитил нечто под названием cppsolver. Правда на тот момент оно только и умело, что парсить входной json.
Воскресенье
В воскресенье я со свежими силами вонзился в хаскельный солвер.Для начала прорешал все 25 квалификационных проблем на глубину 1 юнита. Если вы думаете, что это заняло минут 15, то очень ошибаетесь. Это заняло 4 часа, если предположить, что мы встретились в 9 утра. Правда по дороге я что-то пофиксил в солвере а заодно подготовил три полудохлых хетцнеровских сервачка к ночному дежурству. В ночь на понедельник им по моему замыслу предстояло считать...
Дальнейшие действия были совершенно понятны. Нужно было развивать то, что мы называли Higher Level AI, а именно: переходить от одноюнитовой решалки к многослойной. Т.ч. я принялся колхозить какой-то beam search. Опять же пришлось наплевать на всякую конкретику: отсутствие поддержки вращений, баги в inner graph, отсутствие функции вычисления высоты центра масс стакана, отсутствие функции определения следующей фигурки итд итп. Ну, нам не привыкать работать в условиях неопределённости. Ничего страшного, что программу нельзя запустить, лишь бы компилировалась.
Fred конкретно разогнался к воскресенью и сыпал коммитами как из пулемёта. К полудню он разобрался с наиболее неприятными багами, воспроизвёл орговское кино и стал атаковать моё поделие, пытаясь интегрировать в него свои наработки. В итоге, к 16 часам мы неожиданно научились решать проблему на глубину двух юнитов. Чёрт его знает, откуда появилось это промежуточное решение и почему нельзя было сразу запилить нормальный поиск на произвольную глубину.
В итоге beam search запилил к 18 часам Fred, а я стал заниматься всякими формальностями, типа поддержки command-line интерфейса и сортировки проблем по ожидаемой сложности. И к 19 часам мы имели полностью работающее решение, отвечающее требованиям к сабмишену и даже генерирующее какие-то решения. Правда без фраз силы и очень медленное.
В этот момент на сцену ворвался Лёха, который был подозрительно тих весь день. Оказалось, что он поизучал мой динпрожек на хаскеле, попытался переложить его на c++, не осилил, сварганил промежуточное решение на python, отладил и с него сделал кальку на c++. Всё бы хорошо, только оказалось, что это работает неправильно и генерит невалидные программы. А как отлаживать? Пришлось мне тут продемонстрировать Лёхе всю мощь Emacs'овских макросов... Ладно, это шутка.
На самом деле у меня тогда был уже полнейший цейтнот. Мне хотелось срочно доделать поддержку ограничений по памяти и cpu и успеть запустить 24 проблемы считаться на всю ночь. И тут Лёха ехидно задал простой и незатейливый вопрос:
- А сколько времени у вас один динпрог решается?Стали разбираться и выяснилось, что для референсной 14-ой проблемы один юнит решается что-то в районе 100 миллисекунд. Тогда Лёха для справки сообщил, что а) 100 ms - это примерно вечность б) хаскель - унылая хрень в) моё решение с обновлением всего массива до фиксированной точки, когда там могут меняться лишь несколько ячеек на итерацию, - это "решение математика, но не программиста" г) его c++-ное решение тратит меньше миллисекунды на динпрог.
Поразмышляв несколько вечностей над вышесказанным, я понял, что с этим действительно надо что-то делать. И тут удачно подвернулся Fred, у которого закончились свои идеи. В итоге он взял на себя все недобитые задачи и позволил мне сосредоточиться на профилировании и оптимизации. А сделавший своё грязное дело Лёха вернулся к своему питону и плюсам и накоммитил в репозиторий каких-то загадочных кривых решений, которые нам здорово аукнулись в понедельник (справеливости ради, некоторые из них были лучшими, из того, что у нас было).
В 11-ом часу мы таки добили всё, что было нужно для ночного запуска. Я адски устал, но всё-таки заставил себя аккуратно запустить 24 screen'а с солверами. В метро мы еще пытались рассуждать о том, как нам быть с фразами силы. Я был в таком коматозе, что напрочь забыл, что еще в субботу придумал, как их вплетать в готовую цепочку терминалов. Вместо этого я предложил пробовать вплетать их... sed'ом в уже готовые решения. Fred, который явно чувствовал себя свежее других, из вежливости соглашался со мной. Но если задуматься, то может это было и не самое тупое решение, т.к. предполагалось, что у нас уже не будет времени перерешивать квалификационные проблемы, и нам придётся сабмиттить то, что насчитается ночью.
Понедельник
В понедельник первым делом обнаружились две проблемы. Во-первых, один из хетцнеровских серваков перегрелся и выключился. Таким образом мы потеряли решения 8 проблем. Еще две проблемы сдохли по ограничению на память. Во-вторвых, я не перенаправил вывод решений в файл и их пришлось доставать из screen'а вручную. Из 24 скринов вручную. А решения там о-о-о-очень длинные. А screen не позволяет скопировать сразу весь свой буфер, приходилось экран за экраном аккуратно буковка к буковке... Fred раскопал, как сохранить весь буфер screen'а в файл, но по каким-то причинам это не сработало.Короче, часа два мы занимались тем, что на разные лады спасали эти 14 выживших ночных решений. Я доставал их как мог из screen'а (еще и с лишними переносами строк или какой-то другой проблемой с форматом - не помню), а Лёха с Fred'ом их раскладывали по каким-то файлам, чистили, прогоняли на интерпретаторе, скорили и пытались в них вокнуть известные фразы силы. Короче, тупняк удался на славу. Особенно, если учесть, что это был рабочий день и мы были в разных офисах.
Fred параллельно с этой с этой деятельностью еще успел оптимизировать динпрог, используя свойства симметричных фигурок. Цифр не знаю, но можно предположить, что динпрог ускорился пропорционально количеству симметрий фигурки. Т.е. для одноячеистой - в 6 раз.
Дальше настал мой черёд и я прооптимизировал своё "математическое" решение, сделав его примерно вдвое более "программистским".
Далее была еще череда мелких улучшений и внезапно то, что считалось всю ночь, стало можно посчитать за полчаса. Что и было сделано для 8 проблем-погорельцев и двух неудачников по памяти.
За час до окончания контеста солвер был дополнительно распараллелен, а также был улучшен time и memory management. Fred даже приколхозил какую-то поддержку фраз силы. Правда я почему-то уже решил себя, что "это сложно и мы сейчас делать не будем" и даже не думал об этой проблеме. Хотя очевидное решение лежало на поверхности, было известно с субботы и потребовало всего полчаса на реализацию после контеста... Epic Fail.
Еще один фейл поменьше случился при подготовке финального сабмишена, когда за 15 минут до дедлайна, Лёха с Fred'ом что-то не поделили в репозитории, ситуация как-то резко вышла из под контроля, и мы в итоге на последних секундах засабмитили какой-то адский трэш: хорошие решения вперемешку со всяким случайным шлаком из репозитория.
Итоги
А в итоге мы заняли почётное 117-ое место, причём почему-то без единой фразы силы. На самом деле, я заморочился пересчитать наш "очищенный" от трэшака рейтинг и выяснил, что мы бы заняли 95-ое место, если бы не зафакапили сабмишн. Т.ч. невелика беда.А вот отсутствие фреймворка для фраз сил, который пилился на самом деле за полчаса, - это Настоящая Печаль. Потому что, емнип, он выводил бы нас в top-25. Правда при условии знания всех фраз силы. В общем, конечно, в Final Leaderboard мы бы не попали, но всё равно обидно.
Что касается процесса, то всё было сравнительно неплохо. И Fred нас реально усилил. Что там говорить, благодаря ему, наша команда прыгнула выше собственной головы, и впервые у нас был нормальный Графический Визуализатор! С координатной сеткой, зумом, статистикой, скорингом и отображением следующих фигурок.
Если бы мой скрипт для фотографирования leaderboard'а сработал, то сейчас можно было бы проверить, действительно ли в начале контеста мы поднимались до 5-го места благодаря быстро запиленному интерпретатору и Лёхе, который прорешал кучу задач врукопашную. Кстати, интересной особенностью задания была возможность такого человеко-машинного взаимодействия для решения задач квалификационного раунда.
Я же в течение контеста ухитрился даже не посмотреть, что там за решения мы нагенерили. Это было сделало уже когда пыль улеглась. И сразу выяснилось, тетрис как бы не совсем тетрис. Большинство задач наша тривиальная эвристика с центром масс решала просто до конца, укладывая все фигурки. При этом многие стаканы были такими большими (и пустыми), что даже идеальное укладывание всех фигурок не давало возможность заполнить и убрать много рядов. На таких картах фишка была именно во фразах силы.
Еще было два типа карт, которые наша эвристика могла не прорешать до конца. Во-первых, это сложные карты, где требовалась точная укладка и заглядывание вперёд. Во-вторых, это карты, на которых были какие-то воздушные конструкции в центре, игравшие роль сита: часть фигурок просачивалась вниз, а часть - не могла. Я пытался как-то дополнить эвристику выбора терминала соображениями по "плотности упаковки", но толком ничего не получилось. Ну, что сказать. Как известно, Ктулхи плохо композируются (см. problem 13).
Еще хочу сказать за динпрог. После всех улучшений оказалось, что наш солвер на 14-ой проблеме тратит не более 9 ms на решение одного стакана. А если верить профайлеру, то и не более 4 ms. Т.е. всё еще в 4 раза хуже, чем c++, но в 25 раз лучше первой реализации. Тут сказались не только оптимизации в самом динпроге, но оптимизации, связанные с симметриями, с инкрементальным вычислением центра масс стакана итп. Как выяснилось, там было, чему тормозить и без всякого динпрога.
Кстати, пакет vector оказался совсем неплох. Мне не удалось переписать программу на какие-нибудь мутабельные массивы так, чтобы заработало быстрее.
Вообще, динпрог изначально пилился с дальним прицелом на GPU. Задача как будто очень подходящая для этого дела. Но, то ли я совсем не умею готовить accelerate, то ли древний gtx 8800 уже совсем не может пару чисел сложить, но динпрог на GPU работает крайне медленно. Можно было попробовать на маке, но их греть стрёмно - уж больно нежные ноуты. GPU просто отпаивается и сгорает. Проверено.
Если бы accelerate нормально завёлся, то можно было бы попробовать еще одну интересную оптимизацию: решать весь пучок задач параллельно. Никто, в общем-то не запрещает в один массив запихать несколько стаканов и в каждом из них гнать свой независимый динпрог. Для GPU - самое то.
А для CPU был неплохой вариант не пересчитывать все динпроги в пучке с нуля, а воспользоваться тем, что на каждом слое в каждом стакане падает одна и та же фигурка. Стаканы же в пучке, как правило, начинают различаться только ближе ко дну. Соотвественно, пересчитывать все верхние ряды стаканы каждый раз смысла нет. Аналогичная оптимизация возможна, если та же самая фигурка выпадает позже в этом же стакане. Оба варианта остались нереализованными.
До кучи я попробовал inline-c. Это, опять же, работало слишком медленно. Видимо, маршаллинг между хаскелем и c слишком накладен.
Можно было вообще отказаться от динпрога и подумать о каком-нибудь эвристическом алгоритме. Но мне кажется, что мы в производительность построения множества терминалов на самом деле не упирались. Гораздо важнее было улучшить эвристику отбора терминалов для beam search и запилить фреймворк для вплетения фраз силы.
По завершении контеста я его и запилил. Просто жадный поиск по дереву вариантов ходов из текущей позиции с эвристикой "максимально ценного хода". Ходом считается как "элементарный" ход (0 очков), так и подходящая "фраза силы". Очень дешёвая и сердитая штука получилась.
Потом, воодушевлённый отчётом "Диких Башкортостанских Магов", решил попробовать сделать что-то более содержательное для вплетания фраз силы. В итоге родился нечеловечески сложный алгоритм под названием ultimate, который я сейчас уже совершенно не понимаю. Нет, по сути это, опять же некий динпрог, но для сокращения фазового пространства там возникают какие-то метасостояния, свёрнутые измерения и квантовое туннелирование. В общем, работает немножко медленно... На этом мой пыл и интерес к этой задаче окончательно иссяк.
Орги тоже подвели итоги, признались, что задача была "планом Б", т.к. с "планом А" они переборщили, а также опубликовали дичайший отжиг от все тех же WBM: Оргам респект за то, что честно отыграли роли до конца, за leaderboard и за публикацию официального репозитория. Но задачка не для icfpc всё-таки, imho.
Посмотрим, что через 3 часа нам предложат японские товарищи.
Пока всё выглядит очень интересно. Мы имеем следующие хинты:
- Машинная плавающая точка
- Хило- и метаморфизмы
- Совиный комбинатор
- Элементарая Теория Чисел
- Летающие Подушки
- Покер
- и "Hello, fold/unfold!"
Всё, публикую не перечитывая и сплю.
