Pull to refresh

Data Mining в онлайн играх

Reading time 11 min
Views 32K
АионВо всех онлайн сервисах и играх самая большая доля аудитории уходит прямо на старте – в первые же минуты и часы знакомства с продуктом. Этой теме уже посвящены сотни книг и статей с самыми различными гипотезами успеха и причин лояльности аудитории – уникальность, простота, юзабилити, бесплатность, обучение или инструкция, эмоциональность, и еще множество факторов считаются крайне важными.

Мы захотели узнать, почему уходят игроки и можно ли предсказать их уход. Предмет исследования – ММОРПГ Аион, однако наши результаты оказались применимы к широкому кругу игр и онлайн сервисов.

Чуть ли не британскими учеными установлено, что у пользователя очень короткая память. Сегодня он ушел из игры, а завтра уже не вспомнит, что он вообще ее устанавливал. Если игрок ушел, то действовать надо немедленно. Но как нам определить, действительно ли ушел человек, или просто сегодня вечером пьет пиво с друзьями и в игре не появится? Идеальным случаем было бы предсказание потенциального ухода еще до того, как пользователь нас покинул. И даже до того, как в его сознании зародилась мысль, что Аион не похож на торт. Наверное, такая задача тоже решаема, однако мы ставили более реалистичную цель – оперативно предсказывать уход в день последнего логина в игру. Уходом назовем неактивность человека в течение недели – и мы как раз не хотим ждать эти 7 дней, а желаем знать как можно скорее, что игрок больше не вернется. Мы желаем знать будущее!

Техническая сторона


Для анализа у нас было море информации – у Аиона лучшая система логирования, что я видел среди корейских игр, мы буквально знаем об игроке каждое его движение, каждый чих и каждый след, который он оставил на сервере. Период для анализа – первые девять уровней в игре, около 10 стартовых часов геймплея – за этот период отваливалась примерно половина всех новичков.

На проект выделили часть ресурсов нашей системы аналитики – два блейд сервера Dual Xeon E5630 32Gb RAM, 10 Tb холодного хранилища для исходных и промежуточных данных, 3 Tb горячего хранилища в RAID10 SAS массиве для рабочих данных. Оба сервера под MS SQL 2008R2 – один под БД и один под Analysis Services. Программная часть решения – стандартный пакет Business Intelligence от Microsoft, входящий в SQL Server.

Фаза 1 – я все знаю!


Поскольку я много лет был геймдизайнером и провел под сотню плейтестов, то был уверен, что и сейчас экспертное мнение даст 90% ответов почему уходят игроки. Не научился пользоваться телепортацией, надоело бегать ногами – ушел. Умер от первого же монстра в игре – ушел. Не выполнил вторую миссию, застрял и не знает что делать – ушел. Аион, при всем его качестве и технологичности, не самая дружелюбная к новичку игра. Это черта всех корейских игр, рассчитанных на хардкорную и гиперсоциальную среду корейских игроков, а не одиноких скучающих российских казуальных пользователей.

Я одел шляпу «обычного юзера» и прошел бесплатное начало игры за обе расы и несколько классов, выписав все корявости, нелогичности и проблемы, сформировав первый список гипотез для проверки:
  • Раса и класс персонажей. Предполагалось, что класс будет самым сильным фактором, поскольку геймплей за Целителя разительно отличается от косящего всех направо и налево Мага.
  • Играл ли человек в другие игры – у нас единый аккаунт для всех проектов, так что легко проследить кросс-конверсию.
  • Попробовал ли игрок более 1 персонажа – познал ли другие классы и расу.
  • Сколько раз он умер на уровнях 1-4, 5-7 и сколько раз умер всего за триал.
  • Вступал ли в группы с другими игроками, в том числе с высокоуровневыми (т.е. явно знакомыми по другим играм или в реальной жизни)
  • Сколько на компьютере оперативной памяти, поскольку Аион требователен к ресурсам
  • Получал ли персонаж почту и вступал ли в гильдию – явный признак «твинков», вторичных персонажей, созданных уже активными и опытными игроками.
  • Сколько заданий выполнил персонаж к данному уровню, сколько заданий отменил и сколько просто не взял
  • Проходит ли игрок внутриигровые опросы, за которые дают хорошие плюшки
  • Какими умениями персонаж пользуется в бою и убивает монстров

