Занимательная математика в Hearthstone

Я любитель популярной компьютерной карточной игры Hearthstone, разработанной компанией Blizzard Entertainment. Однажды я задался вопросом: «Можно ли исходя только из правил, описывающих динамику переходов игрока между уровнями при проигрышевыигрыше партии, получить статистику распределения игроков по достигнутому ими уровню?»

Несмотря на то, что в сети есть огромное количество сайтов и wiki, посвящённых Hearthstone, поверхностный поиск результатов не дал. На глубокий поиск было жаль времени, поэтому я решил задачу «на коленке». Полагаю, это решение может стать темой для занятия в школьном математическом кружке.

Описание задачи

В рейтинговом турнире Hearthstone есть 25 уровней и специальный уровень «Легенда». Уровни состоят из подуровней — т.н. «звёзд», причём на разных уровнях число подуровней отличается:

• Уровни с 25 по 21 состоят из 2-х подуровней;
• Уровни с 20 по 16 состоят из 3-х подуровней;
• Уровни с 15 по 11 состоят из 4-х подуровней;
• Уровни с 10 по 1 состоят из 5-и подуровней;
• На «Легенде» подуровней нет.

Таким образом линейка уровней в рейтинге (далее — линейка) состоит из 96 подуровней (включая «Легенду»):

Рисунок 1

Новый игрок стартует в рейтинге с 25-го уровня. За выигрыш партии игрок получает «звезду» (иногда – две), т.е. повышает свой подуровень на 1 (или 2 соответственно).

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

Таблица 1

Очевидно, что «Трамплин» служит для вовлечения новых игроков, так как на «трамплине» есть только награда, но нет наказания за поражение. Кроме того, понятно, что население «трамплина» экспоненциально быстро «вымирает», поскольку правила неизбежно выталкивают игрока с «трамплина» в диапазон «Гонки с ускорением». Вероятность остаться на «трамплине» после 18 игр составляет ~29%, а после 27 игр – менее 1,5%.

«Гонка с ускорением» помогает игрокам с высоким мастерством и хорошими колодами быстрее добраться до «Нормальной гонки», где и начинается настоящее «рубилово». Ну и, наконец, «Легенда» — загончик для топовых игроков.

Мне хотелось найти 2 зависимости:

1. Вычислить вероятность получения игроком определённого уровня после определённого количества сыгранных игр;
2. Вычислить распределение всех игроков по уровням в зависимости от времени.

Выбор метода решения и инструмента

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

Идея решения следующая:

Пусть некоторый прямоугольный диапазон размером 96*1 (например диапазон Source!$C$3:$C$98 в прилагаемых файлах) представляет распределение количества игроков по линейке. Тогда, используя правила из таблицы 1, легко получить распределение, описывающее состояние, после того, как каждый игрок сыграл одну игру. Правила из таблицы 1 расположены в диапазоне Source!$D3:$D$98. Если «протащить» эти правила на нужное количество столбцов, то получившая таблица будет представлять изменение распределения игроков по уровням со «временем». Время в данном случае в кавычках потому, что здесь оно измеряется в «сыгранных играх».

Я начал с Open Office Calc, который всем хорош, но 3-D графики «из коробки» в нём выглядят убого (возможно, я просто не умею их готовить). В итоге решение реализовано на MS Excel и лежит здесь. Вариант для Open Office Calc там же — вполне функциональный, за исключением отсутствия 3-D графиков и отсутствия интерактивности в 2-D графиках.

Вероятность получения игроком определённого уровня

Рисунок 2

Приведённые графики описывают вероятность получить тот или иной уровень для игрока, стартовавшего с 25 уровня и сыгравшего 50, 130, 300, 450 или 570 игр соответственно. В Excel график интерактивный – можно поиграться с числами слева от диаграммы на вкладке «Interface», при этом графики (Рисунок 2) будут меняться.

В 3-D эволюция вероятности получения определённого уровня выглядит очень симпатично:

Рисунок 3

Здесь приведён срез с теми же минимальной и максимальной «временными» границами (50 и 570 игр), что и на рисунке 2.
Тот же график с другого ракурса:

