Monday, June 27, 2011

ICFP 2011 результаты

Объявили результаты первого рауна ICFP 2011. Мы с треском провалились заняв 74-е место из 199 комманд, которые засабмитили результат.

Monday, June 20, 2011

ICFP 2011

День нулевой - начало

В четверг в пять часов вечера мы собрались прочитать и обсудить условия задачи. Нас было пятеро: Пол, Ждей, Кирил, Кирил и я. Вася должен был подключиться удаленно попоже, у него в Киеве была ещё ночь. Нашли свободный офис с четырьмя досками и начали разбираться. За первый час мы только успели немного понять условия задачи. Каждый читал и потом обсуждали правильно ли поняли какие то условия. Обсуждение вели на английском языке, что было не совсем просто. Но учитывая что только трое из нас разговаривали на русском - выхода не было.

Из языков мы планировали использовать C++ и возможно C#. Ещё подумывали о Python-е если понадобится. Забегая вперед скажу, что получилось совсем не так как ожидали. Мы ещё успели до этого установить виртуальные машины с Debian, создать репозиторий на Bitbucket и создать сайт на amazon, с которого сабмитили результат. Как бы мы не любили git, но бесплатного сервиса с закрытым доступом мы не нашли. А bitbucket.org предоставляет возможность использовать Mercurial для закрытыех проектов.

Что бы разобраться с задачей я решил написать прототип эмулятора логики LTG на lua. Этот язык я знаю хорошо и за счет своей простоты и динамической типизации позволяет писать код очень быстро. Через час у меня уже работала большая часть комманд и можно было прогнать тесты указаные в примере к задаче. Появилось более полное понимание задачи. В четверг решили долго не засиживаться и пойти по домам - так что разошлись около 8-9 часов.

Мы с Кирилом ещё пошли дернуть пивка и пообсуждать задачу. Были идеи что функции в условии - слишком нискоуровневые, А надо придумать высокоуровневый язык который уже преобразовывать в нужные компоненты. Что то типа асемблера против С++. Ещё Кирил предложил использовать генетический алгоритм, что бы создавать стратегии. Долго не сидели и пошли домой. И до двух ночи я читал википедию и другие сайты по лямбда и SKI исчеслению. Лаг спать когда прочитал про Y-комбинатор и ничего не понял, прочитал и опять ничего не понял;)

День первый

В пятницу у меня было важное совещание в 10:30, но после него я решил взять отгул, что бы потратить все время на контест. Утром когда проснулся меня осенило как можно создавать любые числа путем инкрамента и умножения на 2. Я быстро написал генератор представлений в SKI исчислении указаном в задаче. Сделал я это канечно же тоже на lua, так как быстрее было. Понял, что для больших чисел надо много операций. Пытался понять можно ли как то сложить два числа собранных в разных ячейках, но это оказалось невозможным. Пошел в офис.

Кирил, Пол и Джей обсуждали стратегии и саму задачу. Джей начал писать интерпретатор, который бы мы смогли использовать на C# (mono) в финальной программе. Пол делал саму программу которая бы взаимодействовала с тестером. В это время я и Кирил пытались разобраться с математикой, он уже реализовал интерпретатор игры на python. Ему было проще работать с питоном как мне с lua.

Мы не могли понять как передавать второй аргумент функции. Как имея в ячейке x(y), где x уже сложная функция, применить к у функцию z, что бы получилось x(z(y)). В этом была загвоздка. Я написал на луа брутафорсер, который бы переберал всевозможные варианты операций и смотрел получили ли мы нужную функцию. Пришлось даже перейти на luajit что бы оно работало быстрее. Но в общем почти весь день ушел в пустую - мы никак не продвинулись на 8 часов вечера.

И тут Кирил нашел в сети способ как можно изменить второй аргумент. Для этого надо было бы просто создать его в нулевой ячейке и применить слева K, потом S, а потом справа get и справа zero. Это был прорыв.

К этому моменту Пол сделал тупого бота, который повторяет действия оппонента и засабмитил его на тестовый сервер. Вел себя он не очень, но это было только начало. Потом пошли модификации бота в сторону использования dec много раз что бы убить ячейку оппонента.

Но что бы убивать ячейку быстро надо было что то придумать получше. Мы с Кирилом обсуждали много вариантов иногда даже срывались на мат русский язык в объяснениях. Кирил нашел в сети программу на haskel для преобразований лямбда выражений - но она не особо помогла нам.

Списался с Васей, он был на работе и обещал присоеденится в суботу с утра, когда прийдет домой.

