Домашний Holodeck

Попросили вытащить в паблик с моего приватного блога. Особо времени на редактирование нет, так что выкладываю "as is".

В пятницу пришел компьютер. Монитор и HTC Vive уже давно были дома. А вот посылка с системным блоком шла чуть дольше. Планировалось доставить в понедельник, но утром пятницы пришла смс что посылка уже на базе и я съездил и забрал ее. Я специально изменил доставку на базу FedEx, что бы они не пытались доставить мне домой пока я на работе. И тут такой сюрприз еще и до работы. Не сюрприз что я в пятницу scrum митинг пропустил и пришел на работу где то в 11:30. Ну и домой ушел в пол пятого.

В пятницу после работы я откалибровал комнату. Игровая площадка вышла где то 3 на 3 метра. Хотя в субботу я прикрутил базовые станции на стены и еще раздвинул мебель. В итоге получилось 3.6 на 3.6 метра. Что очень даже не мало. Я пробовал максимум получается 3.8 на 3.8. Но кабель от шлема уже чувствуется что натягивается так что я оставил квадрат в 3.6.

Я скачал множество бесплатный игр. И еще на $120 купил тех что либо очень рекомендовали, либо понравилось демо. Я забыл что на PC игры могут быть такие дешевые. На PS4 - одна игра либо 60 либо 30. Таких что бы были 5-10 и что бы я в них хотел играть - не попадалось.

Ну и впечатление от игр. Невероятно! Просто невероятно. То что я пробовал в магазине ни разу не сравнилось с тем что я получил. 3D кино - ни разу даже не дает почувствовать то, чего добился шлем виртуально реальности с настоящим 3D. Некоторые игра уж настолько реалистичны, что тяжело отличить от реальности. Играть правда долго не получится. Конечно не так как в 3D кинотеатре что через пол часа начинают глаза болеть. Но после 7 часов в виртуально реальности начинает болеть голова. Ну а больше 9 часов я не выдержал - надо делать перерыв;) По поводу качества картинки - поначалу заметны пиксели. В некоторых играх больше - в других меньше. В одних вообще не замечаешь. Не все игра оптимизированы так хорошо и они уменьшают размер внутреннего буфера что бы добиться 90Hz фреймрейта. Но я думаю это дело поправимое. Раз некоторые игры могут добиться того, что пиксели не чувствуются - то смогут и другие.

Один из лучших проектов - конечно The Lab от Valve. Это комната в которой есть пара игр, в основном небольших экспериментов. Но оно просто невероятны. К примеру - небольшая сцена с починкой робота. У меня просто челюсть отпала. В этом сценарии приносят робота и его надо починить. Скриншоты конечно не могут передать всего ощущения. Когда ты можешь наклониться, подойти и разглядеть маленькую деталь, отражение, индикатор - это совершенно другой опыт по сравнению с обычными играми.

В той же игре есть еще несколько интересных игр. К примеру симулятор лука - самое простое что можно придумать для VR.

Машина похожая на арканоид. Но тут дело в том, что управляешь ты кораблем в 3D. И все происходит в объеме. Наверное как игра Homeworld, но все происходит в рилтайме и более аркадное. Необычная игра. Очень даже понравилась.

Но была еще одна игра которая произвела полный восторг. Это даже не игра. А просто мир в 3D в который можно погрузиться и либо бродить, либо просто сесть и медитировать. Вот одно из мест которые можно посетить.

Это гора Vesper Peak, а с нее открывается вид на другую гору - Sperry Peak. Я был на Vesper Peak 2 года назад. Вот что запечатлел тогда.

Ракурс немного другой, но это одна и та же гора. Я вначале не прочитал описание и увидел эту гору. Я ее сразу узнал, но не мог поверит что это именно она. Но потом прочитал описание и оказалось - действительно Sperry. Для тех кто не поверит что первая фото - это скриншот, а не фотография вот другое фото с няшной.

Ну и еще пару скриншотов с этого приложения.

Игр очень много. Ну не то что бы тонны. Но я ожидал намного меньше. Люди уже начали заниматься ими. Правда AAA только несколько. В основном игры либо демки, либо прототипы, либо короткие. Есть невероятно крутые. Например Everest VR - весь Эверест как на ладони. Есть обычный режим истории, где ты от первого лица испытаешь разные части маршрута. А между ними с высоты самолета показывают гору. А есть Режим бога, где ты сам летаешь как хочешь.

