Русский
Русский
English
Статистика
Реклама

Соревнование

Кошелёк Mobile Challenge итоги конкурса и подробный разбор решений командой разработки

18.12.2020 14:16:13 | Автор: admin

У нас было две платформы, 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. Рады там всем, нам будет интересно обменяться опытом решения подобных задач и с другими компаниями.

Подробнее..

CatBoost и ML-конкурсы

15.05.2021 14:20:40 | Автор: admin

Анализ данных и базоваямодель

Вступление

Эта статья основана на данных конкурса, который компания Driven Data опубликовала для решения проблем с источниками воды в Танзании.

Информация для конкурса была получена Министерством водных ресурсов Танзании с использованием платформы с открытым исходным кодом под названием Taarifa. Танзаниясамая большая страна в Восточной Африке с населением около 60 миллионов человек. Половина населения не имеет доступа к чистой воде, а 2/3 населения страдает от плохой санитарии. В бедных домах семьям часто приходится тратить несколько часов пешком, чтобы набрать воду из водяных насосов.

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

Данные

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

Пункты водоснабжения разделены на исправные, нефункциональные и исправные, но нуждающиеся в ремонте. Цель конкурсапостроить модель, прогнозирующую функциональность точек водоснабжения.
Данные содержат 59400 строк и 40 столбцов. Целевая метка содержится в отдельном файле.
Показатель, используемый для этого соревнования,это classification rate, который вычисляет процент строк, в которых прогнозируемый класс совпадает с фактическим классом в тестовом наборе. Максимальное значение равно 1, а минимальное0. Цель состоит в том, чтобы максимизировать classification rate.

Анализ данных

Описания полей в таблице с данными:

  • amount_tshобщий статический напор (количество воды, доступное для точки водоснабжения)

  • date_recordedдата сбора данных

  • funderкто спонсировал постройку колодца

  • gps_heightвысота на которой находится колодец

  • installerорганизация построившая колодец

  • longitudeGPS координаты (долгота)

  • latitudeGPS координаты (широта)

  • wpt_nameназвание, если оно есть

  • num_privateнет информации

  • basinгеографический водный бассейн

  • subvillageгеографическая локация

  • regionгеографическая локация

  • region_codeгеографическая локация (код)

  • district_code географическая локация (код)

  • lgaгеографическая локация

  • ward географическая локация

  • populationколичество населения около колодца

  • public_meetingда/нет

  • recorded_by кто собрал данные

  • scheme_managementкто управляет колодцем

  • scheme_nameкто управляет колодцем

  • permitтребуется ли разрешение на доступ

  • construction_yearгод постройки

  • extraction_typeтип колодца

  • extraction_type_groupгруппа типа колодца

  • extraction_type_classкласс типа колодца

  • managementкак управляется колодец

  • management_groupгруппа управления колодца

  • paymentстоимость воды

  • payment_typeтип стоимости воды

  • water_qualityкачество воды

  • quality_groupгруппа качества воды

  • quantityколичество воды

  • quantity_groupгруппа количества воды

  • sourceисточник воды

  • source_typeтип источника воды

  • source_classкласс источника воды

  • waterpoint_typeтип колодца

  • waterpoint_type_groupгруппа типа колодца

    Прежде всего, давайте посмотрим на целевую меткуклассы не имеют равномерного распределения:

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

    • уменьшать количество примеров у преобладающих классов(under-sampling)

    • дублировать строки с метками, которых мало(over-sampling)

    • генерировать синтетические выборкиэто случайная выборка атрибутов из экземпляров в классе меньшинства (SMOTE)

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

    Больше про тактики работы с несбалансированными датасетами можно почитать здесь.

    Посмотрим, как водяные насосы распределяются по территории страны.

    Некоторые данные содержат пустые значения.

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

    Следующая тепловая карта представляет наличие/отсутствие связи между переменными. Стоит обратить внимание на соотношение между permit, installer и funder.

    Давайте посмотрим на общую картину взаимоотношений на дендрограмме.

    В характеристиках водяных насосов есть та, которая показывает количество воды. Мы можем проверить, как количество воды связано с состоянием насосов (quantity_group).

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

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

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

    Большинство колодцев с неизвестным качеством из quality_group не работают.

    Есть еще одна интересная характеристика водных точеких тип (waterpoint_type_group).

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

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

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

    Danidaсовместная организация Танзании и Дании по финансированию скважин, и хотя у них много работающих водозаборов, процент неисправных очень высок. Похожая ситуация с RWSSP (программа сельского водоснабжения и канализации), Dhv и некоторыми другими. Следует отметить, что большинство скважин, профинансированных Германией и частными лицами, находятся в рабочем состоянии. Напротив, большое количество скважин, которые финансируются государством, не функционируют. Большинство пунктов водоснабжения, установленных центральным правительством и районным советом, также не работают.

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

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

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

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

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

    Часть данных была заполнена значением 0 вместо реальных данных. Мы также можем видеть, что amount_tsh выше у исправных колодцев (label = 0). Также следует обратить внимание на выбросы в функции amount_tsh. В качестве особенности можно отметить перепад высот и тот факт, что значительная часть населения проживает на высоте 500 метров над средним уровнем моря.

Подготовка данных

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

  • Фича installer содержит множество повторов с разными регистрами, орфографическими ошибками и сокращениями. Давайте сначала переведем все в нижний регистр. Затем по простым правилам уменьшаем количество ошибок и делаем группировку.

  • После очистки мы заменяем все элементы, которые встречаются менее 71 раз (0,95 квантиля), на other.

  • Повторяем по аналогии с фичей funder. Порог отсечки98.

  • Данные содержат фичи с очень похожими категориями. Выберем только по одной из них. Поскольку в датасете не так много данных, мы оставляем функцию с наименьшим набором категорий. Удаляем следующие фичи: scheme_management, quantity_group, water_quality, payment_type, extraction_type, waterpoint_type_group, region_code.

  • Заменим latitude и longitude значения у выбросов медианным значением для соответсвующего региона из region_code.

  • Аналогично повторям для пропущенных значений для subvillage и scheme_name.

  • Пропущенные значения в public_meeting и permit заменяем медианным значением.

  • Для subvillage, public_meeting, scheme_name, permit, создаем дополнительные категориальные бинарные фичи, которы будут отмечать данные с пропущенными значениями. Так как мы заменяем их на медианные, то для модели оставим информацию, что пропуски были.

  • Фичи scheme_management, quantity_group, water_quality, region_code, payment_type, extraction_type, waterpoint_type_group, date_recorded, и recorded_by можно удалить, так как там повторяются данные из других фичей, для модели они будут бесполезны.