Появыилось мнение, что нас спасет Y-комбинатор. Было уже очень поздно и все разошлись по домам, но мы с Кирилом остались и продолжили мозговой штурм. К трем часам ночи у нас появился вариант как использовать Y-комбинатор, что бы наносить много урона за раз. Прийнялись его переводить в комманды к тестовой программе руками. Исписали всю доску, вбили в интерпретатор Кирила, но оно не работало. То что было в википедии - Y-комбинатор в SKI - выдавало ошибку. Мы не могли понять почему. Кирил реализовал факториал в python-е при его помощи. Все было ок, но если взять и использовать Y взятый с вики - не получалось. Внесли в код новую карту Y - которая реализовывала Y-комбинатор и карту F - факториал. Запустили - все было ок. Но SKI функция не работала.

В общем в 4 часа ночи пошли по домам. Но на этом ещё не закончился день. Мы с Кирилом списались в google talk и продолжили работу. Попытались преобразовать лямбда выражение Y-комбинатора в SKI вручную, но было очень тяжело - получалось очень большое выражение. И я где-то доспустил ошибку. Кирил сделал тоже самое при помощи haskel программы - но тоже безрезультатно. Я подумал что надо автоматизировать преобразование лямбды в SKI и прогнать через Y-комбинатор. Начал реализацию, но довел только до половины. 20 часов на ногах. 18 из них программирования и мозгового шторма были очень утомляющими. Пошел спать.

Если подсумировать - то мы по факту ничего не добились. В этот момент мы должны бы были уже все проблемы решить, работать над стратегиями, учитывать действия оппонента и тд.

День второй

Поспав 4 часа я проснулся, принял душ и пошел в офис. Мне надо было в 12 часов уехать на два часа в сервисный центр на плановый техосмотр машины. Поэтому терять время было нельзя.

Я почти доделал преобразователь λ в SKI и поехал в сервисный центр. Пока ждал - дописал, создал Y-комбинатор, который работает. Но он оказался очень большим. Преобразовать его в комманды к игровому серверу было нереально. Поэтому решил написать компилятор SKI в последовательность комманд. По началу казалось легкой задачей, но на создание нормального плана выполнения с оптимизациями типа - реюза уже просчитаных подвыражений у меня ушло около 6 часов. Но эта штука должна была быть очень полезной.

В это время Пол реализовал интерпретатор в своем приложении и засубмитил его на сервер. Он плотно работал с Кирилом - внося новые и новые типы аттак и тестируя их с реальными противниками. У Джея были проблемы с его интерпретатором, поэтому Пол сделал на скорую руку свой. Он был не шибко продвинутым, но позволял понять ситуацию на поле боя.

В то же время Кирил очень неплохо продвинулся. После того как научились делать атаку и безконечного цикла (который прерывался по лимиту действий, но урон оставался), стало возможным сделать продвинутые типы атак, которые выносят ячейки противника намного быстрее. В поединках мы видели, что у многих людей результаты лучше. До этого выигрывали порядка 20-30% матчей, после реализации рекурсивной атаки - около 40%. Тратили на это все 100000 ходов, ни разу не выигрывали досрочно.

Мы были шокированы когда нас оппонент убил за 123 хода. У нас только что бы собрать первую функцию атаки уходило около 200 ходов. А тут все 256 ячеек были убиты за это число ходов. Мы канечно понимали в чем дело - только оружие массового поражения могло такое сделать;) Это канечно была карта zombie, но мы не умели ещё ею пользоваться. Наверняка мы не знали, но были уверены что это zombie.

К тому же Кирил придумал хитрый ход - убивать 0-ю ячейку противника в самом нечале. Это позволяло выиграть у противников, которые не умеют воскрешать ячейки. Эта ячейка самая важная, она нужна почти во всех операциях. Если вынести её раньше того как вынесут нашу ячейку - есть шанс выиграть у не очень умных ботов.

Когда я дописал компилятор SKI - то увидел, что Y-комбинатор в нем занимает 892 хода. Это слишком много, хотя это уже было понятно раньше. За время работы над компилятором я немного отстал от алгоритмов которые обсуждались и пришлось вникать во все что придумали за это время.

Кирил создал очень крутое оружие - rollingAttack - это аттака которая собиралась за 127 ходов и выносила 0-ю ячейку противника на следующем ходу. Она использовала функцию attack - нанося урон и нам, но использовались не очень важные 50 ячеек. И если он не умел воскрешать ячейки - мы оставляли его безоружным и довивали peckingAttack - просто заклевывали обычным dec-ом.