Есть и более мультяшные, но не менее интересные игры. К примеру Accounting. Ужасно забавная игра. На одном дыхании прошел. Она кстати про виртуальную реальность.

Ну или симулятор звездных воин. Короткая сцена минут на 10-15. Надо отразить атаку клонов при помощи светового меча.

Еще одним из самых лучших приложений под VR - Google Earth VR. Все тот же Google Earth. Только теперь в виртуальное реальности. Невероятный опыт. Я нашел сразу дом, пролетел по маршруту от дома на работу. Но в разные моменты поднимался над городом и рассматривал его с высоты птичего полета. Прошелся по разным горам на которые восходил. Включая тот же Rainier.

Также одна из лучших игр - мод для Portal 2. Называется - Portal Stories: VR.

Quanero VR - еще один неописуемый проект. Случлся теракт. И в распоряжении полиции есть ролик с места взрыва. Можно перемещаться по бару в котором прогремел взрыв и перематывать время вперед и назад. Графика не очень правда. Вернее - если выкрутить настройки побольше - то все реалистично и как конфетка - но большой лаг и в VR от этого не очень приятный опыт. Но не смотря на графику, сама идея и исполнение - просто супер.

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

Но не все время я стоял с челюстью упавшей на пол и смотрел на разные игру. В некоторых я даже получил море фана. К примеру - Space Pirate Trainer. Это почти тот же акраноид, но сделан от первого лица. Ты стоишь в небольшом круге, а на тебя прилетают дроны, которые стреляют из бластеров. У тебя есть два пистолета, либо щит и пистолет, и твоя задача продержаться как можно дольше. Просто море фана. Для вечеринок - самое то.

Есть и адверчуры, которые очень даже ничего. Понравилась The Gallery - Episode 1: Call of the Starseed. Это квест. Очень интересно сделан рюкзак. Как настоящий рюкзак. Ну и красивая она.

Есть демки в которых показана технология. Но если с этого сделают игру - будет просто замечательно. Gnomes & Goblins - небольшая демка в которой тебя помещают в небольшую деревушку гоблинов. Графика невероятная. Хоть и немного мультяшная, но такое ощущение что попал в живой мир и гоблины - живые создания.

Еще одна игра - Vanishing Realms - адвенчура он первого лица. С приятным боем. Бой в скайриме был очень необычный и неудобный. Тут тоже самое. Но за счет motion capture - оно очень удобно и интересно.

Ну и на последов хотелось бы отметить российского разработчика. Две игры от компании Nival VR - InMind VR и InCell VR - обе игры невероятно крассивые. Но это были первые две игры которые привели к тошноте. Хотя после минут 20 попыток, я все таки смог побороть вестибулярный апарат и смог пройти 2 уровня в InCell. Но это было тяжело.

Это не все, а помимо этого еще много игр. Но про них в другой раз. Кроме игр есть разные интересные эксперимент - как 3D редактор. Что то типа скульпрурирования или рисования. Попробовал 360 - видео. Очень даже интересно. Но не 3D конечно. Очень понравились концерт - Tomorrowland 2014 и Grand Canyon 360º. Хотя от последнего меня стошнило чуть больше чем от игр Nival;). Есть и просто 3D видео. И, кхм-кхм, VR Porn;) В общем много чего есть.

Последние 2 с половиной дня я провел в виртуально реальности. И это было очень круто. Намного лучше чем я даже себе представлял. Из минусов - как я уже говорил - в некоторых играх видно пиксели. Разрешение что то вроде 1080x1200 в каждом глазу и это чувствуется. Будет раза в 2-3 больше - будет вообще не заметно. Ну и не все игры тянут на моем железе. Которое - один из топовых геймерских компом. Я думал что не будет ни одной игры которая бы тормозила на максимальных требованиях. Но вот 2160x1200 в 16 кратном антиалиэйсинге с мультисемплингом и прочими настройки и - может заставить даже такой компьютер кряхтеть. А если будет меньше 90 герц - то играть в это будет невозможно. Ну может 60 - было бы еще приемлемо, но заметно. Ну и последний минус - шнур. Без него погружение было бы намного лучшим. Видел что в планах есть обновление к шлему для беспроводной трансляции. Всего за 220 долларов. Но одно добавляет 2 мс задержки и люди говорят что это может быть проблемой. Но это новая вещь, пару недель как, так что пока я не буду о ней и думать.

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

