Уроки участі в хакатоне «Dota Science» в рамках «Data Fest 2»

6 днів тому близько опівночі ми, команда «EC.Dota2» з чотирьох чоловік, почали працювати над частиною онлайн хакатона «Dota Science». Ніхто з нас нічого не знав про гру Dota2.

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

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



Тут варто сказати кілька слів про цілях хакатона. Мета опозиції — отримати найвищу щодо інших оцінку якості прогнозів. Мета, відповідна змістом Data Fest — побудувати найкращу, щодо інших, модель для прогнозування результату матчу методами машинного навчання.

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

Фінальна оцінка першого етапу – середнє всіх значень метрики якості для передбачених ймовірностей. Як показує турнірна таблиця першого етапу Хакатона, кількість передбачень на «команду» відрізнялось у 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) Для рідкісних подій (викидів у вигляді дуже рідкісних стратегій) не вистачає спостережень, щоб адекватно врахувати внесок такої стратегії.

Брали ви участь у цьому хакатоне «Dota Science»?

/>
/>


<input type=«radio» id=«vv71753»
class=«radio js-field-data»
name=«variant[]»
value=«71753» />
Так
<input type=«radio» id=«vv71755»
class=«radio js-field-data»
name=«variant[]»
value=«71755» />
Немає

Проголосувало 19 осіб. Утрималося 9 осіб.


Тільки зареєстровані користувачі можуть брати участь в опитуванні. Увійдіть, будь ласка.


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.