Дела уже были получше - у нас хотя бы был полноценный бот, который хоть и был туповатым, но выигрывал у ещё более тупых ботов. Было немного досадно, что дела идут не очень. И было уже понятно что сверх-умного бота со всякими стратегиями - мы уже не сделаем.

Но мы знали, что для успеха надо научится использовать zombie, который вызывает heal. И если бы мы его сделали - то могли бы даже попасть куда то ближе к первым 50 участникам.

Опять уже было поздно, но как и в прошлый день мы с Кирилом остались и продолжили обсуждать проблему с зомби.

Для решения перешли к λ виду выражений и написали функцию, которая должна была бы быть один раз созданой и вставлена в мертвую ячейку. Потом она бы убивала соседнюю ячейку и копировала бы себя туда. Идея была отличная. Тут нам пригодился преобразователь с λ в SKI. Дальше скомпилировали в последовательность команд и запустили в интерпретаторе кирила - все заработало. Но в эмуляторе от судьей - ожидаемого результата не было. Немного подумали и пошли спать - уже было около 3-4 часов утра.

Кстати у Васи появились внеплановые проблемы и он к нам не смог присоедениться. Так что нас было только пятеро.

День третий - финальный

Вставать было очень тяжело. Хоть конкурс и завершался в 5 часов вечера и надо было идти в офис - но я просто физически не мог проснуться. Пришел где то около часа дня. Камрады оптимизировали существующие типы атак. Решили не тратить время на зомби, а сконцентрироваться на уже сделаном и довести до ума.

Но тут оказалось, что интерпретатор Пола отваливается по лимиту CPU на тестовом сервере. Где ошибка найти он не мог.

У нас было ещё две реализации интерпретаторов на lua и python, но доводить их до ума за оставшееся время было нереально. Да ещё и чревато ошибками. Было принято решение воевать в слепую. Имея четкую последовательность ходов - просто применяем её и надеемся что сработает. Тоесть мы вообще в финальной программе не будем знать что происходит на поле.

А это значило, что мы не сможем воскрешать наши мертвые ячейки. Что ж печально. Мы были уверены что оно будет работать, но толи C# был не очень подходящим вариантом, толи реализация. К тому же C# реализация интерпретировала функции, а lua и python - использовали функциональщину для реализации логики.

Я был в этот момент не очень полезен, просто сидел с боку и помогал оптимизировать функции. Залили финальную версию, но до конца оставалось около полутора-двух часов.

Мы уже начали думать о том, как все таки можно было бы сделать зомбей - просто из интереса. Мы знали что даже если сделаем - лучше не рисковать включать в релиз.

Тут кирил попросил попросил посмотреть ещё раз можно ли соптимизировать клюющую атаку. Я построил λ выражение с новой идеей, перевел в SKI и скомпилировал, но получилось что мой вариант убивает одну ячейку за 400 ходов, а все ячейки противника за 123000 ходов. Что не особо лучше предидущей реализации.

Но я не здался и соптимизировал одну инструкцию. Получил при этом убийство ячейки за 123 хода, противника за 94288 ходов. Отлично, но до конца контеста - 30 минут. А у меня формула и комманды к интерпретатору в текстовом файле.

Я быстренько интегрировал в C# код и Пол залил на тестовый сервер. 15 минут до конца. А мы не уверены стоит ли перезаливать финальную ферсию новой. Потестили локально, выиграли два поединка и решили - включать. Было стремно, но получилось все таки намного лучше предидущего результата. Он выигрывает в 55% случаев.

Итоги

В общем это была отличная встряска. Получил неймоверное удовольствие от контеста. Я узнал много про функцилнальщину. Да и просто отлично провел время.

Жаль канечно, что не сделали зомби и что в финальной версии мы отключили интерпретатор логики.

Посмотрел на наш репозиторий, а там: C#, C++, Python, Haskel, Lua, Shell. Вот такой вот зоопарк.

UPD: Наша комманда называется ShallowEndians. Почитал я блоги других комманд. Многие додумались до рекурсивного зомби используя copy, а потом get. Черт, гениально и просто. А пока за ночь наш бот нарубил 50 противников из 85 дуэлей;)

Wednesday, June 8, 2011

Powershell cheatsheet

Useful powershell commands. Will update that list if i find something interesting.

tail -n 10 {filename}
get-content {filename} | select -last 10
gc {filename} | select -last 10
tail -f {filename}
get-content {filename} -wait
gc {filename} -wait
hostname
[System.Net.Dns]::GetHostName()