Рисунок 4

Несколько неожиданным выглядит появление «ребра» на графиках в точке, соответствующей уровню 5 и 2 «звезды» (72-й подуровень по порядку). Данная точка является последней, на которую действует возможность попадания «с ускорением» после 3+ побед подряд.

Если посмотреть правила для 71 – 72 подуровней, то они выглядят следующим образом:
71 =1/8*C69+C70*3/8+0,5*C72
72 =1/8*C70+C71*1/2+0,5*C73
Здесь СNN- количество игроков на подуровне NN на предыдущем шаге:
— первый член обеспечивает «ускоренный перенос» с уровня «текущий -2»;
— второй член обеспечивает обычный переход при победе на уровне «текущий -1»;
— третий член обеспечивает переход с вышележащего уровня при поражении.

Разница в 1/8 в коэффициенте при втором члене обусловлена тем, что, начиная с 5-го уровня (он же 71-й порядковый подуровень), независимо от числа побед подряд, повышение подуровня проходит только на 1, т.е. даже если победа на 71-м подуровне была для игрока 3-й, он перейдёт лишь на 72-й подуровень.

Эта небольшая на первый взгляд добавка приводит к тому, что «поток игроков» на 72-й подуровень чуть выше среднего, соответственно чуть выше будет и поток игроков с 72-го подуровня в его окрестности, т.е. эффект повышения потока игроков на 72-й подуровень самоусиливается, что и приводит к появлению этого замечательного ребра.

Вычисление распределения всех игроков по уровням

Очевидно, что игроки различаются по количеству игр, которые они играют за одно и то же время. Более увлечённые игроки играют больше, казуальные – меньше.

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

Введём обозначения:

• P(L,i) ) — вероятность получения игроком определённого уровня (L) после заданного количества игр (i) (графики приведены на рисунках 2-4)
• N – максимальное количество игр, сыгранное самым увлечённым игроком. Заметим, что N здесь играет роль времени. Конечно, это не обычное время. Однако между обычным временем t и N есть следующее соотношение: , поэтому N в качестве «времени» вполне годится.
• Z (i, N) – вероятность того, что игрок сыграл i игр к моменту «времени» N или распределение игроков по количеству сыгранных игр за «время» N.
• D (L,N) – искомая вероятность нахождения игрока на уровне L, в момент «времени» N или распределение игроков по уровням на момент «времени» N.

Тогда

Сразу скажу, что данных о функции Z(i, N) у меня нет. Но можно немного поспекулировать на эту тему.

Единственное, что пришло мне в голову: «20% людей выпивают 80% пива». Возможно, «20% игроков в Hearthstone играют 80% игр»? То есть гипотеза состоит в том, что распределение игроков по количеству сыгранных игр – это дискретное распределение Парето, или, более точно – распределение Ципфа (см. en.wikipedia.org/wiki/Zipf%27s_law).

Введём обозначения:

1. Вспомогательная функция
   
2. Нормировочный множитель (для момента «времени» N)
   

Тогда распределение Ципфа со степенным показателем s:

Посмотрим на графики искомой функции D (L,N) в предположении, что распределение игроков по количеству сыгранных игр это распределение Ципфа с показателем степени 1.

Здесь и на следующем графике отображена D (L,N) в моменты «времени» N с 50 до 700.

Рисунок 5

Рисунок 6

Выглядит довольно уродливо, хотя и понятно почему – значительная часть игроков в соответствии с распределением Ципфа осталась на «трамплине». Ну что ж, спекулировать – так по полной. Построим модифицированное распределение Ципфа-Мандельброта (см. en.wikipedia.org/wiki/Zipf%E2%80%93Mandelbrot_law).

1. Заменим вспомогательную функцию

Идея введения целочисленного параметра Startshift состоит в следующем: начало «действия» стандартного поведения распределения Ципфа сдвинуто на Startshift шагов.