Список получился внушительным, расписанный до деталей, и способов расстроить новичка до потери желания играть было найдено множество. Заводим в модель первые пару гипотез, предсказываем булеву переменную is_leaver – уйдет ли игрок прямо сейчас, на 7-ом уровне:


Как читать lift chart: нижняя наклонная прямая линия — это результат генератора случайных чисел, предсказывающего нашу булеву переменную научным методом бросания монетки. Верхняя линия, быстро доходящая до 100% — это оракул, идеальный предсказатель будущего. Между ними находится неровная, трепещущая ниточка – это наша модель. Чем ближе график к идеальной линии – тем выше предсказательная точность модели. График приведен для 7-го уровня, но картина похожая от первого до девятого.

Fatality! Наша первая модель предсказывает уходящих игроков чуть-чуть лучше метода орла и решки. Отправляем в модели оставшиеся гипотезы, чистим данные, процессим:


Уже лучше, но все равно точность чуть выше 50%. А если посмотреть детальнее recall (ошибки второго рода), то картина грустная:


Эта же таблица русским языком – из каждых 100 предсказанных моделью уходов 49 будут ложные (игрок никуда уходить не собирался), точность модели составит 1008/(1008+982)=51%. При этом еще часть реальных уходов модель вообще пропустит – примерно 28% из истинно ушедших [391/(391+1008)=28%]. Внимание, это не каноническое определение recall, но такая формула нагляднее.

Итог фазы 1: все изначальные идеи провалились, предсказание не работает. Шеф, все пропало!

Фаза 2 – мы ничего не знаем


Полный разгром и бегство с поля боя, и вечный вопрос «Что делать?». На помощь приходит наивный алгоритм Байеса – максимально человеко-читаемый и понятный из всех data mining классификаторов. Анализ Байесом показал, что выбранные гипотезы довольно слабо характеризуют ушедших и остающихся игроков, то есть я ошибся с выбором изначальных предпосылок. Но, поиграв с глубиной и чувствительностью другого алгоритма, дерева принятия решений, стало понятно – есть правильные гипотезы, дерево ветвится по ним, но факторов решительно недостаточно – рост дерева прерывается на 2-3 ветке.

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

Я собрал брейншторм с командой проекта, где мы фонтанировали идеями – кто же наши новички, как они играют, чем они отличаются друг от друга. Вспоминали истории как наши подруги и жены знакомились с Аионом, и что из этого вышло. Итогом брейншторма стал дополненный список индивидуальных гипотез (пользовался ли игрок телепортацией, расширил ли себе инвентарь, привязал ли точку воскрешения и т.д.) и новая идея – хорошо бы посмотреть насколько вообще отличается активность уходящих от остающихся в игре.

Для изучения средней активности мы рассчитали несколько метрик:
  • число монстров, убитых на данном уровне
  • число выполненных заданий на уровне
  • время в минутах, проведенное на каждом уровне

На этом этапе заодно была переделана ETL часть проекта (загрузка, преобразование и очистка данных). Наш SQL-гуру Илья сделал на SSIS анализатор-конструктор, в который легко подключаются новые события из логов игры. Логов гигабайты, так что недостатка информации не было, а новые гипотезы придумывались каждый день.

Загрузили, обучили, верифицировали, проанализировали. Не буду грузить вас морем lift chart’ов по каждому уровню и каждой модели, приведу сразу обработанные и проанализированные данные:


Пик точности на 9 уровне был связан с внутренней особенностью игры на момент исследования.

В целом картина улучшилась в области 2-4 уровней, но 6-8 ниже плинтуса, с такой точностью данные нам просто бесполезны.

Дерево принятия решений бодро показывает – факторы активности являются самыми важными для предсказания ухода. По сути, три величины – время на уровне, убитые монстры и сделанные задания – определяют львиную долю уходов. Остальные факторы добавляют не более 5% точности. Также дерево по-прежнему остается голым, крона обрывается на третьей ветке – то есть модель жаждет больше релевантных метрик. Что еще непонятно – точность трех алгоритмов сильно меняется от уровня к уровню.

