В 1994 году женатую пару пригласили на встречу с советом директоров второй крупнейшей в Великобритании сети супермаркетов. После неловкого молчания тогдашний глава Tesco лорд МакЛорин сказал Эдвине Данн и Кливу Хамби слова, которые в даталогии (науке о данных) считаются эквивалентом крылатой фразы Армстронга о «маленьком шаге для человека»:
«За три месяца вы узнали о моих клиентах больше, чем я за тридцать лет».
После этого Tesco запустила первую в мире программу лояльности в супермаркетах. Tesco Clubcard показала целому миру, каких результатов можно достичь, просто анализируя, что именно и когда покупают потребители.
Поиск ассоциативных правил – один из алгоритмов, использующихся в подобных программах. Он анализирует, например, вероятность появления в покупательской корзине наборов нескольких предметов. К примеру, если вы купили яйца с беконом, то вы наверняка купите и сосиски.
На мир Доты это правило переносится примерно так: если вы пикнули Shadow Demon, то вы наверняка пикнете и Mirana.
На протяжении последних нескольких недель я извлекал и анализировал данные из Valve API, используя разнообразные методы и алгоритмы. В первом посте мы обсудим «непредсказуемые и нестандартные» пики Wings Gaming, чемпионов шестого The International 2016.
Первый раздел блога содержит короткое описание методологии анализа данных, сделанных мной выборов и упрощенные сведения об используемом алгоритме анализа. Если вас интересуют лишь результаты – перейдите ко второй части.
Методология
В этом проекте я использовал Apriori – алгоритм анализа данных для R (программа для статистического анализа информации, чем-то похожа на Matlab). Он работает следующим образом: вы вводите в него определенную информацию, он определяет в ней закономерности и выдает их в качестве правил. Для упорядочения и оценки этих правил используются три фактора: поддержка (support), достоверность (confidence) и подъем (lift).
Правила обычно представляются в следующем формате:
{Если что-то произошло} => {скорее всего, произойдет кое-что определенное}. Например: { Arteezy играет на Invoker} => {Команда Arteezy победила}.
RHS/LHS: Правая часть правила / левая часть правила. В нашем примере правая часть правила – это «Команда Arteezy победила». Соответственно, левая часть правила – «Arteezy играет на Invoker».
Поддержка указывает на то, как часто левая часть правила появляется в наборе данных. Пример – если команда Arteezy сыграла 14 матчей, и в 7 из них Артур играл на Invoker, то поддержка левой части правила {Arteezy играет на Invoker} равняется 7/14 = 0,5 (конечно, это при условии, что в наборе данных есть лишь одна строка информации для каждого матча).
Достоверность указывает на вероятность срабатывания правила. Продолжим пример, который я привел выше – если в 7 матчах, где Arteezy играл на Invoker, команда одержала победу лишь 4 раза, то достоверность правила {Arteezy играет на Invoker} => {Команда Arteezy победила} составит всего 4/7 = ~0,57.
Объяснить, что такое подъем, будет достаточно сложно. В двух словах – это соотношение одновременно действующих элементов левой и правой частей правила, разделенное на шанс одновременного возникновения левой и правой частей правила, если они сосуществуют независимо (т.е. правило еще не сформировано). Если значение подъема равняется 1 или больше – правило работает достаточно хорошо.
Итак, при анализе данных я искал правила с приемлемыми значениями поддержки и достоверности. Подъем этих правил должен быть равен как минимум 1.
Дополнительная информация
Apriori – достаточно медленный алгоритм, но есть несколько трюков, позволяющих его ускорить. Алгоритм работает, выявляя в наборе данных наиболее часто встречающиеся элементы и «забывая» о реже встречающихся элементах. Потом он формирует из них список. Следующий шаг – повторный анализ данных. На этом этапе алгоритм ищет пары наиболее часто встречающихся элементов (иными словами, формирует правила), затем наборы из трех элементов и так далее. С каждым найденным повторением с достаточной поддержкой и достоверностью список сокращается. Чтобы результаты не перегрузили оперативную память компьютера (или не поставили крест на чьих-то планах на выходные), программист может искусственно ограничить значения этих критериев.
Поскольку я работал эффективно и выбрал достаточно высокие значения поддержки и достоверности, полученные мной правила имели высокое значение подъема.
Начало проекта
Лучший способ начать проект в даталогии – задать себе вопросы, ответы на которые ты надеешься найти в своем наборе данных. Зная это, я сформировал следующие вопросы:
- Есть ли у Wings любимые герои либо частые/повторяющиеся пары героев?
- Каких героев банят, играя против Wings? Есть ли взаимосвязь между определенными пиками и банами как для вражеской команды, так и для самих Wings?
- Есть ли в стиле драфта Wings определенный порядок (например, саппорты пикаются перед керри)?
Чтобы найти ответы на эти вопросы, я создал два небольших набора данных для обработки в Apriori. Первый набор предназначался для работы с 1 и 2 вопросами. Я создал 25-строчный файл с информацией о каждом пикнутом и забаненном герое. Чтобы различить героев в наборе, некоторым из них был присвоен префикс: «e» означал вражеский контрпик, «b» означал бан самих Wings, «eb» означал бан со стороны вражеской команды.
ebKunkka,bElder Titan,ebMirana,bDrow Ranger,eIo,Batrider,Rubick,eLifestealer,bStorm Spirit,ebRazor,bEmber Spirit,ebWeaver,Slark,eNight Stalker,Magnus,eHuskar,bDazzle,ebAncient Apparition,eOgre Magi,Pudge,39,False
Таким образом каждый драфт превращался в «магазинную тележку с героями».
Следующий набор данных предназначался для работы над третьим вопросом. Каждый пик, сделанный Wings во время TI6, превращался в строку данных. В ней содержалась следующая информация: пикнутый герой, отыгравший на нем игрок и порядок пика. Это позволило мне подробнее изучить порядок драфта. К этому моменту я вернусь ближе к концу.
Oracle,111114687,6,39,1
В обоих наборах данных также содержался ID вражеской команды и исход сражения (победили ли Wings или нет). Я ожидал увидеть пики, заточенные под определенные команды (слишком свежим было впечатление от прочтения блога Себастьяна «7ckngMad» Дебса о собственных драфтах и драфтах против вражеских команд, и мне хотелось проверить его слова на деле).
Результаты драфтов Wings
По моему мнению, лучшим героем Wings оказался Oracle. Китайцы пикнули его 8 раз и не проиграли на нем ни единой игры. Интересный факт: Оракула чаще всего пикали, когда у Wings был второй пик в первой стадии драфта (когда у команды есть возможность даблпика) – на этот сценарий приходится четыре пика Оракула из восьми. Остальные пики Оракула не имели какого-то конкретного сценария.
В половине игр, где Wings выбирали Оракула, их противники банили пару Batrider и Huskar. Бан Хускара оправдан метой, но пара Batrider & Oracle лично меня немного озадачила – чем она так опасна, что против Оракула вражеские команды банили Бэтрайдера?
Wings нравится пара Sand King & Oracle. Китайцы никогда не пикали Сэнд Кинга без Оракула. Этой парой Wings сыграли четыре раза.
Wings дважды играли СК как саппортом (в исполнении iceice) и еще дважды – как оффлейнером (в этом случае на нем играл Faith_bian). Этот факт меня заинтриговал, и в поисках ответов я заглянул на Dotabuff. По версии ДБ, во всех играх iceice Сэнд Кинг был роумящим саппортом. Что же касается Оракула, то в одной игре он тоже роумил, а во второй – присматривал за Вайпером на миде против комбы Huskar/Io в исполнении SumaiL/ zai. Когда же на Сэнд Кинга садился Faith_bian, он либо становился роумящим оффлейнером (в той игре с ним также бегал Рубик iceice’а), либо не отходил с харды, вместе с Оракулом отстаивая линию против керри-Войда в исполнении Agressif. (Матчи: 2569470828, 2546938575, 2551226728, 2551167223)
И напоследок об Оракуле. В матчах против Wings его банили 7 раз. Четыре из этих игр Wings проиграли.
Еще одна пара героев, которую я хотел бы отметить – Alchemist & Lifestealer. Оба героя были пикнуты трижды, и они всегда выступали в связке. Что заинтересовало в этой комбе лично меня, так это порядок их пика. В двух играх Лайфстилера пикали в конце второй фазы, а Алхимика – в последней. В третьем матче порядок пика был обратным. Wings также никогда не прибегали к этой комбинации, если они не ластпикали последними. И вновь я не понимаю эту комбинацию героев. Я, конечно, уже играл стратегией «Лайфстилер с аганимом + Баратрум», но мне хотелось бы понять, почему Алхимика со Стилером пикают вместе, еще и в такой интересный способ.
Общая информация
- Wings 4 раза пикали Elder Titan’а. При этом в 75% случаев этот герой выбирался, когда Wings делали ферстпик. Игра, когда Титан брался ферстпиком для команды, но не для карты, в своем роде уникальна – это была единственная игра, когда iceice ферстпикнул героя, на котором в том матче играл сам.
- В играх против Wings Титана банили трижды. Это не помешало Wings выиграть во всех этих матчах.
- В играх против Wings 11 раз забанили Drow Ranger. Единственным матчем, когда Тракса не банилась ни одной из команд, был матч с Pudge и Techies.
- Некоторых героев отдавали лишь строго определенным игрокам: Oracle (пикнут 8 раз), Drow Ranger, Elder Titan, Slardar и Mirana (4 раза), Pudge, Invoker, Alchemist & Lifestealer (3 раза).
- 50% пиков Рубика пришлось на даблпик Wings во второй стадии драфта. Wings проиграли с Рубиком в пике лишь единожды – это был тот самый матч против EG, когда китайцы решили поиграть на Пудже;
- На Рубике всегда играл Innocence. Исключением стал лишь один матч, когда Рубик отошел iceice, а для Innocence выбрали Оракула. Таким образом, 15 из 25 матчей на TI6 Innocence отыграл лишь на двух героях.
Анализ порядка пиков
Помните, я говорил, что вернусь к своему третьему вопросу (Есть ли в стиле драфта Wings определенный порядок (например, саппорты пикаются перед керри) позже? Так вот, настало время ответить и на него.
Первый факт: в 75% матчей Wings против Evil Geniuses китайцы выбирали героя Faith_bian’у именно в первом пике второй стадии (когда на этом этапе драфта у них было право выбирать героя первыми).
Второй факт: в 50% проигранных китайцами игр последним выбирался герой для bLink.
Найти другие закономерности в стиле драфта Wings не удалось. Большинство найденных алгоритмом правил выглядят откровенно бессмысленно. Я попробовал найти лучшее и более простое решение этого вопроса, но об этом мы поговорим уже в конце статьи.
Pudge
Пики Пуджа в играх Wings выглядят крайне интересно. Китайцы выбирали этого героя в самых важных своих играх – в первом матче на турнире, в первом матче плей-оффа и в первой игре грандфинала. По этому поводу можно размышлять очень долго. Может, Wings пикали Пуджа специально, чтобы «расслабиться», а затем взять себя в руки и играть серьезно? Понятия не имею, зачем они выбирали этого героя. Если я когда-нибудь смогу взять интервью у iceice, это будет один из моих первых вопросов.
В этой статье мы уже обнаружили несколько закономерностей в стиле драфта Wings – например, их любовь к парам Sand King + Oracle и Lifestealer + Alchemist или мастерство Innocence на Оракуле. Что ж, вот вам еще одна закономерность – если вы хотите победить в матче против Wings, надейтесь, что они пикнут Пуджа. Еще одна закономерность – в играх с Пуджом Wings всегда банили Elder Titan’а. Увы, конкретно этот тренд бесполезен.
Дальнейшая работа
В начале этого года оказалось, что Netflix использует систему из тысяч жанров для более точного определения вкуса своих пользователей. Где-то в январе я, вдохновившись этим, придумал идею. Почему бы не дать всем герояем в Доте аналогичные категории? Так я смог бы анализировать команды, предпочитающие пушеров, антипушеров, керри, героев с дизейблами, саппортов, героев 4 позиции, контрящих БКБ героев и так далее. Дота очень разнообразна, у одного героя может быть целое множество различных категорий. Если присвоить герою неправильную категорию, можно испортить ему статистику. Да и я не настолько хорош в Доте, чтобы дать каждому герою категорию. Кого-то выбирают лишь ради одной роли, кого-то – сразу для нескольких. Иными словами, если свести драфт к подбору героев по ролям, то можно будет гораздо лучше разобраться в порядке и предпочтениях драфта каждой команды. Применив алгоритмы подбора правил, удастся рассмотреть стратегию каждой команды и стереть границы между компромиссными вариантами пиков (например, Riki / Bounty Hunter). Я хотел бы создать полноценный ИИ для анализа и репликации стиля драфтов каждой команды, но с учетом временных ограничений эта идея вряд ли воплотится в жизнь.
Вернемся к порядку драфтов. Позже я попробую проанализировать драфт по стадиям. Одна лишь первая стадия пиков способна дать больше информации, чем полный, но «разбавленный» процесс. Тем интереснее будет взглянуть на вторую и третью стадию пиков, условно зависимые от более ранних стадий. Еще один способ справиться с проблемой – подобрать средние значения. Создать простую гистограмму с позициями пиков и количеством пиков героя для конкретного игрока в этих позициях. На примере iceice и shadow:
Выборка основана на играх Wings, когда у них был второй пик (18/25 игр). Первая полоса совмещает в себе сразу два пика (поскольку герои выбирались одновременно), но все же наблюдается определенный тренд – для shadow’а герой выбирается предпоследним – вероятно, потому, что любой контрпик можно будет законтрить ластпиком? Ниже полная версия графика со всеми игроками.
В этом графике наибольшее внимание привлек Innocence. Его герой всегда выбирался в ходе первых трех пиков. Тем более интересно, если учесть, что у него был самый слабый пул героев в команде. Героев bLink’у выбирали в первую или последнюю очередь, а герой для Faith_bian лишь раз выбирался в первом пике второй фазы.