Авторы: Мэтт Голла, Джон Ле, Джерри Лью, Джошуа Ротфус, Минакши Сваминатан, Лорри Триа

Введение

League of Legends — одна из самых популярных компьютерных игр в мире, в которую ежемесячно играют более 110 миллионов активных игроков. Игра является частью жанра MOBA (Многопользовательская онлайн-боевая арена), в которой 10 игроков делятся на 2 команды по 5 человек, каждая из которых управляет одним персонажем. Цель каждой команды — пробить оборону врага, получить убийства и цели и, в конечном итоге, уничтожить базу противоположной команды. Соревновательный характер игры породил огромное сообщество и устоявшуюся сцену киберспорта, а чемпионат мира принес призы на сумму более 6 миллионов долларов. Многие игроки, стремящиеся подняться по рейтинговой лестнице и однажды стать профессионалами, вложили массу усилий в исследование различных стратегий, матчей и метаданных, чтобы улучшить свой игровой процесс.

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

Базовая игровая механика

Цель

В игровом процессе участвуют две команды: красная команда и синяя команда (как видно на изображении чемпионата мира 2019 года выше и ниже на карте Ущелья призывателей, игровое поле). В каждой команде по пять игроков, и они начинают в противоположных углах карты рядом со своим нексусом. Цель игры — уничтожить нексус вражеской команды.

Роли и чемпионы

Мы видим, что карта состоит из трех дорожек: верхней, средней (дл) и нижней (том) и джунглей. Каждый игрок выбирает чемпиона, берет на себя роль и занимает одну из трех дорожек или джунглей, кроме нижней дорожки, куда идут два игрока. Разные чемпионы лучше подходят для разных ролей. Игроки, выходящие на линии, убивают вражеских миньонов (объяснено далее), чемпионов и башен, чтобы проложить себе путь к вражескому узлу, зарабатывая при этом золото и очки опыта (XP), которые можно использовать для покупки предметов и получения уровней, чтобы помочь команда. Игрок, который идет в джунгли, отвечает за убийство миньонов джунглей, чтобы получить золото и опыт или помочь игроку на одной из дорожек.

Миньоны или Крипы

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

Оценки повреждений и различий

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

Мы вернемся к некоторым из этих терминов после описания данных. Это также поможет сделать данные более понятными.

Наш технологический процесс

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

Набор данных и предварительная обработка

Поскольку игры League of Legends часто непредсказуемы из-за ошибок и ошибок игроков, необходимо собрать большой набор данных с большим количеством различных матчей, чтобы построить надежную модель, устойчивую к этому шуму. К счастью, Riot Games предоставила разработчикам API для работы, что избавляет от необходимости вручную очищать веб-сайты для получения данных о матчах. Как упоминалось ранее, ошибка игрока является очень распространенным фактором непредсказуемости исхода матча, поэтому, чтобы свести к минимуму ее влияние, мы решили получить данные о матче только от лучших претендентов (самых высоких рейтингов) игроков из каждого региона. Игроки с высоким рейтингом и профессиональные игроки в среднем совершают меньше ошибок, а исход игры в первую очередь определяется матч-ап, сборкой предметов и макросами. Делая это, мы делаем шум более управляемым для моделирования.

Нам пришлось пройти через пару обручей, чтобы получить данные об отдельных матчах из Riot API. Сначала нам нужно было получить список имен лучших игроков-претендентов из каждого региона. У нас есть доступ к 11 региональным серверам (не считая Китая и Юго-Восточной Азии) и от 50 до 300 претендентов из каждого региона. Чтобы упростить задачу, а набор данных не был слишком большим, мы выбираем 50 лучших игроков из каждого региона, что в сумме дает 550 игроков. Серверы Riot хранят до 1000 последних матчей, поэтому теоретически у нас будет набор данных из 550 000 матчей, хотя уникальное количество игр значительно меньше, поскольку многие игроки играют в одни и те же матчи. Поскольку API Riot принимает только уникальные параметры идентификатора для вызовов API вместо простого getMatchBySummonerName, нам пришлось извлекать идентификатор учетной записи для каждого игрока из имени пользователя и, наконец, идентификаторы матчей для всех матчей, сыгранных конкретным пользователем. Наконец, мы извлекли подробные данные соответствия, используя каждый идентификатор совпадения, и сохранили их во временном файле JSON. В итоге получилось около 2 ГБ, всего ~ 50 тыс. совпадений.

Мы взяли эти данные JSON и сделали их более привлекательными, преобразовав их в данные в формате CSV. Следующая схема объясняет отдельные функции и стиль данных.

Match Data Schema
Row Data:
ID                matchID + the Period modifier.
P#-Team           100 for blue side. 200 for red side.
P#-Champ          ID of the champion chosen by this Participant.
P#-Lane           Participant’s calculated lane — MID, JUNGLE, etc.
P#-Role           Participant’s calculated role — DUO_CARRY etc.
P#-CS             Creeps for a specified period.
P#-XP             Experience change for a specified period.
P#-Gold           Gold for a specified period.
P#-Damage         Damage taken for a specified period.
P#-CSDiff         Creep score diff vs. calculated lane opponent(s).
P#-XPDiff         Experience diff vs. calculated lane opponent(s).
P#-DamageDiff     Damage taken diff vs. calculated lane opponent(s).
Period            The time period for this data.
Winner            B = 1, R = 0
(repeat all participant data 10x for all the 10 players)
# — number between 1–10 inclusive representing participantId

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