Итог фазы 2: успех идеи об измерении средней активности, а не индивидуальных факторов. Но точность предсказания все еще неудовлетворительна. Путь по граблям вывел к правильной последовательности анализа результатов – сначала факторы и корреляции (Байес), потом их влияние на итог (дерево решений).

Фаза 3 – мы знаем куда копать


Воодушевленный прогрессом, я наметил три вектора развития проекта – больше метрик общей активности, больше специфических метрик индивидуальной эффективности, и более глубокое изучение инструментов Microsoft BI.

Поэкспериментировав с активностью, мы остановились на следующем наборе:
  • Проведенное время на текущем уровне, на предыдущем уровне и суммарное время в игре к текущему моменту
  • Скорость убивания монстров – штук в минуту на текущем уровне, предыдущем и всего.
  • Скорость выполнения заданий в минуту – аналогично мобам.
  • Среднее время в игре на игровой день, проведенных дней в игре и НЕпроведенных дней (например, человек входил в понедельник и среду – пропущен 1 день).

Эти метрики дали хорошее снижение пропущенных случаев, практически в полтора раза. Дерево решений начало ветвиться до 9 узлов, что показывает релевантность метрик. Плюс хорошим признаком была унификация деревьев для разных уровней – если в прошлой фазе, как я писал, от уровня к уровню сильно скакала точность алгоритмов, то теперь было явно видно – дерево бьется на первом-втором-третьем узле ровно по одним и тем же показателям, независимо от уровня персонажа. И наивный Байес уже отстает от дерева и нейронной сети процентов на 5-10.

Пришлось повозиться с новыми индивидуальными метриками, связанными с глубиной геймплея и эффективностью игры, например процентом автоатаки. Мы сегментировали персонажей по классам (воины направо, целители налево) и для каждого класса рассчитали 25, 50 и 75-й перцентили распределения по %% автоатаки, и разбили всех на 4 категории. Теперь данные нормализованы, и игровые классы можно сравнивать между собой – на вход data mining моделей уходит номер категории.

В онлайн играх персонажи убивают врагов разными заклинаниями и способностями. Автоатака – бесплатный, самый базовый (и слабый) удар, дающийся с рождения. Если игрок эффективен, то он применяет способности своего персонажа – и %% автоатаки среди всех его ударов будет не очень высоким. Однако сильно от игровой механики зависит, какой же именно этот процент для разных классов. В Аионе получился разброс от медианы в 5% для мага до 70% для воина, и даже внутри класса дисперсия высока.

Индивидуальные метрики закрепились на глубине седьмого-девятого узла дерева, т.е. они прибавили пару процентов к точности предсказания, но не улучшили ситуацию кардинально. Следующим шагом было штудирование книги Data Mining with Microsoft SQL Server 2008 на предмет тонкостей работы с Analysis Services. Сама по себе книга помогла только с настройкой чувствительности дерева (от силы плюс один-два процента прироста точности), но натолкнула на мысль о правильной дискретизации.

В примере выше с автоатакой мы сделали ручную дискретизацию данных – разбиение на категории по каким-то признакам. SQL сервер автоматически делает дискретизацию несколькими способами. Экспериментальным путем я быстро понял, что алгоритм разбиения и число сегментов очень сильно влияют на предсказательную силу модели. Ручное изменение числа сегментов сильно влияет на форму и точность дерева. На ручную подгонку я потратил неделю, скрупулезно для каждой структуры каждого уровня (а это 9 уровней по 30+ метрик) экспериментируя с числом сегментов. Для каких-то метрик оптимальным было 7 сегментов (например, время на текущем уровне), для каких-то 12 (суммарное время в игре), для каких-то больше 20 (число убитых монстров).

Ручная настройка дала сильный прирост предсказанных значений – точность при этом не сильно повысилась, но модели стали делать заметно меньше пропусков, а результаты дерева сравнялись с нейронной сетью:

Итог фазы 3: мы вышли на приемлемые показатели точности и аккуратности и узнали много интересного про нашу игру и наших игроков.

Фаза 4 – только победа


Я, честно говоря, думал, что потолок достигнут – дерево ветвится глубиной до 9-12 узлов, аккуратность сильно улучшена. Новые гипотезы точность никак не повышают, новые факторы никакой информации не дают. В принципе, общая точность в 78% и recall 16% — это удовлетворительно для начала работы с игроками. Я бы, наверное, не стал при таких цифрах давать бесплатную подписку для удержания в игре, но сообщать игроку релевантную информацию уже можно без особых ошибок.

