Всем привет! Во втором семестре все первокурсники программы Прикладная математика и информатика в Питерской Вышке делают командные проекты по С++. Мы занимались разработкой умной футболки.

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


Мы Денис Тарасов и Денис Филиппов студенты уже второго курса бакалавриата Прикладная математика и информатика в Питерской Вышке. Мы работали над проектом вместе с Яном Фрейдкиным и Иваном Чунаревым. С ними мы учились в одной школе: Санкт-Петербургском ГФМЛ 30.

В 11 классе у Яна и Ивана был проект по робототехнике Умная футболка (она на первой фотографии). Идея такова: берётся футболка, на неё крепятся различные датчики (акселерометр, гироскоп и другие). По считываемым данным можно определить некоторые показатели, например, корректность осанки. Ребята успели принять участие в нескольких конференциях и собирались после окончания школы продолжить работу над проектом, но поняли, что им нужны программисты. Собственно вот мы и здесь.

Футболка Яна и Ивана могла считывать ЭКГ и отслеживать корректность осанки. Для этого использовалась Arduino UNO платформа разработки с устаревшими микроконтроллерами AVR. Достаточно скоро им стало не хватать памяти для кода. На новой стадии работы над проектом мы поняли, что нужно предъявлять более строгие требования к микроконтроллеру:

• Чтобы можно было подключить больше датчиков, необходим был процессор с большей частотой, большее количество периферии и более скоростная периферия;
• Больший объем flash памяти, оперативной памяти;
• Меньшая стоимость;
• Стабильность работы микроконтроллера.

Мы решили, что нужно менять микроконтроллер. У нас было два варианта: использовать более мощный микроконтроллер серии AVR (в нашем случае Arduino) или перейти на другую серию микроконтроллеров, а именно ARM (в нашем случае STM32). Несмотря на большое сообщество Arduino и простоту в использовании этого микроконтроллера, мы решили перейти на STM32, потому что его производительность лучше, а объем памяти больше. Сейчас мы используем микроконтроллер серии STM32f4*.


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

Первые шаги. Зажгли светодиод

У нас не было опыта программирования микроконтроллеров, и мы прочитали, что инициализация и объявление датчикови пинов на STM это долго и сложно. Поэтому мы использовали высокий уровень абстракции с помощью библиотеки HAL и STM32CubeMX. STM32CubeMX инструмент, который с помощью графического интерфейса настраивает порты микроконтроллера и генерирует соответствующий код, использующий библиотеку HAL. Сначала мы решили сделать самую базовую в программировании микроконтроллеров вещь (на уровне Hello world) зажечь светодиод.


Интерфейс STM32CubeMX

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



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

Прошивка микроконтроллера

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


Общение с микроконтроллером осуществляется по шине I2C. Благодаря библиотеке HAL передача данных производится легко: необходимо вызвать функцию для чтения/записи. Пример чтения данных с акселерометра из кода:

HAL_I2C_Mem_Read(i2c_handle, addres, ACCEL_XOUT_H_REG, 1, buffer, 6, 1000)

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

HAL_I2C_Mem_Write(i2c_handle, addres, GYRO_CONFIG_REG, 1, &Data, 1, 1000)

Также у нас был Bluetooth модуль (HC-05 и HC-06), но он не требовал каких-либо особых манипуляций для работы. После его подключения можно просто слать данные через универсальный асинхронный приемопередатчик (UART) специальное устройство внутри микроконтроллера, которое позволяет общаться с другими устройствами. Для него в HAL предусмотрены функции, схожие с функциями для I2C. Мы лишь написали небольшую обертку над ними, чтобы было проще выводить сообщения во время отладки.


HC-06

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

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