Модель

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

Не будем подбирать оптимальные параметры, пусть это будет домашним заданием. Напишем функцию для инициализации и обучения модели.

def fit_model(train_pool, test_pool, **kwargs):    model = CatBoostClassifier(        max_ctr_complexity=5,        task_type='CPU',        iterations=10000,        eval_metric='AUC',        od_type='Iter',        od_wait=500,        **kwargs    )return model.fit(        train_pool,        eval_set=test_pool,        verbose=1000,        plot=False,        use_best_model=True)

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

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

def classification_rate(y, y_pred):    return np.sum(y==y_pred)/len(y)

Поскольку данных мало, разбивать полную выборку на обучающую и проверочную частине лучший вариант. В этом случае лучше использовать методику OOF (Out-of-Fold). Мы не будем использовать сторонние библиотеки; давайте попробуем написать простую функцию. Обратите внимание, что разбиение набора данных на фолды необходимо стратифицировать.

def get_oof(n_folds, x_train, y, x_test, cat_features, seeds):    ntrain = x_train.shape[0]    ntest = x_test.shape[0]              oof_train = np.zeros((len(seeds), ntrain, 3))    oof_test = np.zeros((ntest, 3))    oof_test_skf = np.empty((len(seeds), n_folds, ntest, 3))    test_pool = Pool(data=x_test, cat_features=cat_features)     models = {}    for iseed, seed in enumerate(seeds):        kf = StratifiedKFold(            n_splits=n_folds,            shuffle=True,            random_state=seed)                  for i, (train_index, test_index) in enumerate(kf.split(x_train, y)):            print(f'\nSeed {seed}, Fold {i}')            x_tr = x_train.iloc[train_index, :]            y_tr = y[train_index]            x_te = x_train.iloc[test_index, :]            y_te = y[test_index]            train_pool = Pool(data=x_tr, label=y_tr, cat_features=cat_features)            valid_pool = Pool(data=x_te, label=y_te, cat_features=cat_features)model = fit_model(                train_pool, valid_pool,                loss_function='MultiClass',                random_seed=seed            )            oof_train[iseed, test_index, :] = model.predict_proba(x_te)            oof_test_skf[iseed, i, :, :] = model.predict_proba(x_test)            models[(seed, i)] = modeloof_test[:, :] = oof_test_skf.mean(axis=1).mean(axis=0)    oof_train = oof_train.mean(axis=0)    return oof_train, oof_test, models

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

Кривая обучения одного изфолдовКривая обучения одного изфолдов

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

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

После усреднения прогнозов:

balanced accuracy: 0.6703822994494413classification rate: 0.8198316498316498

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

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

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

balanced accuracy: 0.6549535670689709classification rate: 0.8108249158249158

Результат заметно хуже.

Итоги

В статье:

  • познакомились с данными и поискали идеи для модели;

  • очистили и подготовили данные для модели;

  • приняли решение использовать CatBoost, так как основная масса фичей категориальные;

  • написали функцию для OOF-предсказания;

  • получили отличный результат для базовой модели.

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

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

Код из статьи можно посмотреть здесь.

Подробнее..

Как организовать локальный чемпионат по робототехнике и сделать его традиционным (vol. 1)

14.03.2021 20:05:08 | Автор: admin

21 февраля 2021 года прошел уже четвертый Сахалинский чемпионат по робототехнике, который собрал 200 участников из 9 (из 18) муниципальных образований Сахалинской области, в пределах 100 гостей (родители, болельщики, неравнодушные граждане) и почти 30 тренеров и наставников, выступивших в роли судей прошедшего мероприятия. Возраст участников от 4 до 18 лет, 5 соревновательных направлений и конкурс интерактивных проектов, долгожданные партнеры, которые помогли обеспечить призовой фонд, мастер-классы для малышни и родителей, и наконец-то в дополнение к медалям и кубкам - дипломы победителей в рамках под стеклом. Этот чемпионат стал очередным психологическим барьером по количеству участников (правда, каждый предыдущий также преодолевал очередной порог), но что важно именно в ковидную эпоху и период длительного локдауна образовательной системы он показал востребованность и важность подобного мероприятия в островном регионе. Однако, перед этим четыре года работы, опыта, согласований, ошибок и удач.

Как все начиналось и почему

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

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

В 2016 году мы решили добавить в курсы для детей что-нибудь новое и родилась идея (в ту пору для центральной России уже совсем не новая, однако, как известно, до глубинки все доходит очень долго и с запозданием на 4-5 лет) ввести курсы по основам робототехники на конструкторах LEGO Mindstorms. Первая небольшая группа в 12 человек у нас занималась бесплатно (не знаешь сам учи других), для нас опыт в освоении новых технологий, для детей возможность использовать сухую математику и планиметрию хоть в какой-то практике.

И буквально сразу же, как из рога изобилия, на нас начали сыпаться возможности участия в различных мероприятиях (в области никто, кроме нас, не занимался робототехникой, а Министерству образования уже нужно было сдавать отчеты с показателями). Первый опыт дальневосточный полуфинал чемпионатов WorldSkills в то время в линейку движения входило направление JuniorSkills фонда Вольное дело Олега Дерипаски, ныне практически почившее. Собственно, в рамках этого JuniorSkills наши воспитанники и попробовали свои силы в этой самой робототехнике, а также показали нам, что мы движемся по правильному пути ребята (почти всегда робототехника это командные соревнования) завоевали третье место вреди команд ДВФО. Пару недель спустя нас пригласили принять участие в робототехническом фестивале РобоФест, да еще и стать региональными представителями (фактически операторами регионального отборочного этапа) данного направления. Первый серьезный выезд и первая серьезная конкуренция (это вам не 7 команд ДВФО) показали нам, как тренерам и преподавателям, что еще предстоит учиться и учиться (хотя ребята оказались в середине рейтинга по итогам фестиваля).

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

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

Найти себе конкурентов

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

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

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

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

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

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

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

