Оригинальная статья

Multiplayer Online Battle Arena (MOBA) — жанр компьютерных игр, сочетающий в себе элементы стратегий в реальном времени и компьютерных ролевых игр. Самыми известными играми в этом жанре являются League of Legends и Dota 2. Каждая игра состоит из стадии выбора (draft stage), в которой игроки по очереди выбирают одного из игровых персонажей (в LoL их называют чемпионами), и самой игры. От выбранных чемпионов очень сильно зависит исход всей партии, поэтому важно подобрать их так, чтобы они синергировали между собой и хорошо себя показывали против чемпионов противника. Но самое важное то, насколько игрок хорошо играет на своем чемпионе. DraftRec предназначен для того, чтобы помочь новичкам и не только выбрать оптимального героя для игры в текущем матче.

В ходе матча в League of Legends есть 2 команды по 5 игроков, каждый из который играет определенную роль (топ, лес, мид, адк и саппорт). Чемпионов в игре на момент написания статьи 156, то есть возможных комбинаций $C_{156}^5 \cdot C_{151}^5$ без учета ролей

В качестве датасета были взяты 280,000 матчей LoL и 50,000 матчей Dota 2. При этом для улучшения качества были выбраны матчи с участием 0.1% лучших игроков (ранг мастер и выше)

Драфт фазу можно считать вариантом рекомендательной системы, в которой хотим предсказать, какого чемпиона предпочитает игрок в данной ситуации, опираясь на историю его игр. При этом также стоит учитывать и то, кого выбрали союзники, чтобы в итоге получить хоть какую-то синергию в команде. То есть рекомендательная модель будет возвращать 2 числа

$\hat{p}_t^i, \hat{v}_t^i = f_{\theta}(s_t^i)$

где $\hat{p}$ обозначает вероятность выбора игроком того или иного чемпиона, а $\hat{v}$ - исход матча. содержит в себе информацию о предыдущих матчах всех игроков в команде, а именно их роли, выбранные чемпионы и послеигровая статистика (количество убийств, смертей, полученное золото, исход матча и т.д.), а также о текущем матче. Сама модель выглядит так

В качестве функции потерь выбрана функция $\mathcal{L}$ , зависящая от $\mathcal{L}_p$ (функция потерь предсказания чемпиона) и $\mathcal{L}_v$ (функция потерь предсказания исхода). $\mathcal{L}_p$ и $\mathcal{L}_v$ - логарифмические функции потерь (кросс-энтропия)

$\mathcal{L} = \frac{1}{T}\sum_{t = 1}^T \lambda \mathcal{L}_p(\hat{p}_t^i, \hat{c}_t^i) + ( 1 - \lambda)\mathcal{L}_v(\hat{v}_t^i, \hat{o}_t^i) + c||\theta||^2$

В таблице ниже можно посмотреть сравнение разных моделей

Предсказание чемпиона, которого выберет игрок

POP - простой бейзлайн, возвращающий чемпиона, которого игрок выбирал чаще всего за последние игры
NCF - фиксирует нелинейные взаимодействия между игроками и чемпионами через MLP с неявной обратной связью
DMF - оптимизирует Latent Factor Model на основе явного коэффициента выбора чемпиона каждым игроком
S-POP - вариант POP, который ранжирует чемпионов на основе последних n игр
Метрики использовались Hit Ratio (HR) и Normalized Cumulative Gain (NG)

Видно, что почти во всех позициях DraftRec работает лучше всего

На heat-map можно увидеть зависимость весов от других ролей. Сильнее всего зависят друг от друга ADC и SUP, так как они находятся всю игру рядом и им важна синергия. Так же видна зависимость (TOP, JGL) и (MID, JGL), что тоже объясняется внутриигровым взаимодействием

В таблице сверху сравниваются подходы, рекомендующие чемпиона по вероятности выбора $\hat{p}_{t, c}$ (DraftRec_p), по вероятности победы (DraftRec_v), и смешанная стратегия (DraftRec_p+v). При этом видно, что в первом случае вероятность победы возрастает по сравнению со вторым, то есть выбор комфортного для игры чемпиона влияет больше, чем композиция в целом. Но при этом вероятность победы для смешанной стратегии еще больше, что подтверждает пользу данной модели рекомендаций.

Пост написан для https://github.com/spbu-math-cs/ml-course

Краткий перевод статьи DraftRec: Personalized Draft Recommendation for Winning in Multi-Player Online Battle Arena Games