Ну вот, он и завершился. Первое, что хочу сказать - было круто. Большое спасибо моим товарищам по команде - swizard, sectoid и grep-z. В позапрошлом году участвовали мы на пару с swizard'ом, а прошлогодний я конкретно прослоупочил. Помня контест 2012 года, подумали, что неплохо бы ещё рабочих рук и светлых голов и потому кинули объяву. На которые откликнулись sectoid и grep-z.
В этом году нужно было программировать поведение пакмана в одноименной игре и поведение приведений, которые за этим пакманом гоняются и хотят его съесть. Код пакмана нужно было написать на ассемблере некой лямбда машины, приведённой в спецификации, а для привидений на обычном трушном ассемблере. Кстати, орги назвали пакмана лямбда-меном, а его управляющую часть "General Computing Processor" (GCC). Привидения так привидениями и остались, а их управляющая часть "GHost Cpu" (GHC). Что как бы намекает, но по смыслу наоборот. :)
Орги выкладывали спецификацию частями. Для молниеносного раунда нужно было лишь подготовить программу на GCC. При этом в спецификации встречались некоторые входные параметры, помеченные как "undocumented". "Это неспроста", - подумали мы, поэтому отреверсили их в эмуляторе и получили, что там находится код для гостов (првидений). Понятно было, что наш пакман обладает способностью анализировать гостов, предсказывать их и на этом строить свою стратегию. Это было круто, конечно, но... :)
В общем, как получили задание, так сразу решили написать транслятор некоего лиспа, который мы назвали "intermediate lisp", в код GCC. Не обошлось без багов, например, путали порядок аргументов во фрейме и то, как они располагаются в стеке. Но обошлось. Стратегией сразу занялся swizard и заключалась она в том, чтобы всё жрать, а от гостов бегать. Собственно, где-то такое решение и засабмитили на лайтнинг. Хотя, теперь могу ошибаться. :)
Как завершился лайтнинг раунд, орги добавили дополнительную спецификацию, где и раскрывались "undocumented" который мы уже, в принципе, и знали. Сразу сели и подумали по нашим ограничениям. Размер программы гостов содержал максимум 256 инструкциий, а врмя на выполнение ограничивало его на 1024 инструкции. Поэтому делать что-то сложное для них теряло смысл. Решили сконцентрироваться на пакмане.
Но пакманом плотно занимался swizard, за транслятор плотно засел sectoid. Витало несколько идей - трансляции ilisp в common lisp, чтобы можно было отлаживаться и другая - трансляции common lisp в ilisp, чтобы тоже можно было отлаживаться. Пытались реализоваться оба варианта, но победил последний. Правда, как высказался swizard, наверное, имело смысл сделать транслятор сразу в GCC.
В общем, чтобы не мешаться, мы с grep-z решили накидать какой-нибудь простой алгоритм для гостов. И тут меня почему-то торкнуло, что надо реализовать волновой алгоритм поиска пути. Товарищ grep-z же решил, что надо попробовать тупо простое сближение. При простом сближении госты тупо застревали на стандартной карте, пока рядом не пробегал пакман. Закончив волновой алгоритм, обнаружилось, что он не укладывается в 1024 инструкции выполнения. Тогда я придумал ещё одну хитрю вещь - на одном запуске GHC исполнять часть алгоритма, на другом - другую часть и т.д. Но боты так не могли долго принять решение и я от этой затеи отказался. :)
Время уже поджимало, долго возились с транслятором и компилятором. Я начал читать какие ещё есть алгоритмы поиска пути. В итоге просто решил запоминать тупиковые клетки и туда не ходить. При этом если клетка граничила с другим тупиком, то там тоже считалось, что хода нет. В итоге родился гост, который преследовал пакмана. Нашли ссылку про стандартное поведение гостов в классическом пакмане и тогда я добавил ещё одного госта, который идёт на опережение на 4 клетки с пакманом, а при расстоянии меньшем переключается на преследование. И в финальный сабмишн ушло два этих госта. Сюда компилятор не писали, испугались ограничений. :) Вместо этого написали некое подобие макроассемблера.
Но программировать на нём - всё равно АДъ!
Что же было не так? Всё же, не хватало знаний по лямбда исчислению. Незнание современных методов поиска пути тоже удручало. Думаю, что надо было попытаться сделать компилятор. Не знаю пока, уложились бы мы с этим компилятором в 256 байт, но повторюсь, это АДъ! Хотя, как привыкнешь, вроде обыденно. Постоянно нас преследовали какие-то ошибки в трансляторе GCC. Вместо отладки ИИ занимались правкой багов.
Что же было отлично? Common Lisp! Хотя, в последнее время я программировал на clojure, но Common Lisp чертовски приятен тоже. Технологично - язык получился hosted и пакмана разрабатывать было хорошо. Хорошая команда. Надеюсь, в следующем году мы точно победим! :)
В этом году нужно было программировать поведение пакмана в одноименной игре и поведение приведений, которые за этим пакманом гоняются и хотят его съесть. Код пакмана нужно было написать на ассемблере некой лямбда машины, приведённой в спецификации, а для привидений на обычном трушном ассемблере. Кстати, орги назвали пакмана лямбда-меном, а его управляющую часть "General Computing Processor" (GCC). Привидения так привидениями и остались, а их управляющая часть "GHost Cpu" (GHC). Что как бы намекает, но по смыслу наоборот. :)
Орги выкладывали спецификацию частями. Для молниеносного раунда нужно было лишь подготовить программу на GCC. При этом в спецификации встречались некоторые входные параметры, помеченные как "undocumented". "Это неспроста", - подумали мы, поэтому отреверсили их в эмуляторе и получили, что там находится код для гостов (првидений). Понятно было, что наш пакман обладает способностью анализировать гостов, предсказывать их и на этом строить свою стратегию. Это было круто, конечно, но... :)
В общем, как получили задание, так сразу решили написать транслятор некоего лиспа, который мы назвали "intermediate lisp", в код GCC. Не обошлось без багов, например, путали порядок аргументов во фрейме и то, как они располагаются в стеке. Но обошлось. Стратегией сразу занялся swizard и заключалась она в том, чтобы всё жрать, а от гостов бегать. Собственно, где-то такое решение и засабмитили на лайтнинг. Хотя, теперь могу ошибаться. :)
Как завершился лайтнинг раунд, орги добавили дополнительную спецификацию, где и раскрывались "undocumented" который мы уже, в принципе, и знали. Сразу сели и подумали по нашим ограничениям. Размер программы гостов содержал максимум 256 инструкциий, а врмя на выполнение ограничивало его на 1024 инструкции. Поэтому делать что-то сложное для них теряло смысл. Решили сконцентрироваться на пакмане.
Но пакманом плотно занимался swizard, за транслятор плотно засел sectoid. Витало несколько идей - трансляции ilisp в common lisp, чтобы можно было отлаживаться и другая - трансляции common lisp в ilisp, чтобы тоже можно было отлаживаться. Пытались реализоваться оба варианта, но победил последний. Правда, как высказался swizard, наверное, имело смысл сделать транслятор сразу в GCC.
В общем, чтобы не мешаться, мы с grep-z решили накидать какой-нибудь простой алгоритм для гостов. И тут меня почему-то торкнуло, что надо реализовать волновой алгоритм поиска пути. Товарищ grep-z же решил, что надо попробовать тупо простое сближение. При простом сближении госты тупо застревали на стандартной карте, пока рядом не пробегал пакман. Закончив волновой алгоритм, обнаружилось, что он не укладывается в 1024 инструкции выполнения. Тогда я придумал ещё одну хитрю вещь - на одном запуске GHC исполнять часть алгоритма, на другом - другую часть и т.д. Но боты так не могли долго принять решение и я от этой затеи отказался. :)
Время уже поджимало, долго возились с транслятором и компилятором. Я начал читать какие ещё есть алгоритмы поиска пути. В итоге просто решил запоминать тупиковые клетки и туда не ходить. При этом если клетка граничила с другим тупиком, то там тоже считалось, что хода нет. В итоге родился гост, который преследовал пакмана. Нашли ссылку про стандартное поведение гостов в классическом пакмане и тогда я добавил ещё одного госта, который идёт на опережение на 4 клетки с пакманом, а при расстоянии меньшем переключается на преследование. И в финальный сабмишн ушло два этих госта. Сюда компилятор не писали, испугались ограничений. :) Вместо этого написали некое подобие макроассемблера.
Но программировать на нём - всё равно АДъ!
Что же было не так? Всё же, не хватало знаний по лямбда исчислению. Незнание современных методов поиска пути тоже удручало. Думаю, что надо было попытаться сделать компилятор. Не знаю пока, уложились бы мы с этим компилятором в 256 байт, но повторюсь, это АДъ! Хотя, как привыкнешь, вроде обыденно. Постоянно нас преследовали какие-то ошибки в трансляторе GCC. Вместо отладки ИИ занимались правкой багов.
Что же было отлично? Common Lisp! Хотя, в последнее время я программировал на clojure, но Common Lisp чертовски приятен тоже. Технологично - язык получился hosted и пакмана разрабатывать было хорошо. Хорошая команда. Надеюсь, в следующем году мы точно победим! :)
Комментариев нет:
Отправить комментарий