6 дней назад около полуночи мы, команда «EC.Dota2» из четырех человек ( ivankomarov, kolyanzzz, Sergei_Smetanin, AzZzone), начали работать над онлайн частью хакатона «Dota Science». Никто из нас ничего не знал об игре Dota2.

Сначала, хронологически, о первой, «онлайн» части. Есть сетка игр мирового финала «The Shanghai Major 2016». Нужно до матча предсказать его исход. Как показало время (но не описание конкурса), предсказывать нужно было матчи за 3, 4, 5 марта. Для обучения были даны исторические данные о матчах в Dota2 по разным прошлым турнирам с агрегированной информацией о каждом матче. Со среды пришлось начать недосыпать, т.к. все днем работают. Для онлайн этапа были разработаны две модели.

В качестве показателя качества прогноза использовалась следующая метрика: score=log2(p_winner)+1, где p_winner — предсказанная до начала матча вероятность победы команды, которая в результате победила.



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

Один выступающий в последний день Data Fest 2 (Nuker?) верно заметил, что «задачу машинного обучения всегда можно решить и без машинного обучения» (своими собственными нейронными сетями в голове). Кто использовал модели, кто использовал экспертный опыт, кто просто случайно играл? Неизвестно.

Финальная оценка первого этапа – среднее всех значений метрики качества для предсказанных вероятностей. Как показывает турнирная таблица первого этапа Хакатона, количество предсказаний на «команду» разнилось в 10-20 раз. Как мы знаем, отсутствующие данные можно, конечно, заменить чем-то, но здесь ключевой вопрос – это человек осознанно заключил, что вероятность 0,5 или просто проспал момент отправки прогноза? Вероятно, проспал, раз не отправил. Поэтому лучше бы было просто не рассматривать в таблице команды с количеством предсказаний меньше, чем, скажем, 10, т.к. слишком мало информации, чтобы оценить модель команды. А лучшая стратегия игры при финальной оценке – сделать удачный прогноз и больше не играть (отправлять 0,5), что, конечно, не соответствует смыслу Data Fest.

Модель онлайн части №1 «Nikolay» (машинное обучение). Алгоритм SVM предсказывает победу первой команды по долям побед первой команды во всех матчах за последние 1, 2, ..., 12 месяцев + то же самое для второй команды. При создании модели был выбран алгоритм и отсеяны незначимые признаки.

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

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

Модель онлайн части №2 «Сергей Сметанин» (предположения + анализ данных). Решили рассматривать матчи только с 01.07.2015. Проанализировав таблицу побед/проигрышей/разницу побед и проигрышей, мы увидели, что сортировка по победам точнее всего группирует команды турнира «The Shanghai Major 2016»:



Соответственно, в качестве ad hoc вероятности победы первой команды использовали сумму с одинаковыми весами по 0.5 двух величин:
1) Отношение количества побед первой команды к суммарному количеству побед первой и второй команд во всех матчах с 01.07.2015;
2) Отношение количества побед первой команды к суммарному количеству побед первой и второй команд в матчах только между первой и второй командами с 01.07.2015.

Почему? Отталкивались от таких предположений:
— команды и опыт сильно менялись во времени, поэтому будем брать только свежую информацию. Что такое свежая? Не знаем. Например, 01.07.2015.
— таблица команд показывает, что победы точнее всего группируют команды «The Shanghai Major». Будем работать с выигрышами.
— вероятно важно, что игра была между двумя интересующими командами. Делаем признак только по таким матчам. (Однако, уже после матчей, пересчет показал, что лучше этот признак не брать. Отчасти, поэтому брали в расчет все команды во второй части хакатона.)
— смотрим на историческую силу команд.
— сила, измеренная выигрышами, уже имеет в себе всю информацию о выборе стратегии, игроков и т.д. Поэтому остановимся пока на ней.

Результаты моделей:
Сначала лидировала модель №2, но человеческий фактор сыграл свою роль – ошиблись при отправке, куда-то потерялось одно предсказание с вероятностью 1. С первого места 3-го марта быстро отдали пальму первенства устойчивой «Nikolay», которая выиграла бы 4-е место из 42 в конце онлайн части, если учитывать не менее 10 матчей.

Офлайн часть официально началась 5 марта в 20:00. Для построения моделей были предоставлены данные (в 0:30) о ходе матчей турнира (состояние игры в различные моменты времени в течение матча). В 1:30 получили последнюю недостающую информацию о том, кто в этих матчах выиграл. К началу первого матча финала (матча до гранд-финала) в 5:30 модель была готова.