class Controller {std::vector<std::unique_ptr<IMU>> IMUSensors; // список сенсоровstd::queue<Request> reqQueue; // очередь запросовstd::vector<std::pair<std::unique_ptr<BaseFunc>, bool>> mithrilFuncs; // список пар //<функция футболки, включена ли она>Controller();void Run(); // основной цикл программы};

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

Что там по прототипу

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

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

Приложение для Android

Мы поставили перед собой цель создать Android-приложение с возможностью общаться через Bluetooth с микроконтроллером. Как и в случае с программированием микроконтроллеров, опытом написания приложений под Android мы не обладали, однако найти информацию про Android оказалось намного легче, чем про STM32. Основы мы изучали при помощи курса на Stepik.org (курс действительно неплохой), где сначала разбирают основы языка Kotlin, а затем рассказывают о программировании под Android.

Первая версия приложения позволяла подключаться к микроконтроллеру через Bluetooth и передавать ему сообщения. Последняя версия не сильно отличается от первой (написание приложение для нас не было в приоритете): в ней появились виджеты для запуска калибровки и включения/выключения функции слежения за корректностью осанки.

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


Меню навигации


Вкладка для подключения через Bluetooth


Вкладка для обмена данными

Обработка осанки

Мы пришли к двум разным способам обработки осанки: с помощью методов анализа данных и без них.

Обработка осанки с помощью методов анализа данных

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

Сначала мы сняли с себя данные: углы закручивания и показания акселерометра с каждого из датчиков. Получили примерно 2000 замеров: около 1000 положительных и 1000 отрицательных. Конфигурация датчиков была следующая (два датчика расположены на лопатках и два на позвоночнике):



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



Проекции данных в двумерное пространство.

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


Далее необходимо было выбрать модели для предсказания. Мы решили попробовать линейную регрессию, а точнее ее модификацию Ridge, метод опорных векторов (SVM) с линейным ядром и дерево принятия решений. Выбор обусловлен простотой переноса моделей на микроконтроллер: первые две описываются некоторым количеством коэффициентов, а последняя представляет из себя набор условий if-else. Модели были взяты из библиотеки scikit-learn. Пример переноса линейной регрессии:

bool isPostureCorrect =(a11 * deviceAngles1[0] + a12 * deviceAngles1[1] + a13 * deviceAngles1[2] +           g11 * deviceGravity1[0] + g12 * deviceGravity1[1] + g13 * deviceGravity1[2] +           a21 * deviceAngles2[0] + a22 * deviceAngles2[1] + a23 * deviceAngles2[2] +           g21 * deviceGravity2[0] + g22 * deviceGravity2[1] + g23 * deviceGravity2[2] +           a41 * deviceAngles3[0] + a42 * deviceAngles3[1] + a43 * deviceAngles3[2] +           g41 * deviceGravity3[0] + g42 * deviceGravity3[1] + g43 * deviceGravity3[2]) > bias;

значения a??, g??, bias берутся из обученной модели.

Точность моделей с разной конфигурацией на тестовой выборке можно увидеть в таблице:


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

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


Пример дерева принятия решений.

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

Обратка осанки без методов анализа данных

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

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


Показатели осанки у людей с большим депрессивным расстройством до (A) и после (B) лечения из статьи J.Canales et al (2010)

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



Конфигурация датчиков

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


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

Демо-видео

Вот демо-видео работы футболки и приложения:


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

Заключение

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

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

Теперь немного о наших планах на будущее. Мы хотим:

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

Ссылки на гитхаб проекта:

github.com/DT6A/Mithril прошивка микроконтроллера,
github.com/DT6A/MithrilApp приложение для android,
github.com/DT6A/MithrilData работа с данными.

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

Под катом подробности внутренней кухни: рассказ о том, как была устроена работа над проектами.



Кратко: каждой команде назначили менторов из числа действующих разработчиков или студентов старших курсов с опытом работы в IT-компаниях. Еженедельно первокурсники рассказывали о прогрессе и сложностях, с которыми пришлось столкнуться, в анкете и во время созвона с ментором. Чтобы команды потренировались выступать публично (а заодно чтобы установить дедлайны, к которым нужно готовиться), мы организовали две предзащиты. На финальной защите все команды успешно представили проекты, средний балл студентов 9,0 по 10-балльной шкале.

Теперь подробнее:

Об организаторах

Мы Наташа Мурашкина, Саша Орлова и Оля Лупуляк студентки старших курсов Прикладной математики и информатики в Питерской Вышке. Мы занимались организацией проектов под руководством куратора направления и лектора курса по С++ Егора Суворова.

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

О проектах

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

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


Демо-видео проекта Fivaproljo (мультиплеерный платформер)

К концу семестра необходимо было получить хотя бы MVP проекта, но многие команды успели добавить больше функциональностей, а кто-то даже написать тесты и оформить страницу на GitHub с описанием и инструкцией по запуску. Примеры: Моделирование и визуализация динамических систем, Анализатор кода UB-tester tool, Компьютерная версия игры Колонизаторы.

Подготовка

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

Ментор это сотрудник IT-компании или студент старших курсов с опытом промышленной разработки. Менторы помогали с распределением задач и решением технических проблем. Они еженедельно созванивались со студентами, чтобы обсудить прогресс и составить план работ на следующую неделю. В число менторов вошли стажеры и сотрудники JetBrains, Яндекса, ВКонтакте, Huawei, Google, Delightex, VeeRoute и других компаний, преподаватели Летней компьютерной школы (ЛКШ), а также студенты нашего факультета, московского кампуса Вышки и кафедры КТ университета ИТМО.

В качестве эксперимента мы даже пригласили мета-ментора (ментора для ментора): опытный сотрудник Google наставлял нашего старшекурсника в менторстве команды.

Работа в течение семестра

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

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

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

Воркшопы

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

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

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

Структура презентации для воркшопов

• Титульный слайд
• Введение в область
• Краткое описание проекта
• Сравнение с аналогами
• Сравнение технологий
• Разбиение на подзадачи для каждого участника (по слайду на участника)
  
