ВведениеПропустить ICFPC-2014 команда THIRTEEN никак не могла, и поэтому 25 июля 2014 года в 12:00 UTC (а у некоторых было 5 утра!) собралась почти тем же составом, что и в прошлом году. В этот раз собраться всем вместе в том же месте не получилось, в команде впервые появились очень удалённые участники. Но основной состав всё же смог собраться в офисе у Brox. Отчёт от tilaridsТак вышло, что поучаствовать в ICFPC в этом году вживую у меня никак не получалось. Но это не повод отчаиваться! Хоть Сан Франциско и находится за 10 часовых поясов от Харькова, ICFPC - это не то, что стоит пропускать. Также был положительный опыт “Зимнего ICFPC”, в котором вообще вся координация происходила по скайпу. Чтобы хоть как-то сгладить негативный эффект от удалённости, я решил сразу писать весь код на Java. Как показывает практика, это Lingua Franca для нашей команды (а еще это язык, на котором пишет Sanny, да еще и обычно пишет очень много кода :)). Решение это было одновременно и правильным, и не очень. Правильность в том, что таки удалось реиспользовать мой код для решения задачи. Неправильность в том, что Java я так и не знаю, да и инструментарий не был подготовлен. Поэтому я за время контеста перешёл с “Eclipse + OpenJDK1.7” на “Sublime Text 3 + OracleJDK1.8 + javac src/**/*.java”, а заканчивал вообще с “IDEA + OracleJDK1.8”. Еще я узнал, что в Java Stack обходится в неочевидном порядке, а сравнение двух Integer’ов - весьма опасная штука :) По прочтению задания ранним утром мгновенно стало ясно, что нужно писать компилятор с какого-либо ЯВУ в коды SECD процессора (о том, что эта штука называется SECD мы узнали уже по окончании контеста). И в то время как Харьков решил писать DSL на Java, поставив во главу возможность запускать и отлаживать программу на хостовом языке, я решил попробовать написать компилятор JavaScript. Причина проста - я хотел в качестве хостового языка нечто похожее на целевую модель, я хотел иметь возможность экспериментировать с этим. И JavaScript - это, наверное, простейший язык с замыканиями и без скобочек, который я знаю. Сейчас я думаю, что стоило перебороть себя и попробовать нечто со скобочками. Потому что писать всё равно приходилось в стиле, который для JavaScript не свойственен. Еще более правильным решением было бы не писать компилятор вообще. Я понимал, что в Харькове пишут свой, но остановиться перед такой интересной задачей я не мог. Итак, написание компилятора я начал борьбой с ANTLR3, после чего довольно быстро завёл парсер на ANTLR4. Еще пара часов - и был готов простейший компилятор. Заняло это от публикации задания до первой версии, которая позволяла скомпилировать простейшего бота, часов 7, из которых часа полтора было потрачено на дорогу и daytime job (пятница - рабочий день же!). Я тут же попытался этот компилер “продать” команде в Харькове в надежде, что кто-то пожелает писать на JavaScript, а не на Java-based DSL. Покупать никто не желал, и тут бы мне напрячься, тем более что [T+8h] Sanny: пытаюсь нагнуть людей писать на полу-жабе, т.к. уже надо писать... И я даже посмотрел на то, что умеет компилятор за авторством Sanny. Но у меня еще была куча идей, что можно сделать с моим компилятором. Так, я закончил реализацию всей арифметики, добавил мутабельные локальные переменные, циклы, так что можно было писать весьма императивный код. В качестве последней крутой фичи я добавил динамическую память - адресуемые массивы. Сделать это было не так просто, потому что команды чтения из фрейма и записи в фрейм не принимали индекс в качестве параметров. Т.е., можно было попросить прочитать 3-ю ячейку и записать 5-ю, а вот попросить прочитать i-ю ячейку было нельзя. Для решения этой проблемы я генерировал подобный код (почему-то я решил назвать это виртуальными таблицами): - А не является ли i нулём? Нет? Двигаем дальше. - А не является ли i двоечкой? Да? LD 0 2! Эти таблицы генерировались единожды и впоследствии вызывались посредством local-call (sel/join). Всё это заработало в T+18h. В результате можно было не задумываясь писать такое: function step(state, world, n, m, lm_status) { } function step_impl(state, tuple4) { function init() { return [0, step_impl]; } Доступ к памяти осуществлялся посредством вызовов функций read_memory(i) и write_memory(i, value). В общем и целом - сплошная императивщина. К сожалению, даже это не сподвигло тиммейтов в Харькове писать алгоритмы на JavaScript. Впрочем, это и хорошо, активное использование read_memory/write_memory явно бы привело к нехватке количества инструкций. В свою очередь я честно попробовал сам написать что-либо на JS, но через несколько часов сдался. Здесь впервые появилась самая страшная напасть этого ICFPC: писать компиляторы в разы интересней, чем скучный AI для простой клеточной игры. После многочасового фана по написанию компилятора для лиспового процессора волновые алгоритмы не доставляли совершенно. Так что я сделал правильную вещь - на [T+21h] я окончательно забросил свой компилятор и больше к нему не притрагивался до конца контеста. На lightning ушёл submission, которым занимался Sanny. А я, прочитав задание для основного раунда, отключился на 4 часа. Проснувшись, и разобравшись, что же умеет наш DSL, я довольно быстро набросал реализацию immutable map(как оказалось впоследствии - довольно бажную реализацию, но особых проблем это не вызвало). После этого реализовал процессор GHC на GCC, что давало возможность эмулировать поведение привидений внутри лямбдабота. На этом этапе ([T+37h]) наш бот уже активно бегает по карте, выедает таблетки, и даже умудряется запускать волну на тот случай, если ему не хватает инфы о ближайших рёбрах (эта инфа считается единожды при инициализации). К сожалению, он довольно медленный, в основном потому, что вовсю использует списки и линейный доступ к ним. Переписываю всю алгоритмику на immutable maps, с O(log2 N) доступом - [T+40h]. И после длительной войны Sanny с компилятором получаю результат ([T+44h]) - никакого видимого прироста производительности нет! Видимо, реализация immutable maps настолько громоздка, что log2N сравним с N при небольших N. Вот это “видимо” нужно было подтверждать числами, а не сравнивать на глаз. Очевидно, что immutable maps нужно было доводить до конца. До [T+49h] занимался внутренней логикой бота на коротких расстояниях (этот код был впоследствии удалён и так никуда и не попал). А потом за 2.5 часа сделал то, что нужно было сделать в самом-самом начале - написал наш внутренний эмулятор GCC. Если бы это было сделано раньше, отладка компилятора сильно бы упростилась. Обоих компиляторов. Проверив, что простейшие программы в эмуляторе работают, уснул. Проснувшись, увидел, что Sanny добавил в эмулятор счётчик инструкций, отладил его и активно использует. Порадовался, и прикрутил к эмулятору ABI. Т.е., добавил возможность писать такое: GCCEmulator cpu = new GCCEmulator("test.txt", 2); cpu.storeInFrame(0, worldState); Последние несколько часов пытался реализовать альтернативное AI для бота, используя A* для поиска пути. A* работал плохо, и на доводку его времени не оставалось. Сабмитили то, что было + привидений, к написанию которых я даже и не притрагивался. Вывод: компиляторы писать весело, и мы это настолько любим, что готовы проиграть, но не будем заниматься чем-то менее интересным! :) Отчёт от sanTLDR: Я компилил Java в байткод лямбда-мена с помощью ECJ + руки, и еще мне помогали кто чем может по мелочам. Затем коллеги писали ghost-ов на простом ассемблере, RST накомпилял с языка Ц (?), а мы с tilarids писали на Java лямбда мена, безуспешно, потому что мутабельность придумали поздно, а алгоритм наш был с использованием “дуг” от развилки до развилки (граф) , что работало быстро, но писалось сложно, и не взлетело совсем. Еще tilarids написал эмулятор ЦПУ, прикрутил к нему мою эмуляцию мира с рандомными ботами, и мы могли тестить компилятор и профилировать программу на перфоманс. Java с лямбдами рулит! Теперь подробнее. Я собрался в месте проведения контеста за 40 минут до начала, и пока настроился и то да сё, уже открыли задание, и мы все начали его читать. Задание было большое и обстоятельное. Я его пробежался и понял общую суть, что pacman и лисп-машина, а детали думал почитать потом (оказалось, что и потом не почитал, а спрашивал у коллег по команде, чтобы быстрее). Так как стало ясно, что прямо на языке указанном в спецификации, его писать не получится, пришлось решать на чём писать. Подумав с полчасика, мы пошли в кафешку всей толпой и стали думать там. Думали еще часа полтора и вышло у нас понимание, что как ни крути, высокоуровневый язык будет похож на лисп, и что хочется не просто “написал, откомпилировал, прогнал в предлагаемом эмуляторе, почитал trace”, а чего-то большего, например отладку в IDE. Я в курсе, что существуют споры “написал, поставил брейкпойнт,остановился на нем, подумал“ VS “подумал, написал, запустил, заработало.”, так вот я отношусь к первой категории и еще с детства инвалид по JAVA и поэтому понял, что будем компилить java. И java эта будет с лямбдами. То что она будет еще с женериками, выяснилось позже, в процессе написания. Tilarids вбросил по скайпу в кафешку, что ANTLR для Java есть, но я нашел что он без лямбд. Чтобы таки взлететь, оставалось произвести последнее действие, о котором я до того только мог мечтать - взять Eclipse Compiler for Java, как это делают все люди, и заюзать его. В нем есть офигенный парсер, который возвращает офигенный DOM, который описывает и лямбды и всё-всё-всё. Когда пришли из кафешки, оказалось, что сам Tilarids решил парсить Javascript, но так как я указанный язык не одобряю ни с какой стороны, кроме разве что target platform для компиляторов, потому что он не типизированный, то решил, что будущее покажет. Короче, как-то так оказалось, что за педалинг я сел то ли в +4 то ли в +5 часов от начала, а до этого в голове у меня плодились идеи компилятора. Очень быстро я определил подмножество Java, на котором уже можно было писать программу, и в этот момент уже можно было начинать писать всё что угодно, покуда я доделываю компилятор, но пишущие коллеги уже озадачили себя ghost-ами, а думающие не были сильны в функциональных алгоритмах, а особенно в жабовом исполнении (nonsense!). Все мои первые сутки прошли в итерационном улучшении компилятора, ловле вредного бага (от -7 до -2 до lightning deadline) и написании первой программы бота (от -2 до 0), которая парсила на этапе инициализации карту на дуги графа через BFS, и потом в первой по близости от бота дуге считала точки и шла туда, где больше дают. Если точек нет, она стояла. Эту программу мы и засабмитили, она набирала 1400 очков, а jabber.ru между прочим, похвастался, что у него уже 10К.... Далее я совершил 3 фатальные ошибки. 1) Сел писать алгоритм сам, а не в паре с товарищем 2) Не додумал сначала как сделать мутабельность, потому что не вкурил как работают CLOSURES при возврате лямбд из функции, а tilarids меня научил токо в середине 2 дня, когда уже дофига кода была написано, который выкидывать жалко. 3) Не до конца продумал алгоритм с дугами, шел по наитию, и не пришел. Непривычно писать на непривычной джаве с фолдами, а хаскельские навыки помогают не слишком. Да и на хаскеле я писал бы это в 5 раз медленнее чем на нормальной жабе, поэтому проверять и тестировать варианты получалось сильно медленно. По второму вопросу: SAS регулярно поднимал тему массивов с O(1) на основе команды записи в environment (в java-script смысле), которая называлась ST и которую я использовал для записи локальных переменных функции. Я это отрицал по двум причинам. Во-первых, прямой доступ даже к имеющемуся массиву по произвольному индексу потребует log2(N) сравнений и прыжков, покуда не допрыгает до нужного места, и это не O(1), а во-вторых я не понимал как менеджить этот массив, т.к. не вкурил этих CLOSURES, их отношений и их lifecycle (т.е. оставил непонятой часть спецификации, аяяй мне!). После объяснений тиларидза о том, что ссылка на CLOSURE сохраняется в момент LDF, у меня мозг стал на место, и я внезапно понял как сделать мутабельный массив, и как его заюзать чтобы не прыгать по сравнениям: для этого всю дугу от перекрестка до перекрестка нужно проинициализировать лямбдами, сразу читающими нужый элемент (ссылки на команды LD const_env const_addr), и проход по дуге превратится в прямой доступ к соответствующим ячейкам заранее проинициализированного картой массива. В конечном итоге я написал этот массив на лямбда-ассемблере, прикрутил ассемблер в компилятор и сделал соответствующую java implementation, чтобы можно было юзать и в прямой java. Ну и постепенно начал перегонять в это дело код (в чём мне помогал SVG), сильно (раз в 6, а может и более) ускорив его, но не перевёл всё до конца, оставив некоторые части как были. Постепенно я дошел и до массива размером в 1, и открывающиеся упущенные перспективы очень грузили меня, ибо время было на исходе. Короче, вот так остальные 2 дня прошли в переменном улучшении компилятора и набрасывании нового лямбдо-кода на компилятор. Постоянное ощущение что вот исправлю последний баг компилятора и всё сразу заработает (так и происходило в общей сложности раз 5-6,, и облегчение наступало, пока в моем компилируемом коде не всплывал очередной case, но ко времени +2.5days всё наконец устаканилось). Вдохновляло, что tilarids мог на этой жабе писать сложные алгоритмы, например эмулятор программ ghosts, который мы так и не заюзали (негде!) Регулярно, уставая от бесплодных идей родить что-то более новое с дугами, я развлекался с профайлером на основе эмулятора tilarids-a, ибо получал от этого в перерывах свой хороший дозняк. Но весь дозняк портило знание того, что наш лямбда-мэн погибал от наших же ghost-ов просто на ура.... Короче, реальным позитивным результатом своей работы считаю 1) очередную дозу фана 2) знакомство с очень классным ECJ, который просто взял и заработал сразу. 3) написание с его помощью компилятора таких вкусностей (которые тупой голове не помогли впрочем):
static class WorldState extends Cons { ListCons<ListCons<Integer>> map; LambdaManState lambdaManState; ListCons<GhostState> ghosts; int fruitStatus; WorldState(ListCons<ListCons<Integer>> map, LambdaManState lambdaManState, ListCons<GhostState> ghosts, int fruitStatus) { super(null, null); this.map = map; this.lambdaManState = lambdaManState; this.ghosts = ghosts; this.fruitStatus = fruitStatus; } } @Compiled private Tuple<AIState, Function2<AIState, WorldState, Tuple<AIState, Integer>>> entryFactual(WorldState ws, ListCons<ListCons> ghostSpecs) { AIState initialState = createInitialState(ws, ghostSpecs); return new Tuple<>(initialState, (nextaistate, worldState) -> performMove(nextaistate, worldState)); } И всякие ListCons<ListCons<ParsedEdge>> newRoutes = map(following, (ParsedEdge next) -> cons(next, lookingEdge)); Queue<ListCons<ParsedEdge>> newqq = fold0(newRoutes, reduced.b, (Queue<ListCons<ParsedEdge>> qq, ListCons<ParsedEdge> nr) -> queue_enqueue(qq, nr)); Здесь нужно обратить внимание и на то, что WorldState реально описывает структуру данных, которую по спецификации получает наша entryPoint, и все остальные типы тоже соответствуют. Java тестировала все типы на компилируемость, а мой компилятор уже компилировал просто текст, используя типы даже без женериков (лишь кое где в сложных выражениях приходилось аннотировать (добавлять class cast) типы напрямую). Отчёт от broxТак уж вышло, что задание главного раунда чудесным образом делилось на 2 независимые части. Поскольку над лямбда-ботом вовсю пыхтели sanny & tilarids, логично было мне и rst7 заняться привидениями. Почему логично? Для rst микроконтроллеры и ассемблер - повседневная работа, а для меня - старые добрые времена. Сперва ZX Spectrum, потом заполонившие все советские журналы самодельные компы на 580-й серии, потом Commodore 64, демосцена и, наконец, Hugi code optimization compo. В сравнении с SECD процессором лямбда-бота, наш проц выглядел просто чудом совершенства - необходимый минимум инструкций, отличная модель памяти с разнообразной адресацией. Потратив совсем немного времени, мы быстро изобрели колесо стек вместе со всеми сопутствующими плюшками - call, ret, push, pop. Сделали символьные метки (а также полезные прибамбасы вроде jmp $+2). Полноценный препроцессор/ассемблер сделал для нас svg на джаве. Это хорошая часть. В глубокий пессимизм ввергал тот факт, что у нашего целевого процессора 256 байт памяти, что ставило жирный крест на всех умных алгоритмах поиска пути. Осознав это, мы начали выдавать на-гора всевозможные глупые алгоритмы. Базовых идей было 2. 1. Бот-патруль. Мы быстро сварганили бота, который умел ходить по правилу правой/левой руки вокруг замкнутой области. На это уходит всего 7 инструкций процессора: int 3 int 6 mov A, B inc A and A, 3 int 0 hlt Проблема была в том, что на классической карте рядом со стартовой позицией привидений охранять нечего. MadHatter взялся модифицировать патруль, чтобы он сперва отходил подальше, а затем уже наворачивал круги 2. Бот-охотник. Два варианта этого мы с rst и подготовили к завершению. Я начал с того, что просто вычислял наилучшее направление на лямбда-бота по разнице координат (по квадрантам). Менял направления только на перекрестках. И если наилучшее направление оказывалось недоступным (стена или запрещенный разворот назад), то выбирал лучшее из оставшихся. Этот алгоритм работал вполне неплохо и съедал 3 жизни нашего лямбда бота, давая тому прожить 20000 тактов и за это время набрать порядка 1000 очков. Ближе к завершению третьего дня svg подбросил идею “целиться с упреждением”. То есть мы запоминали старое положение лямбда-бота, читали его новую позицию и целились вдоль его вектора движения. Величину упреждения я потьюнил на наших собственных ботах, имевшихся на тот момент. Прослеживался четкий экстремум, если целить на 3 шага вперед. Оный ghost и был засабмичен. А также туда добавили элемент “грязной игры” - в промежутках между перекрестками я запускал генератор случайных чисел, и обращался к случайной ячейке карты. И все это с особым цинизмом зациклено - выход по исчерпанию лимита в 1024 инструкции. Не знаю, были ли такие команды, кто сделал полноценную эмуляцию GHC на GCC, но мы постарались осложнить им жизнь, как могли. Про bkg.pngЗа 5 дней до начала соревнования brox нашел, что в bkg.png (картинке которая использовалась для фона на странице-объявлении об ICFPC) закодирована секретная информация (картинка ниже). Если ее сделать более видимой, то получается такая картинка (обратить внимание на бордюр толщиной в 1 пиксель). Короче, мы ее расшифровать не смогли, хотя бились целый день, а в конце орги сказали что это рандом. Они редиски, чтобы не сказать значительно хуже. |
