О том, как Hearthstone был взломан с помощью анализа больших данных

7-10 августа этого года в Лас Вегасе прошел очередной Defcon — ежегодная конференция, на которой собираются хакеры, специалисты по информационной безопасности и иже с ними. 

В рамках этой конференции представил свой доклад и Elie Bursztein, ведущий разработчик компании Google. В сферу его обязанностей входит защита пользователей Google от различного рода угроз в интернете. Но темой его доклада на Defcon стало отнюдь не это, а гораздо более близкая нам игра Hearthstone.

Нет, Elie Bursztein не вламывался на сервера Blizzard и не крал у Майка Морхейма из iCloud его селфи. Тем не менее, можно утверждать что он взломал игру с помощью математического аппарата и анализа больших данных. Почему я так говорю? Читайте до конца.

Суть выступления Эли сводится к двум пунктам:

  • Как найти в игре недооцененные Blizzard карты
  • Как предсказать ход соперника
ui2izyz9nq


Игра Hearthstone очень сложна. Сложна не с точки зрения правил, но как результат существования нескольких сотен уникальных карт. Построить идеально сбалансированную систему в таких условиях невозможно, разработчики ограничены в средствах и не могут оценить одну карту в 1.35 маны а другую в 1.33. Мы же, применив математический аппарат, можем среди карт «недооцененные» — такие, которые за одинаковое количество маны делают больше, чем другие похожие.
:cut:

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

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

6ob6flj3yd

Йети > Огра


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

Условия нашей модели:

1. Сила карты пропорциональна ее стоимости. Карта за 2 маны сильнее карты за 1 ману.
2. Сила карт возрастает приблизительно линейным образом. Если бы это было не так, к примеру если бы сила возрастала по экспоненте, то колоды построенные в расчете на конечную стадию игры, не имели бы шансов (очевидно, это неправда). По той же логике отбрасывается и противоположная ситуация, в которой шансов не имеют колоды, построенные на дешевых картах.
3. Дополнительный эффект карты является константой. Рывок считается одинаковым, к какой бы карте он не был приписан.
4. Карта имеет ценность сама по себе. Поскольку количество карт в колоде ограничено, один тот факт что вы имеете на руке карту, дает вам преимущество.
5. Сила карты вычисляется как сумма сил ее характеристик.

Используя описанную модель, рассмотрим еще один пример, в котором используются пять карт, обладающих рывком и божественным щитом. Для реальной модели пять карт это очень мало, из-за этого в примере появляется странный рассчитанный коэффициент «-1″ для единицы здоровья. Но показывать в примере таблицы из 100 элементов было бы ненаглядным, поэтому обойдемся пятью.

ylguchll4u

Имея эту систему уравнений, мы можем рассчитать значения коэффициентов, в среднем по больнице.
htjnjwxsnx

Теперь на руках у нас есть значения коэффициентов для рывка и так далее. Просуммировав эти значения для каждой конкретной карты, мы можем найти «недооцененные».

b18ohn7tek

Это простая модель и она годится для оценки обычных карт. Но что делать с картами, сила которых зависит от конкретной ситуации, к примеру с Сумеречным драконом? Или с легендарными картами, имеющими зачастую совершенно уникальные свойства? Здесь на помощь приходит анализ больших данных и немного магии.

Возьмем для примера Эдвина ван Клифа. Это сложная карта: ее сила зависит о того, сколько карт вы уже сыграли в этот ход.  

216/40 ван Клиф (тестирование колоды)
 

Как же оценить эту карту? Нам придется построить модель из предыдущего примера для каждого варианта ван Клифа. Рассчитанные для большого количества карт коэффициенты говорят нам, что 1 очко здоровья стоит 0.81 маны и 1 очко атаки стоит 1.14 маны.

wwux2ysjz

