ICFPC-2011: Хроники пикирующего робота
Они заряжают пушку!
Зачем? Они будут стрелять!
В кого? В нас!
Продолжение. Начало здесь.
Команда
В этот раз я не собирался созывать команду программистов со всего города, а захотел ограничиться родной конторой. Записалось четверо, но в конце концов из них остался только старый олимпиадный товарищ Максим (mihmax).
В прошлые годы нам сильно не хватало математиков, поэтому в этом году мы привели аж двоих - Леонида (без ЖЖ) и nushasmall.
Мы с Максимом решили писать на родном Groovy, на котором пишем уже 2 года. Добавили к нему Groovy++, чтобы оно компилировалось так же эффективно, как Java (и оно так и было! правда, не без странных ошибок)
О лямбда-исчислении мы знали только эмпирическое определение лямбда-функции, но в прошлые года это было неважно.
В этом году всё было не так.
Что мы имеем
Орги выдали программу LtG, моделирующую игру. Она умела играть "солитёром" - одним игроком, выполняя команды в консоли; или запускать одну программу против другой, и показывать состояние игрового поля.
Наша программа отдаёт команды "примени функцию(карту) к ячейке поля" или "примени значение ячейки к карте", и принимает ходы противника через ту же консоль.
Чтобы знать состояние игры, надо самому его моделировать. Применять любую часть программы LtG в своём продукте запрещено.
Сам набор функций - это эдакий "ассемблер лямбда-исчисления", а конкретнее - исчисления SKI-комбинаторов. Из команд этого "ассемблера" и предстояло строить программу, которая убьёт оппонента.
Если Вы не знакомы с задачей, то, чтобы читать дальше, откройте, наверное, справочник карт LtG в соседнем окне браузера :)
Мы поняли:
Орги запустили неофициальный тестовый сервер. Туда можно было сабмитить ботов и смотреть результаты.
Чтобы попасть в топ30, сначала хватало 18 побед из 30, потом 21, потом 22 оказались под вопросом. Мы бултыхались где-то в полупроходниках - от 20 до 24 побед, между 50 и 20 местами, один раз выскочили аж на 7-е.
В официальном соревновании правила немного другие: ранжируют по очкам, причём победа по очкам, в конце партии (100000 ходов) даёт 2 очка, а нокаутом, за досрочно полностью убитого врага - 6.
Мы на это нацелились.
Стратегии
Для начала, конечно, нужно научиться стрелять. Нам нужна пушка!
Не снявши 10 тыс. хитов с (хотя бы одной) ячейки оппонента, мы не победим!
Первую половину дня, не будучи специалистами в теории функционального программирования, мы пытались понять условие.
Максим сначала написал "попугая" - бота, который тупо повторяет команды противника. В первый день мало кто его победил :D
Андрей и Леонид занялись вопросом - как убить противника.
Леонид на программе организаторов моделировал разные функции и эмпирически строил теорию SKI-исчисления.
Я засел за моделирование предметной области.
К вечеру Андрей и Максим вручную на доске составили дерево функции, а по нему последовательность из 45 команд, за счёт здоровья 1 и 2 нашей ячейки быстро (в 45 ходов) убивающую 0-ю (важнейшую!) ячейку противника.
Функцию назвали "раш" в честь популярного приёма в стратегических играх - быстро убить стратегически важный объект, даже в ущерб себе. Мы убивали эту ячейку за счёт 16000 здоровья собственных 1-й и 2-й ячейки, не отвлекаясь на их лечение.
Все пришли к выводу, что, чтобы построить что-то сложное - например, пушку, которая стреляет зомбём, который потом на территории врага раскручивает бесконечный цикл с убийством - нужен автоматический планировщик. Очевидно, что здесь надо вывести правила компиляции из понятного нам языка в SKI-формулы LtG.
Второй день
Максим написал в Груви DSL для LtG - чтобы команды LtG можно было писать прямо в Груви в виде S(K(attack),get).
Собрал из этого бота, который понимает команды противника, и выдаёт наши команды уже осмысленно, и воплотил на нём наш "раш-45" - раш на 0 ячейку в 45 команд. Потом поддерживал её в убитом состоянии dec()-ами :D
Использовал при этом юнит-тесты с полной моделью игры. Тесты работали :)
Этот бот работал на тестовом сервере ещё целые сутки и показал себя неплохо - делал 18 побед из 30 матчей. Видимо, 18 из 30 противников не умели оживлять 0 ячейку или не читали её состояние.
На jabber.ru пробежало сообщение, что кто-то умеет убивать полностью за 1600 ходов.
Потом Максим засел за универсальный планировщик задачу и провёл над ней сутки.
(Максим: в итоге сделать его универсальным я так и не смог, но выдохся на нём изрядно. В общем, ИМХО, зря потратил время и вдохновение - ибо эффективный раш мы составили без планировщика, а нашего простого зомби можно было бы составить и ручками).
Я закончил модель игры и перешёл к своей идее-фикс - ИИ (Искусственному Идиоту), который играл бы по нескольким стратегиям.
Математики строили частные и общие случаи полезных функций.
На jabber.ru пробежало сообщение, что кто-то умеет убивать полностью за 900 ходов.
Третий день
Нашего "бота-45" укатали за 360 ходов.
Андрей оптимизировал "раш" на "ассемблере" с 45 команд до 42. Я его подключил к ИИ.
К середине третьего дня, когда подходил срок личного таймбокса Максима для "универсального компилятора формул", он совсем собрался бросить эту затею. Но тут снова пришёл Леонид, и рассказал, как по формуле построить её "предка" - формулу, которая даст искомую, если её применить к zero.
Это, увы, оказалось не общее решение - но достаточно хорошее, чтобы строить не очень сложные формулы. Второй параметр функций S(),attack(),help() не должен был иметь более 2 уровней вложенности.
Короче, наш главный фейл: не зная лямбда-исчисления, мы не сумели скомпилировать произвольную программу в LtG-функцию, а ограничились написанием мелких частных стратегий на "ассемблере" в юнит-тестах.
Убер-пушка, или вундервафля
Две "пушки" мы смогли привести к специальному виду, пригодному для компилятора, и одну из них вечером третьего, последнего, дня, таки всандалили в список стратегий ИИ.
Противопехотный пулемёт
А чтобы выносить мелочь, "единички", которые появляются, когда противник оживляет (revive()) ячейку, нужен или пулемёт - стратегия, которая быстро делает им dec() обратно в 0, - или нацеливаемая по адресу пушка, формулу которой не надо каждый раз составлять заново.
Санитары
Jesus saves.
So should you
Руководство пользователя
Это жизнь. Вернее, это игра.
Но в ней будут убивать - то есть, нам будут убивать ячейки.
Значит, надо им хотя бы делать revive() (оживлять с 1 хитом), не говоря о help() (переливать хиты из здоровой ячейки). Ну, help() денег стоит, а revive() делается быстро и просто.
Думаю, это "упрямство" нам здорово помогло: наша программа во многих случаях просто "отказывалась умирать" и упорно оживляла ячейки. Многие матчи с топовыми командами заканчивались со счётом 256:256 - то есть, все живые :)
Искусственный Идиот в итоге научился:
На тестовом сервере мы начали убивать противников в 0 за десяток тысяч тиков.
На jabber.ru пробежало сообщение, что кто-то убивает за 200 ходов.
Мы делаем примерно 22 победы из 30. При этом одна противная команда Unagi the Gathering вызывает падение нашей программы и нам третий раз засчитывают техническое поражение.
По ходу дела
(писать в stdout нельзя - сервер не поймёт вывод программы и засчитает техническое поражение. Мы как-то полтора часа одну такую шнягу ловили)
...сбросил на телефоне звонок от жены. Это хуже, чем писать в stdout.
...(третья доставка за два дня):
- Вам наша пицца нравится, да?
- Очень кушать хочется!
(человек потерял файл, который засабмитил на официальный сервер. При сабмите записывают sha512 файла, а он хочет переложить его заново. Орги ему отвечают - пожалуйста, но сумма должна совпадать)
...теперь у вас неделя на взлом sha512.
Окончание следует.
Зачем? Они будут стрелять!
В кого? В нас!
Продолжение. Начало здесь.
Команда
В этот раз я не собирался созывать команду программистов со всего города, а захотел ограничиться родной конторой. Записалось четверо, но в конце концов из них остался только старый олимпиадный товарищ Максим (mihmax).
В прошлые годы нам сильно не хватало математиков, поэтому в этом году мы привели аж двоих - Леонида (без ЖЖ) и nushasmall.
Мы с Максимом решили писать на родном Groovy, на котором пишем уже 2 года. Добавили к нему Groovy++, чтобы оно компилировалось так же эффективно, как Java (и оно так и было! правда, не без странных ошибок)
О лямбда-исчислении мы знали только эмпирическое определение лямбда-функции, но в прошлые года это было неважно.
В этом году всё было не так.
Что мы имеем
Орги выдали программу LtG, моделирующую игру. Она умела играть "солитёром" - одним игроком, выполняя команды в консоли; или запускать одну программу против другой, и показывать состояние игрового поля.
Наша программа отдаёт команды "примени функцию(карту) к ячейке поля" или "примени значение ячейки к карте", и принимает ходы противника через ту же консоль.
Чтобы знать состояние игры, надо самому его моделировать. Применять любую часть программы LtG в своём продукте запрещено.
Сам набор функций - это эдакий "ассемблер лямбда-исчисления", а конкретнее - исчисления SKI-комбинаторов. Из команд этого "ассемблера" и предстояло строить программу, которая убьёт оппонента.
Если Вы не знакомы с задачей, то, чтобы читать дальше, откройте, наверное, справочник карт LtG в соседнем окне браузера :)
Мы поняли:
- что бить надо attack()-ом, который, однако, стоит ещё больше своего здоровья;
- что перед этим желательно повысить здоровье своей ячейки функцией help();
- бывает бесконечный цикл - это мы узнали вечером первого дня из намёков на jabber.ru, а потом и прочитали в правилах :)
- что zombie(), в руках которого help, attack и inc/dec приносят "владельцу" только вред, надо запускать, и желательно - с бесконечным циклом;
- что всё это - дело долгое: чтобы сформировать мало-мальски разумную команду в ячейке, нужны десятки ходов;
- что dec(), уменьшающий здоровье одной ячейки врага на 1, полезен редко - 256 ячеек по 10K здоровья он будет выбивать долго. Хотя...
- важно, что применять можно только карту (элементарную функцию) к ячейке или наоборот. Нельзя применить одну составную функцию из ячейки к другой ячейке;
- накопленную в ячейке функцию можно запустить, применив её к карте zero, и тогда I() превратится в константу 0, а succ() - в 1;
- очень важны нулевая и первая ячейки. Только из них наш набор функций может легко взять значение. Например, аргумент get(x) - это номер ячейки, из коотрой уже будет взято значение. А одной картой мы можем задать индекс ячейки только как zero() или succ(x) (помните, мы запускаем функцию, применёё её к карте zero?).
Орги запустили неофициальный тестовый сервер. Туда можно было сабмитить ботов и смотреть результаты.
Чтобы попасть в топ30, сначала хватало 18 побед из 30, потом 21, потом 22 оказались под вопросом. Мы бултыхались где-то в полупроходниках - от 20 до 24 побед, между 50 и 20 местами, один раз выскочили аж на 7-е.
В официальном соревновании правила немного другие: ранжируют по очкам, причём победа по очкам, в конце партии (100000 ходов) даёт 2 очка, а нокаутом, за досрочно полностью убитого врага - 6.
Мы на это нацелились.
Стратегии
Для начала, конечно, нужно научиться стрелять. Нам нужна пушка!
Не снявши 10 тыс. хитов с (хотя бы одной) ячейки оппонента, мы не победим!
Первую половину дня, не будучи специалистами в теории функционального программирования, мы пытались понять условие.
Максим сначала написал "попугая" - бота, который тупо повторяет команды противника. В первый день мало кто его победил :D
Андрей и Леонид занялись вопросом - как убить противника.
Леонид на программе организаторов моделировал разные функции и эмпирически строил теорию SKI-исчисления.
Я засел за моделирование предметной области.
К вечеру Андрей и Максим вручную на доске составили дерево функции, а по нему последовательность из 45 команд, за счёт здоровья 1 и 2 нашей ячейки быстро (в 45 ходов) убивающую 0-ю (важнейшую!) ячейку противника.
Функцию назвали "раш" в честь популярного приёма в стратегических играх - быстро убить стратегически важный объект, даже в ущерб себе. Мы убивали эту ячейку за счёт 16000 здоровья собственных 1-й и 2-й ячейки, не отвлекаясь на их лечение.
Все пришли к выводу, что, чтобы построить что-то сложное - например, пушку, которая стреляет зомбём, который потом на территории врага раскручивает бесконечный цикл с убийством - нужен автоматический планировщик. Очевидно, что здесь надо вывести правила компиляции из понятного нам языка в SKI-формулы LtG.
Второй день
Максим написал в Груви DSL для LtG - чтобы команды LtG можно было писать прямо в Груви в виде S(K(attack),get).
Собрал из этого бота, который понимает команды противника, и выдаёт наши команды уже осмысленно, и воплотил на нём наш "раш-45" - раш на 0 ячейку в 45 команд. Потом поддерживал её в убитом состоянии dec()-ами :D
Использовал при этом юнит-тесты с полной моделью игры. Тесты работали :)
Этот бот работал на тестовом сервере ещё целые сутки и показал себя неплохо - делал 18 побед из 30 матчей. Видимо, 18 из 30 противников не умели оживлять 0 ячейку или не читали её состояние.
На jabber.ru пробежало сообщение, что кто-то умеет убивать полностью за 1600 ходов.
Потом Максим засел за универсальный планировщик задачу и провёл над ней сутки.
(Максим: в итоге сделать его универсальным я так и не смог, но выдохся на нём изрядно. В общем, ИМХО, зря потратил время и вдохновение - ибо эффективный раш мы составили без планировщика, а нашего простого зомби можно было бы составить и ручками).
Я закончил модель игры и перешёл к своей идее-фикс - ИИ (Искусственному Идиоту), который играл бы по нескольким стратегиям.
Математики строили частные и общие случаи полезных функций.
На jabber.ru пробежало сообщение, что кто-то умеет убивать полностью за 900 ходов.
Третий день
Нашего "бота-45" укатали за 360 ходов.
Андрей оптимизировал "раш" на "ассемблере" с 45 команд до 42. Я его подключил к ИИ.
К середине третьего дня, когда подходил срок личного таймбокса Максима для "универсального компилятора формул", он совсем собрался бросить эту затею. Но тут снова пришёл Леонид, и рассказал, как по формуле построить её "предка" - формулу, которая даст искомую, если её применить к zero.
Это, увы, оказалось не общее решение - но достаточно хорошее, чтобы строить не очень сложные формулы. Второй параметр функций S(),attack(),help() не должен был иметь более 2 уровней вложенности.
Короче, наш главный фейл: не зная лямбда-исчисления, мы не сумели скомпилировать произвольную программу в LtG-функцию, а ограничились написанием мелких частных стратегий на "ассемблере" в юнит-тестах.
Убер-пушка, или вундервафля
Две "пушки" мы смогли привести к специальному виду, пригодному для компилятора, и одну из них вечером третьего, последнего, дня, таки всандалили в список стратегий ИИ.
Противопехотный пулемёт
А чтобы выносить мелочь, "единички", которые появляются, когда противник оживляет (revive()) ячейку, нужен или пулемёт - стратегия, которая быстро делает им dec() обратно в 0, - или нацеливаемая по адресу пушка, формулу которой не надо каждый раз составлять заново.
Санитары
Jesus saves.
So should you
Руководство пользователя
Это жизнь. Вернее, это игра.
Но в ней будут убивать - то есть, нам будут убивать ячейки.
Значит, надо им хотя бы делать revive() (оживлять с 1 хитом), не говоря о help() (переливать хиты из здоровой ячейки). Ну, help() денег стоит, а revive() делается быстро и просто.
Думаю, это "упрямство" нам здорово помогло: наша программа во многих случаях просто "отказывалась умирать" и упорно оживляла ячейки. Многие матчи с топовыми командами заканчивались со счётом 256:256 - то есть, все живые :)
Искусственный Идиот в итоге научился:
- переключаться между несколькими стратегиями;
- определять, что стратегия сломалась, и выбрасывать/перезапускать её;
- восстанавливать некоторые стратегии не с начала, а с последнего нужного шага;
- выбирать наиболее приоритетную стратегию простой эвристикой в таком порядке:
- раш,
- оживление своих 0-4 ячеек,
- добивание чужой ячейки с 1-2 хитами,
- и примитивный цикл с dec() на вражескую 0 ячейку;
- хотел ещё научить его анализировать активность, длину и опасность формул во вражеских ячейках, и поворачивать туда пушку (когда ребята её достроят), но этого мы не успели./li>
- И ещё было много хороших и простых идей, которые мы тоже не успели воплотить.
На тестовом сервере мы начали убивать противников в 0 за десяток тысяч тиков.
На jabber.ru пробежало сообщение, что кто-то убивает за 200 ходов.
Мы делаем примерно 22 победы из 30. При этом одна противная команда Unagi the Gathering вызывает падение нашей программы и нам третий раз засчитывают техническое поражение.
По ходу дела
(писать в stdout нельзя - сервер не поймёт вывод программы и засчитает техническое поражение. Мы как-то полтора часа одну такую шнягу ловили)
...сбросил на телефоне звонок от жены. Это хуже, чем писать в stdout.
...(третья доставка за два дня):
- Вам наша пицца нравится, да?
- Очень кушать хочется!
(человек потерял файл, который засабмитил на официальный сервер. При сабмите записывают sha512 файла, а он хочет переложить его заново. Орги ему отвечают - пожалуйста, но сумма должна совпадать)
...теперь у вас неделя на взлом sha512.
Окончание следует.