  • Описание подзадачи, решение, выводы
• Описание текущего состояния проекта (что было сделано с начала)
• Описание прогресса с предыдущей презентации
• Планы до конца разработки
• Можно сделать демо-видео не длиннее 30 секунд

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


Демо-видео проекта Моделирование и визуализация динамических систем

Как оценивали вклад каждого участника

Здесь нам помогали коммиты студентов на GitHub и анкеты менторов.

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

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

Итоговая оценка каждого студента за семестр складывалась из трех частей:

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

Итоги

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


Скриншот с защиты проекта TorrentX

Мы довольны результатами ребят. Трое студентов (из 61) получили оценку удовлетворительно, все остальные хорошо и отлично. Средний балл 9,0 по 10-балльной шкале.

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

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

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

Как и мы :) Так что в следующем году планируем продолжить.

Планы на будущее

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

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

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

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

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

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

И еще +100 заметок, которые мы бережно сохраняли в течение семестра.

Если вы хотели бы на волонтёрских основах побыть ментором студентов-первокурсников в следующем году, заполните форму или напишите нам в Телеграме (@murfel). Будем рады!

Привет!

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

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



В нашей команде 3 человека: Юра Худяков, Валера Головин, Миша Саврасов. Для каждого из нас это первый командный проект, так что в процессе работы мы не только писали на плюсах, но ещё и учились работать в команде и пользоваться системами контроля версий (в нашем случае git). В проекте есть некоторое количество странностей, в частности, велосипедов есть хорошие готовые решения, которыми можно было бы воспользоваться. Однако цель нашего проекта заключалась в том, чтобы получить опыт, так что многое мы придумывали и реализовывали самостоятельно.

Что такое Интеллектор?

Для начала стоит объяснить, что за игру мы писали.

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


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

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

Отличия в механике игры возникают из-за специфики поля. Поле Интеллектора симметрично, и это существенно отличает его от шахмат с их королевским и ферзёвым флангами.

Для понимания этой статьи знание правил и умение играть не потребуются.

Общая архитектура

Что мы хотели получить в нашем приложении?

Для того, чтобы игра заработала, нужно реализовать её основную составляющую: логику игры. В неё входит модель доски и правила ходов. Кроме того, для удобства стоит хранить историю ходов и реализовать отмену/повторение хода.

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

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

План приложения:

1. Логика игры
   • Модель гексагональной доски
     Хранится в виде двумерного массива гексагональных клеток
   • Правила перемещения фигур
     Проверка допустимости хода, получение всех доступных ходов для фигуры, для игрока
   • История ходов
     Отмена и повторение хода
2. Интерфейс
   Планировали 2 интерфейса: ncurses и Qt. В проекте реализован только ncurses, подробнее в разделе Интерфейс.
   • Вывод поля
     Отрисовка и обновление поля в консоли
   • Перемещение курсора клавишами клавиатуры, игра без мышки
   • Отображение текстовой истории ходов
   • Отображение главного меню
3. Бот
   • Случайный бот
   • Жадный бот
   • Альфа-бета бот
     Оптимизировано перебирает все ходы

Как это сделано?

Очень упрощенно архитектуру приложения описывает эта схема:


Раздел Game отвечает за всю игровую логику и хранит доску.

Когда включена игра с компьютером, Game взаимодействует с ботом из Bot

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

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

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

Модель игры

Гексагональная доска

Рассмотрим раздел Game из схемы выше. Он должен хранить доску и обрабатывать всю внутриигровую логику.

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

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


^{Координаты клеток по горизонтальной оси w и вертикальной оси h}

Для удобства описания перемещения фигур мы будем использовать трехмерные координаты. Выберем некоторую клетку в качестве опорной с координатами {0,0,0} (для удобства она будет совпадать с клеткой (0, 0) массива).


^{Трехмерные координаты клеток относительно центральной клетки с координатами {0,0,0}}

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

При этом клетки нумеруются неоднозначно. Например, если из центральной клетки с координатами {0,0,0} мы сдвинемся влево вниз, а затем вверх, то получим координаты клетки {0,1,-1}. Но эта же клетка имеет координаты {1,0,0} если прийти в нее напрямую из центральной клетки, как видно на предыдущем рисунке.


^{Другой вариант задания координат клетки {1,0,0}.}