Входные данные для модели:
— по игрокам: xp_per_min, gold, net_worth, respawn_timer
— по команде: tower_state, barracks_state
— по матчу: duration

Целевая переменная: вероятность победы Radiant

Отобранная модель: логистическая регрессия

Отобранные предикторы: опыт команд (xp), совокупная стоимость команд (net worth), отношение опыта и совокупной стоимости команд (Radiant к Dire), respawn_timer (по героям), level (по героям), respawn_timer * level (по героям).

Обучающая выборка: данные о ходе всех матчей Shanghai Major 2016.

Примечание: respawn_timer – время до возрождение убитого героя.

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

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

Финал удивил многих, когда победила Liquid в матче с EG при отрицательной разнице в опыте в течение всего матча (см. график). EG был фаворитом нашего первого консультанта по Dota2.



Есть редкие стратегии, которые работают таким образом, объяснил нам второй из двух (примкнувших) консультантов, который играл в Dota1 профессионально на уровне чемпионата России. Это не вписывалось в нашу логику отбора признаков, поскольку мы были уверены, что превосходство в опыте – один из самых решающих факторов для победы. Первый же консультант (молодой энтузиаст Dota2) был в шоке от увиденного.

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



На графике показана важность признаков. Здесь много интересного, например, мы удивлены тем, что уровень первого героя R оказался существенно менее важным, чем уровень второго героя R.

К гранд-финалу мы подошли, не слишком веря в силу нашей модели. Двое, кто сделали модель и скрипт для рисования графика разницы в опыте команд в реальном времени, поехали спать, двое остались отправлять результаты модели для оценки и, вообще, «действовать по обстановке».

Также думали о стратегии отправки вероятностей с учетом оценки модели в конце матча. Вероятно, преимущество можно получить, начав как можно раньше предсказывать самые высокие вероятности. Подумали, не сделать ли такую стратегию: отправляем 0,5 пока «не увидим» победу команды и потом отправляем 1. Забегая вперед, можно сказать, что многие применяли такую стратегию или ее варианты. Было бы интересно исследовать более детально вопрос об оптимальной стратегии, но времени не было.

И… начался финал! Мы смотрели игру первый раз в жизни. Модель вдруг… упала. График все равно шел, и мы играли по нему, решив планомерно увеличивать отклонение отправляемой вероятности от 0,5 на трех периодах игры: start (10 мин) ±0,05, middle (20) ±0,25, final (20+) ±0,49.

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

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

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

Третья игра. Что будет? Закончили 15 местом, думаю из-за вмешательств ставок до начала игры на Liquid.

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

Вывод: Хоть модель и представляется резкой, но она – сильная (она… поздравляем ее с 8 марта!). Особенно для матчей, которые идут с перевесом одной команды. Модель не теряла времени зря, не смотрела на недавнее прошлое так… как мы. Не искала стратегий, как консультант. Просто говорила, что от того места, где мы сейчас в матче, исторически все идет вот к такому результату.

В сумме, 10 место (по нашим суммарным подсчетам) из 23 команд, кто играл во все 4 игры гранд-финала.



Если же отсеять «экстремалов» и «уверенных», то место будет и повыше. Кстати, чтобы играли только алгоритмы, было бы полезно, чтобы люди ставили реальные деньги на результат. Тогда бы было интересно посмотреть на 5 последних команд по сумме 4 игр, которые бы скидывались от 9000 до 300000 рублей (при 1 руб. за единицу метрики). Думаю, тогда бы и команда-призер думала бы осторожнее.

Уроки:
1) Хакатон — вещь классная своим сжатым временем проведения и неизвестной темой, которую надо раскрыть. Будем играть в Dota2 хакатоны дальше!
2) Мы выступили неплохо, с учетом сжатых сроков и полного незнания Dota2.
3) Доверяй машине (но проверяй).
4) Эксперты нужны, чтобы передать знания, которые долго вытаскивать из данных и которые потом проверит машина. В этом хакатоне, «модели» экспертов имели одновременно bias + variance, т.е. у них была грубая модель «ставь все на эту команду», и большой разброс («нет, нет, теперь ставь на эту»). Возможно, симбиоз машина + эксперт лучше всего.
5) Не иди в боевую с одним инструментом. Вдруг откажет? Мы благодарны, что у нас был график, который спас первый матч гранд-финала.
6) Для редких событий (выбросов в виде очень редких стратегий) не хватает наблюдений, чтобы адекватно учесть вклад такой стратегии.