Действительно, представляется неправдоподобным, что игрок, прошедший все трудности обучения и только вышедший на рейтинговые игры, с высокой вероятностью бросит играть после одной-двух рейтинговых игр. Можно предположить, что начало «действия» распределения Ципфа примерно совпадает с началом трудностей в продвижении в рейтинге, т.е. с моментом, когда вероятность покинуть «трамплин» превысит ½ (это означает, что startshift=18). Кроме того, из определения вспомогательной функции следует, что общее число игроков «случайно зашедших в Hearthstone» (т.е. сыгравших ≤Startshift игр) совпадает с числом игроков на максимуме распределения. Всё это, конечно, чистая спекуляция, но почему бы не посмотреть, что получится?

Параметр Мандельброта q введён без какого-либо обоснования, на всякий случай.

2. Нормировочный множитель (для момента «времени» N)

Тогда модифицированное распределение со степенным показателем s, параметром Мандельброта q и параметром «стартового сдвига» Startshift:

Посмотрим, что получается при параметрах, приведённых в нижней части графика:

Рисунок 7

Для ручных экспериментов график в Excel сделан интерактивным – можно поиграться с параметрами распределения и отображаемыми «временами» слева от диаграммы на вкладке «Interface», при этом графики (Рисунок 7 и Рисунок 8) будут меняться.

Рисунок 8

И наконец, последний рывок на сегодня. Попробуем подобрать параметры распределения, используя «реальные» данные (http://www.reddit.com/r/hearthstone/comments/23ed7l/how_good_are_you_at_constructed_ladder/). Это результаты какой-то симуляции, детали которой мне неизвестны, неясно, в частности, в какой момент «времени» N проведено измерение и т.д. Это единственное, что я нашёл. Но я не очень старался искать. Надеюсь, читатели статьи подскажут источник более релевантных данных.

Итерационная обработка данных надстройкой solver и ручная подгонка дали следующие значения параметров распределения: s=1,19; q=0,287; Startshift =110. Startshift ожидаемо большой, поскольку в исходных данных симуляции отсутствует информация о населении уровней 25-21, т.е. «трамплин», очевидно, не симулировался.

Финальные картинки:

Рисунок 9

Рисунок 10

Заключение

В заключение повторюсь, что задача, которую я стал решать из чистого любопытства, показалась мне неплохой темой для занятия в школьном математическом кружке. Считаю важным для будущих инженеров и учёных умение использовать для решения внезапно возникающих задач все имеющиеся подручные инструменты: бумагу и карандаш, электронные таблицы, пакет «WOLFRAM MATHEMATICA». Надеюсь, настоящий пример применения электронной таблицы будет кому-нибудь полезен.

При желании преподаватель может проложить мостики от этой задачи ко множеству тем.

Навскидку:

1. Теорвер – распределение Парето – Дзета функция – John Derbyshire. Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics
2. Численные методы решения дифуров в частных производных. (кстати – задача для продвинутых школьников: покажите, что P(L,i) в диапазоне «Нормальная гонка» аппроксимирует некоторое частное решение уравнения в соответствующем масштабе, а в диапазоне «Гонка с ускорением» — уравнения
3. Выбор оптимального для задачи вида функции невязки.

Также можно придумать какие-нибудь расширения к данной задаче. Например, такие:

1) Когда заканчивается сезон, то игроки, достигнувшие определённых уровней в прошлом сезоне, получают некоторую фору. Например, при окончании сезона на уровне 4 игрок получает 21 «звезду», т.е. стартует в новом сезоне не с 25 уровня, а с уровня 17.**- он же 21-й порядковый подуровень (см. Рисунок 1). Уверен, что соответствующие цифры, описывающие зависимость размера форы от достигнутого уровня, легко найти в сети.

Вопросы:

1. Как изменятся P(L,i) и D (L,N) при учёте форы на старте сезона?
2. Сходится ли ряд функций D(L,N, номер сезона) к чему-нибудь при номере сезона, стремящемся к ∞? Если да, то какие ограничения это накладывает на Z (i, N)?
3. Достаточно ли Z (i, N) для корректного ответа на 2-й вопрос?

2) Придумать какую-нибудь внятную теорию для вычисления функции Z(i, N).

Автор: kokonT

Источник