Эти три продукта — и ещё один, с цветными прямоугольниками на фото выше — победили на хакатоне. Команды получили уважение и книжки. Автор этих строк получил Thing Explainer от создателя комиксов xkcd.com. Буду учиться объяснять сложные вещи простыми словами :)

Каждое лето в Контур приходят на стажировку студенты из Екатеринбурга и других городов. В этом году у нас стажировались 90 аналитиков, тестеров, специалистов по data science, бэкенд- и фронтенд-разработчиков.

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

В ночь с пятницы на субботу в Контуре прошёл хакатон для участников RuSSIR (https://vk.com/russir).

Российская летняя школа по информационному поиску (RuSSIR) — ежегодное академическое мероприятие для российских и иностранных студентов. 130 участников собираются на неделю в одном из городов России и слушают лекции по информационному поиску от исследователей из мировых вузов (http://romip.ru/russir2017/program/).

В этом году школа вернулась в Екатеринбург и прошла 21-25 августа в Уральском федеральном университете. Последним мероприятием был хакатон, организованный специалистами по data science из Контура. Команды от 1 до 3 человек решали задачу по анализу поведения пользователей. Набор данных размером 10 ГБ был взят из одного из наших продуктов.

Если вы интересуетесь обработкой текстовой информации и её приложениями (информационный поиск, машинный перевод, автоматическое реферирование), рекомендую курс «Введение в обработку естественного языка» (https://stepik.org/course/1233/). Автор курса — один из организаторов RuSSIR и наш коллега Павел Браславский.

Тем временем организаторы ICFPC 2017 обнаружили, что неправильно учитывали порядок ходов в играх первого раунда в 24-часовом зачёте (https://icfpcontest2017.github.io/post/lightning-two/). Поэтому они устроили переигровку, которая ничего принципиально не изменила. Наша команда поднялась с четвёртого места на первое место с 39 очками из 40, что приятно:

После этого был сыгран второй раунд в 24-часовом зачёте. В нём участвовало 33 команды. Уже 8 ботов сражались на картах среднего размера. Наш бот заработал 58 очков из 64 и занял второе место, уступив команде Unagi:

Победителя последнего, третьего раунда в 24-часовом зачёте объявят на ICFP вечером 5 сентября (http://icfp17.sigplan.org/event/icfp-2017-keynote-talks-programming-contest-report). Организаторы говорят, что во втором раунде боты иногда не справлялись с расчётами и пропускали ходы по таймауту. Непонятно, чей бот окажется сильнее на больших картах с 16 участниками. Поэтому мы продолжаем смотреть записи игр (https://icfpcontest2017.github.io/punttv/tv.html?game=games/lightning2/plain/boston-a6.json) и болеть за нашего бота :)

Это приятно. Алексей Сафронов из команды AIM Tech говорит, что у нас прикольный репозиторий с решением на Гитхабе. Ура, не зря столько текста награфоманили: https://twitter.com/asafrnv/status/901460430513745921, https://twitter.com/asafrnv/status/901461097844273152

Ребята из AIM Tech играли впятером и писали на C++14 и Python 3. Судя по коду (https://github.com/yarrr-ru/icfp2017), у нас были похожие идеи для решений. Результаты тоже похожи: наши боты идут близко по зачётным очкам (points), причём бот AIM Tech стабильно набирает больше обычных очков (score).

Немного триллера, как и положено в заметках об ICFPC. Организаторы опубликовали результаты первого (https://goo.gl/MmnzxY) и второго раунда полного, 72-часового соревнования. В первом раунде участвовало 120 команд, которые играли четвёрками на небольших картах. Мы посмотрели на результаты и расстроились: наш бот набрал всего 70 очков. При этом лучшая команда набрала 122 очка, а медиана — 81,5 очков. Это значит, что наша команда вылетела из соревнования.

Это был «удивительно плохой результат» на фоне 1 и 2 места после 24-часового соревнования. Поэтому мы пошли смотреть записи игр и разбираться, где накосячили.

Сначала выяснили, что наш бот плохо играет в ситуации, когда ему активно противостоят на картах с низкой связностью. Например, в одной игре (https://goo.gl/XF8uBh) красная команда блокировала каждый наш ход — в итоге сама заняла последнее место, а нас утащила на третье, не позволив заработать зачётных очков. Мы обсуждали, что такое поведение противников возможно, и осознанно не учили бота противостоять ей. Такая стратегия может работать только на небольших картах, где низкая связность и мало противников. На средних и больших картах, где много «обходных путей» в графе и больше 4 команд, повредить нашему боту этой стратегией почти невозможно. Много очков мы на этом не потеряли, поэтому продолжили поиски.

Выяснили, что наш бот теряет много очков на конкретной карте — «треугольнике». Это экстремальный пример маленькой карты: всего три «шахты» и очень низкая связность. Если не оставить за собой подходы к шахтам в самом начале, следующими ходами их займут другие команды. Есть игры, где это хорошо видно (https://goo.gl/Nw7pHW). Мы обсуждали отдельную стратегию для таких карт: сделать полный перебор позиций и использовать критерий минимакса. Осознанно не стали этого делать, чтобы не усложнять бота. Были готовы потерять немного очков, чтобы «дождаться» средних и больших карт, где минимакс уже бесполезен.

Эти находки объясняли, почему мы потеряли около 10 очков. Куда делись ещё 50? И тут мы увидели СТРАШНОЕ. В куче игр (например, https://goo.gl/NxW8fD) наш бот делал несколько ходов и начинал неистово пасовать. Поэтому занимал последнее место и получал ноль очков. Страшно было то, что наш бот не умел и не мог пасовать. Мы не программировали такого поведения.

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

Догадались, что наш бот пасует тогда, когда хочет сделать options-ход. Пошли читать исходники и нашли дурацкий баг в Data Transfer Object для сделанного хода. Вот как он фиксится:

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

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

Самое обидное, что мы вылетели из соревнования не из-за слабой стратегии, а из-за ошибки во вспомогательном коде. А узнать, насколько наша стратегия хороша в 72-часовом зачёте, мы всё равно хотим. Не зря ж в 24-часовом так высоко поднялись. Поэтому мы написали организаторам: попросили взять нашего бота с фиксом и позволить ему участвовать вне зачёта. Оказалось, что мы не одни накосячили по мелочи — организаторы пообещали (https://goo.gl/9gX1CA), что устроят дополнительный неофициальный раунд. В нём боты с фиксами сразятся с победителями 72-часового зачёта и между собой. Результаты будут после конференции ICFP, то есть после 9 сентября. Спасибо организаторам за это.

А мы грустим, но продолжаем следить за результатами. К сожалению, WILD BASHKORT MAGES тоже вылетели в первом раунде 72-часового зачёта. Будем болеть за AIM Tech, они держатся молодцом :)