ICFP 2012

Подготовка.

В этом году наша команда ShallowEndians пополнилась новыми людьми. Как и в прошлом году участвовали Джей, Пол, Кирилл Т., Кирилл М. и я. Но к нам ещё присоединились Гена и Млош. Также было решено работать в офисе, но в этом году не было свободных офисов и мы поселились в небольшом конференц зале.

Кирилл Т. создал образ дебиана, а Кирилл М. настроил меркуриал на своем амазоновском сервере. В этом году решили попробовать писать на одном языке. И им должен был стать C++.

До этого самого события мы ещё просто встретились что бы познакомится и просто обсудить предстоящее событие. На встречу я тоже опоздал;)

В пятницу мы договорились собраться в 5 утра в офисе и обсудить задачу. Среди нас только Джей был готов взять отгул на пятницу, что бы посвятить время icfp. Так что по плану мы должны были собраться после работы в 5 вечера.

В этом году я подошел к icfp не совсем в форме. Хоть и приехал с отпуска за две недели до, но ха это время эффект отпуска как рукой сняло. К тому же в четверг меня подняли в 5 утра - у нас были проблемы в одном из кластеров. Хоть фронтэнд и переключился на запасной кластер, но это надо было расследовать. В итоге весь четверг убил на это. А в пятницу в 3 утра опять подняли. На этот раз - это было ложное срабатывание вызванное инцидентом в четверг.

День первый.

По вышеизложенным причинам я не смог присоединится к комрадам в 5 утра. Но я успел прочесть задачу и отослать несколько идей которые появились:

• важно сохранять текущий лучший результат и по SIGINT выводить его в консоль и выходить. Лучше не ждать ещё 10 секунд, так можно схлопотать SIGKILL.
• большие карты решить будет сложно, надо собрать все лямбды локально идти к следующей далекой лямбде.
• A* кажется хорошим строительным блоком для других стратегий.
• интерактивная тулза будет очень важна для анализа решений и отладки алгоритма
• Что бы определить регионы которые надо посещать надо воспользоваться алгоритмом кластеризации

Написав это я лег спать. А Кирилл М. с Джеем за пару часов до работы успели написать почти полный симулятор карты. Джей продолжил работать над симулятором, а Кирилл М. начал работу над BFS ака полный перебор. У комрадов была идея разбить карту на регионы и на каждом запустить BFS что бы найти оптимальные ходы для сбора всех лямбд.

Я присоединился к команде в 5 вечера. Милоша не было, а остальные уже были в зале. Работа кипела и по началу я даже не знал чем заняться. Скачал репу и скомпилил проект. Почитал уже написанный код. Почитал ещё раз задание. В общем все были в работе. И особо отрываться не хотели.

В данный этап в основном кодили Кирил М. и Джей. Кирил работал над BFS, Джей над симулятором. Остальные обдумывали задачу. Придумывали разные сложные карты, пытались определить алгоритмы которые могут пригодится.

Над идеями типа нейронных сетей мы посмеялись, но не приняли всерьёз. Камрады сказали что отказались от A* потому что, по описанию, он плохо работает на динамических картах. Была хорошая идея заключавшаяся в том, что бы разбить алгоритм на множество простых решений - набор предикат-решение опрашивался бы на каждом ходу. Если бы предикат возвращал true, выполнялось бы решение. В этом случае мы могли бы иметь общий алгоритм, который работал бы в большинстве случаев и набор захардкоженых решений для очень сложных случаев.

В итоге последнюю идею мы так и не реализовали. Был только один предикат - проверить падает ли камень на выход, и решение - попробовать оттолкнуть камень. Как мне кажется идея с предикатами и решениями должна была бы быть очень хорошим алгоритмом, но у нес не хватило времени на это.

Про молниеносный раунд никто даже и не заикался. Участие в нем не представлялось возможным.

В общем помозговали немного. Идей было море, но вот времени на их реализацию не очень. Я был уже готов писать код. Не хотел пересекаться с тем что уже идет в разработке. Я задал вопрос комрадам - "что делать то?". На что получил ответ, что когда будет готов BFS, надо будет как то ходить от региона к региону. Вот этим я и занялся.

Я ещё раз прочитал статьи про BFS и A* в википедии. Все же верил, что на динамических картах A* должен работать. И я решил его реализовать. Основная идея была в том, что бы хранить в каждой ячейке карты саму карту, которая бы предоставляла состояние которое будет после того как мы туда доберемся. Эвристика была простой - расстояние + прохождение по земле - пенальти +1, иначе - пенальти 0.