Собственно, как было сказано выше, в течение 2016/2017 учебного года было принято решение о проведении 3 различных соревнований по робототехнике. Для этого пришлось пройти несколько курсов, сдать множество тестов на знание регламентов, один раз съездить на чужой окружной чемпионат линейки РобоФест (ранее это было необходимо для получения статуса судьи, в противном случае чемпионат в субъекте мог быть признан состоявшимся только при приглашении сертифицированного судьи из другого субъекта).

К этому моменту у нас уже прошли первые курсы для преподавателей, проведено несколько образовательных сессий в других образовательных учреждениях, и по итогу на первый нормальный региональный РобоФест собрано около 70 участников (фестивалили 3 дня, устали, но получили первый опыт организации проведения более-менее приличного научно-технического фестиваля). Плюс масштабное освещение в СМИ (по телевидению нас крутили каждый день, больше. Чем губернатора перед выборами). Само собой, с рекламной точки это дало хороший эффект, а также вывод, что овчинка, собственно, стоит выделки на длинной перспективе затраты на проведение и организацию чемпионата были меньше, чем потенциальный доход от нового контингента, пришедшего на платные курсы после проведения чемпионата.

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

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

Традиционно (по крайней мере у нас в субъекте), РобоФест собирал на уровне региона большее количество команд, нежели всероссийская робототехническая олимпиада. И это начало сеять первые диссонансы оба мероприятия имеют выход на уровень федерации, оба по робототехнике, оба весьма уважаемы. А ВРО еще и всемирный этап имеет, что как бы говорит об уровне мероприятия в принципе.

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

Незаслуженно остался почти не упомянутым в этой движухе очередной чемпионат WorldSkills (с все еще живым JuniorSkills), который прошел где-то в феврале 2017. Тогда в чемпионате выступило 10 детей (5 команд) на том же LEGO, фактически получилась тренировка перед выездом в Москву на РобоФест.

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

И вот здесь на поле боя вышел тот самый диссонанс. Посмотрев со стороны на все это дело, мы отранжировали сложность мероприятий для детей. JuniorSkills оказался самым простым и наименее массовым (кто не знает, компетенция считается состоявшейся, если в ней приняли участие 5 и более команд или участников). РобоФест из-за собственной погони за количеством участников федерального этапа по большей части решение образовательных задач по конструированию и программированию на LEGO (а затем не только на нем) не выглядел чем-то особенным (полигон черная линия на белой баннерной ткани и набор объектов, которые надо перевести из точки А в точку Б и прочие подобные задания). ВРО интересная инициатива, практико-прикладные задачи (как минимум информирование детей о проблемах мира, направлениях развития и прочие вещи), наличие какой-никакой преамбулы к заданиям, которая пытается раскрыть смысл тех или иных задач (сравниться с ВРО может First LEGO League там очень детально проработана мотивация участников к занятию робототехникой но так то ж те самые пропагандистские западные технологии, не иначе). Ну так вот это вот ВРО интересней для детей, но и сложнее. Все же все, кто принимает участие, работают с одними и теми же регламентами, и не важно сидишь ли ты в Сингапуре, в Москве, на Сахалине сложность заданий одинаково высокая и для регионального чемпионата, и для всемирного. Оттого и детей меньше принимает участие не все наставники рискуют связываться с заданиями такого уровня.

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

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

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

Есть еще один момент как мы знаем, кто девушку кормит, тот ее и танцует. То же самое происходит и в платном образования (опять-таки, вероятно в силу региональной специфики). Разделить детей по уровням получалось, но не всегда корректно. Приходит родитель, сует деньги, и говорит: Мой маленький гений это ваше лего уже три года собирает, он пойдет в группу по субботам с 10 утра, и точка. Все остальное время у него лыжи, английский, бег трусцой, хинди и бабушкин день рождения. Гений в это время если и собирает LEGO, то исключительно у себя из носа. К сожалению, специфика платных услуг и вопрос выживаемости на рынке, где становится все больше бесплатного дополнительного образования.

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

Пока я был в университете Иннополис во время проведения ВРО 2017 года, судьба познакомила меня с человеком, который принимал участие в организации чемпионата по робототехнике на кубок губернатора в рамках своего субъекта. В тому времени подобные чемпионаты проводились только в 3 субъектах (из уже 85). Из плюсов собственные задания, которые с ходом времени растут в зависимости от роста уровня детей в субъекте.

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

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

По итогу задания получились комбинацией отработки навыков, характерных для РобоФеста, обязательным наличием преамбулы и смысла в задании. По аналогии с ВРО и FLL. Из выбора грантодателя появилась и общая конва проекта, так задания все были объединены единой тематикой Устойчивое развитие Сахалинской области, а три соревновательных направления, их преамбула и игровое задание оказались связаны с перспективными (на тот момент) путями развития островного края Сахалинский туризм (1-4 классы), Сельское хозяйство (5-8 классы), Нефтегазовая промышленность (9-11 классы).

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

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

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

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

По итогам мы провели анализ прошедшего мероприятия, и сделали для себя ряд выводов, не только позитивных, но и негативных. Так, например, один из проколов медали мы выдавали каждому участнику, а вот кубок один на команду; итоговый рейтинг команд и результаты соревновательных заездов не был опубликован (не то, что в режиме реального времени, а вообще). К тому же одинаковый временной регламент работы для учеников 1-2 классов и 10-11 классов оказался сложен из-за разной скорости уставания. К тому же, в рамках первого чемпионата все дети выполняли три соревновательных заезда с перерывами на доработку робота и/или программы. Что ж, мы нашли, куда развиваться дальше.

Продолжение следует...

Подробнее..

Как организовать локальный чемпионат по робототехнике и сделать его традиционным (vol. 2)

19.03.2021 04:21:18 | Автор: admin

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

Ориентированность на образовательные организации или как найти новых участников