Обход любой клетки по циклу влево-вниз вверх вправо вниз приводит нас в ту же клетку, но добавляет к её координатам вектор {-1,1,-1}, сумма координат которого равна -1. Выполняя мысленно такой обход в ту же или в обратную сторону несколько раз, мы можем изменять координаты любой клетки на эквивалентные, которые будут отличаться на вектор, пропорциональный {-1,1,-1}. Чтобы избавиться от неоднозначности, в каждом классе эквивалентности выберем в качестве представителя тройку координат, сумма которых равна нулю. Такой выбор координат является единственным (докажите!).

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

Position(int w, int h) // конструктор из двумерных координат        : x_{-w/2  w % 2 - h}        , y_{w % 2 + 2 * h}        , z_{w / 2  h} {}int posW() const { // метод для получения первой координаты двумерного массива    return -x_ + z_;}int posH() const { // метод для получения второй координаты двумерного массива    return (x_ + z_  (x_ + z_)%2) / 2 + y_;}

Обратите внимание, что конструктор выдает координаты (x,y,z), сумма которых равна нулю. При этом конвертация координат (x,y,z) в (w,h) работает корректно для любого набора координат (сумма не обязательно должна быть равна нулю).

Как мы нашли все эти формулы? Методом научного тыка: путем анализа изменения трёхмерных координат при сдвиге одной из двумерных координат на 1 (конструктор) и в обратную сторону (методы).

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

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

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

Ходы для фигур

Мы сделали класс FigureMoveValidator, у которого 6 наследников для каждого типа фигуры (можно было обойтись и без наследников, если в каждом методе делать switch case на тип фигуры). Конструктор класса имеет 2 параметра: позиция и ссылка на доску. Также в классе есть два метода allMoves и checkMove.

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

Теперь checkMove. Мы помним, что умеем проверять, лежат ли фигуры на одной прямой. Если проверим, что на этой прямой нет других фигур, то получим готовый метод для Доминатора (аналог ладьи). Если фигуры лежат на одной прямой, то мы можем найти расстояние между ними, и получить методы для Прогрессора (пешка), Дефенсера (ходит как король), Интеллектора (король, только не может рубить) и Либератора (может ходить через одну клетку в любую сторону). Остался еще агрессор (аналог слона), который ходит в клетки по диагоналям в шесть направлений от текущей (из клетки {0, 0, 0} в {0, 1, 1}, в {0, 2, 2} и т.д.: см. серые клетки на картинке ниже). Для этой фигуры можно попробовать обнулить одну из координат и проверить, что оставшиеся 2 координаты равны по модулю (спасибо трёхмерным координатам).


^{Возможные ходы для агрессора}

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

Интерфейс

Архитектура

Приложение написано на консольной библиотеке ncurses (вот туториал к ней). Эта библиотека позволяет создавать псевдографику в консоли. К примеру, на ней основаны Midnight Commander и Nano.

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

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

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

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

Вот что происходит, если игрок захочет узнать доступные для хода поля:

1. Игрок перемещает курсор на поле с фигурой и нажимает пробел
2. Поле с фигурой помечается как выбранное
3. Интерфейс обращается к методу selectCell у контроллера
4. Метод selectCell обращается к методу allFigureMoves у модели
5. allFigureMoves создаёт FigureMoveValidator, который вычисляет все доступные ходы
6. allFigureMoves передаёт найденные ходы обратно контроллеру
7. Контроллер передаёт их интерфейсу
8. Интерфейс перерисовывает поле, подсветив доступные поля

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

Как рисуется поле?

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


^{(Злой Пакман, нарисованный буквами о)}

Функция move(int y, int x) в ncurses меняет текущую позицию, а функция addch(chtype c) добавляет символ и смещает текущую позицию на 1 вправо (x > x+1).

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

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

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

attron( *attributes* );addch(c);attroff( *attributes* );

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

Изображения для вывода можно хранить в коде (так мы делали изначально), а можно в отдельных файлах и читать из них при запуске программы. Для этого мы придумали собственный формат файла *.btn.

В нём хранится текстовая картинка, которую прочитает и выведет игра. Например, фигура, или надпись White wins/Black wins, или кнопка меню. При этом иногда может понадобиться прозрачность, чтобы не перезатирать нарисованное ранее. Для этого можно в первую строчку добавить решётку # и после список прозрачных символов, которые будут проигнорированы при выводе.

Например, пусть у нас на экране нарисованы 3 прямоугольника:


Добавим в центр прямоугольник из такого файла:

#CAAAAAAAAAACCCCCCCAACCCCCCCAACCCCCCCAACCCCCCCAACCCCCCCAAAAAAAAAA

И получим следующую картинку:


^{(жёлтым подсвечено для наглядности)}