В общем около 11 вечера у меня уже был алгоритм почти готов - путь находился, но в бектрекинге у меня был баг. Кирилл М. решил пойти домой, ну и я тоже пошел спать. Правда придя домой решил добить A*. Нашел багу и за минут 10 сделал dummysolver, программу которая берет лямбды, сортирует по удалению, пытается пройти к одной лямбде (сперва ближней, потом далее по расстоянию), дальше повторяется. В общем я обрадовался. До конца молниеносного раунда оставалось 4 часа и был шанс засабмитить. Но потом я нашел баг, что робот не умерает если по нему шарахнет камень. С таким багом алгоритм поиска пути выдавал фатальный вариант и робот умерал. Я огорчился и лег спать.

День второй.

Утро субботы началось не очень приятно. Оказалось что мой код не компилируется у большинства людей. Я использовал gcc 4.6, а некоторые - gcc 4.4 в котором не было поддержки auto, некоторые Visual Studio, в которой не было поддержки новому for (for(auto & i : container) {}), у некоторых были проблемы с std::unique_ptr. Немного подумали и самым простым было выпилить новый стандарт со всего кода. На это ушло около часа. Неблагодарная работа. Код стал менее читабельным.

Я объяснил как сделал A*. Рассказал, что хочу ввести более сложные эвристики. Например пенальти за сдвиг камня. Гена проявил сомнения что он будет работать с эвристиками отличными от расстояния. Мы немного подискутировали на эту тему и я сел и написал новые эвристики. Теперь за проходжение сквозь лямбду не было пенальти, пустая ячейка - +1, земля - +3, земля, которая находится под камнем, давала +7 пенальти. И оно заработало. Причем очень даже неплохо.

Дальше я попросил Джея сделать статистику по падению камней. Каждый раз, когда один камень падал, она увеличивалась на 1. Я интегрировал в A* и он стал ещё лучше. Теперь к примеру если был короткий путь, но который сдвинет камень и он упадет на 10 клеточек вниз, получал более низкий приоритет, чем обходной путь, который не тронет камни. Но если выхода не было, то камни двигались.

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

Я нашел проблему в моем алгоритме, робот загонял себя в тупик. Если над ним был камень, а по бокам стены - то он не мог продолжать двигаться. Я по началу начал запрещать двигаться к таким лямбдам, но это не дало ожидаемого результата. Алгоритм стал работать медленно, хотя и работал лучше.

Мне пришла идея использовать симуляцию отжига. Алгоритм был таков - находим первое решение. Запоминаем его. Дальше отрезаем 80% пути и делаем рандомное движение к любой лямбде. Дальше включаем алгоритм найти решение до конца. Получив несколько решений - выбираем лучшие. От них отрезаем 60% пути и продолжаем. Дойдя до 20%-го отрезания - возвращаемся к 80%. В общем этот алгоритм реализовывал некое подобие бектрекинга. Не настоящей бектрекинг, который мы хотели сделать, но первая быстрая версия. Стыдно говорить, но в начале я реализовал неправильно алгоритм. Делал по памяти. В начале отрезал 20%, потом 60%, потом 80%. То есть делал наоборот. Но быстро исправился.

Гена начал работать над высокоуровневыми стратегиями. А у Кирила был готов алгоритм и мы его начали комбинировать с моим. Идея была такова - если в округе есть лямбда - включать BFS, если нету - выбирать ближайшую лямбду и двигаться к ней, а дальше повторить. К тому же в качестве рандомного действия в симуляции отжига - мог включится BFS.

С одной стороны BFS давал хорошие результаты, но как и любой полный перебор - он был не очень быстр - что замедляло симуляцию отжига и уменьшало число популяций алгоритмов которые прорабатывались. Я немного уменьшил размер популяции что бы компенсировать. Результат был уже очень даже ничего.

Кирилл Т. нашел народные карты. Аж 1000 штук. И залил их в репозиторий. На очень больших картах наш dummysolver не очень шустро работал. На самой огромной я не дождался результата за одну минуту. Было над чем поработать.

Но мяньячить не стали, разошлись по домам часа в 4 утра. Джей все же остался, как мы выяснили по ночным коммитам. Он отрефакторил написанный код, что бы было легче продолжать разработку.

День третий.

Гена занялся реализацией кластеризации карты. Нашел библиотеку с кодом для Lin–Kernighan, и прикручевал её. Пол, хотя он и не знает C++, помогал реализовывать последние изменения от организаторов. Джей допилил интерфейс карты и оказалось, что мой A* не надо менять для поддержки трамплинов. Я надеялся на это, но все же было приятным сюрпризом. Кирилл Т. начал работу над тестами.

Кирилл М. оптимизировал BFS. Он придумал способ ускорить его получая лучший результат. На этапе когда память подходила к лимиту он отбрасывал часть решений. В итоге обрабатывалось больше хороших цепочек и получался лучше результат.

Я нашел проблему с тем, что A* не умеет двигаться назад. То есть ему не под силу подойти под камень убрав землю, отойти и подождать пока он упадет, а потом пойти дальше. Хотел решить эту проблему. Даже почти придумали как - убрать все камни, пройти к желаемой лямбде, дальше найти последний камень который мешает, предположить, что мы туда дойдем и включить там BFS, что бы найти путь сквозь камень. Дальше найти предыдущий камень и тд. Но к сожалению я так и не успел реализовать это.

Нам надо было ещё реализовать финальную программу, которую будем отсылать организаторам. Я начал с того, что заменил все std::cout на std::cerr, что бы если мы забудем закомментировать какой то логгинг, это не испортило нам решение. Также сделал хранитель решений, который бы обновлялся последний лучшим решением, а по SIGINT выводил его на экран и завершал программу. Также поддержал SIGABRT и SIGSEGV, на случай если произойдет ошибка, которую не сможем обработать. В этом случае тоже выводился лучший результат и завершалась программа.

Часам к 5 вечера и Пол и Милош нас покинули. А мы остались допиливать решение, исправлять краши, тестировать на разных картах.

Я также внес ещё рандомности в симуляцию отжига отрезая не 80%, а от 80 до 100, а потом не 60%, а от 60 до 80 и тд. Это тоже улучшило результаты.

Часов в 7 мы провели презентацию нашего решения. Не зря же мы поселились в конференц зале с проектором;) Каждый рассказал о том, что сделал и как это внутри работает.

К этому моменту я уже достаточно вымотался. Да и остальные тоже. Джей так вообще без сна был. Никаких кардинальных решений мы не планировали сделать. Только допиливали текущее решения. Только Гена работал над кластерингом, который должен был значительно улучшить результат собирая лямбды в оптимальной последовательности.

Вскоре нас покинул и Кирилл Т. Честно говоря мы так и не успели применить его тесты. Оценить новый алгоритм мы по достоинству не могли, оценивали на глаз и на результат с тестовых карт.

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

А Кирилл, Гена и я остались до победного конца. Я занялся регистрацией и созданием финального бинарника. Кирилл скачал образ с сайта организаторов, а я установил его в Virtual Box и отработал создание архива с исходниками и финальным исполнительным файлом.

Кирилл успел сделать механихм отталкивания камня от лифта и мы игтегрировали его в финальное решение. Часа в 2 ночи, Гена был начал интеграцию кластеризации и приоретизации кластеров в осноной алгоритм. Я все ещё хотел сделать решение с проходом сквозь камни, но руки не дошли. Ещё пришлось повозится с Кириллом над интеграцией LKH библиотеки. Гена писал на виндовсе и хотя библиотека и была на C, у нас ушло достаточно времени что бы её скомпилить и слинковать с нашим решением на C++. К тому же там было много printf-ов. Я то думал что вычистил все std::cout, а про printf не подумал. Пришлось их комментировать или перенаправлять в STDERR. А дальше мы с Кириллом продолжили текстировать и исправлять баги.

Хоть Гена и старался успеть к 5 утра, но если бы и успел, было бы очень рискованно выкладывать не протестированное решение. Так что к сожалению не успели. А последний час шел очень быстро.

В 4:30 мы уже почти были готовы к заливке финальной версии. Где то в 4:45 я начал финальный билд. Кирилл ещё хотел включить небольшое изменение - включать BFS на всей карте если она не очень большая, а не на окне. Но получить билд уже было нереально. К тому же мы заметили регресию на одной из карте, где камень должен был быть отодвинут роботом, но этого не происходило. Но решено было заливать как есть.

Но я был на мобильном интернете. Остальные подключились к корпоративному интернету, но я не стал заморачиваться - для разработки хватало. Но тут интернет начал тупить. Было уже где то 4:55. Я плюнул - скинул билд на телефон и понес к Кириллу. Но почему то его ubunta не хотела монтировать телефон. Гена побежал на свой этаж за флешкой. Пришел где то в 4:58. Я быстро скинул файл. Кирилл открыл флешку, залил в google docs. Все вздохнули с облегчением. Но там надо было ещё нажать разшарить. Кирилл добавил организаторов, но не нажал на финальную кнопку. Мы это заметили - он нажал, все - файл ушел. За последние 5 минут получил не маленькую дозу адреналина;)

Послесловие.

Мне этот год понравился. Может даже больше чем предыдущий. Мы смогли писать на одном языке. И очень продуктивно взаимодействовали. Кирилл М. к примеру считает, что прошлый год был лучше. Но они немного разные были. В ICFP 2012 нам надо было именно реализовывать алгоритмы, а в прошлом году - придумывать их, а сама программа не была очень сложной.

Некоторые проблем мы решили с прошлого года, но все же было много и ошибок. К примеру вот несколько. Джей потратил много времени на мержи кода. У него не было нормальной утилиты как у других - KDiff3. По началу он использовал vimdiff, пока не перелез на винду. Нам надо было больше времени потратить на тесты и использовать их для нахождения оптимального алгоритма. Мы делали это на глазок. Так же мы не успели сделать много что хотели. Некоторые алгоритмы возможно были бы очень кстати, но руки не дошли до них.

Не смотря на проблемы, я все же считаю что мы молодцы. И неважно какое место мы получим. Мы уже получили массу удовольствия. Хотя это немного извращенное удовольствие. После окончания мы были изнеможены полностью. А в понедельник я ещё и пошел на работу, так как не мог пропустить этот день.

Всего было 270 команд. После первого раунда должно остаться 135. Я надеялся что мы попадем в 80, а может и в 60-ку. Кирилл М. дал прогноз, что мы все же пройдем в 2-й раунд, но еле-еле. После мы прочитали, что команда _adept_-а набрала свыше 6 миллионов на народных картах. Уже после окончания мы протестировали наш алгоритм, он набрал всего 1.3M.

К нашему удивлению в первом раунде мы, ShallowEndians, заняли 19-е место набрав 9877 очков. Я крайне обрадовался этому результату. Я все таки верил в нас. Но на 19 место даже не рассчитывал. Но посмотрим на 2-й раунд. Может это была случайности и среди 135 команд мы не попадем и в первые пол сотни. Кто знает.

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

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

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 дуэлей;)

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()

MySQL в tmpfs

Хотелось бы поделиться опытом по использованию MySQL с хранением данных в памяти а не на диске. Это позволило нам сократить load average сервера, который из-за операций с диском стал сильно расти.

В одном проекте мы используем MySQL с движком MyISAM под Debian Lenny. Общие данные загружаются в оперативку демона на С++, а пользовательские данные один раз загружаются при логине и переодически сохраняются во время работы пользователя. Также сохраняются при логауте (либо по таймауту). Ввиду описаной схемы select-ов намного меньше, чем update-ов (select: 24%, delete: 4%, update: 61%, insert: 11%).

В принципе данная проблема - не админская, а вызвана не совсем удачным выбором инструмента. Скорее всего, нам бы подошел InnoDB, который использует row-level locking (блокировка по записям), а не table-level locking (блокировка всей таблицы при записи) как у MyISAM. Хотя объем данных записываемых на диск это врядли сократило бы. С другой стороны, нам SQL особо не нужен и мы склоняемся к портированию проекта на NoSQL (к некоторым из представителей мы давно приглядываемся (Сassandra), а некоторые (tokyo tyrant, Berkeley DB) мы активно используем для логирования пользовательских действий). Но выделить время на перевод хранилища данных на другой движок/базу не было, по этому решили использовать админ. ресурс.

С ростом количества пользователей и введением нового контента мы столкнулись с проблемой роста load average на сервере базы данных (2-3 la на 8-ми ядерном сервере наблюдалось всего при 400 запросах в секунду). При чем память была недогружена, как и процессор. Проблема была в большом большим объемом записи данных на диск (увеличение iowait). В некоторые моменты система начинала заикаться и некоторые примитивные запросы занимали 2 секунды, а то и больше. В нормальном режиме такие запросы выполняются за милисекунды.

Мы немного соптимизировали конфиги MySQL (используя как автоматические скрипты типа mysqltuner, так и ручную настройку), но это дало лишь небольшое снижение нагрузки (процентов на 10-15). По большей части параметры, отвечающие за кеширование данных, нам не подходят, так как у нас основная нагрузка - обновление данных, а не чтение. База находится на SAS диске, но скорости все равно не хватает. Бинарные логи находятся на другом диске (используются для бекапа базы со слейва).

Ускорить работу дисковой системы купив полноценный RAID нам не подходит из-за его большой цены. Но сам сервер почти простаивает, если не учитывать диски. Возможности сжатия данных в памяти до записи на диск в MyISAM нет, но и переходить на другой движек нету пока возможности (Falcon это должен был уметь, но его забросил Oracle после покупки MySQL)

База у нас занимает около 2-2.5 Gb (в tar.gz 700mb) и мы уже давно пробовали использовать MySQL в tmpfs (методом основаном на mylvmbackup), что позволяло не нагружать диск и упростить создание бекапа. К счастью мы недавно провели очистку базы, путем добавления крона, который удаляет старых пользователей, которые почти не пользовались проектом и ни разу не заплатили. Кроме этого мы очистили старые данные, которые собирали для статистики и поставили им срок жизни порядка двух месяцев.

В качестве быстрого решения даной проблемы возникла идея перевести главную базу на tmpfs. Что у нас получилось:

И так мы имели 3 сервера:
1. сервер А (боевая база куда стучатся демоны (у нас на нем 8Г оперативки ))
2. сервер Б (любой сервер на той же площадке со свободной оперативной (у нас 8Г из них 5Г свободно))
3. сервер В (на другой площадке заточен под бекапы всех проектов с максимум оперативки (у нас 16Г))

И так на Сервере А поднимаем tmpfs для файлов базы
mount -t tmpfs -o size=5G tmpfs /var/lib/mysql (с запасом в 2 раза больше чем весит база)
Так же не забываем в конфигах базы написать чтоб бин логи писались на оддельный свободный диск (мастер без них не работает), а под нагрузкой база может писать в эти логи до 1М в сек. Мы храним эти файлы не более 7 дней (более и не надо т.к. для востановления базы если что есть слайвы)

Соответсвено стартуем базу как мастер. Сервер под самими жескими нагрузками не выходит из 1ЛА и по памяти не более 6Г. Средняя скорость выполнения запроса вызросла в десятки раз, если раньше было 0,1-0,3 сек то стало 0.1-3 мсек
Далее на сервере Б так же поднимаем первый слейв тоже в tmpfs тут не стоит забывать о настройках relay-log т.к. если в слайве будет ошибка, а мастер будет доступен в эти логи он будет писать запросы которые были на мастере.. В итоге это может измерятся десятками гигобайт за ночь, прежде чем вы почините слайв, у нас это около 8-10 гигабайт в час. Бекапим эту базу снапшотами ночью 1-2 раза в день когда нагрузка на демоны минимальна. Такой слейв жрет максимум 0.2-0.3 ЛА и чуть более того что весит база.

Также на сервере В у нас подняты сразу несколько слайвов на tmpfs под наши проекты, споконо живут вместе особо не нагружая сервер при этом бекапятся снапшотом раз в 10 минут (если это время разложить то снапшот делается около 3 сек (базы вес которой 2,5 гига) ну и зжатие в архив около 6-7 минут) и да же при этом на сервере ЛА не привышает 2, даже когда бекапы пересикаются по времени. Судя по всему кол-во бекап слейвов на одном сервере определяется размером баз и кол-вом оперативки. Бекапы храним по 10 минут - последние 24 часа, каждые 6 часов - храним 30 дней, каждые 30 дней - вечно.

Далее если вдруг падает слайв Б или В поднять его с любым из бекапов с другово слайва не трогая мастер без проблем ели даже оба падают поднять не трогая мастер 10 минут - скорость переписывания бекапов.
Если падает мастер то есть на это два слейва с отстованием максимум 1-2 апдейта от мастера (не разу ни видели чтоб Slave Delay(отстование от мастера) превышал 0 сек) , при этом срочное решение проблемы это втечении 5 минут из слейва Б сделать мастер .. и перестроить демоны, при тестах они спокойно живут на одном сервере и не мешая друг другу.