2017/2018 год принес, помимо нашего собственного чемпионата, все те же традиционные JuniorSkills (который больше не являлся частью WorldSkills и принялся сдуваться с еще большей скоростью), РобоФест и всероссийскую робототехническую олимпиаду. На First LEGO League мы, на самом деле, в реальной жизни мы посмотрели только в этом учебном году, но он убедил нас в необходимости наличия преамбулы и некоей истории чемпионата. Было и участие в федеральных чемпионатах, которые добавили нам как организаторам своего чемпионата новых компетенций разбивка временного регламента работы на потоки в зависимости от возраста, последовательное награждение всех возрастных категорий и соответствующий отказ от единого закрытия чемпионата, вывод промежуточных результатов заездов в общий доступ, организацию обязательной регистрации участников через сайт мероприятия и прочие интересные вещи.

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

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

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

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

А еще совпала такая интересная часть, что осенью же 2018 года команда нашей некоммерческой организации по запросу Общественной палаты Сахалинской области проводила серию семинаров по муниципалитетам острова (было затронуто 12 из 18 муниципалитетов) как раз на тему привлечения грантовых средств (попутно мы является ресурсным центром для некоммерческих организаций, но это еще одна другая история). Само собой, в качестве положительного опыта привлечения грантовых средств мы всюду демонстрировали ролик, снятый в рамках первого чемпионата. Это привело к тому, что люди, ответственные за образование (по линии органов местного самоуправления) как минимум узнали о наличии подобного мероприятия, мы заложили зерно будущего участия новых команд.

И попутно познакомились с руководителем частной образовательной организации, ведущей деятельность в самом северном городе острова Сахалин Оха. Где, собственно, в том числе были курсы по робототехнике для дошкольников и младших школьников, и тоже на LEGO (правда, наборы WeDo, а не EV3/NXT, которые использовались во всех остальных соревнованиях). Пообщавшись с руководителем, пообещали разработать отдельное направление чемпионата специально под наборы, которые есть в студии Роботекс города Оха. И осенью 2018 года, на второй чемпионат, к нам практически за 1000 километров приехали дошкольники! Даже несмотря на сложности в транспортировке (сначала ~8-9 часов на автобусе, затем ночь в поезде, а потом все то же самое на обратном пути), ребята приехали и показали нам, что чемпионат все же востребованное и правильное дело.

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

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

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

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

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

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

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

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

Количество участников чемпионата постепенно росло. Если первый чемпионат привлек 72 участника (из которых, напомню, большая часть была нашими учениками), во втором чемпионате уже приняло участие 112 детей (помните, там в самом начале я говорил, что каждый чемпионат пробивал очередной психологический барьер?). Третий чемпионат привлек 164 человека, а четвертый, самый сложный по организации и проведению (само собой на данный момент) 204 ребенка (из которых наши воспитанники 30 человек, да и вообще из Южно-Сахалинска было 50 команд, а еще 52 из других муниципалитетов области). И естественно, чем больше участников, тем больше недовольных, и с этим мы тоже со временем смирились. Особенно в самой конкурентной возрастной категории (Сельское хозяйство для 5-8 классов 40 команд).

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

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

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

С другой стороны, с 2018 года наша команда постепенно вливалась в движение WorldSkills (то нормальное, а не JuniorSkills) по компетенции Мобильная робототехника, с проведением региональных чемпионатов, участием в отборочных соревнованиях и Национальном финале (2018, 2019 и 2020 года). К этому моменту мы уже отказались от проведения региональных чемпионатов для РобоФеста, всероссийской робототехнической олимпиады, FLL, оставив при себе три линейки подготовки организацию и проведение (включая подготовку детей) нашего Сахалинского чемпионата по робототехнике, а также компетенции Робототехника и Мобильная робототехника в конкурсах профессионального мастерства Абилимпикс и WorldSkills. Да и с ростом количества федеральных соревновательных мероприятий и их отборочных региональных чемпионатов поняли, что такой темп из одного соревнования в другое не все наши дети начинают тянуть, что может привести к потере численности из-за усталости (а мы помним, что численность есть доход от платных образовательных услуг).

Фактически, из региональных чемпионатов с выходом на федеральный уровень в цикле 2020/2021 годов остался ИКаР (его региональной площадкой является городской Дворец детского (юношеского) творчества) и вернувшийся на Сахалин FLL (его площадкой является Сахалинский государственный университет при поддержке коммерческой фирмы, использующей данную площадку в рекламных целях). Оба оператора имеют возможность административного влияния на подведомственные муниципальные и региональные образовательные организации для обеспечения явки контингента.

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

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

Что мы попытались сделать? Ну во-первых для детей 5-11 классов мы сделали короба для укладки полей (до этого поля располагались на полу). А вот детям младше комфортнее оказалось работать на поле банально вследствие роста. Изменили конкурсное задание, набор полей и набор реквизита, необходимого для организации поля, хоть это и вызвало ряд недовольств со стороны некоторых команд и тренеров. При этом общая тематика Устойчивое развитие Сахалинской области - осталось. Во-вторых, начали расширять линейку соревнований, добавив конкурс интерактивных проектов. Пускай он прошел не так, как мы хотели изначально (но и первый чемпионат прошел не совсем в соответствии с нашими преставлениями и местами), однако он прошел и привлек 12 проектов, по большей части за счет того, что здесь уже не было ограничений на используемые робототехнические наборы.

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

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

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

Продолжение следует...

Подробнее..

ICFP Contest 2020 от идеи до воплощения. Как организовать контест и выжить

09.09.2020 20:04:18 | Автор: admin


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


Как все начиналось


Леша Кирпичников (beevee):


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

Последние два года мы писали организаторам, что хотим попробовать себя в новой роли и разработать следующее соревнование. В сентябре 2019 получили положительный ответ и предложение стать организаторами ICFPC 2020. Мы обрадовались, согласились и только потом задумались, куда именно мы вляпались :)


Про цель


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


Когда ICFPC только появился, 22 года назад, соревнование для программистов было редким явлением. Сейчас по миру проходит очень много разных соревнований, в такой реальности непонятно, какое место занимает ICFPC. Наш ответ такой: у всех остальных соревнований есть вполне определенный формат, а ICFPC это единственное место, где этот формат можно как угодно нарушить и делать максимально нестандартную штуку. Хочешь ботов писать иди на Coding Game и Russian AI Cup, хочешь алгоритмы на codeforces, а хочешь что-то необычное, свежее, непохожее ни на что на ICFPC.


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


Максимально продуманная легенда


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


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