Особенно этот формат пригодился при разработке меню.

Меню

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

Кнопки меню читаются из файлов *.btn. На этих кнопках должен быть крупный красивый текст. Красиво рисовать с помощью ASCII символов мы не умеем, зато умеет figlet утилита для вывода ASCII-текста разными шрифтами:


Кнопки обрамляют надписи, прочитанные из файла:


Затем они центрируются и последовательно выводятся:


В некоторые менюшки можно провалиться и, например, настроить сложность и цвет бота:


Самая интересная часть разработки системы меню это объединение её элементов в одну систему. Этим занимается отдельный элемент системы, который мы назвали мультиплексор. Название навеяно терминальными мультиплексорами.

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

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

Бот

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

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

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

Всего в игре есть три разных вида ботов:

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

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

Всего в OptimizedAlphaBetaBot были реализованы 3 крупных оптимизации (здесь они представлены в порядке убывания полезности):

• Использование откатов ходов. После этой оптимизации больше не нужно было множество раз копировать доску, чтобы сделать какой-то ход.
• Написание нового класса с говорящим названием FigureKeeper, который хранит список фигур каждого цвета, которые сейчас есть на доске. Стало возможным обойти один std::vector вместо всей доски.
• Запоминание уже обработанных позиций с помощью std::unordered_map и Zobrish hashing.

Кроме крупных оптимизаций были и более мелкие. Например, если перед сортировкой просчитать все стоимости позиций на доске с учетом определенного хода, то сортировать уже нужно не сложные объекты Move, а просто intы.

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

Однако архитектура бота все еще поддерживает добавление новых оценочных функций. Для этого нужно определить всего три вещи:

1. Функцию, если нужно посчитать стоимость с нуля по данному расположению фигур
2. Дельта-функцию, которая должна по данному ходу быстро пересчитать стоимость.
3. Номер этого набора функций для конструктора специального класса FunctionSet.

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


^{Игра 2 ботов одинаковой сложности (4 уровень из 6 возможных). Курсор всю игру стоит по центру поля}

Заключение

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

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

Возможно, в ближайшее время всё или часть из этого появится. А пока что спасибо за чтение!

Github-репозиторий

Для программистов настали тяжёлые времена. Хотя Утечка Памяти была уничтожена valgrind-ом, оставшиеся силы UB преследовали программистов по всей галактике.

Избегая встречи с грозными знаковыми переполнениями, группа борцов за свободу, ведомая Кириллом Бриллиантовым, Глебом Соловьевым и Денисом Лочмелисом, обустроила новый секретный репозиторий.

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

Мы трое студентов бакалавриата Прикладная математика и информатика в Питерской Вышке. В качестве учебного проекта во втором полугодии мы решили написать UB-tester анализатор кода на С++.

Вступление

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

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


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


Пример: программа, складывающая два числа типа int, может вызывать UB при переполнении знакового числа, а ее обработанная версия нет.

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

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

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

Сlang и AST

Первым шагом работы ub-tester является нахождение всех ошибкоопасных мест в программе. Парсить код на C++ вручную и с нуля путь в могилу (или по крайней мере в отдельный проект), поэтому нам предстояло подобрать инструменты для решения этой задачи. Пожалуй, самым известным и наиболее практичным инструментом по разбору исходного кода на плюсах является clang, поэтому мы выбрали его в качестве основы для нашего проекта. Сlang большая библиотека, поэтому остановимся только на важных для понимания статьи понятиях.

Сперва стоит сказать об AST (Abstract Syntax Tree). Это структура данных дерево (как можно было догадаться из названия), внутренние вершины которого соответствуют операторам языка, а листья операндам. Вот пример AST для простой программы.

Исходный код:

if (a > b) {print(a);} else { print(b);}

AST:


Описанная абстракция и используется в clang-е для представления исходного кода. Такой структуры данных достаточно для обнаружения ошибкоопасных мест. К примеру, чтобы найти в программе теоретически возможные index out of bounds, нужно изучить все вершины AST, соответствующие операторам обращения к массиву по индексу.

Теперь дело остается за малым: получить доступ к AST. В clang-е существует несколько механизмов для решения этой задачи. Мы пользовались Visitor-ами.

В clang-е реализован базовый класс RecursiveASTVisitor, осуществляющий дфсный обход AST. Каждый Visitor должен от него наследоваться, чтобы уметь путешествовать по дереву. Далее, чтобы выполнять специфичные для определенных вершин операции, класс-наследник должен иметь набор методов вида Visit***, где *** название узла AST. Оказываясь в вершине дерева, Visitor вызывает соответствующий ее названию метод Visit***, затем рекурсивно спускается в ее детей. Таким образом, чтобы создать своего Visitor-а, достаточно реализовать методы обработки конкретных вершин.

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