Немного истории о контролируемом обучении

Обучение с учителем — это метод машинного обучения, при котором нам предоставляются входные и выходные данные системы или явления, и мы строим алгоритм для изучения этого отображения от входа к выходу. Это отличается от неконтролируемого обучения, когда предоставляется только ввод, и у нас есть модель, изучающая базовое поведение или шаблоны в данных. Цель обучения с учителем состоит в том, чтобы при наличии «черного ящика» мы обучали модель изучению поведения черного ящика, чтобы с учетом совершенно новых входных данных мы могли предсказать, каким будет результат. Несколькими примерами алгоритмов обучения с учителем являются классификация, регрессия, методы повышения и методы опорных векторов. С другой стороны, неконтролируемые методы обучения состоят из методов кластеризации, k-средних, ассоциации и обучения с подкреплением. В этом проекте мы в первую очередь будем использовать контролируемые методы обучения для прогнозирования результатов матчей, потому что у нас есть доступ к историческим входным и выходным данным для киберспорта League of Legends.

Модель и поезд

Взаимосвязь функций

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

Обзор моделей

Собрав различные наборы данных, мы обучили различные типы моделей, чтобы предсказать, какая команда выиграет матч. Особенности включали характер и роль каждого игрока, а также индивидуальную статистику за последние 10 минут игрового процесса. Наша цель состояла в том, чтобы обучить модель бинарной классификации, чтобы определить, какая команда в конечном итоге одержит победу в каждом 10-минутном интервале для каждой игры. Другими словами, несколько образцов соответствовали одной и той же игре со статистикой, отражающей предыдущие 10 минут игрового процесса, поэтому мы могли построить графики, показывающие, как вероятность победы менялась на протяжении матчей. Мы использовали четыре основных подхода: XGBoost, Sklearn’s VotingClassifier, CatBoost и нейронную сеть Tensorflow/Keras. Для обучения и тестирования наборы данных были разделены на 80% для обучения и 20% для тестирования. Мы использовали комбинацию перекрестной проверки рандомизированного поиска и поиска по сетке, чтобы найти наилучшие значения гиперпараметров, какие только могли. Более подробную информацию об особенностях каждого метода можно найти на нашем github, где можно найти весь код для этих четырех методов. После настройки параметров лучшие оценки ROC_AUC для каждого метода были следующими:

CatBoost: 0,849

XGBoost: 0,844

Нейронная сеть Tensorflow/Keras: 0,841

Классификатор голосования: 0,840

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

Сводка различных параметров модели

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

CatBoost
     Iterations: 5000
     Learning Rate: 0.011216
     Max Depth: Unlimited
     L2 Leaf Regularizer: 0
     State space search: RandomizedSearchCV
     AUC Score: 0.849
XGBoost
     Max Depth: 12
     Learning Rate: 0.005
     Gamma: 2
     Reg Lambda: 0.1
     Reg Alphs: 0.1
     N estimators: 1000
     AUC Score: 0.844
Voting Regressor
     Models: Random Forest Regressor
             Gradient Boosting Regressor
             Gradient Boosting Classifier
             AdaBoost Regressor
             XGBoost Regressor
     
     AUC Score: 0.840
Neural Network
     Activation Functions: ReLu
     Epochs: 20
     Train/Test Split: 80/20
     Loss Function: MSE
   
     AUC Score: 0.841

CatBoost: наша лучшая модель

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

Одна из идей, которую нам нужно было учитывать для зависимости различных выборок, принадлежащих одному и тому же матчу, заключалась в создании функции, использующей прогнозы базовой модели CatBoost для победителей на базовом наборе данных. С функцией начального прогнозирования новая модель работала значительно хуже (оценка AUC 0,712, что примерно на 0,14 ниже, чем раньше). Мы думаем, что причины такого результата заключаются в том, что новая модель вызывала более экстремальные реакции и в конечном итоге была более суровой, когда одна команда возвращалась (явление, поощряемое игровой механикой). Другая возможная причина заключается в том, что новая модель еще больше переоснащалась и в значительной степени полагалась на свой более ранний прогноз для создания нового. Мы думаем, что с большим количеством времени можно более точно учитывать предыдущий игровой процесс за пределами последних 10 минут, но мы не смогли этого найти.

Нейронная сеть: наша модель метода без повышения

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

Графики показывают нам прогресс предсказания исхода игры с течением времени с использованием модели нейронной сети.

Вывод

Мы смогли успешно обучить 4 разные модели, чтобы предсказать победителя матча по мере его развития во времени. Методы варьировались от обычного повышения градиента до более эзотерического подхода нейронной сети. Мы смогли обнаружить некоторые интересные различия в тенденциях прогнозирования между каждым методом и увидели, что по мере того, как мы играли с функциями, прогнозы и тенденции имели тенденцию колебаться и меняться. В целом проект был отличным упражнением в использовании методов машинного обучения для чего-то интересного, например результатов матчей League of Legends. Будущая реализация использует «живые» отчеты о шансах на победу, которые также могут быть использованы для улучшения зрительского опыта или даже для азартных игр в середине матча.

Ссылка на Github: https://github.com/je66yliu/EE460J-final-project-league-predictor