Зачем этот турнир? Что будет с проигравшими? Какой приз ждет победителей? Мы не знаем! Но наверняка лучше выиграть, чем проиграть :) Поэтому за 72 часа наша задача выбрать самый лучший алгоритм, который способны сделать земляне, и отправить в финальную битву именно его. Финал в ICFP Contest это и есть наш земной турнир между лучшими программистами со всей Земли за право поучаствовать в инопланетном соревновании от имени всех землян.


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


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


Формулировка задачи, Иван Зайцев и Пеговка


Часто в ICFPC громоздкая формулировка задач. Однажды было 40 страниц спецификации, и мы ее читали 4 часа. Это нас деморализовало. И у нас появилась идея: что если сделать контест без спецификации вообще? Вместо четких правил будут инопланетные сообщения, которые участникам нужно будет разгадывать самостоятельно. Когда придумывали сценарий, было очевидно, что сообщения из космоса мы должны как-то получить.


Так родился образ астронома Ивана Зайцева, который принимает на свой радиотелескоп в Пеговской обсерватории сообщения от инопланетян и просит помощи в их расшифровке. Это все стало первым вводным видео на ломаном английском



Для него Леша Кирпичников отрастил бороду (шутка, она сама отросла за время карантина), нашел медицинский халат, принес перфокарты. Мы распечатали текст, который Леша читает, чтобы он был как бы написан на перфокарте. Сделали бейдж с именем Ивана Зайцева, работника Пеговской обсерватории. В пользу легенды также создали блог Ивана Зайцева


Запись первого видео
Запись того, как Леша читает текст с перфокарты


Реквизит
Перфокарта с текстом, бейджик Пеговской обсерватории и карандаш


Кроме этого видео, были посты в блог и еще два вводных видео.


В общем, всеми силами старались создать логичную историю. Это было максимально нестандартно. Никто так не делал раньше. Поэтому в самом начале контеста народ активно спрашивал: Что делать то? Где правила, инструкции, какой код писать? Как очки зарабатываются?. На что мы отвечали Ребята, какие еще очки! Мы получили сообщение от ИНОПЛАНЕТЯН, помогайте нам его расшифровать быстрее!. Все разгадки участникам нужно было закидывать в чат Discord, а мы собирали все дельные идеи в публично доступную спецификацию. Коллективный разум разгадывает в 10 раз быстрее, чем отдельные люди. Спецификация к задаче появилась через 4,5 часа, и вся она состояла из цитат участников в чате.


Почему Иван Зайцев


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


  1. Есть канадский астроном Yvan Dutil. Он один из авторов сообщения, которое в 1999 и 2003 гг. земляне отправляли к звездам с помощью радиотелескопа в надежде найти там разумную жизнь.
    Многие, наверное, знают о существовании SETI института поиска внеземного разума. Но есть еще и менее известный институт METI, который изучает возможности не просто наблюдения за космосом, а общения с внеземными цивилизациями. И с Земли уходило в космос уже несколько десятков посланий. Несколько из них имели вполне профессионально составленное содержание. Смотрите Arecibo message (1974) и CosmicCall (1999 и 2003). В нашем сеттинге мы находимся по другую сторону, мы получатели подобного сообщения.
    Тут есть интересная проблема, как составить сообщение и суметь в нем рассказать что-то нетривиальное существу, восприятие которого, может быть, сильно отличается от нашего. Они не знают, где верх и низ, не знают базовых понятий, с помощью которых можно это донести. Yvan Dutil один из авторов сообщения, которое реально отправили в космос.
  2. Александр Зайцев человек, фамилию которого мы взяли.
    Это российский астроном, радиофизик, глава российской организации SETI. Он один из идеологов и активистов, благодаря которым как раз и реализовались проекты CosmicCall и CosmicCall2.

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


Из чата организаторов


Почему Пеговка


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


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


Итого задача участников была такая


  1. Расшифровать инопланетное послание.
  2. Понять, что там описывается язык программирования и виртуальная машина, его выполняющая, с дисплеем и тачскрином :)
  3. Реализовать на своем любимом языке программирования виртуальную машину и выполнить на ней последнее самое большое сообщение от инопланетного корабля.
  4. В запустившейся программе (участники назвали ее galaxy из-за значка, которым она обозначалась у инопланетян) разобраться с особенностями инопланетного пользовательского интерфейса, понять, что речь идет о галактическом турнире.
  5. Найти обучающие туториалы и изучить с их помощью правил игры.
  6. Написать бота, который будет играть в игру и победит всех.

Как придумывали концепцию задачи


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


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


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


Паша Егоров (xoposhiy):


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

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

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

Паша Егоров взялся за эту идею и начал ее прорабатывать. Он приносил на встречи такие картинки:



Мы их весело разгадывали, и через какое-то время стало понятно, что это самая проработанная часть. К ноябрю 2019 у нас был прототип сообщений от инопланетян, в частности описание виртуальной машины (на основе SKI-комбинаторов). Мы определились, что после введения этого языка программирования мы дадим участникам большое сообщение, для расшифровки которого им надо будет написать виртуальную машину, исполняющую код на инопланетном языке. После исполнения кода перед глазами участников должен появиться тачевый интерфейс инопланетной операционной системы (мы его называли aPad как iPad, только aPad от alien). А вот что будет внутри этой операционки, до последнего оставалось загадкой. У нас были готовы авторская реализация виртуальной машины и несколько примеров программ, которые можно было на ней запустить.


Турнир и космические битвы


В декабре 2019 мы активно обсуждали содержание операционки. Победившей была идея PlanetWars. Бои кораблей, которые вращаются вокруг планеты в двумерном пространстве. Первые картинки этого выглядели так:



Идея требовала работы с числами с плавающей точкой. Это была проблема вводить на инопланетном языке стандарт IEEE 754 никому не хотелось. Но тогда на нас накатило вдохновение, полученное от решения задачек из 12 дня Advent Of Code, которые как раз тогда мы все решали: гравитация должна быть дискретной. Долгое время эта часть контеста так и называлась у нас с префиксом АoC в честь Advent of Code, который подарил нам идею.



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



(траектории на картинке декоративные, в пиксельном отображении их не было)


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


Инопланетный интерфейс


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


Саша Храмцов:


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

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




(история галактических боев с просмотром каждого боя)


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


Я себя просто представлял инопланетянином, висящим в пространстве перед таким голографическим объемным многослойным дисплеем. Так я ставил себя на место пользователя.