class FindBinaryOperatorVisitor : public clang::RecursiveASTVisitor<FindBinaryOperatorVisitor> { public:bool VisitBinaryOperator(clang::BinaryOperator* BinOp) { std::cout << BinOp->getBeginLoc() << \n;return true;}};

Теперь можно со спокойной душой переходить к следующему пункту: к замене участков исходного кода.

CodeInjector

Сразу скажем, что, вероятно, мы избрали далеко не лучшее решение этой задачи. Мы разработали класс CodeInjector, который

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

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

Простой пример. Есть такое выражение:

arr[1] + arr[2];

Пусть мы сначала захотим поменять сложение на ASSERT_SUM, получим следующее:

ASSERT_SUM(arr[1], arr[2]);

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

ASSERT_SUM(ASSERT_IOB(arr, 1), ASSERT_IOB(arr, 2));

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

Мы заметили, что схемы замен состоят из чередования кусков, которые мы оставляем, и кусков, которые мы заменяем. Проиллюстрируем на примере: выражение: arr[1+2]. В нем есть два ошибкоопасных места: обращение к массиву и операция сложения. Должны произойти следующие замены:

• arr[1+2] заменяется на ASSERT_IOB(arr, 1 + 2)
• ASSERT_IOB(arr, 1 + 2) заменяется на ASSERT_IOB(arr, ASSERT_SUM(1, 2))
  arr[1 + 2] ~~~~~> ASSERT_IOB(arr, 1 + 2) ~~~~~~> ASSERT_IOB(arr, ASSERT_SUM(1, 2)
  

Далее мы, внутри команды, договорились об интерфейсе для взаимодейстия с CodeInjector-ом, основанном на этой идее.

Все готово! Можно приступать к самому интересному работе с конкретными видами UB.

Функционал

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

Основные ошибки, выявляемые нашей программой:

• выход за границы С-шного массива;
• UB в целочисленной арифметике;
• обращение к неинициализированной переменной.

Подробно про некоторые аспекты функционала мы расскажем далее.

Целочисленная арифметика

Известнейшие представители UB арифметике целочисленные переполнения в самых разных операциях. Есть и более изощренные UB, которыми могут похвастаться, например, остаток от деления и особенно битовые сдвиги. Кроме того, часто можно встретить составные операторы присваивания (+= и другие) и операторы инкремента/декремента. Во время их использования происходит целая цепочка неявных преобразований типов, которая и может повлечь крайне неожиданный и нежеланный результат. Да и неявные касты сами по себе могут служить большой бедой.

Так или иначе, общее правило для всех UB в арифметике их сложно найти, легко проглядеть (никаких segfault-ов!) и невозможно простить.

Важно: впредь и далее речь пойдет про стандарт С++17, на который и ориентирован ub-tester. Он также поддерживает C++20, но из-за того, что в нем исчезли некоторые виды UB в арифметике (а новых не добавилось), про него говорить не так интересно.

int a = INT_MIN, b = -1, z = 0;int test1 = a + b; // overflowint test2 = a * b; // overflowint test3 = a << 5; // lhs is negative => UBint test5 = 5 % z; // % by 0 => UBint test6 = --a; // overflow

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

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

template <typename T>ArithmCheckRes checkSum(T Lhs, T Rhs) {  FLT_POINT_NOT_SUPPORTED(T);  if (Rhs > 0 && Lhs > std::numeric_limits<T>::max() - Rhs)    return ArithmCheckRes::OVERFLOW_MAX;  if (Rhs < 0 && Lhs < std::numeric_limits<T>::lowest() - Rhs)    return ArithmCheckRes::OVERFLOW_MIN;  return ArithmCheckRes::SAFE_OPERATION;}

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

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


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

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

Вы с другом пошли в лес и решили прибавить к чару единицу Красиво прибавить, то есть ++c. Будет ли вас ожидать в следующем примере UB?

char c = 127;++c;

И тут понеслось. Во-первых, безобидный префиксный инкремент решил вычисляться наподобие своему старшему собрату, то есть как составное присваивание c += 1. Для этого он привел c и 1 к общему типу, в данном случае к int-у. Затем честно посчитал сумму. И перед записью результата обратно в c, не забыл вызвать неявное преобразование к char-у. Уф.

И UB не случилось. Действительно, само сложение произошло в большом типе int, где число 128 законно существует. Но при этом результат все равно получился с изюминкой, благодаря неявному приведению результата к char-у. Более того, такое приведение чисто теоретически могло закончится не -128, а чем-то особенным в зависимости от компилятора документация это допускает, ведь тип знаковый.

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

В случае с операторами составного присваивания AST не жалеет информации, поэтому проследить цепочку преобразований типов несложно. Далее несложно и проверить корректность вычисления в одном типе, затем неявное приведение к исходному (обе такие проверки уже есть в арсенале). Однако по поводу инкремента/декремента AST отказалось сотрудничать, скрыв всю кухню преобразований. Решением было внимательно прочитать документацию С++, а затем начать цепочку приведений с std::common_type от типа аргумента и int-a (типа единицы). Искушенный clang-ом читатель может поймать нас за руку, заметив, что именно по поводу таинственных ++ и AST, вообще говоря, знает, возможно переполнение или нет.


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

Неинициализированные переменные

Каждому, кто знаком с C++, известно (но зачастую это анти-интуитивно для новичков, пришедших из других языков): если объявить переменную базового типа, но не проинициализировать её никаким значением, а потом в неё посмотреть возникает UB. В то же время, такой синтаксис бывает удобен и иногда даже необходим, к примеру, для использования `cin` или `scanf`, поэтому мы решили побороться с этим типом ошибок.

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

template <typename T>class UBSafeType final {public:  UBSafeType() : Value_{}, IsInit_{false} {}  UBSafeType(T t) : Value_{t}, IsInit_{true} {}  T assertGetValue_() const;  T& assertGetRef();  T& setValue_(T Val);  private:  T Value_;  bool IsInit_;};

А затем возникают вопросы. Как мы понимаем, когда происходит именно чтение значения переменной, а когда она просто упоминается каким-либо другим образом? Суть в том, что согласно стандарту, UB возникает именно в момент lvalue to rvalue cast, а его Clang AST выделяет в отдельную вершину `ImplicitCastExpr` нужного типа. Хорошо, тогда более сложный вопрос: пусть есть `scanf`, читающий несколько переменных, но пользователь дал некорректный ввод и прочиталась только одна переменная. Тогда как понять, что происходит внутри наших оберток?

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

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


Пример: обработанная версия программы, читающая IP-адрес по шаблону при помощи scanf, не может обнаружить UB, возникающее при выводе результата на экран

Перейдем к тому, как мы использовали AST. По вершинам `VarDecl` мы находим объявления переменных и заменяем их на конструкторы оберток, по операторам присваивания находим собственно присваивания, которые и являются инициализациями. Интереснее с доступом к значению: информацию о переменной содержат вершины `DeclRefExpr`, но мы-то ищем `ImplicitCastExpr`, находящийся выше в дереве. При этом принципиально важно обработать случаи доступа по значению (с кастом) и по ссылке (без него) по-разному. На помощь приходит технология Parent-ов, позволяющая подниматься по дереву независимо от обхода Visitor-ов. (Передаю привет неполной документации ParentMapContext, из-за которой пришлось долго гулять по исходникам clang-а). Увы, это палка о двух концах из-за потенциального обхода целого дерева асимптотика нашего анализатора возрастает до квадратной, и время работы самого анализатора ухудшается значительно. А что же делать, если обращение к переменной по ссылке? Возможно, эта ссылка куда-то передается, возможно, сохраняется в новую переменную И что делать с полями классов? А вложенных классов?

int main() {  int a = 5;  int& b{a};  int c = b++ + (int&)a;  (b = c) = (b);}

Пример: страшный сон исследователей неинициализированных переменных и его AST

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

Результаты

Полномасштабное тестирование мы, к сожалению, не успели провести. Тем не менее, мы проверяли, как наша программа работает, на 1) отдельных изощренных ситуациях, 2) примерах простеньких программ на C++ из интернета, 3) своих решениях контестов и домашек. Вот пример преобразования, получающегося в результате работы нашего анализатора:

Пример до:

#include "../../include/UBTester.h"#include <iostream>int main() {  int a, b;  std::cin >> a;    char c = 89;  c = 2 * c; // unsafe conversion    int arr[10];  arr[a] = a; // possible index out of bounds    a = b; // uninit variable}

Пример после:

#include "../../include/UBTester.h"#include <iostream>int main() {  UBSafeType<int> a, b;  std::cin >> ASSERT_GET_REF_IGNORE(a);    UBSafeType<char> c(IMPLICIT_CAST(89, int, char));  ASSERT_SET_VALUE(c, IMPLICIT_CAST(ASSERT_BINOP(Mul, 2, IMPLICIT_CAST(c, char, int), int, int), int, char)); // unsafe conversion    UBSafeCArray<int, 10> arr(ASSERT_INVALID_SIZE(std::vector<int>({10})));  ASSERT_IOB(arr, ASSERT_GET_VALUE(a)) = ASSERT_GET_VALUE(a); // possible index out of bounds    ASSERT_SET_VALUE(a, ASSERT_GET_VALUE(b)); // uninit variable}

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


Пример: вот так работает код, приведенный выше, на входных данных 5 и 15

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


В заключение скажем: перед нами не стояло цели создать готовый продукт нам было важно столкнуться с LLVM, clang и С++ и разбиться насмерть. Возможно, результат вышел не самым практичным, но чтение документаций и стандарта оказалось занимательным и особенно полезным времяпрепровождением. Будьте осторожны при использовании С++ и да хранит вас Бьёрн Страуструп.

