[Kermit]

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

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

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

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

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

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


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

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

Йети > Огра

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А где взлом?

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

[Святойоттец]

Все можно свести к цифрам,а цифры упорядочить.
Очень занимательная статья!

[Briz]

Лучше б обнародовал.

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

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

[Sternness]

Лучше бы они такую программу для покера написали и отправили бы исключительно мне одному )

[alsione]

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

[Kitea]

И как разобраться в этом ?

[Хермеус Мора]

Моя жопа после 200+ игр, впринципе так же может определить примерно к 5-6 ходу карты хода противника на 50%, которыми он будет играть. Со мной не связывались разработчики, но по этическим причинам я не могу выложить её 

[Dr.Z]

Представляю в какой алгебраический ад превратилась бы игра, если мана состояла из десятичных дробей

[isource]

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

2) Второй пункт как бы опровергает тезис про игру про рандом, раз уж даже закрытые карты предсказывает. Впрочем, как и указано в статье, после наигрывания достаточного количества игр "в текущей мете" чуйка сама просыпается.

Могли бы и опубликовать программу - ничего страшного бы не случилось. По факту, ничего и не взломали, читающие память программы для арены и так есть давно.

[Zaltir]

И это тревожный звоночек для Хс, я бы сказал. Сотрудники Близзард абсолютно правы в том что обнародование подобной программы снизит интерес к игре. да что там снизит - оно его убъёт просто.

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

А тут против него сел играть новичок с "прогой". Этот новичок собрал топ-колоду (ок, задонатил, видимо) и следует подсказкам программы, которая дает советы не хуже того же про. и у киберспортсмена справедливо подгорает, потому как он весь этот опыт сам добыл и законно пользуется, а оппонент его просто скачал подсказчик. и сделать с этом профессионал ничего не может. и не потому что нет способностей, а потому что сама игра ограничила его правилами и не учитывает его человеческий фактор в своей механике.

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

И вот теперь перед разработчиками из Близзард стоит очень нетривиальная задача о том как сделать игру способной реагировать на человеческий фактор и быть непросчитываемой подобным образом. Частые ребалансы? Ещё более развитый фактор удачи? Поощрение игры особыми (нестандартными) колодами? Какое-то совершенно гениальное решение?

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

Если проще - даешь профессиональным киберспортсменам быть профессиональными киберспортсменами! =)

[Sternness]

даешь профессиональным киберспортсменам быть профессиональными киберспортсменами! =)

В ХС киберспортом даже и не пахнет. Это, бесспорно, интересная игра, но не соревновательная ни разу. Чемпионаты по ней проводят исключительно на волне успеха самой игры. Да и колоды там у всех одинаковые. Я могу выиграть подобный чемпионат с тем-же процентом, что и любой другой участник.

[Амортенция]

Интересная статья)

[m4rv1n]

интересно, спасибо надо же, кто-то ведь заморочился
 
вообще, мне кажется, для хс это болезнь роста. даже при всей видимой и невидимой простоте игры. объясняется это не очень большим кардпулом и отсутствием сложных механик. проигроки мтг играют известными колодами с парочкой собственных новшеств. строго говоря (без учета знания метагейма и подготовки к матчам) это и делается для того, чтобы иметь в рукаве туз - карту, которая встроенная в мозг "программа-предсказатель" (чуйка^) не рассчитывает увидеть сыгранной в числе наиболее вероятных. иногда таким образом рождаются новые подвиды колод.

короче говоря лет через 10, я бы сказал, аналогичное исследование над хартстоуном врядли принесет такие "вау-эффектные" плоды.
но парни круты ваще \(^^)/

[Eldhenn]

Вообще-то ХС-боты уже существуют, и сравнительно давно. Они туповатые, но дейлики народ с ними делает.

[xicecool]

Надеюсь, что эта программа никогда не попадёт в сеть. Хватило того, что натворил NoGCD в своё время в вов(середина-конец вотлка) как в pve так и в pvp.