(интерфейс космического боя и управления кораблем)


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


Наша версия:


Одна из версий участников:

(это главный экран операционной системы, центр галактики точка (0, 0))


Саша Храмцов:


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


Во время контеста мы собирали скриншоты, которые участники публиковали в чате, твиттере и инстаграме получился целый альбом!



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



Про перевернутые картинки


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


Из чата участников:


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


Предлагаем вам трехминутную экскурсию по интерфейсу Галактики:



Инфраструктура


В прошлые годы во время участия мы всегда расстраивались из-за того, как сделаны системы сдачи решений: как правило нужно было собирать zip-файл, в котором лежали бы исходники, исполняемый файл и инструкция, как все это запускать. В 2020 году должно быть по-другому. Есть же автоматизированные CI/CD, можно все собирать по коммиту в репозиторий. Автоматически запускать в докере. И участникам не надо будет вообще ничего для сдачи делать, кроме обычного коммита в гит. Поэтому мы вложились в инфраструктуру очень сильно. Мы собирали коммиты из репозиториев команды, считывали из специального файла в репозитории, какой язык они используют, и запускали их код в подходящем докер образе. После сборки проводились тесты, и если все хорошо, специальная турнирная система запускала код в турнир: выбирала соперников и запускала игру друг против друга.


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


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


В общем, мы сделали то, что как промышленные разработчики умеем делать и не можем без удобства: сайт, CI/CD, гит, масштабирование.


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


Никита Сивухин:


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

Про 72 часа контеста на стороне организаторов


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


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



(Организаторы контеста за работой)


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


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



(Иван Зайцев смотрит трансляцию и переживает за судьбу землян)



(кадр из трансляции: можно было подглядеть крутые стратегии. На картнке корабль защитника разделился на много-много маленьких корабликов и их траектории выглядят запутанным клубком)


Демо боя можно посмотреть в отчете победителей


Про зрелищность и атмосферу


У ICFPC есть проблема: топовым командам обычно выгодно до последнего держать в секрете свои лучшие алгоритмы и выкладывать их в последние 5 минут. Чтобы все думали, что у них нет хорошего решения, и у противников не было шансов проанализировать и подготовиться.


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


Атмосфера соревнования была скорее дружеской: все обсуждали идеи, общались, подшучивали друг над другом. Например, мы изменили название постоянного участника ICFPC команды The Cat #1. Написали специальный код, который в лидерборде переименовывал название команды на текущее место, которое они занимают, например, место 12 и название становится The Cat #12. Это просуществовало часов 6, прежде чем ребята из команды написали в чат: Эй, вы чего сделали название нашей команды динамическим?))) Вы клевые, нам понравилось!.


Каким получился для вас этот контест


Вероника Самохина(aminopyrodin): Эпично сложным и необычным.
Леша Кирпичников: Мы делали контест, в который понравилось бы играть воображаемой идеализированной версии нашей команды. Команде из 5 или больше промышленных разработчиков, которые готовы почти не спать и рубиться все 72 часа, но при этом команде из гораздо более умных и крутых участников, чем мы сами. Это и хорошо, и плохо: нам бы точно понравилось в это играть, но были и команды с другими ценностями, которым это совсем не зашло. В конечном итоге по-другому и быть не могло: вряд ли мы бы стали делать что-то, что не понравилось бы нам самим.
Саша Храмцов: Максимально мозголомный, эпический и масштабный. Потому что история, которая за всем этим лежала, развернулась очень широко. Получилась настоящая история. Контест из виртуального превратился в настоящий.
Никита Сивухин: Многогранный и продуманный. Было очень много точек взаимодействия и компонентов системы как снаружи, так и внутри.


Про планы


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




Победители


Main round, 1st place


Первое место в основном раунде получила команда Closed and Restricted Boltzmann Machine (denplusplus). Ребята лучше всех выполнили задание, писали на Python, играли под нейтральным флагом, потому что все выходцы из России, но живут и работают в разных местах западного побережья США.


Main round, 2nd place


Второе место заняли две команды из Японии: многократные победители ICFPC Unagi, которые писали на Rust, и команда японских студентов 182020, их язык программирования C++. Эти команды обе заняли одно место, потому что их алгоритмы хоть и были разными, но показывали практически одинаковую результативность в турнире: то одна, то другая команда выходила вперед. Мы не смогли их разделить по разным местам и дали обеим командам второе место.


Lightning Round


Команда powder победитель lightning раунда. Этот раунд длится первые 24 часа: выигрывает та команда, которая добилась наибольшего прогресса за это время. В нашем случае они решили больше всех туториалов, обучающих, как вести космические бои. В составе команды четыре человека из разных стран. Ребята писали на языке Haskell.


Judges Prize


Приз жюри получила команда ребят из Уфы WILD BASHKORT MAGES (ripatti). Они так увлеклись написанием виртуальной машины, запускающей галактику, что решили реализовать своих ботов для игры так, что они играли без реверс-инжениринга протокола игры (как делали большинство), а нажимая на экран галактики и распознавая изображения. Неэффективно, но впечатляюще. Использовали язык OCaml.


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


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

Что почитать дальше


Пройти путь участника соревнования и попробовать расшифровать инопланетные сообщения


Начать нужно вот с этой страницы. Скачать recording of this message и попытаться понять, что же имелось в виду.


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


Чтобы отправлять сообщения инопланетянам, нужно воспользоваться нашим прокси-телескопом. Инструкция здесь.


Когда все сообщения до 41-го будут расшифрованы, попробуйте понять, что инопланетяне хотят от нас в главном 42-м сообщении.


Почитать книгу про реализацию функциональных языков программирования


Главная книга, которая помогала нам делать контест, это The Implementation of Functional Programming Languages, которую совершенно бесплатно можно прочитать здесь


Буквально нескольких первых глав достаточно, чтобы достойно справиться с задачей, описанной в инопланетных сообщениях :)


Сразиться в космическом бою с другой командой


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


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


Вдохновиться и посмотреть пару хороших фильмов по теме


Подробнее..

Из песочницы Конфуций и Маргарита

16.08.2020 18:20:26 | Автор: admin


Вступление


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

Глава 1. Никогда не разговаривайте на китайском


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

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