В итоге чтоб одновремено упали 3 машины на 2 разных площадках это очень мало вероятно, поднять базу при любом подении сервера или площадки займет не более 10 минут.

Обязательно настраиваем оповещалки (munin, nagios, zabix - кому что больше по душе) на 2 площадках с измерением отстования слайва, можно по смс или по мылу, у нас нагиос следит за этим и при этом мунин его страхует и при этом рисует графики по которым все очень наглядно виодно что и как и кого.

Load average на серверах снижается осень сильно, теперь основную нагрузку берет на себя процессор и память, а не диск. Вот графики которые мы сняли при ещё одного переводе сервера сегодня:

Стоит заметить что после перевода базы, были так же уменьшены интервалы сохранения пользовательских данных в С++ - поэтому количество апдейтов возросло.

В общем единственная потенциальная проблема — это рост базы. Но сейчас память в серваках достаточно дешевая и увеличить её не составит проблем (на части машин у нас 16Gb, на части 8Gb, но, насколько мне известно, можно поставить в потолке 128Gb). В любом случае кластеризацию базы никто не отменял и мы сможем разпределить базу на несколько серверов с схожей конфигурацией.

InnoDB - http://dev.mysql.com/doc/refman/5.1/en/innodb.html
MyISAM - http://dev.mysql.com/doc/refman/5.1/en/myisam-storage-engine.html
Сassandra - http://cassandra.apache.org/
tokyo tyrant - http://fallabs.com/tokyotyrant/
Berkeley DB - http://www.oracle.com/technetwork/database/berkeleydb/overview/index-085366.html
mysqltuner - http://mysqltuner.com/mysqltuner.pl
Falcon - http://en.wikipedia.org/wiki/Falcon_(storage_engine)
tmpfs - http://en.wikipedia.org/wiki/Tmpfs
mylvmbackup - http://www.lenzg.net/mylvmbackup/

128-bit

Понадобилось на днях умножать и считать остаток от деления для 128 битных чисел на плюсах: (a * b) % c, где все числа 64 битные, а это значит что надо оперировать именно с 128 битами.
Нашел класс uint128_t, который использует два 64 битных числа. и в нем куча функционала. так как boost использовать нельзя было.
Быстро отпилил его, написав вручную недостоющие операторы. Отлично! Даже работает быстро. Но когда запустил на машине для которой создавался код все оказалось медленне раз в 10.
Немного покопав узнал, что дело в 32 битной системе (у меня на ноуте 64 бита). Очень огорчился и уж было думал что всё пропало и ничего сделать нельзя, но потом решил переписать вручную.
Сложить два 128 битных числа можно так:

inline void a_add_b_inplace(uint64_t& a0, uint64_t& a1, const uint64_t b0, const uint64_t b1)
{
 if(a1 >= 0xffffffffffffffffULL - b1)
 {
  ++a0;
 }
 a1 += b1;
 a0 += b0;
}

Умножение двух 64 битных чисел можно эфективно сделать используя три 32 битных числа и сохранить это все в 2 64 битных числа (получится 128 бит информации). Что то типа:

inline void a_mul_b(const uint64_t& a, const uint64_t& b, uint64_t& d0, uint64_t& d1)
{
 uint32_t a0 = (a >> 32) & 0x00ffffffffU;
 uint32_t a1 = a & 0x00ffffffffU;
 uint32_t b0 = (b >> 32);
 uint32_t b1 = b & 0x00ffffffffU;
 uint64_t c0 = ((uint64_t)a0) * b0; // << 64
 uint64_t c1 = ((uint64_t)a0) * b1 + ((uint64_t)a1) * b0; // << 32
 uint64_t c2 = ((uint64_t)a1) * b1;
 d0 = c0; // << 64
 d1 = c2;
 uint64_t c10 = (c1 >> 32) & 0x00ffffffffU;
 uint64_t c11 = c1 & 0x00ffffffffU;
 a_add_b_inplace(d0, d1, c10, c11<<32);
}

Остаток от деления можно получить уже не так просто. Для этого необходимо реализовать ещё несколько операций. Но удивил сам результат - на 32 битной платформе этот код работал в 5 раз бытрее чем класс uint128_t. А ещё на 64 битке эта реализация по скорости почти не отличается от 32-ной. Ура. В итоге я смог реализовать алгоритм Miller-Rabin-а для 64 битных чисел, который работал бы всего в несколько раз меленне на 32-х битной системе, чем на 64-х битной.