Помощь пришла неожиданно – поскольку data mining проект длился уже третий месяц, у нас несколько устарели логи – игра же изменилась за это время. Подгрузив немного свежих данных, а заодно в очередной раз доработав ETL процедуры, мы заметили изменения в моделях. На новых данных они вели себя иначе – при, в общем-то, прежней точности и аккуратности, разбиения дерева были другими. На этом этапе все три алгоритма обучались очень быстро – минуту на каждый уровень из 9, и накормить их дополнительным набором данных просто.

Сказано – сделано, выгружаем вообще все накопленные за 3 месяца данные и одним махом направляем модели обучаться (процесс стал занимать не минуту, а целых пять на каждый уровень – не критично). Очередной раунд ручной подгонки, и вот итог:



Увеличив объем обучающих данных, мы сделали процесс обработки дольше, но зато какой отличный результат!

С первым уровнем, к сожалению, немного можно сделать – около половины уходов, как сказал бы Авинаш Кошик, “I came, I puked, I left”. У нас есть данные о буквально паре действий игрока – и дальше он закрывает клиент игры и никогда не возвращается обратно.

Напоминаю, что все исследования выше – это обучение на накопленных исторических данных. Теперь я хочу проверки боем! Проверяем на живых данных – берем свежих, сегодняшних пользователей, прогоняем через модель и сохраняем результат предсказания. Через неделю сравниваем предсказания модели с объективной реальностью – кто из недельной давности новичков действительно ушел, а кто в игре остался:



Самое интересное


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

Достигнута ли вторая цель, знаем ли мы теперь почему уходят игроки? Нет. И это самый странный для меня результат – при отличной вероятности предсказания ухода, вопрос «А почему?» остается без ответа. Помните, я начал проект с выписывания гипотез об индивидуальных факторах, вида:
  • Раса и класс персонажа
  • Играл ли человек в другие игры Инновы
  • Попробовал ли игрок более 1 персонажа
  • Сколько раз он умер на уровнях 1-4, 5-7 и сколько раз умер всего
  • Вступал ли в группы с другими игроками
  • Сколько на компьютере оперативной памяти
  • Получал ли персонаж почту и вступал ли в гильдию
  • Сколько заданий выполнил персонаж к данному уровню, сколько заданий отменил и сколько просто не взял
  • Проходит ли игрок внутриигровые опросы
  • Какими умениями персонаж пользуется в бою и убивает монстров
Таких факторов было проверено множество — более 60. Ни один из них не является сколь-нибудь существенным и определяющим уход игрока. Ни один! Не нашли мы в игре какого-то магического барьера, который вызывает отток игроков.

Самый главный фактор? Прошел ли игрок первые 7 уровней в первый же день знакомства с игрой (7 уровней – это примерно 3 часа игры). Это ключевой предсказатель ухода – если в первую же сессию игрок не увлекся и не потратил 3 часа, то очень вероятно, что игру он бросит. Следующая по силе группа факторов – это общая активность игрока:
  • Проведенных минут в игре на текущем уровне, прошлом и суммарно
  • Минут нахождения в игре в среднем за игровой день
  • Убитых монстров в час на текущем уровне, прошлом и всего
  • Скорость выполнения заданий – штук в час

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

Победа!


За два месяца, с нуля – никто из нас никогда даже близко с data mining не сталкивался, — с помощью двух книг и желания попробовать что-то новое, на основе созданной нами мощной, но пассивной системы аналитики в Иннове, мы сделали инструмент, активно смотрящий в будущее. В отличие от обычной отчетности и аналитики трендов на исторических данных, мы в 6 утра уже знаем почти наверняка о наших вчерашних новичках в Аионе – увидим ли мы их сегодня в игре или нет. И можем действовать, пока еще не поздно.

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

PS. Если тема хабравчанам интересна, то можно продолжить – про предсказание уходов старичков, сегментацию и кластеризацию, миграцию между кластерами и другие data mining проекты, которые мы сделали в уходящем году.

PS2. Вторая книга, рекомендую абсолютно всем — Программируем коллективный разум
Tags:
Hubs:
+198
Comments 87
Comments Comments 87

Articles