Как мы видим, ван Клиф уже оправдывает свою ману, если сыграть его 4/4. А теперь в дело вступает магия: автор доклада проанализировал 100000 реплеев игр и выяснил, при каких обстоятельствах ван Клиф появляется на доске в реальной жизни.
kz1q5zqmmm

За 100000 игр ван Клиф был сыгран ~3500 раз и его усредненная сила составляет 9.3/9.3, а «честная» цена — ~8.1 маны. И хотя такая цена кажется завышенной, но увеличение стоимости до 5 или 6 этой карте явно бы не помешало. Сейчас же ван Клиф просто подарок для своего обладателя.

Рассмотрим другой пример: Сумеречного дракона. Действуя по той же схеме, строим таблицу коэффициентов и обнаруживаем, что дракон становится хорошим ходом, когда у вас на руке есть 5-6 карт или больше.
heles8su3l

Теперь, используя статистику из реплеев, смотрим когда на самом деле дракона играют.
bl337b4vwe

Усредненная цена дракона оказывается 3.7 маны, что довольно близко совпадает с его реальной ценой (4).

Интересно в связи с этим вспомнить о нерфе, которому подвергался дракон. До нерфа он был 1/1, который получал +1/+1 за каждую карту на руке. Используя те же методы подсчета, мы можем определить что эффективная цена дракона составляла тогда 4.56 маны, следовательно нерф оказался правильным и эффективным.

Поиск недооцененных карт

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

Теперь мы можем пересчитать цену карт — по оси Х цена Близзард, по оси Y — наша цена. Посмотрим на график, зелеными точками отмечены недооцененные карты, красными — переоцененные.

ffpn1i9f3z

Где мои карты, чувак?

К черту все это, какие карты хорошие а какие плохие?

Самые недооцененные карты (сортировка по нормализованной разнице за очко маны):

6mjo952x3

Самые недооцененные карты (сортировка по абсолютной разнице между ценой Близзард и нашей ценой):
qwftzwoou4

Самые переоцененные карты (сортировка по нормализованной разнице за очко маны):

8b7mc8kvxu


Самые переоцененные карты (сортировка по абсолютной разнице между ценой Близзард и нашей ценой):
xu8kmcsb1n

Взаимодействие карт

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

Статистический анализ реплеев позволил выстроить логику синергии с помощью биграмм.
4hii5pbxj

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

А где взлом?

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

Elie Bursztein написал инструмент, который на основании статистического анализа сотни тысяч реплеев и приведенных выше расчетов смог довольно точно предсказывать руку оппонента, исходя из уже сыгранных им карт. Задачу сильно облегчил тот факт, что большая часть стада игроков не парится с экспериментами и изобретением собственных дек, а тупо копирует колоду у популярных стримеров или со всем известных сайтов. Собранная же колода довольно жестко определяет последовательность действий игрока.

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

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

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

d436szl388

И это действительно работает?

Представьте себе, да. Для каждого класса Hearthstone алгоритм обучался на базе 45000 реплеев, и далее тестировался еще на 5000 на предмет точности предсказания.   

Начиная с 4 хода точность предсказания программы составляла не менее 50%.
fg78kylt1l

Каким образом программа получает данные из игры? Есть несколько способов: сниффер пакетов, распознавание образов или анализ дебаг лога клиента.
p59wn0ml0d

Полная запись выступления (на английском языке):

PS. Сообщение из блога автора программы.

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

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

Это было непростое решение — мы потратили много времени на разработку программы, но в конце концов мы согласились с командой Hearthstone в том, что инструмент обнародовать не нужно.

Что насчет реплеев?

Помимо предсказания деки оппонента, в нашу программу был заложен функционал просмотра реплеев — для улучшения собственной игры и облегчения анализа данных. Разработчики заверили нас в том, что функция просмотра реплеев уже готовится ими самими в рамках обычного клиента. Это удержало нас от выпуска урезанной версии программы.

Автор Kermit . Источник 

скачать dle 11.0фильмы бесплатно

Комментариев 0