Ссылка на гитхаб

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


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

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

Итак, 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.

Всем привет! Мы команда из Питерской Вышки, и в этом году мы заняли первое место в RL треке соревнования NeurIPS 2020: Flatland. Цель Flatland разработать алгоритм, способный как можно лучше управлять трафиком движения поездов по сети железных дорог, при этом система должна принимать решения за ограниченное время.

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

Наша команда

В команде JBR_HSE было пять участников: Константин Махнев (учится на 4-м курсе бакалаврской программы Прикладная математика и информатика) Олег Свидченко и Владимир Егоров (оба учатся в магистратуре Программирование и анализ данных), аспирант Дмитрий Иванов и заведующий Центром анализа данных и машинного обучения НИУ ВШЭ Санкт-Петербург Алексей Шпильман. Все, кроме Константина, также работают в лаборатории Агентных систем и обучения с подкреплением JetBrains Research отсюда и название команды. Во время участия в соревновании Костя стажировался в этой же лаборатории.

NeurIPS 2020: Flatland что это?

Flatland это соревнование, которое проходило с 10 июля по 15 ноября на основе платформы AIcrowd и при поддержке известной международной конференции NeurIPS. Цель соревнования разработать алгоритм, способный как можно лучше управлять железнодорожным трафиком. Важным ограничением было то, что решения нужно принимать за ограниченное время (5 секунд на один шаг симулятора), что не позволяло просто подбирать оптимальные действия.



В NeurIPS 2020: Flatland было два направления: общее и Reinforcement Learning (RL). Первое направление было открыто для любых решений, а второе только для тех, которые используют обучение с подкреплением.

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

Решение: как агент будет взаимодействовать с симулятором

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

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

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

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

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



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

Осталось определить только функцию награды для агента. После некоторого подбора, мы остановились на довольно простой: $0.01 \cdot \Delta d 5 \cdot \text{is\_deadlocked} + 10 \cdot \text{is\_succeed}$, т.е. награда отражает то, насколько изменилось расстояние $d$ до пункта назначения после принятия решения, с дополнительными наградой в случае успешного завершения эпизода и наказанием в случае попадания в дедлок.

Алгоритм PPO

Существует множество алгоритмов обучения с подкреплением, которые разработаны для решения мультиагентных задач. Однако в качестве baseline алгоритма мы решили использовать алгоритм PPO Proximal Policy Optimization, поскольку его код можно было бы переиспользовать для реализации алгоритмов multiagent RL (например, COMA). Позже, правда, оказалось, что PPO (с некоторыми модификациями) сам по себе решает задачу неплохо, а вот мультиагентные методы обучаются значительно хуже, поэтому PPO остался основной частью нашего финального решения.

Классический алгоритм PPO состоит из двух частей: актора и критика. Критик приближает value-function, а актор учит рандомизированную политику $\pi_\theta(a | s)$, которая максимизирует математическое ожидание суммарной награды.



Одна из важных модификаций, которые мы сделали добавление в архитектуру актора модуля, который позволяет агенту коммуницировать с ближайшими агентами. Процесс коммуникации построен довольно просто: агенты одновременно генерируют сообщения и рассылают их всем поездам, рядом с которыми находятся, а затем, получив сообщения от соседей, объединяют их в одно сообщение путем взвешенного усреднения. Для определения весов, с которыми будут усредняться сообщения, использовался простой механизм self-attention. При таком построении процесса коммуникации нет необходимости как-то модифицировать процесс обучения, т.к. достаточно просто разрешить градиентам проходить через сообщения во время применения обратного распространения ошибки.

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

Как решить, каким поездам когда стартовать?

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

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

Результаты соревнования

В результате наше решение заняло первое место в треке RL и восьмое место в общем зачете. Это значит, что на данный момент не-RL подход пока решает лучше, однако показывает, что у обучения с подкреплением есть потенциал. В нашем подходе довольно много слабых мест и нерешенных вопросов (например, серьезные проблемы с масштабируемостью на окружения большого размера), поэтому нам есть, над чем еще поработать. Сейчас мы вместе с организаторами соревнования готовим статью для отправки ее в competition book NeurIPS 2020.