Глава 2. Пон Тий Пи Лат


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


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


Я расскажу вам об этом.


Маленький городок, где я родился...
...

Как видно из названия, это в основном субтитры к фильмам и сериалам. К такому же типу принадлежат и субтитры TED'a, которые после парсинга и очистки тоже превращаются во вполне себе параллельный корпус:

Вот чем обернулся наш исторический эксперимент в наказании:


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


И не только на улице, но и в их собственных домах,
WikiMatrix это выровненные LASER'ом тексты из интернет страничек (так называемый common crawling) на различных языках, но для нашей задачи их мало, да и выглядят они странновато:
Збраньки (укр.


Но вам лучше поститься, если бы вы только знали!


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

Есть очень понравившийся мне NLP курс от МФТИ на Степике [2], особенно полезный при прохождении онлайн, там на семинарах разбираются в том числе и системы машинного перевода, причем пишешь их ты сам. Помню восторг от того, что написанная с нуля сеть после обучения в Colab, выдала адекватный русский перевод в ответ на немецкий текст. Модели мы строили на архитектуре трансформеров с механизмом внимания, который в свое время стал прорывной идеей [3].

Естественно, первой мыслью было просто дать модели другие данные на вход и выиграть уже. Но, как знает любой китайский школьник, в китайской письменности пробелы отсутствуют, а наша модель на вход принимает наборы токенов, которыми в ней являлись слова. Разбить китайский текст на слова с какой-то точностью позволяют библиотеки типа jieba. Встроив токенизацию по словам в модель и прогнав ее на найденных корпусах, я получил BLEU около 0,5 (а шкала-то 100-балльная).

Глава 3. Машинный перевод и его разоблачение


К соревнованию был предложен официальный baseline (простое, но работающее решение-пример), который основывался на OpenMNT. Это открытый инструмент для обучения переводу с множеством гиперпараметров для подкрутки. На этом шаге давайте обучать и делать вывод модели через него. Обучать будем на платформе kaggle, так как она дает 40 часов обучения на GPU бесплатно [4].

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

Давайте теперь добавим к найденным на предыдущем шаге корпусам еще парочку:


Первый это огромный корпус юридических документов с заседаний ООН. Доступен он, кстати, на всех официальных языках этой организации и выровнен по предложениям. Второй еще более интересен, так как непосредственно является новостным корпусом с одной особенностью, он китайско-английский. Нас этот факт не смущает, потому что современный машинный перевод с английского на русский очень качественный, и в ход идут Amazon Translate, Google Translate, Bing и Яндекс. Для полноты картины покажем примеры из того, что получилось.

Документы ООН
Этот микроспутник представляет собой недорогостоящую платформу которая имеет умеренно продолжительный срок службы и в будущем может быть модифицирована.


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

UM-Corpus

Facebook закрыл сделку на покупку Little Eye Labs в начале января.
1Little Eye Labs

Четыре инженера в Бангалоре запустили Little Eye Labs около полутора лет назад.
Little Eye Labs

Компания строит программные инструменты для мобильных приложений, сделка будет стоить от 10 до 15 миллионов долларов.
10001500

Итак, наши новые ингредиенты: OpenNMT + качественные корпуса + BPE (про BPE токенизацию можно почитать здесь). Обучаем, собираем в контейнер, и после отладки/очистки и стандартных трюков получаем BLEU 6,0 (шкала по-прежнему 100-балльная).

Глава 4. Параллельные рукописи не горят


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

Тут мы подменяем задачу перевода на задачу выравнивания текстов. Сразу скажу, что эта часть мне понравилась больше всего, потому что сам я увлекаюсь изучением языков и параллельные тексты книг и рассказов, по-моему мнению, это один из наиболее продуктивных способов обучения. Идей для выравнивания было несколько, самой продуктивной оказалось переводить предложения в векторное пространство и считать косинусное расстояние между кандидатами на соответствие. Перевод чего-нибудь в вектора называется embedding, в данном случае это sentence embedding. Для этих целей есть несколько хороших библиотек [6]. При визуализации результата видно, что китайский текст немного сползает за счет того, что сложные предложения на русском часто переводят как два или три на китайском.



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

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


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


По виду лет сорока с лишним.

После обучения на новом корпусе, BLEU вырос до 20 на публичном датасете и до 19,7 на приватном. Тут сыграло и то, что в обучение очевидно попали произведения из валидации. В реальности так никогда делать нельзя, это называется утечкой, а метрика перестает быть показательной.

Заключение


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

[1] Параллельные русско-китайские корпуса
[2] Курс по Natural Language Processing от МФТИ
[3] Прорывная статья Attention is all you need
[4] Ноутбук с примером обучения на kaggle
[5] Публичный docker бейзлайн
[6] Библиотека для multilingual sentence embeddings
Подробнее..

Стратегия выбрать самую нелогичную стратегию, или как мы заняли второе место в Математической регате Тинькофф

14.08.2020 16:23:02 | Автор: admin
Всем привет! Мы студенты четвертого курса Прикладной математики и информатики Питерской Вышки. В июле мы поучаствовали в Математической регате Тинькофф, и в этом посте расскажем о том, что это за соревнование, о том, какова была наша стратегия, и покажем примеры задач.


Картинка с официального сайта Математической регаты

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

Итак, 18 июля пятеро студентов-программистов, которые вошли в состав команды Just4Fun, собрались участвовать в первом туре соревнования. С нами соперничала 391 команда, в каждой было по 35 человек. Всего 1628 участников из 131 города мира.

Правила первого тура


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

Начальный капитал команды 1000 очков. Каждая задача стоит от 100 до 500 очков: чем выше стоимость, тем сложнее задача. Если команда покупает задачу, ее стоимость вычитается из начального капитала (при этом нельзя уходить в минус). За верное решение с первой попытки начисляется $inline$2x$inline$ от стоимости задачи, со второй $inline$1.5x$inline$, с третьей $inline$1x$inline$.

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

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



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

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

Первый тур


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

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

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

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



Отдельно хочется остановиться на процессе решения задач. Все-таки мы скорее программисты, чем математики, и во время соревнования мы активно пользовались компьютером (это было разрешено правилами). Более половины задач мы решили при помощи Wolfram, Python и, неожиданно, C++ (для действительно быстрых переборов). С одной стороны, это не математично, но с другой позволило решить задачи в максимально короткие сроки.

Правила второго тура


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



Каждой задаче соответствовала доминошка (0:1, 0:2, ..., 6:6 всего 27 штук). В первые 2,5 часа команды решали задачи и собирали себе снаряды в виде доминошек.

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

Допустим, наша команда поставила доминошку [2:5] против команды N и решила, что число 5 будет соответствовать атаке, а 2 защите. Команда N поставила против нас доминошку с защитой 3 и атакой 4. Тогда наша команда получит урон, равный 2 $inline$(4-2=2)$inline$, и команда N тоже $inline$(5-3=2)$inline$. Каждое из этих чисел вычитается из очков команды, которая защищалась, и прибавляется к очкам нападающей команды. Побеждает команда с наибольшим количеством очков по итогам трех раундов.

Второй тур


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

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

По результатам финального тура мы заняли второе место, сильно отстав от первой команды и прилично обогнав третью. У нас 25 очков, у первой 55 и у третьей 14.

Общие впечатления


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

Задачки с турнира


Задача из первого тура


Тема: Вероятность.
Стоимость: 500.
У Вани есть два доллара. Он подбрасывает монетку. Если выпадает орел, Ваня получает 2 доллара; если решка, он теряет половину своих денег. Если решка выпала два раза подряд, то игра заканчивается, при этом в последнем раунде Ваня не теряет деньги. Найти матожидание количества денег у Вани после окончания игры.

Решение:
Найдем количество последовательностей длины $inline$n$inline$ из орлов и решек с фиксированным последним элементом, в которых нет двух решек, идущих подряд.

Число последовательностей длины $inline$n$inline$ с последней решкой обозначим как $inline$h(n)$inline$, с последним орлом $inline$F(n)$inline$.
$inline$h(n) = F(n 1)$inline$ (нельзя, чтобы предпоследний элемент тоже был решкой).
$inline$F(n) = F(n 1) + h(n - 1) = F(n - 1) + F(n - 2)$inline$ (предпоследний элемент любой)

Получили последовательность Фибоначчи c начальными данными $inline$F(0) = F(1) = 1$inline$.

Допустим, Ваня сделал $inline$n$inline$ бросков и игра не закончилась. Зафиксируем последнюю выпавшую сторону монетки (орел или решка) и обозначим сумму Ваниных выигрышей по всем последовательностям, удовлетворяющим условиям (последняя сторона зафиксирована и нет двух решек подряд), как $inline$f(n)$inline$ (последний орел) и $inline$g(n)$inline$ (последняя решка).

Осталось написать рекуррентные соотношения на $inline$f$inline$ и $inline$g$inline$.

Для начала разберемся с $inline$g$inline$. Заметим, что если последовательность оканчивается на решку, то предпоследним должен идти орел (т. к. двух последовательных решек быть не может), следовательно, $inline$g(n) = \frac{f(n 1)}{2}$inline$, при выпадении решки Ванина сумма уменьшилась в два раза.

Теперь с $inline$f$inline$. В этом варианте предпоследним может быть как орел, так и решка. По условию, выпадения орла просто добавляет 2 к сумме,т. е. $inline$f(n) = f(n 1) + g(n - 1) + 2F(n)$inline$ (вот для этого $inline$F$inline$ были посчитаны заранее).

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

Игра заканчивается тогда, когда Ваня выбрасывает вторую решку подряд. Заметим, что вероятность в итоге получить конкретную последовательность длины $inline$n > 1$inline$ (с двумя решками в конце) это $inline$\frac{1}{2^n}$inline$ (случайно равновероятно выбираем каждый элемент). Тогда осталось найти $inline$\sum\limits_{i = 2}^{+\infty} \frac{g(i 1)}{2^i} = \frac{f(i - 2)}{2^{i + 1}}$inline$.

Это некоторое техническое упражнение, далее идут соответствующие выкладки. Опустим корректность перестановки слагаемых в суммах.

Сперва вспомогательная сумма:

$$display$$S_1 = \sum_{n = 1}^{\infty} \frac{F(n)}{2^n} = F(1) + \sum_{n=2}^{\infty} \frac {F(n 1) + F(n - 2)} {2 ^ n} = \\ = F(1) + \frac{3}{4} \sum_{n = 1}^{\infty} \frac{F(n)}{2 ^ n} = F(1) + \frac{3}{4} S_1 \implies S_1 = 4$$display$$



И аналогичные действия уже для нашей рекурренты:

$$display$$S_2 = \sum \frac{f(n)}{ 2 ^ {n + 3}} = \sum \frac {F(n)} {2 ^ {n + 2}} + \sum \frac {f(n 1) + f(n - 2) / 2} {2 ^ {n + 3}} = \\ = S_1 / 4 + \frac{5}{8} S_2 \implies S_2 = \frac{8}{3}$$display$$



Ответ: $inline$\frac{8}{3}$inline$

Задача из второго тура


Соответствовала доминошке [2:3].

Больше всего запомнилась одна простая задачка из второго тура. В ней требовалось посчитать, сколько раз нужно проделать операцию $inline$DF$inline$ с кубиком Рубика, чтобы он вернулся в исходное состояние (операция $inline$DF$inline$: сначала по часовой стрелке повернуть фронтальную часть, затем по часовой стрелке повернуть нижнюю часть).

Математическое решение:
Заметим, что повороты кубика рубика можно описать с помощью некоторой подгруппы симметрической группы S_48.

Обозначим поворот фронтальной части как $inline$F$inline$, а нижней как $inline$D$inline$. В таких обозначениях мы с кубиком сначала совершаем операцию $inline$F$inline$, а затем операцию $inline$D$inline$. Таким образом, если кубик находился в состоянии $inline$x$inline$, то он после одного хода перейдет в состояние $inline$DFx$inline$. Мы хотим найти минимальное количество шагов, которое нужно, чтобы перевести кубик в исходное состояние. Т. е. нужно посчитать порядок элемента $inline$DF$inline$. И $inline$D$inline$, и $inline$F$inline$ описываются перемножением перестановок. Давайте перемножим их все и обозначим результат как некоторую перестановку p. Чтобы посчитать ее порядок, достаточно найти НОК длин ее циклов.

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

Ответ: 105.
Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru