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

Всем привет! В этой статье я хочу кратко изложить ключевые моменты своей стратегии в ходе прошедшего соревнования по программированию искусственного интеллекта Russian AI Cup.

Немного о Russian AI Cup

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

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

Правила можно найти здесь.

Привет! В этой статье я хотела бы рассказать вам о своем участии в соревновании по написанию игровых ботов Russian AI Cup CodeWars, на котором мне удалось занять 2 место, и что и как для этого было сделано.

Всем привет.

Астрологи объявили неделю Речь пойдет о соревновании Russian AI Cup 2017, а точнее о написанном мною боте. Участвую в данном конкурсе уже 6-й год подряд — ещё начиная с танчиков. Некоторые могу знать меня по участию в ML Boot Camp и HighLoad Cup.

Место занял (опять) не первое, но есть о чём написать на хабр. Статья, прежде всего, может быть интересна участникам этого года, или тем, кто захочет подчерпнуть какие-то идеи к следующему подобному конкурсу, или просто для тех, кто знаком с тематикой конкурса Russian AI Cup.

Меня зовут Андрей Рыбалка, мне 32, я занимаюсь веб разработкой, а также, периодически участвую в различных чемпионатах по написанию игрового ИИ (обычно на Java). И я хотел бы рассказать о своих подходах к написанию бота для Russian AI Cup 2017. Решил описать и саму историю и техническую часть, но тем, кого интересует именно реализация, можно смело прокручивать до соответствующего подзаголовка.

Итак..

Всем привет! Хочу рассказать про историю своей победы в ежегодном соревновании по написанию игровых ботов Russian AI Cup, в 2017. В финале бот выиграл 98% игр, что, как оказалось, наивысший результат по финалам среди всех годов проведения чемпионата. Также занял 1-е место в песочнице по завершению её работы, в пике переходя за 4000 очков рейтинга.



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

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



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

Всем привет! Не так давно завершился HighLoad Cup. От многих участников поступала масса вопросов об устройстве чемпа изнутри. Мы, команда разработки чемпионатов и образовательных проектов Mail.Ru Group, в данной статье расскажем об устройстве чемпа, о внутренних механиках и немного об истории проведения первого HighLoad Cup!

Уже 6 лет проводится ежегодное соревнование Russian AI Cup. За это время чемпионат оброс постоянной аудиторией и у многих заядлых участников появился небольшой набор инструментов и хитростей, которые помогают им в разработке. Я участвовал в этом соревновании 3 раза и также обзавелся рядом заготовок и скриптов, о которых и хочу рассказать в данной статье.

Седьмого ноября официально стартовала неделя бета-теста Russian Ai Cup 2017. Чемпионат ежегодный, и в этом году мы решили предложить участникам проект под названием CodeWars — конкурс по программированию ботов для игры, которую сами участники сходу окрестили «симулятором игрока в RTS». Бета-тест подошел к концу, чемпионат официально стартовал, и под катом мы хотели бы отчитаться, поделиться новостями о том, что же мы теперь можем предложить. Ну и еще раз зазвать всех поучаствовать, не без этого конечно.

В конце сентября мы рассказывали, что решили попробовать провести контест, где желающие могут потренироваться в решении задач, максимально приближенных к «боевым». Так участники могут понять, какого формата задания получают разработчики на собеседованиях в Яндексе (этим интересуются очень многие), а самое главное — с чем они сталкиваются, работая над Поиском. Типичная задача на собеседовании — составить алгоритм, доказать его корректность, предложить пути оптимизации. Если человек разбирается в алгоритмах, то он быстро сумеет их реализовывать на любом доступном ему языке.

В Блице можно использовать Java, C++, C# или Python. Кроме того, участие в контесте дает возможность проверить свои знания. Если в итоге вы понимаете, что их стоит подтянуть, — это тоже результат. Кстати, тогда вам может пригодиться специализация на курсере «Алгоритмы и структуры данных», в создании которой Яндекс участвовал.

Давайте теперь разберем задачи, которые предлагались в отборочном раунде. У нас было несколько одинаковых по сложности вариантов, каждый из которых содержал по шесть задач. Мы разберем один набор задач полностью, а также наиболее интересные задачи из других наборов. К слову, из 1762 участников квалификационного раунда в финал прошли лишь 263. Так что задачи оказались не самыми простыми.

Уже несколько лет подряд мы проводим Russian AI Cup — нехилый такой конкурс для всех неравнодушных к программированию в целом, к построению ИИ, просто к написанию ботов для игр или автоматизации чего бы то ни было. Естественно, и этот год не будет исключением. Итак, Mail.Ru Group в сотрудничестве с Саратовским государственным университетом официально объявляют о дате старта Russian AI Cup 2017 и счастливы предложить задачу этого года. Жёсткие битвы, макбуки за первые места и минус полтора месяца из жизни разработчика — всё на месте, всё как вы любите. Добро пожаловать под кат за подробностями!

В гольфе выигрывает тот, у кого меньше очков.

Применим этот принцип в Android. Мы собираемся поиграть в APK-гольф и создать приложение минимально возможного размера, которое можно установить на Android 8.0 Oreo.

Базовый уровень

Начнём с дефолтного приложения, который генерирует Android Studio. Создадим хранилище ключей, подпишем приложение и измерим размер файла в байтах командой stat -f%z $filename.

Затем установим APK на смартфон Nexus 5x под Oreo, чтобы убедиться, что всё работает.



Прекрасно. Наш APK весит примерно полтора мегабайта.

Школьники из Санкт-Петербурга под руководством тренера из Университета ИТМО примут участие в мировом этапе конкурса по программированию интеллектуальных робототехнических систем (WRO-2017). Всех, кого заинтересовала эта новость, приглашаем под кат.

Каждый год Министерство образования и науки РФ публикует перечень школьных олимпиад, дающих льготы при поступлении в вузы. С 2015 года в этот список входит и Технокубок — олимпиада по программированию под эгидой Mail.Ru Group.

Поучаствовать в Технокубке могут ученики 8—11-х классов. Олимпиада позволяет ребятам оценить свои силы и пообщаться с профессионалами IT-отрасли, а главное — дает шанс поступить в ведущие профильные вузы России.

Рассказ о том как я участвовал в highloadcup (чемпионат для backend-разработчиков) от Mail.Ru, написал на php сервер обслуживающий 10000 RPS, но всё равно не получил победную футболку.

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

Поздравляем победителей!

1. Yuri Chechushkov — 55954 очка. Приз 3000 USD.
2. Ouanalao — 55653 очка. Приз 2000 USD.
3. Anton Ivakin — 54100 очков. Приз 1000 USD.

(Результаты выше приведены для 100 тестовых уровней.)

Результаты тестирования опубликованы на GitHub.

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

Представлюсь: меня зовут Иван Греков, я из фронтенд-команды Badoo. Мне очень понравился этот пост, я просто не смог пройти мимо и не перевести его. Этот пост – отличный источник вдохновения для любителей прототипирования устройств и open-source-решений. Перевод публикуется с сохранением авторской точки зрения и, надеюсь, будет интересен вам.

UPDATE: Приносим извинения за ошибку, в результате которой решения были изначально протестированы на AWS-сервере типа m3.large вместо заявленного в правилах c3.large. Все решения были перетестированы, и результаты на GitHub обновлены.

Спасибо всем, кто принял участие в нашем конкурсе по программированию! Мы получили 132 решения от 66 уникальных участников. Неделю назад было примерно вдвое меньше — нельзя недооценивать волшебную силу надвигающегося дедлайна.

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

В этой статье мы поговорим о «магической» константе 0x5f3759df, лежащей в основе элегантного алгоритмического трюка для быстрого вычисления обратного квадратного корня.

Вот полная реализация этого алгоритма:

float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;  // представим биты float в виде целого числа
  i = 0x5f3759df - (i >> 1);  // какого черта здесь происходит ?
  x = *(float*)&i;
  x = x*(1.5f-(xhalf*x*x));
  return x;
}

Этот код вычисляет некоторое (достаточно неплохое) приближение для формулы



Сегодня данная реализация уже хорошо известна, и стала она такой после появления в коде игры Quake III Arena в 2005 году. Её создание когда-то приписывали Джону Кармаку, но выяснилось, что корни уходят намного дальше – к Ardent Computer, где в середине 80-ых её написал Грег Уолш. Конкретно та версия кода, которая показана выше (с забавными комментариями), действительно из кода Quake.
В этой статье мы попробуем разобраться с данным хаком, математически вывести эту самую константу и попробовать обобщить данный метод для вычисления произвольных степеней от -1 до 1.

Да, понадобится немного математики, но школьного курса будет более, чем достаточно.